Билет 31. «Обедающие философы»
Пять философов собираются за круглым столом, перед каждым из них стоит блюдо со спагетти, и между каждыми двумя соседями лежит вилка. Каждый из философов некоторое время размышляет, затем берет две вилки (одну в правую руку, другую в левую) и ест спагетти, затем опять размышляет и так далее. Каждый из них ведет себя независимо от других, однако вилок запасено ровно столько, сколько философов, хотя для еды каждому из них нужно две. Таким образом, философы должны совместно использовать имеющиеся у них вилки (ресурсы). Задача состоит в том, чтобы найти алгоритм, который позволит философам организовать доступ к вилкам таким образом, чтобы каждый имел возможность насытиться, и никто не умер с голоду.
Алгоритм решения может быть представлен следующим образом:
# define N 5/* количество философов */
# define LEFT (i-1)%N/* номер легого соседа для i-
ого философа */
# define RIGHT (i+1)%N/* номер правого соседа для
i-ого философа*/
# define THINKING 0/* философ думает */
# define HUNGRY 1/* философ голоден */
# define EATING 2/* философ ест */
typedef int semaphore; /* тип данных «семафор» */
int state[N]={0,0,0,0,0};/* массив состояний философов */
semaphore mutex=1;/* семафор для критической секции */
semaphore s[N];/* по одному семафору на философа */
void philosopher (int i)/* i : номер философа от 0 до N-1 */
{
while (TRUE) /* бесконечный цикл */
{
think();/* философ думает */
take_forks(i);/*философ берет обе вилки или блокируется */
eat();/* философ ест */
put_forks(i);/* философ освобожает обе вилки */
|
|
|
}
}
void take_forks(int i) /* i : номер философа от 0 до N-1 */
{
down(mutex);/* вход в критическую секцию */
state[i] = HUNGRY; /*записываем, что i-ый философ голоден */
test(i); /* попытка взять обе вилки */
up(mutex);/* выход из критической секции */
down(s[i]);/* блокируемся, если вилок нет */
}
void put_forks(i)/* i : номер философа от 0 до N-1 */
{
down(mutex);/* вход в критическую секцию */
state[i] = THINKING; /* философ закончил есть */
test(LEFT); /* проверить может ли левый сосед сейчас есть */
test(RIGHT); /* проверить может ли правый сосед сейчас есть*/
up(mutex); /* выход из критической секции */
}
void test(i) /* i : номер философа от 0 до N-1 */
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
{
state[i] = EATING;
up (s[i]);
}
}
Билет 32. Задача «читателей и писателей»
Другой классической задачей синхронизации доступа к ресурсам является проблема «читателей и писателей», иллюстрирующая широко распространенную модель совместного доступа к данным. Представьте себе ситуацию, например, в системе резервирования билетов, когда множество конкурирующих процессов хотят читать и обновлять одни и те же данные. Несколько процессов могут читать данные одновременно, но когда один процесс начинает записывать данные (обновлять базу данных проданных билетов), ни один другой процесс не должен иметь доступ к данным, даже для чтения. Вопрос, как спланировать работу такой системы? Одно из решений представлено ниже:
|
|
|
typedef int semaphore; /* тип данных «семафор» */
semaphore mutex = 1;/* контроль за доступом к «rc»
(разделямый ресурс) */
semaphore db = 1;/* контроль за доступом к базе
данных */
int rc = 0;/* кол-во процессов читающих или пишущих
*/
void reader (void)
{
while (TRUE)/* бесконечный цикл */
{
down(mutex);/* получить эксклюзивный доступ к «rc»*/
rc = rc + 1;
/* еще одним читателем больше */
if (rc == 1) down(db);
/* если это первый читатель, нужно заблокировать эксклюзивный доступ к базе */
up(mutex); /*освободить ресурс rc */
read_data_base();/* доступ к данным */
down(mutex);/*получить эксклюзивный доступ к «rc»*/
rc = rc – 1; /* теперь одним читателем меньше */
if (rc == 0) up(db);/*если это был последний читатель, разблокировать эксклюзивный доступ к базе данных */
up(mutex);/*освободить разделяемый ресурс rc */
use_data_read();/* некритическая секция */
}
}
void writer (void)
{
while(TRUE) /* бесконечный цикл */
{
think_up_data(); /* некритическая секция */
down(db);/* получить эксклюзивный доступ к данным*/
write_data_base();/* записать данные */
up(db);/* отдать эксклюзивный доступ */
}
|
|
|
}
Билет 33.Задача о «спящем парикмахере»
Рассмотрим парикмахерскую, в которой работает один парикмахер, имеется одно кресло для стрижки и несколько кресел в приемной для посетителей, ожидающих своей очереди. Если в парикмахерской нет посетителей, парикмахер засыпает прямо на своем рабочем месте. Появившийся посетитель должен его разбудить, в результате чего парикмахер приступает к работе. Если в процессе стрижки появляются новые посетители, они должны либо подождать своей очереди, либо покинуть парикмахерскую, если в приемной нет свободного кресла для ожидания. Задача состоит в том, чтобы корректно запрограммировать поведение парикмахера и посетителей.
Понадобится целых 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);/* нет свободного кресла для ожидания – придется уйти*/
}
}
Билет. Сигналы.
Сигналы представляют собой средство уведомления процесса о наступлении некоторого события в системе. Инициатором посылки сигнала может выступать как другой процесс, так и сама ОС. Сигналы, посылаемые ОС, уведомляют о наступлении некоторых строго предопределенных ситуаций (как, например, завершение порожденного процесса, прерывание процесса нажатием комбинации Ctrl-C, попытка выполнить недопустимую машинную инструкцию, попытка недопустимой записи в канал и т.п.), при этом каждой такой ситуации сопоставлен свой сигнал. Кроме того, зарезервировано один или несколько номеров сигналов, семантика которых определяется пользовательскими процессами по своему усмотрению (например, процессы могут посылать друг другу сигналы с целью синхронизации).
Количество различных сигналов в современных версиях UNIX около 30, каждый из них имеет уникальное имя и номер. Описания представлены в файле <signal.h>.
Сигналы являются механизмом асинхронного взаимодействия, т.е. момент прихода сигнала процессу заранее неизвестен. Однако процесс может предвидеть возможность получения того или иного сигнала и установить определенную реакцию на его приход. В этом плане сигналы можно рассматривать как программный аналог аппаратных прерываний.
При получении сигнала процессом возможны три варианта реакции на полученный сигнал:
- Процесс реагирует на сигнал стандартным образом, установленным по умолчанию (для большинства сигналов действие по умолчанию – это завершение процесса).
- Процесс может установить специальную обработку сигнала, в этом случае по приходу сигнала вызывается функция-обработчик, определенная процессом (при этом говорят, что сигнал перехватывается)
- Процесс может проигнорировать сигнал.
Для отправки сигнала существует системный вызов kill():
#include <sys/types.h>#include <signal.h>
int kill (pit_t pid, int sig)
Для определения реакции на получение того или иного сигнала в процессе служит системный вызов signal():
#include <signal.h>
void (*signal ( int sig, void (*disp) (int))) (int)
где аргумент sig — номер сигнала, для которого устанавливается реакция, а disp — либо определенная пользователем функция-обработчик сигнала, либо одна из констант: SIG_DFL и SIG_IGN. Первая из них указывает, что необходимо установить для данного сигнала обработку по умолчанию, т.е. стандартную реакцию системы, а вторая — что данный сигнал необходимо игнорировать. При успешном завершении функция возвращает указатель на предыдущий обработчик данного сигнала (он может использоваться процессом, например, для восстановления прежней реакции на сигнал).
Билет. Неименованные каналы.
Одним из простейших средств взаимодействия процессов в операционной системе UNIX является механизм каналов. Неименованный канал есть некая сущность, в которую можно помещать и извлекать данные, для чего служат два файловых дескриптора, ассоциированных с каналом: один для записи в канал, другой — для чтения. Для создания канала служит системный вызов pipe():
int pipe (int *fd)
Данный системный вызов выделяет в оперативной памяти некоторое ограниченное пространство и возвращает че6рез параметр fd массив из двух файловых дескрипторов: один для записи в канал — fd[1], другой для чтения — fd[0].
Эти дескрипторы являются дескрипторами открытых файлов, с которыми можно работать, используя такие системные вызовы как read(), write(), dup()и пр.
Однако существуют различия в организации использования обычного файла и канала.
Особенности организации чтения данных из канала:
· если прочитано меньше байтов, чем находится в канале, оставшиеся сохраняются в канале;
· если делается попытка прочитать больше данных, чем имеется в канале, и при этом существуют открытые дескрипторы записи, ассоциированные с каналом, будет прочитано (т.е. изъято из канала) доступное количество данных, после чего читающий процесс блокируется до тех пор, пока в канале не появится достаточное количество данных для завершения операции чтения;
· процесс может избежать такого блокирования, изменив для канала режим блокировки с использованием системного вызова fcntl(), в этом случае будет считано доступное количество данных, и управление будет сразу возвращено процессу;
· при закрытии записывающей стороны канала, в него помещается символ EOF (т.е. ситуация когда закрыты все дескрипторы, ассоциированные с записью в канал), после этого процесс, осуществляющий чтение, может выбрать из канала все оставшиеся данные и признак конца файла, благодаря которому блокирования при чтении в этом случае не происходит.
Особенности организации записи данных в канал:
· если процесс пытается записать большее число байтов, чем помещается в канал (но не превышающее предельный размер канала) записывается возможное количество данных, после чего процесс, осуществляющий запись, блокируется до тех пор, пока в канале не появится достаточное количество места для завершения операции записи;
· процесс может избежать такого блокирования, изменив для канала режим блокировки с использованием системного вызова fcntl(). В неблокирующем режиме в ситуации, описанной выше, будет записано возможное количество данных, и управление будет сразу возвращено процессу.
· если же процесс пытается записать в канал порцию данных, превышающую предельный размер канала, то будет записано доступное количество данных, после чего процесс заблокируется до появления в канале свободного места любого размера (пусть даже и всего 1 байт), затем процесс разблокируется, вновь производит запись на доступное место в канале, и если данные для записи еще не исчерпаны, вновь блокируется до появления свободного места и т.д., пока не будут записаны все данные, после чего происходит возврат из вызова write()
· если процесс пытается осуществить запись в канал, с которым не ассоциирован ни один дескриптор чтения, то он получает сигнал SIGPIPE (тем самым ОС уведомляет его о недопустимости такой операции).
В стандартной ситуации (при отсутствии переполнения) система гарантирует атомарность операции записи, т. е. при одновременной записи нескольких процессов в канал их данные не перемешиваются.
Билет. Именованные каналы.
Рассмотренные выше программные каналы имеют важное ограничение: т.к. доступ к ним возможен только посредством дескрипторов, возвращаемых при порождении канала, необходимым условием взаимодействия процессов через канал является передача этих дескрипторов по наследству при порождении процесса. Именованные каналы (FIFO-файлы) расширяют свою область применения за счет того, что подключиться к ним может любой процесс в любое время, в том числе и после создания канала. Это возможно благодаря наличию у них имен.
FIFO-файл представляет собой отдельный тип файла в файловой системе UNIX, который обладает всеми атрибутами файла, такими как имя владельца, права доступа и размер. Для его создания в UNIX System V.3 и ранее используется системный вызов mknod(),а в BSD UNIX и System V.4 – вызовmkfifo()(этот вызов поддерживается и стандартом POSIX):
int mknod (char *pathname, mode_t mode, dev)
int mkfifo (char *pathname, mode_t mode)
В обоих вызовах первый аргумент представляет собой имя создаваемого канала, во втором указываются права доступа к нему для владельца, группы и прочих пользователей, и кроме того, устанавливается флаг, указывающий на то, что создаваемый объект является именно FIFO-файлом (в разных версиях ОС он может иметь разное символьное обозначение – S_IFIFO или I_FIFO). Третий аргумент вызова mknod() игнорируется.
После создания именованного канала любой процесс может установит с ним связь посредством системного вызова open(). При этом действуют следующие правила:
- если процесс открывает FIFO-файл для чтения, он блокируется до тех пор, пока какой-либо процесс не откроет тот же канал на запись
- если процесс открывает FIFO-файл на запись, он будет заблокирован до тех пор, пока какой-либо процесс не откроет тот же канал на чтение
- процесс может избежать такого блокирования, указав в вызове open() специальный флаг (в разных версиях ОС он может иметь разное символьное обозначение – O_NONBLOCK или O_NDELAY). В этом случае в ситуациях, описанных выше, вызов open() сразу же вернет управление процессу
Правила работы с именованными каналами, в частности, особенности операций чтения-записи, полностью аналогичны неименованным каналам.
Ниже рассматривается пример, где один из процессов является сервером, предоставляющим некоторую услугу, другой же процесс, который хочет воспользоваться этой услугой, является клиентом. Клиент посылает серверу запросы на предоставление услуги, а сервер отвечает на эти запросы.
Дата добавления: 2018-08-06; просмотров: 461; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!