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

Еще одна классическая задача на синхронизацию процессов – это так называемая «задача о спящем парикмахере» [2]. Рассмотрим парикмахерскую, в которой работает один парикмахер, имеется одно кресло для стрижки и несколько кресел в приемной для посетителей, ожидающих своей очереди. Если в парикмахерской нет посетителей, парикмахер засыпает прямо на своем рабочем месте. Появившийся посетитель должен его разбудить, в результате чего парикмахер приступает к работе. Если в процессе стрижки появляются новые посетители, они должны либо подождать своей очереди, либо покинуть парикмахерскую, если в приемной нет свободного кресла для ожидания. Задача состоит в том, чтобы корректно запрограммировать поведение парикмахера и посетителей.

Одно из возможных решений этой задачи представлено ниже. Процедура barber() описывает поведение парикмахера (она включает в себя бесконечный цикл – ожидание клиентов и стрижку). Процедура customer() описывает поведение посетителя. Несмотря на кажущуюся простоту задачи, понадобится целых 3 семафора: customers – подсчитывает количество посетителей, ожидающих в очереди, barbers – обозначает количество свободных парикмахеров (в случае одного парикмахера его значение либо 0, либо 1) и mutex – используется для синхронизации доступа к разделяемой переменной waiting. Переменная waiting, как и семафор customers, содержит количество посетителей, ожидающих в очереди, она используется в программе для того, чтобы иметь возможность проверить, имеется ли свободное кресло для ожидания, и при этом не заблокировать процесс, если кресла не окажется. Заметим, что как и в предыдущем примере, эта переменная является разделяемым ресурсом, и доступ к ней охраняется семафором mutex. Это необходимо, так как для обычной переменной, в отличие от семафора, чтение и последующее изменение не являются неделимой операцией.

#define CHAIRS 5

typedef int semaphore; /* тип данных «семафор» */

semaphore customers = 0; /* посетители, ожидающие в очереди */

semaphore barbers = 0; /* парикмахеры, ожидающие посетителей */

semaphore mutex = 1; /* контроль за доступом к переменной waiting */

int waiting = 0;

void barber()

{

while (true) {

down(customers); /* если customers == 0, т.е. посетителей нет, то заблокируемся до появления посетителя */

down(mutex); /* получаем доступ к waiting */

waiting = wating – 1; /* уменьшаем кол-во ожидающих клиентов */

up(barbers); /* парикмахер готов к работе */

up(mutex); /* освобождаем ресурс waiting */

cut_hair(); /* процесс стрижки */

}

void customer()

{

down(mutex); /* получаем доступ к waiting */

if (waiting < CHAIRS) /* есть место для ожидания */

{

waiting = waiting + 1; /* увеличиваем кол-во ожидающих клиентов */

up(customers); /* если парикмахер спит, это его разбудит */

up(mutex); /* освобождаем ресурс waiting */

down(barbers); /* если парикмахер занят, переходим в состояние ожидания, иначе – занимаем парикмахера*/

get_haircut(); /* процесс стрижки */

}

else

{

up(mutex); /* нет свободного кресла для ожидания – придется уйти */

}

}

БИЛЕТ 36 Сигналы. Примеры программирования.

Сигналы.

Сигналы представляют собой средство уведомления процесса о наступлении некоторого события в системе. Инициатором посылки сигнала может выступать как другой процесс, так и сама ОС. Сигналы, посылаемые ОС, уведомляют о наступлении некоторых строго предопределенных ситуаций (как, например, завершение порожденного процесса, прерывание процесса нажатием комбинации Ctrl-C, попытка выполнить недопустимую машинную инструкцию, попытка недопустимой записи в канал и т.п.), при этом каждой такой ситуации сопоставлен свой сигнал. Кроме того, зарезервирован один или несколько номеров сигналов, семантика которых определяется пользовательскими процессами по своему усмотрению (например, процессы могут посылать друг другу сигналы с целью синхронизации).

Количество различных сигналов в современных версиях UNIX около 30, каждый из них имеет уникальное имя и номер. Описания представлены в файле <signal.h>. В таблице приведено несколько примеров сигналов[1]:

Числовое значение	Константа	Значение сигнала
	SIGINT	Прерывание выполнения по нажатию Ctrl-C
	SIGQUIT	Аварийное завершение работы
	SIGKILL	Уничтожение процесса
	SIGALRM	Прерывание от программного таймера
	SIGCHLD	Завершился процесс-потомок

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

При получении сигнала процессом возможны три варианта реакции на полученный сигнал:

- Процесс реагирует на сигнал стандартным образом, установленным по умолчанию (для большинства сигналов действие по умолчанию – это завершение процесса).

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

- Процесс может проигнорировать сигнал.

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

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

Отдельного рассмотрения заслуживает ситуация, когда сигнал приходит в момент выполнения системного вызова. Обработка такой ситуации в разных версиях UNIX реализована по-разному, например, обработка сигнала может быть отложена до завершения системного вызова; либо системный вызов автоматически перезапускается после его прерывания сигналом; либо системный вызов вернет –1, а в переменной errno будет установлено значение EINTR

Для отправки сигнала существует системный вызов kill():

#include <sys/types.h>

#include <signal.h>

int kill(pid_t pid, int sig)

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

Во втором параметре передается номер посылаемого сигнала. Если этот параметр равен 0, то будет выполнена проверка корректности обращения к kill() (в частности, существование процесса с идентификатором pid), но никакой сигнал в действительности посылаться не будет.

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

Для определения реакции на получение того или иного сигнала в процессе служит системный вызов signal():

#include <signal.h>

void (*signal( int sig, void (*disp) (int))) (int)

где аргумент sig — номер сигнала, для которого устанавливается реакция, а disp — либо определенная пользователем функция-обработчик сигнала, либо одна из констант: SIG_DFL и SIG_IGN. Первая из них указывает, что необходимо установить для данного сигнала обработку по умолчанию, т.е. стандартную реакцию системы, а вторая — что данный сигнал необходимо игнорировать. При успешном завершении функция возвращает указатель на предыдущий обработчик данного сигнала (он может использоваться процессом, например, для восстановления прежней реакции на сигнал).

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

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

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

II. Обработка сигнала.

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

#include <sys/types.h>

#include <signal.h>

#include <stdio.h>

int count = 0;

void SigHndlr (int s) /* обработчик сигнала */

{

printf("\n I got SIGINT %d time(s) \n",

++ count);

if (count == 5) signal (SIGINT, SIG_DFL);

/* ставим обработчик сигнала по умолчанию */

else signal (SIGINT, SigHndlr);

/* восстанавливаем обработчик сигнала */

}

int main(int argc, char **argv)

{

signal (SIGINT, SigHndlr); /* установка реакции на сигнал */

while (1); /*”тело программы” */

return 0;

}

III. Программа “Будильник”.

Программа “Будильник”. Существуют задачи, в которых необходимо прервать выполнение процесса по истечении некоторого количества времени. Средствами ОС “заводится” будильник, который будет поторапливать ввести некоторое имя. Системный вызов alarm():

#include <unistd.h>

unsigned int alarm(unsigned int seconds);

инициализирует отложенное появление сигнала SIGALRM - процесс запрашивает ядро отправить ему самому сигнал по прошествии определенного времени.

#include <unistd.h>

#include <signal.h>

#include <stdio.h>

void alrm(int s) /*обработчик сигнала SIG_ALRM */

{

printf(“\n жду имя \n”);

alarm(5); /* заводим будильник */

signal(SIGALRM, alrm); /* переустанавливаем реакцию на сигнал */

}

int main(int argc, char **argv)

{

char s[80];

signal(SIGALRM, alrm);

/* установка обработчика alrm на приход сигнала SIG_ALRM */

alarm(5); /* заводим будильник */

printf(“Введите имя \n”);

for (;;)

{

printf(“имя:”);

if (gets(s) != NULL) break; /* ожидаем ввода имени */

};

printf(“OK! \n”);

return 0;

}

В начале программы мы устанавливаем реакцию на сигнал SIGALRM - функцию alrm(), далее мы заводим будильник, запрашиваем “Введите имя” и ожидаем ввода строки символов. Если ввод строки задерживается, то будет вызвана функция alrm(), которая напомнит, что программа “ждет имя”, опять заведет будильник и поставит себя на обработку сигнала SIGALRM еще раз. И так будет до тех пор, пока не будет введена строка. Здесь имеется один нюанс: если в момент выполнения системного вызова возникает событие, связанное с сигналом, то система прерывает выполнение системного вызова и возвращает код ответа, равный «-1».

IV. Двухпроцессный вариант программы “Будильник”.

#include <signal.h>

#include <sys/types.h>

#include <unistd.h>

#include <stdio.h>

void alr(int s)

{

printf(“\n Быстрее!!! \n”);

signal(SIGALRM, alr);

/* переустановка обработчика alr на приход сигнала SIGALRM */

}

int main(int argc, char **argv)

{

char s[80];

int pid;

signal(SIGALRM, alr);

/* установка обработчика alr на приход сигнала SIGALRM */

if (pid = fork()) {

for (;;)

{

sleep(5); /*приостанавливаем процесс на 5 секунд */

kill(pid, SIGALRM);

/*отправляем сигнал SIGALRM процессу- сыну */

}

}

else {

printf(“Введите имя \n”);

for (;;)

{

printf(“имя:”);

if (gets(s) != NULL) break; /*ожидаем ввода имени*/

}

printf(“OK!\n”);

kill(getppid(), SIGKILL);

/* убиваем зациклившегося отца */

}

return 0;

}

В данном случае программа реализуется в двух процессах. Как и в предыдущем примере, имеется функция реакции на сигнал alr(), которая выводит на экран сообщение и переустанавливает функцию реакции на сигнал опять же на себя. В основной программе мы также указываем alr() как реакцию на SIGALRM. После этого мы запускаем сыновний процесс, и отцовский процесс (бесконечный цикл) “засыпает” на 5 единиц времени, после чего сыновнему процессу будет отправлен сигнал SIGALRM. Все, что ниже цикла, будет выполняться в процессе-сыне: мы ожидаем ввода строки, если ввод осуществлен, то происходит уничтожение отца (SIGKILL).