Дефинирани са 3 действия с променливата семафор:
1. Инициализира се с неотрицателно число.
2. Примитива wait(s)
намалява
стойността на s с 1. Ако стойността
стане отрицателна, процесът (изпълняващ wait)
се блокира.
3. Операцията signal(s)
увеличава
стойността на s с 1. Ако стойността
не е положителна, процесът (блокиран с wait)
се разблокира.
Примитивите wait и
signal
се предполат неделими, т.е. те не могат да бъдат прекъсвани.
struct semaphore {
int count;
queueType queue;
};
|
void wait(semaphore s)
{ s.count--; if (s.count < 0) { place_this_process_in_s.queue; block_this_process; } } |
void signal(semaphore s)
{ s.count++; if (s.count <= 0) { remove_a_process_from_s.queue(P); place_the_process_on_ready_list(P); } } |
Пример.
--- FIGURE 5.8 ---
Ако s.count е отрицателно
число (3, 6 и 7), -s.count е броят
на чакащите на семафора s процеси, т.е. броят на
процесите в опашката s.queue.
Ако s.count е положително
число (1), s.count е броят на процесите,
които могат да минат през семафора, преди той да се затвори. Опашката s.queue
е празна. Ако s.count е 1
(1), то един процес минава и затваря семафора. Ако s.count
е
0 (2, 4 и 5), то идващ процес се блокира и отива на опашката.
Двоични семафори - семафорът има две състояния - отворен
(1) и затворен (0):
struct binary_semaphore {
int value; /* = 0, 1 */
queueType queue;
};
|
void waitB(binary_semaphore s)
{ if (s.value==1) s.value=0; else { place_this_process_in_s.queue; block_this_process; } } |
void signalB(binary_semaphore s)
{ if (s.queue.is_empty()) s.value=1; else { remove_a_process_from s.queue(P); place_process_on_ready_list(P); } } |
** Взаимно изключване - решение на задачата за ВИ със семафори.
/* program mutual_exclusion */
const int n; /* number of processes */
semaphore s = 1;
void P(int i)
{
while (true)
{
wait(s);
<critical section>
signal(s);
<remainder>
}
}
void main()
{
parbegin(P(1), P(2),..., P(n));
}
Стойността на променливата s.count
има
следния смисъл:
- s.count >= 0 е броят
на процесите, които могат да изпълнят примитива wait(s)без
да бъдат блокирани (и няма изпълнение на signal(s));
- s.count < 0 е броят
на процесите, чакащи в s.queue.