《操作系统-并发进程》由会员分享，可在线阅读，更多相关《操作系统-并发进程（147页珍藏版）》请在金锄头文库上搜索。
1、2018/9/16,1,第四章 并发进程,4.1 并发进程 4.2 临界区管理 4.3 信号量与P、V操作 4.4 进程间的通信 4.5 死锁 4.6 管程,2018/9/16,2,第四章 并发进程,4.1 并发进程 4.2 临界区管理 4.3 信号量与P、V操作 4.4 进程间的通信 4.5 死锁 4.6 管程,2018/9/16,3,4.1 并发进程,1）顺序程序顺序程序：指令或语句序列，体现了某种算法，所有程序是顺序的 顺序环境：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响,1、顺序程序与并发进程,2018/9/16,4,4.1 并发进程,2）顺序程序
2、的特征顺序性执行封闭性，独占资源确定性，即可再现性,1、顺序程序与并发进程,2018/9/16,5,4.1 并发进程,3）并发进程并发环境：在一定时间内物理机器上有两个或两个以上的程序 同处于开始运行但尚未结束的状态，并且次序不是事先确定的。,1、顺序程序与并发进程,2018/9/16,6,4.1 并发进程,4）并发进程的特征,1、顺序程序与并发进程,间断性执行，执行-停-执行 资源共享，多个进程共享使用系统资源 不可再现性，执行结果不确定 独立性和制约性 程序和进程不再一一对应,2018/9/16,7,4.1 并发进程,2、与时间有关的错误,例1）并发进程交替使用共享资源时可能出现的错误：
3、例如：P1和P2是两个并发进程 P1: R1=C; R1=R1+1; C=R1; P2: R2=C; R2=R2+1; C=R2; P1全部执行完毕后再执行P2，则C增加2 若P2中的在P1中的之前执行，则C增加1 原因是没有正确地控制对共享变量C的访问,2018/9/16,8,4.1 并发进程,2、与时间有关的错误,例2）飞机订票问题： P1和P2是两个并发的终端订票进程，x=10 P1: Read(x); if x=1 then x:=x-1; write(x); P2: Read(x); if x=1 then x:=x-1; write(x); P1全部执行完毕后再执行P2，则x=8
4、若P2中的在P1中的之前执行，则x=9 出现了1张票卖给2个客户的情况，原因是没有正确地 控制对共享变量x的访问,2018/9/16,9,4.1 并发进程,2、与时间有关的错误,例3）缓冲区读写问题：get、copy、put是3个并发进程,2018/9/16,10,4.1 并发进程,2、与时间有关的错误,例4）进程间的“输赢游戏”,进 程 A 进 程 B,进程A和进程B谁会赢？,2018/9/16,11,4.1 并发进程,3、进程间的联系,1）间接式与直接式制约： 直接式制约：一程序段等待另一程序段的执行结果 间接式制约：并发程序段竞争同一资源 2）相交进程与无关进程： 相交进程：并发进程在逻
5、辑上有某种联系 无关进程：逻辑上无任何联系的并发进程 直接作用只发生在相交进程之间；间接作用可以发生在相交进程之间，也可发生在无关进程之间,2018/9/16,12,4.1 并发进程,3、进程间的联系,3）进程的同步与互斥 进程同步（直接作用）：根据一定的时序关系合作完成一项任务 并发进程因直接制约而互相等待，彼此相互发送消息进行合作，使得各进程按一定的速度执行 进程互斥（间接作用）：各进程竞争使用临界资源 临界资源：一次只允许一个进程使用的系统资源 进程互斥是进程同步的一种特殊情况,2018/9/16,13,第四章 并发进程,4.1 并发进程 4.2 临界区管理 4.3 信号量与P、V操作
6、4.4 进程间的通信 4.5 死锁 4.6 管程,2018/9/16,14,第四章 并发进程,4.1 并发进程 4.2 临界区管理 4.3 信号量与P、V操作 4.4 进程间的通信 4.5 死锁 4.6 管程,2018/9/16,15,4.2 临界区管理,可怜的金鱼,如果每个人独立行动，则金鱼必死无疑。但如果他们都具备观察金鱼是否已经进食过的能力，金鱼还会死么？,原因缺少进程间的通信，导致对临界区管理的失效！,2018/9/16,16,4.2 临界区管理,1、临界区及其使用原则,临界区：进程中涉及临近资源的程序段为临界区/互斥区，多个进程的临界区为相关临界区 临界区的使用原则： 有空让进 无空
7、等待 多中择一 有限等待 让权等待 解决进程互斥的两种做法： 由竞争各方平等协商解决，包括硬件、软件两类方法。 引入进程管理者来协调竞争各方对互斥资源的使用,2018/9/16,17,4.2 临界区管理,2、实现临界区管理的软件方法,bool inside1=false; bool inside2=false; cobegin process P1 process P2while(inside2) do while(inside1) dobegin end; begin end;inside1:=true; inside2 :=true;临界区； 临界区;inside1=false; insi
8、de2=false; coend,1）几个失败的尝试 （1）,2018/9/16,18,4.2 临界区管理,2、实现临界区管理的软件方法,1）几个失败的尝试 （2）“可怜的金鱼”解决方案？,通过“留字条”，能否防止两个进程同时进入临界区？,2018/9/16,19,4.2 临界区管理,2、实现临界区管理的软件方法,1）几个失败的尝试 （3）,bool inside1:=false; bool inside2:=false; cobegin process P1 process P2 begin begininside1:=true; inside2=true;while(inside2) do
9、 while(inside1) dobegin end; begin end;临界区； 临界区;inside1:=false; inside2:=false; end end coend,2018/9/16,20,4.2 临界区管理,2、实现临界区管理的软件方法,1）几个失败的尝试 （4）“可怜的金鱼”解决方案？,通过先“留字条”后“查看字条”（即改进的“留字条”方法），能否防止两个进程同时进入临界区？,2018/9/16,21,4.2 临界区管理,2、实现临界区管理的软件方法,2）成功的解决方案,var inside: array12 of Boolean; inside1=false; i
10、nside2=false; turn: integer; turn:=1 or 2; cobegin process P1 begininside1:=true;while inside2 do if turn=2 thenbegininside1:=false;while turn=2 do begin end;inside1:=true;end临界区;turn := 2；inside1:=false; end; coend,process P2 begininside2:=true;while inside1 do if turn=1 then begininside2:=false;wh
11、ile turn=1 do begin end;inside2:=true;end临界区;turn := 1；inside2:=false; end;,2018/9/16,22,var inside: array12 of Boolean; inside1=false; inside2=false; turn: integer; turn:=1 or 2; cobegin process P1 begininside1:=true;while inside2 do if turn=2 thenbegininside1:=false;while turn=2 do begin end;insid
12、e1:=true;end临界区;turn := 2；inside1:=false; end; coend,process P2 begininside2:=true;while inside1 do if turn=1 then begininside2:=false;while turn=1 do begin end;inside2:=true;end临界区;turn := 1；inside2:=false; end;,2018/9/16,23,4.2 临界区管理,3、实现临界区管理的硬件方法,通过专门提供的硬件指令管理临界区 1）测试并建立指令TSs代表临界资源状态，由TS指令控制s: b
13、oolean; s := true;process Pi /* i = 1,2,n */pi : boolean;beginrepeat pi := TS(s) until pi；临界区;s := true；end;,2018/9/16,24,4.2 临界区管理,3、实现临界区管理的硬件方法,2）交换指令SWAP交换指令将交换两个字的内容。公共变量lock表临界区是否上锁，每个进程的私有变量key用于与lock交换。 void SWAP ( int *a, int *b ) int temp; temp = *a;*a = *b;*b = temp; ,key = true;do SWAP(,
14、2018/9/16,25,4.2 临界区管理,3、实现临界区管理的硬件方法,3）开关中断指令进入临界区前执行“关中断”指令；离开临界区后，执行“开中断”指令，从而控制进程互斥进入临界区硬件方法解决临界区的管理较为简单有效，其缺点主要在于 会导致“忙等待” 会导致“饥饿” 中断屏蔽方法代价较高，不适应多处理器,2018/9/16,26,第四章 并发进程,4.1 并发进程 4.2 临界区管理 4.3 信号量与P、V操作 4.4 进程间的通信 4.5 死锁 4.6 管程,2018/9/16,27,第四章 并发进程,4.1 并发进程 4.2 临界区管理 4.3 信号量与P、V操作 4.4 进程间的通信
15、 4.5 死锁 4.6 管程,2018/9/16,28,4.3 信号量与P、V操作,1、信号量的定义,1）信号量的提出1965年荷兰学者Dijkstra提出信号量（semaphore）与P、V操作机制，这一机制是系统用于管理公有资源的有效手段。 信号量是一个数据结构，负责协调各个进程，以保证它们能够正确、合理的使用公共资源,2018/9/16,29,4.3 信号量与P、V操作,1、信号量的定义,2）信号量定义 Struct semaphore int value; /信号量的值pointer PCBqueue; /信号量队列指针 信号量说明：semaphore s,2018/9/16,30,4.3 信号量与P、V操作,1、信号量的定义,3）信号量的特性,
