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

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

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

Interleaving , race сcodition і взаємовиключення

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

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 розуміються всі атомарні операції, що не входять в критичну секцію.