7.3.1. Квантование времени обслуживания

При реализации алгоритмов полностью стохастических задач, когда априорно неизвестно время обслуживания заявок, мож­но учесть среднее время обслуживания всей совокупности программ управляющей системы. Можно планировать ис­пользование простейших приоритетных дисциплин (s = 1): «первым пришел — первым обслужен», «последним пришел — первым обслужен», дисциплину со случайным выбором зая­вок из очереди.

В первую очередь бывает более выгодно получить решение (окончить обслуживание) задач, которые требуют малого вре­мени работы ЭВМ. Подобный режим применяется в системах с разделением времени.

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

Различают два основных типа систем обслуживания с квантованием по времени:

• циклическая дисциплина обслуживания;

• многоуровневая дисциплина обслуживания.

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


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

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

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

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