автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Исследование алгоритмов управления очередями в вычислительных системах с разделением времени

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МОДЕЛЕЙ УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССШ И ВЫВОД ОБЩИХ СООТНОШЕНИЙ

1.1. Тенденции развития современных операционных систем.

1.2. Обзор существующих моделей.

1.3. Вывод общих соотношений для моделей систем с разделением времени

ГЛАВА 2. ИССЛЕДОВАНИЕ МНОГОУРОВНЕВЫХ АЛГОРИТМОВ С

УСТАНОВКОЙ В КАЖДУЮ ОЧЕРЕДЬ ЗАЯВОК ОДИНАКОВЫХ ПРИОРИТЕТНЫХ КЛАССОВ. * . .;/.

2.1. Относительные приоритеты

2.1.1. Постановка задачи.

2.1.2. Вывод основных функциональных соотношений

2.1.3. Алгоритм поиска решения

2.1.4. Теорема единственности.

2.2. Абсолютные приоритеты.

2.2.1. Постановка задачи.

2.2.2. Вывод основных функциональных соотношений

ГЛАВА 3. ИССЛЕДОВАНИЕ МНОГОУРОВНЕВЫХ АЛГОРИТМОВ С ВОЗМОЖНОСТЬЮ УСТАНОВКИ В КАЖДУЮ ОЧЕРЕДЬ

ЗАЯВОК НЕОДИНАКОВЫХ ПРИОРИТЕТНЫХ КЛАССОВ.

3.1. Относительные приоритеты

3.1.1. Постановка задачи.

3.1.2. Вывод осноёных функциональных соотношений . . . . . *

3.1.3. Алгоритмы поиска решения.

3.2. Абсолютные приоритеты.

3.2.1. Постановка задачи.

3.2.2. Вывод основных функциональных соотношений . •

3.3. Анализ частных случаев многоуровневых алгоритмов.

3.3.1. Простейший многоуровневый алгоритм с относительными приоритетами

3.3.2. Многоуровневый алгоритм с относительными приоритетами и бесконечным квантом обслуживания.

3.3.3. Простейший многоуровневый алгоритм с абсолютными приоритетами.

3.3.4. Многоуровневый алгоритм с абсолютными приоритетами и бесконечным квантом обслуживания.

3.3.5. Алгоритм циклического планирования с квантованием.

3.3.6. Бесприоритетное обслуживание с бесконечным квантом.

ГЛАВА 4. ЧИСЛЕННЫЙ АНАЛИЗ ДИСЦИПЛИН УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕССШ

4.1. Сравнение различных алгоритмов.

4.2. Синтез алгоритмов распределения времени центрального процессора.

4.3. Выбор рациональной дисциплины обслуживания заявок в центре обработки данных (ПОД) системы "СИРЕНА".

Актуальность темы^

Одной из основных экономических задач XI пятилетки; сформулированных на ХХУ1 съезде КПСС, является задача повышения эффективности общественного производства / I /. Решение этой задачи возмогло лишь при условии повышения эффективности всех отраслей народного хозяйства. Наиболее быстрорастущей научно-технической отраслью в настоящее время является разработка автоматизированных систем переработки информации и управления, созданных на основе совместного использования удалённых терминалов; каналов связи и электронных вычислительных машин. Современные АСУ, - работающие в режиме реального времени, использующие диалоговые режимы человеко-машинных систем,' позволяющие производить интенсивные обновления банка данных большой размерности, - требуют от операционных систем обеспечения малого времени реакции на запросы пользователей* Проблема эффективного использования человеко-машинных систем, предназначенных для переработки информации и автоматизации процессов управления организационно-техническими системами,' систем телеобработки информации в АСУ привела к задаче управления вычислительным процессом, позволяющей реализовать концепцию мультипрограммирования и разделения времени. Эта задача сводится к разработке различных алгоритмов распределения основных ресурсов АСУ - времени центрального процессора ЭВМ, оперативной и внешней памяти.

Особую роль в изучении алгоритмов распределения времени центрального процессора играет теория приоритетных систем /3,7,9/« По приоритетным системам имеется большое число работ. Основные результаты обобщены и изложены в монографиях /2,19,23,24¿34/. Наиболее простым алгоритмом управления вычислительным процессом является круговой циклический алгоритм; который позволяет организовать одну очередь /46,50/; Каждой заявке выделяется ограниченное время обслуживания,: по истечении которого заявка» в случае неполного обслуживания» ставится в конец очереди; Если заявка в течение выделенного кванта была обслужена полностью, то она покидает систему. Круговой пщслический алгоритм не учитывает число квантов выделенных заявкам*, требующим большего времени обслуживания; Указанное свойство принимается во внимание в многоуровневых алгоритмах. Простейшим из них является многоуровневый алгоритм с одним входом, согласно которому организуется А/ очередей. Модель этого алгоритма была рассмотрена в /39/. В реальной ситуации может возникнуть необходимость разбиения заявок на классы,1 т.е. назначение внешнего приоритета. Эту особенность учитывает многоуровневый алгоритм со многими входами, рассмотренный в /40/; В /52/ был рассмотрен другой алгоритм, согласно которому в систему поступают К пуассоновских потоков заявок различных классов ( I £ Л N ), причём первоначально заявка К -го класса поступает в К -ю очередь (всего А/ очередей). Если заявка за выделенный ей квант времени не была обслужена до конца| то она переходит в конец менее цриоритетной очереди, т.е. индекс очереди увеличивается на единицу. Если заявка в течение выделенного кванта времени была обслужена полностью,' то она покидает систему;*

Рассмотренным моделям описанных выше алгоритмов присущ общий недостаток: они не учитывают вынужденные при обслуживании заявок прерывания^ которые могут произойти в реальной ситуации; вследствие, например, обращения к периферийным устройствам ввода-вывода; Для большинства современных операционных систем характерен следующий алгоритм распределения времени центрального процессора: при наступлении прерывания по вводу-выводу обслуживание заявки прекращается, а после завершения прерывания заявка поступает в конец более приоритетной очереди, причём выделенный квант обслуживания уменьшается.

Цель работы заключается: а) в разработке обобщённой модели алгоритмов распределения времени центрального процессора в вычислительных системах,' учитывающую: - многоуровневую приоритетную структуру системы очередей;' - изменение приоритетов заявок в процессе обслуживания; - квантование времени; - изменение кванта обслуживания; - прерывания по обращению к периферийным устройствам ввода-вывода; - произвольные законы распределения заявок; б) в использовании полученной модели для анализа и синтеза вычислительных систем, работающих в АСУ реального времени.

Основными задачами исследования являются: исследование влияния управляющих параметров (первоначальный размер кванта обслуживания,5 число приоритетных уровней и классов; интенсивность вход-» ного потока, предполагаемое время обслуживания заявок, время об« работки прерывания заявок по вводу-выводу и т.д.) на средние характеристики системы с учётом прерываний по вводу-выводу, обоснование эффективности работы различных алгоритмов управления вычислительным процессом операционных систем, использующихся в задачах класса АСУ Ш.

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

Научная Новизна работы. Впервые разработана обобщённая модель алгоритмов распределения времени центрального процессора, учитывающая обращения заявок к периферийным устройствам ввода-вывода. Получены соотношения; позволяющие определить средние характеристики системы в этих условиях; Доказаны теоремы единственности решения систем линейных уравнений относительно средних времён ожидания заявок в приоритетных очередях. Выведены выражения для определения вероятностных характеристик поведения заявок в системе,- вероятности наступления прерывания по вводу-выводу," конца обслуживания заявок и т.д. Дан подробный анализ различных дисциплин управления вычислительным процессом;

Практическая ценность. Разработанная обобщённая модель даёт возможность более точно отражать функционирование различных алгоритмов диспетчеризации вычислительного процесса по сравнению с существующими моделями. Выведены соотношения;' пригодные для инженерных расчётов, позволяющие получить управляющие параметры вычислительного процесса в соответствии с любым заданным критерием оценки; т.е. решить задачу синтеза многоуровневого алгоритма. Диссертационная работа велась в Институте проблем управления (автоматики и телемеханики) в соответствии с Программой ПСНТ СМ СССР на I98I-I985 гг; по решению научно-технической проблемы 0.80.09 -задание ГКНТ 05.02.03 в рамках плановой теш (номер гос; регистрации 0182.8 027521): "Создать и ввести в эксплуатацию фрагмент общесоюзной автоматизированной системы управления продажей билетов и бронированием мест на внутренних воздушных линиях".

Реализация -результатов работы;- Результаты диссертационной работы были использованы в Главном вычислительном центре гражданской авиации при разработке технического проекта на подсистему информационного обмена общесоюзной АСУ продажей билетов и бронированием мест на внутрисоюзных воздушных линиях (АСУ "СИРЕНА") , а также при написании технического задания на разработку автоматизированной подсистемы управления отправками АСУ "АВРОРА" (регистрация пассажиров; управление загрузкой сашлётов, выпуск полётной документации); Предложенный метод выбора рациональной дисциплины обелуживания запросов позволил повысить пропускную способность АСУ "СИРЕНА." при высокой загрузке на 40$ и получить годовой экономический эффект в сумме 63 тыс.рублей и улучшить характеристики специализированного пакета подсистемы управления АСУ "АВРОРА" в среднем на 10$.

Апробапия работы« Результаты работы докладывались на Второй Школе по автоматизированным системам массового обслуживания (г.Фрунзе, 1980), на Третьей Школе по автоматизированным системам массового обслуживания (г.Винница, 1981); на Всесоюзном совещании по высокопроизводительным вычислительным системам (г.Тбилиси, 1981), на научно-техническом семинаре "Теория и техника автоматизированных систем массового обслуживания" в ЩЩШ им,Ф.Э.Дзержинского (г.Москва, 1982), на Всесоюзном совещании по автоматизированным системам массового обслуживания (г.Нальчик, 1982). публикации. Основное содержание диссертации отражено в 5 печатных работах /6,15,25,26,27/.

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения;' списка литературы и приложения. Общий объём 135 стр., 31 рис., 4 табл., 58 наименований библ.

ЗАКЛЮЧЕНИЕ

Сформулируем основные научные результаты диссертации:

1. Впервые разработана обобщённая модель алгоритмов распределения времени центрального процессора, учитывающая:

- многоуровневую приоритетную структуру системы очередей;

- изменение приоритетов заявок в процессе обслуживания;

- квантование времени;

- изменение кванта обслуживания;

- прерывания по обращению к периферийным устройствам ввода-вывода;

- произвольные законы распределения длительностей обслуживания заявок и интервалов прерываний обслуживания по вводу-выводу.

2. Рассмотрены два семейства алгоритмов: алгоритмы с установкой в каждую очередь заявок одинаковых приоритетных классов, алгоритмы с возможностью установки в каждую очередь заявок неодинаковых приоритетных классов. Выведенные соотношения пригодны для инженерных расчётов и применялись при выборе рациональной дисциплины обслуживания заявок в центре обработки данных системы "СИРЕНА" и для подсистемы управления отправками системы "АВРОРА".

3. На основе проведённого анализа различных дисциплин управления вычислительным процессом показана перспективность использования многоуровневых алгоритмов распределения времени центрального процессора в задачах класса АСУ МО.

4. Получивший в диссертации дальнейшее развитие математический аппарат моделирования алгоритмов диспетчеризации вычислительного процесса с учётом обращения заявок к периферийным устройствам ввода-вывода реально отражает функционирование различных алгоритмов, применяющихся в современных АСУ реального времени.

5. Различие среднего времени ответа для разных алгоритмов управления вычислительным процессом особо ощутимо при большой нагрузке J>> 0,8. Большим преимуществом многоуровневых алгоритмов является способность к работе при увеличении предельного уровня загрузки, т.е. в условиях перегрузки. При этом средние времена пребывания в системе высокоприоритетных заявок принимают конечные значения.

6. Сравнение двух типов алгоритмов, рассмотренных в главе 2 и главе 3,и в случае относительных приоритетов (многоуровневых алгоритмов с установкой в каждую очередь заявок одинаковых приоритетных классов и алгоритмов с возможностью установки в каждую очередь заявок неодинаковых приоритетных классов) показало, что алгоритмы первого типа позволяют быстрее обслуживать более приоритетные заявки за счёт обслуживания менее приоритетных заявок по сравнению с алгоритмами второго типа. Ещё большую дифференциацию в обслуживании более приоритетных заявок за счёт менее приоритетных заявок вносит использование алгоритмов с абсолютными приоритетами.

7. Увеличение числа уровней многоуровневых дисциплин диспетчеризации особенно существенно в случае законов распределения длительностей обслуживания заявок и интервалов обращения к устройствам ввода-вывода с большой дисперсией.

8. Введение принципа квантования для заявок, обращающихся в процессе обслуживания к устройствам ввода-вывода, ухудшает средние характеристики системы, если время переключения обслуживающего прибора tv О . Уменьшение кванта обслуживания при больших ведёт к увеличению среднего времени пребывания заявок в системе. Однако, принцип квантования позволяет уменьшить время пребывания в системе коротких заявок за счёт длинных.

9. Выбор той или иной дисциплины диспетчеризации, а также набора управляющих параметров следует производить всякий раз для каждою конкретной"' АСУ-МО, исходя из заданного критерия оценки.

10. Для уменьшения среднего суммарного времени пребывания заявок в системе, взвешенного по интенсивности входного потока, необходимо отдавать наивысший приоритет заявкам, имеющим меньшую длительность обслуживания и большую частоту обращения к устройствам ввода-вывода.

11. Характеристики, полученные аналитическим путём с помощью разработанных моделей, хорошо согласуются с характеристиками, полученными в результате непосредственных измерений на действующих АСУ 'МО., и полунатурального моделирования, подтверждают теоретические результаты и показывают эффективность предложенных многоуровневых алгоритмов диспетчеризации вычислительного процесса.

1. КПСС. Съезд, ХШ-й. Москва. 1981. Материалы ХХУ1 съезда КПСС. - М.: Политиздат, 1981.

2. Авен О.И., Коган Я.А. Управление вычислительным процэссом в ЭШ. -М.: Энергия, 1978. 240с.

3. Броншейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно-вычислительных системах. М.: Наука, 1976. - 220с.

4. Бусленко Н.П. Моделирование сложных систем. -М.: Наука, 1978. 399с.

5. Быковский В.П., Шрейберг Я.Д. Моделирование работы и выбор конфигурации обрабатывающего комплекса телеавтоматической системы реального времени. В кн.: Модели систем распределения информации и их анализ. - М.: Наука, 1982. - с.101-112.

6. Вишневский В.М., Ляшев С.Г. Обобщение некоторых алгоритмовраспределения времени центрального процессора. В кн.: Третья Школа по автоматизированным системам массового обслуживания. Винница:Винницкий политехнический институт, 1981.-с.27.

7. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. М.:МГУ,1973.-447с.

8. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. -М.: Наука, 1966. 431с.

9. Джейсуол Н. Очереди с приоритетами. -М.: Мир, 1973. 279с.

10. Дроздов Е.А., Комарицкий В.А., Пятибратов А.П. Электронные вычислительные машины единой системы. -М.: Машиностроение, 1981. 648с.

11. Духовный Й.М. Однолинейная система обслуживания с чередованием приоритетов. Проблемы теории информации, 1969, $ 2, 61-7Ю.

12. Единая система электронных вычислительных машин. Операционная система. Генерация* Руководство системного программиста. Ц51. 804.006 Л 33. М.: 1980. - 105с.

13. Единая. система электронных вычислительных машин. Операционная система. Режим разделения времени. Генерация системы. Руководство системного программиста. Ell.804.000 Л5. М.: 1980. - 120с.

14. Единая система электронных вычислительных машин. Операционная система. Режим разделения времени. Общее описание. Ell.804.00 Д1. -М.:1980.- 109с.

15. Жожикашвили В.А., Вишневский В.М., Ляшев С.Г. Обобщённая модель вычислительного процесса.- В кн.: Всесоюзное совещание по высокопроизводительным вычислительным системам.

16. Тезисы докладов. Тбилиси, сентябрь 1981. М.: Институт проблем управления, 1981. - с.24-25.

17. Жожикашвили В.А., Новохатний A.A., Мицкевич Л.В., Силаев E.H. Телеавтоматическая система массового обслуживания "СИРЕНА".-Приборы и системы управления, 1970, № 9.- с.15-20.

18. ЭВД. Зарубежная радиоэлектроника, 1977, № 7.-с.33-70. 19. Клейнрок Л. Вычислительные системы с очередями.-М. :Мир,1979.-598с.

19. Клейнрок Л. Коммутационные сети. -М.: Наука, 1970. 255с.

20. Клейнрок л. Теория массового обслуживания. М.Машиностроение, 1979. - 620с.

21. Климов Г.П. Стохастические системы обслуживания. М.: Наука, 1966. - 243с.

22. Липаев В.В. Распределение ресурсов в вычислительных системах.-М.: Статистика, 1979. 247с.

23. Липаев В.В., Яшков С.С. Эффективность методов организации вычислительного процесса в АСУ. -М.: Статистика, 1975.

24. Ляшев С.Г. Моделирование работы одной вычислительной системы со многими ресурсами. В кн.: Вторая Школа по автоматизированным системам массового обслуживания. Фрунзе, май, 1980. Тезисы докладов. -М.: Институт проблем управления, 1980.-с.53.

25. Мартин Дж* Системный анализ передачи данных. М.: МИР, 1975, т.2. - 431с.

26. Основы теории вычислительных систем. Под ред. С.А.Майорова.-М.:Высшая школа,1979. 407с.

27. Риордан Дж* Вероятностные системы обслуживания. М.: Связь, 1966. - 184с.

28. Саати Т.Д. Элементы теории массового обслуживания и её приложения. -М.: Сов.радио, 1971. 520с.

29. Феллер В. Введение в теорию вероятностей и её приложение. T.I. -М.: Мир, 1967. 488с.

30. Феррари Д. Оценка производительности вычислительных систем.-М.: Мир,1981. 576с.

31. Шерр А. Анализ вычислительных систем с разделением времени.-М.: Мир, 1970.

32. Шура-Бура М.Р., Ковалевич Э.В., Марголин М.С. и др. Операционная система ДОС ЕС. Общие положения. М.: Статистика, 1975. - 120с.

33. Яшков С.Ф» Некоторые математические модели систем с разделением времени. В кн.: Цифровая вычислительная техника и программирование. Вып.7. -М.: Сов.радио, 1972.

34. ADIRI I. A dynamic time-sharing priority queue. J,ACM, 1971, V. 18, No 4. - p.603-610.

35. ADIRI I. A note on some mathematical models of time-sharing systems. J.ACM, 1971, V.18, I\To 4. - p.611-615.

36. ADIRI I., Avi-Itzhak B. A time-sharing models with many queues. Oper. res., 1969, V.17, No 6. - p.1077-1089.

37. BABAD J.M. A generalized multi-entrance time-sharing priority queue. J.ACM, 1975, V.22, No 2. - p.231-247.

38. Baskett P., Ohandy K.M., Muntz R.R., Palacious F.G. Open, closed and mixed networks of queues with different classes of customers. J.ACM, 1975, No 2. - p.248-260.

39. Borgerson B.R., Hanson M.L., Hartley P.A.

40. The Evolution of the Sperry Univac 1100 Series: A History, Analysis, and Projection. ACM. Communications. . V.21, No 1, 1978, p.25-43.

41. Buzon J.P. Computational algorithme of closed queueing networks with, exponentional servers. Commun. АСЫ, 1973, V.16, No 9. p.527-531.

42. Cobham A. Priority assignment in waiting time problems. -Oper. res., 1954, V.2, No 1. p.70-76.

43. Coffman E.G., Kleinrock L. Feedback queueing models for time-shared systems. J.ACM, 1968, V.15, No 4 - p.549-576.

44. Kleinrock L. Analysis of time-shared processor, Naval Res. Logistics Quart., 1964, V.2, No 1. - p.59-73.

45. Kleinrock L. Time-shared systems: A theoretical treatment. -J.ACM, 1967, V.14, No 2. p.242-261.

46. Kleinrock L., Muntz R.R. Processor sharing queueing models of mixed scheduling disciplines for time-shared systems. J.ACM, 1972, V.19, No 3. - p.464-482.

47. Little J.D.C. Aproof of the queueing formula L-AVi. Oper. res., 1961, V.9, No 3. - p.383-387.

48. McKinney J.M. A survey of analytical time-sharing models. -Comput. Surv., 1969, V.1, No 2. p.105-116.

49. PDP 11. Getting RSX 11 on the oir. Version V007A. - U.S.A.: Digital Equipment Corporation, 1974. - 119 p.

50. Rosberg Z., Adiri I. Multilevel queues with external priorities. J.ACM, 1976, V.23, No 4. - p.680-690.

51. Série IRIS, Niveau IRIS 80. Générateur de systèmes SIRIS 8. Version СЮ. Manuel d'utilisation et d'opérations. 56F27172 REV1. CII HONEYWEL BULL. Paris: Centre de documentation, France, 1978. - 117 p.

52. Shemer J.E. Some mathematical considerations of time-sharing scheduling algorithms. J.ACM, 1967, V.14, No 2 - p.262-272.

53. SPERRY UNIVAC 1100 SERIES. OPERATING SYSTEMS. Concepts of

54. EXEC-8 internal operation. PRINTED III U.S.A.: SPSRRY RAID CORPORA!1 lOli, 1975.

55. Thomson K. UNIX Time-sharing System: UNIX B1PLEEENTATI0N. -Bell System Technical Journal, 1978, V.57, Ho 6. p.1931-1946.

56. Van Vliet R., Wakker W. A time-sharing system for the PDP 8 Series. U.S.: Departament of Computer Science. Mathematical Centrum, 1975/77. - p.1-65.

57. Welch P.D. On a generalized. M/G/1 queueing process in which the first customer of each busy period received exceptional service. Oper. res., 1964, V.12, No 5. - p.736-752.