Базові механізми синхронізації потоків
Механізмами синхронізації є засоби операційної системи, які допомагають розв’язувати основне завдання синхронізації – забезпечувати координацію потоків, котрі працюють зі спільно використовуваними даними. Якщо такі засоби – це мінімальні блоки для побудови багапотокових програм, їх називають синхронізаційними примітивами.
Синхронізаційні механізми поділяють на такі основні категорії:
· універсальні, низького рівня, які можна використовувати різними способами (семафори);
· прості, низького рівня, кожен з яких пристосований до розв’язання тільки однієї задачі (м’ютекси та умовні змінні);
· універсальні високого рівня, виражені через прості; до цієї групи належить концепція монітора, яка може бути виражена через м’ютекси та умовні змінні;
· високого рівня, пристосовані до розв’язання конкретної синхронізаційної задачі (блокування читання-записування і бар’єри).
Розглянемо різні механізми і дамо оцінку перевагам, які має кожен з них, а також можливі їхні недоліки.
Для подальшої ілюстрації матеріалу візьмемо класичний приклад, який демонструє необхідність синхронізації – задачу виробників-споживачів (producer-consumer problem) або задачу обмеженого буфера (bounded buffer).
Формулювання задачі просте. Припустимо, що в нас є потоки-виробники і потоки-споживачі. Виробник створює об’єкти, споживач їх отримує. Завданням є так синхронізувати їхню роботу, щоб споживач не міг намагатися отримувати ще не створені об’єкти, а виробник не міг зробити більше об’єктів, ніж зможе отримати споживач.
|
|
|
Для синхронізації потоків помістимо між виробником і споживачем буфер фіксованої довжини n. Виробник може поміщати об’єкти у буфер ,споживач – забирати їх звідти. Якщо споживач забирає об’єкт, його вилучають із буфера. Необхідно забезпечити кілька вимог.
- Коли виробник або споживач працює із буфером, решта потоків повинна чекати, поки він завершить свою роботу.
- Коли виробник намагається помістити об’єкт у буфер, а буфер повний (у ньому n об’єктів), він має дочекатися, поки в ньому з’явиться місце.
- Коли споживач намагається забрати об’єкт із буфера, а буфер порожній, він має дочекатися, поки в ньому з’явиться об’єкт.
Семафори
Концепцію семафорів запропонував у 1965 році Е. Дейкстра – відомий голландський фахівець у галузі комп’ютерних наук. Семафори є найстарішими синхронізаційними примітивами з числа тих, які застосовуються на практиці.
Семафор – це спільно використовуваний невід’ємний цілочисловий лічильник, для якого задано початкове значення і визначено такі атомарні операції.
· Зменшення семафора (down): якщо значення семафора більше від нуля, його зменшують на одиницю, якщо ж значення дорівнює нулю, цей потік переходить у стан очікування доти, поки воно не стане більше від нуля (кажуть, що потік «очікує на семафорі» або «заблокований на семафорі»). Цю операцію називають також очікуванням – wait. Ось її псевдокод:
|
|
|
void down (semaphore_t sem) {
if (sem>0) sem--;
else sleep();
}
· Збільшення семафора (up): значення семафора збільшують на одиницю; коли при цьому є потоки, які очікують на семафорі, один із них виходить із очікування і виконує свою операцію down. Якщо на семафорі очікують кілька потоків, то внаслідок виконання операції up його значення залишається нульовим, але один із потоків продовжує виконання (у більшості реалізацій вибір цього потоку буде випадковим). Цю операцію також називають сигналізацією – post. Ось її псевдокод:
void up (semaphore_t sem) {
sem++;
if (waiting_threads()) wakeup (some_thread));
}
Фактично значення семафора визначає кількість потоків, що може пройти через цей семафор без блокування. Коли для семафора задане нульове початкове значення, то він блокуватиме всі потоки доти, поки якийсь потік його не «відкриє», виконавши операцію up. Операції up і down можуть бути виконані будь-якими потоками, що мають доступ до семафора.
Дейкстра використовував для операції down позначення Р (від голландського probieren – перевіряти), а для операції up – позначення V (від голландського verhoren – збільшувати). Ці позначення часто використовують у літературі.
Дата добавления: 2018-04-05; просмотров: 1107; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!