Содержание к диссертации
Введение
ГЛАВА I. СТРУКТУРА И ОСОБЕННОСТИ ФУНКЦИОНИРОВАНИЯ БАЗОВЫХ СРЕДСТВ ОПЕРАЦИОННОЙ СИСТЕМЫ II
1.1. Принципы построения и общая структура ОС II
1.2. Диспетчеры элементарных машин и язык системы 22
1.3. Процессы и языки для взаимодействия процессов 34
1.4. Старшие диспетчеры... 46
1.5. Резюме 56
ГЛАВА 2. МОДЕЛЬ ВЗАИМОДЕЙСТВИЙ БЛОКОВ ОПЕРАЦИОННОЙ СИСТЕМЫ 58
2.1. Постановка задачи 58
2.2. Первый способ обслуживания заявок... 64
2.3. Второй способ обслуживания заявок... 83
2.4. Численный анализ задержек процессов 91 в системе МИНИМАКС...
2.5. Резюме 95
ГЛАВА 3. МЕТОДЫ ПРОГРАММНОЙ ОРГАНИЗАЦИИ ОТКАЗОУСТОЙЧИВЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ 97
3.1. Схемы применения точек контроля и возврата. 99
3.2. Предварительная подготовка параллельных программ и функции блоков ОС, обеспечивающих отказоустойчивость вычислений ЮЗ
3.3. Определение оптимальных временных шагов, необходимых для контроля вычислений 122
3.4. Организация отказоустойчивости в системе МИНИМАКС 134
3.5. Резюме 143
ГЛАВА 4. ПОСТРОЕНИЕ СИСТЕМЫ СБОРА, ХРАНЕНИЯ И ПЕРЕРАБОТКИ ДАННЫХ НА ОСНОВЕ ОС МИНИМАКС... 145
4.1. Общее описание и структура системы "РАЙОН" 145
4.2. Применение ОС МИНИМАКС 149
4.3. База данных районного уровня 152
4.4. Язык управления базой данных 162
4.5. Резюме 168
ЗАКЛЮЧЕНИЕ 169
ЛИТЕРАТУРА 171
ПРИЛОЖЕНИЕ 181
- Принципы построения и общая структура ОС
- Постановка задачи
- Схемы применения точек контроля и возврата.
- Общее описание и структура системы "РАЙОН"
Введение к работе
Важнейшими аспектами развития средств вычислительной техники в настоящее время являются повышение ее быстродействия и надежности, улучшение экономических и эксплуатационных характеристик, упрощения связи с пользователями и т.п. Одним из базовых направлений этого развития считается построение модульных многопроцессорных систем, различные классы которых отличаются друг от друга типами и количеством модулей. Успехи интегральной технологии позволяют говорить об установках, в которых каждый модуль имеет свой процессор и свою память. Примерами таких модулей могут служит однокристальные ЭВМ, сходные по своим возможностям с современными малыми ЭВМ. Массовый выпуск мини- и микро-ЭВМ облегчает задачу построения различных макетов вычислительных систем (ВС) на базе модулей такого типа и отработку на них новых архитектурных решений. Вместе с этим, мульти-мини- машинные системы имеют и самостоятельный интерес, позволяют строить проблемно-ориентированные комплексы, обладающие при меньшей стоимости (по сравнению с универсальными ЭВМ) лучшей реакцией на запрос при работе в реальном времени, большей надежностью при круглосуточном цикле функционирования, меньшими сроками окупаемости капитальных затрат и т.п.
Областями применения таких комплексов являются: решение задач управления, в том числе в режиме реального времени (например, управление технологическими процессами, крупными транспортными узлами, воздушным движением); задачи при решении которых требуется обеспечение высокой надежности, живучести и достоверности процесса обработки данных (например, управление ядерными реакторами, воздушным движением). Помимо перечисленных задач, на таких системах могут решаться с той или иной степенью эффективности и чисто вычислительные задачи, представленные параллельными алгоритмами. Это особенно удобно в тех случаях, когда задачи такого класса в некоторой интегральной системе управления не составляют основной доли всех вычислений.
Для эффективного использования возможностей мульти-мини-машинных систем необходимо построение и исследование операционных систем (ОС), основанных на различных методологиче* ских подходах. Проблемам организации параллельных вычислений посвящены работы А.Б.Барского [4], Б.А.Бабаяна [8J, А.П.Ершова [2], Г.Г.Иванникова [9], Ю.В.Капитоновой [ю] , А.Н.Королева [7], Ю.Г.Косарева [і,14], В.Е.Котова [з]; А.А.Летичевского [Ю], С.Д.Пашкеева [б], Д.А.Поспелова б], Э.А.Трахтенгерца [12], Е.А.Ющенко [із], Э.Дейкстры ( E.J)11- Kstra) [іб], К.Рамомурти (CRamomoortHa) [19], А.Хабер-мана (AHabermah) [їв], в.хансена (B.Hahsen ) [15,25],
К.Хооре (С.НоаГе) [17] и др.
Вместе с тем, опыт проектирования операционных систем в первую очередь касается многопроцессорных ЭВМ с общей памятью и сетей ЭВМ. Опыт же построения ОС для систем рассматриваемого класса, предлагающих параллельную обработку данных при решении одной задачи, является еще недостаточным.
В настоящее время создаются и уже созданы вычислительные средства на базе малых ЭВМ, объединенных в систему с целью достижения необходимых технических и эксплуатационных характеристик. При этом используются различные способы объединения ЭВМ: вычислительные системы со связями между машинами через дуплексные регистры и каналы межпроцессорной связи (ВС на основе мини-ЭВМ М-6000/М-7000 АСВТ-М и CM-I и СМ-2 [20,2l]); ВС с общими внешними ресурсами (ВС на базе АСВТ-М с разветвителем сопряжения 2К, ВС на базе СМ ЭВМ с модулем ПШ СМ); ВС с машинами посредниками, где осуществлено разделение функций (система Spider [22], система РАДИУС [27]); ВС с общей шиной (модуль АМС СМ [2б] позволяет объединить СМ ЭВМ таким способом); ВС с общими памятью и шиной (система LUflUfip [24]); ВС с многовходовой оперативной памятью (система Prime [23]).
Во многих этих системах используются неоднотипные МИНИ-ЭВМ, при выборе средств коммутации для ВС не учитываются необходимость наращивания системы и специфика системных взаимодействий в условиях распараллеливания вычислений. Коммутаторы расчитываются, в основном, лишь на попарные взаимодействия мини-ЭВМ, базирующиеся на разделении во времени средств сопряжения. Реконфигурация, программируемость структуры не носит развитого характера, осуществляется,как правило, вручную.
Данная работа связана с исследованиями в области программных средств организации параллельных вычислений, выполненных под руководством Н.Н.Миренкова в рамках научно-исследовательского проекта МИНИМАКС. Одним из внешних условий этого проекта было предположение о том, что аппаратура мульти-мини- машинной системы обладает следующими свойствами: I) позволяет организовать решение одной задачи на всей системе или нескольких задач на различных подсистемах; 2) предоставляет возможность программным способом перестраивать структуру связей между ЭВМ; 3) обладает определенной однородностью своих основных модулей (элементарных машин), позволяет наращивать их число в широких пределах.
Следует отметить, что подобные предположения используются и в более позднем проекте МИКРОС [28J, в котором базовое внимание уделено применению механизмов близким к тем, которые реализуются в сетях ЭВМ.
Важная особенность проекта МИНИМАКС - использование принципа иерархического управления, при котором принятие решений разнесено по нескольким уровням, и связано I) с базовым набором режимов работы подсистем, 2) с преимущественным назначением элементарной машины отдельному пользовательскому процессу.
Целью диссертации является исследование и разработка в рамках проекта МИНИМАКС операционной системы для однородных мульти-мини - машинных систем с программируемой структурой. Достижение цели связывается с рассмотрением следующих задач: разработкой структуры операционной системы и алгоритмов базовых функциональных блоков; аналитическим исследованием взаимодействий этих блоков; разработкой методики программной организации отказоустойчивых параллельных вычислений;
4) созданием экспериментальной ОС и реализацией на.ее основе специализированной системы сбора, хранения и переработки данных.
Методы исследования опираются на теорию массового обслуживания, параллельную обработку данных и системное программирование .
Научная новизна работы связана с предложенной структурой и составом базовых блоков ОС, разработанной моделью взаимодействий блоков и исследованием временных характеристик этих взаимодействий, разработкой алгоритмов управления процессами, происходящими в разных элементарных машинах, подходами к программной реализации отказоустойчивых вычислений.
Практическая ценность работы состоит в следующем.
Создана операционная система МИНИМАКС, обеспечивающая базу для проведения экспериментов по параллельному программированию. На основе этой ОС разработана экспериментальная система сбора, хранения и обработки данных районного уровня.
Получены расчетные формулы и составлена программа, позволяющая вычислять среднее время доступа процесса, происходящего в одной ЭВМ, к памяти другой ЭВМ, а так же расчетные формулы и программа для оптимизации временных шагов, через которые необходим контроль аппаратуры и анализ вычислений. Проведен численный анализ взаимодействий блоков ОС.
Использование результатов работы. Результаты работы нашли свое применение в Институте математики СО АН СССР при создании 3-х машинной системы МИНИМАКС, предназначенной для исследований по параллельной обработке данных, в Сибирском филиале ВГПТИ ЦСУ СССР (Новосибирск) при выполнении работ по системам переработки статистических данных, в ОКБ "Меркурий" (Смоленск) при создании проблемно-ориентированных вычислительных систем.
Аппробация. Основные результаты работы обсуждались на семинаре Лаборатории математического обеспечения Института математики СО АН СССР, на ІУ Всесоюзном симпозиуме по проблемам избыточности (Ленинград, 1974), на ІУ Всесоюзной конференции по однородным вычислительным системам и средам (Киев, 1975), на Всесоюзной конференции им.А.С.Попова (Новосибирск, 1975), на Всесоюзных школах-семинарах "Высокопроизводительные системы и параллельное программированиеи (Алушта, 1982, Уфа 1984) и опубликованы в 18 работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Содержит 140 страниц основного текста, I приложение, 38 рисунков. Общий объем диссертации 183 страницы. Библиография содержит 77 наименований.
Краткое содержание работы. В первой главе формулируются принципы построения операционных систем для ВС из мини-ЭВМ. Рассматривается структура и состав ОС, вопросы реализации алгоритмов основных блоков ОС МИНИМАКС. Описываются языковые средства для задания взаимодействий параллельных процессов.
Вторая глава посвящена аналитическому исследованию взаимодействия блоков ОС. Строится стохастическая модель взаимодействий блоков двух смежных уровней. Рассматриваются два метода обслуживания параллельных процессов при доступе их к памяти других ЭМ, приводятся аналитические оценки среднего времени доступа к такой памяти. Описываются результаты их использования для системы МИНИМАКС.
В третьей главе рассматриваются общие схемы программной организации отказоустойчивого выполнения параллельных программ. Рассматриваются методические аспекты связанные с функционированием специальных блоков ОС, повышающих надежность вычислений. Выводятся формулы для определения временных шагов, через которые необходимы контроль и анализ вычислений. Рассматривается организация отказоустойчивости в системе МИНИМАКС.
В четвертой главе описывается реализация системы сбора, хранения и переработки данных районного уровня на основе ОС МИНИМАКС, Основное внимание уделяется специализированной базе данных и языку управления этой базой, а также применению предложенных подходов для организации отказоустойчивой работы при построении указанной системы. - II -
Принципы построения и общая структура ОС
При переходе от однопроцессорных к многопроцессорным ВС возрастает нагрузка на ОС как за счет интенсификации потока обращений, так и за счет реализации дополнительных (назовем их системными) функций. Список таких функций существенно зависит как от предлагаемых вычислительных услуг, ожидаемых от системы, так и от ее аппаратурных возможностей.
В проекте МИНИМАКС вычислительные услуги в общем виде характеризуются следующим: возможностью параллельного выполнения на разных ЭВМ разных задач или разных частей одной задачи;
- организацией коллективного доступа к системе путем одновременного доступа к разным машинам;
- возможностью продолжения вычислений при появлении аппаратных или программных ошибок;
- постепенным наращиванием числа ЭВМ в системе с сохранением совместимости программного обеспечения.
Аппаратура ВС представляет собой многомодульный комплекс с программно перестраиваемыми связями между модулями 37]. Основу модулей, называемых элементарными машинами (ЭМ), составляют мини-ЭВМ М-6000 и CM-I. Объединение машин в единую многопроцессорную установку осуществляется с помощью специального системного коммутатора, представляющего собой двумерную решетку, в каждом узле которой находится элементарный модуль межмашинной связи (ММС). ММС имеет непосредственную связь с одной мини-ЭВМ и с четырьмя соседними элементарными модулями коммутатора. Взаимодействие ЭМ и разбиение системы на автономно работающие подсистемы обеспечиваются программированием соответствующих путей и непересекающихся графов в двумерной решетке системного коммутатора Минимальное число ЭМ в системе - 2, максимальное - 64.
Каждый процессор имеет доступ к любой ячейке оперативной памяти всей ВС, однако "механизм" доступа к памяти своей машины отличается от "механизма" доступа к памяти других машин, т.е. оперативная память всей системы по отношению к пользовательским процессам трактуется как двухуровневая. Первый уровень - память своей ЭМ, второй - память других ЭМ.
При этом доступ к памяти других ЭМ может осуществляться только посредством операторов системных взаимодействий (см. п. 1.4). Внешние устройства системы подключаются через стандартные средства сопряжения мини-ЭВМ.
Важным свойством системы МИНИМАКС является стандарти-зованность (однородность) ее аппаратурных модулей. Однородность определяется относительно свойств, присущих всем ЭМ. Ее определяют одинаковый интерфейс между ЭМ и формат команд и др.
ММС обеспечивает прием-передачу информации собственной ЭМ, а также транзитные передачи других машин [37]. Все передачи синхронизируются по сигналам запрос/ответ, что обеспечивает обмен информацией в условиях любых рассогласований скоростей работы машин.
Взаимодействие между ЭМ осуществляется по двумерным связям I и по одномерным связям 2 (замкнутым в кольцо), а между ЭВМ и ММС по связям 3 (рис.1.1). Различаются взаимодействия двух типов: управление и обмен, процесс выполнения которых разбивается на три этапа. На первом этапе формируется область связности между участвующими во взаимодействии ЭМ, на втором - выполняется взаимодействие, на третьем производятся действия, разрешающие использовать ЭМ в других взаимодействиях.
Постановка задачи
При обработке оператора индивидуального взаимодействия управление и необходимая информация передаются диспетчеру, находящемуся в этой же ЭМ. Диспетчер, получив управление, устанавливает признак запроса к старшему диспетчеру подсистемы.
Первый способ обслуживания старшим диспетчером заявок от диспетчеров ЭМ состоит в следующем. По каналам межмашинной связи он последовательно проверяет наличие признаков запроса от диспетчеров ЭМ,имена которых находятся в списке проверяемых диспетчеров. Обнаружив запрос от какого-либо диспетчера, он прокладывает канал связи к соответствующей ЭМ и принимает от диспетчера необходимую информацию (паспорт, запроса на взаимодействие с другой ветвью). Ветвь, вызвавшая взаимодействие блоков операционной системы, ставится в очередь ждущих ветвей (запрос заносится в список запросов на взаимодействие). Старший диспетчер проверяет только те диспетчеры ЭМ, у которых нет стоящих в очереди ждущих ветвей. После однократной проверки признаков запроса от всех проверяемых диспетчеров и приема запросов от них (если запросы есть), старший диспетчер проверяет условие синхронизации для каждого запроса из списка запросов на взаимодействие. Условием . синхронизации является истинность определенной логической функции над заданными семафорами. Если для запроса такое условие выполняется, то старший диспетчер коммутирует канал связи между запрашивающей и запрашиваемой ветвью, после чего они реализуют взаимодействие, заданное оператором индивидуального взаимодействия, а также изменение состояния семафоров. Список запросов на взаимодействие проверяется старшим диспетчером многократно, так как нижестоящие по списку запросы могут делать условия синхронизации истинными для вышестоящих запросов. Проверки осуществляются до тех пор, пока в списке останутся только такие запросы, для которых условия синхронизации не выполняются. После взаимодействия ветви продолжают свою работу.
Однократный опрос всех проверяемых диспетчеров и обслуживание запросов, для которых выполнено условие синхронизации будем называть циклом обслуживания подсистемы.
Второй способ обслуживания старшим диспетчером заявок от диспетчеров ЭМ, состоит в следующем. Старший диспетчер по каналам межмашинной связи последовательно проверяет наличие признаков запроса от диспетчеров ЭМ, Обнаружив запрос от какого-либо диспетчера, он прокладывает канал связи к соответствующей ЭМ и принимает от диспетчера необходимую информацию. После чего старший диспетчер проверяет условие синхронизации для поступившего запроса. При выполнении условия синхронизации старший диспетчер обслуживает данный запрос аналогично как и в первом способе обслуживания заявок. После обслуживания запроса старший диспетчер проверяет условие синхронизации для каждого запроса, стоящего в списке запросов на взаимодействие и при выполнении условия синхронизации для какого-либо запроса обслуживает его. Очередь запросов на взаимодействие проверяется старшим диспетчером многократно, т.е. обслуживание очереди запросов осуществляется аналогично как и в первом способе обслуживания заявок.
При невыполнении условия синхронизации для поступившего запроса, ветвь,вызвавшая взаимодействие блоков операционной системы, ставится в очередь ждущих ветвей (запрос заносится в список запросов на взаимодействие).
После чего старший диспетчер последовательно по списку имен проверяемых диспетчеров продолжает проверку запросов от диспетчеров ЭМ.
Схемы применения точек контроля и возврата.
Отказоустойчивость в системах рассматривается по отношению к физическим и субъективным неисправностям. Физическая неисправность - это непредусмотренное изменение значений одной или нескольких логических переменных в системе. Субъективные неисправности связаны с недостатками программного обеспечения системы, которые остались невыявленными до момента возникновения отказа, с ошибками в специальных пользовательских программах, с неправильным взаимодействием человека с машиной через пульт управления и др. [54].
В данном разделе отказоустойчивость рассматривается по отношению к некоторым субъективным неисправностям (неверное задание межпроцессорного взаимодействия) и некоторым физическим неисправностям (сбои аппаратуры, выход из строя отдельных ЭМ).
Обнаружение неисправностей разделяется на два типа: оперативное, осуществляемое одновременно с работой системы; и автономное, осуществляемое при временном перерыве работы.
Программные методы оперативного обнаружения основаны на параллельном исполнении нескольких программ и/или сводятся к введению в программу дополнительных функций (см.3.2). При параллельном исполнении несколько одинаковых программ, соответствующих одной ветви параллельной программы, пользуются отдельными процессорами и разной памятью; сравнение результатов осуществляется ими через определенные промежутки времени путем обмена данными. При выполнении каждой ветви п-программы на одной ЭМ для контроля вычислений вводятся специальные подпрограммы, обеспечивающие: сравнение содержимого заданных областей памяти, повторное выполнение определенных сегментов программы, обмен информацией между ветвями, перестройку п-программы на меньшее число ветвей, обнаружение семантических ошибок в программах и т.д.
Программные методы автономного обнаружения неисправностей предполагают использование стандартных тестовых и диагностических программ отдельных машин системы.
Для выполнения дополнительных функций в программе должны быть выбраны точки (операторы) обращения к соответствующим подпрограммам [32]. Эти точки делятся на два типа: контроля и возврата.
Точка контроля связывается с обменом информации между машинами и анализом определенных областей памяти.
Точка возврата связывается с запоминанием: I) данных, необходимых для перезапуска программы, и 2) места, с которого этот перезапуск нужно осуществить.
Ниже приведены общие схемы применения точек контроля и возврата при создании п-программ, ориентированных на выполнение в системах типа МИНИМАКС. Эти схемы ориентированы на программные методы организации отказоустойчивости.
Метод состоит в повторном выполнении сегментов, заключенных между точкой возврата и точкой контроля, и сравнением результатов обоих выполнений. Несовпадение результатов хотя бы в одной ветви ведет к возобновлению вычислений с начала сегмента (точки возврата) во всех ветвях.
Общее описание и структура системы "РАЙОН"
СистемамРАЙ0Н"[44,60] призвана автоматизировать процессы сбора данных статотчетности ЦСУ СССР и ввода их в систему на предприятиях, ослабить этим самым пиковые нагрузки на лиц, ответственных за ввод данных, упорядочить и усилить контроль за сроками и качеством вводимой информации, обеспечить ведение районной базы данных, переработку данных и оперативную выдачу таблиц отчетности и различных справок.
"РАЙОН" есть совокупность программно-информационных средств, погруженных в аппаратуру мульти- мини машинной системы. Ее пользователю практически не нужно знать ее структуру и особенности внутренних механизмов функционирования; ему достаточно уметь работать за терминалом, установленным на его рабочем месте (исключение составляют те пользователи, которые ответственны за эксплуатацию системы). Конкретные возможности, предоставляемые системой каждому пользователю, определяются языком, на котором осуществляется общение с системой, и заданиями, которые пользователь может давать системе на этом языке.
Отметим общие услуги предоставляемые системой:
1. Возможность для предварительной подготовки и хранения данных статотчетности.
2. Контролируемый по паролю ввод готовых данных.
3. Контроль за своевременным поступлением данных от предприятий.
4. Хранение данных каждого предприятия за текущий год, а при необходимости - и за несколько лет.
5. Организацию внутренней почтовой службы для обмена сообщениями между пользователями.
6. Обработку данных и подготовку сводных таблиц статотчетности за определенный период.
7. Передачу данных в облстатуправление.
8. Выдачу документов статотчетности по директивам статинспекторов или других пользователей.
9. Настройку (адаптацию) системы на число и состав предприятий, формы входной отчетности и выходные сводные таблицы, периоды отчетности и т.д.
Перечисленными услугами пользуются три основных категории пользователей: ответственных за ввод данных на предприятии, статинспекторов, ответственных за эксплуатационное обслуживание системы.
Программное обеспечение системы "РАЙОН" (если у него исключить средства генерации и средства информационной поддержки) можно трактовать как одну параллельную программу, реализующую распределенную обработку данных. В этой параллельной программе существует пять типов ветвей.
Ветви первого типа обеспечивают ввод данных на предприятиях, число таких ветвей равно числу предприятий; ветви второго типа обеспечивают непосредственное обслуживание стат-инспекторов, т.е. они выдают данные из системы (число этих ветвей равно числу элементарных машин системы, играющих роль интеллектуальных терминалов дня указанной категории пользователей); ветви третьего типа организуют хранение данных и доступ к ним, число ветвей определяется числом машин, которые выделяются для ведения банков данных; ветви четвертого типа осуществляют статистическую обработку введенных данных и формируют сводные выходные таблицы, число ветвей также как и в предыдущих случаях определяется при запуске системы в эксплуатацию; наконец, ветвью пятого типа является диспетчерская ветвь, организующая работу и специфические взаимодействия всех ветвей параллельной программы.
Параллельная программа системы "РАЙОН", реализуемая на вычислительной системе МИНИМАКС, представляет собой совокупность шести ветвей, среди которых есть все упомянутые выше типы ветвей, причем две ветви принадлежат второму типу. Ветви получили следующие названия: диспетчерская, ведение базы данных, обработка данных, ввод данных на предприятии, вывод документов для райинспектуры, вывод документов для облстат-управления.
