UNIX
, ,
. , ,
, (-
12.1), -
,
. , -
.
-
- -
. , ,
,
. -
,
. ,
-
.
,
.
, UNIX
,
,
.
+-----------+ +-----------+ +-----------+
| | | | | |
| 1 | | 2 | ........... | n |
+-----+-----+ +-----+-----+ +-----+-----+
----------+-------+-------+--------------+------------+-----------
+---+----+ +-----------+-------------+
| | | |
+--------+ +-------------------------+
12.1.
2 ,
UNIX :
, -
, ,
,
. ,
,
,
, , -
.
362
+-------------------------------------------------------+
| struct queue { |
| |
| } *bp, *bp1; |
| bp1->forp=bp->forp; |
| bp1->backp=bp; |
| bp->forp=bp1; |
| /* |
| * */ |
| bp1->forp->backp=bp1; |
+-------------------------------------------------------+
12.2.
2 (
12.2), ( bp1)
( bp). ,
, A
bp bpA, B -
bpB. -
: ,
B 4 , A
. , , A
. ,
, ( -
2 ).
,
. -
, ,
.
:
1. ,
-
;
2. , -
;
3. -
.
,
.
, - (master) -
, - (slave) - -
, VAX 11/780 (. [Goble 81]).
, ,
.
-
.
-
.
, , -
( 12.3). -
, -
; ,
, .
363
, -
, -
, ,
( 12.4). -
,
. -
, ,
.
, , -
.
-
. ,
,
,
. , -
;
,
. ,
, -
.
+------------------------------------------------------------+
| schedule_process () |
| : |
| : |
| { |
| ( -|
| ) |
| { |
| ( ) |
| ( - |
| ) |
| , |
| ; |
| /* - |
| * */ |
| ( , -|
| ) |
| , |
| ; |
| ( ) |
| , -|
| ; |
| /* |
| * */ |
| } |
| - |
| ; |
| , - |
| ; |
| } |
+------------------------------------------------------------+
12.3.
364
+------------------------------------------------------------+
| syscall /* - |
| * */ |
| : |
| : |
| { |
| ( ) |
| { |
| -|
| ; |
| ; |
| } |
| ;|
| , |
| "" (); |
| ( |
| ) |
| ; |
| } |
+------------------------------------------------------------+
12.4.
-
, -
. , -
(). -
, .
, -
, , -
. ,
, -
, -
. -
, ,
.
. -,
,
. -
, (
,
). -
. -, ,
, , .
UNIX
,
. -
AT&T 3B20A IBM 370, -
(. [Bach 84]).
.
: .
2,
,
365
UNIX
. :
( ) /* */
( );
;
:
;
, -
;
A/ A B/ B
+---------------------------------------------------------
| +---------------------------+
| | |
| - +---------------------------+ -
| - -
| - -
| , ,
|
| () ()
t - + - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
|
|
|
|
v ^ ^
| |
+------+ +------+
12.5. -
,
, 12.5. -
, -
. t -
, ,
.
: , -
, ,
. , ,
A -
B , -
A . -
, , -
:
, -
.
,
() :
* , -
;
* P, .
366
, -
;
* V, .
0, ,
P,
;
* P, CP (conditional P),
"" -
, .
, -
"".
, , -
, 11.
[Dijkstra 65] , -
. 12.6
, . Pprim -
, val;
.
, ,
( val
, 2),
( , 1).
, -
1 . Pprim
, , -
, , -
, -
( [Dijkstra 65] [Coffman 73]).
Vprim -
-
val
lastid. , :
Pprim();
;
Vprim();
() ,
, , -
Pprim, -
. , , IBM 370 compare
and swap ( ), AT&T 3B20 - read and
clear ( ). read and clear -
, ( 0)
0 -
.
, -
, - 0: -
. ,
Pprim ( 12.7).
read and clear , -
, . -
, , 1.
367
,
,
, .
+------------------------------------------------------------+
| struct semaphore |
| { |
| int val[NUMPROCS]; /* ---1 - |
| /* */ |
| int lastid; /* , - |
| /* */ |
| }; |
| int procid; /* - |
| /* */ |
| int lastid; /* , - |
| /* */ |
| |
| INIT(semaphore) |
| struct semaphore semaphore; |
| { |
| int i; |
| for (i = 0; i < NUMPROCS; i++) |
| semaphore.val[i] = 0; |
| } |
| Pprim(semaphore) |
| struct semaphore semaphore; |
| { |
| int i,first; |
| |
| loop: |
| first = lastid; |
| semaphore.val[procid] = 1; |
| /* */ |
+------------------------------------------------------------+
12.6.
, ,
, ,
. Pprim Vprim
, , -
12.3.1.
,
( ),
, . -
, P V -
.
. , -
, . -
P ( 12.8) Pprim
.
,
. -
( Vprim), -
, .
,
, ,
368
+------------------------------------------------------------+
| forloop: |
| for (i = first; i < NUMPROCS; i++) |
| { |
| if (i == procid) |
| { |
| semaphore.val[i] = 2; |
| for (i = 1; i < NUMPROCS; i++) |
| if (i != procid && semaphore.val[i] == 2) |
| goto loop; |
| lastid = procid; |
| return; /* , |
| /* |
| */ |
| } |
| else if (semaphore.val[i]) |
| goto loop; |
| } |
| first = 1; |
| goto forloop; |
| } |
| Vprim(semaphore) |
| struct semaphore semaphore; |
| { |
| lastid = (procid + 1) % NUMPROCS; /* |
| /* */ |
| semaphore.val[procid] = 0; |
| } |
+------------------------------------------------------------+
12.6. ()
sleep ( 6): ,
, -
, ,
. V ( 12.9) -
Pprim -
. , -
" -
".
P V sleep wakeup.
,
, sleep wakeup
. - , -
P ,
P sleep. V, ,
,
wakeup , , -
.
wakeup :
, , -
. , -
, , ,
, , -
-
. :
write,
369
+-------------------------------------------------------+
| struct semaphore { |
| int lock; |
| }; |
| |
| Init(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
| |
| Pprim(semaphore) |
| struct semaphore semaphore; |
| { |
| while (read_and_clear(semaphore.lock)) |
| ; |
| } |
| |
| Vprim(semaphore) |
| struct semaphore semaphore; |
| { |
| semaphore.lock = 1; |
| } |
+-------------------------------------------------------+
12.7. ,
read and clear
-
. , ,
. P V
,
, - -
, . -
(sleep-lock) ,
, -
.
, , -
, P V
.
, -
wakeup ?
while (value(semaphore) < 0)
V(semaphore);
,
, 0, -
, -
. , -
, , A -
,
B P, -
-1 ( 12.10). A , ,
. ,
-
, .
370
+------------------------------------------------------------+
| P /* P */ |
| : (1) |
| (2) |
| : 0 - |
| -1 - |
| , -|
| |
| { |
| Pprim(semaphore.lock); |
| (semaphore.value); |
| (semaphore.value >= 0) |
| { |
| Vprim(semaphore.lock); |
| (0); |
| } |
| /* */ |
| ( ) |
| { |
| ( , - |
| ) |
| { |
| (semaphore.value); |
| ( ) |
| { |
| Vprim(semaphore.lock); |
| (-1); |
| } |
| |
| { |
| Vprim(semaphore.lock); |
| longjmp; |
| } |
| } |
| } |
| -|
| ; |
| Vprim(semaphore.lock); |
| ; |
| (. ); |
| (0); |
| } |
+------------------------------------------------------------+
12.8. P
, -
. , , A B,
. A , B -
; -1. V A
, B
. , A,
- , .
P, , -
, , .
"" . ,
371
+------------------------------------------------------------+
| V /* V */ |
| : |
| : |
| { |
| Pprim(semaphore.lock); |
| (semaphore.value); |
| (semaphore.value <= 0) |
| { |
| , -|
| , ; |
| ; |
| } |
| Vprim(semaphore.lock); |
| } |
+------------------------------------------------------------+
12.9. V
(sleep-lock), A ,
.
sleep-lock ,
.
,
. -
, A B, , -
.
, 12.11,
; A
SA, B SB.
A SB, P -
, SB
0. B,
SA. , .
-
, -
. ,
"" . , -
, -
, , -
, . , , -
- , -
. ,
, CP (. -
12.12): , B
, , -
, , A -
.
, -
, , ,
- , (. 6), -
P . -
" " (spin lock) -
, :
while (! CP(semaphore));
372
A/ A B/ B
+-----------------------------------------------------------
| - +------------------------+ -
| - | = -1 | -
| - +------------------------+ -
| ( - -
| < 0) ? -
| () -
| V() -
| - -
| - +------------------------+ -
| - | = 0 | -
| - +------------------------+ -
| ( - -
| < 0) ? -
| - -
| - P()
| - = -1
| -
| ()
| !!
v
12.10. wakeup -
V
,
0;
, ,
CP.
,
, " ". -
, , , -
;
, " ", -
. 12.13.
A/ A B/ B
+-----------------------------------------------------------
| P( SA); -
| - -
| - -
| - -
| - P( SB);
| - -
| - -
| - -
| - P( SA);
| -
| -
| P( SB);
|
|
v !!
12.11.
-
373
0,
CP "".
, .
,
.
, wait -
, -
, ,
, ,
.
getblk, 3. -
: , -
. -
. ,
200 , ,
; P,
, , ,
V. -
, . -
--
A/ A B/ B
+-----------------------------------------------------------
| P( SA); -
| - -
| - P( SB);
| - -
| - -
| - (! CP( SA))
| - {
| - V( SB);
| - -
| -
| - }
| P( SB);
|
v
12.12. P
, , -
() .
, , , --
; -
374
. -
.
12.14 getblk,
.
, P -
, -. -
, ,
, , , V.
-,
. ,
-. ( A) , -
P ,
, - -
,
. A , -
CP; , -
. A ,
, CP,
, , , -
P, .
, -
.
|
| P();
| ( 0)
|
|
|
| CP() ---
|
|
| .
|
| .
|
| ( )
v
12.13.
, CP - -
, , , . A -
, -, , -
P . P -
, , CP . -
A .
, - -
, A - (*). -
---------------------------------------
(*) - -
, V,
-
, -
.
375
( , )
, CP. -
, , -
. ,
+------------------------------------------------------------+
| getblk /* */ |
| : |
| |
| : , |
| |
| { |
| ( ) |
| { |
| P( -); |
| ( -) |
| { |
| ( CP( ) - |
| ) /* */ |
| { |
| V( -); |
| P( ); /* -|
| * |
| */ |
| ( CP( -) -|
| ) |
| { |
| V( ); |
| ; /* "" |
| */ |
| } |
| ( |
| ) |
| { |
| V( ); |
| V( -); |
| } |
| } |
| ( CP( -|
| ) ) |
| ; /* " " */ |
| ; |
| ; |
| V( ); |
| V( -); |
| ; |
| } |
| /* - |
| * |
| */ |
| /* -|
| * |
| */ |
| } |
| } |
+------------------------------------------------------------+
12.14.
376
, ,
, -
. A, -
, ,
, ,
; -
, . -
, A .
+------------------------------------------------------------+
| wait |
| { |
| (;;) /* */ |
| { |
| -: |
| ( " |
| ") |
| ; |
| P(zombie_semaphore); /* - 0 */|
| } |
| } |
+------------------------------------------------------------+
12.15. wait
.
7 ,
wait
.
wait ,
exit; , , ,
- wait,
, -
. -
, zombie_semaphore -
.
wait/exit ( 12.15). ,
V, -
, wait.
, wait, -
, . -
exit wait , -
exit , , V, -
, -
. - .
-
AT&T 3B20 -
, P V (.
[Bach 84]). 10 , , -
, ( -
377
20).
:
P( );
();
V( );
,
- ,
.
, . , -
,
. ,
, , , -
, . -
, , ;
-
. 3B20A -
,
.
,
: ,
. ,
. 3B20A -
,
.
,
, (.
6). , , -
, . -
,
.
-
, . , ,
, A,
. ,
, ,
A.
B, -
. A -
, A ,
. ,
( ,
) (, , )
.
;
, -
,
. ;
.
,
.
378
Tunis -
UNIX, , Concurrent
Euclid, , .
Tunis ,
, , ,
. ,
.
,
, . -
, , -, -
( P V -
), -,
. ,
, ,
(. [Holt 83], .190).
Tunis
UNIX .
-
UNIX: , -
, ()
, ,
.
, ,
, . , -,
,
. -, , -
, -
; ,
, . -
, ,
:
,
. , -
-
(., , [Beck 85]),
, -
.
1. -
, -
, .
, (-
) . ,
?
?
379
2. , -
, ( 12.6).
P-V
. -
?
3. CP ( P),
P.
4. , P V ( 12.8 12.9) -
. ?
5. " " :
while (! CP());
P ? (
: ,
P ?)
6. getblk, 3. -
, -
.
*7. ,
, -
. -
.
*8. , , -
0 -
-
. ,
, . -
, P
V. .
, -
,
?
*9. ,
. ?
, , -
?
10.
( 8). .
?
380
Last-modified: Thu, 12 Feb 1998 07:20:44 GMT