Определение среднего времени ожидания.

Алгоритм одноуровневого циклического выбора

Одноуровневый циклический выбор (RR— сокращение от Round — Robin) представляет собой метод, который позволяет оценить трудоемкость работ в ходе реализации вычислительного процесса. Этот алгоритм реализуется в соответствии с рисунком. Заявки на выполнение работ поступают с интенсивностью l в очередь O, откуда они выбираются и исполняются в подсистеме процессо­р - память. Для обслуживания отдельной заявки отводится постоянный квант времени q, достаточный для выполнения нескольких тысяч операций. Если работа была выполнена за время q, то она поки­дает систему, а результат передаётся пользователю. В противном случае она прерывается, возвращается в конец очереди и ожидает предоставления ей очередного кванта про­цессорного времени. Таким образом, создается порядок выполнения работ по принципу «короткая работа выполняется первой», который обеспечивает минимум суммарного времени выполнения работ.

Рисунок 2.7- Модель одноуровневого циклического выбора

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

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

Пусть m – среднее число квантов, требуемых для обслуживания работы – случайная величина, распределенная по экспоненциальному за­кону. Тогда средние значения трудоемкостей работ при известных значениях q равно

v= mq.

Такое описание модели соответствует открытой системе массового обслуживания. Среднее время ожидания для работы J, время выполнения ко­торой составляет т квантов

.

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

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

Применяют модифицирование:

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