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


Реалізація моніторів і передачі повідомлень за допомогою семафорів

Розглянемо спочатку, як реалізувати монітори за допомогою семафорів. Для цього нам потрібно уміти реалізовувати ті, що взаємовиключають при вході в монітор і умовні змінні. Візьмемо семафор mutex з початковим значенням 1 для реалізації того, що взаємовиключає при вході в монітор і по одному семафору ci для кожної умовної змінної. Крім того, для кожної умовної змінної заведемо лічильник fi для індикації наявності чекаючих процесів. Коли процес входить в монітор, компілятор генеруватиме виклик функції monitor_enter, яка виконує операцію P над семафором mutex для даного монітора. При нормальному виході з монітора (тобто при виході без виклику операції signal для умовної змінної) компілятор генеруватиме виклик функції monitor_exit, яка виконує операцію V над цим семафором.

Для виконання операції wait над умовною змінною компілятор генеруватиме виклик функції wait, яка виконує операцію V для семафора mutex, дозволяючи іншим процесам входити в монітор, і виконує операцію P над відповідним семафором ci, блокуючи процес, що викликав. Для виконання операції signal над умовною змінною компілятор генеруватиме виклик функції signal_exit, яка виконує операцію V над асоційованим семафором ci (якщо є процеси, чекаючі відповідної події), і вихід з монітора, минувши функцію monitor_exit.

Semaphore mutex = 1;

void monitor_enter(){

P(mutex);

}

void monitor_exit(){

V(mutex);

}

Semaphore ci = 0;

int fi = 0;

void wait(i){

fi=fi + 1;

V(mutex);

P(ci );

fi=fi - 1;

}

void signal_exit(i){

if (fi) V(ci );

else V(mutex);

}

Відмітимо, що при виконанні функції signal_exit, якщо хто-небудь чекав цієї події, процес покидає монітор без збільшення значення семафора mutex, не вирішуючи тим самим всім процесам, окрім розбудженого, увійти до монітора. Це збільшення зробить розбуджений процес, коли покине монітор звичайним способом або коли виконає нову операцію wait над якою-небудь умовною змінною.

Розглянемо тепер, як реалізувати передачу повідомлень, використовуючи семафори. Для простоти опишемо реалізацію тільки одній черги повідомлень. Виділимо в пам'яті, що розділяється, достатньо велику область під зберігання повідомлень, там же записуватимемо, скільки порожніх і заповнених осередків знаходиться в буфері, зберігати посилання на списки процесів, чекаючого читання і пам'яті. Взаємовиключає при роботі з пам'яттю, що розділяється, забезпечуватимемо семафором mutex. Також заведемо по одному семафору ci на взаємодіючий процес, для того, щоб забезпечувати блокування процесу при спробі читання з порожнього буфера або при спробі запису в переповнений буфер. Подивимося, як такий механізм працюватиме. Почнемо з процесу, охочого отримати повідомлення.

Процес-одержувач з номером i перш за все виконує операцію P(mutex), отримуючи в монопольне володіння пам'ять, що розділяється. Після чого він перевіряє, чи є в буфері повідомлення. Якщо немає, то він заносить себе в список процесів, чекаючихповідомлення, виконує V(mutex) і P(ci). Якщо повідомлення в буфері є, то він читає його, змінює лічильники буфера і перевіряє, чи є процеси в списку процесів, спраглих записи. Якщо таких процесів немає, то виконується V(mutex), і процес-одержувач виходить з критичної області. Якщо такий процес є (з номером j), то він віддаляється з цього списку, виконується V для його семафора cj, і ми виходимо з критичного району. Процес, що прокинувся, починає виконуватися в критичному районі, оскільки mutex у нас має значення 0 і ніхто більш не може потрапити в критичний район. При виході з критичного району саме розбуджений процес проведе виклик V(mutex).

Як будується робота процесу-відправника з номером i? Процес, що посилає повідомлення, теж чекає, поки він не зможе мати монополії на використання пам'яті, що розділяється, виконавши операцію P(mutex). Далі він перевіряє, чи є місце в буфері, і якщо так, то поміщає повідомлення в буфер, змінює лічильники і дивиться, чи є процеси, чекаючі повідомлення. Якщо немає, виконує V(mutex) і виходить з критичної області, якщо є, «будить» один з них (з номером j), викликаючи V(cj), з одночасним видаленням цього процесу із списку процесів, чекаючих повідомлень, і виходить з критичного регіону без виклику V(mutex), надаючи тим самим можливість розбудженому процесу прочитати повідомлення. Якщо місця в буфері немає, то процес-відправник заносить себе в чергу процесів, чекаючих можливості запису, і викликає V(mutex) і P(ci).

Реалізація семафорів і передачі повідомлень за допомогою моніторів

Нам досить показати, що за допомогою моніторів можна реалізувати семафори, оскільки отримувати з семафорів повідомлення ми вже уміємо.

Найпростіший спосіб такої реалізації виглядає таким чином. Заведемо усередині монітора змінну-лічильник, пов'язаний з емульованим семафором список процесів, що блокуються, і по одній умовній змінній на кожен процес. При виконанні операції P над семафором зухвалий процес перевіряє значення лічильника. Якщо воно більше нуля, зменшує його на 1 і виходить з монітора. Якщо воно дорівнює 0, процес додає себе в чергу процесів, чекаючих події, і виконує операцію wait над своєю умовною змінною. При виконанні операції V над семафором процес збільшує значення лічильника, перевіряє, чи є процеси, чекаючі цієї події, і якщо є, видаляє один з них із списку і виконує операцію signal для умовної змінної, відповідної процесу.

Реалізація семафорів і моніторів за допомогою черг повідомлень

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

Після отримання повідомлення синхронізуючий процес перевіряє значення лічильника, щоб з'ясувати, чи можна зробити необхідну операцію. Операція V завжди може бути виконана, тоді як операція P може зажадати блокування процесу. Якщо операція може бути здійснена, то вона виконується, і синхронізуючий процес посилає підтверджуюче повідомлення. Якщо процес має бути блокований, то його ідентифікатор заноситься в чергу блокованих процесів, і підтвердження не посилається. Пізніше, коли який-небудь з інших процесів виконає операцію V, один з блокованих процесів віддаляється з черги очікування і отримує відповідне підтвердження.

Оскільки ми показали раніше, як з семафорів побудувати монітори, ми довели еквівалентність моніторів, семафорів і повідомлень.

Висновок

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

У попередніх лекціях ми розглядали способи синхронізації процесів, які дозволяють процесам успішно кооперуватися. Проте в деяких випадках можуть виникнути непередбачені утруднення. Припустимо, що декілька процесів конкурують за володіння кінцевим числом ресурсів. Якщо запрошуваний процесом ресурс недоступний, ОС переводить даний процес в стан очікування. У разі коли необхідний ресурс утримується іншим чекаючим процесом, перший процес не зможе змінити свій стан. Така ситуація називається тупиком (deadlock). Говорять, що в мультипрограмній системі процес знаходиться в стані тупику, якщо вона чекає події, яка ніколи не відбудеться. Системна тупикова ситуація, або «зависання системи», є слідством того, що один або більш за процеси знаходяться в стані тупику. Іноді подібні ситуації називають взаимоблокировками. У загальному випадку проблема тупику ефективного рішення не має.

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


Рис. 8.1. Приклад тупикової ситуації

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

Вище приведений приклад взаимоблокировки, що виникає при роботі з так званими виділеними пристроями. Безвихідь, проте, може мати місце і в інших ситуаціях. Hапример, в системах управління базами даних запису можуть бути локалізовані процесами, щоб уникнути стану гонок (див. лекцію 5 «Алгоритмів синхронізації»). В цьому випадку може вийти так, що один з процесів заблокував записи, необхідні іншому процесу, і навпаки. Таким чином, безвихідь може мати місце як на апаратних, так і на програмних ресурсах.

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

Ресурсами можуть бути як пристрої, так і дані. Hекоторые ресурси допускають розділення між процесами, тобто є ресурсами, що розділяються . Наприклад, пам'ять, процесор, диски колективно використовуються процесами. Інші не допускають розділення, тобто є виділеними, наприклад стрічкопротяжний пристрій. До взаимоблокировке може привести використання як виділених, так і таких, що розділяються ресурсів. Наприклад, читання з диска, що розділяється, може одночасно здійснюватися декількома процесами, тоді як запис припускає винятковий доступ до даних на диску. Можна вважати, що частина диска, куди відбувається запис, виділена конкретному процесу. Тому надалі ми виходитимемо з припущення, що безвихідь пов'язана з виділеними ресурсами, тобто безвихідь виникає, коли процесу надається ексклюзивний доступ до пристроїв, файлів і інших ресурсів.

Традиційна послідовність подій при роботі з ресурсом складається із запиту, використання і звільнення ресурсу. Тип запиту залежить від природи ресурсу і від ОС. Запит може бути явним, наприклад спеціальний виклик request, або неявним – open для відкриття файлу. Зазвичай, якщо ресурс зайнятий і запит відхилений, що запрошує процес переходить в стан очікування.

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

Основні напрями боротьби з тупиками

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

Отже, основні напрями боротьби з безвихіддю:

· Ігнорування проблеми в цілому

· Запобігання безвиході

· Виявлення безвиході

· Відновлення після безвиході

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