Ill:Выполнснис программы а Выполнение про ерам мы в

Счет

Счет

*)

^N Ожидание^—

А В В А В

А в

1

1

I

Рис. 13.1. Выполнение программ в однопрограммном (а) и мульти­программном (б) режимах

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

Практически за счет мультипрограммирования удается по­высить пропускную способность, а следовательно, загрузку про­цессора в 4—5 раз.

Из сказанного следует, что мультипрограммирование явля­ется также средством уменьшения времени выполнения заданно­го набора программ. Более того, если обрабатывается всего одна программа, то за счет распараллеливания программы и муль­типрограммной обработки удается сократить время ее выпол­нения.

Распараллеливание программ является широко используе­мым приемом повышения коэффициента мультипрограммности.

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

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

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

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

Организация обработки пакет а заданий в мультипрограммном режиме

Организация обработки пакета заданий показана на рис. 13.2. Предварительно на языке управления заданиями со­ставляется описание задания и его пунктов, в котором для за­дания указываются необходимая емкость ОП, приоритет и класс, а для каждого пункта — имена используемых программ, входных и выходных наборов данных, приоритет пункта, не-

Пакеты заданий и Входные наборы данных

Устройства входные

системного очереди

ввода заданий

разных классов в ЗУ на дисках

Выходные очереди разных классов в зу на дисках

Устройства

системного

дыдода

Процессор

Рйс. 13.2. Организация обработки пакета заданий в мультипрограммном режиме

обходимые емкость ОП и устройства. Описания заданий объеди­няются в пакет.

Обработка пакета заданий организуется и управляется про­граммами операционной системы (программой супервизор и др.).

Тексты заданий и входные наборы данных вводятся про­граммой системного ввода с устройств системного ввода (перфо- картный ввод, ЗУ на лентах или дисках). Очереди заданий, упо­рядоченные для каждого класса в соответствии с приоритетом заданий, располагаются в ЗУ прямого доступа (ЗУ на дисках).

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

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

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

Группам заданий (задач), находящимся в ОП, может быть назначена обработка с квантованием времени, при которой су­первизор поочередно выделяет заданиям один и тот же интервал (квант) времени работы процессора. Квантованная обработка позволяет избежать монополизации процессора одной задачей, что особенно важно при диалоговом режиме работы ВС.

Результаты выполнения задания (задачи) помещаются в ЗУ прямого доступа (ЗУ на дисках) в выходную очередь, соответ­ствующую выходному классу задания.

Выходные данные выводятся программой системного вывода на одно из устройств системного вывода (пёрфокартный вывод, печатающее устройство, ЗУ на ленте).

Для организации мультипрограммного вычислительного про­цесса ВС требуются определенные аппаратурные и программные средства.

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

Прерывание программ. Часть функций, которые выполняет система прерывания мультипрограммной ЭВМ, свойственна и однопрограммным системам: обеспечение параллельной рабо­ты периферийных устройств и процессора, синхронизация рабо­ты ЭВМ с внешними по отношению к ней устройствами. Не­которые другие функции являются специфическими для муль­типрограммного режима. Если, например, в однопрограммной машине произошло обращение к памяти по несуществующему в данной конфигурации адресу, то машина остановится. При мультипрограммной работе в подобных ситуациях останавлива­ется выполнение только данной программы, но не система. Сле­довательно, каждая ситуация, подобная указанным выше, дол­жна вызывать запрос прерывания, позволяющий супервизору указать пользователю на его ошибку, не прекращая исполнения других программ. Имеются и другие особенности прерывания в мультипрограммных системах.

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

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

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

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

Привилегированные команды. В мультипрограммной системе часть команд может выполняться только супервизором. Такие команды называют привилегированными.

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

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

3. Структура и принцип действия ВС коллективного пользования (разделения времени)

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

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

В результате пользователь утратил непосредственную связь с ЭВМ, характерную для эксплуатации машин первого по­коления.

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

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

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

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

Более характерным является случай, когда в ВСКП по­ступают запросы, сильно отличающиеся по необходимому ма­шинному времени, причем заранее нельзя определить продолжи­тельность обработки того или иного залроса. Такая ситуация характерна для любого вычислительного центра без постоянной номенклатуры расчетов.

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

Для создания эффекта прямого контакта пользователя с системой ■ путем сокращения времени ожидания ответа на короткие запросы в ВСКП применяют квантованное обслужива­ние, или, другими словами, разделение времени при выполнении запросов..

Вычислительная система с разделением времени (СРВ), работающая в мультипрограммном режиме, в определенной по­следовательности обслуживает пользователей, выделяя про­грамме (запросу) каждого пользователя некоторый интервал времени (квант обслуживания). Если в течение выделенного программе кванта времени ее обработка не заканчивается, про­грамма прерывается и становится в очередь программ, ожидаю­щих обработки.

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

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

Дисциплины обслуживания в СРВ. Было предложено не­сколько дисциплин обслуживания пользователей в СРВ. Их можно разбить на две основные группы: одноочередные и много­очередные.

Одноочередная дисциплина обслуживания. Схема однооче­редной СРВ представлена на рис. 13.3. Вновь поступающие от пользователей запросы (программы) ставятся в конец очереди. Для обслуживания выбирается программа из начала очереди, и ей отводится квант времени Л процессора. Если за это время программа успеет завершиться, результат будет выдан пользо­вателю, а процессор приступит к обработке следующей из очере­ди программы. Если программа за выделенный квант времени не закончится, обработка ее прервётся и она поступит в конец очереди.

Иногда в целях уменьшения времени отклика системы на короткие (по времени выполнения) запросы рассматриваемая дисциплина модифицируется, и вновь поступающий в систему

Пульты

пользователей

ф	Очередь		Процессор и другие средства
• •			вычислительной системы
• •		Обслуживание запроса не закончено
Ответ (обслуживание запроса закончено)

Рис. 13.3. Система разделения времени с одноочередной дисциплиной об­служивания

\

рис. 13.4. Система разделения времени с многоочередной дис­циплиной обслуживания

Лоток новых запросов

Очередь О ЧИП Очередь 1 Н"П"П

Обслуживание

закончено

Процессор^*

и

Очередь к

-cm

Обслуживание не закончено

запрос становится в начало очереди. В остальном процесс фун­кционирования остается без изменения.

Многоочередная дисциплина обслуживания. Для сокраще­ния потерь времени, связанных с переключением программ, и обеспечения приоритета для коротких запросов (программ) используют дисциплину обслуживания с несколькими очередями (рис. 13.4). Приоритет очереди убывает с возрастанием ее номе- / ра ш (O^m^fc). Вновь поступающий в СРВ запрос ставится в конец очереди, имеющей старший приоритет (т = 0).

В такой^системе следующим подлежит обслуживанию запрос из начала очереди с номером т, если очереди с меньшими номе­рами (с более высоким приоритетом) пустые. Если за выделен­ный программе, находившейся в очереди т, квант времени ее обработка не заканчивается, программа прерывается и перехо­дит в конец очереди с номером т+1. Выделяемый программе квант времени возрастает с увеличением номера очереди обычно по правилу

Лт=2^тЛ,

где Д_т — квант, выделяемый программе из m-й очереди (0<;

Л — квант для программы из нулевой очереди. Обыч­но Л = 200-i-500 мс.

Программы из последней очереди обслуживаются до конца без прерывания. Если во время обслуживания программы из очереди т в очереди с большим приоритетом появляется новая программа, то после окончания текущего кванта Л обрабатыва­емая программа прерывается и возвращается в начало своей очереди, с тем чтобы впоследствии дополучить недоданное по отношению к значению 2^т А время.

Чтобы избежать недопустимо долгого ожидания для боль­ших программ, приоритет делается зависящим от времени ожи­дания. Если ожидание превысит некоторое установленное значе­ние (например, 60 с), программа перейдет в следующую очередь с меньшим номером. Таким образом, в рассматриваемой системе

приоритетные соотношения между запросами устанавливаются в самом процессе выполнения программ (динамические приори­теты ).

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

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

В алгоритме планирования Ф. Корбато, реализованном в од­ной из первых СРВ, программа сразу поступает в очередь, имею­щую номер

»=]log₂(]y^[+l)[.

где 1_Р — число байт в программе; /_д — число байт, которое может быть передано из оперативной памяти во внешнюю или обратно за время А; от выражений, стоящих в квадратных скобках, берется целая часть. В остальном дисциплина обслужи­вания соответствует описанной выше.

Процесс взаимодействия пользователя с СРВ показан на рис. 13.5. Пользователь со своего пульта вводит запрос (требо-

Пользователь начинает завершает ^ввод запроса __

Пульт ПОЛЬ зо-*

вателя

запроса

Вывод ответа \на запрос

■ *

Щ

Обработка запроса- выполнение програм­мы пользователя