Одноочередные дисциплины обслуживания

а) FIFO (First In -- First Out) – дисциплина обслуживания в порядке поступления. Все заявки поступают в конец очереди. Первыми обслуживаются заявки, находящиеся в начале очереди. Схематически эта дисциплина показана на рис. 4а.

б) LIFO (Last In -- First Out) – дисциплина обслуживания в порядке, обратном порядку поступления. Эта дисциплина является основой построения стековой памяти. Схема дисциплины представлена на рис.4б.

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

в) Дисциплина обслуживания по круговому циклическому алгоритму. Схема данной дисциплины показана на рис.4в.

а)

б)

в)

Рис.4. Схемы одноочередных дисциплин обслуживания процессов:

а – первый пришел – первый обслужился;

б – последний пришел – первый обслужился;

в – круговой циклический алгоритм

Эта дисциплина используется, в частности, при реализации режима разделения времени. В ее основе лежит дисциплина FIFO. Квант времени обслуживания t_k (квант мультиплексирования) ограничивает длительность обслуживания процесса. Если заявка не успевает обслужиться за время t_k, то ее обслуживание прерывается, и она поступает в конец очереди. Здесь имеет место «дискриминация» – в наиболее благоприятных условиях оказываются короткие заявки, они имеют меньшие времена ожидания. Степень благоприятствования коротким заявкам тем больше, чем меньше длительность кванта мультиплексирования. Однако уменьшение t_k ведет к увеличению накладных расходов, необходимых для обработки прерываний и перераспределения ресурса.

Многоочередная дисциплина обслуживания. Схема данной дисциплины приведена на рис. 5.

Рис.5. Схема многоочередной дисциплины обслуживания

Здесь N очередей, все новые заявки поступают в конец первой очереди. Первая заявка из очереди i (1 < i £ N) поступает на обслуживание лишь тогда, когда все очереди от 1-й до (i-1)-й пустые. Если за время t_k обслуживание процесса завершается полностью, то он покидает систему. В противном случае недообслуженная заявка поступает в конец очереди с номером i+1. После обслуживания заявки из очереди i система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Если система выходит на обслуживание заявок из очереди N, то они обслуживаются либо по дисциплине FIFO, либо по круговому алгоритму. Данная система наиболее быстро обслуживает все короткие запросы. Недостаток системы заключается в непроизводительных затратах времени на перемещение заявок из одной очереди в другую.

Дисциплина обслуживания при наличии приоритетов. Такая дисциплина строится на основе рассмотренной выше многоочередной дисциплины. На рис.6. приводится ее условная схема.

Рис.6. Схема приоритетной многоочередной дисциплины обслуживания

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

а) Обслуживание с абсолютным приоритетом. Если во время обслуживания заявки из очереди i (1 < i £ N) в систему поступает более приоритетная заявка, например, в очередь i-1, то обслуживание i-го уровня прерывается и система переходит к обслуживанию поступившей заявки. После окончания ее обслуживания происходит дообслуживание прерванной заявки i-го уровня. Здесь еще больше сокращается время ожидания обслуживания для высокоприоритетных заявок за счет ухудшения обслуживания низкоприоритетных. В то же время усложняется логика системы, возникает проблема прерывания, появляются накладные расходы. При достаточной интенсивности прерываний расходы могут стать ощутимыми. Возникает также дополнительная проблема выработки некоторого правила о дообслуживании прерванных процессов – когда выделять им вновь ресурс, учитывать ли, что он уже какое-то время использовался?

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

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

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