|
|
Решение классических задач синхронизации с помощью семафоровЗадача "ограниченный буфер". Имеются три классических задачи синхронизации процессов, решения которых с помощью семафоров мы рассмотрим:
 В данном разделе рассмотрим реализацию с помощью семафоров задачи ограниченный буфер: имеются процесс-производитель и процесс-потребитель, взаимодействующие с помощью циклического буфера ограниченной длины; производитель генерирует элементы информации и записывает в буфер; потребитель использует информационные элементы из буфера и удаляет их. Будем использовать три общих семафора: semaphore full = n; semaphore empty = 0; semaphore mutex = 1; Семафор full сигнализирует о переполнении буфера, empty – об исчерпании буфера, mutex – используется для взаимного исключения действий над буфером. Код процесса-производителя имеет вид: do { ... сгенерировать элемент в nextp ... wait (full); wait (mutex); ... добавить nextp к буферу ... signal (mutex); signal (empty); } while (1); Код процесса-потребителя: do { wait (empty); wait (mutex); ... взять и удалить элемент из буфера в nextc ... signal (mutex); signal (full); ... использовать элемент из nextc ... } while (1); Поясним использование семафоров. Семафор mutex используется "симметрично"; над ним выполняется пара операций: wait … signal – семафорные скобки. Его роль – чисто взаимное исключение критических секций. Семафор empty сигнализирует об исчерпании буфера. В начале он закрыт, так как элементов в буфере нет. Поэтому при закрытом семафоре empty потребитель вынужден ждать. Открывает семафор empty производитель, после того, как он записывает в буфер очередной элемент. Семафор full сигнализирует о переполнении буфера. В начале он равен n – максимальному числу элементов в буфере. Производитель перед записью элемента в буфер выполняет операцию wait (full), гарантируя, что, если буфер переполнен, записи нового элемента в буфер не будет. Открывает семафор full потребитель, после того, как он освободил очередной элемент буфера. Заметим, что даже в такой сравнительно простой задаче использование семафоров весьма нетривиально и не вполне надежно – очень легко сделать ошибку. Стоит забыть открыть семафор, либо перепутать два семафора при операциях, и в программе может возникнуть взаимная блокировка процессов. Решение с помощью семафоров задачи "читатели – писатели" Суть задачи читатели-писатели в следующем: имеется общий ресурс и две группы процессов: читатели (которые могут только читать ресурс, но не изменяют его) и писатели (которые изменяют ресурс). В каждый момент работать с ресурсом может сразу несколько читателей (когда ресурс не изменяется писателями), но не более одного писателя. Необходимо синхронизировать их действия над ресурсом и обеспечить взаимное исключение соответствующих критических секций. Будем использовать два семафора и целую переменную: semaphore mutex = 1; semaphore wrt = 1; int readcount = 0; Семафор mutex используется читателями для взаимного исключения операций над переменной readcount (счетчиком читателей). Семафор wrt используется для взаимного исключения писателей. Реализация процесса-писателя особых комментариев не требует: wait (wrt); ... изменение ресурса ... signal (wrt); Реализация процесса-читателя несколько более сложна: wait (mutex); readcount++; if (readcount == 1) { wait (wrt); } signal (mutex); ... чтение ресурса ... wait (mutex); readcount--; if (readcount == 0) { signal (wrt); } Процесс-читатель, во-первых, должен увеличить значение readcount, причем обеспечить взаимное исключение для действий над readcount с помощью семафора mutex. Далее, если процесс является первым читателем, он должен закрыть семафор wrt, чтобы исключить одновременное с чтением изменение ресурса писателями. По окончании чтения ресурса, читатель в аналогичном стиле вновь уменьшает readcount. Если при этом оно обнуляется (т.е. это последний на данный момент читатель), то читатель открывает семафор wrt, сигнализируя писателям, что они могут изменять ресурс. Решение с помощью семафоров задачи "обедающие философы" Суть задачи обедающие философы в следующем. Имеется круглый стол, за которым сидят пять философов (впрочем, их число принципиального значения не имеет – для другого числа философов решение будет аналогичным). Перед каждым из них лежит тарелка с едой, слева и справа от каждого – две китайские палочки. Философ может находиться в трех состояниях: проголодаться, думать и обедать. На голодный желудок философ думать не может. Но начать обедать он может, только если обе палочки слева и справа от него свободны. Требуется синхронизировать действия философов. В данном случае общим ресурсом являются палочки. Иллюстрацией условий задачи является рис. 12.1.
Рис. 12.1. Задача "обедающие философы". Данная задача является одной из излюбленных задач профессора Ч. Хоара, который использовал ее, как пример в своих работах по параллельному программированию. При решении задачи будем использовать массив семафоров chopstick, описывающий текущее состояние палочек: chopstick[i] закрыт, если палочка занята, открыт – если свободна: semaphore chopstick [5] = { 1, 1, 1, 1, 1}; Алгоритм реализации действий философа i имеет вид: do { wait (chopstick [i]); /* взять левую палочку */ wait (chopstick [(I + 1) % 5]); /* взять правую палочку */ ... обедать... signal (chopstick [i]); /* освободить левую палочку */ signal (chopstick [(i+1) % 5]); /* освободить правую палочку */ ... думать... while (1); Решение данной задачи с помощью семафоров оказывается особенно простым и красивым. Критические области Критические области (critical regions) – более высокоуровневая и надежная конструкция для синхронизации, чем семафоры. Общий ресурс описывается в виде особого описания переменной: v: shared T Доступ к переменной v возможен только с помощью специальной конструкции: region v when B do S где v – общий ресурс; B – булевское условие, S – оператор (содержащий действия над v). Семантика данной конструкции следующая. Пока B ложно, процесс, ее исполняющий, должен ждать. Когда B становится истинным, процесс получает доступ к ресурсу v и выполняет над ним операции S. Пока исполняется оператор S, больше ни один процесс не имеет доступа к переменной v. Решение с помощью критических областей задачи "ограниченный буфер" Опишем буфер как структуру: struct buffer { int pool [n]; int count, in, out } buf: shared buffer; Алгоритм процесса-производителя: region buf when (count < n) { pool [in] = nextp; in = (in+1) % n; count++; } Заметим, что проверка переполнения буфера выполняется при входе в конструкцию region, и потребитель ждет, пока в буфере освободится хотя бы один элемент. Алгоритм процесса-потребителя: region buf when (count > 0) { nextc = pool [out]; out = (out+1) % n; count--; } Нельзя не отметить, насколько проще и надежнее оказывается решение задачи с использованием данной конструкции, по сравнению с использованием семафоров.   Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
