Содержание к диссертации
Введение
Глава I. Обеспечение функций организации прохождения задач в ОС 12
1.1. Структурная классификация 13
1.2. Режимы работы вычислительной установки . 18
1.3. Типы дисциплин диспетчеризации 19
1.4. Контроль и учет . 24
I.4.I. Назначение цены за пользование
вычислительными ресурсами . 27
1.5. Обзор алгоритмов планирования в ОС 30
1.6. Особенности использования математических методов анализа мультипрограммных систем . 33
1.7. Требования практики 36
Выводы. 37
Глава 2. Комплексный подход к вопросу организации про хождения задач . 38
2.1. Концептуальная модель вычислительной установки 39
2.2. Категория задач. 43
2.3. Классы задач 47
2.4. Взаимосвязь между категорией и классом . 52
2.5. Принципы обслуживания мультипрограммной смеси 53
2.6. Обеспечение режимов разделения времени и реального времени. 55
2.7. Обслуживание задач на многомашинном комплексе . 57
2.8. Обслуживание задач на многопроцессорном комплексе 61
2.9. Прохождение задач в вычислительной системе 62
2.9.1. Ввод задач 64
2.9.2. Планирование задач на буфере ввода . 66
2.9.3. Загрузка задач 68
2.9.4. Планирование мультипрограммной смеси. 69
2.9.5. Завершение задач 71
2.9.6. Обработка завершенной задачи . 72
2.10. Дополнительные средства планирования 74 Выводы . 76
Глава 3. Настройка программных средств планирования задач 77
3.1. Сервис бюджетного планирования 79
3.2. Функции сервиса бюджетной системы 81
3.2.1. Подготовка исходных бюджетов . 81
3.2.2. Корректировка бюджетов 83
3.2.3. Изменение режимов работы 84
3.2.4. Получение текущей информации . 85
3.2.5. Проверка корректности текущих бюджетов 86
3.3. Управление работой планировщика задач . 87
3.4. Управление планировщиком мультипрограммной смеси 89
3.5. Статистика и индексы производительности . 90
3.6. Перспективы развития системы 93
Выводы 95
Заключение 96
Литература
- Типы дисциплин диспетчеризации
- Особенности использования математических методов анализа мультипрограммных систем
- Взаимосвязь между категорией и классом
- Подготовка исходных бюджетов
Введение к работе
Увеличившаяся скорость обработки информации, появление запоминающих устройств большого объема и расширение терминальной сети изменили характер вычислительного процесса на вычислительных центрах. Число задач, решаемых на вычислительном центре резко возросло. В связи с этим возникла проблема автоматизации организации прохождения задач с учетом требований администрации, пользователей и обслуживающего персонала [1-8 ]. Указанные возможности должны обеспечиваться средствами ОС. Поэтому в настоящее время наряду с такими крупными проблемами, как обеспечение фушщионирования банков данных, организация связи с другими ЭВМ (объдинение в многомашинные и многопроцессорные вычислительные комплексы, организация сетей ЭВМ) все актуальнее становится проблема эффективной организации пропуска задач [1,5,9,10,11,12,13,14] .
С технической, экономической и общественной точек зрения очень существенно насколько хорошо вычислительная техника в сочетании с математическим обеспечением (МО) решает задачи, относящиеся к обработке информации [15] . И именно, с помощью механизма управления прохождением задач решается вопрос достижения поставленных целей в рамках крупного вычислительного центра (ВЦ).
Если отвлечься от всех тонкостей, касающихся структуры многомашинного или многопроцессорного вычислительного комплекса и его МО и перейти на точку зрения интересов людей,работающих на ЭВМ и использующих ее как инструмент, то мы име-
ем следующие интересы, которые вскрывают внешнюю проблему организации пропуска задач [ 2 ].
С точки зрения администрации ВЦ существенно иметь возможность:
управлять достаточно гибко всем процессом пропуска задач в соответствии с поставленными целями;
регистрировать все действия, связанные с использованием ЭВМ;
использовать эффективно все оборудование, включая и математиче ское обе спечение;
определять стоимость решения задачи с учетом использования всего оборудования, если это коммерческий центр.
С точки зрения оператора ЭВМ необходимо иметь возможность:
выполнять требования администрации по пропуску задач путем воздействия на ход вычислительного процесса;
получать необходимую информацию о состоянии задач и обеспечивать их дальнейшее прохождение в случае аппаратных и программных сбоев.
С точки зрения пользователя системы [ 5 ]он должен иметь возможность:
получать результаты своей задачи, как правило, в кратчайшие сроки;
компенсировать время, потерянное игл, в случае авост-ного завершения задачи по вине сбоя ОС или аппаратуры;
_ 7-
- планировать свою работу в условиях совместного ис
пользования ЭВМ большим количеством людей.
Кроме вышеперечисленных лиц в ВЦ имеется инженерная служба," которая обеспечивает безсбойное и правильное функционирование аппаратных средств", а также системные программисты, которые усовершенствуют и внедряют новое МО.
Проблема была бы исчерпана, если бы эти интересы обеспечивались соответствующими мощностями, а стоимость этих мощностей была бы невелика*
Но, к сожалению, на практике получается так, что интересы и запросы людей,использующих ЭВМ, растут существенно быстрее, чем развивается ЭВМ и ее МО.
При решении вопроса организации пропуска задач мы должны в первую очередь руководствоваться общими интересами,ко-торые заключаются в увеличении общей производительности системы за счет:
целенаправленного разделения вычислительных мощностей;
увеличения пропускной способности системы;
эффективного совмещения различных режимов использования ЭВМ (пакетного, разделения времени и реального времени)
Прежде всего требуется решить, каким образом будет осуществляться распределение и учет использования ресурсов машины. Решение этого вопроса зависит от режима использования ЭВМ. В настоящее время, как правило различают три режима использования ЭВМ:
- пакетный;.
режим разделения времени;
режим реального времени.
Если ЭВМ используется в одном из режимов, то задача существенно упрощается и для конкретного режима строится специализированная ОС [16,17 ] .
Более экономичным для универсальных ЭВМ является способ совмещения указанных режимов. При этом, обеспечивая включение в режиме пакетных задач, задач реального времени и разделения времени ОС должна руководствоваться следующими принципами:
стремится удовлетворить требования администрации, предъявленные к порядку прохождения задач;
обеспечить приемлемую скорость вхождения в решение задач реального времени и разделения времени;
осуществить скорейшее прохождение имеющегося пакета задач.
Выделяя центральный процессор (ЦП) в момент решения,необходимо учитывать характер задачи. Так, например, терминальные задачи должны обслуживаться так, чтобы обеспечить приемлемое время ответа пользователю, сидящему за терминалом. В качестве фоновых (идущих на фоне других задач) необходимо рассматривать задачи, которые хорошо загружают ЦП и имеют небольшое количество обменов с внешними устройствами. Тогда время ЦП, высвобождаемое терминальными задачами в промежутках между активной работой пользователя и задачами,осуществляющими обмен, может быть заполнено работой фоновой задачи. А дорогостоящий ресурс ЦП не будет простаивать.
Более специфические требования предъявляются к задачам реального времени [17 ].
Особо следует выделить ту среду,в рамках которой приходится решать поставленную задачу, а именно ОС»
Управление прохождением задач является неотъемлемой компонентой современной ОС,и к разработке этой конпоненты предъявляют следующие требования, которые характерны и для всей ОС в целом:
обеспечение эффективности использования всех ресурсов ЭВМ;
гибкость и адаптируемость системы к различным режимам работы;
удобство эксплуатации системы;
надежность функционирования;
небольшой накладной расход на обеспечение ее работы.
Данная работа решает актуальную задачу создания автоматизированной системы управления прохождением задач>удов-летворяющей вышеперечисленным требованиям, в рамках ОС ДИСПАК для ЭВМ типа БЭСМ-6 (включая МВКІ(Зльбрус-і"в комплектации со спецпроцессором, совместимым по системе команд с БЭСМ-6: Э1-К2, Э1-К4, Э1-К6) [18,19,20,21,22 ] .
Перечисленные требования определили те научные проблемы и направления, по которым необходимо было провести исследования при разработке системы управления прохождения задач:
найти и создать базовые средства в рамках ОС по автоматизации всего процесса прохождения задач;
предоставить пользователям возможности по управлению прохождением своих задач;
обеспечить административное воздействие на прохождение задач;
найти приемлемые алгоритмы разделения ресурсов для задач и пользователей;
создать средства учетности информации;
обеспечить различные режимы работы операционной системы (настроенные на поток задач в соответствии с временами суток, днями недели).
Цель диссертационной работы - исследовать и разработать принципы управления прохождением задач, обосновать выбор алгоритмов и методов решения проблем, возникающих при проектировании ОС многопроцессорных и многомашинных систем. В рамках этой задачи необходимо было разработать и практически проверить организацию и способы управления прохождением задач в рамках ОС ДИСПАК.
Новизна научных результатов. Основной элемент научной новизны вносят во-первых, комплексный подход к решению вопроса автоматизации управления прохождением задач, основанный на обеспечении противоречивых интересов административного управления, интересов пользователей и необходимости полной загрузки имеющихся аппаратных средств,во-вторых,многоплановость созданного аппарата,расшатанного как на многомашинные комплексы (связка ЭВМ БЭСМ-6) с выходом на общую внеш-
- II -
нюю память, а также на многопроцессорные комплексы (совокупность ЭВМ работающих на общую память), в-третьих, возможность адаптации указанного аппарата к условиям конкретного вычислительного центра (создания сервиса по управлению прохождением задач).
В свете этих моментов научной новизной обладают:
принципы организации прохождения^задач на вычислительных комплексах;
базовые средства обеспечивающие автоматизацию процесса управления прохождением задач;
аппарат административного воздействия на прохождения задач (бюджетирование);
алгоритмы планирования и диспетчирования;
принципы совмещения различных режимов работы ОС;
способы учета и контроля в рамках операционных систем и регистрации пользователей.
Практическая ценность» Все реализованные алгоритмы, включая сервисные,программы эксплуатируются в рамках ОС ДИСПАК на машинах БЭСМ-6 и Эльбрус I-K2 в комплектации со спецпроцессором [22] . Система показала свою эффективность, удобство использования, настраиваемость на конкретные условия вычислительных центров. Опыт и методы реализации были использованы для реализации аналогичных средств на ЕС ЭВМ [23 ] и могут быть использованы в других операционных системах.
Типы дисциплин диспетчеризации
Указанные выше классификации обязательно должны учитываться в ОС. То есть, она обязана с учетом структуры и способа функционирования выполнять основную цель вычислительной установки: добиваться максимальной производительности системы.
Указанные требования в рамках ОС обеспечиваются так называемой системой диспетчеризации или планирования [ 9] . Под диспетчеризацией (дисциплиной диспетчеризации) будем понимать совокупность правил, которая определяет стратегию распределения ресурса (прежде всего ЦП) между требо ваниями,оформленными в виде задач (заданий, процессов) [5, 9].
Дисциплина диспетчеризации включает две части : - формирование очередей на ресурсы (включая присвоение приоритетов); - обслуживание требований находящихся в очереди задач.
Система диспетчеризации характерна для всех ресурсов вычислительной установки и характеризуется иерархической структурой. Основную роль при этом играет организация распределения центрального процессора, в том числе и на многопроцессорных установках. Через ресурс центрального процессора реализуется доступ к любому другому ресурсу, в том числе и программному. Следующей важнейшей компонентой является память. При этом должно быть прежде всего установлено тесное взаимодействие между стратегией управления памятью и процессором. Такое же взаимодействие характерно и для других видов ресурсов (запрос памяти на Щ, МБ, программные ресурсы и т. д.), что нельзя не учитывать при обеспечении планирования прохождения задач в целом [io] .
При определении очередей одним из основных вопросов является определение рационального количества приоритетов и правил назначения их задачам.
В универсальных системах получить решение указанного вопроса весьма затруднительно. Здесь прежде всего приоритет формируется с учетом внешнего приоритета (назначаемого пользователем или администратором), состояния других задач и наличием ресурсов.
После назначения приоритетов заявки на ресурсы, как правило, оформляются в виде очередей, которые могут быть обслужены по различным правилам. Тот или иной метод обслуживания следует применять с учетом издержек на его обеспечение, так как для этого требуется время ЦП. Поэтому решение о применении того или иного правила должно производиться при учете поставленных целей и издержек на обеспечение работы алгоритма. Перечислим основные наиболее часто встречающиеся дисциплины обслуживания заявок.
Обслуживание в порядке поступления или FIFO (FIRST In -FIRST OUT ). При этом обслуживании первый пришедший - первым будет обслужен. Указанный способ обслуживания носит весьма распространенный характер в силу своей простоты и экономичности. /V ?. — т - ресурс —»- Л/ ИЬИ] Обслуживание по принципу L1 ГО ( LAST In - FiST OUT ) последний пришедший обслуживается первым. Данный принцип обслуживания характерен для обеспечения стековой организации памяти Г25,261 и реентерабельности программ.
Алгоритм ГБл/ (FOREGROund - BACKGROUnd ). В соот-ветствии с данной схемой обслуживания организуется N очередей. Вновь поступившая заявка занимает конец первой очереди. Первая заявка из очереди с номером n I (I п /V ) поступает на обработку только тогда, когда нет очередей с номерами меньшими П . Недообслуженная заявка попадает в конец очереди с номером п +1.
При поступлении новых заявок возможно несколько случаев. Новая заявка поступает в очередь п =1, затем довыполняется прерванная. Либо заявка на уровне п обрабатывается до конца своего кванта,после чего поступает на уровеньп+1, а новая заявка помещается в очередь п =1. Заявки на уровне Л/ обслуживаются по алгоритму pi F0 Данный алгоритм отдает предпочтение вновь поступившим коротким заявкам. При большой интенсивности поступающих заявок и при больших N время ожидания в очереди заявок может быть очень большим.
Особенности использования математических методов анализа мультипрограммных систем
Существует богатый набор различных математических методов, позволяющих описывать и исследовать процесс одновременного решения в ВС множества задач и рассчитывать показатели, характеризующие как работу, выполняемую МВК в целом, так и поведение каждой задачи или множества задач.
Здесь применяется хорошо развитый аппарат теории массового обслуживания [10,15,29,50,511 , теории очередей и теории расписаний, [51,52J .
Основополагающим результатом исследований для систем массового обслуживания с приоритетом является закон сохранения среднего времени ожидания и среднего числа требований в системе. Если .требования обслуживаются: .. \- независимо от их времени обслуживания, то распределение числа требований в системе инвариантно относительно порядка обслуживания; такой же результат справедлив для среднего времени ожидания для требований [ 29] : м X fM = TpW0= const где J L=A L B-L - загрузка системы массового обслуживания I потока; ц - общая загрузка системы массового обслуживания; Ш - количество потоков; у/ - среднее время завершения текущего обслуживания одной заявки из суммарного потока. То есть другими словами говоря, предпочтительное обслуживание заявок одного класса, осуществляется за счет требований другого класса. Данный закон универсален и справедлив для всех дисциплин обслуживания заявок. Его можно использовать для проведения статистического анализа.
При рассмотрении конкретных систем приемлемым является выбор компромисса между сложностью используемого аппарата и адекватностью описания исследуемой системы. Например, при обслуживании системы с количеством состоянии М, применяя о дифференциальный метод, необходимо использовать порядка М слов оперативной памяти и выполнить около М3 операций.
Уместно привести оценки работы алгоритма формирования расписания на использование абонентами ресурсов ВЦКП [ 53 ] . Алгоритм,написанный для ЭВМ EC-I030 на ПІД,в соответствии с исследованиями разработчиков требует объем памяти в байтах n= kN2+2N+22A/ + 2T ( 2 ) где Т - длительность в часах; А/ - число заявок абонентов. Время же выполнения программы пропорционально Л/ Т. Сведения, которые мы имеем по ГПВД г. Новосибирск, указывают, что за сутки на трех ЭВМ БЭСМ-6 проходит около 1500-2000 задач.
Несложные расчеты, при допущении того, что в сутки составляется расписание на 500 задач, а время одного цикла составляет около 0,1 сек показывают, что объем оперативной памяти требуемый для задачи составляет свыше I млн. байт, а время счета, чуть меньше 7 часов процессорного времени. Из указанных цифр видно, что практическое использование таких алгоритмов является проблематичным в условиях соответствующих скоростей ЭВМ и объемов памяти.
Методы моделирования ( аналитическое и имитационное) удобны при оценке производительности вычислительных систем, и это, по-видимому, основное их применение на настоящий момент в алгоритмах планирования прохождения задач. Но и здесь, к сожалению, есть общая для всех методов моделирования трудность - проблема точности и адекватное ти моделируемой системы.
Взаимосвязь между категорией и классом
Взаимная увязка класса и категории задачи происходит на протяжении всего процесса существования задачи в ОС. Категория задачи определяет срочность задачи внутри класса. Очередь задач в классе на момент конкуренции на вход в процессор выстраивается в следующей последовательности: - экспрессные задачи;, - лимитные задачи; - дежурные задачиі
С учетом того, что существует общий бюджет бумаги и заходов, на дальнейшее планирование бюджетная система пропускает на вход планировщику количество задач, соответствующее числу каналов, выделенных на соответствующий класс внутри многомашинного (многопроцессорного) комплекса. Таким образом, если допустим,что 7 классу выделили(на многомашинном комплексе из двух ЭВМ) внутри одной ЭВМ 5 каналов, а внутри другой 4 канала, то общее число пропущенных задач будет равно 9 задачам. Таким образом происходит адсорбция наиболее приоритетных задач по категориям для множества классов и сдерживается поток менее приоритетной категории ( рис.5 ).
При вводе задачи более высокой категории происходит пе рестановка в очереди и она занимает крайнюю позицию внутри своей категории (рис.6).
Следует заметить, что сдерживание потока менее приоритетной категории задач возможно, как уже говорилось, с помощью указания времени, когда необходимо включать соответствующую категорию задач.
Бюджетная система не пропускает на планирование задачи, у которых не установлены магнитные ленты и диски. Поэтому при прохождении через бюджетную систему, задача претендует теперь только на общий разделяемый ресурс, распределяемый из общего банка.
Взаимная увязка категории и номера класса происходит и в момент решения задачи при рассмотрении мультипрограммной смеси.
Принципы обслуживания задач мультипрограммной смеси
Обслуживание находящихся в решении задач производится в соответствии с принципами включения задач в решение, то есть производится с учетом административного и внутреннего приоритета задачи. При просмотре задач на включение в решение мы имеем следующую матрицу шкал, в которой отражены оба типа приоритетов.(рис.7)
Как видно из рисунка,наибольшей приоритетностью обладает задача, имеющая максимальную группу по номеру и максимальный номер подмножества. Группа с большим номером отводится под задачи реального времени, когда решение задач других групп блокируется. Планировщик включения задач в решение просматривает, начиная со старшей группы,задачи слева направо, с учетом их готовности к решению. При этом существует еще один механизм, позволяющий сглаживать возможную предпочтительность задачам, стоящим левее по соответствующей шкале.
Это механизм так называемой лестницы, который обеспечивает заданную скорость выбора задач. Каждой задаче выделяется квант времени К, исчерпав который задача попадает вниз, а вверх подымаются задачи, давно неполучавшие свой квант.При этом еще одним регулятором, позволяющим управлять скоростью выделения процессора, является квант К.
Данная возможность дает средство регуляции выбора задач в одной группе пропорционального кванту. Исходя из данного алгоритма, группа относится к категории задач, а подмножест-BG-I; классу задачи.
Таким образом, при соблюдении указанной стратегии учитывается как административный приоритет, так и системный.
В алгоритме при обработке шкал, оба этих механизма существуют вместе, и поэтому время обработки шкал занимает минимальное время.
Подготовка исходных бюджетов
Возможно получение текущего состояния каждого из каталогов по соответствующим директивам. Кроме этого существует возможность получения сводной таблицы, в которой отражается общее состояние бюджетов. Здесь же возможно получение расходов в коммерческих единицах.
Пользователь может получить сведения по состоянию своих бюджетов по распечатке конца задачи, в которой под колонкой ОСТ.Э КС, ОСТ.ЛШ., ОСТ.ДЕЕ., ОСТ .Б. печатается соответствующее количество бюджетов на данный момент времени (см.рис.П).
Появились возможности в сервисных диалоговых системах, обеспечивающие информацией о состоянии бюджетов пользователей [60,61] .
Общее состояние пакета задач, их очередность и прочую информацию можно получить по директиве ПАК, которая произведет распечатку всего буфера ввода с исчерпывающей информацией по состоянию задач.
В процессе работы ОС бюджетный каталог с текущими бюджетами является наиболее часто изменяемым по сравнению с другими каталогами ОС. Существует вероятность его порчи по сбою аппаратуры или вине операционной системы, что может привести к печальным последствиям. Для обеспечения надежности работы бюджетной системы фиксируется промежуточный каталог бюджетов, где хранится некоторое промежуточное состояние бюджетов от одного момента вызова сервиса до другого. Прежде чем данная фиксация произойдет, производится проверка правильности расходования бюджетов пользователей. Если вдруг у какого-то из клиентов, текущий бюджет оказывается больше промежуточного (т.е. бюджет возрос, чего не должно быть), то происходит восстановление бюджета по промежуточному состояшш. Возможно обновлешіе всего текущего каталога в случае явной порчи и несовпадения некоторого ключа, который фиксируетсяво всех трех каталогах: начальном, промежуточном и текущем. 0 произведенных коррекциях сообщается в виде распечатки и фиксируется в статистике бюджетной системы.
Таким образом, возможный ущерб, который может произойти при порче каталога, соизмерим с промежутком времени от последнего вызова сервиса до момента восстановления. Отсюда следует, что частота вызова сервиса определяется.,исходя из надежности работы вычислительной системы ,и устанавливается для каждой организации в отдельности.
Для изменения работы планировщика задач существуют описатели классов и ячейка режимов работы планировщика. Фактически число классов при задании параїлєтров может изменяться от одного до восьми. Указанное количество является параметром. Разделение на классы в настоящее время производится в основном по заказываемому времени решения, по присутствию шифра и маски в специальном каталоге реального времени, по наличию терминалов и присутствию признака формирования задачи от ОС. Существует возможность изменять интервалы времен, заказываемых задачей для решения, по которым задачи относятся к тому или иному классу. Потенциально возмогло разделение задач на классы и по другим признакам и их совокупности.
В описателе класса присутствуют каналы, которые выделены классу и их копия. Кроме этого, указывается порядок просмотра класса и его копия при обработке планировщішом данного класса. Б описатель входят признаки, которые появляются в динамике работы планировщика такие как: - признак,указывающий на наличие задач, готовых к решению (по томам ВД, Ш ж терминалам); - признак, сообщающий о включении задач из класса при последнем просмотре планировщиком; - признак, указывающий на отсутствие программных каналов на задачи класса; - признак изменения порядка класса.
Данные признаки позволяют получить информацию о состоянии всего класса, а при работе планировщика не просматривать список задач указанного класса, если нет условий для его работы
