Операционные системы. Управление ресурсами

         

Рандеву


Модель взаимодействия процессов, названная рандеву, рассматривает синхронизацию и передачу данных как единую деятельность. Когда процесс A намерен передать данные процессу B, оба процесса должны объявить о своей готовности установить связь, выдав запросы на передачу и прием данных соответственно. Если процесс A выдает заявку на передачу прежде, чем процесс B выдал заявку на прием, то процесс A приостанавливается до выдачи заявки процессом B. И наоборот: если процесс B выдал заявку на прием раньше, чем процесс A на передачу, то приостанавливается процесс B. Таким образом, процессы взаимодействуют только при встрече (рандеву) их заявок на передачу и прием.

В абстрактной записи взаимодействие между процессами записывается так:

1 processA { 2 объявление локальной переменной x; 3 . . . 4 B!x; 5 . . . 6 } 7 processB { 8 объявление локальной переменной y; 9 . . . 10 A?y; 11 . . . 12 }

Нотация B!x в строке 4 означает, что процесс A передает процессу B значение своей переменной x. A?y в строке 10 означает, что процесс B принимает значение, переданное процессом A, и записывает его в свою переменную y.

Эта запись отражает, так называемую, синхронную модель рандеву. Запись асинхронной модели мы можем получить, заменив строку 10 на:

10 ?y;

В синхронной модели оба процесса должны указывать в операторах приема или передачи имя процесса-корреспондента. В асинхронной модели только процесс-передатчик указывает имя процесса-приемника. "Безадресный" оператор приема соответствует идеям структуризации данных и программирования "снизу вверх", развивавшимся автором моделей рандеву и мониторов - К.Хоаром [6]. Асинхронная модель делает возможным разработку библиотечных процессов, которые, во-первых, могут использоваться в разных разработках, а во-вторых, играть роль процессов-серверов, обрабатывающих запросы от разных параллельно выполняющихся процессов-клиентов.

Асинхронная модель рандеву лежит в основе взаимодействия процессов в языке ADA. Мы не имеем возможности дать здесь полное описание языка (его синтаксис во многом подобен синтаксису языка Pascal) и ограничимся только средствами, интересующими нас в первую очередь.
Во всех последующих примерах ключевые слова языка ADA записаны строчными буквами.

Процесс в языке ADA называется задачей и описание задачи состоит из спецификаций задачи и ее тела. Спецификация имеет структуру:

task ИМЯ_ЗАДАЧИ is < описания входных точек > end;

Тело имеет структуру:

task body ИМЯ_ЗАДАЧИ is < переменные и операторы > end ИМЯ_ЗАДАЧИ;

В спецификации указываются точки входа задачи для рандеву. Их описания идентичны описаниям процедур: имя и параметры с указанием направления передачи параметров: in, out или inout. В задаче, обращающейся ко входной точке, обращение выглядит точно так же, как обращение к процедуре. Однако, выполняется такое обращение иначе. В задаче-приемнике такое обращение обрабатывается оператором приема. В простейшем случае такой оператор имеет вид:

accept ИМЯ_ВХОДА ( < параметры > ) do < операторы > end;



Оператор приема входит в структуру последовательно выполняемых операторов тела задачи. Если при обращении к данному входу выполнение задачи-приемника еще не дошло до оператора приема, то задача-передатчик блокируется. Если выполнение дошло до оператора приема, но обращения к данному входу не было, блокируется задача-приемник.

В ряде случаев неизвестно заранее, в какой последовательности будут поступать запросы. Для недетерминированного выбора из нескольких возможных запросов используется оператор отбора:

select < оператор accept > < другие операторы > or < оператор accept > < другие операторы > or . . . else < другие операторы > end;

Когда выполнение приемника доходит до оператора отбора, приемник готов выполнить любой из операторов приема, перечисленных среди альтернатив отбора. Если к этому моменту уже поступили обращения к нескольким входам, включенным в отбор, принимается одно из обращений (какое именно - правила языка не определяют). Если обращений нет, то либо выполняется альтернатива else, либо (если эта альтернатива не задана) процесс-приемник ожидает.

Операторы accept, составляющие альтернативы отбора, могут быть "защищены" условиями.


Заголовок оператора в этом случае выглядит так:

when <логическое выражение > => accept ...

Защищенный оператор приема включается в число альтернатив отбора только в том случае, если логическое выражение имеет значение "истина".

Наше краткое описание средств языка само по себе, видимо, недостаточно для его понимания, поэтому проиллюстрируем его примером - все той же задачей производителей-потребителей:

1 PROD_CONS: declare; 2 /* пустая спецификация производителя */ 3 task PRODUCER is 4 end; 5 /* тело производителя */ 6 task body PRODUCER is 7 /* рабочая область для порции */ 8 WORK : PORTION; 9 begin 10 loop /* цикл производства */ 11 < производство порции в WORK > 12 PUTPORTION(WORK); /* запись порции */ 13 end loop; /* конец цикла производства */ 14 end PRODUCER;/* конец тела производителя */ 15 /* пустая спецификация потребителя */ 16 task CONSUMER is 17 end; 18 /* тело потребителя */ 19 task body CONSUMER is 20 /* рабочая область для порции */ 21 WORK : PORTION; 22 begin 23 loop /* цикл потребления */ 24 GETPORTION ( WORK ); /* выборка порции */ 25 < обработка порции в WORK > 26 end loop; /* конец цикла потребления */ 27 end CONSUMER; /* конец тела потребителя */ 28 /* спецификация задачи-сервера */ 29 task SERVER is 33 /* описание входных точек сервера */ 37 entry GETPORTION(PORT : out PORTION); 32 entry PUTPORTION(PORT : in PORTION); 33 end; 34 /* тело сервера */ 35 task body SERVER is 36 /* буфер */ 37 BUFFER : array [1..BSIZE] of PORTION; 38 /* индексы для чтения и записи */ 39 INCNT, OUTCNT : INTEGER range 1..BSIZE := 1; 40 /* счетчик порций в буфере */ 41 PORTCNT : INTEGER range 0..BSIZE := 0; 42 begin 43 loop /* цикл обслуживания */ 44 /* выбор из наступивших событий */ 45 select when PORTCNT < BSIZE => 46 /* если буфер не полон, обслуживается запись */ 47 accept PUTPORTION(PORT:in PORTION) do 48 BUFFER[INCNT] := PORT; /* запись */ 49 end; 50 /* модификация счетчиков */ 51 INCNT := INCNT mod BSIZE + 1; 52 PORTCNT := PORTCNT + 1; 53 or 54 /* или если буфер не пуст, обслуживается выборка */ 55 accept GETPORTION(PORT:out PORTION) do 56 PORT := BUFFER[OUTCNT]; /* выборка */ 57 end; 58 /* модификация счетчиков */ 59 OUTCNT := OUTCNT mod BSIZE + 1; 60 PORTCNT := PORTCNT - 1; 61 end select; /* конец выбора */ 62 end loop; /* конец цикла обслуживания */ 63 end SERVER; /* конец тела сервера */ 64 /* главная процедура */ 65 begin 66 /* запуск всех задач */ 67 initiate SERVER, PRODUCER, CONSUMER; 68 end.



В нашу программу входят:


  • главная процедура (строки 64 - 68);
  • задача-производитель (строки 2 - 14);
  • задача-потребитель (строки 15 - 27);
  • задача-сервер (строки 28 - 63), обеспечивающая обмен производителя и потребителя с буфером.


Главная процедура запускает три другие задачи оператором initiate (строка 67) и переходит в ожидание. Она завершится, когда завершатся все запущенные ею задачи. Задачи PRODUCER и CONSUMER не имеют операторов приема, поэтому их спецификации (строки 2 - 4 и 15 - 17) вырожденные - пустые. Тела этих задач содержат простые бесконечные циклы (loop), в которых выполняется подготовка или обработка порции и обращение к соответствующей входной точке сервера. Задача SERVER является аналогом монитора. В ее спецификации (строки 28 - 33) описаны две входные точки: GETPORTION и PUTPORTION. Сам буфер является локальным в теле сервера (строка 37), также локальны и индексы чтения и записи (строки 39, 40) и счетчик порций (строкa 41). Выполнение сервера представляет собой бесконечный цикл (строки 43 - 62), в каждой итерации которого обрабатывается одно обращение. Оператор select (строки 45 - 61) обеспечивает выбор из обращений: GETPORTION или PUTPORTION. В зависимости от значения счетчика PORTCNT из числа альтернатив может исключаться GETPORTION - если буфер пуст или PUTPORTION - если полон. Если к началу очередной итерации обращений нет или есть обращение, которое не позволяет принять защита when, сервер ожидает. Обратите внимание на операторные скобки do ... end, следующие за операторами accept (строки 47 - 49 и 55 - 57). Они ограничивают критическую секцию. Выполнение процесса-передатчика не возобновится до тех пор, пока процесс-приемник не выйдет из критической секции. Мы включили в критические секции приемов только операторы, непосредственно работающие с параметрами вызовов, так как основное предназначение этой секции - защита параметров от преждевременного их изменения. Остальные операторы, выполняемые в ходе обработки вызовов (модификация индексов и счетчика), выполняются уже вне критической секции.



В нашем примере мы запустили по одному производителю и потребителю. В языке, однако, имеется возможность запускать любое число однотипных задач - как полностью идентичных, так и различающихся значениями параметров.

Модель рандеву как достаточно универсальный метод взаимодействия позволяет легко реализовать и примитивы взаимного исключения и синхронизации. Двоичный семафор, например, выглядит так:

1 task SEMAPHORE is 2 entry P; 3 entry V; 4 end; 5 task body SEMAPHORE is 6 begin 7 loop 8 accept P; 9 accept V; 10 end loop; 11 end SEMAPHORE;

В этой задаче операторы приема не являются альтернативными, а выполняются строго последовательно. Если какая-либо внешняя задача выполнит P-обращение, то любая задача, выдавшая еще одно P-обращение, будет заблокирована до тех пор, пока не будет выполнено V-обращение, и семафор не войдет в следующую итерацию своего цикла.

Асимметричные рандеву являются дальнейшим развитием идеи мониторов. В большинстве ADA-приложений задачи четко разделяются на задачи-клиенты, выдающие вызовы, и задачи-серверы, их принимающие. Но концептуально рандеву являются более универсальным и гибким средством взаимодействия процессов. Обратите внимание на то, что взаимодействующие задачи не используют общих переменных. Это делает язык ADA независимым от конкретной реализации параллельной работы в системе: это может быть однопроцессорная система с разделением времени, мультипроцессорная система с общей памятью или многомашинная система (сеть).

Существенным недостатком модели рандеву является то, что большинство решений, ее использующих, требует введения дополнительных процессов (в наших примерах - задача-сервер или семафор, как отдельная задача). Это увеличивает число переключений процессов и накладные расходы системы.




Содержание раздела