搜索
操作系统教程(第3版)第三章并发进程面向21世纪课程教材高等教育出版社2003年8月第三章并发进程3.1并发进程3.2临界区管理3.3信号量与PV操作3.4管程3.5进程通信3.6死锁3.1并发进程3.1.1顺序程序设计3.1.2进程的并发性3.1.3与时间有关的错误3.1.4进程的交互（InteractionAmongProcesses）：协作和竞争进程的顺序性•一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作•顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间。顺序程序设计特点–程序执行的顺序性–程序环境的封闭性–程序执行结果的确定性–计算过程的可再现性顺序程序设计例子while(1){input，process，output}78输入机处理器磁带机130150228280300378430450时间处理器利用率：52/(78+52+20)≈35%进程的并发性(1)•进程执行的并发性：一组进程的执行在时间上是重叠的•并发性举例：例如：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行•从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态，•从微观上看，任一时刻仅有一个进程在处理器上运行。进程的并发性(2)•并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。无关的并发进程•并发进程分类：无关的，交往的。•无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。•并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。Bernstein条件R(pi)={a1,a2,…an}，程序pi在执行期间引用的变量集W(pi)={b1,b2,…bm}，程序pi在执行期间改变的变量集若两个程序的变量集交集之和为空集：R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}则并发进程的执行与时间无关。Bernstein条件举例例如，有如下四条语句：S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1于是有：R(S1)={x,y},R(S2)={z}，R(S3)={a,b}，R(S4)={c}；W(S1)={a},W(S2)={b}，W(S3)={c}，W(S4)={w}。S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。交往的并发进程(1)•交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。并发程序设计的例子while(1){input，send}while(1){receive，process，send}while(1){receive，output}处理器利用率：（52*n）/（78*n+52+20）=67%78输入机处理器磁带机130150228306208286384364时间并发程序设计特征•并发程序设计是：把一个程序设计成若干个可同时执行的程序模块的方法。•并发程序设计的特征：并发性、共享性、制约性、交互性。并发程序设计的优点•对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。•对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。•简化了程序设计任务。采用并发程序设计的目的•充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。•并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。与时间有关的错误•对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。•与时间有关错误的表现形式：–结果不唯一–永远等待（结果不唯一）机票问题processTi(i=1,2)varXi:integer;begin{按旅客定票要求找到Aj}；Xi:=Aj;ifXi=1thenbeginXi:=Xi-1;Aj:=Xi;{输出一张票}；endelse{输出票已售完}；end;（永远等待）内存管理问题procedureborrow(varB:integer)beginifBxthen{申请进程进入等待队列等主存资源}x:=x-B;{修改主存分配表，申请进程获得主存资源}end;procedurereturn(varB:integer)beginx:=x+B;{修改主存分配表}{释放等主存资源的进程}end;进程的交往：竞争与协作(1)第一种是竞争关系•系统中的多个进程之间彼此无关•系统中的多个进程之间彼此相关资源竞争的两个控制问题：一个是死锁(Deadlock)问题，一个是饥饿(Starvation)问题，既要解决饥饿问题，又要解决死锁问题。进程的交往：竞争与协作(2)进程互斥(MutualExclusion)•解决进程间竞争关系(间接制约关系)的手段。•进程互斥指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直到占有资源的进程释放该资源。进程的交往：竞争与协作(3)第二种是协作关系(1)•某些进程为完成同一任务需要分工协作。•进程的同步是解决进程间协作关系(直接制约关系)的手段。进程的交往：竞争与协作(4)第二种是协作关系(2)•进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。进程的交往：竞争与协作(5)第二种是协作关系(3)•进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。3.2临界区管理3.2.1互斥与临界区3.2.2实现临界区管理的几种尝试3.2.3实现临界区管理的软件方法3.2.4实现临界区管理的硬件设施3.2.1互斥与临界区(1)•并发进程中与共享变量有关的程序段叫“临界区”(CriticalSection)，•共享变量代表的资源叫“临界资源”(CriticalResource)。•与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。•如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。互斥与临界区(2)临界区的调度原则：一次至多允许一个进程进入临界区内一个进程不能无限地停留在临界区内一个进程不能无限地等待进入临界区即--有空让进、无空等待、择一而入、算法可行。临界区管理的尝试(1)•inside1,inside2:Boolean•inside1:=false;/*P1不在其临界区内*/•inside2:=false;/*P2不在其临界区内*/•cobegin•processP1•Begin•whileinside2dobeginend;•inside1:=true;•临界区;•inside1:=false;•end;•processP2•begin•whileinside1dobeginend;•inside2=true;•临界区;•inside2:=false;•end;•coend临界区管理的尝试(2)•inside1,inside2:boolean;•inside1:=false;/*P1不在其临界区内*/•inside2:=false;/*P2不在其临界区内*/•cobegin•processP1•begin•inside1:=true;•whileinside2dobeginend;•临界区;•inside1:=false;•end;•processP2•begin•inside2:=true;•whileinside1dobeginend;•临界区;•inside2:=false;•end;coendDekker算法(1)Dekker算法用一个指示器turn来指示应该哪一个进程进入临界区。•varinside:array[1..2]ofboolean;•turn:integer;•turn:=1or2;•inside[1]:=false;•inside[2]:=false;•cobegin•processP1•begin•inside[1]:=true;•whileinside[2]doifturn=2then•begin•inside[1]:=false;•whileturn=2dobeginend;•inside[1]:=true;•end•临界区;•turn=2；•inside[1]:=false;•end;Dekker算法(2)Dekker算法(3)processP2•begin•inside[2]:=true;•whileinside[1]doifturn=1then•begin•inside[2]:=false;•whileturn=1dobeginend;•inside[2]:=true;•end•临界区;•turn=1；•inside[2]:=false;•end;•coendPeterson算法(1)•varinside:array[1..2]ofboolean;•turn:integer;•turn:=1or2;•inside[1]:=false;/*P1不在其临界区内*/•inside[2]:=false;/*P2不在其临界区内*/Peterson算法(2)•cobegin•processP1•begin•inside[1]:=true;•turn:=2;•while(inside[2]andturn=2)•dobeginend;•临界区;•inside[1]:=false;•end;Peterson算法(3)•processP2•begin•inside[2]:=true;•turn:=1;•while(inside[1]andturn=1)•dobeginend;•临界区;•inside[2]:=false;•end;•coend实现临界区管理的硬件设施•关中断•测试并建立指令•对换指令关中断•实现互斥的最简单方法•关中断方法的缺点测试并建立指令(1)TS指令的处理过程TS(x):若x=true，则x:=false；returntrue；否则returnfalse；TS指令管理临界区时，可把一个临区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。测试并建立指令(2)s:boolean;s:=true;processPi/*i=1,2,…,n*/pi:boolean;beginrepeatpi:=TS(s)untilpi；临界区;s:=true；end;对换指令(1)对换（Swap）指令的功能是交换两个字的内容：Swap(a,b):temp:=a;a:=b;b:=temp;对换指令(2)lock:boolean;lock:=false;processPi/*i=1,2,…,n*/pi:boolean;beginpi:=true;repeatswap(lock,pi)untilpi=false；临界区;lock:=false；end;3.3信号量与PV操作3.3.1同步与同步机制3.3.2记录型信号量与PV操作3.3.3用记录型信号量实现互斥3.3.4记录型信号量解决生产者-消费者问题3.3.5记录型信号量解决读者-写者问题3.3.6记录型信号量解决理发师问题3.3.1同步和同步机制•著名的生产者--消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。•在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。•解决好生产者--消费者问题就解决好了一类并发进程的同步问题。生产者--消费者问题表述有界缓冲问题•有