Критична секція
Важливим поняттям синхронізації процесів є поняття "Критична секція" програми. Критична секція - це частина програми, в якій здійснюється доступ до даних, що розділяються. Щоб виключити ефект гонок по відношенню до деякого ресурсу, необхідно забезпечити, щоб в кожен момент в критичній секції, пов'язаній з цим ресурсом, знаходився максимум один процес. Цей прийом називають взаємним виключенням.
Простий спосіб забезпечити взаємне виключення - дозволити процесу, що знаходиться в критичній секції, забороняти всі переривання. Проте цей спосіб непридатний, оскільки небезпечно довіряти управління системою призначеному для користувача процесу; він може надовго зайняти процесор, а при краху процесу в критичній області крах потерпить вся система, тому що переривання ніколи не будуть дозволені.
Іншим способом є використання блокуючих змінних. З кожним ресурсом, що розділяється, зв'язується двійкова змінна, яка набуває значення 1, якщо ресурс вільний (тобто жоден процес не знаходиться в даний момент в критичній секції, пов'язаній з даним процесом), і значення 0, якщо ресурс зайнятий. На малюнку 2.4 показаний фрагмент алгоритму процесу, що використовує для реалізації взаємного виключення доступу до ресурсу D, що розділяється, блокуючу змінну F(D). Перед входом в критичну секцію процес перевіряє, чи вільний ресурс D. Якщо він зайнятий, то перевірка циклічно повторюється, якщо вільний, то значення змінної F(D) встановлюється в 0, і процес входить в критичну секцію. Після того, як процес виконає всі дії з ресурсом D, що розділяється, значення змінної F(D) знову встановлюється рівним 1.
Якщо всі процеси написані з використанням вищеописаних угод, то взаємне виключення гарантується. Слід відмітити, що операція перевірки і установки блокуючої змінної повинна бути неподільною. Пояснимо це. Хай в результаті перевірки змінної процес визначив, що ресурс вільний, але відразу після цього, не встигнувши встановити змінну в 0, був перерваний. За час його припинення інший процес зайняв ресурс, увійшов до своєї критичної секції, але також був перерваний, не завершивши роботи з ресурсом, що розділяється. Коли управління було повернене першому процесу, він, вважаючи ресурс вільним, встановила ознака зайнятості і почав виконувати свою критичну секцію. Таким чином був порушений принцип взаємного виключення, що потенційно може привести до небажаних наслідків. Щоб уникнути таких ситуацій в системі команд машини бажано мати єдину команду "перевірка-установка", або ж реалізовувати системними засобами відповідні програмні примітиви, які б забороняли переривання впродовж всієї операції перевірки і установки.
Реалізація критичних секцій з використанням блокуючих змінних має істотний недолік: протягом часу, коли один процес знаходиться в критичній секції, інший процес, якому потрібний той же ресурс, виконуватиме рутинні дії з опиту блокуючої змінної, марно витрачаючи процесорний час. Для усунення таких ситуацій може бути використаний так званий апарат подій. За допомогою цього засобу можуть вирішуватися не тільки проблеми взаємного виключення, але і більш загальні завдання синхронізації процесів. У різних операційних системах апарат подій реалізується по своєму, але у будь-якому випадку використовуються системні функції аналогічного призначення, які умовно назвемо WAIT(x) і POST(x), де x - ідентифікатор деякої події. На малюнку 2.5 показаний фрагмент алгоритму процесу, що використовує ці функції. Якщо ресурс зайнятий, то процес не виконує циклічний опит, а викликає системну функцію WAIT(D), тут D позначає подію, що полягає в звільненні ресурсу D. Функція WAIT(D) переводить активний процес в стан ОЧІКУВАННЯ і робить відмітку в його дескрипторі про те, що процес чекає події D. Процес, який в цей час використовує ресурс D, після виходу з критичної секції виконує системну функцію POST(D), внаслідок чого операційна система проглядає чергу чекаючих процесів і переводить процес, чекаючий події D, в стан ГОТОВНІСТЬ.
Узагальнювальний засіб синхронізації процесів запропонував Дейкстра, який ввів два нові примітиви. У абстрактній формі ці примітиви, P, що позначаються, і V, оперують над цілими ненегативними змінними, званими семафорами. Хай S такий семафор. Операції визначаються таким чином:
V(S): змінна S збільшується на 1 однією неподільною дією; вибірка, інкремент і запам'ятовування не можуть бути перервані, і до S немає доступу іншим процесам під час виконання цієї операції.
P(S): зменшення S на 1, якщо це можливо. Якщо S=0, то неможливо зменшити S і залишитися в області цілих ненегативних значень, в цьому випадку процес, що викликає P-операцию, чекає, поки це зменшення стане можливим. Успішна перевірка і зменшення також є неподільною операцією.
У окремому випадку, коли семафор S може набувати тільки значень 0 і 1, він перетворюється на блокуючу змінну. Операція P містить в собі потенційну можливість переходу процесу, який її виконує, в стан очікування, тоді як V-операция може при деяких обставинах активізувати інший процес, припинений операцією P (порівняєте ці операції з системними функціями WAIT і POST).
Розглянемо використання семафорів на класичному прикладі взаємодії двох процесів, що виконуються в режимі мультипрограмування, один з яких пише дані в буферний пул, а інший прочитує їх з буферного пулу. Хай буферний пул складається з N буферів, кожен з яких може містити один запис. Процес "письменник" повинен припинятися, коли все буфера виявляються зайнятими, і активізуватися при звільненні хоч би одного буфера. Навпаки, процес "читач" припиняється, коли всі буфери порожні, і активізується при появі хоч би одного запису.
Розглянемо використання простішої ідеї для вирішення проблеми змагань.
Неважко помітити, як джерелом нашої помилки є те, що зовні найпростіша операція покладання грошей на рахунок насправді розпадається на кілька операцій, при цьому завжди залишається шанс втручання між ними якогось іншого потоку. У цьому випадку кажуть, що операція не є атомарною.
Звідси випливає, що розв’язанням проблеми змагання є перетворення фрагменту коду, який спричиняє проблему, в атомарну операцію, тобто в таку, котра гарантовано виконуватиметься цілковито без втручання інших потоків. Такий фрагмент коду називають критичною секцією (critical section):
//початок критичної секції
total_amount=total_amount+new_amount;
//кінець критичної секції
Тепер, коли два потоки візьмуться виконувати код критичної секції одночасно, той з них, що почав першим, виконає весь її код цілком до того, як другий почне своє виконання (другий потоік чекатиме, поки перший не закінчить виконання коду критичної секції). У результаті підсумку гарантовано матимемо в нашій програмі послідовність подій за варіантом 2, і змагання не відбудеться ніколи.
Розглянемо властивості, які повинна мати критична секція.
Взаємного виключення (mutual exlusion): у конкретний момент часу код критичної секції може виконувати тільки один потік.
Прогесу: якщо кілька потоків запрсили вхід у критичну секцію, один із них повинен обов’язково у неї ввійти (вони не можуть всі заблокувати один одного).
Обмеженості очікування: процес, що намагається ввійти у критичну секцію, рано чи пізно обов’язково в неї ввійде.
Залишається відповісти на далеко не просте запитання: “Як нам змусити ситему сприймати кілька операцій як одну атомарну операцію?”
Найпростішим розв’язанням такої задачі було б заборонити переривання на час виконання критичної секції. Такий підхід, хоча й розв’язує задачу в принципі, на практиці не може бути застосовуваний, оскільки внаслідок зациклення аьо авірії програми у критичній секції вся система може залишитися із заблокованими перериваннями, а отже, у непрацездатному стані.
