семафор
Одним з перших механізмів, запропонованих для синхронізації поведінки процесів, стали семафори, концепцію яких описав Дейкстра (Dijkstra) в 1965 році. Він запропонував використовувати змінні, які можуть приймати цілі невід'ємні значення. Такі змінні, використовувані для синхронізації обчислювальних процесів, отримали назву семафорів.
Семафор починає діяти з призначеного для нього початкового відліку. Всякий раз, коли потік отримує права володіння ці об'єктом (через функцію очікування), лічильник в семафорі зменшується на одиницю. І всякий раз, коли потік поступається свої права володіння об'єктом володіння цим об'єктом, лічильник в семафорі збільшується на одиницю. Як тільки лічильник в семафорі досягне нуля, семафор блокується в несигнальному стані і жоден з потоків не може отримати до нього доступ. p> Для роботи з семафора вводяться два примітиву, традиційно позначаються Р (від датського слова proberen - перевіряти) і V (від verhogen збільшувати). Нехай змінна S представляє собою семафор. Тоді класичне визначення дії V (S) і P (S) операцій виглядає наступним чином:
P (S):
ЯКЩО S = 0
ТО процес блокується;
ІНАКШЕ S = S - 1;
V (S):
S = S + 1;
Цей запис означає наступне:
- при виконанні операції P над семафором S спочатку перевіряється його значення. Якщо воно більше 0, то з S віднімається 1.
Якщо воно менше або дорівнює 0, то процес блокується до тих пір, поки S чи не стане більше 0, після чого з S віднімається 1. Успішна перевірка і зменшення є неподільною операцією.
- при виконанні операції V над семафором S до його значення просто додається 1. Під час виконання цієї операції до змінної S немає доступу іншим потокам.
Ніякі переривання під час виконання примітивів V і Р неприпустимі.
Однією з типових завдань, що вимагають організації взаємодії процесів з використанням семафорів, є завдання producer-consumer (виробник-споживач). p> Наприклад. Нехай буферний пул складається з N буферів, кожен з яких може містити один запис. p> Поток-виробник здійснює запис у буфер, а потік-споживач - читання з буфера. У загальному випадку потік-виробник і потік-споживач можуть мати різні швидкості і звертатися до буферного пулу з зміною інтенсивністю, В один період швидкість запису може перевищувати швидкість читання, в іншій - навпаки. p> Для правильної спільної роботи потік-виробник повинен припинятися, коли всі буфери опиняються зайнятими, і активізуватися при звільненні хоча б одного буфера. Навпаки, потік-споживач повинен припинятися, коли всі буфери порожні, і активізуватися при появі хоти б одного запису.
Введемо два семафора: е - число порожніх буферів, і f - число заповнених буферів, причому в початковому стані е = N, af = 0. Тоді робота потоків з загальним буферним пулом може бути описана таким чином (рис.1). p> Поток-виробник передусім виконує операцію Р (е), за допомогою якої він перевіряє, маються Чи в буферному пулі незаповнені буфери. Відповідно до семантикою операції Р, якщо семафор е дорівнює 0 (тобто вільних буферів в даний момент немає), то потік-виробник переходить в стан очікування.
Якщо ж значенням е є позитивне число, то він зменшує число вільних буферів, записує дані в черговий вільний буфер і після цього нарощує число зайнятих буферів операцією V (f). Потік-споживач діє аналогічним чином, з тією різницею, що він починає робіт у с перевірки наявності заповнених буферів, а після читання даних нарощує кількість вільних буферів.
В
Семафор може перебувати в сигнальному або несигнальному стані. Додаток виконує очікування для семафора за допомогою таких функцій, як WaitForSingleObject () або WaitForMultipleObject (). p> Розглянемо засоби синхронізації Win32 АРI, засновані па використанні об'єктів виконавчої системи з дескрипторами. Для всіх таких об'єктів організація очікування зводиться до викликанню потоком управління функції очікування, що приймає як параметр дескриптор об'єкта (або масив дескрипторів) і перевіряє, не відбулася чи сигналізація цього об'єкта. Умова сигналізації залежить від об'єкта синхронізації. p> У разі невиконання умови сигналізації потік переходить в стан очікування, витрачаючи дуже мало ресурсів (процесорного часу тощо), до тих пір, поки сигналізація таки не відбудеться або поки не мине максимальний час очікування, якщо такий було встановлено.
Коли сигналізація відбулася, потік негайно виходить зі стану очікування (з функції очікування) і продовжує своє виконання. Функція очікування в цьому випадку перед виходом може змінити стан об'єкта (наприклад, зайняти блокування).
Для очікування сигналізації одного об'єкта у ...
