12.  UNIX , , . , , , (- 12.1), - , . , - . - - - . , , , . - , . , - . , . , UNIX , , . +-----------+ +-----------+ +-----------+ | | | | | | | 1 | | 2 | ........... | n | +-----+-----+ +-----+-----+ +-----+-----+ ----------+-------+-------+--------------+------------+----------- +---+----+ +-----------+-------------+ | | | | +--------+ +-------------------------+ 12.1. 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. - . , . 12.2  , - (master) - , - (slave) - - , VAX 11/780 (. [Goble 81]). , , . - . - . , , - ( 12.3). - , - ; , , . 363 , - , - , , ( 12.4). - , . - , , . , , - . - . , , , . , - ; , . , , - . +------------------------------------------------------------+ | schedule_process () | | : | | : | | { | | ( -| | ) | | { | | ( ) | | ( - | | ) | | , | | ; | | /* - | | * */ | | ( , -| | ) | | , | | ; | | ( ) | | , -| | ; | | /* | | * */ | | } | | - | | ; | | , - | | ; | | } | +------------------------------------------------------------+ 12.3. 364 +------------------------------------------------------------+ | syscall /* - | | * */ | | : | | : | | { | | ( ) | | { | | -| | ; | | ; | | } | | ;| | , | | "" (); | | ( | | ) | | ; | | } | +------------------------------------------------------------+ 12.4. - , - . , - (). - , . , - , , - . , , - , - . - , , . . -, , . - , ( , ). - . -, , , , . 12.3  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 . - , , - : , - . 12.3.1  , () : * , - ; * P, . 366 , - ; * V, . 0, , P, ; * P, CP (conditional P), "" - , . , - "". , , - , 11. 12.3.2  [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) ? - | -