М.Г. Коновалов, Р.В. Разумчик
Минимизация среднего времени пребывания
в ненаблюдаемых системах с параллельным обслуживанием и дисциплиной справедливого
разделения процессора в серверах
Рассматривается
задача эффективного распределения единственного потока однородных заданий в
“почти” ненаблюдаемых системах, состоящих из параллельно работающих серверов с
очередями неограниченной емкости и одного диспетчера, немедленно распределяющего
поступающие по одному задания по серверам. Эффективность понимается в смысле
минимума стационарного среднего времени пребывания задания в системе. Для
выбора сервера диспетчеру доступна лишь следующая информация: производительность
серверов, распределение времени между поступлениями заданий, распределение их размеров,
полная история совершенных действий и промежутки между ними. Динамическая
информация о состоянии системы (как, например, длина очередей) диспетчеру неизвестна.
Предполагается, что в серверах реализована дисциплина справедливого разделения
процессора. Из классических диспетчеризаций для таких систем
применимы лишь: случайный выбор и циклический выбор. В работе
предлагается семейство новых стратегий, которые используют, помимо априорной информации
о системе, оценки состояния серверов по результатам имеющихся наблюдений. На
численных примерах показано, что, по сравнению с известными стратегиями, новые
стратегии позволяют существенно уменьшить среднее время пребывания.
KEYWORDS: системы с параллельным обслуживанием; дисциплина справедливого разделения процессора; диспетчеризация; стратегии размещения заданий; управление при неполном наблюдении