Методи за взаимно изключване - Студопедия

Организирането на взаимно изключване за критични участъци, разбира се, ще избегне появата на състояние на състезание, но не е достатъчно за правилната и ефективна паралелна работа на кооперативните процеси. Нека формулираме пет условия, които трябва да бъдат изпълнени за добър софтуерен алгоритъм за организиране на взаимодействието на процеси, които имат критични участъци, ако могат да преминават през тях в произволен ред [10,17].

Проблемът трябва да бъде решен по чисто програмен начин на конвенционална машина, която няма специални команди за взаимно изключване. Това предполага, че основните инструкции на езика за програмиране (такива примитивни инструкции като зареждане, съхраняване, тестване) са атомарни операции.
Не трябва да има предположения относно относителните скорости на изпълняваните процеси или броя на процесорите, на които те работят.
Ако Pi процес се изпълнява в своята критична секция, тогава няма други процеси, които да се изпълняват в съответните им критични секции. Това условие се нарича условие за взаимно изключване.
Процеси, които са извън своите критични региони и не възнамеряват да навлизат в тях, не могат да попречат на други процеси да навлязат в техните собствени критични региони. Ако няма процеси в критичните секции и има процеси, които желаят да влязат в тях, тогава само онези процеси, които не се изпълняват в останалата секция, трябва да решат кой процес ще влезе в критичната секция. Такова решение не трябва да се взема безкрайно. Това условие се нарича условие за напредък.
Не трябва да има безкрайно чакане процесът да навлезе в критичната си точкапарцел. От момента, в който даден процес е поискал разрешение да влезе в критичната секция до момента, в който е получил това разрешение, други процеси могат да преминават през своите критични секции само ограничен брой пъти. Това условие се нарича условие на обвързано изчакване.

Трябва да се отбележи, че описанието на съответния алгоритъм в нашия случай означава описание на метода за организиране на пролога и епилога за критичната част. Критичният раздел трябва да бъде последван от пролог и епилог, които не са свързани с дейността на един процес. По време на изпълнението на пролога процесът трябва по-специално да получи разрешение за влизане в критичната секция и по време на изпълнението на епилога да информира другите процеси, че е напуснал критичната секция.

Най-простото решение на проблема е да организирате пролога и епилога чрез забрана на прекъсванията:

докато (някое условие)

деактивирайте всички прекъсвания

разреши всички прекъсвания

Тъй като излизането на процеса от състояние на изпълнение без неговото прекратяване се извършва чрез прекъсване, никой в критичната секция не може да се намеси в неговата работа. Ако прекъсванията са забранени, прекъсването на таймера не е възможно. Деактивирането на прекъсванията предотвратява прехвърлянето на процесора към друг процес. По този начин, чрез деактивиране на прекъсванията, процесът може да чете и съхранява споделени данни, без да се страхува от намеса на друг процес. Този метод обаче практически не се използва, тъй като е опасно да се доверява управлението на системата на потребителски процес - това може да отнеме процесор за дълго време, а резултатът от повреда в критична ситуация може да доведе до срив на операционната система и, следователно, цялата система. В допълнение, желаният резултат може да не бъде постигнат в многопроцесорна система, тъй катотъй като деактивирането на прекъсванията ще се прилага само за един процес, останалите процесори продължават да работят и запазват достъп до споделени данни.

Въпреки това дезактивирането и активирането на прекъсване често се прилагат като пролог и епилог към критични секции в самата операционна система, като например при актуализиране на съдържанието на PSW (Programming Status Word).

За да синхронизира нишките на един процес, програмистът може да използваглобални блокиращи променливи. С тези променливи, до които всички нишки на процеса имат пряк достъп, програмистът работи без да прибягва до системни извиквания на ОС.

На всеки набор от критични данни се присвоява двоична променлива. Нишката може да влезе в критичната секция само когато стойността на тази променлива за заключване е 0, като същевременно се променя стойността й на 1 - затваряне на ключалката. При излизане от критичната секция нишката нулира стойността си на 0 - ключалката се отваря.

споделена int lock = 0;

докато (някое условие)

докато (заключване); заключване = 1;

За съжаление, внимателното изследване показва, че такова решение не отговаря на условието за взаимно изключване, тъй като while(lock); заключване = 1; не е атомно. Да кажем, че нишка P0 е тествала стойността на променливата за заключване и е решила да продължи. В този момент, преди променливата за заключване да бъде зададена на 1, планировчикът даде контрол на нишка P1. Той също така проверява съдържанието на променливата за заключване и също решава да влезе в критичната секция. Получаваме два процеса, изпълняващи едновременно своите критични секции.

Нека се опитаме да решим проблема първо за два процеса. Следващият подход също ще използва обща променлива и за двете с начална стойност 0. Само че сега няма да играе ролята на заключване закритична зона, но изрично посочете кой може да влезе в нея следващ. За i-тия процес изглежда така:

споделен ред = 0;

докато (някое условие)

Лесно е да се види, че взаимното изключване е гарантирано, процесите влизат в критичната секция строго на свой ред: P0, P1, P0, P1, P0, . Но нашият алгоритъм не отговаря на условието за напредък. Например, ако стойността на turn е 1 и процес P0 е готов да влезе в критичната секция, той не може да го направи, дори ако процес P1 е в секцията за оставане.

Недостатъкът на предишния алгоритъм е, че процесите не знаят нищо за състоянието един на друг в текущия момент. Нека се опитаме да поправим тази ситуация. Нека два процеса имат споделен масив от флагове за готовност за процесите да влязат в критичния регион

споделено int ready[2] = ;

Когато i-тият процес е готов да влезе в критичната секция, той присвоява на елемента на масива ready[i] стойност, равна на 1. След излизане от критичната секция, той естествено нулира тази стойност на 0. Един процес не влиза в критичната секция, ако друг процес вече е готов да влезе в критичната секция или е в нея.

споделен ред = 0;

докато (някое условие)

Полученият алгоритъм осигурява взаимно изключване, позволява на процес, който е готов да влезе в критичната секция, да влезе в нея веднага след завършване на епилога в друг процес, но все пак нарушава условието за прогрес. Нека процесите почти едновременно се доближат до изпълнението на пролога. След като направи присвояването готово[0] = 1, планировчикът прехвърли процесора от процес 0 към процес 1, който също изпълни присвояването готово[1] = 1. След това и двата процеса чакат един друг за неопределено време на входа на критичната секция. Възниква ситуация, която се наричазадънена улица.

Първото решение на задачата, което отговаря на всички изисквания и използва идеите на разгледаните по-рано алгоритми, е предложено от датския математик Декер. През 1981 г. Питърсън предлага по-елегантно решение. Нека и двата процеса имат достъп до масив от флагове за готовност и до променлив ред.

споделено int ready[2] = ;

споделено на свой ред;

докато (някое условие)

Когато изпълнява пролога на критичната секция, процесът Pi декларира готовността си да изпълни критичната секция и едновременно с това кани друг процес да започне да я изпълнява. Ако и двата процеса се приближиха до пролога почти едновременно, тогава и двамата ще обявят готовността си и ще предложат да се екзекутират взаимно. В този случай едно от предложенията винаги ще следва другото. Така работата в критичния участък ще бъде продължена от процеса, към който беше направено последното предложение.

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

Много изчислителни системи също имат специални процесорни инструкции, които ви позволяват да проверявате и променяте стойността на машинна дума или да разменяте стойностите на две машинни думи в паметта, изпълнявайки тези действия като атомарни операции. Нека видим как концепциите на такива команди могат да се използват за реализиране на взаимно изключване.

Изпълнението на команда Test-and-Set, която проверява стойността на булева променлива, докато задава нейната стойност на 1, може да се разглежда като изпълнениефункции

int Test_and_Set(int *цел)

int tmp = *цел;

С тази атомарна команда можем да модифицираме алгоритъма на заключващата променлива, за да осигурим взаимно изключване.

споделена int lock = 0;

докато (някое условие)

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

Повечето от алгоритмите, обсъдени по-горе, макар и правилни, са доста тромави и им липсва елегантност. Освен това процедурата на изчакване за влизане в критичен регион включва доста дълго въртене на процеса в празен цикъл, което отнема ценно процесорно време. Има и други сериозни недостатъци в алгоритмите, изградени с помощта на конвенционалните езици за програмиране.

Не намерихте това, което търсихте? Използвайте търсачката:

Деактивирайте adBlock! и обновете страницата (F5)наистина е необходимо