b> 3.3.1
Визначення семафорів Семафор являє собою оброблюваний ядром цілочисельний об'єкт, для якого визначені наступні елементарні (неподільні) операції:
В· Ініціалізація семафора, в результаті якої семафору присвоюється невід'ємне значення;
В· Операція типу P, яка зменшує значення семафора. Якщо значення семафора опускається нижче нульової позначки, що виконує операцію процес призупиняє свою роботу;
В· Операція типу V, що збільшує значення семафора. Якщо значення семафора в результаті операції стає більше або дорівнює 0, один з процесів, призупинених у час виконання операції P, виходить зі стану приостанова;
В· Умовна операція типу P, скорочено CP (conditional P), яка зменшує значення семафора і повертає логічне значення "істина" в тому випадку, коли значення семафора залишається позитивним. Якщо в результаті операції значення семафора має стати негативним або нульовим, ніяких дій над ним не виробляється і операція повертає логічне значення "брехня".
Визначені таким чином семафори, безумовно, ніяк не пов'язані з семафора користувацького рівня.
3.3.2 Реалізація семафорів
Дійкстра показав, що семафори можна реалізувати без використання спеціальних машинних інструкцій. Тут представлені реалізують семафори функції, написані на мові Сі. br/>
struct semaphore
{
int val [NUMPROCS];/* замок - 1 елемент на кожен процесор */
int lastid;/* ідентифікатор процесора, який отримав семафор останнім */
};
int procid;/* унікальний ідентифікатор процесора */
int lastid;/* ідентифікатор процесора, який отримав семафор останнім */
Init (semaphore)
struct semaphore semaphore;
{
int i;
for (i = 0; i
semaphore.val [i] = 0;
}
Pprim (semaphore)
struct semaphore semaphore;
{
int i, first;
loop:
first = lastid;
semaphore.val [procid] = 1;
forloop:
for (i = first; i
{
if (i == procid)
{
semaphore.val [i] = 2;
for (i = 1; i
if (i! = procid && semaphore.val [i] == 2)
goto loop;
lastid = procid;
return;
/* успішне завершення, ресурс можна використовувати */
}
else if (semaphore.val [i])
goto loop;
}
first = 1;
goto forloop;
}
Vprim (semaphore)
struct semaphore semaphore;
{
lastid = (procid + 1)% NUMPROCS;/* на наступний процесор */
semaphore.val [procid] = 0;
}
Функція Pprim блокує семафор за результатами перевірки значень, що містяться в масиві val; кожен процесор в системі управляє значенням одного елемента масиву. Перш ніж заблокувати семафор, процесор перевіряє, чи не заблоковано вже семафор іншими процесорами (відповідні їм елементи в масиві val тоді мають значення, рівні 2), а також не робляться чи спроби в даний момент заблокувати семафор з боку процесорів з нижчим кодом ідентифікації (Відповідні їм елементи мають значення, рівні 1). Якщо будь-яке з умов виконується, процесор переустановлює значення свого елемента в 1 і повторює спробу. Коли функція Pprim відкриває зовнішній цикл, змінна циклу має значення, на одиницю перевищує код ідентифікації того процесора, який використовував ресурс останнім, тим самим гарантується, що жоден з процесорів не може монопольно заволодіти. Функція Vprim звільняє семафор і відкриває для інших процесорів можливість отримання виняткового доступу до ресурсу шляхом очищення відповідає поточному процесору елемента в масиві val і переналаштування значення lastid. Щоб захистити ресурс, слід виконати наступний набір команд:
Pprim (семафор);
команди використання ресурсу;
Vprim (семафор);
У більшості машин є набір елементарних (неподільних) інструкцій, що реалізують операцію блокування більш дешевими засобами, бо цикли, що входять у функцію Pprim, працюють повільно і знижують продуктивність системи. Так, наприклад, в машинах серії IBM 370 підтримується інструкція compare and swap (порівняти і переставити), в машині AT & T 3B20 - інструкція read and clear (прочитати і очистити). При виконанні інструкції read and clear процесор зчитує вміст комірки пам'яті, очищає її (скидає в 0) і за результатами порівняння початкового вмісту з 0 встановлює код завершення інструкції. Якщо ту ж інструкцію над тією ж осередком паралельно виконує ще один процесор, один з двох процесорів прочитає початкове вміст, а іншого - 0: неподільність операції гарантується апаратним шляхом. Таким чином, за рахунок використання даної інструкції функцію Pprim можна було б реалізувати менш складними засобами:
struct semaphore
{
int lock;
...
