Вордовские лекции (1115151), страница 5
Текст из файла (страница 5)
Рассмотрим ситуацию, изображенную на Рис. 1:
Рис. 1 Конкуренция процессов за ресурс.
В этом случае символ, считанный процессом А, был потерян, а символ, считанный процессом В, был выведен дважды. Результат выполнения процессов здесь зависит от того, в какой момент осуществляется переключение процессов, и от того, какой конкретно процесс будет выбран для выполнения следующим. Такие ситуации называются гонками (race conditions) между процессами, а процессы – конкурирующими. Единственный способ избежать гонок при использовании разделяемых ресурсов – контролировать доступ к любым разделяемым ресурсам в системе. При этом необходимо организовать взаимное исключение – т.е. такой способ работы с разделяемым ресурсом, при котором постулируется, что в тот момент, когда один из процессов работает с разделяемым ресурсом, все остальные процессы не могут иметь к нему доступ.
Проблему организации взаимного исключения можно сформулировать в более общем виде. Часть программы (фактически набор операций), в которой осуществляется работа с критическим ресурсом, называется критической секцией, или критическим интервалом. Задача взаимного исключения в этом случае сводится к тому, чтобы не допускать ситуации, когда два процесса одновременно находятся в критических секциях, связанных с одним и тем же ресурсом.
Заметим, что вопрос организации взаимного исключения актуален не только для взаимосвязанных процессов, совместно использующих определенные ресурсы для обмена информацией. Выше отмечалось, что возможна ситуация, когда процессы, не подозревающие о существовании друг друга, используют глобальные ресурсы системы, такие как устройства ввода/вывода, принтеры и т.п. В с этом случае имеет место конкуренция за ресурсы, доступ к которым также должен быть организован по принципу взаимного исключения.
При организации взаимного исключения могут возникнуть тупики (deadlocks), ситуации в которой конкурирующие за критический ресурс процессы вступают в клинч – безвозвратно блокируются.
Есть два процесса А и В, каждому из которых в некоторый момент требуется иметь доступ к двум ресурсам R1 и R2. Процесс А получил доступ к ресурсу R1, и следовательно, никакой другой процесс не может иметь к нему доступ, пока процесс А не закончит с ним работать. Одновременно процесс В завладел ресурсом R2. В этой ситуации каждый из процессов ожидает освобождения недостающего ресурса, но оба ресурса никогда не будут освобождены, и процессы никогда не смогут выполнить необходимые действия.
Далее мы рассмотрим различные механизмы организации взаимного исключения для синхронизации доступа к разделяемым ресурсам и обсудим достоинства, недостатки и области применения этих подходов.
Рассмотри классические методы (средства) синхронизации.
4.2.3.1Семафоры Дейкстры
Тип данных, именуемый семафором. Семафор представляет собой переменную целого типа S, над которой определены две операции: down(s) (или P(S)) и up(S) (или V(S)). Оригинальные обозначения P и V, данные Дейкстрой и получившие широкое распространение в литературе, являются сокращениями голландских слов proberen – проверить и verhogen – увеличить.
Операция down(S) проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной. Важно отметить, что вся операция является неделимой, т. е. Проверка значения, его уменьшение и, возможно, блокирование процесса производится как одно атомарное действие, которое не может быть прервано. Операция up(S) увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т. е. Вновь уменьшил значение семафора. При этом также постулируется, что увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией.
Чтобы прокомментировать работу семафора рассмотрим пример. Представим себе супермаркет, посетители которого прежде чем войти в торговый зал должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая количество тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N=1, получим реализацию взаимного исключения. Семафор, начальное (и максимальное) значение которого равно 1, называется двоичным семафором (т. к. имеет только 2 состояния: 0 и 1).
Семафоры – это низкоуровневые средства синхронизации, для корректной практической реализации которых необходимо наличие специальных, атомарных семафорных машинных команд.
4.2.3.2Мониторы Хоара
Идея монитора была впервые сформулирована в 1974 г. Хоаром. В отличие от других средств, монитор представляет собой языковую конструкцию, т. е. Некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор представляет собой совокупность процедур и структур данных, объединенных в программный модуль специального типа. Постулируются три основных свойства монитора:
-
структуры данных, входящие в монитор, могут быть доступны только для процедур, входящих в этот монитор (таким образом, монитор представляет собой некоторый аналог объекта в объектно-ориентированных языках и реализует инкапсуляцию данных);
-
процесс «входит» в монитор путем вызова одной из его процедур;
-
в любой момент времени внутри монитора может находиться не более одного процесса. Если процесс пытается попасть в монитор, в котором уже находится другой процесс, он блокируется. Таким образом, чтобы защитить разделяемые структуры данных, из достаточно поместить внутрь монитора вместе с процедурами, представляющими критические секции для их обработки.
Монитор представляет собой конструкцию языка программирования и компилятору известно о том, что входящие в него процедуры и данные имеют особую семантику, поэтому первое условие может проверяться еще на этапе компиляции, кроме того, код для процедур монитора тоже может генерироваться особым образом, чтобы удовлетворялось третье условие. Поскольку организация взаимного исключения в данном случае возлагается на компилятор, количество программных ошибок, связанных с организацией взаимного исключения, сводится к минимуму.
4.2.4Классические задачи синхронизации процессов
4.2.4.1«Обедающие философы»
|
|
| "Обедающие философы" |
Пять философов собираются за круглым столом, перед каждым из них стоит блюдо со спагетти, и между каждыми двумя соседями лежит вилка. Каждый из философов некоторое время размышляет, затем берет две вилки (одну в правую руку, другую в левую) и ест спагетти, затем опять размышляет и так далее. Каждый из них ведет себя независимо от других, однако вилок запасено ровно столько, сколько философов, хотя для еды каждому из них нужно две. Таким образом, философы должны совместно использовать имеющиеся у них вилки (ресурсы). Задача состоит в том, чтобы найти алгоритм, который позволит философам организовать доступ к вилкам таким образом, чтобы каждый имел возможность насытиться, и никто не умер с голоду.
Рассмотрим простейшее решение, использующее семафоры. Когда один из философов хочет есть, он берет вилку слева от себя, если она в наличии, а затем - вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места. Данный алгоритм может быть представлен следующим способом:
#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]);
}
}
4.2.4.2Задача «читателей и писателей»
Другой классической задачей синхронизации доступа к ресурсам является проблема «читателей и писателей», иллюстрирующая широко распространенную модель совместного доступа к данным. Представьте себе ситуацию, например, в системе резервирования билетов, когда множество конкурирующих процессов хотят читать и обновлять одни и те же данные. Несколько процессов могут читать данные одновременно, но когда один процесс начинает записывать данные (обновлять базу данных проданных билетов), ни один другой процесс не должен иметь доступ к данным, даже для чтения. Вопрос, как спланировать работу такой системы? Одно из решений представлено ниже:
typedef int semaphore; /* некий семафор */
semaphore mutex = 1; /* контроль за доступом к «rc» (разделямый ресурс) */
semaphore db = 1; /* контроль за доступом к базе данных*/
int rc = 0; /* кол-во процессов читающих или пишущих */
void reader (void)
{
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
