НОУ ІНТУІТ, Лекція, Синхронізація паралельних процесів

Завдання синхронізації

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

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

Вимоги до вирішення цього завдання:

затримка будь-якого процесу поза його критичного інтервалу має впливати на розвиток інших процесів;
рішення має бути симетричним щодо процесів;
рішення не повинно допускати глухих кутів.

Рішення за допомогою механізму семафорів:

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

Виділимо комірку пам'яті C , в яку записуватимемо 0, якщо жоден з процесів не вимагає доступу до критичного ресурсу, і номер i того процесу (або виконуючого процесора), який вступив у свій критичний інтервал . Тоді умовою входження i-го процесу в критичний інтервал є результат виконання наступного оператора:

Справді, якщо (C) = 0, процес може увійти в критичний інтервал . Однак можливо, що через невеликий час інший процес (на іншому процесорі) теж зробив таку ж перевірку і слідом за першим зробив засилку C свого номера. Тому потрібна повторна перевірка того, що C знаходиться саме номер даного процесу. При позитивному результаті повторного аналізу процес може вступити докритичний інтервал, тобто. зайняти критичний ресурс. Після виконання критичного інтервалу C посилається 0.

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

2. Завдання "постачальники - споживачі". Є обмежений буфер кілька порцій інформації. Він є критичним ресурсом для двох типів:

процеси "постачальники", отримуючи доступ до ресурсу, поміщають на вільне місце у буфері кілька або одну порцію інформації;
процеси " споживачі " , одержуючи доступом до ресурсу, зчитують із нього порції інформації.

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

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

Можлива схема розв'язання задачі за допомогою семафорів:

Імітація кільцевого (нескінченного) буфера показано на рис. 11.5.

Тоді уточнимо цю процедуру з урахуванням використовуваних індикаторів зчитування та заповнення.

3. Завдання "читачі - письменники".

Є розділений ресурс - область пам'яті, до якої потрібний доступ до процесів двох типів:

Процеси першого типу - "ЧИТАЧІ" - можуть отримувати доступ до ресурсу, що розділяється одночасно. Вони зчитують інформацію.

Процеси другого типу - "ПИСЬМЕННИКИ" - взаємно виключають і один одного, і "читачів". Вони записують у розділювану область пам'яті дані.

Завдання відоме у двох варіантах:

"Читачі", які виявили бажання отримати доступ до ресурсу,повинні отримати його якнайшвидше; це - перше завдання НП.
2. "Читачі", які виявили бажання отримати доступ до ресурсу, повинні отримати його якнайшвидше, якщо відсутні запити від "письменників". "Письменник", що вимагає доступу до ресурсу, повинен отримати його якнайшвидше, але після обслуговування "читачів", що підійшли до ресурсу до першого "письменника". Це — друге завдання НП.

Наведемо можливе розв'язання задач за допомогою комбінованого семафору.

Вважаємо, що процедура ВІДКРИТИ З ЛІКУВАННЯ виконується подібно до процедури ПРОПУСТИТИ, змінюючи тільки значення семафора-лічильника . Процедура ВІДКРИТИ ЗА ЗАПИСУ виконується подібно до процедури ВІДКРИТИ, "відкриваючи" семафор і забезпечуючи запуск "затриманих" процесів з процедур ЗАКРИТИ ЗА ЗАПИСУ або ЧЕКАТИ ЗА ЗАПИСУ, при виконанні яких відбулося переривання.

Тоді критичні інтервали для кожного завдання можуть бути виконані за такими схемами.

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

Представимо наступну модель, яка потребує розв'язання цієї задачі, — модель оперативного обміну між процесорами векторної ПС або рядків (стовпців) матричної ПС (рис. 11.6).

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

Нехай з i-м процесором для передачі вліво пов'язаний "лівий" семафор Ci, для передачі вправо - "правий" семафор Ci+1 (або навпаки). Нехай кожен процесор, який потребує передачі двом сусідам, намагається спочатку закрити свій "правий" (аналогічно, "лівий") семафор. Потім, якщо це не встиг зробити лівий сусід, він спробує закрити "лівий" семафор і зробити передачу. Тоді можливий загальний глухий кут, якщо всі процесори одночасно закриють всі семафори. (При одночасному перерахуванні значень функції у вузлах сітки ймовірність такої ситуації висока.)

Дозволимо парним процесорам спочатку закривати "ліві" ("праві") семафори, а непарним - "праві" ("ліві"). Тоді схеми програм для них виглядатимуть так:

Нехай процесор з непарним номером i потребує обміну — вліво та вправо. Він намагається виконати процедуру ЗАКРИТИ (Ci+1) . Припустимо, що цей семафор (для нього - "правий") закритий i + 1-м процесором. Але для цього процесора з парним номером цей семафор також перший в порядку закриття ("лівий"). Отже, він або чекає на можливість закриття свого "правого" семафору, або веде обмін. Якщо він чекає свого "правого" семафору, він його дочекається, т.к. він - другий для процесора i +2, що веде обмін. Значить, цей процесор закінчить обмін та відкриє свій "лівий" семафор. Тоді процесор i+1 здійснить обмін та відкриє семафор Ci+1. Тоді і процесор i нарешті зможе виконати необхідну процедуру. Після цього він спробує виконати процедуру ЗАКРИТИ (Ci). Цей семафор є " правим " , тобто. другим для процесора з парним номером i-1. Отже, цей процесор закрив обидва пов'язані з ним семафори і веде обмін. Після закінчення обміну він відкриє семафори, і процесор і дочекаєтьсянеобхідного "лівого" семафора та зможе його закрити для себе. Таким чином, тупикова ситуація не може виникнути.

Зазвичай n – ступінь двійки. Якщо ж n непарно, то на кордоні взаємодіють два "непарні" процеси обміну. Тут можливе блокування, коли процесор 1 закриє C2, а процесор n - семафор C1 (1 = (n + 1) mod n). Однак процесор n обов'язково дочекається відкриття семафору Cn і виконає обмін. Отже процесор 1 дочекається відкриття семафора C1, виконає обмін і відкриє C2. Так що глухий кут і в цьому випадку виключені.

Розгляд цієї задачі синхронізації виводить нас за рамки традиційного застосування мультипроцесорної системи типу MIMD, до яких належать, наприклад, НД сімейства "Ельбрус". Однак універсальність такої архітектури допускає принципову можливість відтворення на ній "жорсткіших" архітектур - матричних і векторних, тобто. типу SIMD. Реалізація методу "сіток" на матричних ВС або на структурах типу "гіперкуб" вимагає подібної передачі не тільки двом сусіднім процесорам по рядку, а й сусіднім по стовпцю, діагоналі і т.д. Отже, можливе узагальнення цієї задачі та алгоритму синхронізації. Зазначений вище прийом поділу процесорів на парні та непарні може бути застосований за всіма напрямками обміну - рядками, стовпцями, діагоналі і т.д.

5. Завдання оновлення даних. Заборона використання оновлюваних даних. Наприклад, процесор оновлює запис у базі даних. У найпростішому випадку може бути використана ознака, за якою забороняється звернення до цього запису, доки вона не буде оновлена. (Звичайно, ми не розглядаємо того примітивного рішення, коли БД перетворюється на ресурс із послідовним доступом. Ми прагнемо багатоканального, паралельного доступу.)

Замість ознакиможе бути використаний семафор. Очікування може бути організоване процедурами ЧЕКАТИ або ЖУЖ.