Использование многими процессами того или иного ресурса, который в каждый момент времени может обслуживать лишь один процесс, осуществляется с помощью дисциплин распределения ресурса. Их основой являются:
дисциплины формирования очередей на ресурсы или совокупность правил, определяющих размещение процессов в очереди
дисциплины обслуживания очереди или совокупность правил извлечения одного из процессов очереди с последующим представлением выбранному процессу ресурса для использования
Основным конструктивным, согласующим элементом при реализации той или иной дисциплины диспетчеризации является очередь, в которую по определенным правилам заносятся и извлекаются запросы.
Дисциплины формирования очередей разделяются на два класса:
статический, где приоритеты назначаются до выполнения пакета заданий
динамический, при котором приоритеты определяются в процессе выполнения пакета
Оба класса широко используются в практике организации вычислительного процесса в ЭВМ.
В ЭВМ не только многопрограммных, но и однопрограммных, однопроцессорных, многопроцессорных широко используется ряд дисциплин обслуживания очередей, ставших классическими. Эти дисциплины распределения ресурсов часто называют базовыми. Рассмотрим наиболее часто встречающиеся на практике дисциплины обслуживания.
Дисциплина обслуживания в порядке поступления. Первый пришел — первый обслуживается. В литературе эта дисциплина обозначается как FIFO (First in—First out). Самая простая и широко используемая на практике. Условная схема этой дисциплины показана на рис. 2.3, а.
Все заявки поступают в конец очереди. Первыми обслуживаются заявки, находящиеся в начале очереди.
Дисциплина обслуживания в порядке, обратном порядку поступления. Последняя пришла —первая обслуживается. Обозначается LIFO (Last in—First out). Так же, как и FIFO, проста в реализации и широко используется на практике. Условное обозначение дисциплин на рис. 2.3, б. Данная дисциплина является основой построения стековой памяти.
Общим для названных дисциплин является простота их реализации и определенная "справедливость" в обслуживании всего потока запросов, поступающих в систему. Среднее время ожидания запросов в очереди при некотором установившемся темпе обслуживания и темпе поступления является одинаковым независимо от характеристик процессов-пользователей. Например, если некоторые процессы предполагают длительное использование ресурсов (отрабатываются "длинные" запросы), а другие, наоборот,—непродолжительное (отрабатываются "короткие" запросы), то и "длинные" и "короткие" запросы будут ожидать в очереди в среднем одинаково. Дисциплина FIFO помимо функционального отличия обеспечивает минимизацию дисперсии времени ожидания.
Рис. 2.3 Схемы дисциплин обслуживания процессов
а - FIFO; б - LIFO; в - круговой циклический алгоритм.
Круговой циклический алгоритм. В основе данной дисциплины лежит дисциплина FIFO. Но время обслуживания каждого процесса ограничено и определяется так называемым квантом времени tk. Если запрос на использование ресурса из начала очереди обслуживается до конца за время tk (например, программа процесса за время tk полностью выполнена на процессоре), то он покидает очередь. Если этот запрос не успевает обслужиться до конца, то его обслуживание прерывается и он поступает в конец очереди. Схема дисциплины приведена на рис.2.3, в. Дисциплина широко используется на практике, в частности при реализации режима разделения времени.
Хотя в данной дисциплине нет явных приоритетов. здесь автоматически происходит дискриминация "длинных" и "коротких" запросов. В наиболее благоприятных условиях оказываются короткие запросы, т. е. запросы от процессов, которым требуется меньшее время использования ресурсов. Короткие запросы обслуживаются быстрее, т. е. имеют меньшие средние времена ожидания в системе, чем длинные запросы. Степень благоприятствования коротким запросам тем больше, чем меньше длительность кванта мультиплексирования, чем ближе она к длительности интервала номинального использования ресурса процессом. Однако уменьшение длительности кванта ведет к увеличению накладных расходов, необходимых для отработки прерываний и перераспределения ресурса. Это происходит из-за возрастания частоты прерываний, что особенно неблагоприятно может сказаться на отработке "длинных" запросов. Поэтому на практике используют различные модификации данного алгоритма.
Все рассмотренные дисциплины являются одноочередными. В ЭВМ, в операционных системах широко используются многоочередные дисциплины. Схема одной из таких дисциплин приведена на рис. 2.4. Здесь организуется N очередей. Все новые запросы поступают в конец первой очереди. Первый запрос из очереди i поступает на обслуживание лишь тогда, когда все очереди от 1 до (i—1)-й пустые. На обслуживание выделяется квант времени tk. Если за это время обслуживание запроса завершается полностью, то он покидает систему. В противном случае недообслуженный запрос поступает в конец очереди с номером i+l.
Рис.2.4 Схема многоочередной дисциплины обслуживания
После обслуживания из очереди i система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Таким запросом может быть следующий запрос из очереди i или из очереди i+l (при условии, что после обслуживания запроса из очереди i последняя оказалась пустой). Новый запрос поступает в первую очередь (i = l). В такой ситуации после окончания времени tk, выделенного для обслуживания запроса из очереди i, будет начато обслуживание запроса 1-й очереди.
Если система выходит на обслуживание заявок из очереди N, то они обслуживаются либо по дисциплине FIFO (каждая заявка обслуживается до конца), либо по круговому циклическому алгоритму.
Данная система наиболее быстро обслуживает все короткие по времени обслуживания запросы. Недостаток системы заключается в непроизводительных затратах времени на перемещение запросов из одной очереди в другую.
Все рассмотренные дисциплины обеспечивают не только обслуживание очередей, но и их формирование. Для всех таких дисциплин характерно отсутствие приоритетности запросов при их поступлении в систему. Но после поступления каждый запрос приобретает приоритет, который изменяется в процессе обслуживания одной очереди или многих очередей.
Существуют многоочередные дисциплины, в которые поступают запросы, имеющие определенный приоритет на обслуживание тем или иным ресурсом. Схема такой приоритетной дисциплины приведена на рис.2.5. Основу этой дисциплины представляет ранее рассмотренная многоочередная дисциплина. Поступающие в систему новые запросы не обязательно попадают в 1-ю очередь. Они попадают в очередь в соответствии с имеющимися приоритетами, которые определяются параметрами обслуживаемых процессов.
Рис. 2.5 Схема приоритетной многоочередной дисциплины обслуживания
