Модели СП на базе СМО

Исследование вероятностно-временных характеристик процесса функционирования СП аналитическим методом можно провести с использованием моделей систем массового обслуживания (СМО), если они яв­ляются марковскими или сводятся к марковским, напри­мер, методом вложенных цепей Маркова. В последнее время при создании моделей ВС все чаще стали приме­няться сетевые модели СМО, допускающие при опре­деленных условиях декомпозицию сети на отдельные СМО. Методы теории СМО являются подходящими для ана­лиза ТС и ПО СП по следующим причинам: 1) функцио­нирование СП наиболее естественно описывается на язы­ке очередей (очереди заданий, процессов к ресурсам, процессов к обрабатывающим модулям, очереди к секци­ям оперативной памяти). Напомним, что задание представляет собой со­вокупность действий для выполнения вычислительной системой некоторой работы, предъявляемой пользовате­лем; 2) показатели эффективности выражаются через основные показатели СМО — через время нахождения за­явки в системе, через среднюю производительность уст­ройства обработки, среднюю длину очередей, среднее время ожидания заявок в очереди. Основные элементы СМО показаны на рис. 2.4. Заявки поступают на обслу­живающее устройство. Если в момент поступления заявки обслуживающее устройство занято, то заявка либо ставится в очередь к нему, где ожидает начала обслужива­ние с ожиданием), либо теряется (СМО с потерями). Выбор заявки на обслуживание в какой-то момент времени производится в соответствии с некоторым правилом, которое называется дисциплиной обслуживания. Далее выполняется обслуживание заявки, после чего заявка покидает систему. Выходящий поток обслуженных заявок может оказаться весьма важным в тех случаях, когда он является входящим для другой СМО.

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

Рис. 2.4. Структура системы массового обслуживания

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

1. Первое устройство (узел) прекращает генерировать заявки и хранит уже обслуженную им (сгенерированную) заявку до тех пор, пока не освободится место в накопи­теле, т.е. пока второй узел не примет из ЗУ к обслужи­ванию очередную заявку. Это система с блокировкой, она рассматривается как двухфазная СМО с накопите­лем конечной емкости и потоком заявок с интенсивностью их поступления, равной бесконечности.

2. Заявка, об­служенная первым узлом, теряется, а сам первый узел сразу же начинает обслуживать (генерировать) следующую заявку. Такая дисциплина приводит к СМО с одним обслуживающим прибором, одним потоком заявок и ко­нечным накопителем, известной в теории СМО как си­стема с потерями (рис. 2.4).

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

Рис. 2.5. Двухфазная модель

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

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

Рис. 2.6. Замкнутая сеть из последовательно соеди­ненных обслуживающих устройств

При экспоненциальной длительности обслуживания среднее время ответа i-й СМО складывается из средней длительности обслуживания вновь поступившей заявки и средней длительности обслуживания всех заявок, нахо­дящихся в i-йСМО в момент поступления в нее новой заявки. При таких условиях удается получить замкнутую систему уравнений, связывающую между собой среднее время ответа, среднее время обслуживания, среднюю длину очереди для i-й СМО и пропускную способность сети для заданного значения N. Решая эти уравнения рекуррентно для N i=1, 2, ..., находят интересующие сред­ние показатели сети, рассматривая последнюю, как со­стоящую из совокупности независимых СМО. Замкнуты­ми экспоненциальными сетями СМО описывают модели мультипроцессорных систем с общей памятью и мульти-машинных систем с блоками локальной памяти, струк­туры которых используются для построения МПУ СПИ. Замкнутость сети не противоречит тому, что сообщения (заявки) поступают в систему и покидают ее, так как в условиях высокой загруженности, представляющих наибольший практический интерес, в ВС циркулирует конечное число заданий.

Пример использования такой модели для расчета среднего времени задержки пакетов при обработке их в мультипроцессорном ЦК показан в [3].Математическая модель построена для СП, представленного в виде мультипроцессорной системы, содержащей канальные модули КМ1—КМ3, обрабатывающие модули ОМ1—ОМi, секции ОПП СОП1—СОПi, модуль комплексирования — полнодоступный матричный коммутатор (МК). Рассматривается вариант фиксиро­ванного размещения программных модулей в локальной памяти ОМ.

Каждый из КМ обслуживает один или несколько дис­кретных каналов. На приеме КМ производит накопление блоков информации по каждому из каналов и их пе­ресылку в режиме прямого доступа в отведенные буфе­ры ОПП. На передаче КМ осуществляет поблочную пересылку информации в режиме прямого доступа из бу­феров ОПП в локальную память КМ с последующей по­битовой передачей информации в исходящие КС. ОМ реализует логическую обработку информации, записан­ной в ОПП, согласно функциональным алгоритмам МПУ СПИ. ОПП состоит из секций оперативной памяти (СОП) с независимыми трактами доступа со стороны КМ и ОМ через МК.

Процесс обработки информационных кадров (ИК) в СП представлен в виде системы технологических цепо­чек (ТЦ). Каждый ИК, записанный КМ в ОПП, ге­нерирует задание, которое обрабатывается на ОМ при­кладными процессами, реализующими заданные функ­циональные алгоритмы, по некоторой ТЦ. Каждая ТЦ определяет последовательность обработки ИК и пакетов и задается управляющей информацией, содержащейся в их заголовках. Например, в i-юТЦ (рис. 2.7) входят процессы приема ИК, реализации процедуры РШ1Х на приеме, протокола Х.25 на передаче, адаптивной марцрутизации, реализации процедуры НDLC на передаче, передачи ИК. Считается, что в ТЦ отсутствуют петли. Одновременно, если позволяет число ОМ, может об­рабатываться несколько заданий как различными про­цессами, так и копиями одного процесса. В систему про­цесса 1-го типа (рис. 2.7) входят одна или несколько ко­пий процессов, способных параллельно обрабатывать различные задания по одному и тому же алгоритму и очередь заданий.

Рис. 2.7. Система ТЦ обработки информационных кадров в СП ЦКП

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

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

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

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