Введение к работе
Актуальность работа. Работа посвящена оптимизации очередей в вычислительных системах. Эти задачи возникают в процессе создания и эксплуатации вычислительных систем, во находят применение и в других областях, например, в теории расписаний, в гибких автоматизированных производствах, в распределенных системах и т.д.-
Недостаточное изучение проблем оптимизации очередей требовании (заданий) приводит к существенному уменьшению производительности вычислительных систем, как показал опыт их практических разработок. Это явилось одной из главных причин того, что ни системы с разделением времени, ни суперЭВМ не смогли достичь, запланированной эффективности.
Задача оптимизации' состоит в том, чтобы распределять требования (задания, поступающие в вычислительную систему) так, чтобы оптимизировать некоторый критерий. При этом вычислительную систему представляем следующим образом:
- на вход системы поступают потоки требований (заданий)
нескольких типов; ,
- поступившие требования ставятся в неограниченные очереди;
. - диспетчер (или планировщик заданий) распределяет
требования по приборам (процессорам); . ..
- по окончании обслуживания требования на процессоре оно
либо покидает систему, либо пороадает новые требования, которые
: поступают в очереди. .'."'.'
В такой общей постановке задача слишком громоздка, поэтому чтобы сделать ее обозримой применяется теория очередей (теория массового обслуживания), в которой поступления требований
задаются рекуррентным, и даже пуассоиовским потоком, а
длительности обслуживания предполагаются независимыми и одинаково
распределенными (для кшздого типа). '
Для оптимизации рассматриваемого критерия нужно найти алгоритми работы диспетчера, которые называются дисциплинами обслуживания. Из них наиболее известными являются: обслуживание в порядке поступления, первоочередное обслуживание требований с кратчайшей длительностью обслуживания или дообслухтвашш, многоуровневые, цшш. ,иские и др.
Подобным задачам теории очередей посвящено довольно большое число статей и монографий (Баварии Т.П., Климов Т.П., Липаев В.В., Рыков D.B., Боксма 0., Дягайсуол H.R., Клеинрок Л. и др.). Рассматриваемые п них задачи можно охарактеризовать как изучение дисциплин обслуживания. А соответствующая оптимизационная задача сводится к классической постановке - оптимизации функции от нескольких перемвшшх. ,
Однако как классические методы теории очередей, так и новые математические метода (Боровков А.А., Малышев В.А., Боксма 0... Шассбергер Р. и др.) анализа систем позволяют . получать решение лишь в специальных случаях. Кроме, того, даже найдя оптимальное (по некоторому критерию) решвниа для рассматриваемой дисциплины остается неясным вопрос о том. является ли это решение оптимальным для всех других дйсщяшш.
Одним из наиболее частых критериев является минимизация некоторой функции от средних длин очередей, котбрые являются оововными для разработчиков и администраторов вычислительных систем при определении дисциплины обслуживания. Зная их, можно
найти и другие характеристики, такие, как сроднее время отклика, коэффициенты использоввпия процессоров и коэффициент замедления программ, пропускную способность и т.п.
В настоящей работе рассматривается задача минимизации функции, зависящей от средних длил очередей, по дисциплинам обслуживания в вычислительных системах без потерь требований. *
Для ее решения предлагается новый подход, которые позволяет:
1) получить решение для более широкого класса вычислительных
систем; '
2) получить решение,оптимальное по всем дисциплинам.
Полученные результаты по оптимизации средних длин очередей в
вычислительных системах являются актталышЕя:
1. В алане развития новых подходов к реаению подобных «задач.
-
В плане новых математических моделей вычислительных систем.
-
В плане получения повых алгоритмов' для повышения производительности вычислительных систем.
Цель работы. . Целью работы . является создание эффективных алгоритмов оптимизации управления очередями в вычислительных системах.
Методы исследования. В работе используются методы теории очередей (массового обслуживания К теории выпуклых многогранников, теории графов, теории алгоритмов.
Научная новизна и положения, внносикые на защиту.
1. Описан новый метод оптимизации средних длин очередей. Этот мотод состоит в следующем:
А. Строим множество всевозможных значений средних длин
-6-.
очередей, называемое далее приоритетным;
Б. Исследуем его комбинаторную структуру и решаем оптимизационную задачу на этом множестве; , '
В. Находим дисциплину обслуживания, реализующую любу» точку приоритетного множег-ва.
2. Предлагаемым методом решены задачи оптимизации функции от средних длин очередей для рада'классических систем обслуживания, описываемых в известной символике Кендалла-Башарина как М JG |1, GI|M |1, GIjGJI, МJG |m, IIJG |1 с ветвящимися потоками вторичных требований.
3. Построены эффективные алгоритмы наховдевия решения оптимизационной задачи на приоритетном множестве.
4. Найдена дисциплина, обслуживания, для которой построен эффективный алгоритм нахождения ее параметров по заданным средшш длинам очередей.
Таким образом, теоретические исследования позволили решить важные и конкретные задачи.
Теоретическая и практическая ценность. Работа теоретическая. . Разработанные методы применимы для достаточно широкого класса систем. Предлагаемые алгоритмы решения, в основном, эффективные. Результаты работы позволяют дать.ответ на практкчесішв вопросы о качестве оптимизации очередей.
Апробация работы. Результаты работы докладывались на ряде . конференций "Проблемы теоретической кибернетики" (Иркутск, 1985)., "Системы обслуживания и сети связи" (Витебск, 1990),". "Дискретная математика" (МТУ, 1986, ,1989, 1992, 1995), "Интеллектуальные среды" (МГУ,1995); на семинарах институтапроблем управления
РАН, МГУ, Вычислительного центра РАН, Ярославского государственного университета.
Публикации. Основные результаты диссертации опубликованы в 15 статьях.
Структура и объем работы. Диссертация состоит из введения, семи глав и списка литературы. Изложена на 293 страницах. Библиография - 84 наименования.
