-- ( ) , . , .
S, O R. , , S O. s S o O . , , (r), (w), (e). (). , 1.1.
1.1 | |||||
o1 | o2 | o3 | o4 | ||
s1 | rwe | rw | rw | ||
s2 | e | rwe | r | ||
, o1, o2 , s1 s2.
, , {, , }.
, . , .
. 6 : / , / . 1.2.
R, S, O (S O, |S|=i, |O|=j, i j), Mi j ( , s o M[s,o] ). ( ) S, O, M, R ( ).
. : , , .
1.2
--
s, | S=S{s}; O=O{s}; |
sS | M[s,o]=M[s,o] sS,oO; |
M[s,o]= oO, M[s,s]= | |
sS | |
o, | S=S;O=O{o}; |
oO | M[s,o]=M[s,o] sS,oO; |
M[s,o]= sS | |
S=S\{s};O=O\{s}; | |
s, sS | M[s,o]=M[s,o] sS,oO; |
o, | S=S; O=O\{o}; |
oO | M[s,o]=M[s,o] sS,oO; |
r R | S=S; O=O; M[s,o]=M[s,o]ss,sS, |
M[s,o],sS,oO | oo, oO; |
M[s,o]=M[s,o]{r} | |
r R | S=S; O=O; M[s,o]=M[s,o]ss,sS, |
M[s,o],sS,oO | oo, oO; |
M[s,o]=M[s,o]\{r} | |
|
|
[3]: command (x1, , xk):
if r1 M[xs1,xo1] andand rm M[xsm,xom] then
α1;
αn; end
r1, , rm R , α1, , αn . , Q Q . , , Q=Q. , s f. (read), (write), (own). C, - .
command (s, f)
f;
ownM[s,f]; readM[s,f];
writeM[s,f];
end
, , , .
.
, r R c, Q , r M, r .
Q 0 r, Q, r.
-, .
-- :
1. , , - r;
2. .
, , -- , . , - , , . , - , , .. , , .
-
. :
S (, );
O (, );
|
|
L (, , , -, );
F: S O L , ;
V (F, M), M (, , , Mso, M[s,o], s o).
v0 V, R T: (V R) V, .
- : .
(F,M) , s S, o O :
M[s,o] F(s) F(o),
. . s o, o s. .
(F,M) , s S, o O :
M[s,o] F(o) F(s),
. . s o, o s. .
vV , , .
(v0,R,T) , v0 , v0 R, .
- , . , : , , , . -, .
.
(v0,R,T) (. . v0, R, T) , v0 T , v V, v0 - R ( T(v,r)=v*, v=(F,M) , v*=(F*,M *) ), s S, o O :
1. M*[s,o] M[s,o], F*(s)F*(o);
2. M[s,o] F*(s)<F*(o), M*[s,o];
3. M*[s,o] M[s,o], F*(o)F*(s);
4. M[s,o] F*(o)<F*(s), M*[s,o].
.
. , v0 . v*, v0 R v: T(v,r)=v*. , , T, v* . T , v* . , . .
. . . , - v0 , , v*,
|
|
v0 R. , T(v,r)=v*, v , v* - . .
-, .
1. , .
- , , . , , , . , - .
2. . , , . , - , , .
3. -. : ( , , -) ( ). , , F(s)>F(o), . (, ) .
4. . - ,
, , , , , , . . , .