4.4. Дисциплины распределения ресурсов на основе очередей
Одновременное выполнение нескольких пользовательских программ (мультипрограммирование) неизбежно приводит к появлению очередей, возникающих при обращении процессов к различным ресурсам (центральный процессор, каналы, внешние устройства, наборы данных, модули ОС и т.д.). Очередь формируется из заявок на использование ресурса, поступающих от процессов. Заявки на кратковременное использование ресурса будем называть короткими, а заявки на длительное использование ресурса соответственнодлинными. Не все заявки считаются равноправными, существуют различные системы приоритетов.
Очереди необходимо как формировать, так и обслуживать на основе определенных правил – дисциплин. В зависимости от способа назначения приоритетов, дисциплины формирования очередей делятся на два класса:
статический– приоритеты назначаются до выполнения задания;
динамический– приоритеты определяются в процессе выполнения пакета программ. Рассмотрим наиболее распространенные дисциплины обслуживания очередей.
Одноочередные дисциплины обслуживания.
а) FIFO (First In -- First Out) – дисциплина обслуживания в порядке поступления. Все заявки поступают в конец очереди. Первыми обслуживаются заявки, находящиеся в начале очереди. Схематически эта дисциплина показана на рис. 4а.
б) LIFO (Last In -- First Out) – дисциплина обслуживания в порядке, обратном порядку поступления. Эта дисциплина является основой построения стековой памяти. Схема дисциплины представлена на рис.4б.
Обе рассмотренные дисциплины просты в реализации. Среднее время ожидания заявок в очереди при установившихся темпе обслуживания и поступления одинаково для всех процессов, независимо от того, как надолго процессу требуется распределяемый ресурс.
в) Дисциплина обслуживания по круговому циклическому алгоритму. Схема данной дисциплины показана на рис.4в.
а
)
б)
в
)
Рис.4. Схемы одноочередных дисциплин обслуживания процессов:
а – первый пришел – первый обслужился;
б – последний пришел – первый обслужился;
в – круговой циклический алгоритм
Эта дисциплина используется, в частности, при реализации режима разделения времени. В ее основе лежит дисциплина FIFO. Квант времени обслуживанияtk(квант мультиплексирования) ограничивает длительность обслуживания процесса. Если заявка не успевает обслужиться за времяtk , то ее обслуживание прерывается, и она поступает в конец очереди. Здесь имеет место «дискриминация» – в наиболее благоприятных условиях оказываются короткие заявки, они имеют меньшие времена ожидания. Степень благоприятствования коротким заявкам тем больше, чем меньше длительность кванта мультиплексирования. Однако уменьшениеtkведет к увеличению накладных расходов, необходимых для обработки прерываний и перераспределения ресурса.
Многоочередная дисциплина обслуживания. Схема данной дисциплины приведена на рис. 5.
Рис.5. Схема многоочередной дисциплины обслуживания
Здесь N очередей, все новые заявки поступают в конец первой очереди. Первая заявка из очереди i (1 < i N) поступает на обслуживание лишь тогда, когда все очереди от 1-й до (i-1)-й пустые. Если за время tk обслуживание процесса завершается полностью, то он покидает систему. В противном случае недообслуженная заявка поступает в конец очереди с номером i+1. После обслуживания заявки из очереди i система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Если система выходит на обслуживание заявок из очереди N, то они обслуживаются либо по дисциплине FIFO, либо по круговому алгоритму. Данная система наиболее быстро обслуживает все короткие запросы. Недостаток системы заключается в непроизводительных затратах времени на перемещение заявок из одной очереди в другую.