<<
>>

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

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

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

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

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

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

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

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

а ее обслуживание ЭВМ — через диспетчера Д2.

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

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

ЭВМ 1

Рис. 4.2. Схема организации обслуживания заданий в многомашинной вычислительной системе

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

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

^обсл

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

Пример.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(ІД + А )/>,= АР0 + 2/ЛР2 ;
(2^ +Я )Р2 =
(2// + А)/} = АР_] + (г + 1 < г < л;
(нД -!-А)Р„ = АР^+прР^;
(лд + А)Р„+1 = АР„+іщРп+1\
(лД + А)Р„_2 = АРпА + пцРп+ъ-
(пц + Л)Ря+1 = АРп+н+п/лРп+м,1>1.

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

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

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

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

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

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

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

Л)-

пп+)

р ■ = ■

' »+7

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

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

£ 1, то очередь растет до бесконеч-

п

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

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

ч-4-ч.-

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

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

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

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

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

<< | >>
Источник: Т.П. Барановская, В.И. Лойко, М.И. Семенов, А.И. Трубилин. Информационные системы и технологии в экономике: Учебник. - 2-е изд., доп. и перераб. Под ред. В.И. Лойко. - М.: Финансы и статистика, - 416 с: ил.. 2005

Еще по теме 4.2.ОРГАНИЗАЦИЯОБСЛУЖИВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ:

  1. 14.2. Диспетчеризация и планирование вычислительных задач
  2. 4.3. ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ
  3. 10.2. Частные методики решения вычислительных задач
  4. 1.4.2. Особенности оперативных постановок информационных, вычислительных задач и их комплексов
  5. 7.2. Информационно-вычислительная сеть ФСГС РФ
  6. 6.1. ПОНЯТИЕ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
  7. 4.1. ОРГАНИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
  8. 4.5.5. КОНЦЕПЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С УПРАВЛЕНИЕМ ПОТОКОМ ДАННЫХ
  9. 4.5.3. КЛАССИФИКАЦИЯ АРХИТЕКТУР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
  10. 6.3. ТОПОЛОГИЯ ГЛОБАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ
  11. 4.6. УПРАВЛЕНИЕ РЕСУРСАМИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 4.6.1. ОДНОПРОЦЕССОРНЫЕ СИСТЕМЫ ОПЕРАТИВНОЙ ОБРАБОТКИ
  12. 18.5. Государственная пошлина за совершение уполномоченным федеральным органом исполнительной власти действий по официальной регистрации программы для электронных вычислительных машин, базы данных и топологии интегральной микросхем
  13. Размеры государственной пошлины за совершение уполномоченным федеральным органом исполнительной власти действий по официальной регистрации программы для электронных вычислительных машин, базы данных и топологии интегральной микросхемы
  14. Оперативная постановка задачи
  15. 3.2.1.4. Задачи исследования
  16. Задачи
  17. Задачи