Мониторы. Критические области (critical regions) –более высокоуровневая и надежная конструкция для синхронизации

Критические области

Критические области (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--;

}

Нельзя не отметить, насколько проще и надежнее оказывается решение задачи с использованием данной конструкции, по сравнению с использованием семафоров.

Схема реализации критических областей с помощью семафоров

Будем использовать для реализации конструкции region x when B do S следующие семафоры и целые переменные:

semaphore mutex, first-delay, second-delay;

int first-count, second-count;

Семафор mutex используется для взаимного исключения доступа к критической секции S. Семафор first-delay используется для ожидания процессов, которые не могут войти в критическую секцию S, так как условие B ложно. Число таких процесов хранится в переменной first-count. Семафор second-delay используется для ожидания тех процессов, которые вычислили условие B один раз и ожидают, когда им будет позволено повторно вычислить B (second-count – счетчик таких процессов). Реализация предоставляется студентам в качестве упражнения.

Конструкция монитор предложена в 1974 г. Ч. Хоаром [18]. Она является более высокоуровневой и более надежной конструкцией для синхронизации, чем семафоры.

Описание монитора имеет вид:

monitor monitor-name

{

описания общих переменных

procedure body P1 (…) {

...

}

procedure body P2 (…) {

...

}

...

procedure body Pn(…) {

...

}

{

код инициализации монитора

}

}

Монитор является многовходовым модулем особого рода. Он содержит описания общих для нескольких параллельных процессов данных и операций над этими данными в виде процедур P1, …, Pn. Пользователи монитора – параллельные процессы – имеют доступ к описанным в нем общим данным только через его операции, причем в каждый момент времени не более чем один процесс может выполнять какую-либо операцию монитора; остальные процессы, желающие выполнить операцию монитора, должны ждать, пока первый процесс закончит выполнять мониторную операцию.

По сути дела, концепция монитора явилась развтием предложенной также Ч. Хоаром концепции абстрактного типа данных (АТД) [23 (не найдено)] – определения типа данных как совокупности описания его конкретного представления и абстрактных операций над ним (в виде процедур). Концепция монитора добавляет к АТД возможность синхронизации процессов по общим данным.

Для реализации ожидания внутри монитора по различным условиям, вводятся условные переменные (condition variables) – переменные с описаниями вида condition x,y, доступ к которым возможен только операциями wait и signal: например, x.wait(); x.signal(). Операция x.wait() означает, что выполнивший ее процесс задерживается до того момента, пока другой процесс не выполнит операцию x.signal(). Операция x.signal() возобновляет ровно один приостановленный процесс. Если приостановленных процессов нет, она не выполняет никаких действий.

Схематическое изображение монитора приведено на рис. 12.2.

Рис. 12.2. Схематическое изображение монитора.

Схема монитора с условными переменными приведена на рис. 12.3.

Рис. 12.3. Монитор с условными переменными.

Решение задачи "обедающие философы" с помощью мониторов

Реализуем решение задачи "обедающие философы" (см. Решение с помощью семафоров задачи "обедающие философы") с помощью монитора. Для каждого философа определим состояния (голодный, обедает, думает), и для их хранения будем использовать массив state. Для управления переходом философа из состояния в состояние используем массив условных переменных self. Для каждого философа определим операции pickup – взять палочку; putdown – освободить палочку; test – проверить состояние философа и, если это возможно и если он голоден, перевести его в состояние eating.

Код монитора, реализующего решение задачи:

monitor dp

{

enum {thinking, hungry, eating} state [5];

condition self [5];

void pickup (int i) {

state [i] = hungry;

test (i);

if (state[i]!= eating) {

self[i].wait ();

}

} /* pickup */

void putdown (int i) {

state [i] = thinking;

test ((i+4) % 5));

test ((i-1) % 5));

/* когда палочка свободна, проверить соседей */

} /* putdown */

void test (int i) {

if (state((i+4)%5)!= eating &&

state [i] = hungry &&

state((i+1)%5)!= eating)) {

state[i] = eating;

self[i].signal;

void init () {

for (int i = 0; i < 5; i++) {

state[i] = thinking;

}

}

Дата добавления: 2014-01-20