Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

лучения результатов вычислений, для запроса информа­ ции, хранимой в системе.

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

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

В СРВ запросы пользователей на обслуживание по­ ступают в случайные моменты времени. Случайными ве­ личинами оказываются также требуемое для выполне­ ния программы пользователя время работы процессора, каналов и других устройств и необходимый объем опе­ ративной и внешней памяти. В процессе функционирова­ ния СРВ из-за ограниченности ее ресурсов в системе мо­ гут возникать несколько очередей, в том числе: 1) оче­ редь на ввод новых запросов пользователей; 2) очередь к процессору на обработку программ; 3) очередь к кана­ лам связи с периферийными устройствами; 4) очередь на вывод из системы результатов обработки программ. Длина очередей, время пребывания запросов и программ в очередях являются случайными величинами, завися­ щими от параметров вычислительной системы, вероят­ ностных характеристик потока запросов пользователей и их программ, а также от метода планирования работы вычислительной системы.

Качество функционирования СРВ определяется сле­ дующими основными характеристиками: 1) максималь­ ным количеством пользователей, обслуживаемых систе­ мой; 2) средним временем ожидания программой обслу­ живания; 3) средним временем ожидания пользователем ввода нового запроса на обслуживание; 4) потерей вре­ мени в системе, связанной с переключением программ; 5) длиной очередей программ на обслуживание процес­ сором, каналами, устройствами ввода и вывода. Поря­ док распределения между пользователями основного ре­ сурса вычислительной системы — времени процессора

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

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

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

612

пользователи имеют различный приоритет в обслужи­

вании.

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

р у с е л и ) . Соответствующая схема одноочередной СРВ представлена на рис. 11-15. В системе реализуется об-

Д и стами, и онмые пу ль ты

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

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

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

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

меньше отношение длительности выполнения программы к кванту времени.

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

не

закончено

Очередь к

Об ра тн ая связь

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

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

Дт = 2тД,

где Ат — квант, выделяемый программе из m-й очереди (О< m ^ :k ); А — квант для программы из нулевой оче­ реди. Обычно А соответствует 200—500 мсек.

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

614

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

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

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

і = [log2([LP/L4\ + 1)],

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

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

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

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

Теория и методы анализа СРВ строятся на основе использования результатов теории и методов анализа систем массового обслуживания. Лишь для сравнитель­ но простых случаев удается воспользоваться для анали­

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

В более сложных случаях СРВ исследуются путем построения так называемой «имитационной модели» и ее анализа методом статистических испытаний (методом Монте-Карло).

Н е п р е р ы в н а я м а р к о в с к а я м о д е л ь С Р В . Построим аналитическую модель для СРВ, в основе которой лежит отождествление функционирования системы с простым непрерывным марковским процессом [Л. 48].

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

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

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

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

Примем, что случайные величины — время работы пользователя за пультом (т. е. продолжительность пуль-

Ы 6