《第4章进程同步与死锁课件.ppt》由会员分享，可在线阅读，更多相关《第4章进程同步与死锁课件.ppt（46页珍藏版）》请在三一办公上搜索。
1、第四章 进程同步与死锁,本章主要讲述以下几方面的内容：(1) 进程同步和互斥，临界资源及临界区的基本概念(2) 实现进程互斥的方法(3) 信号量机制与P、V操作(4) 一些经典的进程同步问题(5) 利用管程实现进程同步(6) 进程的死锁及处理机制(7) Linux系统的进程同步及死锁,4.1 进程同步的基本概念,4.1.1 并发性4.1.2 与时间有关的错误4.1.3 进程的同步与互斥4.1.4 临界资源和临界区,4.1.1 并发性,所谓并发性是指一组进程执行在时间点上相互交替，在时间段上相互重叠。,4.1.2 与时间有关的错误,在多进程并发的情况下，进程共享某些变量或硬件资源，由于进程的执行
2、具有不确定性，如果不对进程的执行加以制约其执行结果往往是错误的。例4-1 假设有两个并发进程P1及P2。P1 P2 S1：X=1S4：X=2 S2：X=X+1 S5：X=X*2 S3：A=XS6：B=X进程P1与P2共享变量X，变量A与B分别为进程P1及P2的私有变量。共享变量X的初值为0由此可见，相同的程序由于指令的交错执行，导致最终的结果也不尽相同。这就要求使用进程同步及互斥机制，实现对共享资源的互斥访问，保证程序执行的正确性。,4.1.3 进程的同步与互斥,1.进程的同步所谓进程同步是指，当进程运行到某一点时，若其他进程已完成了某种操作，使进程满足了继续运行的条件，进程才能够继续运行，否
3、则必须停下来等待。通常将进程等待的那一点称为“同步点”而将等待运行的条件称为“同步条件”。2.进程的互斥对系统中的某些进程来说，为保证程序的正确执行，必须相互协调共享资源的使用顺序。通常共享资源可分为互斥共享资源及可同时访问共享资源两类。互斥共享资源是指在某段时间内，只能有一个进程对该资源进行访问，其他进程若想访问该资源则必须停下来等待，直到该共享资源被前一进程释放。可同时访问共享资源是指在某段时间内，可以有多个进程同时对该资源进行访问,4.1.4 临界资源和临界区,1. 临界资源进程在运行过程中，可能会与其它进程共享资源，而对互斥共享资源的访问需要具有排他性。2. 临界区 将程序中对临界资源
4、访问的代码部分称为临界区。图4-2所示为访问临界资源的程序的一般结构。,3临界区访问准则无论使用何种方法解决进程同步问题，对临界区的访问应该遵循如下原则，违背任何一条，都将导致进程同步的错误。(1) 空闲让进：当没有进程处于临界区，临界资源处于空闲状态时，立即可以允许一个进程进入临界区。(2) 忙则等待：任何时候，处于临界区内的进程不可多于一个。当已有进程在临界区，其它欲进入的进程必须等待。(3) 有限等待：进入临界区的进程要在有限时间内完成并退出临界区，以便让其它进程有机会记入临界区。(4) 让权等待：如果进程不能进入自己的临界区，则应该停止运行，让出处理器，避免进程出现“忙等”现象。,4.
5、2 互斥实现方法,4.2.1 硬件方法4.2.2 软件方法,4.2.1 硬件方法,采用硬件方法实现互斥的主要思想就是用一条指令来完成标志的检查和修改两个操作，从而保证检查操作与修改操作不被打断；或者通过禁止中断的方式来保证检查和修改作为一个整体来执行。1 禁止中断,2 专用机器指令（1）TS(Test-and-Set)指令TS指令的功能是检查指定标志后把该标志设置位，可以将TS指令看作一个不可中断的函数，该函数以一个测试标志为参数。当测试标志置位时函数返回0，表示资源被占用，否则函数返回1，表示资源可被占用，同时将测试标志置位。（2）Swap指令Swap对换指令的功能是交换两个字节的内容使用硬
6、件方法管理临界区主要有以下优点：适用范围广：可用于多个并发进程及单处理器或多处理器环境。方法简单：只需要硬件指令即可实现。支持多个临界区：可为每个临界区设置单独的标志，在支持的临界区的个数上没有限制。但是，硬件方法也存在着一些比较明显的缺点：忙等待：从TS指令与Swap指令可以看出，在进程无法进入临界区时会对标志进行循环测试，从而耗费大量处理器资源。进程饥饿现象：在某进程释放临界资源后，下一个进入临界区的进程是不确定的，从而可能会产生有的进程长期无法进入临界区的情况。,4.2.2 软件方法,算法1：利用共享的标志位来表示哪个并发进程可以进入临界区。对并发进程A与B，设置标志变量turn。若变量
7、turn为0则允许进程A进入临界区访问，若变量turn为1则允许进程B进入临界区访问。算法实现代码如下。int turn=0;进程A:while(turn!=0);临界区；turn=1;,进程B：while(turn!=1);临界区；turn=0；,算法2：利用双标志法判断进程是否进入临界区。这种算法通过使用一个flag数组来表示进程是否希望进入临界区。对两个并发进程A与B，若flag0=1则表示进程A期望进入临界区，若flag1=1则表示进程B期望进入临界区。进程A与B在真正进入临界区之前先查看一下对方的flag标志，如果对方正在进入临界区则将进行等待。另外，为了避免并发执行时的错误还需要通
8、过一个变量turn来避免两个进程都无法进入临界区。算法实现代码如下。int flag2=0,0;进程A：flag0=1;turn=1;while(flag1,进程B:flag1=1;turn=0;while(flag0,4.3 信号量,4.3.1整型信号量机制4.3.2记录型信号量机制4.3.3 AND型信号量机制,4.3 信号量,从概念上将信号量类似于交通管理中的信号灯，通过信号量的状态来决定并发进程对临界资源的访问顺序。信号量可以在多进程间传递简单的信号，使一个进程可以在某位置阻塞，直到接收到特定信号后继续运行，从而达到多进程相互协作的目的。在信号量同步机制中包含“检测”与“归还”两个操作
9、。检测操作称为P操作，用来发出检测信号量的操作，查看是否可访问临界资源，若检测通过，则开始访问临界资源，若检测不通过，则进行等待，直到临界资源被归还后才能进入临界区访问。归还操作称为V操作，用来通知等待进程临界资源已经被释放。P操作与V操作都是原子操作，其中的每个步骤是不可分割的。,4.3.1整型信号量机制,整型信号量是最简单的一种信号量，它通常是一个需要初始化值的正整型量。对整型信号量x，定义P操作及V操作原语如下。P操作：P(x)while(x=0);x=x-1;V操作：V(x)x=x+1;,4.3.2记录型信号量机制,由于整型信号量在P操作不成功时需要进行循环等待，而这种等待没有放弃CP
10、U资源，违背了让权等待的原则，造成了系统资源的浪费。记录型信号量在整型信号量的基础上进行了改进，它除包含一个整型值Value外还包含一个阻塞队列queue。对记录型信号量x，定义P操作及V操作原语如下：P操作：P(x)x.value=x.value-1;if(x.value0)block(x.queue);其中block函数将使进程阻塞，并挂入queue等待队列让出处理器资源，wakup函数则负责从queue队列中唤醒一个等待的进程，而使其继续执行。,V操作：V(x)x.value=x.value+1;if(x.value=0)wakeup(x.queue);,4.3.3 AND型信号量机制,
11、在并发进程访问多个临界资源时，需要多次使用P、V操作，很容易由于操作位置放置不当而造成进程死锁。解决死锁问题的一种方法是使用AND型信号量，与整型与记录型信号量不同，AND型信号量对进程所需的多个临界资源进行批量获取和批量释放。对信号量x1、x2、xn定义AND型信号量集如下：AND型信号量要将多个临界资源一次性全部分配给所需的进程，当其中任一个临界资源未获得时进程都将等待，从而避免了获取多个临界资源可能导致进程死锁的问题。,SP(x1,x2,xn) if(x1=0,4.4 经典的进程同步问题,4.4.1 生产者-消费者问题4.4.2 读者-写者问题4.4.3 哲学家进餐问题4.4.4 打瞌睡
12、的理发师问题,4.4.1 生产者-消费者问题,生产者与消费者进程应满足如下同步条件：任一时刻所有生产者存放产品的单元数不能超过缓冲池的总容量N。所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。它们之间应具有的同步关系有：当缓冲池满时生产者进程需等待。当缓冲池空时消费者进程需等待。各个进程应互斥使用缓冲池。设置如下三个信号量： full：表示放有产品的缓冲区数，初值为0。empty：表示可供使用的缓冲区数，初值为N。mutex：互斥信号量，初值为1，使各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。,4.4.2 读者-写者问题,读者-写者问题可根据写者到来后是否仍允许新读
13、者进入而分为两类：读者优先：当写者提出存取共享对象的要求后，仍允许新读者进入。写者优先：当写者提出存取共享对象的要求后，不允许新读者进入。下面利用信号量来解决读者优先的读者-写者问题。这里需要设置两个信号量和一个共享变量：读互斥信号量rmutex，用于使读进程互斥访问共享变量readcount，其初值为1;读写互斥信号量mutex，用于实现写进程与读进程的互斥以及写进程与写进程的互斥，其初值为1;读共享变量readcount，用于记录当前的读进程数目，初值为0。,4.4.3 哲学家进餐问题,为哲学家设定三种状态：THINKING：思考状态，处于该状态的哲学家正在思考。HUNGRY：饥饿状态，处
14、于该状态的哲学家已经停止思考，正在试图取得身边的两只筷子。EATING：就餐状态，处于该状态的哲学家取得了身边的两只筷子，正在就餐。,设定哲学家的编号依次为0到4，用数组State来表明哲学家所处的状态，例如若State3=EATING，那么就表明3号哲学家处于就餐状态。为了方便获得某哲学家左右两边哲学家的编号，定义如下两个宏：#define LEFT(x) (x-1)%5#define RIGHT(x) (x+1)%5定义一个信号量数组s，对应每个哲学家，初值为0，用来在得不到筷子是阻塞哲学家。为保证各哲学家状态的变更和测试能够互斥的进行，定义信号量mutex，初值为1。,4.4.4 打瞌睡
15、的理发师问题,设置变量waiting表示等待理发的顾客的数量，初值为0。定义三个信号量：customers：正在等待的顾客的数量，数值上与waiting相同，初值为0。barbers：理发师的状态，初值为1。mutex：用于互斥访问变量waiting，初值为1。,4.5 管程,利用信号量机制实现进程同步问题时，需要设置很多信号量，并且对于共享资源的管理分散在各个进程之中，因此，难以防止无意的违反同步操作，造成程序设计的错误或出现死锁。,4.5.1 使用信号的管程,为了解决这类问题，Brinch Hansen和Hoare提出一种高级同步机制管程(Monitor)。 利用数据抽象地表示系统中的共享
16、资源，而把对该数据实施的操作定义为一组过程。代表共享资源的数据，以及由对该共享数据实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块。,4.5.1 使用信号的管程,管程由四部分组成： 管程的名称； 局部于管程的数据的说明； 对数据进行操作的一组过程； 对局部于管程内部的共享数据赋初值的语句。,4.5.1 使用信号的管程,尽管管程提供了一种实现互斥的简便途径，但这还不够。还需要一种办法使得进程在无法继续运行时被阻塞。例如，在生产者-消费者问题中，很容易将针对缓冲区是满或是空的测试放到管程过程中，但是生产者在发现缓冲区满的时候如何阻塞呢？解决的方法是引入条件变量以及相关的
17、两个操作原语：wait和signal。当一个管程过程发现它无法继续运行时（例如，生产者发现缓冲区满），它会在某个条件变量上（如full）执行wait操作。该操作导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程，,4.5.1 使用信号的管程,管程自动实现对临界区的互斥，因而用它进行并行程序设计比信号量更容易保证程序的正确性。但它也有缺点。由于管程是一个程序设计语言的概念，编译器必须要识别管程并用某种方式实现互斥。然而，C，Pascal和Java及多数编程语言都不支持管程。所以指望这些编译器遵守互斥规则是不可靠的。实际上，如何能让编译器知道哪些过程属于管程，哪些不属于管程，也是个
18、问题。,4.5.2 使用通知和广播的管程,上述管程的定义要求在条件队列中知道有一个进程，当另一个进程为该条件产生signal时，该队列中一个进程立即运行。因此，产生signal的进程必须立即退出管程，或者挂起在管程上。这种方法有两个缺点：1 如果产生signal的进程在管程内还没有结束，则需要做两次切换：挂起进程切换，当管程可用是恢复该进程又切换一次。2 与信号相关的进程调度必须非常可靠。当产入一个signal时，来自相应条件队列中的个进程必须立即被激活，调度程序必须确保在激活前没有别的进程进入管程，否则，进程被激活的条件又会改变。,两个进程分别准备打印一个非常大的磁带文件。进程A申请打印机，
19、并得到授权。进程B申请磁带机，也得到授权。现在，A申请磁带机，但该请求在B释放磁带机前会被拒绝。然而，B非但不放弃磁带机，反而去申请打印机，而A在申请到磁带机之前也不会释放打印机。这时，两个进程都被阻塞，并且保持下去，这种状况就是死锁（deadlock）。,4.6 死锁,4.6.1 死锁的概念,所谓死锁，就是多个进程循环等待它方占有的独占性资源而无限期的僵持下去的局面。显然，如果没有外力的作用，那么死锁涉及到的各个进程都将永远处于阻塞状态。,4.6.1 死锁的概念,当一个计算机系统同时具备下面4个必要条件时，就会发生死锁：互斥条件：每个资源每次只能分配给一个进程使用，某个进程一旦获得资源，就不
20、准其它进程使用，直到它释放为止。这种独占性资源有打印机、CD-ROM驱动器、平板式绘图仪等。部分分配（占有且等待）条件：进程由于申请不到所需要的资源而等待时，仍然占据着已经分配到的资源。也就是说，进程并不是一次性地得到所需要的所有资源，而是得到一部分资源后，还允许继续申请新的资源。不可抢占（非剥夺）条件：任一个进程不能从另一个进程那里抢占资源，即已被占有的资源，只能由占用进程自己来释放。循环等待条件：存在一个循环的等待序列P1，P2，P3，Pn，其中，P1等待P2所占有的某个资源，P2等待P3所占有的某个资源，而Pn等待P1所占有的某个资源，从而形成一个进程循环等待环。,4.6.2 死锁的处理
21、策略,预防死锁：通过破坏上面提及的四个必要条件之一，可以使系统不具备产生死锁的条件。避免死锁：在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁，则拒绝分配，否则接受申请，为它分配资源。检测思索并恢复：允许系统出现死锁，在死锁发生后，通过一定方法加以恢复，并尽可能地减少损失。忽略死锁：任凭死锁的出现。当系统中出现死锁时，就将系统重新启动。采用这种对策，主要看出现死锁的概率有多大，花费极大的精力去解决系统的死锁问题是否值得。UNIX系统采用这种对策，因为它认为在其系统里，出现死锁的各种可能性都极小。,4.6.3 死锁的预防与避免,破坏互斥条件破坏部分分配（占有且等待）条件破坏不可
22、抢占（非剥夺）条件破坏循环等待条件,4.6.3 死锁的预防与避免,Dijkstra于1965年提出了一个经典的避免死锁的算法银行家算法（bankers algorithm）。 银行家算法从避免死锁的角度上说是非常有效的。但是从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。因此，在实际中，也只有极少的系统使用银行家算法来避免死锁。,4.6.4 死锁的检测与恢复,对资源的分配加以限制可以预防和避免死锁的发生，但这不利于各进程对系统资源的充
23、分共享。解决死锁问题的另一个途径是死锁检测方法，这种方法对资源的分配不加以限制，系统周期性的运行一个“死锁检测”程序，判断系统内是否存在死锁，若检测到，则设法加以解除。死锁检测的频率取决于发生死锁的可能性。在每个进程申请资源时检测可以使算法相对比较简单，并且能尽早发现死锁。但这种频繁的检测会消耗相当多的系统资源。,4.6.4 死锁的检测与恢复,当系统检测到死锁后，需要采用某种措施使系统从死锁中解脱出来。下面列出可能的方法：1 最简单的办法是结束所有进程的执行，并重新启动操作系统；2 结束所有卷入死锁的进程的执行；3 一次结束卷入死锁的一个进程的执行，然后在每次结束后再调用检测程序，直到死锁消失；4 重新启动卷入死锁的进程，希望死锁不再出现；5 从一个或多个卷入死锁的进程中抢占资源，再把这些资源分配给卷入死锁的其余进程之一，然后恢复执行；6 周期性地把各个进程的执行情况记录下来，一旦检测到死锁发生，就可以按照这些记录的文件进行回退，让损失减到最小。,4.6.4 死锁的检测与恢复,对于3和5，选择进程的原则如下：（1）优先级（2）进程已经执行时间，预计剩下的时间（3）进程使用的资源总量（4）进程执行完还需要资源（5）进程是交互式还是批处理的,
