Простейшая система массового обслуживания.

Рассмотрим систему массового обслуживания (например, вычислительную систему), схема которой показана на рисунке 2 9а. Система имеет входной поток заданий, и пока она занята выполнением очередного задания, она не может ввести следующее задание.

Рассмотрим множество условий и событий, характеризующих систему.

Условия:

P₁ - задание ждет обработки;

Р₂ - задание обрабатывается;

Рз - процессор свободен;

Р₄ - задание ожидает вывода.

События:

t₁ - задание помещается во входную очередь;

t₂- начало выполнения задания;

t₃- конец выполнения задания;

t₄- задание выводится.

Сеть Петри, моделирующая рассматриваемую систему, показананарисунке 2.9б.

Поясним работу данной сети. Показанная на рисунке начальная маркировка М₀ = [0,0,1,01 соответствует состоянию, когда система свободна и заявки на обслуживание отсутствуют. При срабатывании перехода t₁(от внешнего источника) поступает задание и получается маркировка М, = [1,0,1,0]. При этом может сработать переход t₂, что означает начало обслуживания задания и приводит к маркировке М₂ = [0.1,0,0]. Затем может сработать переход t₃, что означает окончание обслуживания задания и освобождение системы, т.е. переход к маркировке М₃ = [0,0,1,1]. Переходы t₁ и t₄ могут работать независимо от t₂ и t₃, моделируя поступление и вывод заданий. Сеть Петри, моделирующая последовательность обслуживающих устройств, соединенных в очередь типа FIFO, приведена в задаче 2 раздела 4.1.

2. Двухпоточная СМО.Пусть теперь СМО выполняет задания, поступающие от двух источников и находящиеся в двух очередях. Вывод обработанных заданий осуществляется одним потоком. В этом случае модель системы имеет вид, показанный на рисунке 2.10.

Здесь введены дополнительные условия:

Р₅ - задание из второй очереди ждет обработки;

Р₆- задание из второй очереди обрабатывается.

Также введены дополнительные события:

t₅- задание помещается во вторую очередь;

t₆- начало выполнения задания из второй очереди;

t₇- завершение выполнения задания из второй очереди.

Как видно, здесь имеет место конфликт. Одновременно может выполняться только одно задание из любой очереди.

В то же время, если µ₃=2 (это соответствует двухпроцессорной системе), то возможно одновременное выполнение двух заданий из обеих очередей в любой комбинации.

3. Конвейер.В качестве следующего примера рассмотрим схему управления асинхронной ЭВМ с конвейерной обработкой.

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

А = ±М_А* 2^±Р^a,

В = ±М_В* 2^±Р^b.

Здесь ,

М_A, Мв - мантиссы чисел А и В,

р_а, р_b - двоичные порядки этих чисел.

Требуется получить результат

С = А + В = ±М_С* 2^±Р^c

Как известно, эта операция состоит из следующих этапов:

СП - сравнение порядков;

ВП - выравнивание порядков;

СМ - сложение мантисс;

HP - нормализация результата.

Каждый из этих этапов выполняется отдельным функциональным устройством в устройстве конвейерной обработки. Связь между функциональными устройствами и синхронизация их работы осуществляется с помощью пары регистров: входного Рг_; и выходного Рг₀

Выпишем для i-гo функционального устройства условия:

р_i₁ - входной регистр свободен;

p_i₂ - входной регистр заполнен;

р_i₃ - блок занят;

p_i₄ - выходной регистр свободен;

p_i₅ - выходной регистр заполнен;

p_i₆ - пересылка в следующий блок возможна, и события:

t_i₁ - начало работы i-гo блока;

t_i₂- завершение работы i-гo блока;

t_i₃ - начало пересылки в (i+1)-ыя блок;

t_i₄ - завершение пересылки в (i+1)-ый блок.

При этом модель i-го блока конвейера при начальной маркировке M_Oi = [0,l,0,1,0,0] примет вид, показанный на рисунке 2.12.

Предоставляем читателям самостоятельно проследит последовательность срабатывания переходов и получаемые приэтом маркировки.

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

Пусть необходимо смоделировать фрагмент вычислительной системы, в которой осуществляются обмены междутремя накопителями на магнитных дисках D_1, D₂, D₃ и центральным процессором ЦП через два канала С₁, и С₂. При этом требуется, чтобы D₁ использовал канал С₁; D₂ - канал С₂, D₃- оба канала С₁ и С₂ (рисунок 2.13).

Обыкновенная сеть Петри PN для моделирования этой системы показана на рисунке 2.14.

Позиции p_d₁ , p_d₂ , p_d₃ определяют, свободен или занят, соответствующий дисковод D₁, D₂, D₃, позиции р_с1, р_с2 соответственно- свободен или занят соответствующий канал C₁ и С₂. Позиции р₁и р₂ - выполнение заданий парами D₁C₁ и D₂С₂ позиции р₃₁ и p₃₂ -выполнение задания парами D₃ С₁; и D₃C₂.

Каждый из переходов t,, t₂, t₃, t₄ при срабатывании определяет один из четырех возможных варианту обслуживания задания. При построении дерева маркировок необходимо дать возможность сработать каждому из них.

Переходы t₅, t₆, t₇, t₈ моделируют завершение выполнения задания по каждому из рассмотренных вариантов.

Рассмотренную сеть можно значительно упростить, еслииспользовать формализм раскрашенных сетей Петри CPN. В этом случае она примет вид, показанный на рисунке 2.15.

Здесь позиция p_d определяет наличие свободных дисководов, а позиция р_с - наличие свободных каналов. Введем графическое и буквенное обозначение ресурсов, используемых данной сети:

◦ - (d₁); * - (d₂); + - (d₃) - свободные дисководы;

× - (с₁); × - (с₂) - свободные каналы;

•- е - поступившие/выполненные заявки.

Кроме того, необходимо ввести дополнительные фишки длязапоминания предыдущих состояний сети (на рисунке не указаны):

m₁ - занят дисковод D₁ и канал С₁;

m₂ - занят дисковод D₂ и канал C₂;

m₃ - занят дисковод Ds и канал С₁;

т₄ - занят дисковод Ds и канал С₂;

Правила срабатывания переходов t₁, t₂, t₃ задаются таблицей 2.1.

Приведем теперь формальное описание данной CPN в нотации К. Йенсена (см. п. 2.2).

• Множества цветов:

type colorD = (d1,d.2,d3);

type colorC - (c1, с2);

colorE - (e);

type colorM ={ml,m2,m3,in4).

• Цветовые переменные:

Var d:D; Var c:C; Var x:E; Var m :M.

• Множество позиций:

type P = (p0,pl_}p2,p3,pd,pc);

переменная типа позиции:

Var p:P.

• Множество переходов:
typeT = (t0,t1,t2,t3,t4);
переменная типа перехода:
Var t : T.

• Множество дуг: А = AP U AT;
type AP = (al,a3,a5,a7,a10,a11);
type AT = (a0,a2,a4,а6,а8,а9);
переменные типа дуги:

var a1,a3_ta5,a7,a10,a11: AP;

var a0,a2,a4,a6,a8,a9: AT,

где типы АР и AT описаны, соответственно, выражениями (2.14) и (2.15).

• Цветовая функция

• Выражения на дугах Е(а) задаются таблицей 2.2.

· Блокировочная функция истинна для всех переходов:
G(t)=true.

· Функция инициализации I(p), задающая начальную маркировку т₀(р₀)=(1`е); т₀(р1) = (Ø); т_о(р₂) = (Ø); т₀(p₃) = (Ø); т₀(p_d) = (1`d1,1`d2,1` d3); т₀(р_с) = (1`с1,1`с2).

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

5. Задача об обедающих мудрецах.Введение параллелизма : полезно только в том случае, когда компоненты процессов могут взаимодействовать при решении задачи. Управление взаимодействующими процессами называют синхронизацией.

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

Эта задача была предложена Э. Дейкстрой в 1968 году в статье о параллельных вычислениях, где он впервые ввел понятие "семафора". С тex пор она служит своеобразным тестом для методов решения задач распараллеливания.

Имеется N китайских мудрецов, которые то гуляют по парку обедают. Каждый из них действует совершенно независимо. Проголодавшись, он идет в столовую, садится на свободный стул за круглый стол, на котором стоит блюдо с рисом берет две палочки и ест. Но палочек всего N. Если свободных палочек нет, то мудрец ждет, когда освободятся соседние палочки. Насытившись, он кладет палочки на место уходит. На рисунке 2.16 показана схема столовой для N = 5 ,

Обозначим состояния, относящиеся к произвольному i-му мудрецу (i = 1,...,N):

Mi - i-й мудрец гуляет;

E_i - i-й мудрец ест;

С_k - k-я палочка свободна;

С_li - i-й мудрец держит левую палочку;

С₂_i - i-й мудрец держит правую палочку.

Рассмотрим возможные события:

t_i₁- мудрец начинает есть;

t_i₂ - мудрец уходит гулять и освобождает палочки;

t_i₃ - мудрец взял левую палочку;

t_i₄ - мудрец взял правую палочку.

Тогда для отдельного i-го мудреца имеем обыкновенную сеть Петри (рис. 2.17).

Из рисунка видно, что мудрецы взаимно связаны орудиями питания, т.е. из-за ресурса C_k (палочек) имеется конкуренция.

В соответствии с расположением мест за обеденным столом (рис. 2.16) сети Петри для 1-го и N–го мудрецов должны соединяться. При нумерации мест по часовой стрелке правая палочка 1-го мудреца является левой для N -го. Таким образом, полный граф PN для данного примера представляет собой кольцо,образованное сетями для отдельных мудрецов.

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

Задача о мудрецах может быть смоделирована с помощью раскрашенных сетей Петри, она подробно разобрана в книге [10]. Эта задача предлагается в качестве одного из вариантов задания в лабораторных работах.