Синхронізація за допомогою елементарних прийомів нижнього рівня.

1. Блокування пам'яті.

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

Повернемося до розгляду приклада із двома паралельними процесами.

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

Здавалося б, нічого простіше ні, як запропонувати наступне рішення:

Boolean : Перемикач_1, Перемикач_2;

Begin

 Перемикач_1:=False;

 Перемикач_2:=False;

 parbegin

Процес_1: do while (True);

Цикл_1: do while (Перемикач_2);

            end;

           Перемикач_1:=True;

           /* Критична ділянка 1 */

           Перемикач_1:=False;

           /* частина, Що Залишилася, процесу 1*/

        end;

Процес_2: do while (True);

Цикл_2: do while (Перемикач_1);

            end;

           Перемикач_2:=True;

           /* Критична ділянка 2 */

           Перемикач_2:=False;

           /* частина, Що Залишилася, процесу 2*/

        end;

 parend;

End.

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

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

Ми ж приведемо варіант рішення, запропонованого Деккером.

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

integer: C1,C2,Черга;

Begin

 C1:=0;

 C2:=0;

 Черга:=1;

 parbegin

Процес_1: begin C1:=1;

              do while (C2=1);

               if Черга=2 then

                  begin

                   C1:=0;

                    do while (Черга=2);

                    end;

                      C1:=1;

                  end;

              end;

              Критична ділянка Процесу 1;

              C1:=0;

              Черга:=2;

              частина, Що Залишилася, Процесу 1;

        end;

  Процес_2: begin C2:=1;

              do while (C1=1);

               if Черга=1 then

                  begin

                   C2:=0;

                    do while (Черга=1);

                    end;

                   C2:=1;

                  end;

              end;

              Критична ділянка Процесу 2;

              C2:=0;

              Черга:=1;

              частина, Що Залишилася, Процесу 2;

        end;

 parend;

end.

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

1. Перевірка й установка.

Ця машинна операція значно спрощує рішення проблеми критичної ділянки.

До операції “перевірка й установка” звертаються із двома параметрами: “локальний” й “загальний”. Операція бере значення параметра “загальний” і присвоює його змінній “локальний”, а потім установлює змінній “загальний” значення рівне одиниці.

Головна властивість цієї операції - її неподільність. Коли процес виконує операцію “перевірка й установка” ніяких дій не може відбутися між її початком і кінцем.

Змінна “загальний” розділяється між процесами, які підлягають синхронізації стосовно деякого критичного ресурсу. У кожного процесу є своя власна змінна “локальний”.

Якщо “загальний” = 1, це значить, що якийсь процес перебуває у своїй критичній ділянці. Початкове значення змінної “загальний” = 0.

Приведемо рішення проблеми методом “перевірка й установка”. У цьому решенні припускається, що в машині передбачене блокування пам'яті, тобто операція “загальний” := 0 неподільна.

Алгоритм перевірки й установки:

integer: ЗАГАЛЬНИЙ;

Begin

 ЗАГАЛЬНИЙ:=0;

 parbegin

integer: ЛОКАЛЬНИЙ1;

Процес_1: begin do while (True);

                    ЛОКАЛЬНИЙ1:=1;

                     do while (ЛОКАЛЬНИЙ1=1)

                  Перевірка й установка(ЛОКАЛЬНИЙ1,ЗАГАЛЬНИЙ)

                     end;

                    Критична ділянка 1;

                    ЗАГАЛЬНИЙ:=0;

                    частина, Що Залишилася, Процесу 1;

                   end;

         end;

integer: ЛОКАЛЬНИЙ2;

Процес_2: begin do while (True);

                    ЛОКАЛЬНИЙ2:=1;

                     do while (ЛОКАЛЬНИЙ2=1)

                  Перевірка й установка(ЛОКАЛЬНИЙ2,ЗАГАЛЬНИЙ)

                     end;

                    Критична ділянка 2;

                    ЗАГАЛЬНИЙ:=0;

                    частина, Що Залишилася, Процесу 2;

                   end;

         end;

 parend;

end.

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

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

Одним із прийомів, що дозволяють уникнути активного запобігання є “семафор”.

Семафор – ціла змінна, значення якої можуть міняти тільки операції P й V. Нехай S – семафор. Коли процес виконує операцію P(S), S зменшується на одиницю й

1. Якщо S³0, то процес продовжує роботу.
2. Якщо S<0, то процес зупиняється й стає в чергу очікування, пов'язану з S. Він залишається заблокованим доти, поки операція V(S), виконана іншим процесом, не звільнить його.

Коли процес виконує V(S), S збільшується на одиницю й

1. Якщо S>0, процес продовжує роботу.
2. Якщо S£0, то один процес вилучається із черги очікування й одержує дозвіл продовжити роботу. Процес, що звернувся до операції V(S), теж може продовжувати роботу.

Крім того, операції P й V – неподільні. У кожен момент часу тільки один процес може виконувати операцію P або V над даним семафором. Тому якщо, S=1 і два процеси одночасно спробують виконати операцію P(S), те тільки одному з них буде дозволено продовжити роботу. Інший процес буде заблокований і поставлений у чергу до семафора S.

Раніше ми говорили про те, що стрижень системи – це механізм, що реалізує процеси. Стрижень повинен виділяти процесам і відбирати в них процесори. Операції P й V можна реалізувати усередині стрижня. Таким чином, забезпечується неподільність цієї операції.

Семафор, максимальне значення якого дорівнює одиниці, називається двійковим семафором.

За допомогою двійкового семафора процеси можуть організувати взаємне виключення за допомогою операцій P(S) і V(S).

Приклад:

integer: ВІЛЬНИЙ;

Begin

 ВІЛЬНИЙ:=1;

 parbegin

Процес_1: begin do while (True);

                    Початок Процесу 1;

                    P(ВІЛЬНИЙ);

                    Критична ділянка 1;

                    V(ВІЛЬНИЙ);

                    частина, Що Залишилася, Процесу 1;

                   end;

         end;

Процес_2: begin do while (True);

                    Початок Процесу 2;

                    P(ВІЛЬНИЙ);

                    Критична ділянка 2;

                    V(ВІЛЬНИЙ);

                    частина, Що Залишилася, Процесу 2;

                   end;

         end;

 parend;

end.

Тут S приймає значення 1, 0, -1. Якщо S=1, це значить, що жоден процес не перебуває у своїй критичній ділянці. Якщо S=0 -один процес перебуває у своїй критичній ділянці. Якщо S=-1 – один процес перебуває у своїй критичній ділянці, а другий – у черзі очікування.

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

За допомогою загальних семафорів легко вирішується проблема “Постачальник-Споживач”.

Змінна “наявність” - семафор, значення якого дорівнює числу вільних буферів у пулі.

Змінна “заполн” - семафор, значення якого дорівнює числу заповнених буферів, які були відіслані споживачеві.

Семафор “взаиск” (взаємне виключення) - двійковий. Він гарантує, що в кожен момент тільки один процес зможе працювати з буферними стрілками.

integer: НАЯВНІСТЬ,ЗАПОЛН,ВЗАИСК;

Begin

 НАЯВНІСТЬ:= кількість вільних буферів;

 ЗАПОЛН := 0;

 ВЗАИСК := 1;

 parbegin

ПОСТАЧАЛЬНИК: begin do while (True);

                 Приготувати повідомлення;

                 P(НАЯВНІСТЬ);

                 P(ВЗАИСК);

                 Послати повідомлення;

                 V(ЗАПОЛН);

                 V(ВЗАИСК);

                end;

         end;

СПОЖИВАЧ: begin do while (True);

                 P(ЗАПОЛН);

                 P(ВЗАИСК);

                 Одержати повідомлення;

                 V(НАЯВНІСТЬ);

                 V(ВЗАИСК);

                 Обробити повідомлення;

                end;

         end;

 parend;

end.

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

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

Якщо значення семафора S стає негативним, це значить, що черги, пов'язаної з S, очікує один або кілька процесів.

Коли виконується чергова операція V(S), стрижень повинен вибрати, який процес треба взяти із черги. Стрижень системи може обслуговувати чергу в порядку надходження або використати пріоритетну схему обслуговування. Порядок обслуговування черги повинен обумовлюватися цілями, для яких застосовується даний семафор. Питання визначення дисципліни обслуговування при проектуванні ОС тісно пов'язаний з моделюванням обчислювальних процесів, для чого можуть бути ефективно використані моделі масового обслуговування.

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

Вважається, що семафори - досить ефективний засіб для задоволення потреб ОС при реалізації синхронізації й спілкування між процесами.

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