第2章 进程管理

1、第二章 进 程 管 理 第二章第二章 进程管理进程管理第二章 进 程 管 理 本章要点（本章要点（1/3） 目标：目标：建立起进程的概念，掌握好进程控制、建立起进程的概念，掌握好进程控制、进程同步和进程间通信的基本概念。进程同步和进程间通信的基本概念。 进程的基本概念进程的基本概念 为什么要引入进程 进程的基本特征 进程的状态 进程控制块 进程同步的基本概念进程同步的基本概念 临界资源 临界区 同步机制应遵循的准则第二章 进 程 管 理 本章要点（本章要点（2/3） 信号量机制及其应用信号量机制及其应用 信号量的含义 信号量的物理意义 用信号量实现互斥 用信号量实现前趋关系 经典进程的同步问题

2、经典进程的同步问题 生产者-消费问题 哲学家进餐问题 读者-写者问题这些问题用于解决什么问题如何实现进程互斥如何实现进程同步第二章 进 程 管 理 本章要点（本章要点（3/3） 消息传递通信机制消息传递通信机制 什么是消息传递通信机制 消息传递通信机制的实现方式 如何协调发送进程和接收进程 消息缓冲队列通信机制 线程的基本概念线程的基本概念 为什么要引入线程 线程的特征 创建和终止线程 内核支持线程和用户级线程内核支持线程和用户级线程 什么是内核支持线程 什么是用户级线程第二章 进 程 管 理 本章内容本章内容2.1 2.1 进程的基本概念进程的基本概念2.2 2.2 进程控制进程控制 2.3

3、 2.3 进程同步进程同步2.4 2.4 经典进程的同步问题经典进程的同步问题2.5 2.5 进程通信进程通信2.6 2.6 线程线程第二章 进 程 管 理 2.1 进程的基本概念进程的基本概念第二章 进 程 管 理 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 图图 2-1 程序的顺序执行程序的顺序执行 I1C1P1I2C2P2(a) 程序的顺序执行程序的顺序执行S1S2S3(b) 三条语句的顺序执行三条语句的顺序执行1、程序的顺序执行、程序的顺序执行S1 : a : = x + y;S2 : b : = a - 5;S3 : c : = b + 1;I : 输入操作输入操作C

4、: 计算操作计算操作P : 打印操作打印操作第二章 进 程 管 理 顺序性：顺序性：处理机的操作必须严格按照程序所规定的顺序执行。 封闭性：封闭性：程序在执行时独占系统的全部资源，机器资源状态的改变只与执行的程序有关，而与外界环境无关。 可再现性：可再现性：只要初始条件相同，一个程序的多次重复执行，将得到相同的结果。 2、程序顺序执行的特征、程序顺序执行的特征第二章 进 程 管 理 2.1.2 前趋图前趋图 前趋图前趋图是一个有向无循环图有向无循环图，用于描述描述程序段或进程之间执行的先后次序先后次序关系。图中的结点结点用于描述一个程序段或一个进程，结点间的有向边有向边用于表示两个结点之间存在

5、的偏偏序序或前趋关系“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可写成PiPj，称Pi是Pj的直接前趋直接前趋，而称Pj是Pi的直直接后继接后继。在前趋图中，把没有前趋的结点称为初始结点初始结点，把没有后继的结点称为终止结点终止结点。第二章 进 程 管 理 每个结点还具有一个重量重量，用于表示该结点所含有的程序量程序量或结点的执行时间执行时间。 图图 2-2 前趋图前趋图 P1P2P3P4P5P7P6P8P9(a)具有九具有九个结点的前趋图个结点的前趋图S1S2S3(b)具有循环的具有循环的图图第二章 进 程 管

6、 理 图图 2-3 并发执行时的前趋图并发执行时的前趋图 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 1、程序的并发执行、程序的并发执行I1I2I3I4C1C2C3C4P1P2P3P4第二章 进 程 管 理 例子： 对于具有下述四条语句的程序段 S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 图图 2-4 四条语句的前趋关系四条语句的前趋关系S1S2S3S41、程序的并发执行、程序的并发执行第二章 进 程 管 理 间断性：间断性：由于资源共享和相互合作，并发执行的程序间形成了相互制约关系，导致程序的运行过程出现“执行-暂停-执行”的现象。

7、失去封闭性：失去封闭性：程序在执行时与其他并发执行的程序共享系统的资源，因此，资源状态的改变还与其他程序有关，即程序本身的执行环境要受到外界程序的影响。 不可再现性：不可再现性：同样的初始条件，一个程序的多次重复执行，可得到不同的结果。 2、程序并发执行时的特征、程序并发执行时的特征第二章 进 程 管 理 例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N =N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。 (1) N =N+1在Print(N)和N =0之前，此时得到的N值分别为n+1, n+1, 0。

8、 (2) N =N+1在Print(N)和N =0之后，此时得到的N值分别为n, 0, 1。 (3) N =N+1在Print(N)和N =0之间，此时得到的N值分别为n, n+1, 0。 2、程序并发执行时的特征、程序并发执行时的特征第二章 进 程 管 理 2.1.4 进程的特征与状态进程的特征与状态1、进程的特征和定义、进程的特征和定义 进程进程=？程序？程序 一个进程比一个程序的内容要多 程序只是进程状态的一部分内容第二章 进 程 管 理 引入进程的目的：引入进程的目的：为了使程序能够正确地并发执行。 进程的特征：进程的特征： 结构特征：结构特征：进程实体 = 程序段 + 数据段 + P

9、CB 动态性：动态性： 进程的实质是进程实体的一次执行过程 进程具有一定的生命周期：由创建而产生，由调度而执行，由撤消而消亡。 并发性：并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。 独立性：独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。 异步性：异步性：进程可按各自独立的、不可预知的速度向前推进。1、进程的特征和定义、进程的特征和定义第二章 进 程 管 理 进程与程序的区别：进程与程序的区别： 程序程序是进程的静态文本，进程进程是执行程序的动态过程； 一个进程一个进程可以执行一个或多个程序一个或多个程序，几个进程几个进程可以同时执行一个程序一个程序；

10、程序程序可作为软件资源长期保存，进程进程只是一次执行过程，是暂时的； 进程进程是系统分配调度的独立单位，能与其他进程并发执行。 定义：定义：进程是一个可并发执行的程序，在一个数据集合上的一次运行过程。它是系统进行资源分配和调度的一个独立单位。1、进程的特征和定义、进程的特征和定义第二章 进 程 管 理 就绪状态（就绪状态（Ready） 执行状态（执行状态（Running） 阻塞状态（阻塞状态（Blocked）图图 2-5 进程的三种基本进程的三种基本 状态及其转换状态及其转换 2、进程的三种基本状态、进程的三种基本状态 对单个进程：对单个进程： 任何时刻，进程只能处理三种基本状态之一； 随着进

11、程自身的推进和外界条件的变化，进程的状态可以动态地转换 对整个系统：对整个系统： 每个时刻允许同时有多个进程处于就绪/阻塞状态； 对于执行状态的进程，每个处理机最多只允许有一个。就绪就绪执行执行阻塞阻塞进程调度进程调度I/O请求请求I/O完成完成时间片完时间片完第二章 进 程 管 理 挂起：挂起：实质是使进程不能继续执行 被挂起的进程处于静止状态； 没被挂起的进程处于活动状态。 引起挂起的原因：原因： 终端用户的请求； 父进程请求； 负荷调节的需要； 操作系统的需要；3、挂起状态、挂起状态第二章 进 程 管 理 进程状态的转换SuspendSuspendActiveActive3、挂起状态、挂

12、起状态静止就绪(Readys)静止阻塞(Blockeds)活动就绪(Readya) 活动阻塞(Blockeda) 活动就绪(Readya) 活动阻塞(Blockeda) 静止就绪(Readys) 静止阻塞(Blockeds)第二章 进 程 管 理 3、挂起状态、挂起状态图图 2-6 具有挂起状态的进程状态图具有挂起状态的进程状态图 执行执行静止静止就绪就绪静止静止阻塞阻塞活动活动就绪就绪活动活动阻塞阻塞请求请求I/O挂起挂起激活激活挂起挂起激活激活挂起挂起唤醒唤醒唤醒唤醒进程调度进程调度时间片完时间片完第二章 进 程 管 理 创建状态创建状态 为一个新进程创建PCB，并填写必要的管理信息； 把

13、该进程转入就绪状态并插入就绪队列之中。 引入创建状态的目的引入创建状态的目的 为了保证进程的调度必须在创建工作完成后进行，确保进程控制块操作的完整性。 增加管理的灵活性，操作系统可以根据系统性能或主存容量的限制，推迟创建状态进程的提交。4、创建状态和终止状态、创建状态和终止状态第二章 进 程 管 理 终止状态终止状态 首先等待操作系统进行善后处理； 然后将其PCB清零，并将PCB空间返还系统。 引起进程终止的事件引起进程终止的事件 自然结束； 出现无法克服的错误； 被操作系统终结，或其他有终止权的进程所终结。 终止进程的处理过程终止进程的处理过程 进入终止状态的进程以后不能被执行，但在操作系统

14、中保留有一个记录，其中保存状态码和一些计时统计数据，供其他进程收集； 一旦其它进程完成了对终止状态进程的信息提取后，操作系统将删除该进程。4、创建状态和终止状态、创建状态和终止状态第二章 进 程 管 理 增加创建状态与终止状态的状态转换图增加创建状态与终止状态的状态转换图4、创建状态和终止状态、创建状态和终止状态图图 2-7 进程的五种基本状态及转换进程的五种基本状态及转换 就绪就绪执行执行阻塞阻塞时间片完时间片完进程调度进程调度I/O请求请求I/O完成完成创建创建许可许可终止终止释放释放第二章 进 程 管 理 增加创建状态与终止状态的状态转换图增加创建状态与终止状态的状态转换图4、创建状态和

15、终止状态、创建状态和终止状态图图 2-8 具有创建、终止和挂起状态的进程状态图具有创建、终止和挂起状态的进程状态图 执行执行静止静止就绪就绪静止静止阻塞阻塞活动活动就绪就绪活动活动阻塞阻塞请求请求I/O挂起挂起激活激活挂起挂起激活激活挂起挂起唤醒唤醒唤醒唤醒进程调度进程调度时间片完时间片完创建创建许可许可终止终止释放释放许可许可第二章 进 程 管 理 2.1.5 进程控制块进程控制块1、进程控制块中的信息、进程控制块中的信息PCB程序段程序段私有私有数据数据进程名进程名当前状态当前状态优先数优先数现场保留区现场保留区指示处于同一状态指示处于同一状态进程的链指针进程的链指针资源清单资源清单进程起

16、始地址进程起始地址家族关系家族关系其他其他（a）进程示意图）进程示意图（b）进程控制块的基本内容）进程控制块的基本内容第二章 进 程 管 理 PCB是进程存在的唯一标志是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤消其PCB。 进程控制块进程控制块PCB（Process Control Block）：是进程实体的一部分是操作系统中最重要的记录型数据结构记录了操作系统所需的、用于描述进程当前情况以及控制进程运行的全部信息 PCB的作用：的作用：将程序变成可并发执行的进程 PCB必须长驻内存必须长驻内存2、进程控制块的作用、进程控制块的作用第二章 进 程 管 理 调度进程执行时

17、调度进程执行时,需要从该进程的需要从该进程的PCB中查出其现中查出其现行状态及优先级；行状态及优先级； 调度到某进程后调度到某进程后，根据，根据PCB中所保存的处理机状态中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据信息，设置该进程恢复运行的现场，并根据PCB中中的程序和数据的内存始址，找到其程序和数据；的程序和数据的内存始址，找到其程序和数据； 进程在执行过程中进程在执行过程中，当需要和与之合作的进程实现，当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问同步、通信或访问文件时，也需要访问PCB； 当进程由于某种原因而当进程由于某种原因而暂停执行时暂停执行时，又须将断点

18、的，又须将断点的处理机环境保存在处理机环境保存在PCB中。中。2、进程控制块的作用、进程控制块的作用第二章 进 程 管 理 进程标识符进程标识符 处理机状态处理机状态 进程调度信息进程调度信息 进程控制信息进程控制信息3、进程控制块中的信息、进程控制块中的信息第二章 进 程 管 理 3.1、进程标识符、进程标识符进程标识符进程标识符用于唯一地标识一个进程。用于唯一地标识一个进程。（1）内部标识符。在所有的操作系统中，）内部标识符。在所有的操作系统中，都为每一个进程赋予一个唯一的数字标识都为每一个进程赋予一个唯一的数字标识符，它通常是一个进程的序号。符，它通常是一个进程的序号。（2）外部标识符）

19、外部标识符 由创建者提供，通常是由创建者提供，通常是由用户在访问该进程时使用。由用户在访问该进程时使用。进程标识符进程标识符第二章 进 程 管 理 3.2、处理机状态、处理机状态处理机状态信息处理机状态信息主要是由处理机的各种寄存器中的主要是由处理机的各种寄存器中的内容组成的。内容组成的。 处理机运行时，许多信息都存放在寄处理机运行时，许多信息都存放在寄存器中。当处理机被中断时，所有这些信息都必须存器中。当处理机被中断时，所有这些信息都必须保存在保存在PCB中，以便该进程重新执行时，能从断点中，以便该进程重新执行时，能从断点继续执行。这些寄存器包括：继续执行。这些寄存器包括：通用寄存器通用寄存

20、器：用户可视寄存器，用于暂存信息，用户程序可：用户可视寄存器，用于暂存信息，用户程序可以访问；以访问；指令计数器指令计数器：存放了要访问的下一条指令的地址；：存放了要访问的下一条指令的地址；程序状态字程序状态字PSW:其中包含了状态信息，如条件码、执行方式、其中包含了状态信息，如条件码、执行方式、终端屏蔽标志等；终端屏蔽标志等；用户栈指针用户栈指针：每个用户进程都有一个或若干个与之相关的系：每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指统栈，用于存放过程和系统调用参数及调用地址。栈指针指向栈顶。向栈顶。第二章 进 程 管 理 3.3、进程调度信息、

21、进程调度信息在在PCB中还存放一些与进程调度和进程对换有关的中还存放一些与进程调度和进程对换有关的信息，包括：信息，包括：进程状态进程状态 指明进程的当前状态，作为进程调度和对指明进程的当前状态，作为进程调度和对换时的依据；换时的依据；进程优先级进程优先级 优先级高的进程应先获得处理机优先级高的进程应先获得处理机进程调度所需的其它信息进程调度所需的其它信息 与所采用的进程调度算法与所采用的进程调度算法有关，比如，进程已等待有关，比如，进程已等待CPU的时间总和、进程已的时间总和、进程已执行的时间总和等；执行的时间总和等；事件事件 即阻塞原因，指进程由执行状态转变为阻塞状即阻塞原因，指进程由执行

22、状态转变为阻塞状态所等待发生的事件。态所等待发生的事件。第二章 进 程 管 理 3.4、进程控制信息、进程控制信息程序和数据的地址程序和数据的地址: 指进程的程序和数据所在的内存指进程的程序和数据所在的内存或外存地址，以便再调度到该程序执行时，能从或外存地址，以便再调度到该程序执行时，能从PCB中找到其程序和数据；中找到其程序和数据；进程同步和通信机制进程同步和通信机制:指实现进程同步和通信必需的指实现进程同步和通信必需的机制，如消息队列指针、信号量等；机制，如消息队列指针、信号量等；资源清单资源清单：是一张列出了使用：是一张列出了使用CPU以外的、进程所以外的、进程所需的全部资源及已经分配到

23、该进程的资源的清单；需的全部资源及已经分配到该进程的资源的清单；链接指针链接指针：它给出了本进程（：它给出了本进程（PCB）所在队列中的）所在队列中的下一个进程的下一个进程的PCB的首地址。的首地址。第二章 进 程 管 理 链接方式：链接方式：把具有同一状态的PCB，用其中的链接字链接成一个队列4、进程控制块的组织方式、进程控制块的组织方式执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针空闲队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB915P5正在执行；正在执行；就绪进程有：就绪进程有：P1,P4,P8阻塞进程有：阻塞

24、进程有：P2,P3其余为空闲进程控制块其余为空闲进程控制块PCB第二章 进 程 管 理 索引方式：索引方式：系统根据所有进程的状态建立几张索引表，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。3、进程控制块的组织方式、进程控制块的组织方式PCB1执行指针执行指针就绪表指针就绪表指针阻塞表指针阻塞表指针就绪索引表就绪索引表阻塞索引表阻塞索引表PCB2PCB3PCB4PCB5PCB6PCB7第二章 进 程 管 理 2.2 进程控制进程控制第二章 进 程 管 理 2.2 进程控制进程控制 进程控制进程控制是进程管理中最基本

25、的功能： 创建和撤消进程 对进程在整个生命期中各种状态之间的转换进行有效控制。 进程控制是操作系统的内核通过原语来实现的。 原语：原语：是指由若干条指令组成，用来实现某个特定操作的一个过程。 原语的执行具有原子性； 原语常驻内存，且在系统状态下执行。 第二章 进 程 管 理 2.2 进程控制进程控制 系统状态系统状态和用户状态用户状态是处理机的两种执行状态，用于防止用户程序破坏操作系统内核代码和数据。 系统状态：系统状态：也叫管态或核心状态，它具有较高的特权，能执行一切指令，访问所有寄存器和存储区。 通常操作系统内核就运行在系统状态。 用户状态：用户状态：也叫目态，是一种具有较低特权的执行状态

26、，它只能执行规定的指令、访问规定的寄存器和存储区。 通常用户程序都是运行在用户状态。第二章 进 程 管 理 图图 2-9 进程树进程树 2.2.1 进程的创建进程的创建1、进程图（、进程图（Process Graph） 进程图：进程图：用于描述一个进程的家庭关系的有向树。 父进程 子进程 祖先进程 祖先 子进程可以继承父子进程可以继承父进程所拥有的资源进程所拥有的资源ABCDEFGHIJKLM第二章 进 程 管 理 (1) 用户登录用户登录。 (2) 作业调度作业调度。 (3) 提供服务提供服务。 (4) 应用请求应用请求。 2、引起创建进程的事件、引起创建进程的事件由系统内核创建新进程由应用

27、程序创建新进程第二章 进 程 管 理 创建原语创建原语Creat()： 功能：功能：创建进程控制块PCB 入口信息：入口信息：进程标识符、优先级、进程开始地址、初始CPU状态、资源清单等 实现过程：实现过程： 申请空白PCB； 为新进程分配资源； 初始化进程控制块 将新进程插入就绪队列 3、进程的创建、进程的创建(Creation of Progress) 开始开始申请空白申请空白PCB为新进程分配资源为新进程分配资源初始化进程控制块初始化进程控制块将新进程插入就绪队列将新进程插入就绪队列第二章 进 程 管 理 2.2.2 进程的终止进程的终止 1) 正常结束正常结束 2) 异常结束异常结束

28、越界错误 保护错 非法指令 特权指令错 运行超时 等待超时 算术运算错 I/O故障 3)外界干预外界干预 操作员或操作系统干预 父进程请求 父进程终止1、引起进程终止、引起进程终止(Termination of Process)的事件的事件第二章 进 程 管 理 终止原语：终止原语： 功能：功能：终止一个指定的进程 入口信息：入口信息：被终止的进程名 实现过程：实现过程： 根据被终止进程的标识符，从PCB集合中检索进程的PCB。 若被终止进程正在执行，则终止它的执行，并置重新调度标志。 终止属于该进程的所有子孙进程。 释放被终止进程所拥有的全部资源。 将终止进程移出它所在队列并收回PCB。2、

29、进程的终止过程、进程的终止过程开始开始检索检索PCB，读出进程状态，读出进程状态若是执行，置调度标志为真若是执行，置调度标志为真若有子孙进程，终止其子孙进程若有子孙进程，终止其子孙进程将所拥有的资源归还给父进程或系统将所拥有的资源归还给父进程或系统将将PCB从所在队列移出从所在队列移出第二章 进 程 管 理 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒请求系统服务请求系统服务 启动某种操作启动某种操作 新数据尚未到达新数据尚未到达 无新工作可做无新工作可做 1、引起进程阻塞和唤醒的事件、引起进程阻塞和唤醒的事件第二章 进 程 管 理 阻塞原语（阻塞原语（block()）：）： 功能：功能：将进

30、程从执行状态转换成阻塞状态 入口信息：入口信息：可省略 实现过程：实现过程： 停止进程执行，将其状态改为阻塞状态； 将其PCB插入相应的阻塞队列； 转调度程度进行重新调度。 进程的阻塞是进程的主动进程的阻塞是进程的主动行为行为 2、进程的阻塞过程、进程的阻塞过程开始开始将将CPU当前状态存入当前状态存入PCB设置进程状态为阻塞状态设置进程状态为阻塞状态将将PCB置入阻塞队列置入阻塞队列转处理机调度转处理机调度第二章 进 程 管 理 唤醒原语（唤醒原语（wakeup()）：）： 功能：功能：当被阻塞进程所等待的事件完成时，唤醒某一处于等待队列当中的进程。 入口信息：入口信息：被唤醒进程的名字 实

31、现过程：实现过程： 将被阻塞的进程从等待该事件的阻塞队列中移出； 将其PCB中的状态由阻塞改为就绪； 将该PCB插入到就绪队列中。3、进程唤醒过程、进程唤醒过程开始开始从阻塞队列删除该从阻塞队列删除该PCB设置进程状态为就绪状态设置进程状态为就绪状态将将PCB置入就绪队列置入就绪队列结束结束第二章 进 程 管 理 2.2.4 进程的挂起与激活进程的挂起与激活挂起原语（挂起原语（suspend()）：）： 功能：功能：将指定进程挂起 实现过程：实现过程：挂起进程处于活动就绪状态，将其转换为静止就绪；挂起进程处于活动阻塞状态，将其转换为静止阻塞；把被挂起的进程的PCB复制到某指定的内存区域；若被挂

32、起的进程正在执行，则转向调度程序重新调度。如果挂起是为了对换，则在挂起进程时还必须将它换出到外存1、进程的挂起、进程的挂起第二章 进 程 管 理 激活原语（激活原语（active()）：）： 功能：功能：使处于静止状态的进程变为活动 执行过程：执行过程：若进程处于静止阻塞状态，则将它转换成活动阻塞状态；若进程为静止就绪状态，则将它转换为活动就绪状态；若进程转换成活动就绪状态，而系统又采用抢占调度策略，则应检查该进程是否有权抢占CPU，若有则应进行进程调度；如果挂起是为了对换，则在激活被挂起的进程时还必须将它调入内存。2、进程的激活、进程的激活第二章 进 程 管 理 2.3 进程同步进程同步第二

33、章 进 程 管 理 进程同步问题的提出进程同步问题的提出 进程异步推进可能造成混乱 混乱可能导致不可再现 进程同步目标进程同步目标2.3 进程同步进程同步第二章 进 程 管 理 间接相互制约关系（进程互斥进程互斥）：这种制约源于资源共享。 直接相互制约关系（进程同步进程同步）：这种制约源于进程间合作。 2.3.1 进程同步的基本概念进程同步的基本概念同同 步步互互 斥斥进程-进程进程-资源-进程时间次序上受到某种限制未竞争到物理资源的进程处于阻塞状态相互清楚对方的存在及作用，交换信息不一定清楚其他进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间通讯制约例：生产与消费之间，发送与

34、接受之间，作者与读者之间，供者与用者之间例：交通十字路口，单轨火车的拨道岔口1、两种形式的制约关系、两种形式的制约关系第二章 进 程 管 理 临界资源：临界资源：在一段时间内只允许一个进程访问的资源。临界资源的访问要求互斥的访问。 物理设备，如输入机、打印机、磁带机 软件资源，如公用变量、数据、表格、队列等 为了使多个进程有效地共享临界资源，并使程序的执行具有可再现性，系统必须保证它们互斥地互斥地使用临界资源使用临界资源。2、临界资源、临界资源(Critical Resource) 第二章 进 程 管 理 3、生产者、生产者消费者问题消费者问题放产品放产品取产品取产品一次只能放一个产品；一次只

35、能放一个产品；一次只能取走一个产品；一次只能取走一个产品；缓冲区满则生产者不能放产品；缓冲区满则生产者不能放产品；缓冲区空则消费者不能取产品；缓冲区空则消费者不能取产品；生产者进程生产者进程消费者进程消费者进程并发并发第二章 进 程 管 理 012345 n-1生产者消费者缓冲池inoutcounter数据结构：var n:integer; /*具有n个缓冲区的缓冲池*/ type item=; var buffer:array0,1,n-1 of item; in,out:0,1,n-1; /*指向缓冲区的指针*/ counter:0,1,n; /*缓冲区中的消息数*/3、生产者、生产者消费

36、者问题消费者问题第二章 进 程 管 理 register2:=counter;register2:=register2-1;counter:= register2;producer: repeat producer an item in nextp while counter=n do no-op; bufferin:=nextp; in:=(in+1)mod n counter:=counter+1; until false;consumer: repeat while counter=0 do no-op; nextc:=bufferout; out:=(out+1)mod n count

37、er:=counter-1; consume the item in nextc; until false;说明：nextp:局部变量，用于暂时存放每次生产出的消息。 nextc:局部变量，用于存放每次要消费的消息。register1:=counter;register1:=register1+1;counter:= register1;3、生产者、生产者消费者问题消费者问题inout01234567第二章 进 程 管 理 3、生产者、生产者消费者问题消费者问题register 1:=counter; register 1:=register+1; counter:=register 1; r

38、egister 2:=counter；register 2: =register 2 -1;counter:= register 2 按什么顺序执行时，按什么顺序执行时，counter的值是的值是6？register 1:=counter;register 1:=register 1+1;register 2:=counter;register 2:=register 2-1;counter:=register 2;counter:=register 1;register 1=5register 1=6register 2=5register 2=4counter=4counter=6假设假设

39、counter的当前值为的当前值为5为了解决以上问题，可将为了解决以上问题，可将counter作为临界资源作为临界资源第二章 进 程 管 理 不论是硬件临界资源，还是软件临界资源，多个进程不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。必须互斥地对它进行访问。临界区定义：临界区定义：每个进程中访问临界资源的那段代码；4、临界区、临界区(critical section) P1P2P3临界区临界区临界区临界区临界区临界区第二章 进 程 管 理 4、临界区、临界区(critical section) repeatentry sectionexit sectioncritica

40、l sectionremainder section;until false;用于对临界资源进用于对临界资源进行检查行检查将临界区正被访将临界区正被访问的标志恢复为问的标志恢复为未被访问的标志未被访问的标志第二章 进 程 管 理 (1)空闲让进空闲让进(2) 忙则等待忙则等待 (3) 有限等待有限等待 (4) 让权等待让权等待 5、同步机制应遵循的规则、同步机制应遵循的规则 第二章 进 程 管 理 人与人之间的合作6、牛奶过剩问题、牛奶过剩问题时间时间A先生先生B先生先生3：00看电冰箱，没有牛奶了3：05去商店3：10到达商店看电冰箱，没有牛奶了3：15买牛奶去商店3：20回家，将牛奶拿出到

41、达商店3：25买牛奶3：30回家，将牛奶拿出第二章 进 程 管 理 使用便条避免购买太多的牛奶 在去购买前留下一张便条（类似“加锁”） 购买回来后拿走便条（类似“解锁”） 如果看到便条则不去购买（等待） 假定用一台计算机去实现这项工作：if (noMilk) if (noNote) leave Note;buy milk;remove note;6、牛奶过剩问题、牛奶过剩问题解决方案解决方案1结果会是什么呢？结果会是什么呢？第二章 进 程 管 理 仍然存在牛奶过剩的情况，但只是偶尔而已6、牛奶过剩问题、牛奶过剩问题解决方案解决方案1间歇性地失败！间歇性地失败！第二章 进 程 管 理 用先放便条

42、的方法试着修正间歇性失败的问题leave Note;if (noMilk) if (noNote) buy milk;remove note; 这时会发生什么？ 很好，对人而言，可能没什么问题 但对计算机而言：就会再也没人去购买牛奶6、牛奶过剩问题、牛奶过剩问题解决方案解决方案1 fix第二章 进 程 管 理 使用带标记的便条 现在我们可以在检查前留下便条6、牛奶过剩问题、牛奶过剩问题解决方案解决方案2这样会正常运转吗？这样会正常运转吗？第二章 进 程 管 理 可能两个线程都不去买牛奶！6、牛奶过剩问题、牛奶过剩问题解决方案解决方案2这种情况称为这种情况称为“饥饿饥饿”第二章 进 程 管 理

43、双便条解决方案 这样会正常运转吗？6、牛奶过剩问题、牛奶过剩问题解决方案解决方案3 在X处 如果没有便条B，A去购买是安全的 否则等待，查找发生什么事情了 在Y处 如果没有便条A，B去购买是安全的 否则，A要么购买，要么等待B退出临界区临界区忙等忙等A的代码不同于的代码不同于B的代码的代码如果如果有很多个线程，那又怎么办呢？有很多个线程，那又怎么办呢？第二章 进 程 管 理 2.3.2 信号量机制信号量机制信号量机制的基本概念 信号量信号量(Semaphores) 信号量机制是进程同步工具 信号量是对具体物理资源的抽象 不同类的资源用不同名称的信号量代表 同类资源的个数用 0的信号量值表示 信

44、号量值为 0 或 1 的信号量表示临界资源第二章 进 程 管 理 信号量：信号量：Dijkstra把整型信号量定义为一个整型量S。 特性：特性：除初始化外，仅能通过两个标准的原子操作原子操作wait(s)（P操作）和signal(s)（V操作）来访问。描述如下： wait(S): while S0 do no-op； S = S 1； signal(S): S = S + 1； 存在问题：存在问题：只要S=0，wait操作就会不断地测试，没能做到“让权等待让权等待” 1、整型信号量、整型信号量第二章 进 程 管 理 引入进程阻塞机制，解决了引入进程阻塞机制，解决了“忙等忙等”问题。问题。 在信

45、号量里增加对阻塞进程的记录在信号量里增加对阻塞进程的记录 在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还增加一个等待队列指针L，记录型的数据结构描述如下： type semaphore = record value: integer; /*代表资源数目*/ L: list of process;/*等待进程链表*/ end2、记录型信号量、记录型信号量第二章 进 程 管 理 2、记录型信号量、记录型信号量 wait(S)和和signal(S)操作描述：操作描述： procedure wait(S) var S: semaphore; begin S.value := S

46、.value 1; if S.value 0 then block(S.L) endprocedure signal(S) var S: semaphore; begin S.value := S.value + 1; if S.value 0时，可进行资源预留 di：申请个数 一次可申请一种资源的多个4、信号量集、信号量集第二章 进 程 管 理 信号量集流程信号量集流程 1 1）将正在执行的进程移入第一）将正在执行的进程移入第一个个S Si i t ti i的等待队列中；的等待队列中；2 2）将程序指针指向该进程中）将程序指针指向该进程中SwaitSwait操作开始处操作开始处4、信号量集、

47、信号量集第二章 进 程 管 理 信号量集流程信号量集流程将与将与S Si i相关的等待队列相关的等待队列中的所有进程移到准备中的所有进程移到准备队列队列4、信号量集、信号量集第二章 进 程 管 理 4、信号量集、信号量集应用应用61A52B41C到达顺序：P1，P2，P3，P4资源申请向量：P1(3,2,1)，P2(2,2,1)，P3(1,1,1)，P4(1,1,1)Var S1,S2,S3:semaphore:=6,5,4;BeginParbeginProcess P1:Swait(S1,1,3,S2,2,2,S3,1,1); use the critical resource;Ssigna

48、l(S1,3,S2,2,S3,1);endProcess P2:Swait(S1,1,2,S2,2,2,S3,1,1); use the critical resource;Ssignal(S1,2,S2,2,S3,1);endProcess P3:Swait(S1,1,1,S2,2,1,S3,1,1); use the critical resource;Ssignal(S1,1,S2,1,S3,1);end四个进程对应的代码段为：四个进程对应的代码段为：第二章 进 程 管 理 4、信号量集、信号量集应用应用61A52B41C到达顺序：P1，P2，P3，P4资源申请向量：P1(3,2,1)，

49、P2(2,2,1)，P3(1,1,1)，P4(1,1,1)Process P4:Swait(S1,1,1,S2,2,1,S3,1,1); use the critical resource;Ssignal(S1,1,S2,2,S3,1);endP1到达333P2到达112P3到达, S2t2阻塞阻塞P4到达, S2t2阻塞阻塞P1执行完成，释放资源433P3 P4都被唤醒322P3 申请到资源P4 申请到资源211第二章 进 程 管 理 (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S

50、, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。 4、信号量集、信号量集特殊情况特殊情况S=2Swait(S,1,0) 临界区临界区P1 P2 P3 PnS=0Swait(S,1,0)临界区临界区P1 P2P3Pn第二章 进 程 管 理 2.3.3 信号量的应用信号量的应用对竞争资源的互斥访问过程1、利用信号量实现进程互斥、利用信号量实现进程互斥第二章 进 程 管 理

51、利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; endparend 1、利用信号量实现进程互斥、利用信号量实现进程互斥wa

52、it(mutex)和和signal(mutex)必须成对出现必须成对出现第二章 进 程 管 理 保证进程间的前驱、后继关系2、利用信号量实现前趋关系、利用信号量实现前趋关系第二章 进 程 管 理 Pi代表进程；Si代表Pi中的语句；s为具有前驱关系的两进程的公用信号量，其初值为0。var s:semaphore:=0;begin parbegin begin S1; signal(s);end; begin wait(s); S2; end; parendendS1S2sp1p22、利用信号量实现前趋关系、利用信号量实现前趋关系第二章 进 程 管 理 2、利用信号量实现前趋关系、利用信号量实现

53、前趋关系S1S2S5S3S4S6abcdgfeVar a,b,c,d,e,f,g: semaphore:=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end; begin wait(a);S2;signal(c);signal(d);end; begin wait(c);S3;signal(e);end; begin wait(d);S4;signal(f);end; begin wait(b);S5;signal(g);end; begin wait(e);wait(f);wait(g);S6;end; parenden

54、d第二章 进 程 管 理 2.3.4 管程机制管程机制信号量同步的缺点信号量同步的缺点 同步操作分散：同步操作分散：信号量机制中，同步操作分散在信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（各个进程中，使用不当就可能导致各进程死锁（如如P P、V V操作的次序错误、重复或遗漏）操作的次序错误、重复或遗漏） 易读性差：易读性差：要了解对于一组共享变量及信号量的要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序操作是否正确，必须通读整个系统或者并发程序 不利于修改和维护：不利于修改和维护：各模块的独立性差，任一组各模块的独立性差，任一组变量或一段代码

55、的修改都可能影响全局变量或一段代码的修改都可能影响全局 正确性难以保证：正确性难以保证：操作系统或并发程序通常很大操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误，很难保证这样一个复杂的系统没有逻辑错误第二章 进 程 管 理 管程：管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块。 管程的组成：管程的组成： 管程的名称 局部于管程内部的共享数据结构说明； 对该数据结构进行操作的一组过程； 对局部于管程内部的共享数据设置初始值的语句。1、管程（、管程（Monitors）的定义）的定义Hansen第二

56、章 进 程 管 理 图图 2-13 管程的示意图管程的示意图 1、管程的定义、管程的定义初始化代码初始化代码一组操作过程一组操作过程共享数据共享数据条件（不忙）队列条件（不忙）队列进入队列进入队列第二章 进 程 管 理 管程的语法：管程的语法： type monitor_name=monitor define ; use ; procedure (); begin end; function (): 值类型; begin end; begin ; end 1、管程的定义、管程的定义管程名：monitor_name局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初

57、始值的语句第二章 进 程 管 理 1、管程的定义、管程的定义 管程的特点：管程的特点： 局部性：局部性：管程内的局部变量只能被局部于管程内的过程所访问；反之亦然，即局部于管程内的过程只能访问管程内的变量； 访问接口：访问接口：任何进程只能通过调用管程提供的过程入口进入管程 互斥性：互斥性：任一时刻，最多只能有一个进程在管程中执行注：注：保证进程互斥地进入管程是由编译器负责的。即管程是一 种编程语言的构件，它的实现需要得到编译器的支持。第二章 进 程 管 理 1、管程的定义、管程的定义 管程的特性（从语言角度看）：管程的特性（从语言角度看）： 模块化：模块化：管程是一个基本程序单位，可以单独编译

58、。 抽象数据类型：抽象数据类型：管程中不仅有数据，而且有对数据的操作。 信息：信息：管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程（函数）的具体实现外部不可见。第二章 进 程 管 理 1、管程的定义、管程的定义 管程和进程的区别：管程和进程的区别： 定义的数据结构：定义的数据结构：进程定义的是私有数据结构PCB；管程定义的是公共数据结构； 数据结构上的操作：数据结构上的操作：进程由顺序程序执行有关操作；管程主要进行同步操作和初始化操作； 设置的目的：设置的目的：设置进程的目的在于实现系统的并发性；管程的设置则是解决共享资源的

59、互斥使用问题； 工作方式：工作方式：进程通过调用管程中的过程对共享数据结构实行操作，因此进程是主动工作方式，管程是被动工作方式； 并发性：并发性：进程之间能并发执行，而管程则不能与其调用者并发； 进程具有动态性，由创建而生，由撤消而亡；而管程是操作系统的一个资源管理模块，供进程调用。第二章 进 程 管 理 实现要素实现要素 管程中的共享变量在管程外部是不可见的，外部只能通过管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的调用管程中所说明的外部过程外部过程（函数）来间接地访问管程（函数）来间接地访问管程中的共享变量；中的共享变量； 为了保证管程共享变量的数据完整性，规定为了保

60、证管程共享变量的数据完整性，规定管程互斥进入管程互斥进入； 管程通常是用来管理资源的，因而在管程中应当设有管程通常是用来管理资源的，因而在管程中应当设有进程进程等待队列等待队列以及相应的以及相应的等待及唤醒操作等待及唤醒操作； 访问控制访问控制 局部于管程内部的数据结构，仅能被局部于管程的过程所局部于管程内部的数据结构，仅能被局部于管程的过程所访问，任何管程外的过程都不能访问它；访问，任何管程外的过程都不能访问它； 局部于管程的过程也仅能访问管程内的数据结构局部于管程的过程也仅能访问管程内的数据结构2、管程的设计与实现、管程的设计与实现第二章 进 程 管 理 管程的设计管程的设计 必须设置同步