Реализация механизма мониторов. Хоара в мультипрограммных системах. Задача о спящем парикмахере

     

     Рисунок 2 

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

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

4. Условные  переменные

     Условная  переменная(conditional variable) – символизирует ожидание потоком, выполняющим метод монитора, наступления некоторого события.

     Существует  три операции:

1. Wait – выполняется поток, который хочет подождать наступления события.  Снимает блокировку монитора, после чего другой поток может войти в него; ожидает, пока какой-либо другой поток не подаст условный сигнал.
2. Signal – выполняется поток, сигнализирующём о наступлении события. Пробуждает максимум один ожидающий поток; если отсутствуют потоки, ожидающие события, информация о приходе сигнала теряется.
3. Broadcast – также выполняется потоком, сигнализирующем о наступлении события. Пробуждает все ожидающие события потоки.

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

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

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

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

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

5. Пример  монитора Хоара

     Пример  монитора Хоара:

     Monitor Resource;

     condition free;                     {условие – свободный}

     Var busy : Boolean;

     Procedure Request;              {запрос}

     Begin

           If busy then WAIT(free);

           busy:=true;

           TakeOff;                         {выдать ресурс}

     End;

     Procedure Release;

     Begin

           TakeOn;                          {взять ресурс}

           busy:=false;

           SIGNAL(free)

     End;

     Begin

           busy:=false;

     End

     Единственный  ресурс динамически запрашивается  и освобождается процессами, которые  обращаются к процедурам REQUEST и RELEASE. Если процесс обращается к REQUEST в тот момент, когда ресурс используется, то значение busy=true, и REQUEST выполнит операцию монитора WAIT(free). Обратившийся процесс помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free.

     Когда процесс, использующий ресурс, обращается к RELEASE, операция монитора SIGNAL(free) деблокирует процесс из начала очереди. Он готов сразу после операции WAIT(free), которая его и блокировала, возобновить выполнение процедуры REQUEST.

     Если  же SIGNAL(free) выполняется в то время, когда нет ожидающего условия free процесса, то никакие действия не выполняются.

     Доступ  к разделяемым переменным ограничен  телом монитора, а мониторы входят в состав ядра ОС, поэтому разделяемые  переменные становятся системными переменными, что автоматически исключает критические интервалы (два процесса никогда не смогут получить одновременного доступа к разделяемым переменным).

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

6. Преимущества  монитора

     Преимущества  монитора перед другими средствами синхронизации:

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

     Если  несколько процессов совместно  используют ресурс и работают с ним  совершенно одинаково, то в мониторе нужна только одна процедура, в то время как решение с семафорами требует наличия КС в каждом процессе.

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

 

3. Задача  о спящем парикмахере

     Задача  о парикмахере, который спит на работе, является аллегорической демонстрацией подсистемы управления процессами и была сформулирована Дейкстрой в 1968 г.

1. Постановка  задачи

     Парикмахерская  состоит из комнаты ожидания О  и комнаты, в которой стоит кресло парикмахера З. Через двери Д можно попасть из комнаты О в комнату З, а из комнаты З на улицу. Если парикмахер заходит в комнату ожидания и никого там не находит, то он идет спать. Если клиент заходит в парикмахерскую и находит спящего парикмахера, то он его будит. В комнате ожидания число мест ограничено и равно N.

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

     

    Рисунок 3 – Задача о спящем парикмахере 

2. Реализация  задачи с помощью  сетей Петри

    Сети  Петри — математический аппарат  для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

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

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

     Общий принцип работы сетей Петри:

1. Переходы
2. Места (зал ожидания, место у парикмахера)

    Состояние сети определяется её разметкой. Места, из которых ведут дуги на данный переход, называются входными местами  для данного перехода. Места, из которых выходят дуги, называются выходными. Выполнение условия обозначается на схеме сети изменением её разметки, т.е. помещением в данное место сети n фишек, где n- это емкость условия.

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

    

     Рисунок 4 - Реализация алгоритма с помощью сетей Петри

3. Листинг программы

     Для реализации на языке высокого уровня необходимо создать N потоков, которые будут  моделировать действия клиентов. В решении  предлагается использовать три семафора:

1. customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается – он уже не ждет);
2. barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента; 
3. mutex для реализации взаимного исключения.

     Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей. Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.

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

    Далее представим основные фрагменты кода программы написанной на языке высокого уровня (С++).  

#include<windows.h>

//---------------------------------------------------------------------------

int yshed = 0;                   //кол-во ушедших без стрижки

int dovol = 0;                   //счетчик подстриженных

int count = 0;                   //ожидающие

int client;                       //счетчик клиентов

//для  реализации взаимного исключения (для распределения доступа к ожидающим)

HANDLE mutex;     

HANDLE customerSemaphore;         //для подсчета ожидающих посетителей

//количество  брадобреев (0 или 1),простаивающих  в ожидании клиента

HANDLE barberSemaphore;

DWORD WINAPI customer(LPVOID);    //посетитель

DWORD WINAPI barber(LPVOID);      //парикмахер

void getPricheson();                               //функция стрижки

randomize();

DWORD SLEEP_STR = rand()%200+250; // время стрижки

DWORDSLEEP_PRX = rand()%2000+2000; //время прихода клиента

void Zprint(AnsiString text) // печать

{