Стратегии планирования процессора
1. Первый пришел — первый обслуживается FIFO — first come — first served (FCFS). FCFS является наиболее простой стратегией планирования процессов и заключается в том, что процессор передается тому процессу, который раньше всех других его запросил. Когда процесс попадает в очередь готовых процессов, РСВ присоединяется к хвосту очереди.
Среднее время ожидания для стратегии FCFS часто весьма велико и зависит от порядка поступления процессов в очередь готовых процессов.
2. Стратегия «наиболее короткая работа выполняется первой» SJF — Shortest Job First. Это стратегия, позволяющая процессу из очереди выполняться первым. Стратегия SJF снижает время ожидания очереди.
Стратегия SJF часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим.
3. Приоритетное планирование. Описанные ранее стратегии могут рассматриваться как частные случаи стратегии приоритетного планирования. Эта стратегия предполагает, что каждому процессу приписывается приоритет, определяющий очередность предоставления ему CPU. Например, стратегия FCFS предполагает, что все процессы имеют одинаковые приоритеты, а стратегия SJF предполагает, что приоритет есть величина, обратная времени последующего обслуживания.
Обычно приоритет — это целое положительное число, находящееся в некотором диапазоне, например от 0 до 7 или от 0 до 1024. Будем считать, что чем меньше значение числа, тем выше приоритет процесса.
Главный недостаток приоритетного планирования заключается в возможности блокирования на неопределенно долгое время низкоприоритетных процессов.
Известен случай, когда в 1973 году в Массачусетском технологическом институте при остановке компьютера IBM 7094 в очереди готовых процессов были обнаружены процессы, представленные в 1967 году и все еще не выполненные.
Вопросы:
Что такое процесс, ресурс, процессор?
Что такое процесс в вычислительной системе? Какие типы процессов вам известны?
Какие состояния процессов вам известны?
Понятие очереди.
Взаимодействие процессов?
Стратегии планирования процессов.
Тема 4.2 Управление невиртуальной памятью
Студент должен:
иметь представление:
об аппаратных и программных средствах защиты памяти;
знать:
принципы распределения памяти;
способы защиты памяти;
проблемы фрагментации памяти
Механизм разделения центральной памяти. Разделение памяти на разделы. Распределение памяти с разделами фиксированного размера. Распределение памяти с разделами переменного размера. Способы защиты памяти. Проблема фрагментации памяти и способы ее разрешения.
Со времен создания первых компьютеров основная память (ОЗУ) считается относительно дорогим ресурсом и разработчики систем стараются оптимизировать ее использование. В частности, необходимо решить, будет ли ОС располагать в оперативной памяти только один процесс или несколько. При работе с несколькими процессами следует подумать над тем, как разделять между ними память: выделять им одинаковые порции или разные и т.д.
Методы управления памятью:
1. Свопинг (swapping). Свопингом (перекачкой) называется метод управления памятью, основанный на том, что все процессы, участвующие в мультипрограммной обработке, хранятся во внешней памяти.
Процесс, которому выделен CPU, временно перемещается в основную память (swap in/roll in). В случае прерывания работы процесса он перемещается обратно во внешнюю память (swap out/roll out).
Замечание: при свопинге из основной памяти во внешнюю (и обратно) перемещается вся программа, а не ее отдельная часть.
Свопинг иногда используют при приоритетном планировании CPU. В этом случае с целью освобождения памяти для высокоприоритетных процессов, низкоприоритетные процессы перемещаются во внешнюю память.
Основное применение свопинг находит в системах разделения времени.
В начале каждого временного кванта блок управления памятью выгружает из основной памяти процесс, работа которого была только что прервана, и загружает очередной выполненный процесс.
Пример. Пусть очередной загружаемый в память процесс имеет размер 100 Кбайт. Диск позволяет читать данные со скоростью 1 Мбайт в секунду, следовательно, 100 Кбайт могут быть загружены за 100 мс. Будем считать, что для первоначального подвода головки чтения-записи потребуется 8 мс. Таким образом, операция свопинг займет 108 мс, а общее время свопинга — 216 мс.
Недостаток «чистого» свопинга заключается в больших потерях времени на загрузку или выгрузку процессов. Поэтому в современных операционных системах используются модифицированные варианты свопинга.
2. Смежное размещение процессов. Методы размещения процессов в основной памяти по отношению к расположению участков памяти, выделенных для одной и той же программы, делят на два класса. Первый — метод смежного размещения, второй — метод несмежного размещения.
Смежное размещение является простейшим и предполагает, что в памяти, начиная с некоторого начального адреса, выделяется один непрерывный участок адресного пространства.
При несмежном размещении программа разбивается на множество частей, которые располагаются в различных, необязательно смежных участках адресного пространства.
1) Однопрограммный режим при смежном размещении. Рис. 4.4 иллюстрирует смежное размещение одной программы в основной памяти.
При смежном размещении размер загружаемой программы ограничивается размером ОЗУ. Для того чтобы при смежном размещении загружать программы, размеры которых превышают размеры ОЗУ, используют метод оверлейных сегментов (overlay segments).
Рисунок 4.4 - Однопрограммный режим
Рисунок 4.5 - Оверлейные структуры программ
2) Метод оверлейных сегментов. Программист разделяет программу на логические блоки. Когда программе становится ненужным какой-либо блок, программа может удалить его из памяти и разместить на его месте какой-либо другой блок или его часть. (Рис. 4.5)
3)Мультипрограммирование с фиксированными разделами (MFT — Multiprogramming with a fixed number of tasks) предполагает разделение адресного пространства на ряд разделов фиксированного размера. В каждом разделе размещается один процесс (рис. 4.6).
В этом случае, если соответствующий адресам процесса раздел занят, процесс остается в очереди во внешней памяти даже в том случае, когда другие разделы свободны.
Рисунок 4.6 - Режим мультипрограммирования с фиксированным количеством разделов (задач)
Уменьшить фрагментацию памяти при мультипрограммировании с фиксированными разделами можно, если загрузочные модули создаются в перемещаемых адресах. Такой модуль может быть загружен в любой свободный раздел после соответствующей настройки.
При мультипрограммировании с трансляцией в перемещаемых адресах имеются две причины фрагментации. Первая — размер загруженного процесса меньше размера, занимаемого разделом (внутренняя фрагментация), вторая — размер процесса в очереди больше размера свободного раздела, и этот раздел остается свободным (внешняя фрагментация).
Для защиты памяти при мультипрограммировании с фиксированным количеством разделов необходимы два регистра. Первый регистр верхней границы (наименьший адрес), второй — регистр нижней границы (наибольший адрес).
Рисунок 4.7- Режим мультипрограммирования с фиксированным количеством разделов (фрагментация памяти)
Рисунок 4.8 - Регистры границ для MFT
Прежде чем программа в разделе N начнет выполняться, ее граничные адреса загружаются в соответствующие регистры. В процессе работы программы все формируемые ею адреса контролируются на удовлетворение неравенства а < Адр. < б.
При выходе любого адреса программы за отведенные ей границы работа программы прерывается.
Мультипрограммирование с переменными разделами (multiprogramming with a variable number of tasks — MVT) предполагает разделение памяти на разделы и использование загрузочных модулей в перемещаемых адресах, однако границы разделов не фиксируются.
По мере завершения работы программы освобождаются отдельные разделы. В том случае, когда освобождаются смежные разделы, границы между ними удаляются и разделы объединяются.
За счет объединения или слияния смежных разделов образуются большие фрагменты, в которых можно разместить большие программы из очереди.
Мультипрограммирование с переменными разделами и уплотнением памяти. Уплотнением памяти называется перемещение всех занятых разделов по адресному пространству памяти таким образом, чтобы свободный фрагмент занимал одну связную область (рис. 4.9).
Рисунок 4.9 - Режим уплотнения памяти
3. Страничная организация памяти (paging) относится к методам несмежного размещения процессов в основной памяти. Основное достоинство страничной организации памяти заключается в том, что она позволяет свести к минимуму общую фрагментацию за счет полного устранения внешней фрагментации и минимизации внутренней фрагментации.
Базовый метод. Адресное пространство основной и внешней памяти разбивают на блоки фиксированного размера, называемые страничные рамки (frames). Логическое адресное пространство программы также разбивается на блоки фиксированного размера, называемые страницами (pages). Размеры страничных рамок и страниц совпадают. Процесс загружается в память постранично, причем каждая страница помещается в любую свободную страничную рамку основной памяти.
Разбиение адресного пространства на страницы осуществляется вычислительной системой незаметно для программиста.
Каждый адрес, генерируемый процессором, состоит из двух частей: П -номер страницы (page number) и Д — смещение в пределах страницы (offset). Номер страницы может использоваться как индекс для таблицы страниц (page table).
Таблица страниц содержит начальные адреса f всех страничных рамок, в которых размещена программа. Физический адрес определяется путем сложения начального адреса страничной рамки f и смещения Д.
Рисунок 4.10 показывает, что страничная организация памяти полностью исключает внешнюю фрагментацию.
Рисунок 4.10 - Размещение содержания страниц на внешней памяти
В современных операционных системах типичный размер страницы составляет 2 Кбайт или 4 Кбайт.
Каждая операционная система поддерживает свой собственный метод работы с таблицей страниц. Обычно за каждым процессом, находящимся в основной памяти, закреплена отдельная таблица страниц. В этом случае указатель на таблицу страниц хранится в РСВ соответствующего процесса.
Аппаратная поддержка страничной организации памяти. Преобразование логического адреса в физические осуществляется для каждого адреса, генерируемого процессором, поэтому часто для ускорения этого процесса применяются аппаратные методы, например ассоциативные регистры (associative registers).
Каждый ассоциативный регистр, кроме операций чтения-записи, может обрабатывать операцию сравнения кода, поступающего на его вход с частью кода, хранимого в регистре. Матрица ассоциативных регистров хранит часть таблицы страниц. Номер страницы П подается одновременно на входы всех ассоциативных регистров, которые параллельно выполняют операцию сравнения. На выходе матрицы ассоциативных регистров образуется начальный адрес страничной рамки f того регистра, в котором произошло совпадение кода.
В том случае, если требуемый номер страницы находится в таблице страниц, то есть ни в одном из ассоциативных регистров не произошло совпадения, происходит обращение к таблице страниц, находится искомый номер страничной рамки, а найденная строка таблицы страниц переписывается в один из ассоциативных регистров.
Защита страничной памяти основана на контроле уровня доступа к каждой странице, возможны следующие уровни доступа:
только чтение;
чтение и запись;
только выполнение.
В этом случае каждая страница снабжается 3-битовым кодом уровня доступа. При трансформации логического адреса в физический сравнивается значение кода разрешенного уровня доступа с фактически требуемым. При их несовпадении работа программы прерывается.
Вопросы:
Что такое свопинг?
Что подразумевает понятие «смежное размещение процессов»?
Что такое метод оверлейных сегментов?
Что происходит при мультипрограммировании с фиксированными разделами?
Что происходит при мультипрограммировании с переменными разделами?
Что такое страничная память? Приведите примеры организации страничной памяти.