Рішення за допомогою семафорів завдання

Розглянемо реалізацію за допомогою семафорів завдання обмежений буфер: є процес-виробник і процес-споживач, взаємодіючі за допомогою циклічного буфера обмеженої довжини; виробник генерує елементи інформації й записує в буфер; споживач використовує інформаційні елементи з буфера й видаляє їх.

Семафор mutex використається "симетрично"; над ним виконується пара операцій: wait... signal - семафорні дужки. Його роль - чисто взаємне виключення критичних секцій. Семафор empty сигналізує про вичерпання буфера. На початку він закритий, тому що елементів у буфері немає. Тому при закритому семафорі empty споживач змушений чекати. Відкриває семафор empty виробник, після того, як він записує в буфер черговий елемент. Семафор full сигналізує про переповнення буфера. На початку він дорівнює n - максимальному числу елементів у буфері. Виробник перед записом елемента в буфер виконує операцію wait (full),гарантуючи, що, якщо буфер переповнений, запису нового елемента в буфер не буде. Відкриває семафор full споживач, після того, як він звільнив черговий елемент буфера.

Рішення за допомогою семафорів завдання "читачі - письменники"

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

Рішення за допомогою семафорів завдання " філософи, що обідають,"

Суть завдання філософи, що обідають, у наступному. Є круглий стіл, за яким сидять п'ять філософів (втім, їхнє число принципового значення не має – для іншого числа філософів рішення буде аналогічним). Перед кожним з них лежить тарілка з їжею, ліворуч і праворуч від кожного – дві китайські палички. Філософ може перебувати в трьох станах: голоду, думати й обідати. На голодний шлунок філософ думати не може. Але почати обідати він може, тільки якщо обидві палички ліворуч і праворуч від нього вільні. Потрібно синхронізувати дії філософів. У цьому випадку загальним ресурсом є палички. Ілюстрацією умов завдання є рис. 12.1.

 

Рис. 12.1. Завдання " філософи, щообідають,".

Критичні області

Критичні області (critical regions) – більше високоринева й надійна конструкція для синхронізації, чим семафори. Загальний ресурс описується у вигляді особливого опису змінної:

v: shared T

Доступ до змінного v можливий тільки за допомогою спеціальної конструкції:

region v when B do S

де v - загальний ресурс; B - булева умова, S - оператор (утримуючий дії над v).

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

Рішення за допомогою критичних областей завдання "обмежений буфер"

Опишемо буфер як структуру:

struct buffer {

 

int pool [n];

 

int count, in, out

 

}

 

buf: shared buffer;

Алгоритм процесу-виробника:

region buf when (count < n) {

 

pool [in] = nextp;

 

in = (in+1) % n;

 

count++;

 

}

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

Алгоритм процесу-споживача:

region buf when (count > 0) {

 

nextc = pool [out];

 

out = (out+1) % n;

 

count-і;

 

}

Не можна не відзначити, наскільки простіше й надійніше виявляється рішення завдання з використанням даної конструкції, у порівнянні з використанням семафорів.

Схема реалізації критичних областей за допомогою семафорів

Будемо використати для реалізації конструкції region x when B do S наступні семафори й цілі змінні:

semaphore mutex, first-delay, second-delay;

 

int first-count, second-count;

Семафор mutex використається для взаємно виключення доступу до критичної секції S. Семафор first-delay використається для очікування процесів, які не можуть увійти в критичну секцію S, тому що умова B хибна. Число таких процесів зберігається в змінної first-count. Семафор second-delay використається для очікування тих процесів, які обчислили умову B один раз й очікують, коли їм буде дозволено повторно обчислити B (second-count - лічильник таких процесів).

Монітори

Конструкція монітор запропонований в 1974 р. Ч. Хоаром. Вона є більше високорівневою і більше надійною конструкцією для синхронізації, чим семафори.

Монітор є багатовходовим модулем особливого роду. Він містить описи загальних для декількох паралельних процесів даних й операцій над цими даними у вигляді процедур P1, …, Pn... Користувачі монітора - паралельні процеси - мають доступ до описаного в ньому загальним даним тільки через його операції, причому в кожен момент часу не більш ніж один процес може виконувати яку-небудь операцію монітора; інші процеси, що бажають виконати операцію монітора, повинні чекати, поки перший процес закінчить виконувати моніторну операцію.

По суті справи, концепція монітора з'явилася розвитком запропонованої також Ч. Хоаром концепції абстрактного типу даних (АТД) – визначення типу даних як сукупності опису його конкретного подання й абстрактних операцій над ним (у вигляді процедур). Концепція монітора додає до АТД можливість синхронізації процесів за загальним даними.

Для реалізації очікування усередині монітора по різних умовах, уводяться умовні змінні (condition variables) – змінні з описами виду condition x,y, доступ до яких можливий тільки операціями wait й signal: наприклад, x.wait(); x.signal(). Операція x.wait() означає, що процес, її виконав, затримується до того моменту, поки інший процес не виконає операцію x.signal(). Операція x.signal() відновляє рівно один припинений процес. Якщо припинених процесів нема, вона не виконує ніяких дій.

Схематичне зображення монітора наведене на рис. 12.2.

 

Рис. 12.2. Схематичне зображення монітора.

Схема монітора з умовними змінними наведена на рис. 12.3.

 

Рис. 12.3. Монітор з умовними змінними.

Рішення завдання " філософи, що обідають," за допомогою моніторів

Реалізуємо рішення завдання " філософи, що обідають,") за допомогою монітора. Для кожного філософа визначимо стану (голодний, обідає, думає), і для їхнього зберігання будемо використати масив state. Для керування переходом філософа зі стану в стан використаємо масив умовних змінних self. Для кожного філософа визначимо операції pickup - взяти паличку; putdown - звільнити паличку; test - перевірити стан філософа й, якщо це можливо і якщо він голодний, перевести його в стан eating.

Синхронізація в ОС Solaris

Система Solaris надає різноманітні види блокіровщиків для підтримки багатозадачності, багатопоточності (включаючи потоки реального часу) і мультипроцессирования. Використовуються адаптивні мюьтексы (adaptive mutexes) – ефективний засіб синхронізації доступу до даних при їхній обробці короткими сегментами коду. Для більше довгих сегментів коду використаються умовні змінні й блокіровщики читачів-письменників (reader-writer locks; rwlocks).

Для синхронізації потоків використовуються "вертушки" (turnstiles) – синхронізуючі примітиви, які дозволяють використати або adaptive mutex, або rwlock.