Алгоритми синхронізації

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

Проблема взаємного виключення

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

Ресурс - це загальний термін, що описує фізичний пристрій або область пам'яті , які можуть запитуватися для використання декількома завданнями. Якщо ресурс може бути використаний одночасно кількома завданнями , то він називається розділяються . Якщо в даний момент часу ресурс може бути використаний тільки одним завданням , то він є неподілюваний. Неподілюваний ресурс називається критичним.

Нерозділення ресурсів відбувається по одній з наступних причин :

Фізична природа ресурсу унеможливлює його поділ : типовий приклад - принтер : неможливо переключити його між печаткою аркушів різних процесів .

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

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

Давайте тимчасово відвернемося від операційних систем , процесів і ниток виконання і поговоримо про деякі "дії". Під діями ми будемо розуміти послідовне виконання ряду операцій , спрямованих на досягнення певної мети. Дії можуть мати місце в програмному та технічному забезпеченні , у звичайній діяльності людей і тварин. Ми будемо розбивати дії на деякі неподільні , або атомарні , операції.

Наприклад , дію « приготування бутерброда » можна розбити на наступні атомарні операції:

1 ) Відрізати скиби хліба.

2 ) Відрізати скибочку ковбаси.

3 ) Намазати скибочку хліба маслом.

4 ) Покласти скибочку ковбаси на підготовлену скибочку хліба. Неподільні операції можуть мати внутрішні невидимі дії

(взяти батон хліба в ліву руку , взяти ніж в праву руку , провести відрізання ) . Ми ж називаємо їх неподільними тому, що вважаємо виконуваними за раз , без переривання діяльності .

Нехай є дві дії

Р: а Ь с
Q: d e f

де а, Ь, с, d, е, f - атомарні операції. При послідовному виконанні дій ми отримуємо таку послідовність атомарних операцій:

РQ: а Ь c d e f

Що станеться при виконанні цих дій псевдопараллельно, в режимі поділу часу? Дії можуть розслоїтися на неподільні операції з різним чергуванням, тобто може статися те, що в англійській мові прийнято називати словом iterleaving. Можливі варіанти чергування:

а b з d e f
а b d c e f
a b d e c f
а b а е f c
а b d з e f
..........
d e f a b c

Атомарні операції можуть чергуватися всілякими різними способами із збереженням порядку розташування всередині дій. Так як псевдопаралельне виконання двох дій призводить до чергуванню їх неподільних операцій, результат псевдопараллельного виконання може відрізнятися від результату послідовного виконання. Розглянемо приклад. Нехай у нас є дві дії Р і Q,кожна складаються з двох атомарних операцій:

Р : х = 2       Q : х = 3
у = х -1         у = х +1

Що ми отримаємо в результаті їх псевдопаралельного виконання, якщо змінні х і у є для дій загальними? Очевидно , що можливі чотири різних набору значень для пари (х,у): (3,4), (2,1), (2,3) і (3,2). Ми будемо говорити, що набір дій (наприклад, програм) детермінований , якщо всякий раз при псевдопаралельному виконанні для одного і того ж набору вхідних даних він дає однакові вихідні дані. В іншому випадку він недетермінірованний. Вище наведено приклад недетермінірованного набору програм. Зрозуміло, що детермінований набір активностей можна безбоязно виконувати в режимі поділу часу. Для недетермінірованного набору таке виконання небажано.

Чи можна до отримання результатів визначити, чи є набір активностей детермінованим чи ні? Для цього існують достатні умови Бернстайна. Викладемо їх стосовно до програм з розділяються змінними.

Введемо набори вхідних і вихідних змінних програми . Для кожної атомарної операції набори вхідних і вихідних змінних - це набори змінних , які атомарна операція зчитує і записує. Набір вхідних змінних програми R(P) (R від слова read ) суть об'єднання наборів вхідних змінних для всіх її неподільних дій . Аналогічно , набір вихідних змінних програми W(P) ( W від слова write ) суть об'єднання наборів вихідних змінних для всіх її неподільних дій . Наприклад , для програми

P: x = u + v
   y = x * w

отримуємо R ( P ) = { u , v , x , w } , W (P) = { x , y } . Зауважимо , що змінна x присутня як в R (P) , так і в W ( P).

Тепер сформулюємо умови Бернстайна.

Якщо для двох даних дій P і Q :

   перетин W (P) і W (Q) пусто ,
   перетин W (P) з R ( Q) пусто ,
   перетин R ( P ) і W (Q) пусто ,

тоді виконання P і Q детерміноване.

Якщо ці умови не дотримані , можливо , паралельне виконання P і Q детерміноване , а може бути , і ні.

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

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

Про недетермінірованний набір програм (і дій взагалі ) говорять , що він має race condition (стан гонки , стан змагання). У наведеному вище прикладі процеси змагаються за обчислення значень змінних x і y .

Задачу упорядкованого доступу до даних, що розділяються (усунення race condition ) у тому випадку , коли нам не важлива його черговість , можна вирішити , якщо забезпечити кожному процесу ексклюзивне право доступу до цих даних. Кожен процес , який звертається до ресурсів , виключає для всіх інших процесів можливість одночасного спілкування з цими ресурсами , якщо це може призвести до недетермінірованного поведінки набору процесів . Такий прийом називається взаимоисключения ( mutual exclusion ) . Якщо черговість доступу до ресурсів, що важлива для отримання правильних результатів , то одними взаимоисключения вже не обійтися , потрібна взаімосінхронізація поведінки програм .

Критична секція

Важливим поняттям при вивченні способів синхронізації процесів є поняття критичної секції ( critical section ) програми. Критична секція - це частина програми , виконання якої може призвести до виникнення race condition для певного набору програм. Щоб виключити ефект гонок по відношенню до деякого ресурсу , необхідно організувати роботу так , щоб в кожний момент часу тільки один процес міг перебувати у своїй критичній секції , пов'язаної з цим ресурсом. Іншими словами , необхідно забезпечити реалізацію взаимоисключения для критичних секцій програм. Реалізація взаимоисключения для критичних секцій програм з практичної точки зору означає , що по відношенню до інших процесів , які беруть участь у взаємодії , критична секція починає виконуватися як атомарна операція. Давайте розглянемо наступний приклад , в якому псевдопаралельние взаємодіючі процеси представлені діями різних студентів ( таблиця 1) :

Тут критична ділянка для кожного процесу - час від операції " Бачить, що хліба немає " до операції "Повертається в кімнату" включно. У результаті відсутності взаємовиключення ми з ситуації " Немає хліба " потрапляємо в ситуацію " Занадто багато хліба". Аби ця критична ділянка виконуваляся як атомарна операція - " Дістає два батони хліба" , то проблема появи надлишків була б знята.

Зробити процес добування хліба атомарною операцією можна було б таким чином:

• перший стедент має залишити записку, тоді інші студенти чекатимуть його вдома і не підуть по хліб;
• У випадеку якщо в кімнаті 1 ключ, отримаємо таку послідовність операцій: хліба нема-> закрити кімнату-> йти по хліб;

(закрити двері зсередини на засув і йти добувати хліб через вікно, а придбавши хліб, повернутися в кімнату через вікно і відсунути засув. Тоді поки один студент1 здобуває хліб, всі інші знаходяться в стані очікування під дверима)

• створення графіку придбання хліба.

У загальному випадку структура процесу, що бере участь у взаємодії, може бути представлена ​​наступним чином:

while (some condition) {
   entry section
      critical section
   exit section
      remainder section
}

Тут під remainder section розуміються всі атомарні операції, що не входять в критичну секцію.

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

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

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

Забезпечення взаимовиключения є однією з ключових проблем паралельного програмування.

Механізми взаимовиключения повинні забезпечувати :

• Цілісність структур поділюваних даних;

• Відсутністю взаємних блокувань завдань ;

• Відсутність тупиків.

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