Основы операционных систем 1

возникновения тупиковых ситуаций при приоритетном планировании
while (some condition) {
entry section
critical

section

exit section

remainder section

}

while (some condition) {

entry section

critical section

exit section

remainder section

}

L

H

процесс блокируется;
S = S - 1
V(S): S =

S + 1

S – семафор – целая разделяемая переменная с неотрицательными значениями

При создании может быть инициализирована любым неотрицательным значением

конечного размера – N

1;
Semaphore full = 0;
Semaphore empty = N;
P(empty);
P(mut_ex);
V(full);
V(mut_ex);
while (1) {
}
consume_item();
get_item();
P(full);
P(mut_ex);
V(empty);
V(mut_ex);

}
void m2(…) { … }
void mn(…) { … }
…
Блок инициализации

переменных;

Структура

только одного процесса, ожидающего этого (если он существует)
Процесс, выполнивший операцию

wait над условной переменной, всегда блокируется

Условные переменные (condition variables)

C.wait
C.signal

Процесс, выполнивший операцию signal, немедленно покидает монитор

{
}
consume_item();
PC.get ();
Monitor PC {
}
Condition full, empty;
int count;
void put ()

{
if (count == N) full.wait;
put_item(); count++;
if (count == 1) empty.signal;
}

{ count = 0; }

void get () {
if (count == 0) empty.wait;
get_item(); count--;
if (count == N-1) full.signal;
}

send (address, message)
блокируется при попытке записи в заполненный

буфер
Для приема данных
receive (address, message)
блокируется при попытке чтения из пустого буфера

Обеспечивают взаимоисключения при работе с буфером

(1) {
}
receive (address,item);
consume_item()

= 1; /* Для организации взаимоисключения */
При входе в монитор
При

нормальном выходе из монитора

void mon_enter (void){
P(mut_ex);
}

void mon_exit (void){
V(mut_ex);
}

Semaphore ci = 0; int fi = 0; /* Для каждой условной переменной */

Для операции wait

void wait (i){
fi += 1;
V(mut_ex); P(ci);
fi -= 1;
}

Для операции signal

void signal_exit (i){
if (fi) V(ci);
else V(mut_ex);
}

процесса: Semaphore ci = 0;
Очередь на чтение
Очередь на запись
Один на

всех: Semaphore mut_ex = 1;

Чтение

P(mut_ex)

Есть msg?

– встать в очередь

– V(mut_ex)

– P(ci)

– прочитать

– есть кто на запись?

– V(mut_ex)

– удалить

– V(cj)

Semaphore cj = 0;

Один на всех: Semaphore mut_ex = 0;

-нет

Pi

-да

M1

-нет

Pj

-да

Semaphore cj = 1;

процесса: Semaphore ci = 0;
Очередь на чтение
Очередь на запись
Один на

всех: Semaphore mut_ex = 1;

Запись

P(mut_ex)

Есть место?

– встать в очередь

– V(mut_ex)

– P(ci)

– записать

– есть кто на чтение?

– V(mut_ex)

– удалить

– V(cj)

Semaphore cj = 0;

Один на всех: Semaphore mut_ex = 0;

-нет

Pj

-да

M1

-нет

Pi

-да

Semaphore cj = 1;

M2

M3

M4

{
int count;
Condition ci;

/* для каждого процесса */
очередь для ожидающих процессов;
void P(void){
if (count == 0) { добавить себя в очередь;
ci.wait;
}
count = count -1;
}
void V(void){
count = count+1;
if(очередь не пуста) { удалить процесс Pj из очереди;
cj.signal;
}
}
{ count = N; }
}

send (A, “P, P1”);
receive

(P1, msg);

P1

Pm

A

int count = 1;

P0

Для
ожидания

while(1) {
receive (A, msg);
if(это “P” сообщение){
if(count > 0) {count = count -1;
send (Pi, msg); }
else добавить в очередь;
}
else if(это “V” сообщение) {

P1

send (A, “V,Pm”);
receive (Pm, msg);

Pm

…

send(Pi, msg);
if(есть ждущие){
удалить из очереди;
send (Pk, msg); }
else count = count+1;
}
}

P:

V:

“P, P1”

int count = 0;

msg

P1

“V,Pm”

msg

msg