《操作系统原理与实践教程 教学课件 ppt 作者 7-302-13410-3j czxt04》由会员分享，可在线阅读，更多相关《操作系统原理与实践教程 教学课件 ppt 作者 7-302-13410-3j czxt04（99页珍藏版）》请在金锄头文库上搜索。
1、第 4 章 进程的同步和死锁,4.1 进程的同步和互斥,4.1.1 进程的同步 1.进程同步举例 例.公共汽车中的司机和售票员。,司机 P1 售票员 P2 while (true) while (true) 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； ,4.1 进程的同步和互斥,2.进程同步的概念 进程的同步是指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。 通常，把共同完成一个任务的若干进程称为合作进程。合作进程在并发执行
2、时必须同步推进才能得到正确的执行结果。,4.1 进程的同步和互斥,4.1.2 进程互斥 1.进程互斥举例 假定系统中只有一台打印机，进程p1，p2都需要使用打印机，如果让它们同时使用，则两个进程的输出交织在一起，打印出的结果无法使用。 为了解决这一问题，进程使用之前先要提出申请，一旦系统将打印机分配给它，就一直由它独占使用，其它申请使用打印机的进程则必须等待。 进程p1和p2在逻辑上完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。这种进程之间的间接制约关系不具有时间次序的特征，谁先向系统提出申请，谁就先执行。这种对共享资源的排他性的使用关系就是进程的互斥关系。,4.1 进程的同步和互
3、斥,2.临界资源 在计算机的资源中，有些资源，如上面提到的打印机资源，一次能被一个进程使用，这类资源称为临界资源（Critical Resource）。 临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。它们虽然可以被若干个进程所共享，但一次能为一个进程所利用。 为了保证共享临界资源的各个进程能正确运行，当临界资源由一个进程占用后，其它进程如果要使用它，必须等待占用进程使用完毕并把它释放后，才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。,4.1 进程的同步和互斥,3.临界区的概念 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（
4、共享资源）进行操作。在进程中涉及到临界资源的程序段叫临界区或临界段。 对临界区操作的诸进程必须互斥地进入临界区。,4.1 进程的同步和互斥,临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不相交，所以不必互斥地执行，而相对于同一临界资源的若干个临界区，则必须互斥的进入，即对临界资源的操作必须互斥地执行。 例如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。,4.1 进程的同步和互斥,临界区进入准则： 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进
5、入临界区的进程立即进入自己的临界区。 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待。 有限等待。对任何要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死等”状态。 让权等待。当进程不能进入自己的临界区，应立即放弃占用CPU，以使其他进程有机会得到CPU的使用权，以免陷入“忙等”。,4.1 进程的同步和互斥,4.进程同步和互斥的区别 互斥的各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。 而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只要当它们互相配合、共同协
6、调推进时才能得到正确的运行结果。 互斥的进程只要求它们不能同时进入临界区，而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。 一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。,4.1 进程的同步和互斥,4.1.3 信号量机制 信号量（Semaphore）机制是荷兰学者E.W.Dijkstra在1965年提出的一种解决进程同步、互斥问题的更通用工具，并在THE操作系统中得到实现。 信号量S是个整数变量，除了初始化外，它只能通过两个标准的
7、原子操作wait和signal来访问。这两个操作原来被称为P(用于wait，表测试)和V(用于signal，表增加)操作。,4.1 进程的同步和互斥,wait的经典定义可用伪代码表示为： wait(s) while (s=0) ； / no.op s - - . .; signal的经典定义可用伪代码表示为： signal (s) s + +； ,4.1 进程的同步和互斥,1.信号量的使用 可使用信号量来解决n个进程的临界区问题。这n个进程共享一个信号量mutex,并初始化为1。每个进程Pi的组织结构如下：,wait(mutex） 临界区（CS) signal(mutex),4.1 进程的同步
8、和互斥,也可以使用信号量来解决各种同步问题。例如，考虑两个正在执行的并发进程：p1有语句s1，而p2有语句s2。假设要求只有在s1执行完之后才执行s2，可以很容易地实现这一要求：让p1和p2共享一个共同信号量synch，且初始化为0。 在进程p1中插入语句： s1; signal (synch); 在进程p2中插入语句： wait(synch); s2;,4.1 进程的同步和互斥,2.信号量的实现 上面定义的信号量虽然能够用来解决进程的同步和互斥问题，但存在一个明显的缺陷，即该机制没有遵循“让权等待”的原则，而是使进程处于“忙等”状态。 为了克服这个缺点，可定义一个结构体信号量： typede
9、f struct int value; struct process *L; /进程链表 semaphore;,4.1 进程的同步和互斥,信号量操作wait现在可按如下来定义： void wait (semaphore S) S.value - -; if (S.value 0) add this process to S.L; block(); 信号量操作signal现在可按如下来定义： void signal (semaphore S) S.value + +; if (S.value = 0) remove a process P from S.L; wakeup(P); ,4.1 进程
10、的同步和互斥,信号量的说明： 在信号量的实现中，S.value的初值表示系统某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源。 当S.value0时，表示该类资源已分配完毕，因而进程调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。此时，S.value的绝对值表示在该信号量链表中已阻塞进程的个数、亦即恰好等于对信号量S实施wait操作而被封锁起来并进入信号量S队列的进程数。 对信号量的每次signal操作，表示执行进程释放一个单位资源。,4.1 进程的同步和互斥,3. AND型信号量 (1)问题的引入 假定有两个进程A和B，
11、它们都要求访问共享数据D和E。当然，共享数据都应作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即 process A: process B: wait (Dmutex); wait(Emutex); wait (Emutex); wait(Dmutex); 若进程A和B按下述次序交替执行wait操作： process A: wait(Dmutex);于是Dmutex=0 process B: wait(Emutex);于是Emutex=0 process A: wa
12、it(Emutex);于是Emutex=-1,A阻塞 process B: wait(Dmutex);于是Dmutex=-1,B阻塞,4.1 进程的同步和互斥,(2)AND型信号量的基本思想 上述例子出现死锁的原因主要在于进程运行时需要多个资源，在为每个进程分配所需的全部资源时，不能保证原子操作，从而导致进程之间相互等待对方释放所占资源的死锁状态。为了解决进程同时需要多种资源且每种资源要占用一段时间的问题，人们提出了AND型信号量同步机制。 AND型信号量的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有
13、可能为之分配的资源，也不分配给它。亦即，对若干个临界资源的分配，采取了原子操作方式：要么全部分配给进程，要么一个也不分配。,4.1 进程的同步和互斥,AND型信号量wait原语为Swait,其定义如下： Swait(S1, S2, , Sn) if(S1 =1 ,4.1 进程的同步和互斥,AND型信号量集signal原语为Ssignal, 其定义如下： Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si; /释放占用的资源； for (在Si.queue中等待的每一个进程P) 从等待队列Si.queue中取出进程P; if(判断进程P是否通过Swa
14、it中的测试) /重新判断 进程P进入就绪队列; break； else 进程P进入某等待队列； ,4.1 进程的同步和互斥,引入AND信号量后，上面的例子就可以简单改写为： process A: process B: Swait(Dmutex,Emutex); Swait(Emutex,Dmetux); Ssignal(Dmutex,Emutex); Ssignal(Emutex,Dmutex); 这样也就不会出现死锁问题。,4.1 进程的同步和互斥,4. 信号量的应用 利用信号量可以很好的解决进程之间的同步问题。一般同步问题可分为两类：一类是保证一组合作进程按逻辑需要所确定的次序执行；另一
15、类是保证共享缓冲区（或共享数据）的合作进程的同步。 （1）合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行，然而，这些并发进程之间根据逻辑上的需要，有的操作可以没有时间上的先后次序，即不论谁先做，最后的计算结果都是正确的。但有的操作有一定的先后次序，也就是说它们必须遵循一定的同步规则，只有这样，并发执行的最后结果才是正确的。,4.1 进程的同步和互斥,为了描述方便，可以用一个图来表示进程集合的执行次序。图的连接描述了进程开始和结束的次序约束。此图称为进程流图。如果用s表示系统中某一任务启动，f表示完成，则可以下列的进程流图来表示这一组合作进程执行的先后顺序。,4.1 进程的同步和互斥,例题：假设某个程序段包含如下语句： int a,b,c,d,e,f; int t1,t2,t3,t4,t5; t1=a+b; t2=c+d; t3=e/f; t4=t1*t2; t5=t4-t3;,4.1 进程的同步和互斥,例题4-1：进程pa,pb,pc为一组合作进程，其进程流图如右图所示，使用信号量机制来实现这三个进程的同步。,分析： 从图可以看出，进程pb、pc只有在进程pa执行完成以后才能执行，进程pb、pc可以并发执行。 为确保这三个进程的执行顺序，设两个同步信号量SB、SC分别表示进程pb
