ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Вимоги, що пред'являються до алгоритмів

Організація того, що взаємовиключає для критичних ділянок, звичайно, дозволить уникнути виникнення race condition, але не є достатньою для правильної і ефективної паралельної роботи кооперативних процесів. Сформулюємо п'ять умов, які повинні виконуватися для хорошого програмного алгоритму організації взаємодії процесів, що мають критичні ділянки, якщо вони можуть проходити їх в довільному порядку.

1. Завдання має бути вирішена чисто програмним способом на звичайній машині, що не має спеціальних команд того, що взаємовиключає. При цьому передбачається, що основні інструкції мови програмування (такі примітивні інструкції, як load, store, test) є атомарними операціями.

2. Не повинно існувати ніяких припущень про відносні швидкості процесів, що виконуються, або число процесорів, на яких вони виконуються.

3. Якщо процес Pi виконується в своїй критичній ділянці, то не існує ніяких інших процесів, які виконуються у відповідних критичних секціях. Цю умову отримала назва умови того, що взаємовиключає (mutual exclusion).

4. Процеси, які знаходяться поза своїми критичними ділянками і не збираються входити в них, не можуть перешкоджати іншим процесам входити в їх власні критичні ділянки. Якщо немає процесів в критичних секціях і є процеси, охочі увійти до них, то тільки ті процеси, які не виконуються в remainder section, повинні ухвалювати рішення про те, який процес увійде до своєї критичної секції. Таке рішення не повинне ухвалюватися нескінченно довго. Цю умову отримала назва умови прогресу (progress).

5. Не повинно виникати необмежено довгого очікування для входу одного з процесів в свою критичну ділянку. Від того моменту, коли процес запросив дозвіл на вхід в критичну секцію, і до того моменту, коли він цей дозвіл отримав, інші процеси можуть пройти через свої критичні ділянки лише обмежене число разів. Цю умову отримала назва умови обмеженого очікування (bound waiting).

Треба відмітити, що опис відповідного алгоритму в нашому випадку означає опис способу організації прологу і епілогу для критичної секції.

Заборона переривань

Найбільш простим рішенням поставленої задачі є наступна організація прологу і епілогу:

while (some condition) {

заборонити всі переривання

critical section

вирішити всі переривання

remainder section

}

Оскільки вихід процесу із стану виконання без його завершення здійснюється по перериванню, усередині критичної секції ніхто не може втрутитися в його роботу. Проте таке рішення може мати наслідки, що далеко йдуть, оскільки дозволяє процесу користувача вирішувати і забороняти переривання у всій обчислювальній системі. Допустимо, що користувач випадково або по злому наміру заборонив переривання в системі і зациклив або завершив свій процес. Без перезавантаження системи в такій ситуації не обійтися.

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

Змінна-замок

Як наступна спроба рішення задачі для призначених для користувача процесів розглянемо іншу пропозицію. Візьмемо деяку змінну, доступну всім процесам, з початковим значенням рівним 0. Процес може увійти до критичної секції тільки тоді, коли значення цієї змінної-замку дорівнює 0, одночасно змінюючи її значення на 1 – закриваючи замок. При виході з критичної секції процес скидає її значення в 0 – замок відкривається (як у випадку з покупкою хліба студентами в розділі "Критична секція").

shared int lock = 0;

/* shared означає, що */

/* змінна є такою, що розділяється */

while (some condition) {

while(lock); lock = 1;

critical section

lock = 0;

remainder section

}

На жаль, при уважному розгляді ми бачимо, що таке рішення не задовольняє умові того, що взаємовиключає, оскільки дія while(lock); lock = 1; не є атомарним. Допустимо, процес P0 протестував значення змінної lock і ухвалив рішення рухатися далі. У цей момент, ще до привласнення змінній lock значення 1, планувальник передав управління процесу P1. Він теж вивчає вміст змінної lock і теж ухвалює рішення увійти до критичної ділянки. Ми отримуємо два процеси, що одночасно виконують свої критичні секції.

Строге чергування

Спробуємо вирішити задачу спочатку для двох процесів. Черговий підхід також використовуватиме загальну для них обох змінну з початковим значенням 0. Тільки тепер вона гратиме не роль замку для критичної ділянки, а явно указувати, хто може наступним увійти до нього. Для i-го процесу це виглядає так:

shared int turn = 0;

while (some condition) {

while(turn != i);

critical section

turn = 1-i;

remainder section

}

Очевидно, що те, що взаємовиключає гарантується, процеси входять в критичну секцію строго по черзі: P0, P1, P0, P1, P0 ... Але наш алгоритм не задовольняє умові прогресу. Наприклад, якщо значення turn дорівнює 1, і процес P0 готовий увійти до критичної ділянки, він не може зробити цього, навіть якщо процес P1 знаходиться в remainder section.

Прапори готовності

Недолік попереднього алгоритму полягає в тому, що процеси нічого не знають про стан один одного у нинішній момент часу. Давайте спробуємо виправити цю ситуацію. Хай два наші процесу мають масив прапорів готовності входу процесів, що розділяється, в критичну ділянку

shared int ready[2]= {0, 0};

Коли i-й процес готовий увійти до критичної секції, він привласнює елементу масиву ready[i] значення рівне 1. Після виходу з критичної секції він, природно, скидає це значення в 0. Процес не входить в критичну секцію, якщо інший процес вже готовий до входу в критичну секцію або знаходиться в ній.

while (some condition) {

ready[i]= 1;

while(ready[1-i]);

critical section

ready[i]= 0;

remainder section

}

Отриманий алгоритм забезпечує те, що взаємовиключає, дозволяє процесу, готовому до входу в критичну ділянку, увійти до нього відразу після завершення епілогу в іншому процесі, але все одно порушує умову прогресу. Хай процеси практично одночасно підійшли до виконання прологу. Після виконання привласнення ready[0]=1 планувальник передав процесор від процесу 0 процесу 1, який також виконав привласнення ready[1]=1. Після цього обидва процеси нескінченні довго чекають один одного на вході в критичну секцію. Виникає ситуація, яку прийнято називати тупиковою (deadlock). (Докладніше про тупикові ситуації розповідається в лекції 7.)

Алгоритм Петерсона

Перше вирішення проблеми, що задовольняє всім вимогам і що використовує ідеї раніше розглянутих алгоритмів, було запропоноване данським математиком Деккером (Dekker). У 1981 році Петерсон (Peterson) запропонував витонченіше рішення. Хай обидва процеси мають доступ до масиву прапорів готовності і до змінної черговості.

shared int ready[2]= {0, 0};

shared int turn;

while (some condition) {

ready[i]= 1;

turn =1-i;

while(ready[1-i]&& turn == 1-i);

critical section

ready[i]= 0;

remainder section

}

При виконання прологу критичної секції процес Pi заявляє про свою готовність виконати критичну ділянку і одночасно пропонує іншому процесу приступити до його виконання. Якщо обидва процеси підійшли до прологу практично одночасно, то вони обидва оголосять про свою готовність і запропонують виконуватися один одному. При цьому одна з пропозицій завжди слідує після іншого. Тим самим роботу в критичній ділянці продовжить процес, якому було зроблено останню пропозицію.

Давайте доведемо, що все п'ять наших вимог до алгоритму дійсно задовольняються.

Задоволення вимог 1 і 2 очевидно.

Доведемо виконання умови того, що взаємовиключає методом від осоружного. Хай обидва процеси одночасно опинилися усередині своїх критичних секцій. Відмітимо, що процес Pi може увійти до критичної секції, тільки якщо ready[1-i]== 0 або turn == i. Відмітимо також, що якщо обидва процеси виконують свої критичні секції одночасно, то значення прапорів готовності для обох процесів збігаються і рівні 1. Чи могли обидва процеси увійти до критичних секцій із стану, коли вони обидва одночасно знаходилися в процесі виконання циклу while? Ні, оскільки в цьому випадку змінна turn повинна була б одночасно мати значення 0 і 1 (коли обидва процеси виконують цикл, значення змінних змінитися не можуть). Хай процес P0 першим увійшов до критичної ділянки, тоді процес P1 повинен був виконати перед входженням в цикл while принаймні один передуючий оператор (turn = 0;). Проте після цього він не може вийти з циклу до закінчення критичної ділянки процесу P0, оскільки при вході в цикл ready[0]== 1 і turn == 0, і ці значення не можуть змінитися до тих пір, поки процес P0 не покине своя критична ділянка. Ми прийшли до суперечності. Отже, має місце те, що взаємовиключає.

Доведемо виконання умови прогресу. Візьмемо, без обмеження спільності, процес P0. Відмітимо, що він не може увійти до своєї критичної секції тільки при сумісному виконанні умов ready[1]== 1 і turn == 1. Якщо процес P1 не готовий до виконання критичної ділянки, то ready[1]== 0, і процес P0 може здійснити вхід. Якщо процес P1 готовий до виконання критичної ділянки, то ready[1]== 1 і змінна turn має значення 0 або 1, дозволяючи процесу P0 або процесу P1 почати виконання критичної секції. Якщо процес P1 завершив виконання критичної ділянки, то він скине свій прапор готовності ready[1]== 0, дозволяючи процесу P0 приступити до виконання критичної роботи. Таким чином, умова прогресу виконується.

Звідси ж витікає виконання умови обмеженого очікування. Оскільки в процесі очікування дозволу на вхід процес P0 не змінює значення змінних, він зможе почати виконання своєї критичної ділянки не більше ніж одного проходу по критичній секції процесу P1.

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти