Серйозна проблема виникає в ситуації, коли два (або більше) процесу одночасно намагаються працювати з загальними для них даними, причому хоча б один процес змінює значення цих даних.
Проблему часто пояснюють на такому, трохи умовному, прикладі. Нехай є система резервування авіаквитків, в якій одночасно працюють два процеси. Процес A забезпечує продаж квитків, процес B - повернення квитків. Не заглиблюючись у деталі, будемо вважати, що обидва процеси працюють зі змінною N - числом залишилися квитків, причому відповідні фрагменти програм на псевдокоді виглядають приблизно так:
Процес A: Процес B:
| Процесс A: | Процесс B: |
| . . . R1 := N; R1 := R1 - 1; N := R1; . . . | . . . R2 := N; R2 := R2 + 1; N := R2; . . . |
Уявімо собі тепер, що при квазіпараллельний реалізації процесів в ході виконання цих трьох операторів відбувається перемикання процесів. В результаті, в залежності від непередбачуваних випадковостей, порядок виконання операторів може виявитися різним, наприклад:
1) R1: = N; R2: = N; R2: = R2 + 1; N: = R2; R1: = R1 - 1; N: = R1;
2) R2: = N; R2: = R2 + 1; R1: = N; R1: = R1 - 1; N: = R1; N: = R2;
3) R1: = N; R1: = R1 - 1; N: = R1; R2: = N; R2: = R2 + 1; N: = R2;
Ну і що? А те, що у випадку 1 значення N в результаті виявиться зменшеним на 1, у випадку 2 - збільшеним на 1, і тільки в разі 3 значення N, як і належить, не зміниться.
Можна навести менш екзотичні приклади.
· Якщо два процеси одночасно намагаються відредагувати одну і ту ж запис бази даних, то в результаті різні поля одного запису можуть виявитися неузгодженими.
· Якщо один процес додає повідомлення в чергу, а інший в цей час намагається взяти повідомлення з черги для обробки, то він може прочитати не повністю сформоване повідомлення.
· Якщо два процеси одночасно намагаються звернутися до диска, кожен зі своїм запитом, то що саме кожен з них в результаті прочитає або запише на диск - сказати важко.
Ситуація зрозуміла: не можна дозволяти двом процесам одночасно звертатися до одних і тих же даних, якщо при цьому відбувається зміна цих даних.
Те, що ми розглядали квазіпараллельний реалізацію процесів, не настільки істотно. Для процесів, що працюють на різних процесорах, але одночасно звертаються до одних і тих же даних, ситуація приблизно та ж.
Задовго до створення багатозадачних систем розробники засобів автоматики зіткнулися з неприємним ефектом залежності результату операції від випадкового і непередбачуваного співвідношення швидкостей поширення різних сигналів в електронних схемах. Цей ефект вони назвали «гонками». Ми тут ведемо мову, по суті, про те ж.
Для більш чіткого опису ситуації було введено поняття критичної секції.
Критичної секцією процесу по відношенню до деякого ресурсу називається така ділянка програми процесу, при проходженні якого необхідно, щоб ніякий інший процес не був у своїй критичній секції по відношенню до того ж ресурсу.
У прикладі з квитками наведені три оператори в кожному з процесів складають критичну секцію цього процесу по відношенню до загальної змінної N.
Алгоритм роботи кожного процесу окремо правильний, але правильна робота двох процесів у сукупності може бути гарантована, тільки якщо вони не сунуться одночасно кожен в свою критичну секцію.
А як їм це заборонити?
На перший погляд здається, що ця проблема (її називають проблемою взаємного виключення процесів) вирішується просто. Наприклад, можна ввести булеву змінну Free, доступну обом процесам і має сенс «критична область вільна». Кожен процес перед входом в свою критичну область повинен чекати, поки ця змінна не стане істинною, як показано нижче:
| Процесс A: | Процесс B: |
| . . . while not Free do ; Free := false; (критическая секция A) Free := true; . . . | . . . while not Free do ; Free := false; (критическая секция B) Free := true; . . . |
В обох процесах цикл while не робить нічого, крім очікування, поки інший процес вийде зі своєї критичної секції.
А чи не потрібно було щось зробити зі змінною Free ще до запуску процесів A і B?
Перш за все, відзначимо, що запропоноване рішення використовує таку неприємну річ, як активне очікування: процесорний час витрачається на багаторазову перевірку змінної Free. Але це півбіди.
Біда в тому, що таке рішення нічого не вирішує. Якщо реалізувати його на практиці, то «неприємності» стануть рідше, але не зникнуть. У першому, нехитрому варіанті програми загрозливих ділянок були критичні секції обох процесів. Тепер же уразливий ділянку звузився до однієї точки, зазначеної в програмі кожного процесу штриховою лінією. Це точка між перевіркою змінної Free і зміною цієї змінної. Якщо перемикання процесів станеться, коли витісняється процес буде знаходитися саме в цій точці, то спочатку в критичну секцію увійде (з повним правом на це) інший процес, а потім, коли управління повернеться до першого процесу, він без додаткової перевірки теж увійде в свою критичну секцію.
Розробники перших програмних систем, що використовують взаємодію паралельних процесів, не відразу усвідомили складність проблеми взаємного виключення. Були випробувані різні програмні рішення, перш ніж вдалося знайти таке, яке задовольняло трьом природним умовам:
· У будь-який момент часу не більше, ніж один процес може знаходитися в критичній секції;
· Якщо критична секція вільна, то процес може безперешкодно увійти в неї;
· Всі процеси рівноправні.
Спробуйте самі знайти таке рішення. У книгах / 3 / і / 4 / можна знайти кілька варіантів рішення з аналізом їхніх помилок.
Зрештою правильні алгоритми вирішена завдання взаємного виключення запропонували спочатку Деккер (його алгоритм досить заплутаний, що часто трапляється з першими рішеннями складних завдань), потім Пітерсон, чий алгоритм простіше і зрозуміліше.
Для допитливих приводимо рішення Пітерсона. У ньому використовуються булеві змінні flagA, flagB, спочатку рівні false, і змінна перераховується типу turn: A.. B.
| Процесс A: | Процесс B: |
| . . . flagA := true; turn := B; while flagB and turn = B do ; (критическая секция A) flagA := false; . . . | . . . flagB := true; turn := A; while flagA and turn = A do ; (критическая секция B) flagB := false; . . . |
Наведений алгоритм дійсно вирішує проблему, проте у нього є два істотні недоліки. По-перше, якщо в конкуренції за критичну секцію беруть участь не два процеси, а три або більше, то програма стає дуже громіздкою. По-друге, рішення Пітерсона засноване на використанні активного очікування.
Ще одним напрямком в реалізації взаємного виключення стало включення спеціальних машинних команд в набори команд нових процесорів. Оскільки небезпека, як ми бачили, пов'язана з поділом за часом операцій перевірки і присвоювання, то були запропоновані команди, виконують одночасно перевірку і присвоювання. Такі команди є, наприклад, у процесорів Pentium. З їх допомогою дійсно можна простіше реалізувати взаємне виключення, але для цього все одно потрібно активне очікування.