Взаємо-виключення

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

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

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

Для прикладу розглянемо задачу.

Програма друкування файлів. Програма повинна надрукувати всі файли, імена яких послідовно (у порядку надходження) розміщені у загальнодоступному файлі „замовлень”, іншими програмами.

Спеціальна,загальнодоступна, змінна Next містить номер першої вільної, доступної для запису позиції файлу замовлень. Процеси-клієнти читають цю змінну, записують у вказану позицію файлу „замовлень” назву свого файлу та нарощують значення Next на одиницю.

Припустимо, що в деякий момент процес R вирішив роздрукувати свій файл. (Див. Рис. __). Для цього він прочитав значення змінної Next (допустимо, що воно рівне 4). Процес запам’ятав це значення, але розмістити імені файлу не встиг, так як його виконання було перерване (вичерпався квант часу).

Рис. __

Черговий процес S, який хоче роздрукувати свій файл, прочитав те саме значення змінної, розмістив свій файл у вказаній позиції (4) та наростив значення змінної на одиницю.

Коли керування буде передано процесові R, то він продовжить своє виконання з розміщення імені свого файлу в позицію 4 файлу „замовлень”, так як цю позицію він запам’ятав підчас попереднього кванту часу, підмінивши таким чином назву файлу, що записана процесом S.

Таким чином процес S ніколи не побачить свого файлу роздрукованим.

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

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

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

Причому: - кожна машинна команда виконується як операція, що не може бути поділена;

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

2. Не повинно бути ніяких припущень щодо відносних швидкостей виконання асинхронних паралельних процесів.

3. Процеси, що знаходяться поза своїми критичними секціями, не можуть заважати іншим процесам заходити у свої власні критичні ділянки.

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

Програмну реалізації цієї задачі запропонував голландський математик Дейкстра.

Алгоритм Дейкстри.

Процес 1. (П1). Процес 2. (П2).

program Алгоритм Дейкстри

var вибранийпроцес: цілий; { перший, другий }

П1хочезайти, П2хочезайти: логічний;

procedure Процес1

Дата добавления: 2014-01-11