Дисциплины распределения ресурсов в ОС

Множество параллельных процессов порождает запросы к ресурсам, каждый из которых в каждый момент времени может использоваться только одним процессором. Элементом, согласовывающим использование такого ресурса, является очередь. Очередь – это многоэлементная структура данных, каждый элемент которой (заявка) содержит информацию, однозначно определяющую процесс, запрашивающий ресурс и параметры этого запроса (заявки). Использование ресурсов множеством процессов осуществляется с помощью некоторой дисциплины распределения ресурсов, содержащей совокупность правил, которые определяют порядок, во-первых, размещения заявок на использование ресурса в очереди, во-вторых, извлечения заявки из очереди и предоставления ресурса по ней. Существенное влияние на дисциплину распределения оказывает приоритет заявки. Все дисциплины разделяют на два класса: 1) со статическими приоритетами (при этом приоритет заявок после постановки их в очередь не изменяется ); 2) с динамическими приоритетами (при этом приоритет заявок может изменяться либо при их выполнении, либо при выполнении других заявок из очереди). Рассмотрим основные (типовые) дисциплины.

1. Дисциплина обслуживания в порядке поступления реализует принцип «первый пришел – первый обслужился» FIFO (first in – first out). Это самая простая и широко используемая на практике дисциплина. Все заявки поступают в конец очереди, а первыми обслуживаются заявки, находящиеся в конце очереди.

2.Дисциплина обслуживания в порядке, обратном порядку поступления, реализует принцип LIFO (last in – first out). Она также широко распространена. Общим для LIFO и FIFO является простота реализации и справедливость в обслуживании этих заявок. Среднее время ожидания заявок в очереди при установившемся темпе обслуживания одинаково.

3. Круговой циклический алгоритм реализует принцип RR (Round Robin – “Круговой разбойник”), хотя в его основе лежит дисциплина FIFO. Используется при реализации режима разделения времени. Вновь поступающие заявки от пользователей порождают запросы на выполнение определенных программ. Эти запросы помещаются в порядке их поступления в конец очереди FIFO. Для обслуживания выбирается запрос из начала очереди и запускается соответствующая программа, для выполнения которой выделяется некоторый фиксированный квант времени. Если в течение этого кванта программа будет завершена, то результат будет выдан пользователю, и

4.процессор приступит к выполнению следующего по очереди запроса. В противном случае выполнение программы прерывается, и она помещается в конец очереди. Основные свойства дисциплины: так как все программы равноприоритетны, и им через определенный промежуток времени выделяется для исполнения по одному кванту времени, то 1)гарантируется обслуживание всех заявок; 2) обеспечивается время обслуживания, пропорциональное времени выполнения соответствующей программы.

5. Дисциплина, реализующая принцип FB_N (Foreground - Background) – «Приоритетный фоновый». Рассмотренные дисциплины являются одноочередными, однако, в ОС широко используются многоочередные дисциплины, позволяющие сократить потери времени, связанные с переключением программ и обеспечением большего приоритета для коротких запросов. Т – квант обслуживания, q – квант времени, N – количество очередей. Поступившая на обслуживание заявка ставится в конец n-й очереди (n=1). Первая заявка из очереди с номером n>1 поступит на обработку только тогда, когда очереди с номерами меньше, чем n, пусты. Выбранной для обработки заявке из очереди с номером n<N выделяется квант времени. Если в течение этого кванта программа будет завершена, то результат будет выдан пользователю, и на обработку поступит первая заявка из непустой очереди с низшим номером. В противном случае заявка на незавершенную программу попадает в конец очереди с номером n+1 (как бы поднимается). Заявки из очереди с номером n=N обслуживаются до конца либо по дисциплине FIFO, либо RR. В данной дисциплине нет явных приоритетов, но происходит автоматическое разделение длинных и коротких заявок, при этом наиболее быстро обслуживаются короткие заявки. Предпочтение отдается новым заявкам, поступающим в систему. Если частота поступления новых заявок будет достаточно велика, то при больших значениях N время ожидания в очереди заявок, требующих продолжительного обслуживания может возрасти до недопустимых величин. Этих недостатков лишена следующая дисциплина.

6. Дисциплина, реализующая алгоритм Корбато. Также как и в FB_N создается несколько очередей. Поступающая в систему заявка помешается не в самую первую очередь, как в FB_N, а в очередь с номером, зависящим от параметров программы, обрабатывающей заявку. Правило присвоения приоритетов основано на предположении, что время счета программы пропорционально его объему. Учитывается и время вызова программы из внешней памяти, также зависящее от объема программы. Такой алгоритм широко применяется в системах разделения времени, которые обладают общим признаком: необходимостью подкачки (swapping) в оперативную память программ из внешней памяти или наоборот (при переключении исполняемых процессором программ). Для подобных систем оправдано стремление уменьшить непроизводительные затраты процессорного времени на выполнение таких пересылок. Правило присвоения приоритета (т.е. номера очереди, куда первоначально поступает заявка) имеет вид: n=]log₂(] [+1)[, где ]x[ - целая часть х (путем отброса), W_p – объем программы в словах, W_q – количество слов, которое может быть передано в ОЗУ из внешней памяти и обратно за квант времени q. Дисциплина Корбато построено так: из всех имеющихся в наличии очередей каждый раз в период планирования (в конце кванта обслуживания) выбирается первая непустая очередь с наименьшим номером, равным n (n= ). Каждая очередь с любым номером обслуживается по алгоритму FIFO. Первая программа, стоящая в очереди с номером n, запускается на выполнение с квантом времени обслуживания T=2ⁿ*q, где q – некоторая константа. Если к концу выделенного кванта времени данная программа не завершилась, то она, также как в FB_N, штрафуется, т.е. переводится в конец очереди с номером n+1. При запуске ее из очереди n+1 через некоторое время ей будет выделен квант времени T^!=(2ⁿ⁺¹*q)>T . Применяемое в алгоритме Корбато правило присвоения приоритетов отдает предпочтение в первостепенности обслуживания программам, требующим мало времени для обмена с внешней памятью. Наибольшее время отводится наиболее длинным программам (т.е. обладающим меньшим приоритетом). Это обеспечивает их редкое прерывание, что снижает потери на обмен с внешней памятью. Недостатки: 1) величина отводимого кванта Т зависит только от W_p, не учитывая другие факторы; 2) приоритет программы не меняется в зависимости от времени ожидания обслуживания в очереди. Это может привести к слишком большим периодам ожидания для больших программ. Особо опасное увеличение времени ожидания может произойти при увеличении частоты поступления новых коротких заявок.