33. Взаємні блокування

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

1. Потік Т^А блокує доступ до ресурсу R^A.

2. Потік Т^в блокує доступ до ресурсу R^B.

3. Потік Т^А намагається отримати доступ до ресурсу R^B і призупиняється, оскіль­ки той зайнятий потоком Т^в.

4. Потік Т^в намагається отримати доступ до ресурсу R^A і теж призупиняється, ос­кільки той зайнятий потоком Т^А.

34. Умови виникнення взаємних блокувань

Є чотири умови виникнення взаємних блокувань (коли хоча б одна з них не ви­конується, взаємні блокування в системі неможливі):

• взаємне виключення — ресурсом у конкретний момент може володіти тільки один потік, інші мають очікувати;

• утримування і очікування — потік у конкретний момент може володіти кіль­кома ресурсами і робити запити на нові; усі інші потоки мають очікувати, по­ки він не звільнить доступ до своїх ресурсів;

• відсутність витиснення — у потоку не можна відібрати ресурси, якими він во­лодіє, потік має звільнити їх сам;

• циклічне очікування — має існувати така циклічна послідовність потоків, за якої кожен попередній очікує доступу до ресурсу, зайнятого наступним (цик­лічність послідовності полягає в тому, що останній потік чекає ресурсу, зай­нятого першим).

35. Запобігання взаємним блокуванням на рівні ос

У літературі описані складні алгоритми і стратегії виявлення взаємних блоку­вань і запобігання ним в ОС, які використовують переважно теорію графів. Біль­шість таких алгоритмів ґрунтуються на попередніх знаннях про особливості роз­поділу ресурсів між процесами і тому не мають практичного значення (оскільки в системах, де одночасно виконуються сотні процесів, такої інформації бути не може). Докладніше про це сказано в [44].

У більшості сучасних систем використовують найпростіший можливий алго­ритм — «алгоритм страуса»: система не вживає ніяких дій для запобігання взаєм­ним блокуванням, оскільки організація таких дій коштує дорожче, ніж можливі втрати від появи блокувань. Оскільки на практиці блокування з'являються рідко, на них не звертають уваги. Якщо потрібно, відповідне застосування можна явно знищити

36. Підхід ведучого-веденого

Найпростішим підходом до організації потоків є підхід ведучого-веденого (mast­er-slave). Основний (ведучий) потік запускає набір ведених потоків і передає кожному з них його обсяг роботи. Він відомий заздалегідь і нарівно розділений між веденими потоками. Після того як ведучий потік запустить всі ведені, він очікує їхнього завершення, виконуючи операцію приєднання потоків. Потім, якщо це необхідно, ведені потоки запускаються знову для виконання роботи наступного етапу. Цей підхід можна використовувати тоді, коли ведені потоки виконуються не­залежно один від одного, тому між ними не потрібна синхронізація.