АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Пусть имеются два (или более) циклических процесса, в которых есть абстракт­ные критические секции, то есть каждый из процессов состоит из двух частей: некоторого критического интервала и оставшейся части кода, в которой нет рабо­ты с общими (критическими) переменными. Пусть эти два процесса асинхронно разделяют во времени единственный процессор либо выполняются на отдель­ных процессорах, каждый из которых имеет доступ к некоторой общей области памяти, с которой и работают критические секции. Проиллюстрируем эту ситуа­цию с помощью рис. 6.4.

' Проблема кажется легко решаемой, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические интервалы попеременно. Для этого одна общая пе­ременная может хранить указатель того, чья очередь войти в критическую сек­цию. Текст такого решения на языке, близком к Pascal, приведен в листинге 6.1.

Листинг 6.1. Первый вариант попытки реализации взаимного исключения

Var перекл: integer:

Begin перекл:- 1: { при перекл=1 в CS находится процесс ПР1 }

Parbegin

While true do Begin

while перекл - 2 do begin end: CS1: { Критическая секция процесса ПР1 } перекл:• 2;

PR1: (оставшаяся часть процесса ПР1 } End And

While true do

Begin

while перекл - 1 do begin end: CS2: { Критическая секция процесса ПР2 } перекл:- 1;

PR2: { оставшаяся часть процесса ПР2 } End

.Parend End.

Здесь и далее конструкция следующего типа

parbegin...Sll: S12:...: SIN, and... S21: S22:...: S2N₂

and... SKI: SK2:...; SKN_lk pa rend

означает параллельность К описываемых последовательных процессов. Конст­рукция из операторов Sll; S12;...: S1N1 выполняется оператор за оператором, о чем свидетельствует наличие точки с запятой между операторами. Конструкция

while true do

begin SI: S2: SN end

означает, что каждый процесс может выполняться неопределенное время. Конст­рукция типа begin end означает «пустой» оператор.

Итак, решение, представленное в листинге 6.1, обеспечивает взаимное исклю­чение в работе критических интервалов. Однако если бы часть программы PR1 была намного длиннее, чем программа PR2, или если бы процесс ПР1 был забло­кирован в секции PR1, или если бы процессор для ПР2 был с большим быстро­действием, то процесс ПР2 вскоре вынужден был бы ждать (и, может быть, чрез­вычайно долго) входа в свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. То есть при таком решении один процесс вне своей критической секции может помешать вхождению другого в свою критическую секцию.

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

Пусть с каждым из процессов ПР1 и ПР2 будет связана переменная, по смыслу являющаяся переключателем, которая принимает значение true, когда процесс находится в своем критическом интервале, и fal se — в противном случае. Преж­де чем войти в свой критический интервал, процесс проверяет значение пере­ключателя другого процесса. Если это значение равно true, процессу не разре­шается входить в свой критический интервал. В противном случае процесс «включает» свой собственный переключатель и входит в критический интервал. Этот алгоритм взаимного исключения представлен в листинге 6.2.

Данный алгоритм не гарантирует полного выполнения условия нахождения толь­ко одного процесса внутри критического интервала. Отсутствие гарантий связа­но с различными, в общем случае, скоростями развития процессов. Поэтому,

например, между проверкой значения переменной перекл2 процессом ПР1 и по­следующей установкой им значения переменной перекл! параллельно выполняю­щийся процесс ПР2 может установить перекл2 в значение true, так как перекл! еще не успел установиться в значение true. Отсюда следует, что оба процесса мо­гут войти одновременно в свои критические интервалы.

Листинг 6.2. Второй вариант попытки реализации взаимного исключения

Van перекл1.перекл2.: boolean: begin nepewil:-false;

перекл2:-false; parbegin

while true do begin

while перекл2 do begin end:

перекл!:-true;

CS1 (* Критический интервал процесса ПР1 *) перекл!:-false:

PR! (* процесс ПР1 после критического интервала *) end and

while true do begin

while перекл! do begi n end; nepewi2:=true;

(* Критический интервал процесса ПР2 *) nepewi2:=false;

(* процесс ПР2 после критического интервала *) end pa rend end.

Следующий (третий) вариант решения этой задачи (листинг 6.3) усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной перекл2 выполняется после установки переменной перекл! в значение true (анало­гично для ПР2).

Листинг 6.3. Третий вариант попытки реализации взаимного исключения

van перекл!. перекл2: boolean: begin перекл!:-false; nepewi2:=false: parbegin

ПР1: while true do begin

перекл!:=true;

while перекл2 do

begin end:

CS1 { Критический интервал процесса ПР1 } nepeMil:=false;

PR! { ПР1 после критического интервала } end and

ПР2: while true do begin

перекл2:Чгие; while перекл! do

begin end;

CS2.{ Критический интервал процесса ПР2 } nepewi2:=false;

PR2 { ПР2 после критического интервала } end

parend end.

Алгоритм, приведенный в листинге 6.3, также имеет свои недостатки. Действи­тельно, возможна ситуация, когда оба процесса одновременно установят свои пе­реключатели в значение true и войдут в бесконечный цикл. В этом случае будет нарушено требование отсутствия бесконечного ожидания входа в свой критиче­ский интервал. Предположив, что скорости исполнения процессов произвольны, мы получили такую последовательность событий, при которой процессы вообще перестанут нормально выполняться.

Рассмотренные попытки решить проблему критических интервалов иллюстри­руют некоторые тонкости, лежащие в основе этой проблемы.

Последний вариант решения задачи взаимного исключения, использующий только блокировку памяти, который мы рассмотрим, — это известный алгоритм, пред­ложенный математиком Деккером.

Дата добавления: 2015-01-18 | Просмотры: 849 | Нарушение авторских прав