С.Ф.Яшков, А.С.Яшкова

Разделение процессора: обзор математической теории

За последнее десятилетие эгалитарное разделение процессора (EPS) стало играть заметную роль в прикладной теории вероятностей, в особенности в теории очередей и ее компьютерных приложениях. В то время как парадигма EPS возникла в 1967 как идеализация циклического (roundrobin: RR) алгоритма диспетчеризации в вычислительных системах с разделением времени, недавно возобновился интерес к ней как к мощной концепции для моделирования WEB серверов. Статья суммирует важнейшие результаты по точным решениям системы обслуживания M/GI/1 с эгалитарным разделением процессора. Материал почерпнут, в основном, из статей авторов, которые дополнены в небольшой степени другими смежными результатами. Многие дальнейшие результаты установлены под непосредственным влиянием наших более ранних статей. Главной целью является дать обзор состояния и достижений современной теории системы обслуживания M/GI/1EPS. Упор сделан на методах точного и асимптотического анализа этой системы обслуживания. В отличие от стандартных обзоров, в статью включены сокращенные доказательства (или идеи доказательств) ключевых теорем и следствий. Мы очертим недавние достижения в точных решениях системы M/GI/1EPS по стационарным и нестационарным (транзиентным) распределениям основных вероятностно-временных характеристик. В частности, данная статья включает результаты по совместному нестационарному распределению времени пребывания в системе требования, поступающего в момент t с требуемой длительностью обслуживания (длиной) u, и числа требований в системе M/GI/1EPS в момент t-, полученные в терминах многомерных преобразований. Демонстрируется также, как могут быть использованы нестационарные решения для получения известных и новых результатов, позволяющих предсказать поведение системы обслуживания и обнаружить ее новые неожиданные свойства. Мы также обсудим ряд предельных теорем, возникающих при исследовании очередей с разделением процессора.