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

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

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

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

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

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

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

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

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

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

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

Р: а Ь с

Q: d e f

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

РQ: а Ь c d e f

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

а Ь з d e f

а Ь d c e f

a Ь d e c f

а Ь а е 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 (Р) (R від слова rеаd ) суть об'єднання наборів вхідних змінних для всіх її неподільних дій . Аналогічно , набір вихідних змінних програми W (P) ( W від слова write ) суть об'єднання наборів вихідних змінних для всіх її неподільних дій . Наприклад , для програми

P: x = u + v

y = x * w

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