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

:: Меню ::

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

:: Друзі ::

Карта сайту
 

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

 

 

 

 

 

Формулювання завдання

  Я щось не бачу пивного рундука.
Мабуть, його
Встигли знести за ніч.
Б. Гребенщиков

Щоб зрозуміти, які ж методики застосовні для взаємодії ниток, що паралельно виконуються, давайте чіткіше сформулюємо завдання. Для цього нам також треба ввести деяку кількість термінів. Крім того, нам доведеться висловити ряд міркувань, частина яких може здатися читачеві банальностямі.
Встановимо, що для кожної з ниток створюється ілюзія строго послідовного виконання (наприклад, обробник переривання може створити для основного потоку програми таку ілюзію, акуратно зберігаючи при виклику і відновлюючи при завершенні всі регістри процесора). Якщо для якоїсь з ниток ця умова не завжди дотримується, ми рахуватимемо її двома або великим числом різних ниток. Якщо ця умова не дотримується ніколи, ми маємо справу з процесором нефон-неймановской архітектура.
Загальноприйнята назва для взаємодії між різними нитками — асинхронна взаємодія у протилежність синхронній взаємодії між різними модулями послідовно виконуваної програми.
Якщо нитка працює лише з об'єктами (під об'єктом ми, в даному випадку, розуміємо не лише групу змінних в оперативній пам'яті або об'єкт в сенсі ООП, але і фізичні об'єкти, наприклад керовані комп'ютером зовнішні пристрої), достаток яких не може бути змінене іншими нитками, проблеми взаємодії, та і самої взаємодії, як такого, не існує.
Якщо нитка працює з об'єктами, достаток яких взагалі не піддається модифікації, наприклад, з кодом або таблицями констант, проблеми також немає. Проблема виникає тоді і лише тоді, коли модифікації піддається об'єкт, що розділяється декількома нитками. При цьому для виникнення проблеми вистачає, щоб лише одна нитка займалася модифікацією, а останні нитки прочитували достаток об'єкту.
Інтервал, протягом якого модифікація порушує цілісність структури даних, що розділяється, і, навпаки, інтервал, протягом якого алгоритм нитки покладається на цілісність цієї структури, називається критичною секцією. Завдання написання коректної багатопотокової програми, таким чином, може вирішуватися двома способами: або викорінюванням критичних секцій зі всіх використовуваних алгоритмів, або забезпеченням гарантії того, що жодні дві нитки ніколи одночасно не увійдуть до критичної секції, пов'язаної з одним і тим же об'єктом, що розділяється. Наявність в програмі критичної секції з негарантованим виключенням і є помилка змагання, яка рано чи пізно спрацює.
Повне викорінювання критичних секцій з коди вимагає глибокої переробки всіх алгоритмів, які використовуються для роботи з даними, що розділяються. Результат такої переробки ми бачили в прикладі 5.2: дивна, на перший погляд, подвійне завантаження регістра в налагодженому записі PLT в даному прикладі обумовлене саме бажанням уникнути проблем при паралельному налаштуванні одного і того ж запису двома різними нитками (як вправа читачеві пропонується розібратися, в якому порядку інтерпретатор модифікує запис, і як виглядає проміжний код). У автора немає прикладів, що демонструють неможливість такої переробки в обшем випадку, але очевидно, що навіть до украй простих алгоритмів вона абсолютно не застосовна на практиці.
Друга дорога — надання гарантій взаємовиключають (mutual exclusion) — також непростий, але, на відміну від першого, практично реалізовується і широко застосовується.

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

Група операцій модифікації структури даних, що розділяється, яка відбувається атомарно (неділимо), не уриваючись жодними іншими операціями з тією ж структурою даних, називається транзакцією. У разд. Монітори і сервери транзакцій ми побачимо радикальніше визначення терміну "транзакція" як групи операцій, які завжди або відбуваються всі разом, або не відбуваються взагалі, навіть якщо під час спроби їх виконання трапиться загальносистемний збій. Зрозуміло, що для реалізації транзакцій того, що одного лише взаємовиключає, що так розуміються, недостатньо.
Програмний модуль, усередині якого є хоч би одна критична секція, для якої не забезпечено взаємне виключення, називається нереєнтерабельним. Виклик процедур такого модуля з різних ниток приведе до помилок змагання і допустимий лише за умови, що зухвала програма реалізує взаємне виключення самостійно. Відповідно, модуль, в якому таких секцій немає, або який сам забезпечує взаємне виключення для них, називається реєнтерабельним (від англ. re-enterable — здібний до повторного входження) або рєєнтрантним (reentrant). У сучасній англомовній літературі часто також уживаються терміни thread-unsafe (для позначення нереєнтерабельних процедур) і thread-safe (відповідно, для реєнтерабельних).
Розглянемо простий випадок об'єкту, що розділяється: змінну прапора, яка може набувати значень True і False . Така змінна, зокрема, може використовуватися для реалізації взаємного виключення в секції, що працює із складнішою структурою даних.
Якщо в критичній секції не знаходиться жодної нитки, змінна рівна False інакше — True. При вході в секцію нам необхідно перевірити значення змінної і, якщо ділянка, що блокується, вільна, привласнити їй True. Даний приклад цікавий не лише своєю простотою, але і тим, що поєднує в собі обох типів критичних секцій: зміна даних, що розділяються, і аналіз даних, які можуть паралельно модифікуватися кимось ще.
Наївний спосіб роботи з такою змінною приведений в прикладі 7.1 (приклад реалізований на паськалеподобном псевдокоді. Оператори parbegin/parend символізують паралельного виконання укладених між ними операторів). Здавалося б, важко уявити собі простішу програму, проте саме завдяки простоті легко зрозуміти, що вона нікуди не годиться: перевірка прапора і його установка реалізуються двома різними операторами, в проміжку між якими інший процес може отримати управління і також встановити змінну прапора! Вікно, в якому відбувається змагання, складає всього две-трі команди, але при попаданні обох процесів в це вікно ми отримуємо якраз те, чого прагнули уникнути: обидва процеси можуть увійти до критичної секції одночасно.

Приклад 7.1. Наївна реалізація взаємного виключення на основі змінної прапора


program прапор;
var flag: Boolean;
procedure процессодін;
begin
while True do begin
while flag do;
flag := True;
крітічеськаясекция!;
flag := False;
...
end
end;
procedure процессдва; begin
while True do begin
while flag do;
flag := True;
крітічеськаясекция2;
flag := False;
end
end;
oegin
flag:= False;
parbegin
процессодін;
процессдва;
parend
еnd.

 

:: Реклама ::

 

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


 

 

 


Copyright © Kivik, 2017