4.2.ОРГАНИЗАЦИЯОБСЛУЖИВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ

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

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

онный) характер. При              прямой задачи се условиями

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

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

На рис. 4.2 изображена схема организации многомашинной вычислительной системы, где упорядочение очереди из потока заданий осуществляется диспетчером Д1. а ее обслуживание ЭВМ — через диспетчера Д2.

Такая система может быть охарактеризована как система с дискретными состояниями и непрерывным временем. Под диск­

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

Система (в нашем случае вычислительная система) изменяет свои состояния под действием потока заявок (заданий) — посту­пающие заявки (задания) увеличивают очередь. Число заданий в очереди плюс число заданий, которые обрабатываются ЭВМ (т.е. число заданий в системе)., — это характеристика состояния сис­темы. Очередь уменьшается, как только одна из машин заканчи­вает обработку (обслуживание) задания. Тотчас же на эту ЭВМ из очереди поступает стоящее впереди (или по какому-либо дру­гому приоритету) задание и очередь уменьшается. Устройства обработки заявок в теории систем массового обслуживания на­зывают каналами обслуживания. В этой теории поток заданий (за­явок на обслуживание) характеризуется интенсивностью X — средним количеством заявок, поступающих в единицу времени

 

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

^обсл

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

Пример.

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

•       в системе протекают марковские случайные процессы;

•       потоки событий (появление заданий и окончание их обработки) являются простейшими;

•      число заданий в очереди не ограничено, но конечно.

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

Простейший поток событий характеризуется стационарностью, ор­динарностью и "беспоследействием'⁷. Стационарность случайного по­тока событий означает независимость во времени его параметров (на­пример, постоянных интенсивностей Я и ц). Ординарность указывает на то, что события в потоке появляются поодиночке, а "беспоследей­ствие"— на то, что появляющиеся события не зависят друг от друга (т. е. поступившее задание не обязано своим появлением предыдущему).

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

Обозначим состояния рассматриваемой вычислительной системы: 5о — в системе нет заданий;

— в системе одно задание, и оно обрабатывается на ЭВМ 1; $2 — в системе два задания, и они обрабатываются на ЭВМ 1 и ЭВМ 2;

— в системе п заданий, и они обрабатываются на ЭВМ 1, ЭВМ 2,..., ЭВМ М

Б„ + [ — в системе (л + 1) заданий, п заданий обрабатываются ЭВМ, а одно стоит в очереди;

+ — системе (и + 2) заданий, два задания стоят в очереди;

^п + т — в системе (п + т) заданий, т заданий стоят в очереди.

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

Здесь окружности — состояния, дуги со стрелками — направления переходов в следующие состояния. Дугами помечены интенсивности потоков событий, которые заставляют систему менять состояния. Пе­реходы слева направо увеличивают номер состояния (т. е. число зая­вок в системе), справа налево — наоборот. Как уже указывалось, уве­личение числа заявок в системе происходит под воздействием входно­го потока заявок с постоянной интенсивностью X. Уменьшение числа заявок в системе (уменьшение номера состояния) происходит под воз­действием потока обслуживания, интенсивность которого определяет­ся средним временем обслуживания задания одной ЭВМ и числом ЭВМ, участвующих в обработке заданий при данном состоянии системы. Если одна ЭВМ обеспечивает интенсивность потока обслуживания ц (на­пример, в среднем 30 заданий в час), то одновременно работающие две ЭВМ обеспечат интенсивность обслуживания 2|1. три ЭВМ — Зц, п ЭВМ — щ. Такое увеличение интенсивности обслуживания будет про­исходить вплоть до состояния когда п заданий параллельно нахо­дятся на обработке на п ЭВМ. Появление в этот момент заявки перево­дит систему в состояние + \, при котором одна заявка стоит в очере­ди. Появление еще одной — в состояние + 2 и т.д. Интенсивность же потока обслуживания при этом будет оставаться неизменной и равной иц, так как все ЭВМ вычислительной системы уже задействованы.

При исследовании такой вероятностной системы важно знать зна­чение вероятностей состояний, с помощью которых можно вычислить показатели эффективности, такие, как количество заданий в системе, время ожидания обработки, пропускная способность и т.д. Как извест­но, значение вероятности лежит в пределах от 0 до 1. Так как мы рас­сматриваем дискретную систему, то в любой момент времени она мо­жет находиться только в одном из состояний и,      сумма вероятностей состояний Р) всегда равна 1, т.е.

где к — число возможных состояний системы;

I — номер состояния.

Для того чтобы определить значение Р, (0, приведенной формулы недостаточно. Кроме нее составляется еще система дифференциаль­ных уравнений Колмогорова, решение которой и дает искомые значе­ния Л'(0- Чаще всего реальные вычислительные системы быстро дос­тигают установившегося режима, и тогда вероятности состояний пере­стают зависеть от времени и практически показывают, какую долю достаточно длинного промежутка времени система будет находиться в том или ином состоянии. Например, если система имеет три возмож­ных состояния: Р\ = 0,2, /"г = 0,6, Рз =0,1, то это означает, что в состо­янии 8] система в среднем находится 20% времени, в Бх      60%, а в

времени. Такие не зависимые от времени вероятности назы­вают финальными.

Финальные вероятности системы вычислить уже проще, так как уравнения Колмогорова при этом превращаются в алгебраические.

 

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

 

Это система однородных уравнений (свободный член равен нулю), но благодаря тому, что

система разрешима. Финальные вероятности состояний системы в ре­зультате решения описываются следующими математическими отно­шениями:

вероятность состояния при котором в системе заявок нет;

параметр системы, показывающий, сколько в среднем заявок

приходит в систему за среднее время обслуживания заявки од­ной ЭВМ (одним каналом обслуживания);

 

где Р, — вероятность состояния 5,;

где Р_п — вероятность того, что все ЭВМ заняты;

п^п+)

р ■ = ■

' »+7

где />„ +j— вероятность того, что все ЭВМ системы заняты обработкой заданий и/ заявок стоят в очереди.

Приведенные формулы имеют смысл только в том случае, если очередь конечна. Условием конечности длины очереди является

£<1. п

Или если заменить р его выражением через А, и |_1, то

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

п

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

Основными показателями эффективности рассматриваемой систе­мы являются: среднее число занятых каналов (т.е. ЭВМ) — к, среднее число заданий в очереди — и в системе — среднее время

пребывания задания в системе —  очереди —

 

 

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

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

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

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