Методы и алгоритмы диспетчеризации вычислений с динамически изменяющимися приоритетами тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Дубовик, Александр Евгеньевич

• Дубовик, Александр Евгеньевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Дубовик, Александр Евгеньевич

ВВЕДЕНИЕ

Глава 1. АНАЛИЗ МЕТОДОВ ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ :

1.1. Методы диспетчеризации вычислений в операционных системах

1.1.1. Диспетчеризация в операционной системе ДИАМС

1.1.2. Диспетчеризация в операционных системах реального времени VAXELN, QNX и USIX

1.1.3. Диспетчеризация в операционной системе UNIX

1.2. Проблемы диспетчеризации в сетях ЭВМ

1.3. Постановка задачи исследования

Глава 2. ОПТИМАЛЬНЫЙ ЧИСЛЕННЫЙ МЕТОД

ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ

2.1. Методы оптимального управления и экстремальные задачи

2.2. Основы оптимального численного метода диспетчеризации вычислений и критерий оптимальности

2.3. Решение задачи минимизации критерия

Глава 3. РЕАЛИЗАЦИЯ ЧИСЛЕННОГО МЕТОДА

ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ

3.1. Примеры применения численного метода

3.2. Технология реализации в ОС LINUX

3.3. Технология реализации в сетях ЭВМ

3.4. Особенности реализации метода в сетях типа ATM

3.5. Управление группами приоритетов в многопроцессорных системах

3.6. Использование метода для защиты от несанкционированного доступа

3.7. Примеры программной реализации

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы диспетчеризации вычислений с динамически изменяющимися приоритетами»

Одной из основных задач операционных и сложных вычислительных систем и комплексов является рациональное распределение (планирование) ресурсов вычислителей между пользователями и выполняемыми вычислительными процессами (задачами). При построении управляющих программ (планировщиков, диспетчеров) используется целый ряд различных методов и алгоритмов диспетчеризации вычислений. Управляющие программы при любом из методов диспетчеризации вычислений решают задачу минимизации времени ожидания и сведения к минимуму возможных потерь информации. При этом учитывается и оценивается время ожидания вычислительных процессов (заявок, задач, сообщений), и то обстоятельство, что обработка информации, особенно в диалоговых, больших коммуникационных и других вычислительных системах производится путем многократного выполнения циклов, состоящих из запроса задачи абонента-пользователя и/или реакции, ответа ЭВМ (узла сети, сервера и т.д.). Анализ существующих методов диспетчеризации вычислений в различных операционных системах показал имеющиеся ограничения применяемых методов. Методы и алгоритмы, лежащие в основе управляющих программ для решения разнообразных задач диспетчеризации вычислений реализуют, в основном, традиционные вычислительные дисциплины обслуживания "первым пришел - первым обслужен" или "последним пришел - первым обслужен", а также дисциплины обслуживания на основе очередей приоритетов. Первые из вышеуказанных методов основываются на учете только на одного параметра - времени поступления заявки на обслуживание вычислительного процесса (сообщения). Второй метод, учитывая особенности каждого конкретного процесса: размер процесса, приоритет процесса, содержащуюся в нем информацию и т.д., как правило, не учитывает время поступления запроса. В результате могут происходить значительные задержки в обслуживании других процессов и сообщений и как следствие отказы в работе систем управления при предельных нагрузках системы и/или ограниченном времени ожидания). В ряде случаев при наличии значительного количества вычислительных процессов в системе (или поступающих сообщений), при анализе подобных вычислительных систем, и выборе алгоритмов диспетчеризации вычислительных процессов пытаются использовать методы теории массового обслуживания, учитывая так или иначе известное количество входных потоков задач (сообщений) и их вероятностные характеристики. Однако, практическое решение таких задач диспетчеризации вычислений (да и др. подобных задач) является достаточно сложным и имеет неоднозначный ответ. Кроме того при диспетчеризации вычислений следует учитывать, что в подобных приоритетных вычислительных системах и сетях ЭВМ всегда имеется вероятность того, что низкоприоритетные процессы вовсе не получат вычислительных ресурсов. Поэтому дать полную практическую, адекватную реальности оценку работы подобных существующих вычислительных систем методами теории массового обслуживания .можно лишь приближенно, так как эти методы требуют учета столь многочисленных разнообразных вероятностных факторов, которые практически невозможно выразить количественно и тем более объединить в единый оценочный критерий. В этой связи задача разработки эффективных методов и алгоритмов диспетчеризации вычислений, особенно как для разнообразных задач разделения времени, так и реального времени, связанных со сбором, обработкой и передачей информации с многочисленных источников, а также задач коммуникации и маршрутизации сообщений в локальных и глобальных сетях ЭВМ, является чрезвычайно актуальной и важной.

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

В диссертационной работе решены следующие основные задачи:

- дан сравнительный анализ существующих методов и алгоритмов диспетчеризации вычислений в различных вычислительных системах;

- разработан оптимальный численный метод и технологии диспетчеризации вычислений с динамически изменяющимися приоритетами в реальном времени;

- разработан критерий оптимальности и приведена строгая математическая формализация решения задачи, оптимизации численного метода диспетчеризации вычислений с динамически изменяющимися приоритетами;

- исследованы возможности практической реализации разработанного численного метода и технологий диспетчеризации вычислений в различных вычислительных системах;

- проведены исследования возможностей разработанного численного метода диспетчеризации вычислений при моделировании временных характеристик вычислительных процессов и систем для оценки их рабочих характеристик, таких как быстродействие и пропускная способность;

- показаны возможности численного метода диспетчеризации для защиты информации от несанкционированного доступа.

В теоретических и экспериментальных исследованиях использованы теория оптимального управления и решения экстремальных задач , методы динамического программирования и вычислительной математики.

В диссертации получены следующие результаты, характеризующиеся научной новизной:

- разработан новый, аналитически формализованный и обоснованный численный метод диспетчеризации вычислений в реальном масштабе времени;

- доказана эффективность использования предложенного метода для численной диспетчеризации вычислительных процессов в реальном масштабе времени;

- показана возможность использования предложенного численного метода для диспетчеризации вычислений в операционных системах, системах коммуникации сообщений и сетях ЭВМ;

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

Результаты диссертационной работы получены в Институте электронных управляющих машин в рамках Федеральной целевой программы «Реструктуризация и конверсия обороной промышленности» (1996-2000гг.) и отражены в научно-техническом отчете «Разработка численных методов и алгоритмов диспетчеризации вычислений с динамически изменяющимися приоритетами», подготовленным для Министерства науки и технической политики в соответствии с его Распоряжениями N 636 Ф от 17.03.1997 и 329 Ф от 6.04.1998.

Результаты работы используются в учебном процессе Московского государственного института радиотехники, электроники и автоматики (МИРЭА). Разработан методический материал для практических занятий по методам диспетчеризации вычислений для студентов кафедры «Управляющие ЭВМ». Результаты работы используются также при создании сети ЭВМ МДМ-банка и внедрены в эксплуатацию в составе прикладного программного обеспечения для управления технологическими процессами на Красногорской компрессорной станции в ООО «Уралтрансгаз» [52].

Материалы диссертационной работы докладывались и обсуждались:

- на 3-ей Международной конференции SUUG'92, Санкт-Петербург, 1992 г.;

- на Международной конференции «Free Soft 93», Москва, 1993 г.

- на Международной конференции «Открытые системы - решения для нового мира», Москва, 1994 г.;

- на Международной конференции EAST-WEST «Информационные технологии в проектировании - Information technology in design», Москва, 1996 г.;

- на IV Международной конференции «Развитие и применение открытых систем», Нижний Новгород, 1997 г.;

- на I Международной конференции «Цифровая обработка сигналов и ее применение - DSPA-98», Москва, 1998 г.;

- на II Международной конференции «Идентификация систем и задачи управления», SICPR.0'03, Москва, ИПУ, 2003 г.

Основные результаты работы отражены в 12 научных публикациях.

1.Дубовик А.Е. Численный метод диспетчеризации вычислений для систем промышленной автоматизации. Автоматизация в промышленности. №12. 2003.

2. Дубовик А.Е. Численный алгоритм диспетчеризации вычислений с динамически изменяющимися приоритетами. Тезисы доклада 4ой научно-практической конференции "Современные информационные технологии в управлении и образовании", Москва, НИИ «Восход». 2003.

3. Дубовик А.Е., Дубовик Е.А. Оптимальный метод диспетчеризации вычислений. Сборник докладов 3-ей Международной конференции SUUG

Society for UNIX User Groups - сообщество групп пользователей ОС UNIX), Санкт-Петербург, SUUG, 1992г.

4. Дубовик А.Е., Дубовик Е.А. Управляющие программы с динамически изменяющимися приоритетами. В сборнике докладов международной конференции "FrecSoft 93", Москва, SUUG,1993.

5. Дубовик А.Е., Дубовик Е.А. Численный метод диспетчеризации вычислений с динамически изменяющимися приоритетами. Тезисы докладов Международной конференции "Открытые системы - решение для нового мира", Москва, SUUG, 1994.

6. Dubovik A.,Ye.,Dubovik Ye.A. The optimal numeric metod of calculation dispatching with dynamic priorities. Сборник докладов международной конференции EAST-WEST, EWITD'96., Москва, 1996.

7. Дубовик A.E., Дубовик Е.А. PC Based CAD Workstation. В сборнике докладов Международной конференции EAST-WEST "Информационные технологии в проектировании" - Information technology in design, EWID'96, стр. 147-152, Москва, 1996.

8. Дубовик А.Е., Дубовик Е.А. Численный метод коммутации и маршрутизации сообщений, в сборнике докладов IV международной конференции "Развитие и применение открытых систем", Нижний Новгород, 1997, стр. 9095.

9. Дубовик А.Е., Дубовик Е.А. Основы и методы многоканального измерения функций различного спектрального состава. В сборнике докладов 1-ой Международной конференции "Цифровая обработка сигналов и ее применение" DSPA'98, т.4, стр. 102-112, Москва, 1998.

10. Dubovik A.,Ye.,Dubovik Ye.A. Multichahhel measurement basics and method for functions with different spectral composition. The ist International

Conference "Digital signal processing and its applications', DSPA'98, vol IV-E, 5862, Moscow, 1998.

11. Прохоров H.Jl., Дубовик A.E. «Системное программное обеспечение ЭВМ. Методы диспетчеризации вычислений». Методические указания по выполнению практических занятий для студентов специальности 220100. МИРЭА, 1999.

12. Дубовик Е.А., Дубовик А.Е. Оптимальные методы и технологии многоканального измерения функций различного спектрального состава. Сб. докладов II Международной конференции «Идентификация систем и задачи управления», SICPRO'03, Москва, ИПУ РАН, раздел 6-8, 2003.

В опубликованных работах лично соискателю принадлежат следующие результаты:

- разработка метода, численных алгоритмов, программ и технологий реализации диспетчеризации вычислений с динамически изменяющимися приоритетами;

- разработка различных модификации численного алгоритма диспетчеризации вычислений для эффективного использования в сетевой архитектуре, узлах сети ЭВМ и для эффективной загрузки линий связи;

- разработка метода динамической защиты информации и передачи данных от несанкционированного доступа;

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

Заключение диссертации по теме «Вычислительные машины и системы», Дубовик, Александр Евгеньевич

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В процессе выполненных диссертационных исследований, направленных на повышение эффективности методов и алгоритмов диспетчеризации вычислений, получены следующие основные результаты:

1. Проведен последовательный анализ методов и алгоритмов диспетчеризации вычислений в различных операционных системах и сетях ЭВМ. Показаны особенности и ограничения применяемых методов диспетчеризации вычислений.

2. Разработан, обоснован и аналитически формализован новый оптимальный численный метод и алгоритмы диспетчеризации вычислений с динамически изменяющимися приоритетами, базирующийся на экстремальной теории.

3. Проведена новая модификация вычислительных процедур метода динамического программирования, ориентированная для решения экстремальных задач в реальном масштабе времени.

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

5. Приведенные исследования показали, что оптимальный численный метод диспетчеризации вычислений и его технологии могут быть эффективно и достаточно просто использованы в любых приоритетных открытых операционных системах и сложных вычислительных системах и комплексах.

6. Показано, что технология оптимального численного метода диспетчеризации вычислений может эффективно использоваться для диспетчеризации вычислений с динамически изменяющимися приоритетами, как в любых узлах сети ЭВМ, так и для регулирования загрузки различных линий связи локальных и глобальных сетях ЭВМ.

7. В работе показаны принципы реализации численного метода диспетчеризации в различных вычислительных системах и показаны его потенциальные возможности. Приведены результаты внедрения метода в сеть МДМ-банка и в составе прикладных программ АСУ ТП Красногорской компрессорной станции.

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

9. Полученный в работе оптимальный численный метод диспетчеризации вычислений позволяет достаточно эффективно заниматься моделированием самых сложных вычислительных систем и процессов для получения оценок их основных временных и рабочих характеристик, таких как быстродействие, пропускная способность и др.

Список литературы диссертационного исследования кандидат технических наук Дубовик, Александр Евгеньевич, 2004 год

1. Дисковая Диалоговая Операционная система ДИАМС. Описание. НПО "Центрпрограммсистем", 1980.

2. Программирование в системе VAXELN, М.: ВЦП, 1987.

3. UNIX SVRIV Operation Manual, Jan. 1992, p. 4-164--4-167

4. Лорин Г., Дейтел Х.М. Операционные системы. М.:Финансы и статистика. 1984.

5. Кузьминский М. Открытые системы. N1, с. 18-22. 1997.

6. OS MVS. System Tuning Guide. 1983.

7. M.Loukides System Tuning. O'Reillu Assoc., 1992.

8. Frish A. Essential System Administration. 2nd Ed. O'Reili Assoc., 1995.

9. А. Робачевский, Операционная система UNIX, С-Пб, BHV, 1997.

10. O.Bach MJ. The Design of the UNIX Operating System. Prentice Hall. 1990.

11. Dubovik Ye.A. Optimal adaptive sampling in measurement system "Automation and Remote Control", vol 3, 15, part 1, p 769-775. may 1975.

12. Дубовик E.A. Многоканальное измерение функций различного спектрального состава. ИКА, 1 4, с 14-24. 1984.

13. Дубовик А.Е., Дубовик Е.А. Оптимальный метод диспетчеризации вычислений. Сборник тезисов докладов 3-ей международной конференции SUUG'92, Санкт-Петербург, 1992г.

14. Беллман Р. Динамическое программирование, М.: И.Л.1960.

15. Dubovik A.,Ye.,Dubovik Ye.A. The optimal numeric metod of calculation dispatching with dynamic priorities. Сборник докладов международной конференции EAST-WEST, EWITD'96.

16. Сотовский Б. Нужна ли вам сеть ATM, Computerweck N 14-15, стр. 11, 1997.

17. Дубовик А.Е., Дубовик Е.А. Управляющие программы с динамически изменяющимися приоритетами. В сб. докладов международной конференции "FreeSoft 93", Москва, 1993.

18. Дубовик А.Е., Дубовик Е.А. Численный метод диспетчеризации вычислений с динамически изменяющимися приоритетами. Тезисы доклада международной конференции "Открытые системы решение для нового мира", Москва, 1994.

19. Дубовик А.Е., Дубовик Е.А. Численный метод коммутации и маршрутизации сообщений, в сб. докладов IV международной конференции "Развитие и применение открытых систем", Нижний Новгород, стр. 90-95, 1997.

20. Дубовик А.Е., Дубовик Е.А. Основы и методы многоканального измерения функций различного спектрального состава. В сб. докладов 1-ой Международной конференции "Цифровая обработка сигналов и ее применение" DSPA'98, т.4, стр. 102-112, Москва, 1998.

21. Dubovik A.,Ye.,Dubovik Ye.A. Multichahhel measurement basics and method for functions with different spectral composition. The ist International Conference "Digital signal processing and its applications', DSPA'98, vol IV-E, 58-62, Moscow, 1998.

22. Дубовик А.Е., Дубовик Е.А. PC Based CAD Workstation. В сб. докладов Международной конференции EAST-WEST "Информационные технологии в проектировании" Information technology in design, EWID'96, стр. 147-152, Москва, 1996.

23. Прохоров H.JI., Дубовик А.Е. Системное программное обеспечение ЭВМ. Методы диспетчеризации вычислений. Методические указания по выполнению практических занятий для студентов специальности 220100. МИ-РЭА, 1999.

24. Любимов А. Средства удаленного подключения к ЛВС. Компьютер-пресс, июль 1996.

25. Егоров Г.А., Красовский В.Е., Прохоров И.Л., Тювин Ю.Д., Шкамарда А.Н., Управляющие ЭВМ /под ред. Н.Л. Прохорова, МИРЭА, 1999.

26. Трифаленков И., Макоев О. Критерии выбора средств защиты информации, СЮ № 5,2002.

27. Егоров Г.А., Шяудкулис В.И., Л.И. Столяр. Операционная система USIX. Тезисы доклада международной конференции SUUG'94, Москва, 1994.

28. Е.А. Дубовик, Г.А. Егоров, В.А. Зимин. Вопросы построения измерительно-информационных систем на базе СМ ЭВМ. Приборы и системы управления, № 12, 1977.

29. Дубовик Е.А. Дубовик А.Е. Оптимальные методы и технологии многоканального измерения функций различного спектрального состава. Сб. докладов на II Международной конференции «Идентификация систем и задач управления» SICPRO'03, ИПУ РАН, Москва, 2003.

30. СМ ЭВМ: Комплексирование и применение /Г.А. Егоров, В.В. Родионов, М.А. Островский и др.; Под ред. Н.Л. Прохорова М.: Финансы и статистика, 1986.

31. Малые ЭВМ высокой производительности. Архитектура и программирование /Т.П. Васильев, Г.А. Егоров, B.C. Зонис и др.: Под ред. Н.Л. Прохорова. М.: Радио и связь, 1990.

32. Особенности реализации операционной системы USIX. Г.А. Егоров, H.JI. Столяр, В.И. Шяудкулис и др. // Тез. докл. III Международной конференции «Развитие и применение открытых систем». М., 1996.

33. СМ ЭВМ. Рекламный проспект. М.: ИНЭУМ, 2001.

34. Управляющие вычислительные комплексы. /Г.А. Егоров, В.Е. Красовский, А.Н. Шкамарда и др.; Под ред. H.JI. Прохорова. М.: Финансы и статистика, 2003.

35. Фабио Кон. Описание алгоритма Round Robin. Материалы сервера http://devius.cs.uiuc.edu.

36. Морис Дж. Бах. Архитектура операционной системы UNIX. Copyright 1986. Корпорация Bell Telephone Laboratories (перевод с английского к.т.н. Крюкова А.В.).

37. Процессы и их приоритеты в ОС UNIX. Открытые системы. № 6, 1997.

38. Г. Корн, Т. Корн. Справочник по математике (для научных работников и инженеров). М.: «Наука», 1974.

39. Диалоговая многотерминальная система для СМ ЭВМ. /В.П. Семик, F. П. Остапенко, А.Л. Фридман и др. М.: Финансы и статистика, 1983.

40. Справочник по системотехнике. Под ред. Маколо Р. М.: Сов. радио, 1971.

41. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

42. Флейшман Б.С. Исследование операций. М.: Сов. радио, 1972.

43. Фельбаум А.А. Основы теории оптимальных автоматических систем. М.: Наука, 1966.

44. Калаба Р. Беллман Р. Динамическое программирование и современная теория управления. М.: Наука, 1969.

45. Дубовик Е.А., Кантор А.В., Переверткин С.М., Щербакова Т.И. Оптимизация методов и устройств сбора и обработки информации. В сборнике Автоматическое управление и вычислительная техника, 1975, № 11.

46. Операционная система QNX. http://www.sdw.ru/qnx.

47. Болтянский В.Г. Математические методы оптимального управления. М.: «Наука», 1969.

48. Болтянский В.Г. Опимальное управление дискретными системами. М.: «Наука», 1973.

49. Математическая теория оптимальных процессов. JI.C. Понтрягин, В.Г. Болтянский, Р.В. Гамкрелидзе и др. - М.: «Наука», 1969.

50. Дубовик А.Е. Численный алгоритм диспетчеризации вычислений с динамически изменяющимися приоритетами. Тезисы доклада 4-й научно-практической конференции "Современные информационные технологии в управлении и образовании", М.: НИИ " Восход", 2003.

51. Дубовик А.Е. Численный метод диспетчеризации вычислений для систем промышленной автоматизации. Автоматизация в промышленности. №12.2003.

52. Коваленко Е. Архитектура ReliantlOOO. Открытые системы. №6. 1996.