[,]:
n ;
n ;
n *).
[]. .
5.4.1
( , ) . , [] , , .
[,,].
, , . - . . .
: -, , , -, .
, . . , . , .
[md]. , . , . , . . 5.2 . 1 2, p1, 1 2, p2 1- . , 2 , , 2- , .
. .
. . , , , .
|
|
|
. , . . , (indefinite postponement), , []. , , . . .
5.4.2
. , . , , .
, , , []. , . . , -. , , , .
. - . . , . .
:
type
n=Number_of_Process;
Process_Resource_State =
record
Claim:integer; {}
Held:integer; { }
Request:boolean;{ }
end;
Allocation_State =
record
Hold:array [1..n] of Process_Resource_State;
Free:integer;{ }
end;
. . :
1) , ;
2) , ();
3) Held, , .
, . , . , . , .
|
|
|
. .5.4 )
.
)
)
. 5.4.
.5.4.) , 2, 1, 3, . , 2 . 2 . 2 5 , 1 ( - 4). 4 . .
, , , . , , .5.4.) , .5.4.), . . , .
. .
, , :
1) , , ;
2) , , ;
3) i- , .
, , , . n! , . n², .
O(n²), O order of, :
S = ;
S <> []
S, ;
, - S,
;
;
;
, .
[]. S[0..r-1], r - .
S[i] = r - i i: 0 £ i < r;
, C h , S[i] i: 0 ≤ i < C-h.
- S[i] , - .
|
|
|
, . . . . , . , . , , .
5.4.3 .
, . : . , , , , , . , - , , .
5.4.4. .
. . . . , , .
[].
, - , , , . , , , , .
- .
L = (X,U;P) , X ¹ (), U () - P, P(x,u,y) : u x y :
) P x, u, y, x, y Î X
u Î U;
) " uÎU $ x, y ÎX { P(x,u,y) & " x',y'Î X [ P(x',u',y') Þ (x = x' & y = y') V (x = y'&
y = y'& y = x')]}, .. - () x, y, y,x ( ..) [].
, x y, y x .
, X , - = p1,p2,..., pn - r1,r2,..., rm: X = , .
|
|
|
(r,p), r Î p Î . (p,r), pÎ r Î .
.4.5 . , , . , .
, , () . pi, , , , pi pi. . pi . . 4.6 .
, p1 r1 r2. , p1. p2.
, , . , .
r1 p1 (.4.7), p1 p2, . . - .
, . . , . , , *).
, , pi.
. [,].
5.4.4.1. .
, .
, , {p,r} {r,p}, , . , . .
. pi .
Type
process_ptr = ^Held;
Held = record
resource: resource_type; { }
number: integer; { }
next: process_ptr;
end;
Var p1,...,pn: process_ptr;
.
rj..
Type
resource_ptr = ^Inquiry;
Inquiry = record
process: process_type;
number: integer; { }
next: resource_ptr;
end;
Var r1,r2,...,rm: resource_ptr;
, , . .
.
, . , , . , , . , , n(n+1)/2. m , , , mn².
|
|
|
, : , ; pi i, , . .
, , . , , , . , .
[] , . : . , ( ) ( ). , .4.8. , - .
. :
1) p1 r1;
2) p2 r3;
3) p3 r2;
4) p2 r4;
5) p1 r5;
6) p1 r3; r3 , . : j = 1, i = 3, k = 2;
() k = 2 ;
() 1 3;
7) p2 r2;
j = 2, i = 2, k=3;
k = 3 ; 2-
2;
8) p3 r5;
j = 3, i = 5,k = 1;
k = 1 3, l = 3; () , 3- 2 (n = 2);
(j = n) k = 2; , 2 2; , 2 3, n = 3;
(j = n) ! p3 .
.
. .
5.4.5. .
. : -, , , -, . / , , , . , .
, , . : 1) , ; 2) , . .
, , . . : 1) , , , , ; 2) , .
. . , , .
. , . , . , , , .
5.4.6.
, [,,] , .
, ( ) , . ( ), . , , , (.4.7.). : , . , , .. , .
:
1) , , , , , ;
2) , , ;
3) - , , , , , , .
, .
. , . .
. , . , . : , , , ; .. , . . (starvation).
, . , , . . . . . . , . . . .
. .
. , . , .
, . . .
.
5.1. , . 1000 , . , 19000 . 1000 . :
1) 19000 ;
2) .
, .
5.2. . . ? , . ?
5.3. ? ? ?
5.4. .
5.5. , , , . , :
) ;
) ;
) , ;
) ;
) .
5.6. , . . , .
5.7. , . , , :
5.7. , . , , :
5.8. , , , .
5.9. ? ?
) .
) .
) .
) .
) .
) .
) .
5.10. , , : ; , , , .
5.11. . , . m n . . n . m+n. , .
