Приоритетное планирование.

Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение — приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше приоритет у процесса.

Принципы назначения приоритетов могут опираться как на внутренние критерии вычислительной системы, так и на внешние по отношению к ней. Внутренние используют различные количественные и качественные характеристики процесса для вычисления его приоритета. Это могут быть, например, определенные ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Внешние критерии исходят из таких параметров, как важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и других политических факторов.

Статические и динамические приоритеты.

Механизмы статической приоритетности легко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболее приоритетного процесса. Однако статические приоритеты не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамического приоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамического приоритета процесса является единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменение приоритета процессов проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования. Схемы с динамической приоритетностью гораздо сложнее в реализации и связанны с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением поведения системы.

Реализация приоритетного планирования.

Многоуровневые очереди.

Для систем, в которых процессы могут быть легко рассортированы на разные группы, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность (см. рисунок 3.5). Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается больше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, — ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR. Подобный подход, получивший название многоуровневых очередей, повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм.

Многоуровневые очереди с обратной связью.

Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи. Здесь процесс не постоянно приписан к определенной очереди, а может мигрировать из очереди в очередь, в зависимости от своего поведения.

Многоуровневые очереди с обратной связью представляют собой наиболее общий подход к планированию процессов из числа подходов, рассмотренных нами. Они наиболее трудоемки в реализации, но в то же время они обладают наибольшей гибкостью.

Управление памятью

Абстрактная модель памяти.

1. память – последовательность автономных неперекрывающихся ячеек, хранящих команду/данные

2. размер ячейки фиксирован или переменный, но всегда достаточен для размещения команды/данных

3. ячейки пронумеров и упорядоч имеют адрес, все множество адресов есть адресное пространство

4. мощность адресного пространства зависит от разрядности процессора 2^16 или 2^32

5. над ячейками выполняется чтение/запись

6. время выполнения зап/чтен и порядок доступак ячейке не зависит от адреса

Базовые принципы управления памятью.

Менеджер памяти - модуль ОС для управления памятью

• Разделение адресных пространств - на логическое (обращается программа) и физическое(обращение к памяти)

• Сегментация – разбиение логического адресного пространства на области (данные, код, стек и тд).позволяет контролировать порядок работы сданными

• Локальность – для выполнения команды программы не обязательно наличие всей программы в памяти

Схемы управления памятью.

• С фиксированныи разделами - разбиение основной памяти на разделы фиксированного размера

• С переменными разделами – каждой вновь поступающей задаче выделяется необходимый участок памяти

Этапы обработки программ и связывание адресов.

Связывание логический адресов, порожденных командой программы, с физическими выполняется до или в момент выполнения команды.

Этапы:

Исходный модуль(на языке выс ур) -> транслятор -> объектный модуль -> редактор связей -> загрузочный модуль -> загрузчик -> образ в памяти

Каждый этап отображает одно адресное пространство в другое: Транслятор связывает символические адреса с логическими (выч относительно начала модуля),редакт св – соединяет несколько модулей и выч адреса уже относительно начало общего кода, загрузчик – св логич адреса с физич

Связ лог и физ адресов может быть на других этапах:

• Компил и редакт – если извесно точное положение процесса в памяти, можно сгенерировать сразу физич адрес,но если местоположение поменяется нужно перекомпил код и заново выполнить редакт связей

• Загрузка – если не известно положение проц в памяти, то генерир перемещаемые адр отн начала модуля или программы, если изменится местоположение достаточно изменить адреса с учетом нового знач начального адреса

• Выполнение – если положение образа памяти не фикс в памяти она может его поменять и связ выполняется непосредственно во время работы прогр. Это поддерживается аппаратно регистрами перемещения, значения которых прибавляются к каждому адресу сгенерированному процессом, работающим с логич адресами

Схема с фиксированными разделами.

Базовые принципы.

Разбиение операт памяти на разделы фикс размера на этапе генерации/момент загрузки системы.Процесс помещается в раздел подходящего размера.Каждый раздел может иметь свою очередь процессов или мб глабальная очередь для всех разделов. Тогда сист выбирает подход раздел в соотв со стратегией размещения задания в разделе сравнивая размер прогр со свободными разделами, загр прогр и настраивает адреса.

Минус:внешняя фрагментация – потеря памяти,неискольз ни одним процессом, тк проц занимает не весь раздел и тк имеющиеся разделы малы для прогамм в очереди.

Плюс: простота управления памятью. Тк нужно только поддерживать таблицу разделов(местоположение, размер, текущее состояние занятости раздела)

Стратегии размещения задания в разделе:

• Первого подходящего – задание помещается в первый подходящий по разм раздел

• Наиболее подходящего – задание помещается в раздел, где остается меньше всего свободной памяти

• Наименее подходящего – помещается в самый большой раздел, оставляя самый большой свободный участок(не примен в случае фиксирован разделов)