Содержание к диссертации
Введение
Глава 1. Анализ методов диспетчеризации вычислений :
1.1. Методы диспетчеризации вычислений в операционных системах 11
1.1.1. Диспетчеризация в операционной системе ДИАМС 13
1.1.2. Диспетчеризация в операционных системах реального времени VAXELN, QNX и USIX 16
1.1.3. Диспетчеризация в операционной системе UNIX 25
1.2. Проблемы диспетчеризации в сетях ЭВМ 37
1.3. Постановка задачи исследования 40
Глава 2. Оптимальный численный метод диспетчеризации вычислений 43
2.1. Методы оптимального управления и экстремальные задачи 44
2.2. Основы оптимального численного метода диспетчеризации вычислений и критерий оптимальности 57
2.3. Решение задачи минимизации критерия 60
Глава 3. Реализация численного метода диспетчеризации вычислений 69
3.1. Примеры применения численного метода 69
3.2. Технология реализации в ОС LINUX 73
3.3. Технология реализации в сетях ЭВМ 76
3.4. Особенности реализации метода в сетях типа ATM 88
3.5. Управление группами приоритетов в многопроцессорных системах 94
3.6. Использование метода для защиты от несанкционированного доступа 102
3.7. Примеры программной реализации 107
Основные результаты работы 117
Приложение 1
- Диспетчеризация в операционных системах реального времени VAXELN, QNX и USIX
- Основы оптимального численного метода диспетчеризации вычислений и критерий оптимальности
- Технология реализации в ОС LINUX
- Управление группами приоритетов в многопроцессорных системах
Введение к работе
Одной из основных задач операционных и сложных вычислительных систем и комплексов является рациональное распределение (планирование) ресурсов вычислителей между пользователями и выполняемыми вычислительными процессами (задачами). При построении управляющих программ (планировщиков, диспетчеров) используется целый ряд различных методов и алгоритмов диспетчеризации вычислений. Управляющие программы при любом из методов диспетчеризации вычислений решают задачу минимизации времени ожидания и сведения к минимуму возможных потерь информации. При этом учитывается и оценивается время ожидания вычислительных процессов (заявок, задач, сообщений), и то обстоятельство, что обработка информации, особенно в диалоговых, больших коммуникационных и других вычислительных системах производится путем многократного выполнения циклов, состоящих из запроса задачи абонента-пользователя и/или реакции, ответа ЭВМ (узла сети, сервера и т.д.). Анализ существующих методов диспетчеризации вычислений в различных операционных системах показал имеющиеся ограничения применяемых методов. Методы и алгоритмы, лежащие в основе управляющих программ для решения разнообразных задач диспетчеризации вычислений реализуют, в основном, традиционные вычислительные дисциплины обслуживания "первым пришел - первым обслужен" или "последним пришел - первым обслужен", а также дисциплины обслуживания; на основе очередей приоритетов. Первые из вышеуказанных методов основываются на учете только на одного параметра - времени поступления заявки на обслуживание вычислительного процесса (сообщения). Второй метод, учитывая особенности каждого конкретного процесса: размер процесса, приоритет процесса, содержащуюся в нем информацию и т.д., как правило, не учитывает время поступления запроса. В результате могут происходить значительные задержки в обслуживании других процессов и сообщений и как следствие отказы в работе систем управления
5 (при предельных нагрузках системы и/или ограниченном времени ожидания).
В ряде случаев при наличии значительного количества вычислительных процессов в системе (или поступающих сообщений), при анализе подобных вычислительных систем, и выборе алгоритмов диспетчеризации вычислительных процессов пытаются использовать методы теории массового обслуживания, учитывая так или иначе известное количество входных потоков задач (сообщений) и их вероятностные характеристики. Однако, практическое решение таких задач диспетчеризации вычислений (да и др. подобных задач) является достаточно сложным и имеет неоднозначный ответ. Кроме того при диспетчеризации вычислений следует учитывать, что в подобных приоритетных вычислительных системах и сетях ЭВМ всегда имеется вероятность того, что низкоприоритетные процессы вовсе не получат вычислительных ресурсов. Поэтому дать полную практическую, адекватную реальности оценку работы подобных существующих вычислительных систем методами теории массового обслуживания можно лишь приближенно, так как эти методы требуют учета столь, многочисленных разнообразных вероятностных факторов, которые практически невозможно выразить количественно и тем более объединить в единый оценочный критерий. В этой связи задача разработки эффективных методов и алгоритмов диспетчеризации вычислений, особенно как для разнообразных задач разделения времени, так и реального времени, связанных со сбором, обработкой и передачей информации с многочисленных источников, а; также задач коммуникации и маршрутизации сообщений в локальных и глобальных сетях ЭВМ, является чрезвычайно актуальной и важной.
Диссертационная работа посвящена разработке оптимального численного метода, алгоритмов и технологий диспетчеризации вычислений с динамически изменяющимися приоритетами в реальном масштабе времени для различных сложных вычислительных систем и комплексов. За критерий оптимальности вычислительной системы принимается минимальное время ожидания вычислительных процессов на обслуживание.
В диссертационной работе решены следующие основные задачи:
дан сравнительный анализ существующих методов и алгоритмов диспетчеризации вычислений в различных вычислительных системах;
разработан оптимальный численный метод и технологии диспетчеризации вычислений с динамически изменяющимися приоритетами в реальном времени;
разработан критерий оптимальности и приведена строгая математическая формализация решения задачи, оптимизации численного метода диспетчеризации вычислений с динамически изменяющимися приоритетами;
исследованы возможности практической реализации разработанного численного метода и технологий диспетчеризации вычислений в различных вычислительных системах;
проведены исследования возможностей разработанного численного метода диспетчеризации вычислений при моделировании временных характеристик вычислительных процессов и систем для оценки их рабочих характеристик, таких как быстродействие и пропускная способность;
показаны возможности численного метода диспетчеризации для защиты информации от несанкционированного доступа,
В теоретических и экспериментальных исследованиях использованы теория оптимального управления и решения экстремальных задач , методы динамического программирования и вычислительной математики.
В диссертации получены следующие результаты, характеризующиеся научной новизной:
разработан новый, аналитически формализованный и обоснованный численный метод диспетчеризации вычислений в реальном масштабе времени;
доказана эффективность использования предложенного метода для численной диспетчеризации вычислительных процессов в реальном масштабе времени;
~ показана возможность использования предложенного численного метода для диспетчеризации вычислении в операционных системах, системах коммуникации сообщений и сетях ЭВМ;
- обоснована возможность использования численного метода для созда
ния динамически изменяющихся в реальном времени ключей защиты
от несанкционированного доступа.
Результаты диссертационной работы получены в Институте электронных управляющих машин в рамках Федеральной целевой программы «Реструктуризация и конверсия обороной промышленности» (1996-2000гг.) и отражены в научно-техническом отчете «Разработка численных методов и алгоритмов диспетчеризации вычислений с динамически изменяющимися приоритетами», подготовленным для Министерства науки и технической политики в соответствии с его Распоряжениями N 636 Ф от 17.03.1997 и 329 Ф от 6.04.1998.
Результаты работы используются в учебном процессе Московского государственного института радиотехники, электроники и автоматики (МИРЭА). Разработан методический материал для практических занятий по методам диспетчеризации вычислений для студентов кафедры «Управляющие ЭВМ». Результаты работы используются также при создании сети ЭВМ МДМ-банка и внедрены в эксплуатацию в составе прикладного программного обеспечения для управления технологическими процессами на Красногорской компрессорной станции в ООО «Уралтрансгаз» [52].
8 Материалы диссертационной работы докладывались и обсуждались:
на 3-ей Международной конференции SUUG'92, Санкт-Петербург, 1992 г.;
на Международной конференции «Free Soft 93», Москва, 1993 г.
на Международной конференции «Открытые системы - решения для нового мира», Москва, 1994 г.;
на Международной конференции EAST-WEST «Информационные технологии в проектировании - Information technology in design», Москва, 1996 г.;
на IV Международной конференции «Развитие и применение открытых систем», Нижний Новгород, 1997 г.;
на I Международной конференции «Цифровая обработка сигналов и ее применение - DSPA-98», Москва, 1998 г.;
на II Международной конференции «Идентификация систем и задачи управления», SICPRO'03, Москва, ИЛУ, 2003 г.
Основные результаты работы отражены в 12 научных публикациях.
І.Дубовик А.Е. Численный метод диспетчеризации вычислений для систем промышленной автоматизации. Автоматизация в промышленности. №12. 2003.
Дубовик А.Е, Численный алгоритм диспетчеризации вычислений с динамически изменяющимися приоритетами. Тезисы доклада 4ой научно-практической конференции "Современные информационные технологии в управлении и образовании", Москва, НИИ «Восход». 2003.
Дубовик А.Е., Дубовик Е.А. Оптимальный метод диспетчеризации вычислений. Сборник докладов 3-ей Международной конференции SUUG
9 (Society for UNIX User Groups - сообщество групп пользователей ОС UNIX),
Санкт-Петербург, SUUG, 1992г.
Дубовик А.Е., Дубовик Е.А. Управляющие программы с динамически изменяющимися приоритетами. В сборнике докладов международной конференции "FrecSoft93", Москва, SUUG,1993.
Дубовик А.Е., Дубовик Е.А, Численный метод диспетчеризации вычислений с динамически изменяющимися приоритетами. Тезисы докладов Международной конференции "Открытые системы - решение для нового мира", Москва, SUUG, 1994.
Dubovik A.,Ye.,Dubovik Ye.A. The optimal numeric metod of calculation dispatching with dynamic priorities. Сборник докладов международной конференции EAST-WEST, EWITD'96., Москва, 1996.
Дубовик A.E., Дубовик Е.А. PC Based CAD Workstation. В сборнике докладов Международной конференции EAST-WEST "Информационные технологии в проектировании" - Information technology in design, EW1D'96, стр. 147-152, Москва, 1996,
Дубовик А.Е., Дубовик Е.А. Численный метод коммутации и маршрутизации сообщений, в сборнике докладов IV международной конференции "Развитие и применение открытых систем", Нижний Новгород, 1997, стр. 90-95.
Дубовик А.Е., Дубовик Е.А. Основы и методы многоканального измерения функций различного спектрального состава. В сборнике докладов 1-ой; Международной конференции "Цифровая обработка сигналов и ее применение" DSPA'98, т.4, стр. 102-112, Москва, 1998.
10. Dubovik A.,Ye.,Dubovik Ye.A. Multichannel measurement basics and
method for functions with different spectral composition. The ist International
10 Conference "Digital signal processing and its applications', DSPA'98, vol IV-E, 58-62, Moscow, 1998.
Прохоров H.Л., Дубовик A.E. «Системное программное обеспечение ЭВМ. Методы диспетчеризации вычислений». Методические указания по выполнению практических занятий для студентов специальности 220100. МИРЭА, 1999.
Дубовик Е.А., Дубовик А.Е. Оптимальные методы и технологии многоканального измерения функций различного спектрального состава. Сб. докладов II Международной конференции «Идентификация систем и задачи управления», SICPRO'03, Москва, ИЛУ РАН, раздел 6-8, 2003.
В опубликованных работах лично соискателю принадлежат следующие результаты:
разработка метода, численных алгоритмов, программ и технологий реализации диспетчеризации вычислений с динамически изменяющимися приоритетами;
разработка различных модификации численного алгоритма диспетчеризации вычислений для эффективного использования в сетевой архитектуре, узлах сети ЭВМ и для эффективной загрузки линий связи;
разработка метода динамической защиты информации и передачи данных от несанкционированного доступа;
исследования возможностей численного метода диспетчеризации для моделирования и оценки временных характеристик вычислительных
систем.
Диспетчеризация в операционных системах реального времени VAXELN, QNX и USIX
ОС РВ являются многозадачными, многопользовательскими системами. ОС РВ; должны реагировать на несколько одновременно происходящих событий, причем за время, критическое для этих событий вне зависимости от влияния других выполняемых задач или процессов. В связи с этим можно выделить две главные архитектурные особенности ОС РВ - структура ядра и механизмы реального времени: особые механизмы планирования задач, средств межзадачного взаимодействия, переключения задач и др.
Планирование задач (процессов) связано с системой приоритетов и алгоритмами диспетчеризации. В многозадачных ОС общего назначения планировщик в большинстве случаев использует модификации алгоритма круговой диспетчеризации. В соответствии с ним процессы находятся в циклической очереди на выполнение. Ресурс процессора предоставляется процессу на определенный квант (time Slice). По истечении кванта времени процесс выгружается и, если он все еще не обслужен, помещается в конец очереди. Ресурс процессора передается следующему процессу, первому в очереди. Очередь может регулироваться приоритетами. Может быть выделено несколько уровней приоритетов, и на каждом уровне выполняется циклическое продвижение задач к началу очереди.
Недостаток такого алгоритма с точки зрения систем реального времени в том, что только один процесс может владеть ресурсом процессора в течение определенного кванта времени. Планировщики ОС РВ1 используют алгоритмы диспетчеризации, позволяющие при необходимости переключить процесс до окончания предоставленного кванта времени. Текущий процесс приостанавливается сразу при наступлении события, если в очереди появляется более приоритетный процесс. Приоритеты процессов могут задаваться различными способами, например, динамически изменяться в зависимости от активности процесса. Планировщик запускается всегда, если какой-либо процесс изменил свое состояние после получения сообщения в результате аппаратного прерывания.
К механизмам межзадачного взаимодействия относятся семафоры, разделяемая память, сообщения и др., позволяющие синхронизировать процессы и обеспечивать быстрый обмен информацией между ними. Важной архитектурной особенностью является возможность переключения процессов во время выполнения не только пользовательской, но и системной фазы ядра, что обеспечивает возможность обработки критических к времени прерываний.
ОС РВ могут содержать ряд специальных механизмов работы с памятью, например, возможность блокировки страниц оперативной памяти, позволяющей фиксировать в ней высокоприоритетные процессы, критические к времени реакции, что ускоряет переключение контекста и запуск этих процессов; средства оптимизации обмена данными с диском, например, кэширование дисков, позволяющее повысить быстродействие за счет хранения в оперативной памяти часто используемых дисковых блоков и другие механизмы, позволяющие обрабатывать любой процесс в пределах требуемого времени.
Рассмотрим принципы диспетчеризации в ОС РВ на типичном примере операционной системы реального времени VAXELN.
Система VAXELN представляет собой достаточно оригинальный и узко-профильный системный программный продукт с характерной диспетчеризацией, предназначенной для разработки вычислительных систем реального времени для процессоров класса VAX, фирмы DEC [2], В VAXELN широко используется понятие вычислительный процесс (или просто процесс), под которым понимается задание (задача) или группа связанных зада ний, при этом каждый процесс в системе находится всегда в одном из следующих четырех состояний: выполнения, готовности к выполнению, ожидания и приостановки: выполнение; процесс в этом состоянии имеет управление центральным процессором, т.е. процесс к задаче выполняется процессором; готовность к выполнению; процесс в этом состоянии не выполняется, но он готов к запуску так скоро, как это возможно. Это состояние является начальным для каждого процесса немедленно после его создания;
ожидание; процесс находится в этом состоянии, если он ожидает выполнения определенного набора заданных условий. Это может быть ожидание прохождения конкретного промежутка времени, возникновения конкретного события, получения сообщения, и т.д. Процесс может перевести себя (и только себя) в это состояние путем вызова специальных процедур (WAIT_ALL,WAIT_ANY); приостановка; процесс в этом состоянии не является подходящим для выполнения, то есть, он не может перейти в состояние готовности, пока не будет возобновлен явным образом. Процесс может быть переведен сам (или любой другой процесс) в это состояние с помощью процедуры SUSPEND и выведен с помощью процедуры RESUME.
Переход от одного состояния к другому, или изменение состояний, описывает поведение системы в соответствии со следующими правилами: начальное состояние каждого процесса- готовность; когда ожидаемые условия удовлетворяются для ждущего процесса - он переходит в состояние готовности; когда для приостановленного процесса выдается команда
ESUME, то этот процесс переводится в предыдущее состояние перед приостановкой. Процесс переходит в состояние готовности, если он был перед приостановкой готов к выполнению. Если процесс был в состоянии:ожидания, то он вернется в это состояние и будет оставаться там до тех пор, пока не будут выполнены указанные условия (возможно, что ожидаемые условия будут удовлетворены во время пребывания процесса в состоянии приостановки). В этом случае, возобновленный процесс затем изменит свое состояние с ожидания на готовность.
Диспетчеризация вычислений в этом случае происходит следующим образом: из множества процессов, находящихся в состоянии готовности, диспетчер (ядро VAXELN) выбирает процесс с наивысшим приоритетом и изменяет его состояние на состояние выполнения, передавая ему управление центральным процессором. Выполняемый перед этим; процесс переходит в состояние готовности. Приоритеты процессов изменяются по очередности и специально программируются, исходя из условий реального времени.
Планирование заданий и процессов в системе VAXELN производит пользователь системы следующим образом в соответствии с режимом реального времени. В VAXELN пользователь назначает приоритеты процессам, где более высокий приоритет означает, что процессу следует дать преимущество
Основы оптимального численного метода диспетчеризации вычислений и критерий оптимальности
Как отмечено ранее, разработка и практическая реализация существующих логических методов и алгоритмов диспетчеризации вычислений для создания различных управляющих программ (от самых простых до сложнейших), требует решения задачи минимизации возможных потерь информации и, самое главное, времени ожидания. При этом учитывается и/или оценивается, как правило, время ожидания вычислительных процессов (заявок на обслуживание) и то обстоятельство, что обработка информации, особенно в диалоговых и др. коммутационных системах, производится путем, многократного выполнения циклов, состоящих из любого даже удаленного запроса (например, пользователя) и- ответа ЭВМ. Эффективность подобных систем характеризуется временем ответа (включая и коммутацию при удаленном запросе), причем, отклонения от этого времени (как в большую, так и в меньшую стороны) нежелательны. Как показано в предыдущих разделах, существующие логические методы и алгоритмы, лежащие в основе различных управляющих программ для решения задач диспетчеризации вычислений (несмотря на их разнообразие и многочисленность) реализуют, в основном, традиционные дисциплины типа "первым пришел - первым обслужен" или "последним пришел - первым обслужен", а также так называемые дисциплины очереди с приоритетами. Первые методы диспетчеризации используют и основываются только на одном параметре времени поступления заявки, игнорируя все остальные его характеристики. Вторые методы, учитывая и анализируя особенности заявок (например, размер процесса, содержащуюся в нем информацию и т.д.), как правило, не учитывают время их поступления, в результате чего могут происходить значительные задержки в обслуживании заявок или даже отказы в обслуживании (при предельных нагрузках системы и/или ограниченном времени ожидания). Проанализировать и практически оценить эффективность работы подобных (и особенно сложных) систем, связанных с диспетчеризацией вычислений, практически невозможно. Даже при использовании методов теории массового обслуживания, удается получить лишь весьма приближенные результаты, так как требуется учесть столь многочисленные и разнообразные вероятностные факторы, которые практически невозможно выразить количественно и, тем более, объединить в единый критерий оценки.
Поэтому в данном разделе работы, в отличие от существующих вероятностных и др. приведенных ранее логических методов, алгоритмов и реально существующих управляющих программ диспетчеризации вычислений, в различных открытых вычислительных системах (особенно для диспетчеризации задач в сложных вычислительных системах, системах сбора и передачи информации, а также системах коммутации и маршрутизации сообщений) для эффективной организации вычислений, предлагается разработанный универсальный оптимальный численный метод диспетчеризации вычислений с динамически изменяющимися приоритетами. Предлагаемый численный метод диспетчеризации вычислений может быть достаточно просто и эффективно использован при создании управляющих программ в самых различных вычислительных и коммутационных системах, в системах сбора и передачи информации, в телекоммуникационных системах, а также в сетях ЭВМ [17,18,19,20,21,22,23].
Переходя к единой мере оценки различных вычислительных систем следует прежде всего отметить, что в любой проблеме оптимизации центральный вопрос связан с выбором критерия оптимальности или общего и достаточно универсального критерия оценки любой вычислительной системы, и учесть при этом, что никакие удобства математического или иного характера не могут компенсировать недостатки при выборе неадекватного системе и/или задаче критерия. Поэтому в качестве достаточно универсального критерия оптимальности диспетчеризации вычисления для широкого класса вычислительных систем предложен критерий, минимизирующий суммарную длительность времени ожидания вычислительных процессов (заявок) на обслуживание, при минимизации времени ожидания каждой заявки или ограничении типа Щ(ї\) Wv, где IVP -допустимое время ожидания заявки в очереди. Пропускная способность системы может определяться либо быстродействием вычислителя, либо количеством обслуженных процессов в единицу времени и/или временем выполнения тех или иных процедур при заданном быстродействии вычислителя и т.д.
Выражение для предлагаемого критерия оптимальности при оценке вычислительных систем запишется в виде
Следует особо подчеркнуть, что впервые сформулированная таким образом задача минимизации критерия оптимальности при оценке вычислительных систем (2.33) относится к новому и достаточно перспективному (учитывая развитие вычислительной техники) классу экстремальных задач, требующих получения оптимальных решений (т.е. правил диспетчеризации) в реальном масштабе времени [11,12,13].
Решение подобных экстремальных задач, связанных с минимизацией критерия (2.33) определяет и представляет собой новый класс нетривиальных экстремальных задач, которые формализуются следующим образом. Учитывая, что на вход системы поступает (и/или в системе имеется) конечное множество вычислительных процессов и/или заявок на обслуживание, в общем случае систему можно представить в виде традиционной системы массового обслуживания. В этом случае для облегчения формализации задачи можно считать, что заявки могут поступать по различным каналам и с различными временными интервалами (которые, например, могут определять уровни приоритета и/или связаны с временем поступления или выполнения процессов при мультипрограммной работе вычислительной системы). Причем границы этих интервалов между заявками так или иначе определены и/или так или иначе заданы. Однако, в отличие, от традиционных и широко используемых для решения подобных вероятностных задач методов теории массового обслуживания (когда после известных допущений необходимо предварительно просуммировать заявки для получения пуассоновского закона распределения и т.д.), решение экстремальной задачи, минимизирующей критерий (2.33) будет осуществляться путем оптимального управления
Технология реализации в ОС LINUX
В первой главе приведены достаточно подробно существующие принципы диспетчеризации и организации приоритетов в операционных системах.
Учитывая, что система LINUX весьма распространена, и доступна различным пользователям и разработчикам, рассмотрим возможности реализации методов и технологий численного метода диспетчеризации вычислений в операционной системе LINUX. Самая большая сложность подобной реализации достаточно простых программ численного метода диспетчеризации заключается в том, что диспетчер LINUX (или обработчик процессов), как и в UNIX, является частью ядра системы и не всегда доступен для управления процедурой распределения вычислительных ресурсов между процессами. Диспетчер поддерживает понятие классов распределения, где каждый класс задает порядок распределения для процессов внутри него и каждый класс связан с набором очередей приоритетов, в которых находятся: процессы, готовые к выполнению. Эти очереди преобразуются системной конфигурацией в набор глобальных приоритетов, которые доступны процессам внутри класса (диспетчер всегда выбирает для выполнения процесс с наивысшим глобальным приоритетом в системе). Очереди приоритетов, ассоциированные с данным классом, видны только этому классу как последова-тельн ы й набор уровней приоритетов, начи наю щийся от 0 (младшего) до п (старшего - значение п зависит от конфигурации системы), а набор глобальных приоритетов может не начинаться, с 0 и не быть соприкасающимся-(с шагом 1), что тоже зависит от конфигурации системы. Самой простой возможностью реализации численного метода представляется следующая. Процессы в классе разделения времени, выполняемые в пользовательском режи ме, распределяются в соответствии с параметрами, указанными в таблице ts_dptbl, за исключением процессов, идущих в режиме ядра после выхода из состояния ожидания. В LINUX, как в других UNIX системах, в последнем случае процессы обрабатываются с учетом специального набора приоритетов, зарезервированных для таких процессов и не затрагиваемых параметрами ts_dptbl до возвращения в пользовательский режим. Использование вместо таблиц ts__dptbl, состоящих из массива структур параметров (struct ts_dpent), программы численного метода диспетчеризации для организации уровней приоритетов процессов в пользовательском режиме, позволит повысить эффективность использования ресурсов. В этом случае каждый уровень приоритета будет задан этой программой численной диспетчеризации. Далее целесообразно вписаться в структуру параметров, состоящих из элементов, описанных в библиотеке \usr\include\sys\ts.h: - ts_j»Iobpri - глобальный приоритет диспетчеризации, соответствующий уровню приоритета. Соответствие между уровнями приоритета разделения времени и глобальным уровнем приоритета также задается во время загрузки.
Вместо ts_quantum - длинны кванта времени, предоставляемого процессам на этом уровне в тиках (HZ) вставляется уровень приоритета, определенный числовым методом, ts_tqexp - уровень приоритета новой очереди, который определяется следующим шагом, выполняемым на текущем уровне. Кванты времени выполнения; определяются, либо по завершению каждого текущего процесса, либо на начальном уровне при оценке времени выполнения задач. При этом изменится и ts_slpret - уровень приоритета новой очереди, в которую помещается процесс, бывший предварительно в пользовательском режиме на этом уровне, после возвращения в пользовательский режим из состояния ожидания. ts__maxwait - счетчик процесса ts_disp\vait сбрасывается в 0 каждый раз, когда процесс возвращается в очередь диспетчера, если процесс выйдет из состояния ожидания и ts_dispwait не сбрасыва ется в 0, если процесс замещен другим процессом с большим приоритетом. Кроме того, если значение ts_dispwait процесса превысит значение tsjnaxwait для этого уровня, приоритет процесса изменяется на значение, указанное ts_lwait, что предотвращает зависание процесса.
В этом случае администратор системы может влиять на поведение той части диспетчера, которая ведает процедурой разделения времени. Все компоненты структуры ts_dptbl, за исключением ts_globpri, могут быть также проверены и модифицированы с использованием программы численного метода. Активизация процедуры численного метода для класса разделения времени позволяет администратору следить за текущей конфигурацией ts_dptbl из внутренней таблицы ядра, или переписать внутреннюю таблицу ядра с помощью значений файла конфигурации. При этом, линии приоритетов используются для задания значений параметров уровней приоритетов разделения времени. Первая линия задает параметры для уровня приоритета О, вторая для первого уровня и т.д. Каждому уровню приоритета также будет соответствовать ровно одна линия. Эти уровни приоритета LINUX могут быть проиллюстрированы с помощью наглядного распределения уровней приоритета на примере, приведенном в разделе 3.1.
В случае реализации численного метода диспетчеризации вычислений минимальная длина кванта времени в тиках может быть также равна одному тику, т.е. ts_quantum, равный одному тику, может соответствовать наивысшему приоритету. Все остальные приоритеты могут быть назначены по правилам, приведенным в разделе 3.1 и определяться путем текущих вычислений по правилу (2.37). Вместо выделенного LINUX кванта времени выполнения процесса, можно ждать завершения текущего процесса.
Развитие в конце XX века информационной и коммуникационной отрасли сопровождается весьма серьезными и главное все возрастающими проблемами (по мере роста числа пользователей), возникающими при диспетчеризации вычислений и организации доступа пользователей к серверам, провайдерам, браузерам и др. вычислительным ресурсам локальных и глобальных сетей ЭВМ ( в том числе Internet и др.). Этипроблемы не решаются только установкой протокола TCP/IP и пары новых серверов. Проблема в доступе к глобальной сети и узлам сети. Например, канал связи на входе, далее пользователь и узел сети, включающего компьютер, сервер, затем опять сеть. Далее вычислительные ресурсы другого узла (снова ЭВМ, серверы и др.). На выходе, вычислительные ресурсы узла сети, выход в сеть и снова пользователь другого узла. Размеры такой паутины сетевых узлов (Web), как Internet с ее 70 миллионами пользователей и ее состояние на сегодняшний день (когда пользователи одного узла сети подолгу не могут пробиться к вычислительным ресурсам другого узла), порождают серьезную задачу уменьшения времени и упорядочения доступав сеть за счет, как диспетчеризации
Управление группами приоритетов в многопроцессорных системах
Это новое сложнейшее и перспективное направление возможности использования предложенных численных методов диспетчеризации вычислений с динамически изменяющимися приоритетами.
Как отмечено, существующие логические методы и алгоритмы, лежащие в основе различных управляющих программ для решения задач диспетчеризации вычислений (несмотря на их разнообразие и многочисленность) реализуют, в основном, традиционные дисциплины типа "первым пришел -первым обслужен" или "последним пришел - первым обслужен", а также так называемые дисциплины очереди с приоритетами. Первые методы диспетчеризации используют и основываются только на одном параметре времени поступления заявки, игнорируя все остальные его характеристики. Вторые методы, учитывая и анализируя особенности заявок (например, размер процесса, содержащуюся в нем информацию и т.д.), как правило, не учитывают время их поступления, в результате чего могут происходить значительные задержки в обслуживании заявок или даже отказы в обслуживании (при предельных нагрузках системы и/или ограниченном времени ожидания). Аналогичные и/или похожие задачи возникают и при распределении заданий в больших многопроцессорных вычислительных системах. В данном разделе работы, в отличие от существующих вероятностных и логических методов диспетчеризации вычислений, предлагается использовать оптимальный численный метод диспетчеризации вычислений с динамически изменяющимися приоритетами, в различных открытых многопроцессорных вычислительных системах, особенно для диспетчеризации вычислений в больших вычислительных, а также больших системах, связанных с коммутацией, маршрутизацией заданий между процессорами. Именно универсальный численный метод в любой конкретной модификации можно достаточно просто использовать при создании эффективных управляющих программ распределения вычислительных ресурсов и заданий между процессорами или группами процессоров, а также больших массивов данных в больших многопроцессорных системах и комплексах.
Оптимальное численное распределение вычислительных ресурсов с динамически изменяющимися приоритетами рассмотрим на примерах многопроцессорных масштабируемых вычислительных систем SMP и МРР архитектур [53].
В качестве примера рассмотрим архитектуру Reliant RM1000 Архитектура Reliant RM1000 основана на множестве отдельных процессоров, соединенных высокоскоростной сетью. Такую архитектуру называют слабо связанной, так как отдельные процессоры относительно независимы друг от друга. Это архитектура параллельных вычислений с массовой масштабируемостью (т.е. по аналогии с МРР - вычисления с массовым параллелизмом). Все процессоры RM1000 имеют собственную оперативную и дисковую память и называются процессорными узлами. Высокоскоростная сеть, соединяющая узлы, организована в виде регулярной решетки, в которой1 каждый узел подсоединен к сети через маршрутизатор. Маршрутизаторы (MRC — плата сетевого маршрутизатора) обеспечивают обмен данными между процессорными узлами. Каждый маршрутизатор может одновременно передавать пакеты данных в четырех направлениях и управлять группами приоритетов при реализации численного метода диспетчеризации и коммутации сообщений с динамически измененным приоритетом. Каждый узел сети состоит из одного микропроцессора, оперативной памяти, сетевого интерфейса и двух SCSI-2 контроллеров. Системные диски подсоединены к двум узлам: каждая SCSI шина соединена с контроллерами ввода/вывода двух микропроцессоров (двойное подключение позволяет применять автоматическое переключение при сбое в узле, что гарантирует постоянный доступ к диску).
Пусть компьютер Reliant RM1000 представлен в виде следующей конфигурации. Конструктивно процессорные узлы объединяются в ячейки, которых может быть до 32. В каждую входит 6 микропроцессоров, 24 диска (по 2 или 4 Гбайта), 128-512 Мбайт оперативной памяти на узел, 16 Кбайт первичный и 1 —4 Мбайта вторичный кэш. В качестве процессоров используются модели из семейства MIPS Rxxxxx. В этом случае межузловые связи с помощью управления маршрутизатором можно организовать используя оптимальный численный метод, динамически регулируя приоритеты по конкретным правилам «первым пришел - первым обслужен» и дисциплины очереди с приоритетами. Динамическое численное регулирование приоритетов в этом случае возможно с учетом как времени поступления процессов на каждый узел масштабируемой многопроцессорной системы, так и особенностей самих процессов, режима их обработки в каждом узле и т.п. путем выбора функции
Учитывая, что Reliant RM1000 относится к классу систем с массовым параллелизмом (МРР), рассмотрим основные характеристики МРР архитектур, используя базы данных в качестве примера типичной коммерческой области их применения. Типичные базы данных, как правило, реализуются таким образом, чтобы обработка поступившего от приложения задания реапи-зовывалась путем запуска группы процессов, синхронизируемых через разделяемую оперативную память. Кроме того, для того, чтобы ускорить доступ к информации, части базы данных хранятся в разделяемой глобальной области (SGA - Shared;Global Area), которая также доступна для всех процессов СУБД. И в однопроцессорных, и в многопроцессорных системах время реакции зависит от двух главных факторов: производительности процессов и процедур ввода/вывода. Кроме того, даже большая буферная область также уменьшает время реакции, если только доступ к данным не осуществляется хаотически. В многопроцессорных архитектурах семметричного мультипро-цессирования SMP (по сравнению с однопроцессорными) увеличивается суммарная процессорная мощность, в тоже время в характеристиках системы ввода/вывода такого пропорционального роста нет. Поэтому верхний предел производительности SMP диктуется характеристиками системы ввода/вывода и организацией вычислительного процесса. Природа приложений, ориентированных на оперативную обработку транзакций делает необходимым выполнение максимально большого числа запросов, но производительность шины в SMP системах налагает ограничение на масштабируемость. В тоже время из соображений вычислительной производительности требуются кластерные процессорные архитектуры с разделяемыми дисками. Как показывает практика, в SMP системах обслуживающих коммерческие БД, не включают больше 30 процессоров. Поэтому считается возможным решением при использовании SMP систем в этих приложениях создание очень больших буферных областей. Однако эту же проблему можно эффективно решать управлением вычислительными процедурами, с помощью численного метода.
Архитектура систем с массовым параллелизмом, как и архитектура SMP, позволяет эффективно наращивать производительность за счет увеличения числа процессоров. Однако в этой архитектуре одновременно необходимо адекватное увеличение производительности системы ввода/вывода, так как каждый узел имеет собственные средства ввода/вывода, не зависящие от всех других узлов (рис. 3.4).
Учитывая также, что независимость узлов создает проблему отсутствия разделяемой общей памяти, через которую происходит синхронизация различных процессоров в SMP архитектурах, необходима быстрая сеть, связывающая индивидуальные процессоры. В этом случае возникает широкое поле
