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

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

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

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

Переходы

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

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

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

Пришел клиент

Зал, в нем 5 мест

Кресло парикмахера

ра

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

Конечный автомат

A=(V,Q,R,q₀,I), гдеV– алфавит конечного автомата,

Q– конечное не пустое множество состояний,

R– множество заключительных состояний,

q₀– начальное состояние,

I- программа автомата,

V- множество допустимых символов, которые могут быть поданы на вход автомата.

Конечный автомат можно представить как машину Тьюринга, но имеющую следующие особенности:

выделены заключительные состояния,

машина считывает символы с входной ленты ничего на неё не записывая,

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

автомат останавливается в случае достижения конца слова.

Конечный автомат на примере клиента парикмахерской

Клиент вошёл в парикмахерскую

Сел на скамейку в зале ожидания

Сел в кресло парикмахера (подстригается)

Уходит

Описание алгоритма

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

Реализация алгоритма вTurboC++

В реализации данной задачи в Turbo C++ были использованы семафоры, как механизм синхронизации процессов. Этот выбор основан на том, что семафоры имеют возможность подсчета ресурсов, что позволяет заранее определённому числу потоков одновременно войти в синхронизируемый участок кода.

При создании формы в первом листинге с помощью функции CreateProcess() создаётся объект ядра – процесс – «парикмахер». Далее, в процедуре Timer, создаётся несколько процессов «клиент», после чего синхронизация созданных процессов осуществляется таким образом. При создании процесса «парикмахер» создаются два семафора («кресло» и «зал ожидания»). В процедуре Timer мы сканируем семафор на наличие клиента в кресле парикмахера. Если поиск успешен, выводится сообщение о том, что парикмахер стрижет. Иначе – сообщение о том, что клиентов нет. В процедуре Timer есть счётчик ожидания: если значение счётчика по своей величине превзошло 5, выводится сообщение о том, что парикмахер заснул. Работа с двумя созданными семафорами ведется в процессе «клиент». В процедуре Timer этого процесса вызывается функция OpenSemaphore() для обоих семафоров, после чего клиент проходит в зал ожидания (счётчик семафора уменьшается на единицу), если функция WaitForSingleObject() вернёт значение «истина» (т.е. в зале ожидания ещё есть места). Если функция WaitForSingleObject() возвращает значение «ноль», то завершаем работу процессов «клиент». Из зала ожидания клиент, дождавшись освобождения семафора, с помощью функции WaitForSingleObject() переходит в кресло парикмахера. При этом с помощью функции ReleaseSemaphore() освобождается место в зале. После подстрижки клиент освобождает кресло парикмахера (ReleaseSemaphore()) и уходит (завершение процесса).