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

:: Меню ::

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

:: Друзі ::

Карта сайту
 

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

 

 

 

 

 

Гармонійно взаємодіючі послідовні потоки

У разд. Формулювання завдання ми бачили, що проблеми того, що взаємовиключає і синхронізації виникають тоді і лише тоді, коли декілька ниток розділяють один і той же ресурс. Те, що взаємовиключає доступу до даних, що розділяються, приводить до необхідності вводити додаткову суть (семафори і інші примітиви того, що взаємовиключає і синхронізації) і ускладнювати програму.
Необгрунтоване розширення ділянок виняткового доступу приводить до зростання часу реакції системи і зниження продуктивності, а прагнення скоротити їх може привести до помилок змагання. Структури даних, що тому розділяються, є предметом ненависті теоретиків і джерелом серйозних помилок при розробці програм.
Бажання усунути ці проблеми привело свого часу Е. Дейкстру до концепції, відомої як гармонійно взаємодіючі послідовні потоки. Ця концепція полягає в наступному.

  1. 1. Кожним потоком (нитка) є незалежний програмний модуль, для якого створюється ілюзія чисто послідовного виконання.
  2. 2. Нитки не мають даних, що розділяються.
  3. 3. Всі обміни даними і взагалі взаємодія відбуваються з використанням спеціальних примітивів, які одночасно виконують і передачу даних, і синхронізацію.
  4. 4. Синхронізація, що не супроводиться передачею даних, просто літ6" на сенсу — нитки, що не мають структур даних, що розділяються, абсолютно незалежні і не мають ні критичних крапок, ні нереєнтерабельних модулів.

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

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

Гармонійна взаємодія, строго кажучи, не виключає проблему мертвого блокування: замкнувши гармонійно взаємодіючі нитки в кільце (А отримує інформацію від В, У від З, З від А), ми можемо отримати класичне триланкове мертве блокування. Втім, в даному випадку блокування вимагає наявність циклічної залежності даних, яка свідчить про серйозні помилки проектування програми (і, можливо, про внутрішню суперечність вимог до цієї програми). Така помилка може бути відносне легко виявлена за допомогою формального аналізу специфікацій і потоків даних.
На практиці, втім, гармонійна взаємодія обходить основну масу проблем, що виникають при тому, що взаємовиключає доступу до багатьом ресурсам, — і блокування, і "проблему голодного філософа". Річ у тому, що гармонійно взаємодіючий потік має справу не з ресурсом, що розділяється, безпосередньо, а з копією достатку цього ресурсу. Якщо нам потрібно два ресурси, ми (не обов'язково одночасно) знімаємо з них дві копії — для цього нам не треба одночасно захоплювати самі ресурси.
Зокрема, тому групові операції над примітивами гармонійної взаємодії (оператор select у Ada, системний виклик select у системах сімейства Unix, команда alt у трансп'ютері) працюють не за принципом транзакції, а повертають управління і дані за умови, що хоч би один з примітивів групи готовий ці дані надати. Відтворити "проблему голодного філософа" в цих умовах неможливо.
У сучасних системах реалізований цілий ряд засобів, які здійснюють передачу даних спільно з синхронізацією: поштові скриньки (mailboxes) в системах лінії Rsx-11 — VMS, труби (pipes) (у російськомовній літературі їх часто називають програмними каналами) в UNIX, рандеву (rendesvous — побачення) в мові Ada, лінки (link — з'єднання) в мікропроцесорах сімейства Transputer і так далі Більшість цих засобів обговорюватимуться детальніше в разд. Приклади реалізацій засобів гармонійної взаємодії.
Примітиви синхронного обміну даними відрізняються великою різноманітністю. Основні принципи класифікації такі.

  1. 1. Примітиви можуть бути двоточкові (що допускають лише один прийом, ник і один передавач), або багатоточкові, допускаючі декілька приймачів і передавачів. Многоточечность буває як симетрична коли може бути декілька і приймачів, і передавачів, так і асиметрична: один передавач і багато приймачів — широкомовна (broadcast) або групова (multicast) передача — або один приймач і багато передавачів.
  2. 2. Примітив може передавати неструктурований потік байтів, або структуровані дані, розбиті на повідомлення певного розміру. У першому випадку передавач може породжувати дані блоками одного розміру, а приймач — прочитувати їх блоками іншого розміру В другому випадку приймач завжди зобов'язаний прочитати повідомлення цілком (можливо, відкинувши якусь його частина). Повідомлення можуть бути як фіксованого, так і змінного розміру.
  3. 3. Примітив може бути синхронним, таким, що буферизує або з негарантованою доставкою. У першому випадку передавач вимушений чекати, поки приймач не прочитає всі передані дані. У другому, дані складаються в буфер і можуть бути прочитані приймачем пізніше. У третьому випадку, якщо потенційний приймач не був готовий прийняти повідомлення, воно просто ігнорується.

Синхронні примітиви можуть використовуватися не лише для гармонійної взаємодії, але і для реалізації примітивів чистої синхронізації. Зокрема, в підручниках з мови Ada (наприклад [Василеську 1990]) і по програмуванню для трансп'ютерів (наприклад [Харп 1993]) чомусь люблять наводити приклади реалізації семафорів, відповідно, рандеву і лінков.
Примітиви, що буферизують, для синхронізації використані бути не можуть. Зате буферизація корисна, якщо нам треба погоджувати швидкості роботи ниток, що мають різні пріоритети, — наприклад, якщо нитка реального часу повинна швидко обробити подію і передати частину даних для відкладеної обробки менш пріоритетною ниткою, не допустившись при цьому власного блокування.
Примітив, що буферизує, може бути легко реалізований на основі пари синхронних примітивів і нитки-монітора буфера (або черги). У цьому сенсі, синхронні примітиви є більш низькорівневими, ніж що буферизують.
Синхронні примітиви за природою своїй завжди двоточкові. Та і в разі примітивів, що буферизують, багатоточкова взаємодія не завжди легко реалізовується, а інколи просто небезпечно, особливо в разі потокової передачі даних: операція прочитування даних з потоку необратіма, а природного розбиття потоку на повідомлення немає, тому якщо один з приймачів помилково захопить шматок повідомлення, призначеного не йому, то дані в потоці будуть необоротний зіпсовані.
Втім, деякі потокові примітиви, наприклад труби (pipes) в системах сімейства Unix, допускають (хоча документація і рекомендує пользо-яться цим з обережністю) наявність декількох передавачів при одному приймачі.
Навпаки, симетрично багатоточкові черги повідомлень широко поширені. Часто такі примітиви дозволяють споживачеві відбирати повідомлення з черги по якомусь критерію, наприклад за значенням спеціального поля, званому типом або тегом. Ряд широкомовних і групових сервісів передачі даних відноситься до категорії примітивів з негарантованою доставкою.
Другий і третій критерії нашої класифікації (якщо доки відвернутися від сервісів з негарантованою доставкою) практично ортогональні один одному: існують всі чотири варіанти (таблиця. 7.1). Легко зрозуміти, що передавати потік неструктурованих даних в режимі негарантованої доставки безглуздо: розриви потоку неминучі, а ми не зможемо навіть взнати, чи стався такий розрив, і якщо стався, то де. Всі існуючі сервіси з негарантованою доставкою передають лише повідомлення.

Таблиця 7.1. Примітиви синхронізованной передачі даних

Примітиви Синхронні Що буферизують
Потокові Лінки (трансп'ютер) Труби (Unix), сокети (Tcp/ip)
Структуровані Рандеву (Ada) Черги повідомлень

На перший погляд, взагалі незрозуміло, чому комусь може бути корисний сервіс з негарантованою доставкою. Але під цей опис личать багато низькорівневих мережевих протоколів (Ethernet, IP) і деякі відносно високорівневі мережеві сервіси, так звані дейтаграммниє протоколи. Прикладом такого сервісу є UDP (User Datagram Protocol), що входить в сімейство протоколів Tcp/ip.
У мережевих протоколах відсутність гарантії доставки повідомлення має двоякий сенс — повідомлення може бути втрачене не лише через неувагу одержувача, але і із-за фізичних помилок передачі або перевантаження маршрутизаторів і каналів зв'язку по дорозі від передавача до приймача. У цьому сенсі можна сказати, що розробники мережевих протоколів вимушені використовувати негарантовану доставку не тому, що їм потрібна Саме вона, а тому, що інших засобів-то і ні.
У чистому вигляді негарантована доставка прийнятна для реалізації одиночних запитів, на які повинна послідувати одиночна ж відповідь. Якщо відповіді за визначений протоколом інтервал часу немає, передавач повторює запит, а після деякої кількості спроб приходить до висновку, що приймач не функціонує, або взагалі відсутній.
Для реалізації надійного зв'язку на основі сервісів з негарантованою доставкою використовуються різного роду підтвердження, так зване квитування. Зрозуміло, що при реалізації квитування необхідно брати до уваги можливість втрати не лише самого підтверджуваного повідомлення, але і пакету-підтвердження. Зрозуміло також, що в більшості випадків посилка підтвердження на кожне повідомлення, що прийшло, недоцільна. Тому реальні протоколи такого роду відносно складні (див. наприклад [RFC 0793]) і їх обговорення заслуговує на окрему книгу. Накладні витрати при реалізації таких протоколів значительни, тому часто виявляється доцільно змиритися з негарантованою доставкою.
Концепція гармонійно взаємодіючих процесів дуже приваблива з теоретичної точки зору і дозволяє легко писати правильні програми. Проте всі примітиви синхронізованной передачі даних погані саме тим, що вимагають передачі, копіювання даних. І передавач, і приймач вимушені мати по буферу, в якому дані слід зберігати (в разі примітивів, що буферизують, дані зберігаються тричі). Накладні витрати при копіюванні даних великого об'єму також можуть виявитися значними.
Якщо нитки виконуються на різних комп'ютерах, що не мають спільної пам'яті і сполучених лише відносно (в порівнянні з системною шиною) низькошвидкісними мережевими каналами, ми так чи інакше не можемо обійтися без передачі і подвійного зберігання даних. Втім, навіть і в цьому випадку інколи має сенс подумати про вживання багатопортової пам'яті або реалізацій NUMA або сома-архітектури.
При виконання ж ниток на одній машині, з міркувань продуктивності і економії пам'яті нерідко виявляється недоцільно відмовлятися від пам'яті, що розділяється, і повністю переходити на примітиви гармонійної взаємодії. Найчастіше це відбувається, коли до ресурсу виконується багато звернень для читання, а модифікації відносно рідкі, і при цьому дані мають великий об'єм. Навіть в цьому випадку буває доцільно замінити пряме розділення пам'яті на моніторний процес. а при доступі до даних отримувати у нього лише безпосередньо необхідне їх підмножина. Проте ситуації бувають різні, і не завжди таке рішення виявляється оптимальним.
У цьому сенсі пам'ять, що розділяється, нагадує інший предмет ненависті структурних програмістів — оператора goto. І те, і інше при безрозсудному використанні є потенційним джерелом помилок і проблем, але інколи без них виявляється не можна обійтися.

 

:: Реклама ::

 

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


 

 

 


Copyright © Kivik, 2017