Механизмы взаимного исключения

Механизмы взаимного исключения

Состояние состязания. Задача об обедающих философах. Детерминированный набор. Условия Бернстайна. Понятие кри- тического ресурса. Критическая область. Взаимное исключение. Механизмы взаимного исключения. Алгоритм Деккера. Ал- горитм Петерсона

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

-  передача информации от одного процесса другому;

-  исключение того, что процессы пересекутся в конфликтных ситуациях;

-  согласование обмена данными: если процесс А поставляет данные, а процесс В использует их, то он должен ждать, пока процесс А не даст данные.

Вторая и третья ситуации относятся и к потокам. Передача информации для потоков не является проблемой, поскольку у них общее адресное пространство. Рассмотрим ситуацию, когда два процесса используют один и тот же ресурс, при этом рабо- тают асинхронно. Пусть каждый из процессов хочет вывести файл на печать, для этого он читает индекс свободной ячейки в очереди заданий на печать, помещает туда имя файла и увеличивает индекс. Демон печати обрабатывает эту очередь. На- пример, в очереди 2 задания уже есть, номер свободной ячейки в очереди заданий соответственно 3. Процесс А читает ин- декс, это число 3. Тут время, выделенное ему диспетчером задач, заканчивается, и управление переходит к процессу В. Он также читает индекс, это по прежнему 3. Он помещает туда имя файла, увеличивает значение индекса на 1. Тут управление возвращается к процессу А. Он знает, что индекс равен 3, хотя на самом деле уже 4, и заносит в него имя файла, увеличивает индекс. В итоге имя, занесенное процессом В, затирается, и этот файл никогда не будет напечатан. С точки зрения демона, ошибок не произошло – число заданий в очереди находится в полном соответствии с индексом. Ситуация, когда несколько процессов считывают или записывают данные одновременно, и результат зависит от того, кто из них был первым, называет- ся состоянием состязания.

Проблема обедающих философов. Сформулирована в 1965 году Дейкстрой. Пять философов сидят за круглым столом и у каждого есть тарелка со спагетти. Чтобы пообедать, необходимо две вилки. Между каждыми тарелками лежит по одной вил- ке. Философы в течение дня размышляют и обедают. Когда философ голоден, он берет правую вилку, затем левую, съедает спагетти, кладет вилки и какое-то время размышляет. Однако, если философы подойдут к столу одновременно, и одновре- менно возьмут правые вилки, никто из них не сможет начать кушать: нет ни одной свободной вилки. Произошла взаимобло- кировка. Фактически каждый из процессов (философов) захватил часть критического ресурса (одну из двух вилок). Требует- ся организовать взаимное исключение. Здесь же имеется и еще одна проблема. Например, можно решать задачу так. Если философ взял одну вилку, но вторую взять не может, он должен положить вилку обратно, подождать и повторить все снача- ла. Но если один философ очень медлителен, а его сосед, напротив, очень быстр, то медленный философ умрет от голода: он подходит к столу, берет вилку, вторая захвачена быстрым соседом, кладет вилку, немного ждет. За это время быстрый сосед успевает покушать, положить вилки, поразмышлять, вновь подойти к столу, и взять вилки для обеда. Медленный философ берет вилку, а вторая занята соседом… И так до бесконечности. Это проблема называется голоданием.

Бернстайн сформулировал условия, при соблюдении которых при псевдопараллельном выполнении нескольких процессов для одного и того же набора входных данных они дают одинаковые выходные данные (т.е. набор процессов детерминиро- ван). Обобщение условий на N процессов выглядит следующим образом:

Пусть Ri – набор входных переменных процесса i, Wi – выходных. Тогда выполнение N процессов детерминировано, если: - Wi  Wj = , i,j=1,2,…,N; ij -     Wi  Rj = , i,j=1,2,…,N; ij

Пример. Пусть процесс А вычисляет: x=u+v; y=x*w; а процесс В вычисляет: a=b*c; z=x+a; Wa = {x,y}, Ra = {u,v,x,w}; Wb = {a,z}; Rb = {b,c,x,a}.

Wa  Wb = , Wa  Rb ={x}, Wb  Ra = . Условия не выполняются.

Если условия не соблюдаются, то параллельное выполнение набора процессов может быть детерминированным, а может быть недетерминированным. Условия по сути требуют практически невзаимодействующих процессов. Недетерминирован- ный набор и приводит к состояниям состязания.

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

случае      с              принтером проблема возникла из-за того, что процесс В начал работу с ресурсом   до того,    как         процесс                А закончил с ним работать. Кроме реализации в ОС средств для организации

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

Для корректной организации взаимодействия параллельных процессов необходимо выполнение следующих 4 условий: - в любой момент времени только один процесс должен находиться в своей критической области (условие взаимного ис- ключения);

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

-  ни один процесс не должен ждать бесконечно долго вхождения в критическую область и, следовательно, ни один про- цесс не должен находиться в критической секции бесконечно долго; (условие ограниченного ожидания)

-  не должно быть предположений о скорости или количестве процессов.

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

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

Другое решение состоит в использовании специальных переменных для блокировки. Выделяется переменная, изначально равная 0. Если процесс желает попасть в критическую область, он считывает эту переменную, и если она равна 0, то уста- навливает ее в 1 и входит в критическую область. Если же переменная равна 1, то процесс ждет, пока она не установится в 0. Однако такое решение позволяет нескольким процессам одновременно войти в критические области.

Еще одним вариантом организации взаимного исключения является чередование доступа к критическому ресурсу. Для это- го имеется общая переменная, указывающая, чья очередь входить в критическую область:

Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием. При этом нерационально тратится процессорное время. Блокировка, использующая активное ожидание, называется спин- блокировкой. Здесь возможны и другие проблемы. Например, некритическая секция процесса 2 значительно длиннее, чем у процесса 1. Пусть очередь доступа у 1 процесса. Он входит в критическую область. Второй процесс в это время ожидает вхождения в цикле. Первый процесс выполняет критическую область, передает очередь. Второй процесс входит в критиче- скую область. Первый процесс выполняет некритическую область. Второй процесс выполняет критическую область, переда- ет очередь, и тоже приступает к выполнению некритической области. Первый процесс вновь входит в критическую область, выполняет ее, передает очередь, входит в некритическую область. Второй процесс по прежнему находится вне критической области. Первый процесс выполняет некритический фрагмент, и переходит к ожиданию в цикле, пока второй процесс не пе- редаст очередь. Но при этом второй процесс находится вне критической секции, и выполнит ее еще очень не скоро. Т.о., на- рушается одно из условий, рассмотренных ранее: процесс, находящийся вне критической области влияет на функционирова- ние процесса, ожидающего доступа. Фактически требуется, чтобы процессы попадали в критические секции строго пооче- редно, ни один из процессов не может попасть в критическую секцию дважды подряд.

Алгоритм Деккера. Датским математиком Деккером впервые был предложен алгоритм взаимного исключения, не требую- щий строгого чередования. По сути, он объединяет два предыдущих подхода. Он основан на наличии 3 переменных: switch[0], switch[1], turn, отвечающих за требования процессов на вхождение в критическую область, и чья очередь на вхож- дение при условии, если оба процесса требуют ресурс. Алгоритм работы процесса представлен на граф-схеме.

// глобальные переменные, изначально все в значении 0

Если установлен флаг запроса от процесса 0, и нет флага запроса от процесса 1, то выполняется критическая секция процесса 0 независимо от того, чья очередь, и очередь передается другому процессу. Если же установлены оба флага, то выполняется критическая секция того процесса, чья очередь. Второй процесс при этом ожидает передачи очереди. Алгоритм Деккера позволяет гарантированно решить проблему критических интервалов. Флаги запроса обеспечивают невозможность одновременного вхождения в критическую об- ласть, переменная очереди избавляет от взаимной блокировки. Однако в случае обобщения на N процессов алгоритм усложняется.

Алгоритм Петерсона. В 1981 году был разработан более простой алгоритм взаимного исключения. Алгоритм основан на двух процедурах. Одна из них вызывается перед вхождением в критическую область, вторая - по окончании ее.

// глобальные переменные, изначально все в значении 0

int turn;    // переменная, указывающая, чья очередь доступа int switch[2];     // запросы на вхождение в критическую область

             #define PROC_NUM 0     // 0 – для 1 процесса, 1 – для второго

void process(void)

{while (1)

{switch[PROC_NUM]=1; // запрос на вхождение в КС turn=PROC_NUM; // установка очереди на текущий процесс while (turn==PROC_NUM && switch[1-PROC_NUM]==1);}// ожид., если

// очередь тек. проц., но есть другие запросы

critical_section(); // выполнение критической секции switch[PROC_NUM]=0; // снятие запроса

                         non_critical_section();}}      // выполнение оставшейся, некритической

// части кода

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

менную очереди в 0 (процесс 0). Поскольку процесс 1 не устанавливал флаг запроса, то процесс 0 входит в критическую об- ласть, затем, после ее выполнения, в функции выхода снимает запрос. Если оба процесса вызывают функцию вхождения практически одновременно, происходит следующее. Процесс 0 устанавливает флаг запроса, и устанавливает переменную очереди на свой номер (0). В это время процесс 1 устанавливает свой флаг запроса и изменяет переменную очереди на свой номер (1). Проверяется условие цикла: от процесса 0 есть запрос и очередь установлена на текущий процесс. Процесс 1 пе- реходит к активному ожиданию. Тем временем процесс 0 приступает к определению истинности условия цикла: запрос от процесса 1 есть, но очередь также установлена на процесс 1. Условие ложно, ожидания не происходит, и процесс входит в критическую область. После ее прохождения он снимает флаг запроса. В этот момент у процесса 1 условие также становится ложным, поскольку уже нет запросов от других процессов, и он входит в критическую секцию.

Типовые механизмы синхронизации

Операции Test & Set. Поддержка механизма TS в современных процессорах. Семафоры Дейкстры. Базовые операции над семафорами. Мьютексы. Задача “поставщик-потребитель”. Поддержка механизмов синхронизации в Windows и UNIX. Мониторы Хоара. Поддержка мониторов в языках программирования. Задача о парикмахерской. Задача “читатели- писатели”

Операция “Проверка и установка” является аппаратным механизмом организации взаимного исключения. В IBM360 эта команда называлась TS (Test & Set). Команда имеет два операнда и выполняется следующим образом. Значение второго опе- ранда присваивается первому, после этого второй операнд устанавливается в единицу. Особенность команды в том, что она является неделимой, т.е. оба эти действия выполняются неразрывно. Для возможности использования этой операции требу- ется одна общая переменная, доступная всем процессам. Переменная должна принимать значение 1, если какой-либо про- цесс находится в своей критической области. Кроме того, с каждым из процессов связана еще и своя персональная перемен- ная, устанавливаемая в 1, если процесс хочет войти в критическую секцию. TS будет использоваться так: значение общей переменной будет считываться в локальную и устанавливаться в 1.

             int common=0;                                                                   // глобальная переменная

             #define PROC_NUM 0                                                     // 0 – для 1 процесса, 1 – для второго

 void process(void)

{int proc; // персональная переменная запроса while(1)

                      {proc=1;                                                                    //запрос на вхождение в критическую секцию

while(proc==1) TS(proc, common); //пока запрос не обслужен, выполняется операция TS critical_section(); //выполнение критического интервала common=0; //флаг, что в критической секции нет процесса non_critical_section();}} //дальнейшие действия

Происходит следующее. Допустим, что в критической секции процесса нет. В этом случае все переменные равны 0. Первый процесс хочет получить доступ к критическому ресурсу. Он выставляет флаг. Операция TS выполняет proc=common, com- mon=1, т.е. поскольку common была 0, то фактически запрос снимается, флаг входа в КС устанавливается, процесс выходит из цикла и входит в КС. Допустим, что в этот момент процесс 2 устанавливает свой флаг. Он входит в цикл, TS выполняет proc=common, common=1. Поскольку Common и так уже в 1, т.е. в КС находится другой процесс, то запрос не снимается, так же как и сам флаг не изменяет значения. Процесс2 ожидает в цикле. Теперь процесс1 выходит из КС и снимает флаг. Про- цесс2 в очередной раз выполняет TS, поскольку common=0, то запрос снимается, флаг входа в КС устанавливается, процесс выходит из цикла и входит в КС.

В современных микропроцессорах есть специальные команды, являющиеся разновидностью TS: BTC, BTS, BTR. BTS (bit test & set) также имеет два операнда: BTS Op, B. Процессор сохраняет бит с номером В переменной Op во флаге CF (carry - перенос), и устанавливает бит B переменной Op в 1. В качестве номера бита может быть указан регистр процессора, в кото- ром этот номер хранится. Этот индекс берется по модулю 32, т.е. использует только 5 младших бит числа, соответственно индекс находится в диапазоне 0 – 31, что позволяет выбрать любой бит в пределах 4-байтной переменной или регистра.

                        L: BTS m, 1              ; бит 1 глобальной переменной m – флаг нахождения в КС какого либо процесса

                             JC L           ; пока в ней есть процесс, ожидание; флаг переноса выступает в качестве локальной переменной

CALL critical_section

AND m, 0fffffffeh ; сброс флага нахождения в критической секции

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

Команда ВТR Op, B выполняет полностью аналогичные действия, но бит В сбрасывается в 0. Команда BTC Op, B инверти- рует значение бита В. Обе эти команды сохраняют прежнее значение бита во флаге переноса.

Существует и еще одна проблема при использовании TS или алгоритма Петерсона. Это проблема инверсии приоритетов. Пусть имеется 2 процесса: Н с высоким приоритетом и L с низким, которым требуется один и тот же ресурс. Планировщик в этом случае немедленно запускает процесс Н, если тот оказался в состоянии ожидания. Допустим, процесс L находится в критической области. В этот момент Н попадает в состояние ожидания. Планировщик запускает его, но поскольку ресурс занят процессом L, то процесс H остается в состоянии активного ожидания. Однако процесс L не может завершить критиче- скую секцию, т.к. ему не будет предоставлено время, соответственно Н останется в активном ожидании.

Семафоры Дейкстры. Понятие семафоров было введено Дейкстрой. Семафор S – это переменная специального типа, дос- тупная параллельным процессам для проведения над ней только двух неделимых операций: закрытия P(S) и открытия V(S).

Поскольку эти операции неделимы, то они исключают друг друга. Семафорный механизм работает по следующей схеме: вначале исследуется состояние критического ресурса, определяемое значением семафора. В зависимости от результата про- исходит или предоставление ресурса или ожидание доступа в очереди в режиме “пассивного ожидания”. В состав механизма включаются специальные средства формирования и обслуживания очереди ожидающих процессов ОС. В силу неделимости операций, даже если некоторые процессы одновременно захотят использовать критический ресурс, доступ получит только один, а второй будет помещен в очередь. Процессам из очереди не предоставляется процессорное время, пока ресурс занят. Допустимыми значениями семафоров являются целые числа. Семафор называется двоичным, если максимальное значение, которое он может принять, это 1. Если больше, то семафор – N-ричный. Рассмотрим пример реализации. Допустим, семафор S инициализируется ОС в значение 1. Тогда операции P и V имеют вид:

Пусть оба процесса пытаются выполнить P(S), и это успешно удается второму процессу. Он устанавливает семафор в 0 и переходит к выполнению КС. Тем временем процесс 1 пытается выполнить P(S). Он устанавливает семафор в –1, и помеща- ется ОС в очередь ожидания. Процесс 2 выполняет КС, и вызывает V(S). Поскольку семафор<0, т.е. есть очередь, то процесс 1 выводится из очереди и переходит к выполнению КС. Тем временем процесс 2 восстанавливает значение семафора до 0. В итоге противоречий нет: семафор закрыт, в очереди нет процессов.

Возможны и другие реализации семафоров. Неделимость примитивов P и V обеспечивается в однопроцессорной системе простым запретом прерываний на время их выполнения. В многопроцессорных системах это проблему не решит, поскольку доступ к семафору по-прежнему будет иметь несколько процессов одновременно. Для разграничения доступа требуется ис- пользовать переменные блокировки и операцию TS.

Одним из вариантов организации работы с семафором являются мьютексы mutex (mutual exclusion – взаимное исключе- ние). Реализованы во многих ОС, представляют собой простейшие двоичные семафоры, которые могут находиться только в одном из двух состояний – открыт или закрыт. Соответственно для реализации требуется всего 1 бит, хотя обычно исполь- зуют переменную типа int, у которой 0 – открытое состояние, 1 – закрытое. Значение мьютекса устанавливается 2 процеду- рами. Если процесс хочет войти в КС, он вызывает процедуру закрытия мьютекса, например mutex_lock. Если мьютекс от- крыт, то запрос выполняется и вызывающий процесс может попасть в КС. Если же мьютекс закрыт, то процесс блокируется, пока другой процесс, находящийся в КО, не выйдет из нее, открыв мьютекс соответствующей процедурой, например, mutex_unlock. Как только какой-либо процесс становится владельцем объекта mutex, он закрывается, а когда задача его ос- вобождает, он открывается. Пример реализации мьютекса:

От прямого использования операции TS имеется одно существенное отличие: не используется активного ожидания. Сущест- вует еще одна проблема, связанная с синхронизацией, про которую не было сказано. В рассмотренных ранее случаях (алго- ритмы Деккера и Петерсона, семафоры) предполагалось, что имеется общая глобальная переменная. Однако процессы име- ют каждый свое адресное пространство. Как организовать доступ к общему участку памяти? Существует 2 варианта реше- ния. 1: совместно используемые переменные, например, семафоры, хранить в ядре с доступом через системные запросы. 2: позволить процессам использовать некоторую общую область памяти. Как правило, в современных ОС реализованы оба ва- рианта.

Задача производитель-потребитель.

Два процесса совместно используют буфер ограниченного размера. Процесс-производитель помещает туда данные, а про- цесс потребитель считывает. Проблема возникает, когда производитель пытается поместить данные, и обнаруживает, что буфер полон. Решение в том, чтобы ждать, пока буфер частично или полностью не освободится. Аналогично, если потреби- тель обращается за данными, а буфер пуст, он также переводится в состояние ожидания. Решение “в лоб” приводит к со- стоянию состязания, как в случае с печатью файлов. Рассмотрим тривиальное, но неверное решение. Нужна переменная для отслеживания количества записей в буфере count. Пусть N - максимальная длина буфера:

Рассмотрим эту ситуацию. Производитель подготовил объект и пытается поместить его в буфер, который заполнен

до отказа (count=N). Он читает значение счетчика, сравнивает его с максимальным, но перейти в состояние ожидания не ус- певает, поскольку планировщик переключает процессы, передавая управление потребителю. Тот читает счетчик, берет эле- мент из буфера, уменьшает счетчик и, поскольку буфер был полон, посылает сигнал производителю на выход из состояния ожидания. Однако производитель не находится в состоянии ожидания и сигнал пропадает. Когда, наконец, планировщик вновь переключит процессы, производитель благополучно перейдет к ожиданию, несмотря на то, что состояние буфера уже поменялось. В результате потребитель выберет из буфера все элементы и также перейдет в состояние ожидания. Оба про- цесса будут ожидать – один освобождения буфера, другой – его заполнения. Аналогичные проблемы возникают при пустом буфере Проблема в том, что производитель не успел перейти в состояние ожидания и сигнал активации пропал впустую, создавая типичную ситуацию гонок. Одно из решений проблемы в использовании бита активации. Если сигнал активации посылается процессу, который не находился в состоянии ожидания, то бит устанавливается. Если процесс пытается уйти в состояние ожидания, проверяется этот бит. Если он установлен, то процесс не переводится в состояние ожидания, а всего лишь сбрасывает этот бит, продолжая обработку. Однако задача может быть обобщена на случай N производителей и M по- требителей, и одного бита становится недостаточно.

Рассмотрим решение с помощью семафоров.

#define N 100 typedef int semaphore;

void producer(void)

{int item;

while (1)

{item=produce_item();      // создание данных

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

Поддержка механизмов синхронизации в ОС Windows. Поддерживаются следующие объекты синхронизации: критиче- ские секции, мьютексы, семафоры, события. Объект критической секции создается и удаляется функциями void InitializeCriticalSection (LPCRITICAL_SECTION lpCriticalSection) void DeleteCriticalSection (LPCRITICAL_SECTION lpCriticalSection)

В качестве параметра передается указатель на переменную типа CRITICAL_SECTION. Эти объекты не имеют дескрипторов и соответственно не могут использоваться совместно разными процессами, только потоками. При входе и выходе из крити- ческого участка кода поток вызывает соответственно функции:

void EnterCriticalSection (LPCRITICAL_SECTION lpCriticalSection) void LeaveCriticalSection (LPCRITICAL_SECTION lpCriticalSection)

Внутри области кода, защищенной одним и тем же объектом КС может находиться только один поток. Если другой в это время вызывает EnterCriticalSection, он блокируется. Объекты КС не являются объектами ядра и поддерживаются в про- странстве пользователя, что позволяет увеличить производительность. Это простейший механизм синхронизации потоков одного и того же процесса.

В отличие от объектов КС, мьютексы могут иметь имена и дескрипторы, реализуются в пространстве ядра и их можно ис- пользовать для синхронизации потоков разных процессов. Дополнительно мьютексы позволяют задавать конечный период ожидания в состоянии блокировки. Мьютекс создается функцией

HANDLE CreateMutex (

LPSECURITY_ATTRIBUTES lpsa,

BOOL bInitialOwner,

LPCTSTR lpName)

Здесь lpsa – указатель на структуру атрибутов защиты, определяет возможность наследования указателя на объект мьютекса дочерними процессами. Если NULL – не наследуется. BInitialOwner определяет, требуется ли захват мьютекса сразу после создания. TRUE – да, FALSE – нет. LpName – указатель на нуль-строку, содержащую имя создаваемого объекта. Функция возвращает указатель типа HANDLE на созданный объект. Если создание не удалось, возвращается NULL. Созданный мью- текс имеет два состояния – сигнальное и нет. В сигнальном состоянии он может быть захвачен, в противном случае при по- пытке захвата поток блокируется. Для получения указателя на уже имеющийся объект используется функция HANDLE OpenMutex (

DWORD dwDesiredAccess,

BOOL bInheritHandle,

LPCTSTR lpName) Первый параметр определяет режим использования. MUTEX_ALL_ACCESS определяет разрешение всех возможных вари- антов работы с объектом. Второй параметр определяет возможность наследования указателя на объект мьютекса. Третий – указатель на имя. Для удаления ссылки на мьютекс используется BOOL CloseHandle (HANDLE hObject)

Ссылка удаляется и автоматически при закрытии потока. Мьютекс уничтожается системой автоматически, если с ним не связано ни одного указателя. Для захвата мьютекса используется одна из функций ожидания сигнального состояния. Если объект находится в этом состоянии, происходит захват, и он переводится в несигнальное состояние. Другой поток буде вы- нужден ждать. Рассмотрим две функции из этого множества:

DWORD WaitForSingleObject (

HANDLE hHandle,

DWORD dwMilliseconds)

Здесь hHandle –указатель на объект, сигнальное состояние которого ожидается, второй параметр – максимально допустимое время ожидания в милисекундах. Если интервал задан 0 – тестируется текущее состояние и происходит немедленный воз- врат. Если указано INFINITE интервал тайм-аута не используется. В случае ошибки возвращается значение WAIT_FAILED. Иначе WAIT_ABANDONED, если поток, который создал мьютекс, уже завершился без освобождения объекта с помощью Release. Вызвавший функцию процесс становится владельцем, а мьютекс переходит в несигнальное состояние. WAIT_OBJECT_0, если состояние объекта сигнальное, WAIT_TIMEOUT, если завершился тайм-аут. Функция позволяет работать не только с мьютексами, но и с другими объектами, в т.ч. семафорами, события, процессы, потоки, таймеры и др.

DWORD WaitForMultipleObjects (

                         DWORD nCount,                                  число указателей на объекты

                         CONST HANDLE *lpHandles,         массив указателей

BOOL bWaitAll,       если TRUE, то ждет всех объектов в сигнальном состоянии, FALSE – любого из них DWORD dwMilliseconds)     тайм-аут

Возвращаемые значения аналогичны, однако, если bWaitAll=FALSE, то возвращаемое значение минус WAIT_OBJECT_0 (либо WAIT_ABANDONED) указывает номер указателя в массиве на тот объект, который находится в сигнальном состоя- нии. Если bWaitAll=TRUE функция не изменяет значения объектов синхронизации до тех пор, пока все они не будут в сиг- нальном состоянии, т.е. либо атомарно выполняются все операции сразу, либо не выполняются вообще. DWORD MsgWaitForMultipleObjects(

DWORD nCount,

LPHANDLE pHandles,

BOOL fWaitAll,

DWORD dwMilliseconds,

                         DWORD dwWakeMask)                    тип сообщений в очереди, по которым ожидание так же должно закончиться

Аналогичная функция, позволяющая дополнительно обрабатывать сообщения из очереди, например, для обработки клавиа- туры или мыши. Параметры идентичны. WakeMask: QS_ALLINPUT – любое сообщение в очереди, QS_HOTKEY - сообще-

ние WM_HOTKEY, QS_INPUT – сообщение ввода, QS_KEY – сообщения WM_KEYUP, WM_KEYDOWN, WM_SYSKEYUP, WM_SYSKEYDOWN, QS_MOUSE - сообщения WM_MOUSEMOVE или нажатия кнопок мыши

(WM_LBUTTONUP, WM_RBUTTONDOWN, и др.), QS_MOUSEBUTTON – нажатие кнопок мыши (WM_LBUTTONUP, WM_RBUTTONDOWN, и др.), QS_MOUSEMOVE - сообщение WM_MOUSEMOVE, QS_PAINT - сообщение WM_PAINT, QS_POSTMESSAGE – сообщение иное, чем в данном списке, QS_SENDMESSAGE – сообщение присланное другим потоком или приложением, QS_TIMER - сообщение WM_TIMER. Возвращаемые значения аналогичны, дополнительно WAIT_OBJECT_0 + nCount указывает, что появилось сообщение в очереди.

DWORD SignalObjectAndWait(

                         HANDLE hObjectToSignal,               объект, устанавливаемый в сигнальное состояние

                         HANDLE hObjectToWaitOn,            объект, сигнальное состояние которого ожидается

                         DWORD dwMilliseconds,                  тайм-аут

BOOL bAlertaible)

Эта функция позволяет атомарным образом один объект установить в сигнальное состояние, после чего дождаться сигналь- ного состояния второго объекта. Windows поддерживает асинхронные вызовы процедур. При создании потока с ним связы- вается очередь асинхронных вызовов процедур (APC queue). ОС либо пользователь могут помещать в нее запросы на выпол- нение функций в контексте данного потока. Эти функции не могут быть выполнены немедленно, поскольку поток может быть занят. Параметр bAlertaible указывает, оканчивать ли ожидание, если пришел запрос на асинхронный вызов процедуры.

Возвращаемые значения аналогичны WaitForSingleObject.

BOOL ReleaseMutex (HANDLE hMutex)

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

Механизм семафоров поддерживает счетчики, если значение счетчика больше 0, он в сигнальном состоянии. Отрицательные значения не допускаются. Создание:

HANDLE CreateSemaphore (

                         LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,             - права наследования

                         LONG lInitialCount,                                                                            - начальное значение

                         LONG lMaximumCount,                                                                    - максимально допустимое значение

                         LPCTSTR lpName)                                                                              - указатель на имя

Удаление ссылки производится уже рассмотренной функцией CloseHandle или автоматически при завершении потока. Объ- ект автоматически удаляется, если нет связанных с ним указателей. Получение указателя на существующий объект – HANDLE OpenSemaphore (

DWORD dwDesiredAccess,

BOOL bInheritHandle,

LPCTSTR lpName)

Параметры полностью идентичны функции OpenMutex. Ожидание сигнального состояния производится с помощью рас- смотренных WaitForSingleObject, WaitForMultipleObjects и др. Снятие захвата (операция V) производится функцией

BOOL ReleaseSemaphore (

                         HANDLE hSemaphore,                       указатель на объект

                         LONG lReleaseCount,                         величина, на которую надо увеличить значение семафора, больше 0

                         LPLONG lpPreviousCount)   указатель на переменную, куда будет возвращено предыдущее значение семафора

Объект события позволяет сигнализировать другим процессам о наступлении какого-либо события. Существуют сбрасывае- мые программно (вручную) события, когда сигнал может быть передан одновременно всем потокам, и сбрасываемые авто- матически после освобождения одного из потоков. Создание объекта:

HANDLE CreateEvent (

                         LPSECURITY_ATTRIBUTES lpEventAttributes,       атрибут наследования

                         BOOL bManualReset,                                                          TRUE для ручного сброса

BOOL bInitialState, начальное состояние, TRUE - сигнальное LPCTSTR lpName) указатель на имя.

Ручной сброс выполняется функцией BOOL ResetEvent (HANDLE hEvent). OpenEvent аналогично уже рассмотренным ва- риантам возвращает указатель на существующий объект события. BOOL SetEvent (HANDLE hEvent) устанавливает событие в сигнальное состояние. BOOL PulseEvent (HANDLE hEvent) освобождает все потоки, ожидающие сбрасываемого вручную события, и событие сразу же сбрасывается.

Для работы с разделяемой памятью используются функции OpenFileMapping, MapViewOfFile, UnmapViewOfFile, Close- Handle. Разделяемая память организуется либо через отображение на память файла, либо непосредственно в памяти. Далее этот объект отображается на адресное пространство потока, в результате с файлом можно работать как с обычным массивом данных в памяти.

Все рассмотренные функции создания объектов синхронизации и разделяемой памяти CreateXXX возвращают дескриптор и в том случае, если объект с таким именем уже существует. Однако в этом случае функция GetLastError возвращает значение ERROR_ALREADY_EXISTS, в случае же первичного создания она возвращает 0.

Поддержка механизмов синхронизации в UNIX. POSIX библиотека pthreads поддерживает мьютексы следующими функ- циями для создания, удаления, захвата и освобождения мьютекса: pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_unlock. В системах на основе System V, в т.ч. и ряде дистрибутивов Linux реализована наиболее общая версия семафоров. Создание массива семафоров: int semget (key_t key, int nsems, int semflg);

key – 32 разрядная переменная-ключ, идентифицирующая набор семафоров, nsems – число семафоров в наборе, semflg – ре- жим доступа Значение IPC_CREAT для создания нового набора, если он уже существует, проверяются права доступа. Если необходимо, чтобы возвращалась ошибка, если набор уже существует, должна использоваться совместно еще одна констан- та IPC_EXCL. Для подключения к уже существующему набору эти флаги не нужны. Младшие 9 бит флага отвечают за пра- ва доступа для root’а, владельца, группы. Возвращает идентификатор массива семафоров или –1 в случае ошибки. При соз- дании набора создается одна общая для набора структура: struct semid_ds{

struct ipc_rerm sem_perm; поля этой структуры содержат информацию о владельце, группе и правах доступа struct sem* sem_base;              указатель на массив объектов-семафоров ushort sem_nsems;                число семафоров в наборе time_t sem_otime;          время последней операции (P или V) time_t sem_ctime; время последнего изменения

…}

При создании инициализируются поля структуры sem_perm, sem_otime устанавливается в 0, sem_ctime в текущее время. Для каждого семафора создается структура следующего вида: struct sem{

                         ushort semval;        текущее значение семафора

pid_t sempid;             идентификатор процесса, вызвавшего последнюю операцию ushort semncnt;     кол-во процессов ожидающих увеличения значения семафора ushort semzcnt;} кол-во процессов ожидающих нулевого значения семафора

Ключ key можно задавать явно, однако это не гарантирует уникальности ключа – такой уже может существовать в системе. Большую гарантию (однако не 100%) дает использование функции key_t ftok(char* pathname, int proj_id);

Первый параметр задает путь доступа и имя существующего файла, в качестве которого может выступать и корневой ката- лог (“/”), и текущий каталог(“./”). Второй параметр – заданный пользователем ненулевой идентификатор. Хотя это перемен- ная типа int, для генерации реально используется только 8 младших бит. Гарантируется уникальность ключа для отличаю- щихся пар и идентичность для одинаковых. В случае ошибки возвращает -1, и ключ-идентификатор набора в случае успеха.

Операции над семафорами в массиве выполняются вызовом int semop (int semid, struct sembuf *sops, unsigned nsops)

semid – идентификатор набора, sosp – указатель на массив структур sembuf, определяющих, что выполняется с набором, nsosp – число элементов в этом массиве. В результате один вызов обрабатывает несколько семафоров. Ядро гарантирует ато- марность этих операций, т.е. никакой другой процесс не начнет обработку над тем же набором, пока текущий процесс не завершит ее. Структура sembuf имеет следующий вид:

struct sembuf { unsigned sort sem_num; short sem_op; shot sem_flg} Здесь sem_mun – номер семафора в наборе. Если sem_op = 0, то происходит блокировка процесса до тех пор, пока семафор не станет равным нулю, если sem_op>0, то sem_op добавляется к текущему значению семафора, в результате может быть разбужен процесс, ожидающий увеличения семафора. Если sem_op<0, то происходит блокировка процесса до тех пор, пока значение семафора не станет равным или больше по абсолютному значению, чем sem_op, после чего от текущего значения семафора вычитается sem_op. Если флаг sem_flg = IPC_NOWAIT, вместо блокировки происходит возврат с возвращением ошибки. Если процесс завершает работу, не освободив захваченный семафор, то ожидающий процесс будет заблокирован бесконечно. Чтобы этого не происходило, указывается флаг SEM_UNDO. В этом случае ядро запоминает произведенные процессом операции над семафором и автоматически прокручивает их в обратном порядке при завершении работы процесса. Из системы семафоры удаляются принудительно. В противном случае они будут существовать в системе, даже если ни один процесс с ними не связан. С другой стороны это позволяет поддерживать семафоры, не зависящие от жизненного цикла про- цессов. Для управления объектами набора используется вызова int semctl (int semid, int semnum, int cmd, …)

У вызова 3 или 4 параметра. Первый – идентификатор набора, второй – номер семафора в наборе, если операция выполняет- ся над одним семафором набора, третий – команда, четвертый параметр arg – объединение следующего вида:

union semun {

int val;

struct semid_ds *buf; unsigned short *array; struct seminfo * buf;} Возможны следующие команды:

IPC_STAT – копирует данные о наборе в структуру, определяемую arg.buf. Параметр semnum игнорируется.

IPC_SET – устанавливает поля структуры semid_ds о пользователе, группе и режиме доступа из arg.buf. При этом модифи- цируется поле sem_ctime. Параметр semnum игнорируется.

IPC_RMID – немедленно удаляет набор семафоров, активируя все заблокированные на нем процессы. Параметр semnum иг- норируется.

GETALL возвращает semval для всех семафоров набора в arg.array. Параметр semnum игнорируется. GETVAL возвращает semval для семафора semnum набора semid.

GETNCNT возвращает значение semncnt (число процессов, ожидающих увеличения) для семафора semnum.

GETZCNT возвращает значение semzcnt (число процессов, ожидающих 0) для семафора semnum.

GETPID возвращает sempid (т.е. pid процесса, последним выполнявшим операцию) для семафора semnum

SETALL устанавливает semval для всех семафоров набора из arg.array. Модифицирует sem_ctime набора. Изменение влияет на пробуждение ожидающих процессов. Параметр semnum игнорируется. Отрицательные значения не допускаются.

SETVAL устанавливает semval для семафора semnum. Модифицирует sem_ctime набора. Изменение влияет на пробуждение ожидающих процессов. Отрицательные значения не допускаются.

Для любой команды у процесса должны быть необходимые привилегии. Для команд, изменяющих значения, идентификатор вызвавшего их процесса должен иметь права суперпользователя или же процесс должен быть владельцем либо создателем набора семафоров. В случае ошибки возвращает –1, 0 в случае успеха (за исключением команд GETNCNT, GETZCNT, GET- VAL, GETPID).

UNIX также поддерживает разделяемые страницы памяти. Создание разделяемой области выполняется вызовом int shmget (key_t key, int size, int shmflg)

Здесь size – размер задаваемой области, остальные параметры аналогичны рассмотренным для семафоров. Подключение об- ласти к виртуальному адресному пространству процесса производится вызовом void * shmat (int shmid, const void *shmaddr, int shmflg)

Здесь shmid – идентификатор области, shmaddr – адрес виртуального пространства, куда необходимо произвести отображе- ние, если NULL , то система вправе подключить область по любому адресу. Если флаг shmflg –SHM_RDONLY – то область подключается как только для чтения. Возвращает адрес, на который происходит отображение. В случае ошибки возвращает

–1. Отключение отображения в виртуальное адресное пространство процесса выполняет вызов int shmdt (const void *shmaddr)

Здесь shmaddr – адрес отображения, возвращенный ранее shmat. Вызов int shmctl (int shmid, int cmd, struct shmid_ds *buf)

позволяет управлять соответствующими структурами, отвечающими за разделяемую память и отображение. Shmid – иден- тификатор области, cmd – соманда, buf – указатель на структуру с информацией об области. Команда IPC_RMID позволяет освободить занятые структуры, при этом область удаляется лишь в том случае, если все отображения будут отключены про- цессами. При ошибке возвращает –1, при успешном завершении 0.

Сравнение возможностей механизмов синхронизации:

Однако использование семафоров тоже имеет свои ограничения. Если семафоры в листинге поменять местами, то может произойти взаимоблокировка, т.е. программы не застрахованы от случайных ошибок пользователя. Для организации взаи- модействия в 1974 г. Хоар и Хансен предложили примитив синхронизации более высокого уровня – монитор. Монитор – это набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Например, какой- либо ресурс должен разделяться между процессами. Соответственно для получения ресурса процесс должен обратиться к некоторому планировщику, который с помощью внутренних переменных отслеживает, занят ресурс или свободен и выпол- няет последующие необходимые действия. Процедуры этого планировщика разделяются всеми процессами, однако плани- ровщик может обслуживать только один процесс. Такой планировщик и является монитором.

Процессы могут вызывать процедуры монитора, однако у внешних процедур нет прямого доступа к внутренним структурам монитора. Важным свойством монитора является следующее: при обращении к монитору в любой момент времени актив- ным может быть только один процесс. Мониторы являются структурным компонентом языка программирования, и компи- лятор знает, что процедуры монитора надо обрабатывать иначе, чем вызовы других процедур. Как правило, первые несколь- ко команд процедуры монитора проверяют, нет ли уже в мониторе активного процесса. Если есть, то вызывающий процесс ожидает. Для реализации взаимного исключения обычно используется мьютекс или бинарный семафор. Этого еще недоста- точно. Необходим способ блокировки процессов, которые не могут продолжаться дальше. Решение в том, чтобы ввести пе- ременные состояния и две операции wait и signal. Если процедура монитора обнаруживает, что она не может продолжать работу, то она выполняет операцию wait на какой-либо переменной состояния. Это приводит к блокировке вызывающего процесса и позволяет другому процессу войти в монитор. Другой процесс может активизировать его, выполнив операцию signal на той переменной состояния, на которой тот был заблокирован. Еще надо сделать так, чтобы в мониторе не было двух процессов одновременно. Хоар предложил запуск разбуженного процесса и остановку второго. Хансен предложил, что про- цесс, выполнивший signal, должен немедленно покинуть монитор. Т.е. операция signal должна выполняться в самом конце монитора. Если signal выполнена на переменной, с которой связаны несколько заблокированных процессов, планировщик выбирает только один из них. Существует и третье решение: позволить процессу, выполнившему signal, продолжать работу и запустить ожидающий процесс только после того, как первый процесс покинет монитор. Переменные состояния не явля- ются счетчиками. Они не накапливают значения. Это значит, что в случае выполнения операции signal на переменной со- стояния, с которой не связано ни одного блокированного процесса, сигнал будет утерян. Т.е. операция wait должна выпол- няться раньше, чем signal.

Механизм мониторов поддерживается Java. Ключевое слово synchronized гарантирует, что если хотя бы один поток начал выполнение этого метода, ни один другой поток не сможет выполнять другой синхронизированный метод данного класса. Т.е. идет поддержка механизма мониторов на уровне языка, что отсутствует в C. Решение задачи производители- потребители с помощью мониторов на Java:

{wait();}   // ожидание с обработкой исключения catch (InterruptedException exc) {};}}}

Внешний класс ProducerConsumer создает и запускает два потока. Класс монитора содержит два синхронизированных пото- ка, используемых для текущего помещения элементов в буфер и извлечения их оттуда. Поскольку эти методы синхронизи- рованы, то состояние состязания исключается автоматически средствами языка программирования. Переменная Count от- слеживает количество элементов в буфере, lo – содержит индекс, откуда надо извлекать элемент, hi – куда помещать. Если lo=hi, то в буфере или нет элементов, или он заполнен полностью, что можно отследить с помощью count. Синхронизиро- ванные методы в Java несколько отличаются от классических мониторов тем, что у них отсутствует переменная состояния. Взамен предлагаются аналогичные процедуры wait и notify.

Доступ к разделяемым переменным всегда ограничен телом монитора, что автоматически исключает критические интерва- лы. Монитор является пассивным объектом в том смысле, что это не процесс, его процедуры выполняются только по требо- ванию процессов. Мониторы обладают следующими свойствами:

-          Высокая гибкость при реализации синхронизирующих операций

-          Локализация разделяемых переменных в теле монитора позволяет вынести специфические синхронизирующие кон- струкции из параллельных процессов

-          Процессы имеют возможность совместно использовать модули, имеющие критические секции

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

Volatile. Даже если синхронизация успешно решена без помощи специальных механизмов, этого может быть недостаточно, если используются оптимизирующая компиляция программы. В этом случае измененное значение переменной может остав- ляться в регистре процессора, а не заноситься сразу в заданную ячейку памяти, что опять приводит к гонкам. В стандарте ANSI C описан спецификатор volatile позволяющий гарантировать, что переменная после изменения будет возвращена в па- мять.

Проблема обедающих философов. Решение:

{if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING) {state[i]=EATING;             // есть

                  V(&s[i]);}}                                    // философ не использует и не требует вилок

Задача читатели-писатели. Ситуация типична при доступе к БД. Например, бронирование билетов. В системе есть процес- сы-читатели, которые только читают какую-то общую для всех информацию, и писатели, которые могут ее изменять. Чтение может быть разрешено одновременно, однако при записи доступ для всех процессов, в. т.ч. и на чтение, должен быть закрыт. Решение:

                {P(&mutex);                     // закрыть доступ к счетчику читателей

Первый читатель закрывает доступ к БД. Остальные всего лишь увеличивают счетчик читателей. Когда базу покинет по- следний читатель, он открывает к ней доступ. Если один читатель уже работает с базой, второй тоже получит к ней доступ и

т.д. Если в этот момент доступ запросит писатель, он перейдет к ожиданию, поскольку доступ закрыт. Доступ писатель по- лучит только когда базу покинет последний читатель.

Пусть одновременно начали работу 2 читателя и 1 писатель. Ч2 успевает первым получить доступ к счетчику rc, наращивает его. Ч1 ожидает доступа к rc. Ч2 получает доступ к БД, открывает доступ к счетчику. Ч1 разблокируется. В этот момент дис- петчер включает писателя. Тот блокируется на доступе к БД. Ч1 получает доступ к счетчику, увеличивает его. Поскольку rc=2, блокировки на БД не происходит, хотя доступ к БД закрыт. Ч1 заканчивает чтение, уменьшает счетчик, однако БД не открывает, поскольку rc=1. Ч2 читает данные, уменьшает счетчик, открывает доступ к БД. Писатель продолжает работу. Ес- ли бы П активировался когда оба читателя не дошли до блокировки базы, он бы начал работу, захватив db. Ч2 был бы забло- кирован на db, Ч1 соответственно на mutex. После освобождения db писателем, Ч2 продолжил бы работу, захватив доступ к БД, далее разблокировал бы mutex, и Ч1 также смог бы продолжить работу. Однако такое решение позволяет получить дос- туп вновь прибывающим читателям, даже если в системе есть ожидающий писатель. В результате он может ожидать беско- нечно.

Задача о парикмахерской. Есть парикмахерская, в ней один парикмахер, его кресло и n стульев для посетителей. Если его услугами никто не пользуется, он спит, сидя в своем кресле. Когда приходит клиент, он должен разбудить парикмахера. Ес- ли клиент приходит, а мастер занят, то клиент либо садится на стул, если есть место, либо уходит, когда места нет. Требует- ся избежать состояния состязания. Решение:

#define CHAIRS 5 // кол-во стульев typedef int semaphore;

semaphore customers=0; // Кол-во ожидающих посетителей semaphore barbers=0; // Кол-во брадобреев, готовых к работе

semaphore mutex=1;             // Для взаимного исключения int waiting=0; // ожидающие посетители

             void barber(void)               // брабобрей

Для подсчета ожидающих посетителей используется семафор customers, при этом обслуживаемый клиент не учитывается. Barbers, кол-во готовых к работе брадобреев. Waiting фактически дублирует семафор customers, поскольку прочитать значе- ние семафора невозможно, а приходящий посетитель должен знать сколько их в очереди, и если стульев больше, то остаться для ожидания.

Начал работу процесс парикмахер. Он пытается получить доступ к посетителю, и уходит в ожидание, поскольку семафор =0. Приходит первый посетитель, запрашивает доступ к счетчику, увеличивает его, открывает семафор, открывает доступ к счетчику, пытается получить доступ к парикмахеру. Поскольку семафор customer уже открыт, мастер просыпается, получает доступ к счетчику, уменьшает его, открывает семафор burber, открывает доступ к счетчику. Теперь посетитель получает дос- туп к услугам. Приходит 2 клиент. Получает доступ к счетчику, увеличивает его, увеличивает семафор customers, освобож- дает доступ к счетчику. Мастер обслуживает первого клиента, пытается обслужить второго. Поскольку посетитель есть, то запрашивается доступ к счетчику, счетчик уменьшается, открывается семафор парикмахера, освобождает счетчик. Второй посетитель пытается получить доступ в кресло парикмахера и получает его. Посетитель уходит. Парикмахер вновь пытается пригласить клиента. Их нет, и он переходит к ожиданию.