, . , . , , . . , , , , , , .
() [10].
- (, ). , . , . , . .
- (, ). , , , -, . .
- (, , ). . .
, , , .
| |||
| |||
|
|
() . . , , . -, , , .
|
|
. . , , , , . , , .
() . (mutual exclusion). , , (. 5.12). , , , (critical section) . , . , , , .
. 5.12.
. (deadlock) . , , P1 P2, R1 R2. , . : R1 2, R2 1. . , , . .
, [17] ( Holt, 1972). 2 : - -. , () (), , , . , . 5.13 ).
, () (), , . , . 5.13 ) ). .
. , 3 (1, 2, 3), R. , 1 , 2 3 R. 1 2 3.
|
|
. 5.13.
3. , 1. R 3 , 1. 3 R. , , 2 , , .
. (), (), . , () . ( ), , . , , .
.
, () :
P: a; b; c; Q: d; e; f;
a, b, c, d, e, f .
:
PQ: a b c d e f
, ? , , interleaving. :
b c d e fa b d c e fa b d e c fa b d e f ca d b c e f......d e f a b c. , . P Q, :
P: x=2; y=x-1; Q: x=3; y=x+1, x y ? , (x, y): (3, 4), (2, 1), (2, 3) (3, 2). , , . . . , . .
, , , ? [17]. .
. , . R(P) (R read) . , W(P) (W write) . ,
|
|
R(P) = {u, v, x, w}, W(P) = {x, y}. , x R(P), W(P).
.
P Q:
- W(P) W(Q) ,
- W(P) R(Q) ,
- R(P) W(Q) ,
P Q .
, , P Q , , . .
, . , . , , . , .
, race condition ( , ). x y.
( race condition), , , , . , , , . (mutual exclusion). , .
, . , , . , . .
- , , . , . . 1, 2, 3, , , 1. , 1 2 , 3 , 1.
, , race condition, . , , , [10, 17].
- , . , ( , load, store, test) .
- , .
- Pi , , . (mutual exclusion).
- , , . , , , remainder section, , . . (progress).
- H . , , , , . (bound waiting).
, . , . , , , , .
|
|
:
while (some condition) { critical section remainder section }, . , . . , , . , , , , . , , , .
, , , PSW (Programming Status Word).
. , , , .
. , - 0, 1 . 0 .
shared int lock = 0;while (some condition) { while(lock); lock = 1; critical section lock = 0; remainder section }, , , while(lock); lock = 1; . , P0 lock . , lock 1, P1. lock . , .
. 0. , , . i- :
|
|
, , : P0, P1, P0, P1, P0,... . , turn 1 P0 , , P1 remainder section.
, . .
shared int ready[2] = {0, 0};i- , ready[i] , 1. , , 0. , .
shared int turn = 0;while (some condition) { ready[i] = 1; while(ready[1-i]); critical section ready[i] = 0; remainder section }, , , , . . ready[0] = 1 0 1, ready[1] = 1. . , (deadlock).
, , (Dekker). 1981 (Peterson) . .
shared int ready[2] = {0, 0};shared int turn;while (some condition) { ready[i] = 1; turn =1- i; while(ready[1-i] && turn == 1-i); critical section ready[i] = 0; remainder section }Pi . , . . , .
, . , - .
, , . , .
Test-and-Set, 1,
int Test_and_Set (int *target) { int tmp = *target; *target = 1; return tmp; }- ,
shared int lock = 0;while (some condition) { while(Test_and_Set(&lock)); critical section lock = 0; remainder section }, . , , , . . .
, , , . , , . , .
, , , (Dijkstra) 1965 . , , , , : P ( proberen ) V ( verhogen ). :
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.
- . (, ALGOL-68), . . P V, , , . P , , , FIFO.
, , producer-consumer (-). . , . , :
Producer: while(1) { produce_item; put_item; } Consumer: while(1) { get_item; consume_item; }, , , . , . ? empty, full mutex. full , , .
empty , mutex , put_item get_item ( " " " " , ). :
Semaphore mutex = 1;Semaphore empty = N, N ;Semaphore full = 0;Producer: while(1) { produce_item; P(empty); P(mutex); put_item; V(mutex); V(full); } Consumer: while(1) { P(full); P(mutex); put_item; V(mutex); V(empty); consume_item; }, . , : .
producer-consumer , , , , . , P, mutex, full empty. , , (mutex ), , . . , . .
. , interleaving' , . , 1974 (Hoare) , , . , .
, - . , . -, . , - , , . :
monitor monitor_name { ; void m1(...){... } void m2(...) {... }... void mn(...) {... } { ; }m1,..., mn - , , : - - .
, , . . "" "", . , , , , , . , , , .
, , . , full empty . (condition variables), wait signal, P V .
, , wait - . , wait, , , .
, - signal . , . signal , . , , , ? , , . (Hansen) : signal. . "-".
monitor ProducerConsumer { condition full, empty; int count; void put() { if(count == N) full.wait; put_item; count += 1; if(count == 1) empty.signal; } void get() { if (count == 0) empty.wait; get_item(); count -= 1; if(count == N-1) full.signal; } { count = 0; } } Producer: while(1) { produce_item;ProducerConsumer.put(); } Consumer: while(1) { ProducerConsumer.get(); consume_item;}, .
()
, [37].
- . , .
- . , , .
- . . , , .
- . , , .
, . , .
.
- .
- . , - .
- .
- , .
, , , . , , , .
. . , , , , , .
.
. , , , .
, (A, B, C, D, E, F, G) (R, S, T, V,W, U) [17].
1. A R S.
: , , ?
, (. 5.14).
. 5.14.
, , D, E, G ( ). , .
. P={P1, P2,... Pn}, n , E={E1, E2,... Em}, m . , , . A={A1, A2,... Am}. , Aj<= Ej, j = 1, 2, , m.
:
C={ci,j| i = 1, 2,, n; j = 1, 2, , m} , ci,j j- , Pi;
R={ri,j| i = 1, 2,, n; j = 1,2, , m} () , ri,j j- , Pi.
m :
. ( ). , , , , . .
.
- Pi, i- R A, .. Ri <= A, rj,I <Aj, j=1, 2, , m.
- , , , . , i- , .. Aj = Aj + ci,j, j=1, 2, , m. 1.
- , . .
? , , , , , . : , ( !) .
, . ? .
: , , , , . , , .
. , . , , . , , , , , . , , . , , .
. , . , .
, . .