操作系统概论第6章_并发管理

1、第6章 并发管理操作系统概论操作系统概论主要内容6.1进程的并发性进程的并发性 6.2与时间有关的错误与时间有关的错误 6.3临界区与临界区与PV操作操作 6.4进程的互斥与同步进程的互斥与同步 6.5进程通信进程通信 6.6死锁死锁 重点：分析与时间有关的错误；用PV操作实现进程的互斥与同步；解决死锁问题的方法6.1 6.1 程序的顺序执行与并发执行程序的顺序执行与并发执行 一一. 程序的顺序执行与特征程序的顺序执行与特征 1. 什么是程序的顺序执行什么是程序的顺序执行 一个程序由若干个程序段组成，而这些程序段的执一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式

2、就称为程序的顺行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。序执行。 例如：例如： 2. 顺序程序的特征顺序程序的特征 （1）顺序性：处理机的操作严格按照程序规定的顺）顺序性：处理机的操作严格按照程序规定的顺序执行，即只有前一操作结束后，才能启动后一操序执行，即只有前一操作结束后，才能启动后一操作的执行作的执行 （2）封闭性：程序在封闭的环境下运行，并独占全）封闭性：程序在封闭的环境下运行，并独占全机，因此机内的资源的状态只有运行的程序操作才机，因此机内的资源的状态只有运行的程序操作才能改变它，其执行结果不受外界因素的影响能改变它，其执行结果不受外界因素的影响 （3）可再现性：只要程

3、序执行时的环境和初始条件）可再现性：只要程序执行时的环境和初始条件相同，程序经多次运行后所得的结果必然相同相同，程序经多次运行后所得的结果必然相同 二二. 程序的并发执行程序的并发执行 1. 什么是程序的并发执行什么是程序的并发执行 若干个程序段同时在系统中运行，这些程序段若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行叠是很小的一部分，也称这几个程序段是并发执行的。的。PQR例：三个

4、并发执行的程序段。例：三个并发执行的程序段。 用下图说明在多道批处理系统中，大量操作执用下图说明在多道批处理系统中，大量操作执行的先后次序。行的先后次序。 I1 I2 I3 I4C1C3C2P1P2讨论：讨论：(1) 哪些程序段的执哪些程序段的执行必须是顺序的？为行必须是顺序的？为什么？什么？(2) 哪些程序段的执哪些程序段的执行是并行的？为什么？行是并行的？为什么？2. 2. 表示方法表示方法s0;cobegins1; s2; sn;coendsn+1;s0s1s2snSn+1程序顺序执行在顺序环境下在顺序环境下:先先A,后后B CPU利用率利用率= 40/80 = 50%DEV1利用率利用

5、率=18.75%DEV2利用率利用率= 31.25%程序并发执行在并发环境下在并发环境下CPU利用率利用率=89%DEV1并发环境下利用并发环境下利用=33%DEV2并发环境下利用并发环境下利用=66%并行和并发在单在单CPU系统中，系统调度在某一时刻只能让一系统中，系统调度在某一时刻只能让一个线程个线程(进程进程)运行，虽然这种调度机制有多种形运行，虽然这种调度机制有多种形式式(大多数是时间片轮巡为主大多数是时间片轮巡为主)，但无论如何，要，但无论如何，要通过不断切换需要运行的线程让其运行的方式就通过不断切换需要运行的线程让其运行的方式就叫叫并发(concurrent)。而在多而在多CPU系

6、统中，可以让两个以上的线程系统中，可以让两个以上的线程(进进程程)同时运行，这种可以同时让两个以上线程同时同时运行，这种可以同时让两个以上线程同时运行的方式叫做运行的方式叫做并行(parallel)多道程序设计和并发的关系多道程序设计和并发的关系6.2 6.2 与时间有关的错误与时间有关的错误 1. 1. 什么是与时间有关的错误什么是与时间有关的错误 执行结果与并发程序执行的相对速度相关执行结果与并发程序执行的相对速度相关 2. 2. 为什么会发生与时间有关的错误为什么会发生与时间有关的错误 当两个或多个程序有共同的临界资源时，由于程序当两个或多个程序有共同的临界资源时，由于程序执行的速度不同

7、，则会发生与时间有关的错误执行的速度不同，则会发生与时间有关的错误例：例：P111例：例：P113并发程序的特征并发程序的特征 1. 失去程序的封闭性和可再现性失去程序的封闭性和可再现性 如果程序执行的结果是一个与时间无关的函数，即具有封如果程序执行的结果是一个与时间无关的函数，即具有封闭性。闭性。 若一个程序的执行可改变另一个程序的变量，程序执行的若一个程序的执行可改变另一个程序的变量，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。对速度，在这种情况下就失去了程序的封闭性。 在并发环

8、境中，机内资源状态将由多个程序来改变，因此在并发环境中，机内资源状态将由多个程序来改变，因此使程序的运行失去了封闭性。使程序的运行失去了封闭性。 2. 2.程序与计算不再一一对应程序与计算不再一一对应 一个程序的一次执行称为一个计算一个程序的一次执行称为一个计算 在并发的环境下，一个程序可对应多个计算。在并发的环境下，一个程序可对应多个计算。 在程序顺序执行时，一个程序总是对应一个具体在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，使用同一个程序，但处理（计算）

9、的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用例如，在多用户环境下，可能同时有多个用户调用C C语语言的编译程序，这就是典型的一个程序对应多个用户言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。源程序的情况。 3.3.程序并发执行的相互制约程序并发执行的相互制约 在多道程序设计的环境下，程序是并发执行的。在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在即系统中有多道程序在“同时同时”执行，这些程序之间执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际

10、上是一合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。种相互制约，有直接的，也有间接。 （1 1）资源共享）资源共享 （间接制约关系）（间接制约关系） （2 2）进程合作）进程合作 （直接制约关系）（直接制约关系） 无关的并发进程并发进程分类：并发进程分类：无关的，交互的无关的并发进程：一组并发进程分并发进程：一组并发进程分别在不同的变量集合上操作，一个别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展进程的执行与其他并发进程的进展无关无关并发进程的无关性是进程的执行与时间无关的一个充分条件进程的相互制约关系进程的相互制约关系交互的并发进程交互的并发进程

11、：一组并发进程共享交互的并发进程：一组并发进程共享某些变量，或者一组进程相互合作某些变量，或者一组进程相互合作; ;一一个进程的执行可能影响其他并发进程个进程的执行可能影响其他并发进程的结果的结果与时间有关的错误执行的相对速度无法相互控制执行的相对速度无法相互控制表现形式：表现形式：结果不唯一结果不唯一 例：例：P P111,111,P P113113永远等待永远等待 例：死锁例：死锁进程的交互：竞争与协作 并发进程之间的竞争关系并发进程之间的竞争关系共享资源共享资源 进程的互斥进程的互斥 并发进程之间的协作关系并发进程之间的协作关系进程的相互合作进程的相互合作进程的同步进程的同步进程的交互：

12、竞争与协作第一种是竞争关系 资源竞争的两个控制问题：一个是死锁一个是死锁(Deadlock)(Deadlock)问题问题 一个是饥饿一个是饥饿(Starvation) (Starvation) 问题问题既要解决饥饿问题，又要解决死锁问题既要解决饥饿问题，又要解决死锁问题进程的交互：竞争与协作进程互斥是解决进程间竞争关系是解决进程间竞争关系( (间接制约关系间接制约关系) )的手段的手段进程互斥指若干进程要使用同一共指若干进程要使用同一共享资源时，任何时刻最多允许一个享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直进程使用，其他进程必须等待，直到占有资源的进程释放该资源到占有资源的进

13、程释放该资源进程的交互：竞争与协作第二种是协作关系(1) 某些进程为完成同一任务需要某些进程为完成同一任务需要分工协作分工协作 进程的同步是解决进程间协作是解决进程间协作关系关系( (直接制约关系直接制约关系) )的手段的手段进程的交互：竞争与协作第二种是协作关系(2) 进程同步指两个以上进程基于某个指两个以上进程基于某个条件来协调它们的活动。一个进程条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直作进程的消息或信号时需等待，直到消息或信号到达才被唤醒到消息或信号

14、到达才被唤醒 进程的交互：竞争与协作第二种是协作关系(3)进程互斥关系是一种特殊的进程进程互斥关系是一种特殊的进程同步关系，即同步关系，即逐次使用逐次使用互斥共享互斥共享资源，是对进程使用资源次序上资源，是对进程使用资源次序上的一种协调的一种协调6.3临界区与PV操作6.3.1临界区临界区 6.3.2 PV操作操作 6.3 6.3 临界区和临界区和PVPV操作操作 引例：引例： 宿舍电话的使用宿舍电话的使用 打印机的使用打印机的使用 1. 临界资源：一次仅允许一个进程使用的资源称为临临界资源：一次仅允许一个进程使用的资源称为临界资源界资源 引例中的电话和打印机都属于临界资源。除此之外引例中的电

15、话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源，还有内存变量、指针、数组等等也是临界资源2 2、临界区：、临界区：每个进程中访问临界资每个进程中访问临界资源的那段程序段称为临源的那段程序段称为临界区（临界段）界区（临界段）临界区临界区例：例：P111例：例：P113临界区临界区互斥互斥定义定义: : 在操作系统中，当某一进程正在访问某临界区时，在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生就不允许其它进程进入，否则就会发生( (后果后果) )无法无法估计的错误。我们把进程之间的这种相互制约的关估计的错误。我们把进程之间的这种相互制约

16、的关系称为互斥系称为互斥 进入临界区的准则：进入临界区的准则： (1)(1)每次至多有一个进程处于临界区；每次至多有一个进程处于临界区； (2)(2)当有若干个进程欲进入临界区时，应在有当有若干个进程欲进入临界区时，应在有限的时间内使其进入；限的时间内使其进入； (3)(3)进程在临界区内仅逗留有限的时间进程在临界区内仅逗留有限的时间信号量信号量 信号量信号量是一个确定的二元组是一个确定的二元组(s，q)，s是一个具有非负初是一个具有非负初值的整型变量，值的整型变量，q是一个初始状态为空的队列。操作系是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和统利用信号灯的

17、状态对并发进程和共享资源进行控制和管理管理 s代表资源的实体代表资源的实体，是，是整型变量整型变量 s 0 0 时，表示绿灯，进程执行时，表示绿灯，进程执行( (表示系统拥有的表示系统拥有的资源个数资源个数) s 0 0 时，表示红灯，进程停止执行时，表示红灯，进程停止执行( ( |s|表示等待表示等待某资源的进程个数某资源的进程个数) ) 注意：创建信号灯时，应准确说明信号灯注意：创建信号灯时，应准确说明信号灯 s 的意义的意义和初值和初值 (这个初值绝不能为负值这个初值绝不能为负值)用原语实现互斥用原语实现互斥记录型信号量设s为一个记录型数据结构,一个分量为整型量value,另一个为信号量

18、队列queue, P和V操作原语定义： P(s)：将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态 V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程记录型信号量type semaphore = record value:integer; queue: list of process;Endprocedure P(var s:semaphore);begin s := s 1; / /* * 把信号量减去把信号量减去1 1 * */ / if s 0 then W(s);/ /* * 若信号量小于若信号量小于0 0，则调用，则调用P(s)P(s)

19、的进的进 程被置成等待信号量程被置成等待信号量s s的状态的状态 * */ /end;procedure V(var s:semaphore);begins := s + 1; / /* * 把信号量加把信号量加1 1 * */ /if s 0表示有S个资源可用；S=0表示无资源可用；S0则| S |表示S等待队列中的进程个数。P(S):表示申请一个资源; V(S)表示释放一个资源。信号量的初值应该大于等于0P.V操作讨论P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操

20、作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前,而两个V操作无关紧要总结：如何描述进程同步问题？先写出对问题的初步描述（用汉语，流程）；例如司机售票员问题中：司机（进程）：启动车辆；正常行驶；停车问题中存在的关系（互斥、同步，各有几种）；互斥：涉及到对共享资源的访问同步：涉及到进程之间的执行次序设置信号量（信号量的个数和初值（考虑问题的初始状态），信号量的物理含义）； 信号量的初值：0，1，n三种情况 1：表示临界资源； 0：表示进程间的同步（前驱）关系 n：表示若干个资源总结：如何描述进程同步问题？（续）把P、V操作放到合适的位置。P操作：要控制谁就放在谁的

21、前面；6.5 进程通信P.V操作实现的是进程之间的低级通讯，所操作实现的是进程之间的低级通讯，所以以P.V为低级通讯原语。它只能传递简单的为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息信号，不能传递交换大量信息如果要在进程间传递大量信息则要用如果要在进程间传递大量信息则要用Send / Receive原语（高级通信原语）原语（高级通信原语）目前常用的高级通信方式有信箱通信、消息缓冲通信、管道通信。6.5.1 信件发送者名发送者名-进程名进程名信息信息(地址和长度地址和长度)等等/不等回信不等回信回信存放地址回信存放地址6.5.2 信箱若干个进程可向同一进程发送信件若干个进程可向同一

22、进程发送信件.接受信件的进程接受信件的进程可以设立一个信箱可以设立一个信箱信箱的大小决定了可容纳的信件数信箱的大小决定了可容纳的信件数由信箱说明和信箱体两部分组成由信箱说明和信箱体两部分组成6.5.3 通信原语通信遵循规则通信遵循规则:发送信件时信箱已满发送信件时信箱已满,则将发送信件的进程置为则将发送信件的进程置为”等信箱等信箱”状态状态,直到信箱有空才被释放直到信箱有空才被释放取信件信箱为空取信件信箱为空,则将收信件的进程置为则将收信件的进程置为”等信等信件件”状态状态,直到有信件才被释放直到有信件才被释放通信原语send(N,M) 功能：把信件功能：把信件M送到指定的送到指定的信箱信箱N

23、中中 receive(N,X) 功能：从指定信箱功能：从指定信箱N中取中取出一封信，存放到指定的地址出一封信，存放到指定的地址X中中 6.6死锁6.6.1死锁的形成死锁的形成 6.6.2死锁的必要条件死锁的必要条件 6.6.3死锁的防止死锁的防止 6.6.4死锁的避免死锁的避免 6.6.5死锁的检测死锁的检测 例例1： 进程进程P 进程进程Q : : 请求读卡机请求读卡机 请求打印机请求打印机 : : 请求打印机请求打印机 请求读卡机请求读卡机 : : 释放读卡机释放读卡机 释放读卡机释放读卡机 : : 释放打印机释放打印机 释放打印机释放打印机 : :资源分配不当产生死锁资源分配不当产生死锁

24、6.6.1 死锁的形成死锁的形成例例2：m个资源被个资源被n个进程共享，每个进程要求个进程共享，每个进程要求k个资个资源，则当源，则当 m=n*(k-1) 时，如果分配不当就可能发时，如果分配不当就可能发生死锁。生死锁。 死锁的定义：死锁的定义：在两个或多个并发进程中，如果在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。它或它们现在保持着的资源，否则就不能向前推进。此时每个进程都占用了一定的资源但又都不能向前此时每个进程都占用了一定的资源但又都不能向前推进，称这一组进程产生可死锁。

25、推进，称这一组进程产生可死锁。资源分配不当产生死锁资源分配不当产生死锁1. 产生死锁的原因产生死锁的原因 资源不足资源不足 进程推进次序不合适进程推进次序不合适2. 2. 产生死锁的必要条件产生死锁的必要条件 互斥条件互斥条件 一个资源一次只能被一个进程使用。一个资源一次只能被一个进程使用。 不可剥夺条件不可剥夺条件 一个资源仅能被占有它的进程释放。一个资源仅能被占有它的进程释放。 部分分配部分分配 一个进程已占有了一些资源，但仍然要求其它资源。一个进程已占有了一些资源，但仍然要求其它资源。 环路条件环路条件 系统中存在着一个由若干个进程形成的环形请求链。系统中存在着一个由若干个进程形成的环形

26、请求链。6.6.2. 死锁的必要条件死锁的必要条件解决死锁问题的策略解决死锁问题的策略破坏产生死锁的四个必要条件之一破坏产生死锁的四个必要条件之一 解决死锁的策略：解决死锁的策略： 死锁的防止死锁的防止 死锁的避免死锁的避免 死锁的检测死锁的检测6.6.3 6.6.3 死锁的防止死锁的防止 1.1.静态分配资源：静态分配资源：仅当系统能满足作业运行时所仅当系统能满足作业运行时所需的全部资源时，才把该作业调入内存运行，需的全部资源时，才把该作业调入内存运行，同时在作业运行前，将其所需的全部资源一次同时在作业运行前，将其所需的全部资源一次性地分配给该作业。作业在运行过程中不再提性地分配给该作业。作

27、业在运行过程中不再提出新的资源要求出新的资源要求破坏破坏“占有且等待资源占有且等待资源”和和“循环等待资源循环等待资源” 缺点：资源利用率低缺点：资源利用率低 作业等待时间长作业等待时间长2. 2. 按序分配资源：按序分配资源：系统中的所有资源类都分给系统中的所有资源类都分给一个唯一的序号，并要求每个进程均应一个唯一的序号，并要求每个进程均应严格按照递增的次序请求资源严格按照递增的次序请求资源破坏破坏 “循环等待资源循环等待资源” 缺点：缺点：对于实际资源使用顺序与资源序号不一对于实际资源使用顺序与资源序号不一致的作业仍存在着资源浪费现象致的作业仍存在着资源浪费现象3. 剥夺式分配资源剥夺式分配资源：可抢夺其它进程的资源：可抢夺其它进程的资源破坏破坏 “非抢夺式分配非抢夺式分配” 例：分配主存例：分配主存6.6.4 死锁的避免死锁的避免 银行家算法银行家算法 检查申请者对各类资源的最大需求量，如果检查申请者对各类资源的最大需求量，如果系