7

Операционные системы. Лекция 8. (Мультипрограммирование и мультипроцессирование)

Приоритетные дисциплины диспетчеризации (ПДД)

Принцип, заложенный для приоритетов: HPF – highest priority first (наивысший приоритет - первым).

Приоритет – это право на первоочередное обслуживание.

ПДД – характеризуется более сложной работой с очередью.

Назначение приоритета процессам происходит на основе:

• статистических характеристик:

• ожидаемый объем ввода/вывода;

• априорное t_{обслуж.}; (знание, полученное до опыта, апостериори – после опыта)

• внешний приоритет;

• ожидаемый объем ОП.

• динамических характеристик:

• время нахождения в системе;

• объем вводимых/выводимых операций в предыдущий момент времени.

ДД с фиксированным приоритетом

Процессы располагаются в очереди готовых процессов в соответствии со своим приоритетом. Если поступило несколько процессов одного приоритета, то в очереди они обслуживаются по принципу FIFO.

Недостатки дисциплин с фиксированным приоритетом

• неточность априорных характеристик приводит к приблизительности приоритета;

• возможность приспосабливаемости пользователей к системе приоритета. Если пользователю известно о системе приоритетов, т.е. больше «уважают» короткие заявки в системе, то пользователь составит 2 короткие вместо 1-ой длинной, но тогда система становится на уровень FIFO;

• при хороших и средних характеристиках параметра t_{ожидан.}, отдельные заявки в системе могут длительное время ждать. Для устранения этого недостатка надо бы повысить приоритет задачи, но т.к. он фиксирован, это невозможно;

• отсутствует настраиваемость системы на изменение характеристик входного потока заявок.

ДД с динамическим приоритетом

Приоритет изменяется в период пребывания в системе (либо в процессе ожидания, либо в процессе выполнения)

Если низкоприоритетный процесс ждет длительное время, его приоритет повышается.

P_i(t) = a_i t_{ожидан.} + b_i t_{выполн.,} где P_i(t) – приоритет i- го процесса

Дисциплины с динамическим приоритетом

1. Следующий - с минимальным оставшимся временем(srt).

(SRT – shortest-remaining-time)

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

Аналог SJN с перераспределением процессора.

Короткие процессы еще более выигрывают за счет длинных.

Так как SJN и SRT основаны на оценке времени, то они не подходят для диспетчеризации интерактивных процессов.

Недостатком дисциплин, основанных на сокращении общего времени ожидания, является задержка выполнения длинных процессов (процессы могут теряться практически навсегда).

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

1. Следующий – с наивысшим отношением отклика(hrrn)

(HRRN - highest response ratio next)

Отношение отклика R= (w+s)/s , где w -время затраченное процессом на ожидание ,s –ожидаемое время обслуживания. Минимальное значение R (равное 1) при входе процесса в систему.

Правило стратегии: При завершении, прерывании или блокировании текущего процесса, для выполнения из очереди готовых процессов выбирается тот, который имеет наибольшее значение R (учитывается возраст процесса). Циклическая дисциплина с приоритетом.

Достоинства системы с динамическим приоритетом:

• возможность настраиваться при изменении характеристик входного потока на эффективное обслуживание;

• дисциплина основана на реальных динамических характеристиках процессов.

Недостаток: сложность реализации.

Вывод по приоритетным ДД - они сокращают время ожидания_. высокоприоритетных заявок за счет увеличения времени ожидания низкоприоритетных.

Дисциплины с несколькими очередями.

Процессы делятся на классы и процессы разных классов обслуживаются по разному.

Классы процессов:

1. Реального времени (д.б. обслужен до наступления конкретного момента времени) (Оперативные процессы с высоким приоритетом).

2. Интерактивные (д.б. обслужен в течение приемлемого времени реакции). (Оперативные процессы с высоким приоритетом).

3. Пакетные (нет жестких ограничений на время обслуживания). (Фоновые процессы с низким приоритетом).

Для каждой из очередей можно использовать свою дисциплину и разные значения управляющих параметров (например, длина кванта).

Связь процесса с очередью м.б.:

• статична – процесс всегда возвращается в одну и ту же очередь;

• динамична – процесс при различных обстоятельствах возвращается в разные очереди.

Гарантия обслуживания.

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

В системе с пакетными и интерактивными процессами на последние можно наложить жесткие временные ограничения, чтобы обеспечить необходимое время ответа.

Гарантировать обслуживание можно тремя разными способами:

1. Выделять минимальную долю процессорного времени классу процессов, если по крайней мере один из процессов готов к исполнению (классы –процессы реального времени, интерактивные процессы, пакетные процессы)

2. Выделять минимальную долю процессорного времени некоторому конкретному процессу, если он готов к исполнению.

3. Выделять столько процессорного времени некоторому процессу, чтобы он мог выполнить необходимые действия к сроку

Диспетчеризация в мультипроцессорной системе

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

1. Алгоритм разделения времени

Простейший алгоритм диспетчеризации процессов (или потоков) состоит в поддержании единой очереди готовых потоков (возможно с различными приоритетами).

Наличие единой очереди, используемой всеми центральными процессорами, обеспечивает процессорам режим разделения времени подобно тому, как это выполняется на однопроцессорной системе.

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

2. Алгоритм родственного планирования.

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

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

Двухуровневое планирование обладает тремя преимуществами

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

• Во-вторых, двухуровневое планирование по возможности использует преимущество родственности кэша.

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