Процесс обработки информации

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

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

Источник вычислительных задач формирует входной поток заявок на их решение. С помощью диспетчера реализуется опознавание поступившей заявки и постановка ее в очереди, которая ожидает начала обслуживания в зависимости от требуемой информационной нагрузки на ячейках оперативной памяти. Заявки отображаются кодами и взаимосвязи между задачами. Диспетчер выбирает из очередей заявку на обслуживание, т.е. передает вычислительную задачу для обработки на ЭВМ. Обслуживание обычно осуществляется в соответствии с принятым планом организации вычислительного процесса. Процесс выбора заявки из множества называется диспетчированием Обычно выбирается заявка, имеющая преимущественное право на обслуживание. При этом инициируется соответствующая программа, реализующая вычислительный алгоритм решения требуемой задачи. При отсутствии заявок в очередях диспетчер Д₂ переключает процессоры ЭВМ в состояние ожидания. В общем случае в вычислительной системе реализуется многолинейное обслуживание за счет наличия ЭВМ ₁...ЭВМ _s. Можно считать, что процесс обслуживания осуществляется в два этапа. Сначала заявки ставятся в очередь с помощью диспетчера Д₁, а на следующем этапе они обслуживаются путем выбора заявок из очереди на основе работы диспетчера Д₂. Диспетчеры реализуются программным путем, представляя собой управляющие программы. При появлении заявки работа процессора прерывается, заявка вводится в вычислительную систему, далее передается управление диспетчеру, который определяет последовательность обслуживания поступивших заявок с учетом имеющихся в ЭВМ. На логическом уровне могут быть заданы правила диспетчирования, т.е. дисциплина обслуживания. При разработке модели обработки данных удобно предположить, что все операции по планированию вычислительного процесса, определению приоритетов, передаче заявок от одной ЭВМ к другой выполняет диспетчер, а сам процесс обслуживания реализуется набором ЭВМ.

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

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

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

Состояние системы массового обслуживания в некоторый момент времени t определяется числом находящихся в ней заявок N(t). N(t) - это случайная величина, во времени N(t) отображает случайный процесс с дискретными состояниями. Положим, что система находится в состоянии k, если в ней имеется k заявок. Вероятность такого состояния обозначим P_k(t)=P[N(t)=k]. Для любого момента времени tS_kP_k(t)= 1. Переход из состояния i в состояние j опишем с помощью вероятности P_ij(t₁, t₂), если в момент t₁ система находилась в состоянии i, а к моменту t₂ переходит в состояние j. При t₁- t₂= Dt и Dt® 0: P_ij(Dt)» f_ij Dt, где f_ij = lim|_D_t_®₀[P_ij(Dt)/Dt] - плотность вероятности перехода. Рассмотрим последовательность переходов системы из состояния в состояние, пользуясь понятием марковской цепи. Выберем интервал U в пределах t₁ < U< t₂:

Тогда P_ij(t₁, t₂)=S_r₌₀^N P_ir(t₁, U) P_rj(U, t₂), 0 £ i, j£ N,

где N - максимальное число заявок в системе. Полагая t₁= 0; U = t; t₂= t + t, t > 0, получим P_ij( 0 ,t+t) = S_r₌₀^N P_ir( 0 ,t)P_rj(t, t+t),

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

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

Экспоненциальный закон времени обслуживания простейшего потока заявок. Простейшим называют стационарный ординарный поток без последействия. Обозначим параметр потока т.е. интенсивность заявок, через l: l= const. Простейший поток описывается распределением Пуассона, в соответствии с которым вероятность возникновения k заявок за время t составляет P(k, t)=(lt)^k е^-^l^t(k!)^-1; где l - интенсивность потока заявок, т.е. количество заявок, поступающих за единицу времени. Среднее число заявок или математическое ожидание числа заявок за время t определяется как

M = S_k₌₀^¥ k(lt)^k е^-^l^t(k!)^-1= lt.

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

D = S_k₌₀^¥k²P(k, t)-lt)²=lt.

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

Экспоненциальному закону распределения времени обслуживания соответствует плотность распределения вероятности b(t)= m е^-^m^t, где m - интенсивность обслуживания: m=Т_обс^-1, здесь Т_обс - среднее время обслуживания одной заявки. Для составления уравнений, описывающих поведение системы массового обслуживания, рассмотрим граф переходов цепи Маркова для данной модели. Отсутствие заявок соответствует узлу 0, максимальное число заявок отображается узлом N. На дугах графа указаны плотности вероятности перехода системы из одного состояния в другое. При анализе процесса обработки необходимо установить вероятности состояний P_k(t), для этого необходимо составить N+ 1 линейных дифференциальных уравнений с постоянными коэффициентами. Структура уравнений одинакова: левая часть представляет собой производную вероятности состояния, а правая - включает члены, равные произведению плотности вероятности перехода на вероятность того состояния, из которого совершается переход. Число членов в правой части соответствует числу стрелок, входящих и исходящих из рассматриваемого состояния. Члены, соответствующие исходящим стрелкам, берутся со знаком минус, а соответствующие входящим - со знаком плюс. В общем виде уравнение, описывающее k - e состояние системы, может быть представлено как

dP_k(t)/dt = - S_j₌₀^N f_kj P_k(t)+ S_i₌₀^N f_kj P_i(t).

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

dP₀(t)/dt= -lP₀(t)+mP₁(t);

...

dP_k(t)/dt= -(l+m)P_k(t)+lP_k_-1(t)+mP_k₊₁(t); k= 1 ,..., N;

...

dP_N(t)/dt= -mP_N(t)+lP_N_-1(t).

Условие нормировки вероятностей имеет вид S_k₌₀^N P_k(t) = 1.

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

0 = -lP₀(t)+mP₁(t);

...

0 = -(l+m)P_k(t)+lP_k_-1(t)+mP_k₊₁(t); k= 1 ,..., N;

...

0 = -mP_N(t)+lP_N_-1(t).

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

P₀(t)=( 1 -r)( 1 -r^N⁺¹)^-1; r=l/m.

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

P_k(t)=( 1 -r) r^k ( 1 -r^N⁺¹)^-1; 0 £ k £ N.

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

Экспоненциальный закон времени обслуживания с потерями простейшего потока заявок при S обслуживающих приборов. В этом варианте вычислительная система не имеет возможности хранить очередь, поэтому заявки непосредственно через диспетчера Д₂ поступают на одну из S ЭВМ. Число заявок не может превышать S, поэтому в случае загрузки всех ЭВМ вновь поступающее требование теряется, так как очередь не предусмотрена, а на обслуживание оно не может быть принято. На графе переходов S обслуживающей системы в узлах 0 ,..., S - по числу заявок в системе, и дуги размечены плотностями вероятностей переходов из одного состояния в другое. Исходя из этого графа, для установившегося режима запишем алгебраическую систему уравнений в виде:

0 = -lP₀(t)+mP₁(t);

...

0 = -(l+ km)P_k(t)+lP_k_-1(t)+ (k+ 1 )mP_k₊₁(t); k= 1 ,..., S;

...

0 = - SmP_S(t)+lP_S_-1(t).

Условие нормировки вероятностей имеет вид S_k₌₀^S P_k(t) = 1. Решая данную систему уравнений, найдем вероятность пребывания вычислительной системы в k - м состоянии:

P_k= (r^k(k!)^-1)[S_j=1^S r^j(j!)^-1]^-1; k = 0 ,..., S.

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

P_пот= P_S= (r^S(S!)^-1)[S_j=1^S r^j(j!)^-1]^-1.

Выражение для вероятности P_k известно в литературе как формула потерь Эрланга. Вероятность отсутствия заявок в системе P₀=[S_j r^j(j!)^-1]^-1.

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

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

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

0 = -lP₀(t)+mP₁(t);

...

0 = -(l+ km)P_k(t)+lP_k_-1(t)+ (k+ 1 )mP_k₊₁(t); k= 1 ,..., S;

...

0 = - (l+Sm)P_S(t)+lP_S_-1(t)+ SmP_S₊₁(t);

...

0 = -(l+ Sm)P_S₊_n(t)+lP_S₊_n_-1(t)+ SmP_S₊_n₊₁(t); n= 1 ,..., L- 1;

...

0 = - P_S₊_L(t)+lP_S₊_L_-1(t).

Условие нормировки вероятностей имеет вид S_k₌₀^S P_k + S_n₌₁^L P_S₊_n = 1.

Решая систему уравнений, определим вероятность нахождения вычислительной системы в k - м состоянии P_k= P₀ r^k(k!)^-1; k= 0 ,..., S.

Соответственно вероятность состояния (S+n): P_S₊_n=P_S(r/S)ⁿ(k!)^-1; n= 0 ,...,L.

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

Р₀=[ 1 +S_k=1^S r^k(k!)^-1+ r^S(S!)^-1S_n=1^L (r/S)ⁿ]^-1.

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

P_пот = P_S+L= P_S(r/S)^L= r^S+LS^L(S!)^-1[ 1 +S_k=1^S r^k(k!)^-1+ r^S(S!)^-1S_n=1^L (r/S)ⁿ]^-1.

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

Организация очереди в вычислительной системе требует знания ее средней длины. Установим эту величину из условия, что очередь возникает, когда заняты все обслуживающие приборы, и в системе имеет место количество заявок от S+ 1 до S+L. Поэтому ` l = S_k₌_S₊₁^S⁺^L kP_k. Подставляя соответствующие значения вероятностей P_k, получим

` l = P_S r [ 1 -(r/S)^L(S+ 1 -r)]S^-1( 1 -r/S)^-1.

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

P[Т_ож > t] = S_r₌₀^L(l/(Sm))^rP_S S_k₌₀^r(Smt)^ke^-^S^m^t (k!)^-1.

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

`T_ож= P_S [ 1 -(r/S)^L(S+ 1 -r)]S^-1m^-1( 1 -r/S)^-2.

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

`T = `T_ож + [ 1 -(r/S)^LP_S]/m.

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

P_k =r^k( 1 -r)( 1 -r^L⁺²)^-1; k= 0 ,...,L- 1.

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

P_пот = [ 1 -r^L⁺¹] [ 1 -r^L⁺²]^-1.

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

`T=[m( 1 -r)]^-1-L r^L[m( 1 -r)^L]^-1.

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