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

ИНСТИТУТ ЭЛЕКТРОННЫХ УПРАВЛЯЮЩИХ МАШИН

На правах рукописи

ДУБОВИК АЛЕКСАНДР ЕВГЕНЬЕВИЧ

МЕТОДЫ И АЛГОРИТМЫ ДИСПЕТЧЕРИЗАЦИИ ВЫЧИСЛЕНИЙ С ДИНАМИЧЕСКИ ИЗМЕНЯЮЩИМИСЯ ПРИОРИТЕТАМИ

Специальности 05.13.15 - Вычислительные машины и системы, 05.13.11-Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных

сетей.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва 2004

Работа выполнена в Институте электронных управляющих машин (ИНЭУМ), г.Москва

Научный руководитель к.т.н., доцент Красовский В.Е.

Научный консультант д.т.н., ст.н.с. Егоров ГЛ.

Официальные оппоненты д.т.н., проф. Ильин В.Д.

к.т.н., ст.н.сотр. Остапенко Г.П.

Ведущая организация ОАО «НИИ Вычислительных комп-

лексов им. М. А.Карцева»

Защита состоится « 2- » ССЮИ-^ 2004 г. в часов на заседании диссертационного совета КР 409.009.14 при Институте электронных управляющих машин (ИНЭУИ) по адресу 119991, ГСП-1, Москва, Вавилова 24.

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан « <0» Я/^рДЛ^? 2004г.

И. О. ученого секретаря диссертационного совета

к.т.н., ст. н. сотр. Фукс В.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

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

Цельработы

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

Достижение поставленной цели предполагает решение следующих основных задач:

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

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

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

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

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

Методы исследования

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

Научная новизна работы

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

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

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

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

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

Практическая ценность и реализация результатов работы

- разработанные алгоритмы и технологии численного метода диспетчеризации вычислений нашли применение в составе прикладных программ, для диспетчеризации вычислений в специальной локальной сети и для приоритетного ввода информации в сети АСУ ТП;

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

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

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

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

Апробация работы

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

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

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

1993 г.

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

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

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

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

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

Публикации

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

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

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

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

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

Структура и объем работы

Диссертация состоит из введения, трех глав, заключения и приложений. Работа содержит 142 страниц, включая 12 рисунков и приложения. Список цитированной литературы включает 53 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе «Анализ методов диспетчеризации вычислений» приведен последовательный анализ методов и алгоритмов диспетчеризации вычислений, характерных и разнообразных операционных систем, таких как ДИАМС, VAXELN, UNIX, USIX, QNX и др. Показаны особенности и различия применяемых в них методов диспетчеризации вычислений. Приведен анализ существующих методов диспетчеризации вычислений в коммутационных системах и различных сетях ЭВМ, а также проблемы, которые возникают при работе в существующих сетях. Показано, что эти проблемы связаны с задержками, отказами в обслуживании и даже потерями информации, при предельных нагрузках сетей и/или ограниченном времени ожидания.

Приведенный в главе анализ методов и алгоритмов диспетчеризации вычислений в приоритетных вычислительных системах показал, что несмотря на их многообразие в основе лежат известные традиционные дисциплины «первым пришел - первым обслужен» или «последним пришел — последним обслужен», а также так называемые дисциплины очередей с приоритетами (где в качестве приоритета выступает, например, размер задачи).

С учетом приведенного анализа сформулированы цель и задачи диссертационной работы.

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

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

где Щ (/,) - длительность времени ожидания в очереди ^ОЙ заявки или процесса,

- момент поступления ^Й заявки на обслуживание,

- интервал времени, соответствующий пропускной способности системы,

- интервал времени поступления заявки, т.е. минимально возможное (или средне допустимое, или любое другое) значение интервала поступления заявки, которое определит уровень ее приоритета,

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

(0</,<Т),

- количество потоков заявок.

ь

А Г Ат,

Следует особо подчеркнуть, что впервые сформулированный таким образом критерий оптимальности (1) при оценке вычислительных систем, относится к новому и достаточно перспективному классу экстремальных задач, требующих получения оптимальных решений (т.е. правил диспетчеризации вычислений, минимизирующих критерий) в реальном масштабе времени. В работе приводится формализация и решение задачи минимизации критерия (1). Задача представляет собой новый класс нетривиальных экстремальных задач, которые формализуются следующим образом. Учитывая, что на вход системы поступает (и/или в системе имеется) конечное множество вычислительных процессов и/или заявок на обслуживание, в общем случае систему можно представить в виде традиционной системы массового обслуживания. В этом случае для облегчения формализации задачи можно считать, что заявки могут поступать по различным каналам и с различными временными интервалами (которые, например, могут определять уровни приоритета и/или связаны с временем

поступления или выполнения процессов при мультипрограммной работе вычислительной системы). Причем границы этих интервалов между заявками, так или иначе, определены и/или так или иначе заданы. Однако, в отличие от традиционных и широко используемых для решения подобных вероятностных задач методов теории массового обслуживания (когда после известных допущений необходимо предварительно просуммировать заявки для получения пуассоновского закона распределения и т.д.), решение экстремальной задачи, минимизирующей критерий (1) будет осуществляться путем оптимального управления приоритетами. С помощью управляющих воздействий системы выбор заявок на обслуживание будет подчиняться оптимальным правилам, суть которых заключается в следующем. На начальном этапе, как отмечено, предварительно упрощая задачу, представим систему в общем случае в виде вычислителя с одним потоком последовательно поступающих процессов и/или задач на выполнение (Рис. 1).

гае

\У, - входящий поток заявок,

Ш* - поток заявок на выходе,

Дт, - интервалы поступления задач на выполнение.

Рис 1. Однопотоковая очередь

Если пропускная способность Д/ подобной вычислительной системы выше интенсивности поступления задач на обслуживание (и/или времени их выполнения), Д? Д^тш ожидания не происходит.

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

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

Рис 2. Очередь с несколькими потоками заявок

К каждому моменту времени выбора той или иной задачи (или процесса) на выполнение следует определять минимальное значение разности интервалов Д/ ,

где . интервал, соответствующий значению приоритета процесса.

Минимум разности интервалов (3) определяет приоритет выполнения в каждый конкретный момент времени j-й задачи, обеспечивая тем самым минимум времени ожидания, в соответствии с критерием (1).

тт {дг^ - А/* }< тт { Ж,(дг„)}

(4)

{АгЛ

Суммируя минимальные значения разностей интервалов (4), по всем имеющимся задачам многозадачной и/или др. системы и, на всем интервале приоритетного обслуживания задач (0^ /,< Т), и учитывая динамику изменения порядка приоритетов при обслуживании вычислительных процессов (задач), получим новое оптимальное правило (5). Это правило (5) определит технологию диспетчеризации вычислений, в любой сложной многозадачной, многофункциональной и др. системе, удовлетворяющее критерию (1).

при Слн) = 0 , где яу/= Дг7, + р,ь&1*, Ъ = 0,1,.....п , а это

номер зафиксированного значения обслуживаемого

процесса.

Следуя полученному правилу (5), диспетчеризация вычислений, в любой сложной вычислительной системе обеспечит минимум суммарного времени ожидания при заданной пропускной способности системы, удовлетворяющий критерию (1).

В общем случае полученные результаты показывают, что независимо от приоритета и/или времени обслуживания вычис-

(5)

(6)

лительной системой каждого текущего вычислительного процесса, выбор следующего текущего процесса на обслуживание должен осуществляться по приведенному численному оптимальному правилу (5), обеспечивающему минимум времени ожидания, т.е. минимум критерия (1). Однако при этом в работе обращено особое внимание на размерность полученного соотношения (5). Решается новая экстремальная задача минимизации функции многих переменных на длительном временном интервале и в реальном масштабе времени. Поэтому от выбора поэтапных вычислительных процедур зависит принципиальная возможность ее решения. Очевидно, чем проще процедура вычислений, тем лучше метод, но, даже используя для решения задачи (5) метод динамического программирования Р. Беллмана, который в общем случае отличается радикальным упрощением вычислений, не получим нужного результата (так как при решении (5) требуется получать необходимые результаты в реальном масштабе времени). Для поэтапного решения полученной экстремальной задачи минимизации времени ожидания, путем выбора заявок на обслуживание, удовлетворяющего критерию (1), предлагается модификация вычислительного метода, который специально ориентирован на решения экстремальных задач в реальном масштабе времени. Этот метод можно в общем виде представить как некоторую модификацию вычислительных процедур метода динамического программирования на заданных временных отрезках, соответствующих пропускной способности системы. Таким образом, предложенная в данной работе модификация вычислительных процедур специально ориентирована для решения высокоразмерных задач оптимизации (5) в реальном масштабе времени. Предлагая новые вычислительные процедуры модифицированного метода динамического программирования, в работе сформулирован модифицированный принцип оптимальности, ориентированной на решение предложенной экстремальной задач в реальном масштабе времени. Каково бы ни было каждое данное решение (выбор той или иной задачи и/ини процесса на обслуживание), в каждый данный момент времени /,/ на задан-

ном интервале обслуживания, соответствующем пропускной способности системы, каждое последующее решение (т.е. каждый

последующий выбор задачи) для моментов времени /,+у......... /„ =

Т и интервалов Д^,....... Атт , не зависит от "предыстории" и,

должно быть оптимальным (т.е. обеспечивать минимум времени ожидания), относительно каждого данного решения на заданном интервале времени. Таким образом, следуя предложенной формулировке принципа оптимальности отметим, что каждый последующий выбор задачи на обслуживание осуществляется по приведенным правилам (3, 4) и на заданном интервале Д? , соответствующем пропускной способности данной вычислительной системы. В терминах динамического программирования это означает, что поиск оптимальной стратегии выбора каждого приоритета происходит на заданных временных интервалах, соответствующих реальному времени. Рассмотрим рекуррентные вычислительные процедуры последовательностей выбора управляющих воздействий,. минимизирующих критерий (1). Именно эти последовательности рекуррентных вычислительных процедур определят процесс оптимальной приоритетной диспетчеризации вычислений в реальном масштабе времени, удовлетворяющий. критерию оптимальности (1). Для этого, записав зависимость

где V - управляющее воздействие, р = 0,1,.....г,

сведем задачу к выбору значений управляющих воздействий , определяющих последовательный, порядок распределения вычислительных ресурсов между процессами. К каждому моменту времени выбора задачи на обслуживание, соответствующему пропускной способности системы, рассматриваются так или иначе фиксированные значения приоритетов и соответственно разностей (3). Последовательность значений этих разностей зависит от соотношения исходных значений Д^„ Д/ - интервалов и соответствующим им приоритетам, т.е. определенных фиксированных чисел, разность которых определяет к моменту времени

приоритет выполнения системой той или иной задачи. В начальный момент, учитывая нулевые начальные условия функционирования системы, элементы последовательности (5) имеют вид

откуда для первого момента времени (/=1) следует

Для определения последовательности рекуррентных соотношений, связывающих текущие последовательности значений и Сд', исходим из сформулированного модифицированного принципа оптимальности для решения экстремальных задач в реальном масштабе времени. Если /, - время выбора управляющего воздействия по приведенному правилу (5) на заданном интервале At, предоставляющее приоритет j-й задачи, то независимо от типа каждой конкретной задачи и времени ее выполнения системой, оставшееся время до конца процесса распределения приоритетов по правилу (5) будет использовано для каждого последующего оптимального выбора управляющего воздействия, определяющего приоритет выполнения следующей задачи с помощью последовательности рекуррентных функциональных уравнений.

с К [(?„ - РAt-),и " }= min {(а„ - p,At')+ CN[(a,(M) - ]}

Ы

С,[{а)П-рМ\и- ]= тт {{а)п - /»вА»')+ (:_,[(.,<„_„ - Р{а^Г\иг "']} {«/.}

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

В третьей главе «Моделирование и практическая реализация» представлены результаты практической реализации оптимального метода, алгоритмов, программ и технологий для численной диспетчеризации вычислений в различных вычислительных системах и сетях ЭВМ. Приведенные в работе примеры практической реализации оптимального численного метода при диспетчеризации вычислительных процессов в различных системах позволяют просто и доступно оценить его практические возможности. Для иллюстрации приведем численный пример, показывающий простоту и эффективность оптимального численного метода, при диспетчеризации вычислений в реальном масштабе времени, в реальном узле сети. В качестве исходных данных рассмотрен небольшой узел сети с тремя потоками заявок (и/или сообщений) К1, К2, КЗ, которые заданы своими интервалами поступления, и/ши уровнями приоритета Дг/ = 1.5, Дг? = 2.6 и Дг? = 4.0. Для простоты определим величину интервала, соответствующего пропускной способности узла сети, Д/* = 1. Следуя оптимальному решающему правилу (5), к каждому мо-

менту времени обслуживания // необходимо определить минимальное значение разности, т.е. вычесть из значений 1.5, 2.6, 4.0 по единице. Очевидно, минимум этой разности соответствует интервалу Аг[ и управляющее воздействие С/ определит приоритет выполнения (или прохождения), заявки К1. Суммируя значение Ац и А/* (т.е. 1.5 + 1), осуществляем динамическое смещение начала отсчета заявки К1 в последнее зафиксированное значение. Вычисления продолжаются аналогично для последующих моментов времени 72>—А 'п = Т. Вычислительную процедуру диспетчеризации в соответствии с определяемыми приоритетами выполнения заявок Ю, 1<2, КЗ можно представить следующим образом:

1.5-1 1 2.5-2 2 3.5-3 3.5-4 4 5.5-5 5.5-6 6 7.5 -7

2.6 -1 2.6-2 2.6-3 3 5.6-4 5.6-5 5.6-6 5.6 -7 7

4 -1 4-2 4-3 4-4 4-5 5 9-6 9-7

7.5-8 8 9.5-9 11.5- 1С 10 11.5-11 11.5-12 12 13.5-13

9.6-8 9.6-9 9.6-10 13.6-11 11 13.6-12 13.6-13

9-8 9-9 9 13-10 13-11 13-12 13-13 13

Упрощая вычисления, можно представить вычислительную процедуру в виде

1.5-1 1 1.5-1 2 1.5-1 0.5-1 4 1.5-1 0.5-1 6 1.5-7

2.6-1 1.6-1 0.6-1 3 2.6-1 1.6-1 0.6-1 0.6-7 7

4-1 3-1 2-1 1-1 0-1 5 4-1 3-7

0.5-1 8 1.5-1 0.5-1 10 1.5-1 1.5-1 12 1.5-1

2.6-1 1.6-1 0.6-1 0.6-1 11 2.6-1 1.6-1

2-1 1-1 9 4-1 3-1 2-1 1-1 13

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

Процедура оптимальной численной диспетчеризации вычислений, минимизирующая время ожидания, проиллюстрирован на рис.3. Здесь, для приведенного примера - узла сети с тремя потоками заявок на обслуживание К1, К2, КЗ точками показаны оптимальные моменты выбора задач (из трех потоков заявок).

|*Ат1 = 15 ЯАт2 = 26 ДхЗ = 4 0 |

О 10 20 30 40 50

Рис 3. График обслуживания заявок в зависимости

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

К1 - 1,2,4,6,8, 10,12,14... К2 - 3,7,11,15,...

КЗ - 5,9, 13,..., т.е. заявки с более высоким приоритетом К1 обслуживаются чаще в моменты , заявки К2 - в ,

, а низкоприоритетные заявки КЗ - в и т.д. В работе

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

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

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

Особо отмечено важное преимущество приведенного алгоритма и технологии численной диспетчеризации. Эта технология позволяет достаточно эффективно численно реализовать возможность динамически изменять приоритеты, учитывая как время поступления процессов (и/или сообщений), так и особенности самих процессов. Например, режима их обработки, путем выбора функции параметры сообще-

ния (длина, время обработки и др.).

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

практической реализации численного метода диспетчеризации вычислений в операционных системах проиллюстрирована на примере установки программы численной диспетчеризации в ОС LINUX.

Эффективность различных систем разделения времени, диалоговых и коммутационных систем характеризуется, как правило, временем реакции вычислителя (то есть интервалом времени между поступлением запроса и ответом). Исследования показывают, что наиболее эффективным является постоянное время реакции системы и, как отмечено, отклонения от этого времени нежелательны, как в большую, так и в меньшую сторону. Известно, что основное влияние на время реакции оказывают характеристики распределения потоков заявок или сообщений, и время их обработки. Время обработки зависит в основном от типа сообщения и может быть достаточно точно определено априори. Поэтому уровень приоритета сообщения может, например, выражаться соотношением где - среднее время обработки сообщения типа A=max (AQ. Используя подобный выбор уровня приоритета при диспетчеризации, как показали исследования, можно получить характеристику времени реакции системы, приближающуюся к идеальной, т.е. можно создать операционную систему с практически идеальными возможностями.

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

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

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

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

Приводятся примеры программной реализации численного алгоритма. Результаты исследований отражены в отчете ИНЭУМ для Миннауки «Разработка численных методов и алгоритмов диспетчеризации вычислений с динамически изменяющимися приоритетами», внедрены в эксплуатацию в составе прикладного

программного обеспечения для управления технологическими процессами на Красногорской компрессорной станции в ООО «Уралтрансгаз», используются при создании сети ЭВМ МДМ-банка. При создании участка сети МДМ-банка прикладная программа, реализующей численный алгоритм диспетчеризации вычислений, ориентированна на функциональные задачи конкретных пользователей данной сетевой системы. Использование этой программы позволило сократить время ожидания сообщений на 15-20%, а также исключить потери информации.

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

3. Дубовик А.Е., Дубовик Е.А. Оптимальный метод диспетчеризации вычислений. Сборник докладов 3-ей Международной конференции SUUG (Society for UNIX User Groups - сообщество групп пользователей ОС UNIX), Санкт-Петербург, SUUG,1992r.

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

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

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, 58-62, Moscow, 1998.

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

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

«•-9172

Печатный салон "Моментальная Полиграфия". Комсомольский пр-т, 13.Тел.: 246-00-14 Тираж 100шт. Заказ N8203

ВВЕДЕНИЕ

Глава 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. Полученный в работе оптимальный численный метод диспетчеризации вычислений позволяет достаточно эффективно заниматься моделированием самых сложных вычислительных систем и процессов для получения оценок их основных временных и рабочих характеристик, таких как быстродействие, пропускная способность и др.

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.