М.Г. Коновалов, Р.В. Разумчик

Минимизация среднего времени пребывания в ненаблюдаемых системах с параллельным обслуживанием и дисциплиной справедливого разделения процессора в серверах

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

KEYWORDS: системы с параллельным обслуживанием; дисциплина справедливого разделения процессора; диспетчеризация; стратегии размещения заданий; управление при неполном наблюдении