Самодел 2 (1114717), страница 10
Текст из файла (страница 10)
Двоичный семафор - семафор, начальное (и максимальное) значение которого равно единице. То есть двоичный семафор может иметь значения только 0 и 1.
Использование двоичного семафора для организации взаимного исключения проиллюстрировано на рисунке.
С
емафоры – это низкоуровневые средства синхронизации, для корректной практической реализации которых необходимо наличие специальных, атомарных семафорных машинных команд.
Мониторы
Монитор - языковая конструкция, т.е. некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор – это совокупность процедур и структур данных, объединенных в программный модуль специального типа.
Идея монитора была впервые сформулирована в 1974 г. Хоаром. В отличие от других средств, монитор представляет собой языковую конструкцию, т. е. Некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор представляет собой совокупность процедур и структур данных, объединенных в программный модуль специального типа.
Три основных свойства монитора:
-
структуры данных, входящие в монитор, могут быть доступны только для процедур, входящих в этот монитор (таким образом, монитор представляет собой некоторый аналог объекта в объектно-ориентированных языках и реализует инкапсуляцию данных);
-
процесс «входит» в монитор путем вызова одной из его процедур;
-
в любой момент времени внутри монитора может находиться не более одного процесса. Если процесс пытается попасть в монитор, в котором уже находится другой процесс, он блокируется. Таким образом, чтобы защитить разделяемые структуры данных, из достаточно поместить внутрь монитора вместе с процедурами, представляющими критические секции для их обработки.
Монитор представляет собой конструкцию языка программирования, и компилятору известно о том, что входящие в него процедуры и данные имеют особую семантику, поэтому первое условие может проверяться еще на этапе компиляции, кроме того, код для процедур монитора тоже может генерироваться особым образом, чтобы удовлетворялось третье условие. Поскольку организация взаимного исключения в данном случае возлагается на компилятор, а количество программных ошибок, связанных с организацией взаимного исключения, сводится к минимуму.
Если монитор занят, то пытающиеся его занять другие процессы блокируются, и может возникнуть очередь заблокированных процессов.
Бытовой пример монитора – кабина с телефоном. Если желающих позвонить нет, то кабина (монитор) свободна и телефон (ресурс) не занят. Как только появляется желающий, он занимает кабину и телефон. Если в это время появляются другие желающие, то они уже не смогут занять кабину и телефон (блокируются) до тех пор, пока предыдущий не освободит ее.
Обмен сообщениями
Обмен сообщениями – средство, решающее проблему синхронизации:
-
для однопроцессорных систем и систем с общей памятью
-
для распределенных систем (когда каждый процессор имеет доступ только к своей памяти)
Основная функциональность метода обеспечивается двумя примитивами (являющимися, как и семафоры, в отличие от мониторов, системными вызовами, а не конструкциями языка):
Посылка сообщения: send (destination, message)
Прием сообщения: receive (source, message)
Основные особенности, которыми может обладать та или иная система обмена сообщениями:
-
Синхронизация
- Операции посылки/приема сообщения могут быть блокирующими и неблокирующими.
Неблокирующий send – сообщение всегда отправляется, причем оно может потом быть прочтено, а может и нет. Блокирующий send – процесс блокируется, пока кто-нибудь не прочитает его сообщение.
Блокирующий receive – если нет сообщения для прочтения, то процесс блокируется. Неблокирующий receive – или получит сообщение, или код о том, что сообщения нет, и тут же продолжает выполнение процесса.
-
Модель рандеву – блокирующий send, блокирующий receive
Не требует реализации очереди сообщений и может быть использована в реализации сообщений.
-
Неблокирующий send, блокирующий receive
Используется в моделях Клиент-Сервер (сервер может блокироваться, а клиент - нет).
-
Неблокирующий send, неблокирующий receive
Есть проблема организации буферизации.
Если send неблокирующий, то процесс-отправитель не знает, дошло ли его сообщение до получателя или нет. В этих случаях часто используют отчеты о доставке сообщения.
Блокирующий receive плох, если сообщение потеряно – может произойти зависание процесса.
Симметричное взаимодействие: участники имеют примерно одинаковые права.
Это был вопрос, связанный с синхронизацией. Рассмотрим остальные:
-
Адресация
-
Прямая (ID процесса)
-
Получатель сообщения однозначно определен.
Явная – каждый из процессов имеет свое имя и при отправке явно указывается, кому оно.
Неявная – допустима при взаимодействии между сыном и отцом, т.е. можно не указывать ID явно.
Точно так же это применимо к получению: например процесс может заявить «дайте сообщение от такого-то ID»
-
Косвенная (почтовый ящик, или очередь сообщений)
Нет указания, кому/от кого сообщение. Обычно есть буферизация (почтовый ящик или очередь сообщений). Получатель по определенной стратегии (например, очередь или стек) выбирает оттуда сообщения.
-
Длина сообщения
Сообщения могут быть фиксированного или произвольного размера. Последнее предполагает передачу внутри себя информации о своей длине.
Классические задачи синхронизации процессов
«Обедающие философы»
П
ять философов собираются за круглым столом, перед каждым из них стоит блюдо со спагетти, и между каждыми двумя соседями лежит вилка. Каждый из философов некоторое время размышляет, затем берет две вилки (одну в правую руку, другую в левую) и ест спагетти, затем опять размышляет и так далее. Каждый из них ведет себя независимо от других, однако вилок запасено ровно столько, сколько философов, хотя для еды каждому из них нужно две. Таким образом, философы должны совместно использовать имеющиеся у них вилки (ресурсы). Задача состоит в том, чтобы найти алгоритм, который позволит философам организовать доступ к вилкам таким образом, чтобы каждый имел возможность насытиться, и никто не умер с голоду.
Рассмотрим простейшее решение, использующее семафоры. Когда один из философов хочет есть, он берет вилку слева от себя, если она в наличии, а затем - вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места. Данный алгоритм может быть представлен следующим способом:
#define N 5 /* число философов*/
void philosopher (int i) /* i – номер философа от 0 до 4*/
{
while (TRUE)
{
think(); /*философ думает*/
take_fork(i); /*берет левую вилку*/
take_fork((i+1)%N); /*берет правую вилку*/
eat(); /*ест*/
put_fork(i); /*кладет обратно левую вилку*/
put_fork((i+1)%N); /* кладет обратно правую вилку */
}
}
Функция take_fork(i) описывает поведение философа по захвату вилки: он ждет, пока указанная вилка не освободится, и забирает ее.
Вышеобозначенное решение может привести к тупиковой ситуации. Что произойдет, если все философы захотят есть в одно и то же время? Каждый из них получит доступ к своей левой вилке и будет находиться в состоянии ожидания второй вилки до бесконечности. Другим решением может быть алгоритм, который обеспечивает доступ к вилкам только четырем из пяти философов. Тогда всегда среди четырех философов, по крайней мере, один будет иметь доступ к двум вилкам. Данное решение не имеет тупиковой ситуации. Алгоритм решения может быть представлен следующим образом:
# 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]; /* массив состояний каждого из философов */
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]);
}
}
Задача «читателей и писателей»
Другой классической задачей синхронизации доступа к ресурсам является проблема «читателей и писателей», иллюстрирующая широко распространенную модель совместного доступа к данным. Представьте себе ситуацию, например, в системе резервирования билетов, когда множество конкурирующих процессов хотят читать и обновлять одни и те же данные. Несколько процессов могут читать данные одновременно, но когда один процесс начинает записывать данные (обновлять базу данных проданных билетов), ни один другой процесс не должен иметь доступ к данным, даже для чтения. Вопрос, как спланировать работу такой системы? Одно из решений представлено ниже:
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); /* отдать эксклюзивный доступ */
}
}
Надо заметить, что приведенный алгоритм дает преимущество при доступе к базе данных процессам-читателям, т.к. процесс, ожидающий доступа по записи, будет ждать до тех пор, пока все читающие процессы не окончат работу, и если в это время появляется новый читающий процесс, он тоже беспрепятственно получит доступ. Чтобы этого избежать, можно модифицировать алгоритм таким образом, чтобы в случае, если имеется хотя бы один ожидающий процесс-писатель, новые процессы-читатели не получали доступа к ресурсу, а ожидали, когда процесс-писатель обновит данные. Однако, обратная сторона данного решения в том, что оно несколько снижает производительность процессов-читателей, т.к. вынуждает их ждать в тот момент, когда ресурс не занят в эксклюзивном режиме.
Задача о «спящем парикмахере»
Рассмотрим парикмахерскую, в которой работает один парикмахер, имеется одно кресло для стрижки и несколько кресел в приемной для посетителей, ожидающих своей очереди. Если в парикмахерской нет посетителей, парикмахер засыпает прямо на своем рабочем месте. Появившийся посетитель должен его разбудить, в результате чего парикмахер приступает к работе. Если в процессе стрижки появляются новые посетители, они должны либо подождать своей очереди, либо покинуть парикмахерскую, если в приемной нет свободного кресла для ожидания. Задача состоит в том, чтобы корректно запрограммировать поведение парикмахера и посетителей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
