Critical Sections
У складі API ОС Windows є спеціальні та ефективні функції для організації входу в критичну секцію і виходу з неї потоків одного процесу в режимі користувача. Вони називаються EnterCriticalSection і LeaveCriticalSection і мають в якості параметра попередньо проініціалізувати структуру типу CRITICAL_SECTION.
Орієнтовна схема програми може виглядати наступним чином.
Функції EnterCriticalSection і LeaveCriticalSection реалізовані на основі Interlocked -функцій, виконуються атомарним чином і працюють дуже швидко. Суттєвим є те, що в разі неможливості входу в критичний ділянку потік переходить в стан очікування. Згодом, коли така можливість з'явиться, потік буде "розбуджений" і зможе зробити спробу входу в критичну секцію. Механізм пробудження потоку реалізований за допомогою об'єкта ядра "подія" (event), яке створюється тільки в разі виникнення конфліктної ситуації.
Уже говорилося, що іноді, перед блокуванням потоку, має сенс деякий час утримувати його в стані активного очікування. Щоб функція EnterCriticalSection виконувала задане число циклів спін-блокування. критичну секцію доцільно проинициализировать за допомогою функції InitalizeCriticalSectionAndSpinCount.
прогін програми
В якості самостійного вправи рекомендується реалізувати синхронізацію в вище наведеній програмі async за допомогою перерахованих примітивів. Важливо не забувати про коректний вихід із критичної секції, тобто про парне використання функцій EnterCriticalSection і LeaveCriticalSection.
Синхронізація потоків з використанням об'єктів ядра
Критичні секції, розглянуті в попередньому розділі, підходять для синхронізації потоків одного процесу. Завдання синхронізації потоків різних процесів прийнято вирішувати за допомогою об'єктів ядра. Об'єкту ядра може бути присвоєно ім'я, вони дозволяють задавати тайм-аут для часу очікування і володіють ще рядом можливостей для реалізації гнучких сценаріїв синхронізації. Однак їх використання пов'язане з переходом в режим ядра (приблизно 1000 тактів процесора), тобто вони працюють трохи повільніше, ніж критичні секції.
Майже всі об'єкти ядра, розглянуті раніше, в тому числі, процеси, потоки і файли, придатні для вирішення завдань синхронізації. У контексті завдань синхронізації про кожного з об'єктів можна сказати, чи знаходиться він у вільному (сигнальному, signaled state) або зайнятому (nonsignaled state) стані. Правила переходу об'єкта з одного стану в інший залежать від об'єкта. Наприклад, якщо потік виконується, то він знаходиться в зайнятому стані, а якщо потік успішно завершив очікування семафора, то семафор знаходиться в зайнятому стані.
Потоки знаходяться в стані очікування, поки очікувані ними об'єкти зайняті. Як тільки об'єкт звільняється, ОС будить потік і дозволяє продовжити виконання. Для припинення потоку і переведення його в стан очікування звільнення об'єкта використовується функція
де hObject - описувач очікуваного об'єкта ядра, а другий параметр - максимальне час очікування об'єкта.
Потік створює об'єкт ядра за допомогою сімейства функцій Create (CreateSemaphore, CreateThread і т.д.), після чого об'єкт за допомогою описателя стає доступним всім потокам даного процесу. Копія описателя може бути отримана за допомогою функції DuplicateHandle і передана іншому процесу, після чого потоки зможуть скористатися цим об'єктом для синхронізації.
Іншим, більш поширеним способом отримання описателя є відкриття існуючого об'єкта на ім'я, оскільки багато об'єктів мають імена в просторі імен об'єктів. Ім'я об'єкта - один з параметрів Create -функцій. Знаючи ім'я об'єкта. потік. володіє потрібними правами доступу, отримує його описувач за допомогою Open -функцій. Нагадаємо, що в структурі, яка описує об'єкт. є лічильник посилань на нього, який збільшується на 1 при відкритті об'єкта і зменшується на 1 при його закритті.
Дещо детальніше розглянемо ті об'єкти ядра, які призначені безпосередньо для вирішення проблем синхронізації.
Відомо, що семафори, запропоновані Дейкстрой в 1965 р являє собою цілу змінну в просторі ядра, доступ до якої, після її ініціалізації, може здійснюватися через дві атомарні операції. wait і signal (в ОС Windows це функції WaitForSingleObject і ReleaseSemaphore відповідно).
Семафори зазвичай використовуються для обліку ресурсів (поточне число ресурсів задається змінною S) і створюються за допомогою функції CreateSemaphore. в число параметрів якої входять початкове і максимальне значення змінної. Поточне значення не може бути більше максимального і негативним. Значення S. рівне нулю, означає, що семафор зайнятий.
Нижче наведено приклад синхронізації програми async за допомогою семафорів.
У даній програмі синхронізація дій двох потоків. забезпечує однаковий результат для всіх запусків програми, виконана за допомогою двох семафорів, приблизно так, як це робиться в завданні producer- consumer. см. наприклад [Таненбаум]. Потоки по черзі відкривають один одному дорогу до критичного ділянці. Першим починає працювати потік SecondThread. оскільки значення лічильника утримує його семафора проініціалізувати одиницею при створенні цього семафора. Синхронізацію за допомогою семафорів потоків різних процесів рекомендується виконати в якості самостійного вправи.
М'ютекси також є об'єктами ядра, використовувані для синхронізації, але вони простіше семафорів, так як регулюють доступ до єдиного ресурсу і, отже, не містять лічильників. По суті вони поводяться як критичні секції, але можуть синхронізувати доступ потоків різних процесів. Ініціалізація мьютекса здійснюється функцією CreateMutex. для входу в критичну секцію використовується функція WaitForSingleObject. а для виходу - ReleaseMutex.
Якщо потік завершується, чи не звільнивши м'ютекс, останній переходить у вільний стан. Відмінність від семафорів в тому, що потік, який посів м'ютекс, отримує права на володіння ним. Тільки цей потік може звільнити м'ютекс. Тому думка про м'ютексів як про семафорі з максимальним значенням 1 не повною мірою відповідає дійсності.
Об'єкти "події" - найбільш примітивні об'єкти ядра. Вони призначені для інформування одного потоку іншим про закінчення будь-якої операції. Події створюються функцією CreateEvent. Найпростіший варіант синхронізації: переводити подію в зайняте стан функцією WaitForSingleObject і у вільний - функцією SetEvent.
У керівництві з програмування [Ріхтер]. [Харт]. розглядаються більш складні сценарії, пов'язані з типом події (скидаються вручну і скидаються автоматично) і з управлінням синхронізацією груп потоків, а також ряд додаткових корисних функцій.
Розробку програм, в яких для вирішення завдань синхронізації використовуються м'ютекси і події, рекомендується виконати в якості самостійного вправи.
Сумарні відомості про об'єкти ядра
В інструкціях по програмуванню, див., Наприклад, [Ріхтер]. і в MSDN містяться відомості і про інші об'єкти ядра стосовно синхронізації потоків.
Зокрема, існують такі властивості об'єктів:
- процес і потік знаходяться в зайнятому стані, коли активні, і у вільному стані, коли завершуються;
- файл знаходиться в зайнятому стані, коли виданий запит на введення-виведення, і у вільному стані, коли операція введення-виведення завершена;
- повідомлення про зміну файлу знаходиться в зайнятому стані, коли в файлової системі немає змін, і в вільному - коли зміни виявлені;
- і т.д.
Синхронізація в ядрі
Рішення проблеми взаємовиключення особливо актуально для такої складної системи, як ядро ОС Windows.
Одна з проблем пов'язана з тим, що код ядра часто працює на пріоритетних IRQL (рівні IRQL розглянуті в "Базові поняття ОС Windows") рівнях "DPC / dispatch" або "вище", відомих як "високий IRQL". Це означає, що традиційні засоби синхронізації. пов'язані з припиненням потоку, не можуть бути використані, оскільки процедура планування і запуску іншого потоку має більш низький пріоритет. Разом з тим існує небезпека виникнення події, чий IRQL вище, ніж IRQL критичного ділянки, який буде в цьому випадку витіснений. Тому в подібних ситуаціях вдаються до прийому, який називається "заборона переривань" [Карпов]. [Таненбаум]. У разі Windows цього домагаються, штучно підвищуючи IRQL критичного ділянки до найвищого рівня, використовуваного будь-яким можливим джерелом переривань. В результаті критичний ділянку може безперешкодно виконати свою роботу.
На жаль, для мультипроцесорних систем подібна стратегія не годиться. Заборона переривань на одному з процесорів не виключає переривань на іншому процесорі, який може продовжити свою роботу і отримати доступ до критичних даними. У цьому випадку потрібен спеціальний протокол установки взаємовиключення. Основою цього протоколу є установка блокує змінної (зміною-замку), зіставленої з кожної глобальною структурою даних, за допомогою TSL команди. Оскільки установка замку відбувається в результаті активного очікування. то кажуть, що код ядра встановлює (захоплює) спін-блокування. Установка спін-блокування відбувається при високих IRQL рівнях, тому код ядра, захоплюючого спін-блокування і утримує її для виконання критичної секції коду, ніколи не витісняється. Установка і звільнення спін-блокувань здійснюється функціями ядра KeAcquireSpinlock і KeReleaseSpinlock. які активно використовуються в ядрі і драйвери пристроїв. На однопроцесорних системах установка і зняття спін-блокувань реалізується простим підвищенням і пониженням IRQL.
Нарешті, маючи набір глобальних ресурсів, в даному випадку - спін-блокувань, необхідно вирішити проблему виникнення потенційних тупиків [Сорокіна]. Наприклад, потік 1 захоплює блокування 1, а потік 2 захоплює блокування 2. Потім потік 1 намагається захопити блокування 2, а потік 2 - блокування 1. В результаті обидва потоки ядра виснуть. Одним з варіантів розв'язання проблеми є нумерація всіх ресурсів і виділення їх тільки в порядку зростання номерів [Карпов]. У разі Windows є ієрархія спін-блокувань: все, вони будуть розміщені в список в порядку убування частоти використання і повинні захоплюватися в тому порядку, в якому вони вказані в списку.
У разі низьких IRQL синхронізація здійснюється традиційним чином - за допомогою об'єктів ядра.
висновок
Проблема недетермінізма є однією з ключових в паралельних обчислювальних середовищах. Традиційне рішення - організація взаємовиключення. Для синхронізації із застосуванням змінної-замку використовуються Interlocked -функції, що підтримують атомарность деякої послідовності операцій. Взаємовиключення потоків одного процесу найлегше організувати за допомогою примітиву Crytical Section. Для більш складних сценаріїв рекомендується застосовувати об'єкти ядра, зокрема, семафори, м'ютекси і події. Розглянуто проблему синхронізації в ядрі, основним рішенням якої можна вважати установку і звільнення спін-блокувань.