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

:: Меню ::

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

:: Друзі ::

Карта сайту
 

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

 

 

 

 

 

Паралелізм з точки зору програміста

  Ти вибежалза кут купити вина
Ти повернувся, а замість будинку стіна.
Б. Гребенщиков

На палубу вийшов, і палуби немає
У очах у нього помутилося.
В. Пельовін

У попередній главі ми бачили, що навіть в сучасному однопроцесорному персональному комп'ютері відбувається безліч паралельних процесів: звукова карта грає, жорсткий диск і мережевий інтерфейс передають дані, користувач рухає мишею — робота кипить! А що почнеться, якщо користувач запустить завдання на друк, так і просто страшно подумати. Написання програм, здатних працювати в середі з безліччю процесів, що паралельно відбуваються, є нетривіальним завданням. На перший погляд, складнощі тут жодної немає — апаратура надає нам механізм переривань. Обробив переривання — і настало щастя. Насправді, жодного щастя від однієї лише обробки переривання не настане, поки ми не повідомимо про подію, що сталася, основний потік програми, зацікавленої в цій події.
Основний потік програми і що реалізовуються цією програмою обробники переривань повинні взаємодіяти і розділяти ті або інші дані. При цьому в обробнику переривання ми не завжди можемо точно з'ясувати, в якій крапці основний потік програми був перерваний (в принципі, можна проаналізувати збережений лічильник команд і, можливо, локальні змінні основного потоку, але це дуже складно і само по собі навряд чи наблизить нас до реалізації коректно взаємодіючих потоків), а основний потік не завжди може знати, в який момент відбувалося (і чи відбувалося) переривання.
Більшість практично вживаних структур даних повинні відповідати тим або іншим припущенням критеріям цілісності. Наприклад, у впорядкованому масиві кожен наступний елемент має бути больще (те, що в даному конкретному випадку мається на увазі під "більше", називається критерієм або умовою сортування) попереднього або дорівнює йому основний спосіб модифікації впорядкованого масиву — це вставка в нього додаткового елементу. Вставка в такий масив може бути здійснена різними способами, наприклад, додаванням нового елементу в кінець і виконанням сортування методом "бульбашки", або пошуком місця, куди елемент має бути вставлений, і переміщенням елементів з великими індексами.
Поважно, що будь-який спосіб вставки відбувається не миттєво, і весь час роботи цієї процедури масив не є впорядкованим. Якщо вставка відбувалася в основному потоці програми, обробник переривання, який в цей час спробує працювати з масивом, як з впорядкованим — наприклад, провести в нім дихотомічний пошук — буде жорстоко розчарований.
Завдання розробки програми, що взаємодіє з обробником переривання, таким чином, може бути переформулірована як написання програми, деякі змінні якої схильні до зміни в непередбачувані моменти часу.
Ця обставина різко ускладнює аналіз алгоритмів (зокрема, доказ коректності програм) і доставило свого часу багато хвилювань теоретикам програмування. Наприклад, в [Дейкстра 1978] один із засновників структурного програмування, Е. Дейкстра, дуже емоційно описує свою реакцію при першому зіткненні з системою, що використовує переривання. Окрім теоретичних складнощів, розробка таких програм зв'язана і із складнощами практичними.
При розробці паралельної програми ми можемо неявно сделать і використовувати при кодуванні припущення, що достаток деякого об'єкту в деякий період часу не міняється — а воно може змінитися. Якщо така помилка зроблена в програмі, що послідовно виконується, вона може бути виявлена при першому ж тестовому прогоні. Для виявлення ж її в програмі з модулями, що асихронно виконуються, буде потрібно значно більше тестових запусків, при яких ми повинні викликати переривання в різні моменти часу.
Для вичерпного тестування необхідно перебрати всі можливі відносні моменти виклику переривання, тобто забезпечити хоч би раз виклик переривання після кожної з команд в кожній з можливих послідовностей виконання основної програми. Вартість такого тестування заборонний висока, тому помилки такого роду (у англомовній літературі вони називаються race condition (дослівно — помилка змагання), хорошого ж російського терміну авторові невідомо) практично неможливо викоренити в процесі тестування.
Таким чином, єдиний спосіб уникнути помилок змагання — це не робити їх. Для того, щоб не робити помилок, потрібна формальна методика розробки і кодування програм, що паралельно виконуються. Зрозуміло, що і наявність методики не може повністю виключити помилки. Проте, якщо вироблена методика адекватна, кожна помилка буде її порушенням, тому помилки можуть виявлятися аналізом коди на відповідність формальним вимогам.
На щастя, авторові цієї книги немає необхідності займатися розробкою такої методики з чистого аркуша. Досить лише, по можливості зв'язно, викласти вже винайдені методи. Не утруднятиму себе і читача повним доказом коректності пропонованих методик, приводячи лише "інтуїтивне" обгрунтування їх застосовності. Сумнівається можу запропонувати або розробити повний доказ самостійно, або звернутися до спеціальної літератури, наприклад [Хоар 1989].
Приведене раніше формулювання завдання справедливе не лише для взаємодії основного потоку програми з обробником переривання, але і для взаємодії програм, що виконуються на різних процесорах, а також для програми, що безпосередньо взаємодіє із зовнішніми подіями, наприклад за допомогою опиту. У разд. Витісняюча багатозадачність ми побачимо, що [псевдо]паралельні нитки виконань, що не є обробниками переривань, досить легко можна реалізувати на однопроцесорній машині, і практично всі сучасні ОС надають такий сервіс.
Більшість концепцій, що обговорюються в цій главі, прикладені до всіх перерахованих випадків, тому далі в тексті ми говоритимемо не про програму і обробника переривання, а про два або більш потоках або нитках виконань. Насправді, одна з взаємодіючих "ниток" може не бути процесом виконання програми, а бути фізичним процесом (наприклад, перемотування стрічки, переміщення прочитуючої голівки дисковода, або хімічну або навіть ядерну реакцію в установці, якою управляє наш комп'ютер) або процесом, що відбувається в голові або інших модулях нервової системи користувача-людини, але в більшості випадків нас ця тонкість не цікавить.

 

:: Реклама ::

 

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


 

 

 


Copyright © Kivik, 2017