The design of the UNIX Operating System 29 страница
Для того чтобы не допустить возникновения подобных проблем, были разработаны различные механиз-мы синхронизации более высокого уровня. Описанию ряда из них – семафоров, мониторов и сообщений
– и посвящена данная лекция.
Семафоры
Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.
Концепция семафоров
Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ лю-бого процесса к которой, за исключением момента ее инициализации, может осуществляться только че-рез две атомарные операции: P ( от датского слова proberen – проверять) и V (от verhogen – увеличивать). Классическое определение этих операций выглядит следующим образом:
|
|
|
P(S): пока S == 0 процесс блокируется;
S = S – 1;
|
|
|
V(S): S = S + 1;
Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение . Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокирует-ся до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1. В момент создания семафор может быть инициали-зирован любым неотрицательным значением.
|
|
|
Подобные переменные-семафоры могут с успехом применяться для решения различных задач организа-ции взаимодействия процессов. В ряде языков программирования они были непосредственно введены в
синтаксис языка (например, в ALGOL-68), в других случаях реализуются с помощью специальных сис-темных вызовов. Соответствующая целая переменная располагается внутри адресного пространства ядра операционной системы. Операционная система обеспечивает атомарность операций P и V, используя,
|
|
|
| Основы операционных систем | 59 |
например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблоки-рования может быть произвольным, например, FIFO.
Решение проблемы producer-consumer с помощью семафоров
Одной из типовых задач, требующих организации взаимодействия процессов, является задача producer-consumer (производитель-потребитель). Пусть два процесса обмениваются информацией через буфер ог-раниченного размера . Производитель закладывает информацию в буфер , а потребитель извлекает ее от-туда. На этом уровне деятельность потребителя и производителя можно описать следующим образом.
Producer: while(1) { produce_item; put_item;
}
Consumer: while(1) { get_item; consume_item;
}
Если буфер заполнен, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то потребитель должен дожидаться нового сообщения. Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора: empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появит-ся информация. Семафор empty будем использовать для организации ожидания производителя при за-полненном буфере, а семафор mutex – для организации взаимоисключения на критических участках, ко-торыми являются действия put_item и get_item (операции "положить информацию" и "взять информа-цию" не могут пересекаться, так как в этом случае возникнет опасность искажения информации). Тогда решение задачи на C-подобном языке выглядит так:
Semaphore mutex = 1;
Semaphore empty = N; /* где N – емкость буфера*/ Semaphore full = 0;
Producer: while(1) {
produce_item; P(empty); P(mutex); put_item; V(mutex); V(full);
}
Consumer: while(1) {
P(full);
P(mutex); get_item; V(mutex); V(empty); consume_item;
Дата добавления: 2021-01-21; просмотров: 122; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!