Двоичните семафори на Дейкстра

Двоичните семафори на Дейкстра - Раздел Образование, Операционни системи Великият Гол подходи към проблема за взаимното изключване по напълно различен начин.

Големият холандски учен E.Dijkstra (1966) подходи към проблема за взаимното изключване по съвсем различен начин. Той предложи да се използва нов вид програмни обекти -семафори. Тук ще разгледаме най-простата им версия -двоични семафори, те също самютекси (mutex, от думите MUTual EXclusion - взаимно изключване).

Двоичният семафор е променлива S, която може да приема стойности 0 и 1 и за която са дефинирани само две операции.

P(S) е операцията за заемане (затваряне) на семафора. Той изчаква, докато стойността на S стане равна на 1, и щом това се случи, присвоява стойността на S на 0 и прекратява изпълнението си. Много важно: операцията P по дефиниция е неделима, т.е. между проверката и присвояването, никой друг процес не може да се намеси, за да промени стойността на S.
V(S) е операция за освобождаване (отваряне) на семафор. Той просто задава S на 0.

Как една семафорна променлива се различава от нормалната булева променлива? Фактът, че за него не са разрешени други операции, освен P и V. Не можете да напишете S:=1 или if(S)then в програмата. ако S е дефиниран като семафор.

Как се различава операцията P от варианта проверка и присвояване, който сметнахме за незадоволителен по-горе? Неделимост. Но това е „по дефиниция“, но как да постигнем тази неделимост на практика? Това е отделен, напълно разрешим въпрос.

Заслугата на Дейкстра е именно в това, че той разделя проблема за взаимното изключване на два независими проблема от различни нива:

на ниво внедряване: как да се гарантира, че семафорите работят в съответствие с тяхната дефиниция;
на ниво взаимодействие между процесите: как да напишем правилно работеща програма, ако програмистът има семафори на свое разположение.

Решаването на тези две задачи поотделно е по-лесно от двете заедно и обикновено трябва да се решават от различни хора: първият е разработчиците на операционната система, а вторият е разработчиците на приложната програма.

Нека първо да разгледаме изпълнението. Очевидно функциите P и V са по-удобни и по-надеждни за внедряване веднъж в ОС, отколкото всеки път по нов начин - в приложни програми. (Имената на тези функции могат да бъдат различни, по-изразителни в конкретни системи.)

Системната функция P(S) трябва да провери дали е свободен семафорът S. Ако е свободен (S = 1), тогава системата го заема (S := 0) и функцията приключва дотук. Ако семафорът е зает, тогава системата блокира процеса, който е извикал функцията P, и запомня, че този процес е блокиран в очакване на освобождаването на семафор S. По този начин, когато се прилагат семафори, е възможно да се избегне активното чакане.

Неделимостта на операцията се осигурява от факта, че по време на изпълнение на функцията P от системата, превключвателните процеси са забранени. В екстремни случаи операционната система има възможност да деактивира прекъсванията за кратко време.

Системната функция V(S) разбира се не е просто присвояване на S := 1. Освен това системата трябва да провери дали сред спящите процеси има такъв, който чака освобождаването на семафора S. Ако бъде открит такъв процес, системата го отключва и променливата S в този случай съхранява стойността 0 (семафорът отново е зает, вече от друг процес).

Може ли да се случи няколко спящи процеса да чакат освобождаването на един и същ семафор? Да, може и да е така. Кой от тези процеси трябва да се събуди от системата? От гледна точка на правилната работа и съответствие с дефинициите на функциите P и V -всеки, но само един. От гледна точка на ефективността на работа вероятно е необходимо да се събуди процесът с най-висок приоритет, а в случай на равенство на приоритетите ... е, очевидно този, който спи по-дълго.

Сега, след като се занимавахме с имплементацията на семафорите, можем да забравим за това [9] и да помним само, че семафорите съществуват и могат да бъдат използвани, ако е необходимо.

Сега помислете за втората половина на проблема - използването на семафори за контрол на взаимодействието на процесите. Как можете да реализирате правилната работа на процеси с критични секции, ако използвате двоичен семафор? Да, много просто.

Процес А:	Процес B:
. . . P(S); (критичен участък A) V(S); . . .	. . . P(S); (критичен участък B) V(S); . . .

И това е. Сложността влезе в изпълнението на семафори. Необходимо е само да се уверите, че семафорът S е отворен, преди процесите да започнат.