Демьянович Ю.К., Иванцова О.Н. Технология программирования для распределенных параллельных систем

Подождите немного. Документ загружается.

Операциями wait и signal поддерживается обычная очередь

FIFO (приоритетом является время задержки).

Приоритетный оператор wait(cv, rank) позволяет влиять на

порядок в очереди п ри своени ем процессу того или иного ранга.

Здесь cv — условная переменная, а rank — целочисл енн ое выра-

жение.

Приостановленные процессы упорядочиваются в очереди со-

гласно присвоенным им приоритетом (рангом) в порядке возрас-

тания параметра rank (при одинаковых значениях rank (порядок

следования не стандартизуется и может зависеть от реализации);

хотя обычно запускается процесс, ожидавший дольше всех).

Для избежания ошибок в программе следует применять только

один тип оператора wait.

При определении ранга процесса, находящегося в начале очере-

ди задержки, применяется оператор minrank: вызов

minrank(cv);

возвращает ранг процесса в начале очере ди, связанной с пере-

менной cv, при условии, что очередь не пуста, и что при организа-

ции очереди используется приоритетн ый оператор wait; в против-

ном случае возвращается непредсказуемое целое число.

Операция signal_all применяется в виде

signal_all(cv);

посылает сигнал запуска всем процессам в очереди cv; каждый

из них соверш ает перепроверку условий запуска и запускается в

соответствии с правилами исключения (например, в одной очереди

могут оказаться процессы, затребовавшие разн ые ресурсы, которые

уже захвачены каким-либо процессом; некоторые ресурсы к этому

моменту могут освободиться).

В результате операции signal_all некоторые процессы могут

остаться в очереди, другие — запустятся; заметим, что процесс вы-

работавший сигнал, всегда продолжает работать в мониторе.

Фактически операция

signal_all(cv)

эквивалентна строке

while (!empty(cv)) signal(cv);

Замечание. Как было сказано, здесь и далее используется

стратегия SC (signal and continue) — “сигн али зир овать и про-

должить”. Если бы использовалась стратегия “сигнализировать и

ждать”, то возникал бы вопрос о пер ед аче исключительного пра-

ва владения данной процедурой. Отметим также, что в Unix, Java,

Pthreads использована страте гия SC.

§ 7. Монитор, реализующий кольцевой буфер

Для представления очереди сообщений использован массив buf

длины n, который “замкнут в кольцо”, т. е. и нде кс j определяется

по модулю n.

Целочисленные переменные front и rear указывают на первую

заполненную и первую пустую ячейку (см. рис. 3). Условные пере-

менные not_full и not_empty связаны с двумя очередями. Опера-

ции с буфером deposit (“вклад”) и fetch (“выборка”) — процедуры

монитора.

Рис. 3. Кольцевой монитор

monitor Bounded_Buffer {

type T buf[n]; # массив некоторого типа T

int front=0; # индекс первой заполненной ячейки

rear=0; # индекс первой пустой ячейки

count=0; # число заполненных ячеек

## rear=(front+count)%n

cond not_full,

# - получает сигнал при count меньше n

not_empty;

# - получает сигнал при count больше нуля

procedure deposit(type T data) {

while (count==n) wait(not_full);

buf[rear]=data; rear=rear+1%n; count++;

signal(not_empty);

}

procedure fetch(type T &result) {

while (count==0) wait(not_empty);

result=buf[front]; front=(front+1)%n; count--;

signal(not_full);

}

Как и прежде, процесс, запущенный signal, начинает выпол-

няться и сразу (из-за нашей стратегии) и потому в промежуточ-

ные моменты, например, другой процесс-производитель может об-

ратиться к процедуре deposit и заполнить свободное место. Таким

образом, процесс, запущенный signal должен перепроверить усло-

вия запуска, а при его выполнении он может работать.

§ 8. Задача о “читателях” и “писателях”

Процесс-читатель может только читать записи базы данных, а

процесс-писатель просматривает их и изменяет.

Читатели обращаются к базе данных одновременно, а писатель

должны иметь исключительный доступ, а именно: писатель в дан-

ной базе может быть единовременно только один; других писателей

и читателей в этот промежуток времени быть не должно.

В этой задаче упорядочивающий монитор RW дает разрешение

на доступ к базе данных.

Поскольку имеется два вида процессов (read и write) и два

вида действий на каждый пр оцес с (начало и конец), то в мониторе

нужны четыре вида процедур:

request_read запрос на чтение ;

release_read окончание чтения;

request_write запрос на запись;

release_write окончание записи.

Пусть постоянные переменные монитора RW: nr — число читате-

лей, nw — число писателей.

Правильная синхронизация дол жна удовлетворять условию

RW: (nr==0 ∪ nw==0) ∩ nw<=1 (инвариант монитора).

monitor RW_Contr {

int nr=0, nw=0;

cond oktoread; # получает сигнал при nw==0

cond oktowrite; # получает сигнал при nr==0 и nw==0

procedure request_read() {

while (nw>0) wait(oktoread);

nr=nr+1;

}

procedure release_read() {

nr=nr-1;

if (nr==0) signal(oktowrite);

# запустить один процесс-писатель

}

procedure request_write() {

while (nr>0 || nw>0) wait(oktowrite);

nw=nw+1;

}

procedure release_write() {

nw=nw-1;

signal(oktowrite);

# запустить один процесс-писатель

signal_all(oktoread);

# запустить все процессы-читатели

}

При вызове

1) RW_Contr.request_read — запрос ч тени я: процесс-читатель

должен приостановиться если nw>0, а в противном случае (nw=0)

число читателей возрастает на единицу;

2) RW_Contr.release_read — уведомление о конце чтения:

процесс-читатель уведомляет о том, что он кончил чтение; при этом

число читателей уменьшаем на единицу и если оказалось их число,

равным нулю, то разрешается запустить один процесс-писатель;

3) RW_Contr.request_write — запрос записи: п роце сс- пис атель

хочет писать: если nr>0 или nw>0, ему приходится ждать в очереди

oktowrite, иначе число писателей увеличивается на единицу;

4) RW_Contr.release_write — уведомление о конце запи си:

имеется возможность просигнализировать одного писателя и о за-

пуске всех читателей.

§ 9. Распределение ресурсов по приоритетам

Здесь воспользуемся приоритетным оператором wait(cv,rank),

который располагает приостановленные процессы в порядке возрас-

тания ранга.

Схема “самое короткое задание” предполагает выполнения зада-

ний в порядке возрастания требуемого ресурса времени.

Для этого требуется две операции: request — запросить,

release — освободить.

После получения и использования ресурса процесс вызывает

процедуру release, в результате чего ресурс передается процессу,

который будет использовать его самое короткое время; если про-

цессов больше нет, ресурс освобождается.

monitor Shortest_Job {

bool free=true;

cond turn; # получает сигнал, когда ресурс доступен

procedure request(int time) {

if (free)

free=false;

# - процесс получает требуемый ресурс

else

wait(turn,time);

# - процесс ждет в очереди по приоритетам

}

procedure release() {

if (empty(turn))

free=true;

else

signal(turn);

}

Использующий этот монитор процесс должен иметь вид

Shortest_Job.request(15);

[получение и использование затребованного ресурса];

Shortest_Job.release;

§ 10. Организация “спящих” процессов

Основой такой организации является интервальный таймер,

позволяющий процессу перейти в состояние “сна” на некоторое ко-

личество единиц времени. Фактически речь идет о приостановке

процесса.

Необходимый здесь интервальный таймер ре ализ уется в виде

монитора, предс тавляющего логические часы.

С логическими часами возможны две операции:

delay(interval) — операция, приостанавливающая процесс на

interval “тиков” таймера;

tick — операция, увеличивающая значение логических часов и

периодически запускаемая аппаратным таймером с высоким при о-

ритетом (для сохранения точности логических часов).

Замечание. Особая точность логических часов не требуется, по-

скольку происходит проверка числа “тиков” и запуск или приоста-

новка процесса может происход ить только после очередного “тика”.

Будем считать, что значение логических часов хранится в пере-

менной tod (time of day) так что инвариантом требуемого мо-

нитора является

CLOCK: {tod>=0}

{tod монотонно увеличивается на единицу}

После вызова операции delay(interval) процесс “засыпает” на

interval “тиков”.

В процедуре (операции) delay вводится локальная переменная

wake_time, в которой хранится же лаем ое время запуска

wake_time=tod+interval;

“Засыпающий” процесс вычисляет период своего “сна” interval

и вызывает процедуру delay, в которой вычисляется упомянутое

время запуска.

Далее запускается цикл while с условием wake_time>=tod.

Процедура tick лишь увеличивает значение переменной tod на

единицу; она регулярно запускается высокоприоритетным процес-

сом, связанным аппаратным таймером.

Один из вариантов реализации — использование так называе-

мого накрывающего условия. Смысл этого условия в том, что его

выполнение влечет запуск всех ожидающих процессов, которые по-

сле этого должны проверить условия своего выполнения.

При этом в мониторе можно использовать одну условную пе-

ременную (назовем ее check) с накрывающим ус ловие м “значение

tod увеличено”. В этом случае при каждом запуске процедуры

tick будут запускаться все ожидающие процессы и будут прове-

рять условия своего запуска; в результате запустятся те процессы,

условия запуска которых выполнены. Остальные останутся в со-

стоянии ожидания. Для запуска всех процедур в процедуре tick

используется оповещающая операция signal_all.

monitor Timer{

int tod=0;

cond check; # получает сигнал при увеличении tod

procedure delay(int interval){

int wake_time;

wake_time=tod+interval;

while (wake_time>tod) wait(check);

}

procedure tick(){

tod=tod+1;

signal_all(check);

}

Использование “покрывающих условий” подходит, если затраты

на ложные сигналы невелики (т. к. пр и “ложном” сигнале процесс

запускается, проверяет условия своего вып олне ния, а затем снова

возвращается в состояние ожидания). Если же периоды “сна” вели-

ки, то скорее всего такой подход приводит к излишним затратам

ресурсов.

Для больших периодов “сна” более эффективно использовать в

мониторе приоритетный оператор wait. Это удобно в тех случа-

ях, когда имеется статическая упорядоченность (т. е. упорядочен-

ность, не меняющаяся во времени). В нашей ситуации процессы

можно упорядочить в соответствии со временем их запуска (“про-

буждения”). После этого можно использовать операцию minrank

для того, чтобы определить, настало ли врем я запуска самого пер-

вого процесса, приостановленного с помощью check; если это так,

то процесс получает сигнал для запуска.

Тепе рь не нужен цикл while в процедуре delay, но он нужен

в процедуре tick при посылке сигнала, ибо этого времени запуска

могут ожидать несколько процессов.

monitor Timer{

int tod=0;

cond check; # получает сигнал, когда minrank<=tod

procedure delay(int interval){

int wake_time;

wake_time=tod+interval;

if (wake_time>tod) wait(check, wake_time);

}

procedure tick(){

tod=tod+1;

while(!empty(check) && minrank(check)<=tod)

signal(check);

}

Изложенный способ (использование приоритетного оператора

wait) удобен в случае статических условий запуска процессов (не

меняющихся со временем в зависимости от работы других процес-

сов). В этих условиях он имеет явные преимущества перед “покры-

вающего условия”.

В случае нестатических условий запуска удобно применение на-

крывающего условия; более мощным средством, но менее эффек-

тивным с точки зрения захвата ресурсов, является использование

в мониторе отдельной условной переменн ой для каждого условия

задержки.

Глава 3. РАНДЕВУ И АКТИВНЫЕ МОНИТОРЫ

§ 1. Рандеву

Рандеву — особый тип синхронизации, применяемый, например,

при планировании работы головки дискового накопителя. Для на-

глядности эта синхронизация иллюстрируется “задачей о спящем

парикмахере”.

В тихом городке имеется парикмахерская с двумя дверями и

несколькими креслами. Посетитель входит через одну дверь, ждет

в кре сле пока освободится парикмахер (если он занят), будит па-

рикмахера (если он свободен), садится в кресло для обслуживания

и засыпает (пока его стрижет парикмахер). После стрижки парик-

махер открывает посетителю выходную дверь и закрывает за ним.

Если есть ожидающи е посетители, он будит и приглашает в кресло

одного из них. Если нет посетителей, то парикмахер засыпает.

Посетители и парик махер — это процессы:

посетители — это клиенты, которые запрашивают сервис (“стри ж-

ку”);

парикмахер — это сервер, обеспечивающий этот сервис.

Таким образом, рассматриваемые отношения име ют тип “клиент

– сервер”.

В реализации соответствующего монитора можно обойтись тре-

мя процедурами

get_haircut — запрос (“хочу постричься”);

get_next_customer — запрос (“хочу следующего”);

finished_cut — сообщение об окончании (“стрижки”).

Постоянные переменные используются для хранения состояний

процессов и пре доставления “кресел”, в которых клиенты “сп ят”.

Основная часть здесь — рандеву: для встречи

– парикмахер должен дождаться прихода посетителя;

– посетитель должен дождаться освобождения парикмахера.

Таким образом, ситуация аналогична двухпроцессорному барье-

ру: для продолжения работы к нему должны придти оба процесса;

однако, отл ич ие состоит в том, ч то в качестве процесса-посетителя

может быть любой процесс, нуждающимся в “стрижке”.

Процесс-посетитель должен ждать, пока парикмахер закроет

дверь после “стри жки ”, а процесс-парикмахер должен открыть

дверь после стрижки и подождать, пока уйдет посетитель и по-

сле него закрыть дверь; кроме того, парикмахер ждет, если нет

посетителей (находится в состоянии “сна”).

Будем использовать возрастающие счетчики для запоминания

числа процессов, д остигш их каждого э тапа.

У посетителей (client) имеется два важных этапа:

1) пребывание в кресле парикмахера (cinchair);

2) выход из парикмахерской (cleave).

У парикмахера (barber) циклически проходят этапы:

1) освобождение от работы (bavail);

2) стрижка (bbusy);

3) завершение стри жки (bdone).

Все счетчики в начале имеют значение нуль. Поскольку все э та-

пы проходят последовательно, то сп раведл ив следующий инвари-

ант:

C1: cinchair>=cleave

bavail>=bbusy>=bdone

С другой стороны нужно учесть следующее:

1) посетитель не может садиться в кресло чаще, чем парик-

махер освобождается от работы;

2) парикмахер не может начинать стрижку чаще, чем посети-

тель садится в его кресло.

C2: cinchair<=bavail

bbusy<=cinchair

Кроме того, посетители не могут выходить чаще, чем парикма-

хер завершает стрижку; поэтому

C3: cleave <= bdone

Итак, инвариант монитора имеет вид

BARBER: C1

Недостаток возрастающих счетчиков: их значения не могут воз-

растать неограниченно. Этого можно избежать, изменив перемен-

ные. В данном случае введем три новые переменные:

barber=bavail-cinchair

chair=cinchair-bbusy

open=bdone-cleave

Все три переменные принимают лишь два значения нуль и единица:

barber =



1, если парикмахер ждет посетителя,

0, если парикмахер обслуживает посетителя.