Таненбаум Э. Распределенные системы. Принципы и парадигмы

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

6.1.

Обзор 331

снижению общей производительности сервера. Ниже мы еще вернемся к кон-

фликту «производительность против масштабируемости».

6.1.2. Репликация объектов

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

данными (совместно используемыми), полезно рассматривать не отдельные дан-

ные,

а объекты. Достоинство объектов состоит в том, что они инкапсулируют

данные и операции над ними. Это облегчает нам разделение операций, которые

зависят от данных, и операций, которые от данных не зависят. Последний тип

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

пример тех, которые реализуются посредством многих описанных в этой книге

систем промежуточного уровня.

Рассмотрим распределенный удаленный объект, совместно используемый мно-

гими клиентами (рис. 6.1). До того как мы начнем думать о репликации удален-

ного объекта на несколько машин, мы должны решить проблему защиты объекта

от одновременного доступа нескольких клиентов. У этой проблемы существуют

два основных решения [75].

Машина клиента

1—1 J—1

П^^

Машина

сервера

Сервер

£^ ,

—^

ппп

^^—I

щ^шщ—^

Скелетон

)

ОС сервера

Машина

клиента

1—1 1—1

Г—П

Сеть

Рис. 6.1. Организация распределенного удаленного объекта,

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

Первое из решений состоит в том, что одновременные вызовы обрабатывает

сам объект. В качестве примера укажем, что объект Java может быть сконструи-

рован в виде монитора путем объявления его методов

си}Щ)онизированными.

Пред-

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

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

сервере, на котором находится этот объект.

Java, если методы объекта синхро-

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

окажется заблокированным до дальнейших уведомлений. Могут быть созданы

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

что средства обработки параллельных обращений реализует сам объект. Этот

принцип иллюстрирует рис. 6.2, а.

332 Глава 6. Непротиворечивость и репликация

Механизм

взаимного -

исключения

Параллельные

обращения

Машина сервера

Сервер

ппп

ЖЖА

Скелетон

AAA

Адаптер

ОС

^ AAA

Машина сервера

Входящие запросы

Механизм

взаимного

исключения

Адаптер

Параллельные

обращения

Входящие запросы

а б

Рис. 6.2. Удаленный объект, способный самостоятельно обрабатывать параллельные

обращения (а). Удаленный обьект, которому

для

обработки параллельных

обращений необходим адаптер объекта (б)

Второе решение состоит в том, что объект вообще никак не защищается от па-

раллельных обращений, вместо него ответственность за работу с параллельными

обращениями несет сервер, на котором расположен объект. В частности, исполь-

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

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

щий для каждого объекта один поток выполнения, может сериализовать весь

доступ к каждому из объектов, которыми он управляет (рис. 6.2, б).

Репликация удаленных, совместно используемых объектов без специальных

приемов обработки параллельных обращений может привести к проблемам с не-

противоречивостью. Эти проблемы связаны с тем, что для параллельных обра-

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

низации. Примером такой синхронизации может быть реплицируемая база дан-

ных банковских счетов, описанная в разделе 5.2. И вновь у нас есть два основных

способа решения проблемы.

Первый подход основан на осведомленности объекта о том, что он был репли-

цирован. В этом случае сам объект отвечает за непротиворечивость своей реплики

в условиях параллельных обращений. Такой подход весьма напоминает ситуа-

цию с объектами, которые самостоятельно обрабатывают параллельные обращения.

Распределенные системы, предлагающие подобные объекты, обычно не нуждают-

ся в централизованной поддержке репликации. Поддержка может быть ограни-

чена предоставлением серверов и адаптеров, помогающих в построении осведом-

ленных о репликации объектов (рис. 6.3, а). Примеры таких систем, которые мы

рассмотрим в главе 9, — это SOS [409] и Globe

[471].

Преимущество осведом-

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

6.1.

Обзор 333

фическую для объекта стратегию репликации, подобно тому, как параллельно

работающие объекты могут обрабатывать параллельные обращения каким-ни-

будь особым образом.

Реплицированный

—••у^

объект

"^j—-

Промежуточный

уровень

Сетевая ОС

Зависящий

от объекта

протокол

репликации

Промежуточный

уровень

Сетевая ОС

Сеть

Реплицированный

--—^объект

\j—-

Промежуточный

уровень

Сетевая ОС

Промежуточный

уровень

Протокол

"репликации»

промежуточного

уровня

Сетевая ОС

Сеть

Рис. б.З. Распределенная система для осведомленных о репликации

распределенных объектов (а). Распределенная система,

отвечающая за управление репликами (б)

Второй, более общий вариант обеспечения непротиворечивости параллельных

объектов

—

сделать ответственной за управление репликацией распределенную

систему, как это показано на рис. 6.3, б. В частности, распределенная система от-

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

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

Piranha

[281],

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

упорядоченных и причинно упорядоченных обращений к объектам в технологии

CORBA. Использование распределенной системы для управления репликацией

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

адаптировать специфические для объектов решения, и в этом недостаток таких

систем. Как мы увидим, эти решения часто требуются для масштабирования.

6.1.3. Репликация как метод масштабирования

Репликация и кэширование, увеличивающие производительность, часто исполь-

зуются в качестве способа масштабирования. Масштабирование обычно ведет к

проблемам с производительностью. Однако размещение копий данных и объек-

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

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

блемы масштабирования.

Возможно, платой за это будет необходимость сохранения актуальности копий,

что потребует дополнительной пропускной способности сети. Рассмотрим про-

цесс Р, который обращается к локальной реплике Л/'раз в секунду, в то время как

сама реплика обновляется М раз в секунду. Допустим, что обновление полно-

стью изменяет предьщущую версию локальной реплики. Если Л^«М, то есть соот-

334 Глава 6. Непротиворечивость и репликация

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

когда обращений ко многим обновленным версиям со стороны Р попросту не бу-

дет и задействовать сетевую связь для доставки этих версий бесполезно. В этом

случае может быть правильнее не устанавливать локальную реплику вблизи про-

цесса Р или применить другую стратегию обновления этой реплики. Ниже мы

вернемся к этим вопросам.

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

жества копий само по себе может стать серьезной проблемой масштабирования.

Интуитивно понятно, что набор копий актуален, если все копии постоянно оди-

наковы. Это означает, что операция чтения должна давать одинаковые результа-

ты для каждой из копий. Соответственно, при выполнении операции обновле-

ния одной из копий обновление должно распространиться на все копии до того,

как начнется следующая операция. При этом безразлично, с какой копии нача-

лась эта операция.

Такой тип непротиворечивости иногда неформально (и неверно) называют

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

хронную репликацию [78]. (В следующем разделе мы представим точное опреде-

ление непротиворечивости и введем ряд моделей непротиворечивости.) Ключевой

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

операция или транзакция. К сожалению, реализация атомарности операции, если

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

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

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

Трудности вытекают из того факта, что мы должны синхронизировать все ре-

плики. Конкретно это означает, что все реплики должны достичь согласия в том,

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

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

с использованием механизма отметок времени Лампорта или завести координа-

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

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

бросаны по глобальной сети.

Итак, мы оказались перед дилеммой. С одной стороны, остроту проблем мас-

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

вызовут рост производительности. С другой стороны, чтобы поддерживать все

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

торая чересчур сильно влияет на производительность. Лекарство может оказать-

ся хуже болезни.

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

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

атомарности операций обновления, мы сможем отказаться от необходимости

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

сти.

Ценой за это станет ситуация возможной неодинаковости копий. То, в какой

степени мы можем пожертвовать непротиворечивостью, зависит от вариантов до-

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

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

6.2. Модели непротиворечивости, ориентированные

на

данные

335

В следующем разделе мы сначала рассмотрим ряд моделей непротиворечиво-

сти,

которые позволят нам дать точное определение непротиворечивости. Затем

мы продолжим наш разговор о различных способах реализации этих моделей с

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

ные подходы к классификации непротиворечивости и реплицирования можно

найти в [176, 492].

6.2. Модели непротиворечивости,

ориентированные на данные

По традиции непротиворечивость всегда обсуждается в контексте операций чте-

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

ленной памяти (разделяемой) или в файловой системе (распределенной). В этом

разделе мы задействуем общий термин хранилище данных {data

store).

Хранили-

ще

данных может быть физически разнесено по нескольким машинам. В частно-

сти,

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

может означать наличие доступной через хранилище локальной (или располо-

женной неподалеку от него) копии данных. Операции записи распространяются

и на другие копии, как это показано на рис. 6.4. Операции над данными называ-

ются операциями записи, если они изменяют данные. Все прочие операции счи-

таются операциями чтения.

Процесс Процесс Процесс

Распределенное

хранилище данных

Рис. 6.4. Обобщенная организация логического хранилища данных, физически

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

Модель непротиворечивости {consistency

model),

по существу, представляет со-

бой контракт между процессами и хранилищем данных. Он гласит, что если про-

цессы согласны соблюдать некоторые правила, хранилище соглашается работать

правильно. Обычно процесс, выполняющий операцию чтения элемента данных,

ожидает, что операция вернет значение, соответствующее результату последней

операции записи этих данных.

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

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

которые приведут к созданию моделей непротиворечивости. Каждая модель будет

336 Глава 6. Непротиворечивость и репликация

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

ния над элементом данных. Как можно догадаться, модели с минимальным объ-

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

ниями

—

труднее. Плата за это, разумеется, состоит в том, что простые модели

работают хуже, чем сложные. Такова жизнь. Дополнительную информацию по

моделям непротиворечивости можно почерпнуть в [4, 303].

6.2.1.

Строгая непротиворечивость

Наиболее жесткая модель непротиворечивости называется

строгой

непротиворе-

чивостью {strict

consistency).

Она определяется следующим условием:

всякое

чте-

ние элемента данных х

возвращает

значение,

соответствуюш,ее

результату по-

следней

записи X.

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

мевает существование абсолютного глобального времени (как в классической фи-

зике),

в котором определение «последней» однозначно. Однопроцессорные сис-

темы традиционно соблюдают строгую непротиворечивость, и программисты таких

систем склонны рассматривать такое поведение, как естественное. Рассмотрим

следующую программу:

а = 1: а = 2: pr1nt(a);

Система, в которой эта программа напечатает 1 или любое другое значение,

кроме 2, быстро приведет к появлению толпы возбужденных программистов и

массе полезных мыслей.

Для системы, в которой данные разбросаны по нескольким машинам, а до-

ступ к ним имеет несколько процессов, все сильно усложняется. Допустим, что

X —

это элемент данных, хранящийся на машине В. Представим, что процесс, ра-

ботающий на машине Л, читает х в момент времени

Т1,

то есть посылает В сооб-

щение с требованием возвратить х. Чуть позже, в момент времени 72, процесс с

машины В производит запись х. Если строгая непротиворечивость сохраняется,

чтение должно всегда возвращать прежнее значение, которое не зависит от того,

где находятся машины и насколько мал интервал между Т1 и Т2. Однако если

Т2-Т1 равно, скажем, одной наносекунде, а машины расположены в трех метрах

друг от друга, то чтобы запрос на чтение

от

АкВ дошел до машины раньше В от-

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

света, а это противоречит теории относительности Эйнштейна. Разумно ли про-

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

это требование противоречит законам физики?

Проблема со строгой непротиворечивостью состоит в том, что она завязана на

абсолютное глобальное время. В сущности, в распределенной системе невозмож-

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

ную с действительным глобальным временем. Мы можем снизить остроту этой

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

тервалов. Каждая операция может происходить в пределах интервала и получает

отметку времени, соответствующую этому интервалу. В зависимости от того.

6.2. Модели непротиворечивости, ориентированные на данные 337

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

ции, когда на один такой интервал будет приходиться больше одной операции.

К сожалению, на то, что на один интервал будет приходиться максимум одна

операция, нет никаких гарантий. Соответственно, мы вынуждены учитывать воз-

можность наличия в одном интервале нескольких операций. Аналогично ситуа-

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

ном и том же интервале приводят к конфликту, если производятся над одними

теми же данными, и одна из них

—

операция чтения. Важный момент для опре-

деления модели непротиворечивости

—

точно выяснить, какой тип поведения

применим при наличии конфликтующих операций.

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

примеров. Чтобы сделать эти примеры точнее, мы нуждаемся в специальной но-

тации, при помощи которой отобразим операции процессов на ось времени. Ось

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

волы Wi(x)a и Ri(x)b означают соответственно, что выполнены запись процес-

сом Р в элемент данных х значения а и чтение из этого элемента процессом Р,

возвратившее

Ь.

Мы полагаем, что каждый элемент данных первоначально был

инициализирован нулем. Если с процессом доступа к данным не было никаких

проблем, мы можем опустить индексы у символов Wn R.

В качестве примера на рис. 6.5, а процесс Р1 осуществляет запись в элемент

данных

Ху

изменяя его значение на а. Отметим, что в принципе эта операция,

W1(x)aj

сначала производит копирование значения в локальное хранилище дан-

ных

Р1,

а затем распространяет его и на другие локальные копии. В нашем примере

Р2 позже читает значение х из его локальной копии в хранилище и обнаружи-

вает там значение а. Такое поведение характерно для хранилища данных, сохра-

няющего строгую непротиворечивость. В противоположность ему, на рис. 6.5, б

процесс Р2 производит чтение после записи (возможно, лишь на наносекунду

позже, но позже) и получает нуль (NIL). Последующее чтение возвращает

а.

Такое

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

некорректно.

Р1:

W(x)a Р1: W(x)a

Р2:

R(x)a Р2: R(x)NIL R(x)a

Рис. 6.5. Поведение двух процессов, работающих с одним

тем же элементом данных.

Горизонтальная ось

—

время.

Хранилище со строгой непротиворечивостью (а).

Хранилище без строгой непротиворечивости (б)

Итак, когда хранилище данных строго непротиворечиво, все операции записи

мгновенно замечаются всеми процессами. Выдерживается абсолютный глобаль-

ный порядок по времени. Если элемент данных изменяется, все последующие

операции чтения, совершаемые с данными, возвращают новое значение, при этом

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

какой процесс производит чтение и где он расположен. Соответственно, если про-

изводится чтение, оно возвращает это текущее значение, и неважно, как быстро

после этого производится следующая запись.

338 Глава 6. Непротиворечивость и репликация

В следующем пункте мы ослабим требования этой модели, заменив абсолют-

ное время временными интервалами, и точно определим приемлемое поведение

для конфликтующих операций.

6.2.2. Линеаризуемость и последовательная

непротиворечивость

Хотя строгая непротиворечивость и представляет собой идеальную модель непро-

тиворечивости, реализовать ее в распределенных системах невозможно. Кроме

того,

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

не столь строгими моделями. Так, например, все книги по операционным систе-

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

ний. При этом, как правило, имеется предупреждение о том, что правильно напи-

санные параллельные программы (такие, как программа «производитель—потре-

битель») не должны делать никаких предположений об относительных скоростях

процессов или об очередности выполнения инструкций. Обработка двух событий

в одном процессе происходит так быстро, что другой процесс не в состоянии сде-

лать что-нибудь, если между ними обнаружит проблему. Вместо этого читателя

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

самом деле, ссылок на память) не имел никакого значения. Если важна очеред-

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

зации. Принятие этого аргумента означает согласие на модель слабой непротиво-

речивости.

Последовательная непротиворечивость {sequential consistency) —

это менее стро-

гая модель непротиворечивости. Впервые она была определена в [250] в контек-

сте совместно используемой памяти мультипроцессорных систем. В общем, хра-

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

творяет следующему

условию:

результат

любого действия такой

же^

как

если

бы

операции {чтения и записи) всех

процессов

хранилище

данных

выполнялись

бы в

некотором последовательном

порядке

причем операции

каждого отдельного

про-

цесса выполнялись бы в

порядке,

определяемом его

программой.

Это определение означает, что когда процессы выполняются параллельно на

различных (возможно) машинах, любое правильное чередование операций чте-

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

процессы

видят

одно

и то

же

чередо-

вание операций. Отметим, что о времени никто не вспоминает, то есть никто не

ссылается на «самую последнюю» операцию записи объекта. Отметим, что в дан-

ном контексте процесс «видит» записи всех процессов, но только свои собствен-

ные чтения.

Итак, время роли не играет, что мы и видим на рис. 6.6. Рассмотрим работу

четырех процессов с одним элементом данных х. На рис. 6.6, а сначала процесс

Р1 осуществляет запись W{x)a в элемент х. Позднее (по абсолютному времени)

процесс Р2 также осуществляет запись, устанавливая значение хвЬ. Однако оба

процесса, РЗ и

Р4,

сначала

читают значение b и лишь затем

—

значение а. Други-

ми словами, операция записи процесса Р2 представляется им происходящей

раньше записи процесса Р1.

6.2. Модели непротиворечивости, ориентированные

на

данные 339

Р1

Р2

РЗ

Р4

W(x)a

W(x)b

R(x)b

R(x)a

W(x)a

W(x)b

R(x)b R(x)a

R(x)a R(x)b

Рис. 6.6. Хранилище данных с последовательной непротиворечивостью (а).

Хранилище данных без последовательной непротиворечивости (б)

В противоположность происходящему на рис. 6.6, а, на рис. 6.6, б последова-

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

наковое чередование операций записи. В частности, для процесса РЗ дело выгля-

дит так, что элемент данных сначала принимает значение

Ь,

а затем

—

а. С другой

стороны, Р4 полагает, что итоговое значение элемента данных

—

Ь.

Модель непротиворечивости, более слабая, чем строгая непротиворечивость,

но более сильная, чем последовательная

—

это

линеаризуемость

{linearizability).

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

ные часы, имеющие конечную точность. Такие часы могут быть реализованы

рас-

пределенной системе из предположения, что у процессов имеются слабо синхро-

низированные часы, которые обсуждались в предыдущей главе. Пусть tsop{x)

—

это отметка времени, назначенная операции ОР, которая работает с элементом

данных

причем ОР

—

это операция чтения {К) или записи (W). Хранилище

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

ни и соблюдается следующее условие

[199]:

результат

всякого

действия такой

же

как если бы все операции {чтения и записи) всех

процессов с хранилищем

дан-

ных выполнялись

бы в

некотором последовательном

порядке,

причем операции ка-

ждого отдельного процесса выполнялись

бы в

этой последовательности

в порядке,

определенном

в их

программах,

и,

кроме

того,

если

tsopi(x) <

tSoP2{x),

то операция

0Р1(х) в этой

последовательности должна предшествовать

операции 0Р2(у).

Отметим, что линеаризуемое хранилище данных обладает еще и последова-

тельной непротиворечивостью. Разница между ними состоит в том, что при уче-

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

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

содействия в формальном подтверждении параллельных алгоритмов

[199].

До-

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

вии с отметками времени, делает затраты на реализацию линеаризации выше,

чем на реализацию последовательной непротиворечивости, как показано в [20].

Последовательная непротиворечивость напоминает сериализуемость в тран-

закциях, о которой мы говорили в предыдущей главе. Напомним, что набор па-

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

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

тельно с определенной очередностью. Основная разница заключается в степени

детализации: последовательная непротиворечивость определяется в понятиях опе-

раций записи и чтения, а сериализуемость

—

в понятиях транзакций, которые

объединяют эти операции в одно целое.

340 Глава 6. Непротиворечивость и репликация

Чтобы получить более конкретное представление о последовательной непро-

тиворечивости, рассмотрим три параллельно выполняюш.ихся процесса, Р1, Р2

иРЗ, приведенные в табл. 6.1

[130].

Элементы данных в этом примере представ-

лены тремя целыми переменными

—

х, у и z, которые хранятся в последователь-

но непротиворечивом хранилище данных (возможно, распределенном), предна-

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

инициализирована нулем. В этом примере присвоение соответствует операции

записи, а инструкция print

—

одновременным операциям чтения обоих аргумен-

тов.

Все инструкции считаются неделимыми.

Таблица 6.1. Три параллельно выполняющихся процесса

Процесс Р1 Процесс Р2 Процесс РЗ

х=1;

prlnt(y.z):

у=1:

print(x.z):

z=l:

prlnt(x.y):

При выполнении возможны различные варианты чередования. Имея шесть

независимых выражений, мы получаем 720 (6!) потенциально возможных после-

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

ный в программах. Рассмотрим 120 (5!) последовательностей, которые начи-

наются с х=1. В половине из них инструкция print(x,z) выполняется раньше

инструкции

у=1,

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

мы.

Еще у половины инструкция prlnt(x.y) выполняется раньше инструкции z=l

и также нарушают порядок выполнения инструкций программы. Только 1/4 из

120 последовательностей являются допустимыми (всего 30). Еще 30 допустимых

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

у=1

и еще 30

—

с инструк-

ции z=l, давая в сумме 90 допустимых последовательностей выполнения инст-

рукций. Четыре из них приведены в табл. 6.2.

Таблица 6.2. Четыре варианта допустимых последовательностей

выполнения процессов

Инструкции

Печать

Сигнатура

Вариант

х=1;

prlnt(y.z);

У=1:

prlnt(x.z):

z=l;

print(x.y):

001011

х=1:

У=1:

prlnt(x.z):

prlnt(y.z):

z=l;

prlnt(x.y):

101011

y=l:

z=l:

print(x.y):

print(x.z):

x=l:

prlnt(y.z);

010111

110101

y=l:

x=l:

z=l:

prlnt(x.z):

prlnt(y.z):

prlnt(x.y):

111111

В варианте

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

Р1,

после

него

Р2,

затем

РЗ.

В трех других вариантах демонстрируются различные, но также