русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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

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

В нашей парикмахерской три кресла, три парикмахера, зал ожидания, в котором четыре клиента могут разместиться на диване, а остальные — стоя (см. рис. 5.6). Правила пожарной безопасности ограничивают общее количество клиентов внутри помещения 20 людьми. В нашем примере мы предполагаем, что всего мастерская должна обслужить 50 клиентов.


Рис. 5.6. Парикмахерская

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

 

Неполное решение задачи о парикмахерской

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

Основное тело программы активизирует процессы 50 клиентов, трех парикмахеров и одного кассира. Рассмотрим теперь назначение различных синхронизирующих операторов.

Вместимость парикмахерской и дивана. Вместимость парикмахеской и дивана управляется семафорами max_capacity и sofa, соответственно.Каждый раз при попытке клиента войти в парикмахерскую значение семафора max_capacity уменьшается на 1; когда клиент покидает парикмахерскую, оно увеличивается. Если парикмахерская заполнена, то процесс клиента приостанавливается функцией wait (max_capacity). Аналогично обрабатывается и попытка присесть на диван.

Емкость парикмахерских кресел. В наличии имеются три парикмахерских кресла, и следует обеспечить их корректное использование. Семафорbarber_chair гарантирует одновременное обслуживание не более трех клиентов, так чтобы один клиент не оказался на коленях у другого. Клиент не поднимется с дивана до тех пор, пока не окажется свободным хотя бы одно кресло (вызов wait (barber_chair)), а каждый парикмахер сообщает о том, что его кресло освободилось (вызов signal (barber_chair)). Справедливый доступ к парикмахерским креслам гарантируется организацией очередей семафоров: клиент, который первым блокирован в очереди, первым же и приглашается на стрижку. Заметим, что если в процедуре клиента вызов wait (barber_chair) разместить после signal (sofa), то каждый клиент будет только присаживаться на диван, после чего немедленно вскакивать и занимать стартовую позицию у кресла, создавая излишнюю толкотню и мешая работать парикмахеру.

Размещение клиента в кресле. Семафор cust_ready обеспечивает подъем спящего парикмахера, сообщая ему о новом клиенте.  Без этого семафора парикмахер никогда не отдыхал бы и приступал к стрижке немедленно после того, как очередной клиент покинет кресло. При отсутствии клиента в этот момент парикмахер стриг бы воздух.
Удержание клиента в кресле. Если уж клиент оказался в кресле, он должен отсидеть там до окончания стрижки, о чем просигнализирует семафор finished.

Ограничение количества клиентов в креслах. Семафор barber_chair предназначен для ограничения количества клиентов в креслах — их не должно быть более трех.  Однако одного семафора barber_chair для этого недостаточно.Клиент, который не получит процессорное время непосредственно после того, как парикмахер сообщит о завершении работы над его прической (вызов signal (finished)), останется в кресле (например, впав в транс или глубокозадумавшись о задаче о парикмахерской), в то время как в этом же кресле будет стараться устроиться новый клиент. Для решения данной задачи используется семафор leave_b_chair, который не позволяет парикмахеру пригласить нового клиента до тех пор, пока предыдущий не покинет кресло.

Оплата стрижки. Естественно, с деньгами надо быть особенно осторожным. Кассир должен быть уверен, что каждый клиент, покидая парикмахерскую, сперва расплатится, а каждый клиент, оплатив стрижку, должен получить чек. Это достигается передачей денег кассиру из рук в руки — каждый клиент, покинув кресло, оплачивает услуги парикмахера, после чего дает знать об этом кассиру (вызов signal (payment)) и дожидается получения кассового чека (вызов wait (receipt)). Кассир осуществляет прием платежей, ожидая сигнала о платеже, принимая деньги, а затем сообщая об этом. Здесь следует постараться избежать ряда программных ошибок. Если вызов signal (payment) выполняется непосредственно перед вызовом pay (), то клиент может оказаться прерванным в этот момент, и кассир будет пытаться принять не переданные деньги. Еще более серьезная ошибка происходит при обмене строкsignal (payment) и wait (receipt). Это может привести к взаимоблокировке всех клиентов и кассира их операциями wait.
Координация действий кассира и парикмахера. В целях экономии средств парикмахерская не нанимает отдельного кассира. Это действие выполняет парикмахер, когда не стрижет клиента. Для того чтобы обеспечить выполнение парикмахером в один момент времени только одной функции, используется семафор coord.
Назначение каждого семафора программы указано в табл. 5.3.
Листинг 5.13. Неполное решение задачи о парикмахерской


semaphore max_capacity = 20;
semaphore sofa = 4;
semaphore barber_chair = 3;
semaphore coord = 3;
semaphore cust_ready = 0,   finished =0,
leave_b_chair = 0,          payment = 0,
receipt = 0;

void customer()
{
wait(max_capacity);
enter_shop ();
wait(sofa);
sit_on_sofa();
wait(barber_chair);
get_up_from_sofa ();
signal(sofa);
sit_in_barber_chair();
signal(cut_ready);
wait(finished);
leave_barber_chair () ;
signal(leave_b_chair);
pay();
signal(payment);
wait(receipt);
exit_shop();
signal(max_capacity);
}

void barber()
{
while(true)
{
wait(cust_ready);
wait(coord);
cut_hair();
signal(coord);
signal(finished) ;
wait(leave_b_chair);
signal(barber_chair);
}
}
void cashier ()
{
while(true)
{
wait(payment);
wait(coord);
accept_pay();signal(coord);
signal(receipt);
}
}

void main ()
{
parbegin(customer,[50  раз], customer,barber,barber,barber,cashier);
}

Таблица 5.3. Назначение семафоров в листинге 5.13


Семафор

Операция wait

Операция signal

max_capacity

Клиент ожидает возможности войти в парикмахерскую

Клиент, покидающий парикмахерскую, сигнализирует об этом ожидающему входа

sofa

Клиент ожидает возможности сесть на диван

Клиент, встающий с дивана, сигнализирует об этом ожидающему возможность сесть на диван

barber_chair

Клиент ожидает пустое кресло

Парикмахер сигнализирует, что кресло свободно

Cust_read

Парикмахер ожидает, пока клиент сядет в кресло

Клиент сигнализирует парикмахеру, что он уже сел в кресло

finished

Клиент ожидает окончания стрижки

Парикмахер сигнализирует клиенту, что стрижка окончена

Leave_b_chair

Парикмахер ожидает, пока клиент покинет кресло

Клиент сигнализирует парикмахеру о том, что он встал с кресла

payment

Кассир ожидает оплаты услуг клиентом

Клиент сигнализирует парикмахеру о том, что он оплатил стрижку

receipt

Клиент ожидает кассовый чек

Кассир сигнализирует о том, что оплата принята

coord

Ожидание освобождения парикмахера для стрижки или для выполнения обязанностей кассира

Сигнал об освобождении парикмахера

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

 

 

Полное решение задачи о парикмахерской

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

В листинге 5.13 отражена проблема, которая может привести к некорректной работе с клиентами. Предположим, что в настоящий момент в парикмахерских креслах сидят три клиента. Они, скорее всего, заблокированы вызовами wait (finished) и в соответствии с организацией очереди будут деблокированы в том порядке, в котором они садились в кресла. Но что если один из парикмахеров очень быстро работает (или один из клиентов лысый)? Получится ситуация, когда одного клиента будут вытаскивать из кресла и заставлять платить за незаконченную прическу, в то время как другого, полностью постриженного клиента будут держать в кресле силой.

Эта проблема решается добавлением новых семафоров, как показано в листинге 5.14. Мы присваиваем каждому пользователю номер (как если бы при входе в парикмахерскую каждый клиент получал номерок). Семафор mutexl обеспечивает защиту доступа к глобальной переменной count, гарантируя уникальность номера каждого клиента. Семафор finished превратился в массив из 50 семафоров. Когда клиент садится в кресло, он выполняет инструкцию wait (finished[custnr] ), ожидая свой собственный семафор. По окончании стрижки парикмахер выполняет инструкцию signal (finished[b_cust] ), отпуская из кресла того клиента, которого он стриг.
Нам остается рассмотреть, каким образом парикмахер узнает номер клиента. Клиент помещает свой номер в очередь enqueue 1 непосредственно перед тем, как сообщить парикмахеру о готовности при помощи семафора cust_ready. Когда парикмахер готов стричь клиента, dequeuel (b_cust) удаляет номер клиента из очереди и помещает его в локальную переменную парикмахера b_cust.

Листинг 5.14. Полное решение задачи о парикмахерской


semaphore max_capacity =20;
semaphore sofa  =  4;
semaphore barber_chair = 3, coord = 3;
semaphore mutexl     = 1, mutex2 = 1;
semaphore cust_ready = 0,leave_b_chair = 0,
payment= 0, receipt = 0;
semaphorefinished[50] = {0};

void customer()
{
int custnr;
wait(max_capacity);
enter_shop();
wait(mutexl);
count++;
custnr = count;
signal(mutexl);
wait(sofa);
sit_on_sofa();
wait(barber_chair);
get_up_from_sofa();
signal (sofa) ;
sit_in_barber_chair();
wait(mutex2);
enqueuel(custnr);
signal(cut_ready);
signal(mutex2);
wait(finished[custnr]);
leave_barber_chair();
signal(leave_b_chair);
pay();
signal(payment);
wait(receipt);
exit_shop();
signal(max_capacity) ;
}

void barber()
{
int  b_cust;
while(true)
{
wait(cust_ready);
wait(mutex2);
dequeuel(b_cust);
signal(mutex2);
wait(coord);
cut_hair();
signal(coord);
signal(finished[b_cust]);
wait (leave__b_chair) ;
signal(barber_chair);
}
}
void cashier()
{
while(true)
{
wait(payment);
wait(coord);
accept_pay();
signal(coord);
signal(receipt);
signal(max_capacity);
}
}

void main ()
{
parbegin(customer,[50 раз],customer,barber,barber,barber,cashier);
}

Просмотров:

Вернуться в оглавление:Операционные системы




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.