В качестве другого примера использования семафоров для реализации параллельных вычислений рассмотрим простую задачу о парикмахерской.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);
} |
