• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

5. Команда “перевірка” та “встановлення”.

6. Використання семафорів для синхронізації та впорядкування паралельних процесів.

7. Монітороподібні засоби синхронізації паралельних процесів.

8. Поштові ящики.

9. Конвеєри.

10. Черги повідомлень.

1. Незалежні та взаємодіючі обчислювальні процеси.

Основною особливістю сучасних операційних систем як складової частини СПЗ є виконання декількох задач одночасно (паралельно в часі). При цьому під паралельними задачами (процесами) розуміють не тільки процеси які виконуються паралельно на різних процесорах чи пристроях вводу/виводу, але й ті послідовні процеси, які розділяють один центральний процесор і хоча б частково перекриваються в часі.

Паралельні процеси – це такі послідовні процеси, які знаходяться в активному стані одночасно. Такі процеси можуть бути незалежні та взаємодіючі.

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

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

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

Конкуруючі – це процеси, які сумісно виконують спільну роботу і мають доступ до спільних змінних.

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

2. Види задач синхронізації паралельних процесів.

Задача “взаємного виключення”.

Дозволяє попередити некоректне виконання конкуруючих процесів через нерегламентований доступ до сумісно – використовуваних змінних. Ті частини коду програми, які здійснюють звертання до критичних ресурсів називаються критичною секцією програми.

Рішення задачі взаємного виключення полягає в організації такого доступу до критичного ресурсу, коли тільки одному процесу дозволено “зайти” в критичну секцію (почати виконання своєї критичної секції).

Для кожного критичного ресурсу можуть існувати окремі критичні секції процесу. До критичних секцій процесу існують наступні вимоги:

· в кожен момент часу тільки один процес може знаходитись в певній критичній секції;

· ні один процес не може знаходитись в критичній секції в необмежений відрізок часу;

· жоден процес не повинен чекати входження в критичну секцію в нескінченний проміжок часу;

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

Задача “виробник – споживач”.

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

Процеси взаємодіють між собою через деяку спільну область пам’яті, яка є критичним ресурсом. Синхронізація роботи таких процесів повинна задовольняти такі вимоги:

· задача взаємного виключення повинна бути забезпечена по відношенню до спільної області пам’яті;

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

Спроба процесу виробника записати повідомлення в спільну область пам’яті, з якої не було прочитане повідомлення процесом споживачем, повинна бути блокована. Аналогічно повинна бути блокована спроба споживача зчитати повідомлення з області пам’яті у випадку, коли процес виробник не помістить такого повідомлення в спільну область пам’яті.

Задача “читачів – письменників”.

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

Виділяють два паралельних процеси:

1) процеси “читачі” – вони зчитують одночасно інформацію зі спільного файлу, якщо це допускається при роботі з таким файлом;

2) процеси “письменники” – вони записують інформацію в цей спільний файл, при умові забезпечення задачі взаємного виключення як з процесами “читачами”, так з процесами “письменниками”. Це забезпечується двома шляхами:

· встановлюється пріоритетність при виконанні поточного ресурсу читачем. В цьому випаду хоча б один процес читач користується ресурсом, то цей ресурс недоступний процесам письменникам;

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

Задача “синхронізації виконання гілок алгоритмів”.

Використовується тоді, коли декілька процесів реалізовують один і той самий алгоритм паралельно. Ця задача зводиться до визначення точок (операторів) алгоритмів, яких необхідно отримати результатом виконання кожного процесу. Для цього використовують спеціальну змінну або набір змінних типу “подія”. Подія – це зафіксований результат будь якої операції (запис файлу, закінчення процесу).

3. Синхронізація за допомогою блокування пам’яті.

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

Для забезпечення задачі взаємного виключення використовують дві змінні key 1 і key 2.

Приклад на мові Pascal

var key1, key2: boolean;

begin

key1:=false, key2:=false;

par begin

PR1: white true do

begin key1:=true

while key2 do begin … end {критична секція PR1}

key1:=false

end

and

PR2: white true do

begin key2:=true

while key1 do begin … end {критична секція PR2}

key2:=false

end

par end

При виконанні цього алгоритму можлива ситуація коли два процеси встановлять одночасно свої змінні key 1 і key 2 в true і ввійдуть у безкінечний цикл. Тому для вирішення цієї проблеми був запропонований алгоритм Деккера.

Читайте також:

1. Rete-алгоритм
2. Алгоритм
3. Алгоритм
4. Алгоритм 1.
5. Алгоритм RLE
6. Алгоритм безпосередньої заміни
7. Алгоритм Берлекемпа-Мессі
8. Алгоритм відшукання оптимального плану.
9. Алгоритм Дейкстри.
10. Алгоритм Деккера.
11. Алгоритм діагностики при травмах живота.

Переглядів: 1579