Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

рейтинг ТОП 5 российских хостингов

Мертві і живі блокування

  Потім ударили морози.
Замерзнуло все, лисиця пішла в кредит. Ведмідь же вмерзнув в дупло
І до цих пір дивиться.
Би. Гребінників.

Вирішивши проблему того, що взаємовиключає для одиночних ресурсів, що розділяються, ми ще не можемо розслаблятися. Річ у тому, що якщо ми використовуємо будь-які механізми того, що взаємовиключає для доступу до декількох різних ресурсів, може виникнути специфічна проблема, звана мертвим блокуванням (dead lock).
Розглянемо дві нитки, кожна з яких працює з двома різними ресурсами одночасно. Наприклад, одна нитка копіює дані із стріммера на касету Exabyte, а інша — у зворотному напрямі. Доступ до стріммеру контролюється змінній прапора flag1 а до касети — flag2 (замість змінних прапорів можуть використовуватися і складніші засоби того, що взаємовиключає).
Перша нитка спочатку встановлює flag1 потім fiag2 друга поступає навпаки. Тому, якщо друга нитка отримає управління і замкне flag2 у проміжку між відповідними операціями першої нитки, то ми отримаємо мертве блокування (мал. 7.1) — перша нитка ніколи не визволить flag1 бо стоїть в черзі в змінної flag2 зайнятою другою ниткою, яка стоїть в черзі в flagi, зайнятою першою.

Мал. 7.1. Мертве блокування

Всі останні нитки, що намагаються дістати доступ до стріммеру або касети, також ставатимуть у відповідні черги і чекатимуть, поки адміністратор не зніме одне із завдань, що "замкнулися".
Цикл взаємного чекання може полягати і з більшої кількості ниток Можливе також мертве блокування за участю лише одній нитки і одного ресурсу: для цього досить спробувати захопити одну і ту ж змінну прапора двічі. Критерієм блокування є утворення замкнутого циклу в графі чекаючих один одного завдань.
Ця проблема може бути вирішена декількома способами. Часто вживане рішення, що володіє, втім, серйозними недоліками — це відправка повідомлення програми про те, що спроба встановити примітив того, що взаємовиключає приведе до мертвого блокування. Це рішення небезпечне по-перше, тим, що сильно ускладнює кодування: тепер ми вимушені брати до уваги не лише можливість захвату примітиву іншою ниткою, але і складніші ситуації. По-друге, отримавши помилку установки прапора, програміст випробовує сильну спокусу зробити саме те, чого робити в даному випадку не можна: повторити спробу захвату ресурсу.
Розглянемо ситуацію, коли дві нитки намагаються захопити необхідні ним ресурси, отримують повідомлення про можливість мертвого блокування, і тут же повторюють спробу захвату того ж ресурсу. Оскільки звільнення ресурсів не відбувається, взаємозалежність між цими нитками не усувається, і повторний захват також приводить до повідомлення про можливість мертвого блокування. Якщо нитки циклічно повторюватимуть спроби захвату, ми отримаємо багатство, яке називається живим блокуванням (livelock) (мал. 7.2). Цей достаток рідше розглядається в підручниках, але теоретично воно анітрохи не краще за мертве блокування. Практично ж воно набагато гірше — якщо нитки, що зачепилися намертво, тихо висять і заподіюють шкоду лише тим ниткам, яким могли б знадобитися зайняті ними ресурси, то нитки, що зачепилися живцем, непродуктивно витрачають час центрального процесора.

Мал. 7.2. Живе блокування

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

Живе блокування при арбітражі шини
Розглянемо процес арбітражу шини: два пристрої змагаються за доступ до середи передачі. Пристрій починає передачу і при цьому порівнює передаваний сигнал з тим, що приймається з шини. Виникнення розбіжностей між цими сигналами інтерпретується як колізія (collision) — передбачається, що розбіжності обумовлені роботою іншого передавача. Виявивши колізію, пристрій припиняє передачу. Сигнал поширюється по шині з кінцевою швидкістю, тому припинити передачу будуть вимушений обидва пристрої (у разд. Пристрої графічного виходу ми побачимо приклад того, як в низькошвидкісних локальних шинах це обмеження можна обійти). Таким чином, обидва пристрої не можуть почати передачу відразу ж після того, як в шині "встановиться тиша": це приведе до живого блокування. Схема дозволу колізій Csma/cd (Carrier Sence Multiple Access/collision Detection, множинний доступ з прослухуванням тієї, що несе і виявленням колізій), використовувана в протоколах локальних мереж сімейства Ethernet, вимагає від пристрою, що виявив колізію, чекання протягом випадкового інтервалу часу.

Єдино правильна реакція на здобуття повідомлення про мертве блокування — це визволити всі зайняті ниткою ресурси і почекати протягом випадкового проміжку часу. Таким чином, пошук можливих блокувань сильно ускладнює і логіку роботи самих примітивів того, що взаємовиключає (потрібно підтримувати граф, що описує, КТО КТО чекає), і код, що використовує ці примітиви.
Просте альтернативне рішення — дозволити кожній нитці в кожен момент часу тримати захопленим лише один об'єкт — простий і вирішує проблему в корені, але часто виявляється неприйнятним. Більше личить угода про те, що захвати ресурсів повинні завжди відбуватися в певному порядку. Цей порядок може бути будь-яким, поважно лише, щоб він завжди дотримувався.
Ще один варіант рішення полягає в наданні можливості об'єднувати примітиви і операції над ними в групи. При цьому програма може виконати операцію захвату прапорів fiag1 і fiag2 єдиною командою, під час виконання якої жодна інша програма не може дістати доступ до цих змінних. Групова операція виконується як транзакція, тобто або відбувається вся цілком, або не відбувається взагалі. Якщо хоч би одна з операцій групи приводить до чекання, груповий примітив знімає всі прапори, які встиг поставити до цього.
Чекання із звільненням ресурсів, втім, породжує ряд більш специфічних проблем. Розглянемо одну з них: нитки А потрібні ресурси X і Y, які вона розділяє, відповідно, з нитками В И С. Якщо нитка А захоплює ресурси відповідно до запропонованого протоколу (визволяючи їх при невдалій спробі захвату), можливий такий сценарій виконання ниток В і З, при якому нитка А не отримає доступу до ресурсів ніколи. Навпаки, захват ресурсів у міру їх звільнення іншими нитками може (якщо В і Із зчеплені по якихось іншим ресурсам) привести до мертвого блокування. Спільного рішення задачі дозволу блокувань і родинних ним ситуацій при тому, що взаємовиключає доступу до багатьом ресурсам на сьогодні не запропоновано.
Описане вище явище інколи називають "проблемою голодного філософа". Історія цієї колоритної назви сходить до моделі, яку використовував для демонстрації описаного цього феномену.
Деяка кількість (в Е. Дейкстри — п'ять) філософів сидить довкола столу, на якому коштує блюдо спагетті (замість спагетті можна узяти, наприклад, млинці). Спагетті їдять двома вилками. У нашому випадку, кількість вилок дорівнює кількості філософів, так що сусіди за столом розділяють вилку (гігієнічний аспект проблеми ми опускаємо).
Кожен філософ деякий (змінний) проміжок часу роздумує, потім намагається узяти лежачі поряд з ним вилки (мал. 7.3). Якщо йому це удається, він береться за їду. Їсть він також змінний проміжок часу, після цього відкладає вилки і знов занурюється в роздуми. Проблеми виникають, коли філософ не може узяти одну з вилок.

Мал. 7.3. Філософи, що обідають

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

Мал. 7.4. Мертве блокування у виконанні п'яти філософів

Цикл можна розімкнути, пронумерувавши вилки і зажадавши, щоб кожен філософ брат спочатку вилку з меншим номером, і тільки потім — з великим. Якщо вилки пронумеровані за годинниковою стрілкою, для всіх філософів, окрім одного, ця вимога збігається з висловленим в попередньому абзаці — спочатку брати праву вилку, і лише потім чекати лівою. Проте для того, КТО попав між п'ятою і першою вилками, це правило звертається — він повинен спочатку діждатися лівої вилки, і тільки потім праву. Легко продемонструвати, що цей філософ в середньому буде своїх вилок довше, ніж останні четверо.
Якщо ж філософ бере вилки тоді і лише тоді, коли вони доступні обидві одночасно, це може привести до проблеми голодного філософа-согласовав свої дії, сусіди бідолахи можуть необмежено довгий час залишати його голодним (мал. 7.5).

Мал. 7.5. Голодний філософ

 

:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017