Модели обслуживания вычислительных задач

 

При наличии пла­на организации вычислительного процесса основная проблема за­ключается в обслуживании заявки, которое характеризуется време­нем пребывания заявки в системе. Это время складывается из времени ожидания в очереди и времени обслуживания, представ­ляющего собой время обработки информации процессором на ос­нове принятой программы. Анализ процесса обслуживания заявки может быть выполнен на основе теории массового обслуживания. Тогда вычислительная система может быть представлена математи­ческой моделью системы массового обслуживания, которая харак­теризуется числом обслуживающих приборов, т. е. ЭВМ, дисципли­ной образования очереди, числом вычислительных задач в ИВЗ, дисциплиной обслуживания очереди с помощью диспетчера Д₂.

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

Другая модель системы характеризуется тем, что заявка на решение вычислительной задачи, поступившая в вычислительную систему, может ожидать и покидает ее только после полного об­служивания. В реальных вычислительных системах это оказывается возможным благодаря тому, что предусматриваются очереди O₁-О_N. Так как очередь не может быть не ограниченной, то данная система характеризуется числом заявок, ожидающих начала обслуживания. Возможны дополнительные ограничения на время ожидания, на время пребывания заявки в вычислительной системе и др. Существенное влияние как на параметры обслуживающей системы, так и на процесс ее анализа оказывает характер входящего потока заявок. Заявки от ИВЗ образуют во времени поток, который может иметь ограниченное или неограниченное число задач. Раз­личными могут быть и правила обслуживания заявок, находящихся в очереди. В соответствии с этим устанавливается некоторая дис­циплина обслуживания диспетчером Д₂. Естественной дисциплиной является дисциплина «первым пришел — первым обслужен». Воз­можен инверсный подход: «последним пришел — первым обслу­жен». Допускаются и случайные дисциплины обслуживания, когда заявки из очереди выбираются в произвольном порядке. В ряде случаев заявки обладают приоритетами. Это наиболее характерно для реальных задач ИС, в которых имеются информационные взаимосвязи. Тогда заявки имеют разную степень важности повремени исполнения и каждой заявке присваивается некоторый приоритетный индекс. Заявка с меньшим индексом имеет наиболь­ший приоритет. Для приоритетного обслуживания различают дис­циплины абсолютного, относительного и смешанного приоритетов, абсолютный предполагает прерывание обслуживания заявки при поступлении более приоритетной. При относительном приоритете обслуживание заявки продолжается, а после его завершения на обслуживание принимается поступившая приоритетная заявка, т. е. прерывание обслуживания не допускается. При смешанном приори­тете ЭВМ выбирает либо новую заявку, либо продолжает обслужи­вание предыдущей заявки. Критерием выбора может служить время обслуживания заявки.

В теории массового обслуживания под временем обслуживания понимают время, которое затрачивается на обслуживание одной заявки конкретным обслуживающим прибором (ЭВМ). В общем случае время обслуживания характеризуется определенным законом распределения F(t)=P(t_o6c<t), где Р(t_o6c<t) — вероятность того, что время обслуживания t_o6c<t. При t_o6c≤0 F(t)=0. В зависимости от закона распределения заявки на решение вычислительные задачи могут быть разделены на типы. В рамках одного и того же закона распределения заявки можно различать по среднему времени об­служивания. Время обслуживания реальной заявки на ЭВМ опреде­ляется числом операций, входящих в программу. Существенное влияние на это время оказывает и разветвленность программы. Для слабо разветвленных программ число выполняемых операций прак­тически для каждой задачи одинаково и может быть использована модель с постоянным временем обслуживания. При значительной разветвленной программы в зависимости от типа заявки ее ре­ализация может пойти по разным направлениям, время выполнения программы будет случайной величиной, т. е. реализуется модель с переменным временем обслуживания. Поведение вычислительной системы во времени может быть описано на основе исследования марковского процесса. Тогда удается оценить характеристики си­стемы массового обслуживания аналитическим путем.

Состояние системы массового обслуживания в некоторый мо­мент времени t определяется числом находящихся в ней заявок N(t), где N(t) — это случайная величина, во времени N(t) отображает слу­чайный процесс с дискретными состояниями. Положим, что система находится в состоянии k, если в ней имеется k заявок. Вероятность такого состояния обозначим P_k(t)=P[N(t)=k]. Для любого момента времени t . Переход из состояния i в состояние j опишем с помощью вероятности P_ij(t₁,t₂), если в момент t₁ система находилась в состоянии i, а к моменту t₂ переходит в состояние j.

При t₂-t₁=∆t и ∆t→0 P_ij(∆t)»f_ij∆t, где , где f_ij — плотность вероятности перехода. Рассмотрим последовательность переходов системы из состояния в состояние, пользуясь понятием Марковской цепи. Выберем интервал U в пределах t₁<U<t₂.

Тогда

где N — максимальное число заявок в системе. Полагая t₁=0, U=t, t₂=t+t, t>0, получим

.

Можно составить систему таких уравнений для определенна вероятностей Р_k(t).

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

Экспоненциальный закон времени обслуживания про­стейшего потока заявок. Простейшим называют стационарный ординарный поток без последействия. Обозначим параметр потока, т. е. интенсивность заявок, через l, l=const. Простейший поток описывается распределением Пуассона, в соответствии с которым вероятность возникновения k заявок за время t составляет

,

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

 

Среднее число заявок или матема­тическое ожидание числа заявок за время t определяется как

.

Соответственно дисперсия числа заявок за время t

.

Особенностью простейшего потока является то, что при объединении независимых простейших потоков с параметрами l₁, l₂ воз­никает суммарный простейший поток с параметром (l₁+l₂).

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

Экспоненциальному закону распределения времени обслужива­ния соответствует плотность распределения вероятности b(t)=me^-mt, где m — интенсивность обслуживания; здесь Т _обс — среднее время обслуживания одной заявки. Для составления уравнений, описывающих поведение системы массового обслужива­ния, рассмотрим граф переходов цепи Маркова для данной модели. На рис. 53 представлен размеченный граф состояний однолиней­ной системы обслуживания с очередью.

Отсутствие заявок соответ­ствует узлу 0, максимальное число заявок отображается узлом N. На дугах графа указаны плотности вероятности перехода системы из одного состояния в другое. При анализе процесса обработки необходимо установить вероятности состояний Р_k(t), для этого необходимо составить N+1 линейных дифференциальных уравне­ний с постоянными коэффициентами. Структура уравнений оди­накова: левая часть представляет собой производную вероятности состояния, а правая — включает члены, равные произведению пло­тности вероятности перехода на вероятность того состояния, из которого совершается переход. Число членов в правой части соот­ветствует числу стрелок, входящих и исходящих из рассматрива­емого состояния. Члены, соответствующие исходящим стрелкам, берутся со знаком минус, а соответствующие входящим — со зна­ком плюс. В общем виде уравнение, описывающее k -е состояние системы, может быть представлено как

В соответствии с рассмотренным графом для однолинейной системы обслуживания с очередью получаем следующую систему дифференциальных уравнений:

.

Условие нормировки вероятностей имеет вид

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

.

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

.

Вероятность существования в системе k заявок, из которых одна обслуживается ЭВМ, а остальные находятся в очереди, составит

.

При k>N вероятность k -го состояния Р_k=0. Это соответствует случаю переполнения системы, т. е. в очереди имеется N-1 заявок и одна заявка обслуживается ЭВМ (рис. 54). Таким образом, при полной загрузке системы, т. е. наличии в ней N заявок, вновь поступившее требование получает отказ. Поэтому полезно перейти к многолинейному обслуживанию, когда используется N обслужи­вающих приборов (ЭВМ).

Экспоненциальный закон времени обслуживания с по­терями простейшего потока заявок при S обслуживаю­щих приборах. В этом варианте вычислительная система не имеет возможности хранить очередь, поэтому заявки непосредственно через диспетчера Д₂ поступают на одну из S ЭВМ. Число заявок не может превышать 5, поэтому в случае загрузки всех ЭВМ вновь поступающее требование теряется, так как очередь не предусмотрена, а на обслуживание оно не может быть принято. Граф переходов S обслуживающей системы представлен на рис. 55, где в узлах графа указаны состояния «0, 1,..., S» — по числу заявок в системе, а дуги размечены плотностями вероятностей переходов из одного состояния в другое.

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

Условие нормировки вероятностей имеет вид . Решая данную систему уравнений, найдем вероятность пребывания вычис­лительной системы в k -м состоянии:

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

.

Выражение для вероятности Р_k известно в литературе как формула потерь Эрланга. Вероятность отсутствия заявок в системе

Отметим, что вероятность потери заявки может быть умень­шена за счет увеличения интенсивности обслуживания m и числа обслуживающих приборов S.

Для любой системы весьма важным показателем является загрузка , которая показывает среднее число заявок, поступающих в вычислительную систему за среднее время об­служивания одной заявки одной ЭВМ. Стационарный режим имеет место в системе, если r<S. Наиболее распространенным вариантом реализации вычислительной системы является много­линейное обслуживание с очередью, к рассмотрению которого и перейдем.

Экспоненциальный закон времени обслуживания про­стейшего потока заявок при S обслуживающих приборах. В этом варианте обслуживания вычислительная система включает S обслуживающих приборов (ЭВМ) и имеет очередь для поступа­ющих заявок с числом мест L. При наличии хотя бы одной свобод­ной ЭВМ поступившая заявка сразу принимается на обслуживание. Если все ЭВМ заняты, то она становится в очередь. Естественной дисциплиной обслуживания является «первым пришел — первым обслужен». По числу заявок система может иметь состояния: «0,1,.... S+L». Граф переходов системы представлен на рис. 56.

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

.

Условие нормировки вероятностей имеет вид

Решая систему уравнений, определим вероятность нахождения вычислительной системы в k -м состоянии

.

Соответственно вероятность состояния (S+n)

,

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

.

Отказ в приеме на обслуживание заявки возникает в случае, когда заняты все ЭВМ и в очереди находится L заявок, т. е.

.

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

Организация очереди в вычислительной системе требует знания ее средней длины. Установим эту величину из условия, что очередь возникает, когда заняты все обслуживающие приборы и в системе имеет место количество заявок от S+1 до S+L. Поэтому

.

Подставляя соответствующие значения вероятностей P_k получим

.

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

.

В этом выражении первая сумма включает вероятности состоя­ний обслуживающей системы от S до S+L, а вторая сумма — веро­ятности обслуживания от 0 до r заявок с помощью S обслужива­ющих приборов за время t. Среднее время ожидания

.

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

.

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

.

Потери заявок возникают с вероятностью

.

Соответственно среднее время пребывания заявки в вычисли­тельной системе составит

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

 

2.5.2. Модели планирования вычислительного процесса

 

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

Рассмотрим модель планирования вычислительного процесса. Будем считать, что в целом для ряда вычислительных задач необходимым является выполнение определенной номенклатуры типовых вычислительных работ J₁ — J_y, для которых необходимо предоставление ресурсов R­₁ — R_у. Связь между работами и ре­сурсами можно установить в виде матрицы трудоемкости работ. Элементами этой матрицы служат параметры t_ij, которые в зависимости от характера требуемого ресурса имеют размерность числа единиц потребной памяти либо единиц времени, необхо­димых для выполнения соответствующей работы. Тогда вводимая матрица имеет вид

Имея данную матрицу, при составлении плана организации вычислительного процесса необходимо указать очередность выпол­нения работы отдельными устройствами вычислительной системы, т. е. последовательность использования ресурсов R₁ — R_ν.

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

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

1) для любого устройства ВС (фазы обработки данных) каждая последующая работа не может начаться до окончания предыдущей;

2) каждое устройство на данной фазе может выполнять только одну информационно-вычислительную работу;

3) начавшаяся информационно-вычислительная работа не долж­на прерываться до полного ее завершения.

Если в процессе обработки выделить g фаз, на каждой из кото­рых используется одно вычислительное устройство, то решение данной задачи путем перебора требует рассмотрения (N!)^g вариан­тов, где N — число заявок на решение вычислительных задач в вы­числительной системе. Джонсоном получен эффективный алгоритм для g =2, требующий перебора N(N+1)/2 вариантов. Частное реше­ние задачи Джонсона соответствует случаю g=l. По сути, это однолинейная система обслуживания (S=1), в которой имеется очередь заявок. Требуется установить порядок выборки этих заявок Диспетчером Д₂ для обработки в ЭВМ. Критерием может быть минимум времени пребывания заявки в вычислительной системе, включая и время ожидания ее в очереди. Алгоритм выборки заявок из очереди по данному критерию соответствует их расположению в порядке убывания времени пребывания в вычислительной системе. Отметим, что решение задачи Джонсона при g=1 имеет слабое фактическое применение для вычислительной системы. Обычно при обработке данных используется более одного устройства.

Отметим, что решение задачи Джонсона при g>2 означает практически сведение этой задачи к двухфазной. В частности, для g=3 получаем матрицу трудоемкостей, содержащую три столбца. Эту матрицу преобразуем в двухстолбцовую матрицу путем попарного сложения элементов трудоемкостей первого и второго, второго и третьего столбцов. Если ограничения, указанные Джонсоном, не выполняются, то точного решения задачи планиро­вания вычислительного процесса не имеется, и переходят к эв­ристическим алгоритмам планирования информационно-вычис­лительных работ. В основе эвристических алгоритмов лежит выделение фазы работ с наибольшей суммарной продолжитель­ностью. Данная фаза является приоритетной при запуске работ, которые располагаются в порядке убывания величин трудоем­костей их выполнения. Оценка эффективности эвристических методов планирования осуществляется по степени близости суммарного времени выполнения работ к минимально возможному времени.

Планирование по критерию максимума загрузки средств обработ­ки. Если последовательность использования вычислительных устройств в системе при решении задач неизвестна, то планирование ведут на основе критерия максимальной загрузки устройств. В этом случае из J₁...J_g отбирается совокупность работ, которые могут выполняться совместно на базе имеющихся ресурсов. По мере окончания хотя бы одной работы из этой совокупности выполнения заеняется одной из работ, находящихся в ожидании. Для определения составов совокупностей работ преобразуем матрицу трудоемкостей в матрицу загрузки устройств. Введенные ранее ресурсы R₁...R_g принадлежат некоторым устройствам У₁...У_g. Тогда матрица загрузки может быть представлена в виде

где элемент матрицы З_ij показывает загрузку j- гo устройства i- й работой; ; — потребность i -й работы в использовании j -гo ресурса. В каждой строке матрицы выделим элемент З_ij, с наибольшим значением.

Тогда значение j определит номер потока, к которому будет отнесена работа, соответствующая данной строке матрицы. Число потоков будет равно числу устройств, т. е. g. Если в первой строке наибольшее значение имеет элемент З₁₂, то работу J₂, относим к потоку П₂. Соответственно если во второй строке наибольшее значение имеет элемент З_2g, то работу J₂ относим к потоку П_g. При разбиении работ на потоки примем ограничение, что каждая из них может быть отнесена только к одному потоку. Каждый поток включает тогда некоторую последовательность работ. Сформиро­вав g потоков, можно перейти к составлению совокупностей работ. Совокупности работ, поступающих на обработку, образуются пу­тем выборки их из потоков П₁...П_g. В начальный момент времени формируется первая совокупность, включающая g работ, взятых по одной из каждого потока. Эти работы поступают на соответст­вующие устройства при условии, что они не перегружают некото­рый общий ресурс. В качестве такого ресурса может выступать емкость оперативной памяти, поэтому для каждого момента форм­ирования совокупности работ должно соблюдаться ограничение: сумма емкостей памяти, занимаемых работами, включенными в со­вокупность, не должна превышать общей емкости памяти. Пусть в начальный момент совокупность работ имеет вид C₁={J₃, J₁,…,J₂}. Эта совокупность содержит g членов, из которых, как раньше приняли, работа J₁ принадлежит потоку П₂, а работа J₂ прянадлежит потоку П_g. Ограничение по оперативной памяти примет вид V₃+ V₁ +... + V_i+... + V₂≤ V, где V — общий объем оперативной памяти; V_i — объем оперативной памяти, необходимый для работы i.

Если в некоторый момент времени завершается работа J₁, то на ее место в совокупность работ включается следующая работа из того же потока П₂. При этом опять проверяется ограничение.

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

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