3.2 Реализация задачи с помощью сетей Петри
Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.
Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами, вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.
Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, разновременно при выполнении некоторых условий.
Общий принцип работы сетей Петри:
1. Переходы
2. Места (зал ожидания, место у парикмахера)
Состояние сети определяется её разметкой. Места, из которых ведут дуги на данный переход, называются входными местами для данного перехода. Места, из которых выходят дуги, называются выходными. Выполнение условия обозначается на схеме сети изменением её разметки, т.е. помещением в данное место сети n фишек, где n- это емкость условия.
На каждом из последующих шагов работы мы переходим в следующее состояние. Выполнение условия обозначает срабатывание перехода, событие обозначается изменением разметки сети. Работа сети представляет собой совокупность срабатывания переходов. На рисунке 4 представлена сеть Петри.
Рисунок 4 - Реализация алгоритма с помощью сетей Петри
3.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) // печать
{
MainFormBarber->Memo1->Lines->Add("[" + Time() + " " + Date() + "]==> " + text);
}
//---------------------------------------------------------------------------------------------------------------
DWORD WINAPI barber(LPVOID) //парикмахер
{
While(TRUE)
{
If(count == 0) //нет никого, тогда посплю
{
Zprint("Парикмахер решил вздремнуть");
MainFormBarber->Label8->Caption = "Сплю";
//заблокируемся до появления посетителя
WaitForSingleObject(customerSemaphore,INFINITE);
}
else //буду работать тогда
{
//получаем доступ к ожидающим
WaitForSingleObject(mutex,INFINITE);
count--; //уменьшаем кол-во ожидающих клиентов
ReleaseSemaphore(mutex,1,NULL); //выход из критической области
//парикмахерготовкработе
ReleaseSemaphore(barberSemaphore,1,NULL);
getPricheson() ; //получить модную стрижек
}
}
}
//--------------------------------------------------------------------------
DWORD WINAPI customer(LPVOID) //клиент
{
WaitForSingleObject(mutex,INFINITE); //вход в критическую область
if(count < NUMBER_OF_SEATS ) //если есть свободное место
{
Sleep(SLEEP_PRX); //приостановка потока
char buffer2[100];
sprintf(buffer2, "Пришел %d клиент. Cел на %d кресло для ожидания",client+1,count+1);
Zprint((AnsiString)buffer2);
client++; //увеличиваем счетчик клиентов
count++; // увеличиваем кол-во ожидающих клиентов
switch ( count ) {
case 1: {MainFormBarber->Label5->Caption = IntToStr(client); break;}
case 2: {MainFormBarber->Label9->Caption = IntToStr(client); break;}
case 3: {MainFormBarber->Label10->Caption = IntToStr(client); break;}
case 4: {MainFormBarber->Label11->Caption = IntToStr(client); break;}
case 5: {MainFormBarber->Label12->Caption = IntToStr(client); break;}
}
MainFormBarber->Label13->Caption = "Свободно!";
MainFormBarber->Label14->Caption = IntToStr(client);
//если парикмахер спит, это его разбудит
ReleaseSemaphore(customerSemaphore,1,NULL);
ReleaseSemaphore(mutex,1,NULL); // выходи из критической области
//если парикмахер занят, переходим в состояние ожидания
WaitForSingleObject(barberSemaphore,INFINITE);
}
else
{
Sleep(SLEEP_PRX); //приостановка потока
//нет свободного кресла для ожидания – идем домой. Выход из критической области
ReleaseSemaphore(mutex,1,NULL);
char buffer3[100];
sprintf(buffer3, "Клиент %d видит, что все места заняты и уходит",client+1);
MainFormBarber->Label13->Caption = "Занято!!!";
Zprint((AnsiString)buffer3);
yshed++; //увеличиваем счетчик ушедших
client++; //увеличиваем счетчик клиентов
MainFormBarber->Label14->Caption = IntToStr(client);
}
Sleep(SLEEP_PRX); //приостановка потока
}
//---------------------------------------------------------------------------------------------------------------
void getPricheson() //функция стрижки
{
char buffer1[100];
sprintf(buffer1, "Парикмахер стрижет клиента, который сидел на месте %d",count+1);
Zprint((AnsiString)buffer1);
switch ( count+1 ) {
case 1: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label5->Caption =""; break;}
case 2: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label9->Caption =""; break;}
case 3: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label10->Caption =""; break;}
case 4: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label11->Caption =""; break;}
case 5: {MainFormBarber->Label8->Caption = IntToStr(client);
MainFormBarber->Label12->Caption =""; break;}
}
dovol++; //увеличиваем счетчик бритоголовых
Sleep(SLEEP_STR); //приостановка потока на время стрижки
//---------------------------------------------------------------------------------------------------------------
void __fastcall TMainFormBarber::FormDestroy(TObject *Sender)
{
//удаляемвсесемафоры
CloseHandle(customerSemaphore);
CloseHandle(barberSemaphore);
CloseHandle(mutex);
}
//---------------------------------------------------------------------------------------------------------------
void __fastcall TMainFormBarber::clickClick(TObject *Sender) //обработчик кнопки
{
MainFormBarber->click->Enabled = false;
//семафоры
mutex=CreateSemaphore(NULL,1,1,NULL);
customerSemaphore = CreateSemaphore(NULL, 0, 1, NULL);
barberSemaphore = CreateSemaphore(NULL, 0, 1, NULL);
// потоки клиентов и парикмахера
HANDLE threadCus[NUMBER_OF_CUSTOMERS];
HANDLE threadBar;
DWORD cusThreadId;
DWORD barThreadId;
for(int i=0;i< NUMBER_OF_CUSTOMERS;++i)
{
threadCus[i] = CreateThread(NULL, 0, customer, (LPVOID)i, 0, &cusThreadId);
}
threadBar = CreateThread(NULL, 0, barber, (LPVOID)1, 0, &barThreadId);
}