成都信息工程学院：操作系统原理：os-3

1 操 作 系 统 | 进 程 的 同 步 与 通 信 1 CUIT 徐虹 第三章进程的同步与通信 ?并发执行的进程之间的关系 ?进程的互斥与同步问题 ?进程间的高级通信 操 作 系 统 | 进 程 的 同 步 与 通 信 2 CUIT 徐虹 3．1进程互斥 ?并发引起的操作系统的改变 ?操作系统必须记住各种活跃的进程 ?必须为每个进程分配和释放各种资源 ?保护每个进程的数据和物理资源 ?进程的结果必须与执行速度无关 操 作 系 统 | 进 程 的 同 步 与 通 信 3 CUIT 徐虹 ?进程间的制约 系统中的诸进程可以共行执行，并以 各自独立的速度向前推进。但由于资源共 享及进程合作（即诸进程协同完成一项共 同的任务），因而产生了进程之间的相互 制约。 ?临界区 ?临界资源（Critical Resource）：一次 仅允许一个进程使用的资源。 操 作 系 统 | 进 程 的 同 步 与 通 信 4 CUIT 徐虹 例1：两个进程对同一变量count访问和修改， P1：count+=1; P2：count-=1; 若count = 5。 P1：R1 = count; R1 = R1+1; count = R1; P2：R2 = count; R2 = R2 – 1 ; count = R2; 若顺序执行P1、P2，则count = 5。 操 作 系 统 | 进 程 的 同 步 与 通 信 5 CUIT 徐虹 P1：R1 = count; P1：R1 = count; P2：R2 = count; R1 = R1+1; P1：R1 = R1+1; P2：R2 = count; count = R1; R2 = R2 – 1; P2：R2 = R2 – 1; count = R2; count = R2; P1：count = R1; 若执行顺序如上，若执行顺序如上， 则count = 4则count = 6。 操 作 系 统 | 进 程 的 同 步 与 通 信 6 CUIT 徐虹 例2. 进程P1、P2共同调用函数echo()。 void echo() { chin = getchar(); chout = chin; putchar(chout); } 2 操 作 系 统 | 进 程 的 同 步 与 通 信 7 CUIT 徐虹 Process P1 Process P2 .. chin = getchar(); . . chin = getchar(); chout = chin; . chout = chin; putchar(chout); . . putchar(chout); .. 操 作 系 统 | 进 程 的 同 步 与 通 信 8 CUIT 徐虹 ?临界区：不允许多个并发进程交叉执行的一段程序。 cobegin process 1：begin L1：CS1; Remainder of process 1; Goto L1; end process 2：begin L2：CS2; Remainder of process 2; Goto L2; end coend 操 作 系 统 | 进 程 的 同 步 与 通 信 9 CUIT 徐虹 ?互斥 ?不允许两个以上的共享该资源的并 发进程同时进入临界区称为互斥。 ?临界区调度原则 ?空闲让进 ?忙则等待 ?有限等待 ?让权等待 操 作 系 统 | 进 程 的 同 步 与 通 信 10 CUIT 徐虹 ?互斥的软件实现 进程Pi，Pj共享临界资源R。Turn：进程编号。 ?算法1：共享一个公用整型变量turn Pi :repeat while turn <> i do no_op; critical section turn := j; remainder section until false; 操 作 系 统 | 进 程 的 同 步 与 通 信 11 CUIT 徐虹 ?算法2：用数组代替算法一中的turn var flag : array [0… n] of boolean = flase; repeat while flag[j] do no_op; flag[i] := true ; critical section flag[i] := false ; remainder section until false ; 操 作 系 统 | 进 程 的 同 步 与 通 信 12 CUIT 徐虹 ?算法3： repeat flag[i] : = true ; while flag[j] do no_op; critical section flag[i] := false ; remainder section until false ; 3 操 作 系 统 | 进 程 的 同 步 与 通 信 13 CUIT 徐虹 ?算法4：进程共享两个公用变量 Pi: repeat flag[i] : = true ; turn := j ; while ( flag[j] and turn = j ) do no_op; critical section flag[i] := false ; remainder section until false ; 操 作 系 统 | 进 程 的 同 步 与 通 信 14 CUIT 徐虹 ?算法5：对临界区S设置一个变量状态W， W=0表示资源可用，W=1表示资源已被占用。 例：Begin integer W = 0 ; Cogegin Begin L1：lock W; CS1; Unlock W; Remainder of process 1; Goto L1; End Begin L2：lock W; CS2; Unlock W; Remainder of process 2; Goto L2; End Coend End 操 作 系 统 | 进 程 的 同 步 与 通 信 15 CUIT 徐虹 ?关锁原语 lock W：if W = 1 then begin block(n); insert(WL,n); scheduler; end else W = 1; 操 作 系 统 | 进 程 的 同 步 与 通 信 16 CUIT 徐虹 ?开锁原语 unlock W：if WL<> NULL then begin remove(WL,q); status(q) = “ready”; insert(RL,q); end else W = 0; 操 作 系 统 | 进 程 的 同 步 与 通 信 17 CUIT 徐虹 ?硬件实现进程互斥 ?利用Test_and_Set 指令 function TS (var lock : boolean ) : boolean ; begin TS := lock ; Lock := true ; End Lock = true ：资源被占用 Lock = false ：资源可用 操 作 系 统 | 进 程 的 同 步 与 通 信 18 CUIT 徐虹 利用TS指令实现互斥： repeat while TS (lock) do skip ; critical section lock := false ; remainder section until false ; 4 操 作 系 统 | 进 程 的 同 步 与 通 信 19 CUIT 徐虹 ?利用Swap指令实现进程互斥 初值lock = false 表示资源可用。 Procedure Swap (var a,b : boolean) Var temp : boolean ; Begin Temp := a ; a := b ; b := temp ; End 操 作 系 统 | 进 程 的 同 步 与 通 信 20 CUIT 徐虹 repeat key := true ; repeat Swap(lock,key) ; Until key = false ; critical section lock := false ; remainder section until false ; 操 作 系 统 | 进 程 的 同 步 与 通 信 21 CUIT 徐虹 3．2信号量机制 ?整型信号量机制 ?信号量(sem) sem>=0: 表示可供并发进程使用的资源实体的个数 sem<0: 表示正在等待使用临界区的进程数。 Sem的值只能由P、V操作改变。 P：wait ( s ) V：signal (s ) 按信号量数值分为二元信号量和一般信号量。 操 作 系 统 | 进 程 的 同 步 与 通 信 22 CUIT 徐虹 ?Wait（P）和signal（V）原语 ?Wait(s) 原语 wait(s) ：Begin Lock out interrupts; s = s – 1; If s < 0 then Begin Status(q) ：= blocked; Insert(WL, q); Unlock interrupts; Scheduler; End Else unlock interrupts; End 操 作 系 统 | 进 程 的 同 步 与 通 信 23 CUIT 徐虹 ?signal原语 signal(s) ：Begin Lock out interrupts; s = s + 1; If s < =0 then Begin Remove(WL，R); Status(R) ：= ready; Insert(RL，R); End Unlock interrupts; End 操 作 系 统 | 进 程 的 同 步 与 通 信 24 CUIT 徐虹 ?利用信号量实现互斥 Begin integer mutex = 1; cobegin process1：Begin L1：wait (mutex);CS1; signal (mutex); Remainder of process 1; Goto L1; End Process2：Begin L2：wait (mutex);CS2; signal (mutex); Remainder of process 2; Goto L2; End Coend End 5 操 作 系 统 | 进 程 的 同 步 与 通 信 25 CUIT 徐虹 例、进程A、B、C依赖于D的结果 操 作 系 统 | 进 程 的 同 步 与 通 信 26 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 27 CUIT 徐虹 ?利用信号量描述前趋关系 P1：S1 P2：S2 S1——>S2 则设置信号量s=0， P1：S1；signal(s)； P2：Wait(s)；S2； 操 作 系 统 | 进 程 的 同 步 与 通 信 28 CUIT 徐虹 1 2 3 4 5 6 7 a b c d e f g h 例：根据前趋图写出可并发执行的程序： var a,b,c,d,e,f,g,h:semaphore := 0,0,0,0,0,0,0,0; 操 作 系 统 | 进 程 的 同 步 与 通 信 29 CUIT 徐虹 begin parbegin begin S1;signal(a); signal(b); signal(c); end begin wait(a); S2; signal(d); end begin wait(b); S3; signal(e); end begin wait(c); S4; signal(f); end begin wait(d); S5; signal(g); end begin wait(e); wait(f); S6 ; signal( h); end begin wait(g); wait(h); S7; end parend end 操 作 系 统 | 进 程 的 同 步 与 通 信 30 CUIT 徐虹 ?记录型信号量机制 type semaphore = record value:integer; L:list of process; end 6 操 作 系 统 | 进 程 的 同 步 与 通 信 31 CUIT 徐虹 procedure wait(s) var s:semaphore; begin S.value := S.value – 1; If S.value < 0 then block(S,L); end procedure signal(s) var s:semaphore; begin S.value := S.value + 1; If S.value < = 0 then wakeup(S,L); end 操 作 系 统 | 进 程 的 同 步 与 通 信 32 CUIT 徐虹 -1 -2 -1 操 作 系 统 | 进 程 的 同 步 与 通 信 33 CUIT 徐虹 ?信号量集机制 ?AND型信号量集机制 ?问题引入 进程A、B访问共享数据D和E 信号量Dmutex=1，Emutex=1 process A : wait(Dmutex) ; wait(Emutex) ; process B : wait(Emutex) ; wait(Dmutex) ; 操 作 系 统 | 进 程 的 同 步 与 通 信 34 CUIT 徐虹 A、B交替执行： process A : wait(Dmutex) ;则Dmutex = 0 process B : wait(Emutex) ; 则Emutex = 0 process A : wait(Emutex) ; 则Emutex = -1，阻塞 process B : wait(Dmutex) ; 则Dmutex = -1，阻塞 发生死锁。 操 作 系 统 | 进 程 的 同 步 与 通 信 35 CUIT 徐虹 ?AND同步机制的思想 Swait(S1,S2,…,Sn) If S1>=1 and S2>=1 and … and Sn>=1 then For i:=1 to n do Si := Si – 1; Endfor Else 将进程插入第i（Si<1）个等待队列。 设置该进程的程序计数器到Swait操作的开始。 Endif 操 作 系 统 | 进 程 的 同 步 与 通 信 36 CUIT 徐虹 Ssignal(S1,S2,…,Sn) For i:=1 to n do Si := Si + 1; 将所有等待Si资源的进程移到就绪队列。 Endfor 7 操 作 系 统 | 进 程 的 同 步 与 通 信 37 CUIT 徐虹 ?一般“信号量”机制 Swait(S1,t1,d1;…;Sn,tn,dn) If S1>=t1 and S2>=t2 and … and Sn>=tn then For i:=1 to n do Si := Si – di; Endfor Else 将执行进程插入第i（Si<ti）个等待队列。 设置该进程的程序计数器到Swait操作的开始。 Endif 操 作 系 统 | 进 程 的 同 步 与 通 信 38 CUIT 徐虹 Ssignal(S1,d1,…;Sn,dn) For i:=1 to n do Si := Si + di; 将所有等待Si资源的进程移到就绪队列。 Endfor 操 作 系 统 | 进 程 的 同 步 与 通 信 39 CUIT 徐虹 特例： ? Swait(S,d,d)：一个信号量，可每次 申请d个资源； ? Swait(S,1,1)：记录型信号量（S>1） 或互斥信号量（S=1）； ? Swait(S,1,0)：当S>=1，允许多个进 程进入某临界区；当S=0后，阻止任 何进程进入临界区。 操 作 系 统 | 进 程 的 同 步 与 通 信 40 CUIT 徐虹 3．3经典进程同步问题 ?同步的概念 例：计算进程和打印进程使用同一缓冲区Buf。 Pc：…… Pp：…… local Cbuf local PBuf A：Computer(Cbuf); B：While (Buf != NULL) While (CBuf!= NULL) Buf——> PBuf CBuf ——>Buf Print(PBuf)； Goto A; Goto B; 操 作 系 统 | 进 程 的 同 步 与 通 信 41 CUIT 徐虹 ?异步环境 相互合作的一组并发进程，其中每 一进程都能以各自独立的，不可预知的 速度向前推进。 ?进程同步 相互合作的进程之间需要交换一定的 信息，当某进程未获得其合作进程发来的 信息之前，该进程等待，直到该信息到来 时才被唤醒继续执行，从而保证诸进程的 协调运行。 操 作 系 统 | 进 程 的 同 步 与 通 信 42 CUIT 徐虹 ?生产者—消费者问题 ?问题描述 通过由n个环形缓冲区构成的 缓冲池，把生产者P1，P2，……， PM和一群消费者C1，C2，……， CK联系起来。 ?算法描述 8 操 作 系 统 | 进 程 的 同 步 与 通 信 43 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 44 CUIT 徐虹 变量定义： begin Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1] of item; in,out:integer := 0,0; 操 作 系 统 | 进 程 的 同 步 与 通 信 45 CUIT 徐虹 parbegin producer: begin repeat produce next product ; wait (empty); wait (mutex); buffer(in):=nextp ; in := (in+1) mod n ; signal (full); signal (mutex); until false ; end 操 作 系 统 | 进 程 的 同 步 与 通 信 46 CUIT 徐虹 consumer: begin repeat wait (full); wait (mutex); nextc := buffer(out); out := (out+1) mod n; signal (empty); signal (mutex); consume the item in nextc; until false ; end parend end 操 作 系 统 | 进 程 的 同 步 与 通 信 47 CUIT 徐虹 wait(empty) empty >= 0则数据送入缓冲区 empty < 0被阻塞（满） signal(empty) empty > 0 empty <= 0释放一个空缓冲区，唤醒一个 阻塞的生产者进程 操 作 系 统 | 进 程 的 同 步 与 通 信 48 CUIT 徐虹 wait(full) full >= 0则从缓冲区取走数据 full < 0被阻塞（空） signal(full) full > 0 full <= 0数据装入缓冲区，唤醒一个 阻塞的消费者进程 9 操 作 系 统 | 进 程 的 同 步 与 通 信 49 CUIT 徐虹 ?注意： ?互斥和同步信号量的原语必须成对 出现。 ?signal操作的次序无关紧要，但wait 操作的次序不能颠倒，否则会造成 死锁。 ?用AND信号量解决生产者——消 费者问题 操 作 系 统 | 进 程 的 同 步 与 通 信 50 CUIT 徐虹 ?读者——写者问题 读者进程 写者进程(互斥的存取共享对象) 解决读写问题,导致饥饿现象 public class readersandwriters { int readcount; semaphore x = new semaphore(1); semaphore wsem = new semaphore(1); 操 作 系 统 | 进 程 的 同 步 与 通 信 51 CUIT 徐虹 public void reader() { while (true) { wait (x); readcount++; if (readcount == 1) wait (wsem); signal (x); READUNIT(); wait (x); readcount--; if (readcount == 0) signal (wsem); signal (x); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 52 CUIT 徐虹 public void writer() { while (true) { wait (wsem); WRITEUNIT(); signal (wsem); }} public static void main (String args[]) { readcount = 0; parbegin (reader, writer); } 操 作 系 统 | 进 程 的 同 步 与 通 信 53 CUIT 徐虹 ?哲学家进餐问题 操 作 系 统 | 进 程 的 同 步 与 通 信 54 CUIT 徐虹 public class diningphilosophers { semaphore [] fork = new semaphore[5](1); int i; 10 操 作 系 统 | 进 程 的 同 步 与 通 信 55 CUIT 徐虹 public void philosopher (int i) { while (true) { think(); wait (fork[i]); wait (fork [(i+1) % 5]); eat(); signal(fork [(i+1) % 5]); signal(fork[i]); }} 操 作 系 统 | 进 程 的 同 步 与 通 信 56 CUIT 徐虹 public static void main() { parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4)); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 57 CUIT 徐虹 ?解决死锁的方法： ?至多允许四个哲学家同时进餐。 ?仅当哲学家的左右两支叉子均可用时， 才进餐。（用AND信号量机制解决哲 学家进餐问题。） ?奇数号哲学家先拿左边的叉子，偶数 号哲学家先拿右边的叉子。 操 作 系 统 | 进 程 的 同 步 与 通 信 58 CUIT 徐虹 3 . 4管程机制 ?管程的引入 ?管程的基本概念 ?管程的定义 ?条件变量 ?利用管程解决生产者——消费者 问题 操 作 系 统 | 进 程 的 同 步 与 通 信 59 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 60 CUIT 徐虹 ?利用管程解决哲学家进餐问题 Monitor forks; final static int N = 5; final static int LEFT = (i-1) mod N; final static int RIGHT = (i+1) mod N; final static int THINKING = 0; final static int HUNGRY = 1; final static int EATING = 2; 11 操 作 系 统 | 进 程 的 同 步 与 通 信 61 CUIT 徐虹 public class semaphore { int value; } int [] state = new int[N]; semaphore mutex = new semaphore(1); semaphore [] s = new semaphore[N](); 操 作 系 统 | 进 程 的 同 步 与 通 信 62 CUIT 徐虹 public void take_forks(int i) { wait(mutex); state[i] = HUNGRY; test(i); signal(mutex); if (state[i] = EATING) then wait(s[i]); } 操 作 系 统 | 进 程 的 同 步 与 通 信 63 CUIT 徐虹 public void put_forks(int i) { wait(mutex); state[i] = THINKING; test(LEFT); test(RIGHT); signal(mutex); } 操 作 系 统 | 进 程 的 同 步 与 通 信 64 CUIT 徐虹 void test(int i) { if (state[i] ==HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) { state[i] = EATING; signal(s[i]); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 65 CUIT 徐虹 public void philosopher (int i) { while (true) { think( ); take_forks(i); eat( ); put_forks(i); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 66 CUIT 徐虹 3．5进程通信 进程之间的信息交换称为进程通信。 低级通信和高级通信 ?共享存储系统（Shared-Memory System） ?基于共享数据结构的通信方式 ?基于共享存储区的通信方式 12 操 作 系 统 | 进 程 的 同 步 与 通 信 67 CUIT 徐虹 ?管道通信 管道（pipe）指用于连接一个读进程和一个 写进程，以实现它们之间通信的共享文件。 例：UNIX的管道 管道按FIFO方式单向传送消息。 写端fd[1] fd[0]读端 —————> pipe(fd) ————— > write (fd[1],buf,size) read(fd[0],buf,size) 操 作 系 统 | 进 程 的 同 步 与 通 信 68 CUIT 徐虹 例：建立一个管道，同时父进程生成一个子进程，子进 程向管道中写入一字符串，父进程从管道中读出字符 串。 #include <stdio.h> main() {int x,fd[2]; char buf[30],s[30]; pipe(fd); while ((x=fork()) == -1); if (x == 0) { sprintf(buf,”this is an example.\n”); write(fd[1],buf,30); exit(0); } else { wait(0); read(fd[0],s,30); printf(“%s”,s); } } 操 作 系 统 | 进 程 的 同 步 与 通 信 69 CUIT 徐虹 ?消息传递系统 ?通信链路（communication link） ?消息的格式 ?进程同步方式 操 作 系 统 | 进 程 的 同 步 与 通 信 70 CUIT 徐虹 操 作 系 统 | 进 程 的 同 步 与 通 信 71 CUIT 徐虹 ?信箱 当两个进程间需要通信时，由发送进程 创建一个与接收进程相连的信箱。发送进 程把消息送到信箱，接收进程从信箱中取 走消息。 信箱头：名称，大小，方向，进程名等； 信箱体：由若干格子组成，每一格存放一条 消息。 双向信箱 信箱溢出 操 作 系 统 | 进 程 的 同 步 与 通 信 72 CUIT 徐虹 13 操 作 系 统 | 进 程 的 同 步 与 通 信 73 CUIT 徐虹 ?信箱通讯原语 ?创建信箱原语 用来创建一个有格子数目和大小一定 的信箱，同时把允许该进程所创建的信 箱数目减1。 ?链接原语 信箱创建后，利用链接原语把信箱链接 在窗口上，断开链接是通过把信箱链接到 虚窗口上实现的。 操 作 系 统 | 进 程 的 同 步 与 通 信 74 CUIT 徐虹 ?发送原语 发送进程私用信号量fromnum，初值为格子数n； 接收进程私用信号量mesnum，初值为0； deposit(m) begin local x wait (fromnum) 选择空格x mailbox(x) ←m 置格x的标志为满 signal (mesnum) end 操 作 系 统 | 进 程 的 同 步 与 通 信 75 CUIT 徐虹 ?接收原语 receive(m) begin local x wait (mesnum) 选择满格x m ←mailbox(x) 置格x的标志为空 signal (fromnum) end 操 作 系 统 | 进 程 的 同 步 与 通 信 76 CUIT 徐虹 ?撤消信箱原语 信箱可在任何时候由它的拥有者 调用撤消原语予以撤消，同时将进程 所允许创建的信箱数加1，并将信箱 所占用的看见归还拥有者进程。 ?信箱类型 ?私用信箱：单向通信链路，由用户创建。 ?公用信箱：多输入/输出公用信箱，提 高效率。双向通信链路，由OS创建。 ?共享信箱：由进程创建。 ?发送进程和接受进程的对应关系 操 作 系 统 | 进 程 的 同 步 与 通 信 77 CUIT 徐虹 ?消息缓冲队列通信机制 ?通信原语 Send ( Receiver , message ) ; Receive ( Sender , message ) ; ?消息缓冲区 Type message buffer = record Sender Size Text Next end 操 作 系 统 | 进 程 的 同 步 与 通 信 78 CUIT 徐虹 ?用直接通信原语解决生产者——消费者问题 repeat produce an item in nextp ; Send ( consumer , nextp) ; Until false ; repeat receive ( producer , nextc ) ; consume the item in nextc ; Until false ; 14 操 作 系 统 | 进 程 的 同 步 与 通 信 79 CUIT 徐虹 ?PCB中有关通信的数据项 Type message buffer = record … mq mutex sm … end 操 作 系 统 | 进 程 的 同 步 与 通 信 80 CUIT 徐虹 ?发送原语 procedure send ( receiver , a ) begin getbuf ( a , size , I ) ; i.sender := a.sender ; i.size := a.size ; i.text := a.text ; i.next := 0 ; getid ( PCB set , receiver , j ) ; wait ( j.mutex ); insert ( j.mq.i ) ; signal ( j.mutex ) ; signal (j.sm ) ; end 操 作 系 统 | 进 程 的 同 步 与 通 信 81 CUIT 徐虹 ?接收原语 procedure receive ( b ) begin j := internal name ; wait ( j.sm ); wait ( j.mutex ); remove ( j.mq.i ) ; signal ( j.mutex ) ; b.sender := i.sender ; b.size := i.size ; b.text := i.text ; b.next := 0 ; end