Стохастическое планирование

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

Последовательный выбор

Последовательный выбор заключается в том, что первая пришедшая работа обслуживается первой FIFO, трудоемкость работ здесь не оценивается на предварительном этапе. Модель можно представить как бесприоритетное обслуживание заявок на основе дисциплины FIFO, которое организуется в соответствии с рисунком 1, где ЦП/ОП — процессор и оперативная память выступают в роли обслуживающих приборов, О — очередь для заявок типа z₁, ..., z_M. Вновь поступившая за­явка заносится в конец очереди. Заявки выбираются на обслужива­ние из начала очереди.

Рисунок 2.6. - Модель последовательного выбора заявок на основе дисциплины FIFO.

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

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

,

где R = ( ) < 1 — суммарная загрузка подсистемы процессор-память, а - коэффициент загрузки подсистемы процессор-память i-м потоком задач.

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

= + = (1+ ).

С учетом этого среднее время ожидания

.

Из формулы видно, что среднее время ожидания заявок в очереди минимально при постоянной длительности обслуживания заявок каж­дого типа ( = 0) и увеличивается по мере роста дисперсии времени обслуживания и становится максимальным при экспоненциальном законе обслуживания ( =1).

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

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

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