第2章进程管理

1、第第2 2章章 进程管理进程管理 （处理机管理）（处理机管理） 操作系统教学网站介绍操作系统教学网站介绍 本章主要内容本章主要内容 2.1 进程的基本概念进程的基本概念 2.2 进程控制进程控制 2.3 进程同步进程同步 2.4 经典进程的同步问题经典进程的同步问题 2.5 进程通信进程通信 2.6 线程线程 本章重点本章重点 进程的定义； 进程的结构特征； 进程控制块的作用； 进程同步的概念 信号量机制； 经典进程的同步问题； 进程通信的类型 什么是线程及为什么要 引入线程 进程同步机制及其应用 本章难点本章难点 本章学习建议：本章学习建议： 在掌握进程及进程同步的基本概念的基础上，熟记在掌

2、握进程及进程同步的基本概念的基础上，熟记 信号量机制的定义；信号量机制的定义； 通过信号量机制的应用及对经典进程同步问题的分通过信号量机制的应用及对经典进程同步问题的分 析，能够解决常见问题的同步析，能够解决常见问题的同步 本章计划学时：12学时 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 2.1.2 前驱图前驱图 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 2.1.4 进程的特征与状态进程的特征与状态 2.1.5 进程控制块进程控制块 2.1 2.1 进程的基本概念进程的基本概念P34P34 本节主要内容： 返回返回 本节学习目标：本节学习目标： 2.1 2.1

3、进程的基本概念进程的基本概念 （1）了解程序的顺序执行及其特征）了解程序的顺序执行及其特征 （2）会利用前驱图描述进程（或程序）的执行）会利用前驱图描述进程（或程序）的执行 （3）掌握程序并发执行的特征）掌握程序并发执行的特征 （4）熟练掌握）熟练掌握 进程的定义、特征及基本状态进程的定义、特征及基本状态 程序本身程序本身是具体代码，不能反映程序的执行过程；是具体代码，不能反映程序的执行过程； 概概 述述 进程进程是抽象的，它是一个结构体，进程记录程序的是抽象的，它是一个结构体，进程记录程序的 开始状态、执行状态、结束状态等开始状态、执行状态、结束状态等。 尤其在多道程序环境中，允许多个程序并

4、发执行，从尤其在多道程序环境中，允许多个程序并发执行，从 而引入进程。而引入进程。 在多道程序环境下，在多道程序环境下，程序程序不能独立运行。作不能独立运行。作 为资源分配和独立运行的基本单位是为资源分配和独立运行的基本单位是进程进程。操操 作系统所有的特征都是基于进程而体现的作系统所有的特征都是基于进程而体现的。 概概 述（续）述（续） 2.1.12.1.1程序顺序执行及其特征程序顺序执行及其特征 1.程序顺序执行程序顺序执行 I1 C1P1I2C2P2 一个程序段的多条语句也有一个执行顺序问题：一个程序段的多条语句也有一个执行顺序问题： S1:a:=x+y S2:b:=a-5 S3:c:=

5、b+1 图图2-1 程序的顺序执行程序的顺序执行 S1S2S3 图图2-2 语句的顺序执行语句的顺序执行 2.程序顺序执行时的特征程序顺序执行时的特征 1） 顺序性：顺序性：每个操作在上一操作结束每个操作在上一操作结束 后开始；后开始； 2） 封闭性：封闭性：程序开始执行，其执行结果程序开始执行，其执行结果 不受外界因素影响；不受外界因素影响； 3）可再现性）可再现性：只要环境和初始条件相同，：只要环境和初始条件相同， 其执行结果一定相同。其执行结果一定相同。 定义：前驱图是一个定义：前驱图是一个有向无循环图有向无循环图（DAG)， 用于描述进程之间执行的前后关系。用于描述进程之间执行的前后关

6、系。 6 7 注意：注意：前驱图中前驱图中不能存在循环不能存在循环。 1 2 3 4 5 2.1.2 前驱图 注意：注意：每个结点可用每个结点可用 于表示一条语句、一于表示一条语句、一 个程序段或进程。结个程序段或进程。结 点间的有向边则表示点间的有向边则表示 在两结点之间存在的在两结点之间存在的 偏序或前驱关系。可偏序或前驱关系。可 用用“ ”表示。表示。 图图2-3 前驱图前驱图 2.1.3 2.1.3 程序并发执行及其特征程序并发执行及其特征 1.程序并发执行程序并发执行 I1I2I3I4 C1 C2C3C4 P1P2P3P4 上图存在下述前驱关系：上图存在下述前驱关系： (Ii,Ci)

7、 , (Ii,Ii+1) , (Ci,Pi) , (Ci,Ci+1) , (Pi,Pi+1) 图图2-4 程序并发执行的前驱图程序并发执行的前驱图 例如，四条语句的程序段：例如，四条语句的程序段： S2:b:=y+4 S3:c:=a+b S4:d:=c+6 图图2-5语句并发执行的前驱图语句并发执行的前驱图 S1 S2 S3S4 显然：显然：S1和和S2可以并发执行。可以并发执行。 S1:a:=x+2 要求：要求：根据给定的描述画出前驱图，并能指出哪些可以根据给定的描述画出前驱图，并能指出哪些可以 并发执行，哪些只能顺序执行。并发执行，哪些只能顺序执行。 前驱图说明前驱图说明 1）程序顺序执行

8、、并发执行均可用前驱图表示；）程序顺序执行、并发执行均可用前驱图表示； 2）在前驱图中）在前驱图中 2结点之间若有结点之间若有-，则必须按此顺序执行；，则必须按此顺序执行； 2结点之间无结点之间无 -，则既可以顺序执行也可以并发执行。，则既可以顺序执行也可以并发执行。 I1I2I3I4 C1 C2C3C4 P1P2P3P4 1）间断性：）间断性： 共享资源共享资源 - 相互制约相互制约 - 执行执行-暂停暂停-执行执行 2.程序并发执行时的特征程序并发执行时的特征 2.程序并发执行时的特征程序并发执行时的特征(续）续） 2）失去封闭性：）失去封闭性： 一个程序的执行受到其他程序的影响一个程序的

9、执行受到其他程序的影响 3）不可再现性）不可再现性 例如：例如：设有两个循环程序设有两个循环程序A 、B共享变量共享变量N，N的初值是的初值是n A：N+1操作；操作； B：先执行：先执行print(N)，再将，再将N置置0（即（即N=0）。）。 A、B并发执行的并发执行的3种情况如下：种情况如下： （1）先执行）先执行A，再执行，再执行B，得到，得到N值分别为：值分别为：n+1，n+1，0。 （2）先执行先执行B，再执行，再执行A，得到，得到N值分别为：值分别为：n，0，1。 （3） 先执行先执行print(N)，再，再A，最后，最后N:=0之间，得到的之间，得到的N值分别为：值分别为： n

10、，n+1，0。 以上情况以上情况OS应避免，所应避免，所 以引入进程同步以引入进程同步 例如：例如： 作业作业A： 需要需要CPU - 25； 需要需要DEV1-5； 需要需要DEV2 -10。 作业作业B：需要：需要CPU- 15； 需要需要DEV1-10； 需要需要DEV2-15。 要求：要求：分别求出分别求出CPU、DEV1、DEV2的使用率。的使用率。 实例：比较顺序执行和并发执行的性能实例：比较顺序执行和并发执行的性能 t(s) t(s) CPU DEV1 DEV2 CPU CPU A 10 15 20 3040 DEV2 CPU DEV 1 DEV2 CPU B 1020 30 4

11、0 25 （1 1）顺序执行顺序执行A A、B B： 图图2-6 顺序环境下的程序执行顺序环境下的程序执行 （2 2）A A、B B并发执行：并发执行： 图图2-7 并发环境下的程序执行并发环境下的程序执行 并发执行时，并发执行时， CPU执行时间不执行时间不 变，但总运行时变，但总运行时 间缩短了。间缩短了。 结论：结论：并发是提高资源利用率的好方法，从而提高并发是提高资源利用率的好方法，从而提高 系统吞吐量，所以程序尽量并发执行。系统吞吐量，所以程序尽量并发执行。 1）串行是顺序执行；串行是顺序执行； 2）并发是交叉使用设备；并发是交叉使用设备； 3）并行使用多个处理机并行使用多个处理机-

12、更快。更快。 2.1.4 2.1.4 进程的特征与状态进程的特征与状态P37P37 1.进程的特征和定义 1）结构特征）结构特征 从结构上看，进程实体是由从结构上看，进程实体是由程序段程序段、数据段数据段及及进程进程 控制块（控制块（PCB）三部分组成三部分组成. -UNIX中将这三部分称为中将这三部分称为“进程映像进程映像”。 创建进程：创建进程：创建进程实体中的进程控制块（创建进程实体中的进程控制块（PCB）。）。 撤销进程：撤销进程：撤销进程实体中的进程控制块（撤销进程实体中的进程控制块（PCB）。）。 2）动态性）动态性 3）并发性）并发性 4）独立性）独立性 5）异步性）异步性 进程

13、的实质是进程的实质是 进程实体的一进程实体的一 次执行过程。次执行过程。 多个进程在一多个进程在一 段时间内同时段时间内同时 运行。运行。 独立运行、独独立运行、独 立分配资源和立分配资源和 独立调度独立调度 按各自独立的、按各自独立的、 不可预知的速度不可预知的速度 向前推进。向前推进。 不同角度的进程定义：不同角度的进程定义：ProcessProcess 进程是程序的一次执行。进程是程序的一次执行。 进程是一个程序及其数据在处理机上顺序执进程是一个程序及其数据在处理机上顺序执 行时所发生的活动。行时所发生的活动。 进程是程序在一个数据集合上的运行过程，进程是程序在一个数据集合上的运行过程，

14、 是系统进行是系统进行资源分配资源分配和和调度调度的独立单位。的独立单位。 进程模型进程模型 “进程进程”是进程实体的运行过程，是系统进行是进程实体的运行过程，是系统进行 资源分配资源分配和和调度调度的一个独立单位。的一个独立单位。 或者：或者：可并发执行的程序在一个数据集合上可并发执行的程序在一个数据集合上 的运行过程。的运行过程。 进程的定义：进程的定义： 程序与进程之间的区别：程序与进程之间的区别： 程序、作业和进程程序、作业和进程 现代操作系统把进程管理进程管理归纳为：“程序程序”成为 “作业作业”进而成为“进程进程”，并被按照一定规则 进行调度。用程序、作业和进程这几个术语定义 了计

15、算机工作过程的不同状态不同状态。 程序是静止的 作业（Job）是程序的另一个状态，是指程序从被 选中运行直到运行结束的整个过程。 例如，打开IE浏览器程序登录Web网站，浏览网页， 最后关闭IE浏览器，在这个过程中，IE浏览器程 序就成为了作业。 显然，所有作业都是程序，但不是所有程序都是 作业。 当一个作业被选中后进入内存运行，这个当一个作业被选中后进入内存运行，这个 作业就成为进程。作业就成为进程。 所有进程都是作业，但不是所有的作业都所有进程都是作业，但不是所有的作业都 是进程。正在运行的程序才是进程。是进程。正在运行的程序才是进程。 作业是介于程序和进程之间的一种状态作业是介于程序和进

16、程之间的一种状态 举例说明三者的关系 一个电台的访谈节目，可以接听听众的电一个电台的访谈节目，可以接听听众的电 话话 收听电台节目的人是收听电台节目的人是“程序程序”，等待和主，等待和主 持人交流的听众是持人交流的听众是“作业作业”，正在与主持，正在与主持 人谈话的听众是人谈话的听众是“进程进程”。 图图2-8 三个进程三个进程 并发执行的图示并发执行的图示 调度程序调度程序; 分配器分配器 图图2-9 2-9 各进程的轨迹各进程的轨迹 图图2-10: 3进程并进程并 发执行发执行 的轨迹的轨迹 2.进程的三种基本状态进程的三种基本状态 1） 就绪（就绪（Ready）状态）状态 2） 执行状态

17、执行状态 3） 阻塞（阻塞（Block）状态）状态 进程因发生进程因发生 某事件而暂某事件而暂 停执行。停执行。 进程分配了除进程分配了除 处理机之外的处理机之外的 所有资源。所有资源。 使进程阻塞的典型事件：请求使进程阻塞的典型事件：请求I/O、 申请缓冲空间、等待其它进程传申请缓冲空间、等待其它进程传 数据等。数据等。 执行执行 就绪就绪 阻塞阻塞 图图2-11 2-11 进程的进程的3 3状态转换状态转换 I/O请求请求 时间片用完时间片用完 （中断）（中断） 调度调度 I/O完成完成 进程转换进程转换 1 1）就绪）就绪 - - 执行执行 -调度程序选择一个新的进程运行。调度程序选择一

18、个新的进程运行。 2 2）执行）执行 - - 就绪（产生中断）就绪（产生中断） 执行进程用完了时间片；执行进程用完了时间片； 执行进程被中断，因为一高优先级进程处于就执行进程被中断，因为一高优先级进程处于就 绪状态；绪状态； 有一个更短的作业到来。有一个更短的作业到来。 3 3）执行）执行 - - 阻塞阻塞 当一进程必须等待时当一进程必须等待时 OSOS尚未完成服务尚未完成服务 对一资源的访问尚不能进行对一资源的访问尚不能进行 初始化初始化I/O I/O 且必须等待结果且必须等待结果 等待某一进程提供输入等待某一进程提供输入 (IPC)(IPC) 4 4）阻塞）阻塞 - - 就绪就绪 当所阻塞

19、的事件发生时当所阻塞的事件发生时 进程转换进程转换 3. 3. 进程的挂起状态进程的挂起状态 1)引入挂起状态的原因引入挂起状态的原因 终端用户的需要终端用户的需要 父进程的请求父进程的请求 操作系统的需要操作系统的需要 负荷调节的需要负荷调节的需要 由活动到由活动到 静止，由静止，由 内存到外内存到外 存存 图图2-12 进程的进程的4状态转换状态转换 2）进程状态的转换）进程状态的转换-有挂起状态有挂起状态 状态转换状态转换 ( (中级调度中级调度) ) 活动阻塞活动阻塞 -静止阻塞静止阻塞 静止阻塞静止阻塞 - - 活动阻塞活动阻塞 静止就绪静止就绪-活动就绪活动就绪 当内存中没有就绪进

20、程时当内存中没有就绪进程时 活动就绪活动就绪-静止就绪静止就绪 ( (较少见较少见) ) 当没有被阻塞的进程，而为了性能上的考虑，必须当没有被阻塞的进程，而为了性能上的考虑，必须 释放一些内存时。释放一些内存时。 4.创建（创建（New）状态和终止状态）状态和终止状态 2）终止状态：）终止状态：先等先等OS进行善后处理，再将进行善后处理，再将 进程的进程的PCB空间返还给系统。空间返还给系统。 OS OS 已完成为创建一进程所必要的工作已完成为创建一进程所必要的工作 已构造了进程标识符已构造了进程标识符 已创建了管理进程所需的表格已创建了管理进程所需的表格 但还没有允许执行该进程但还没有允许执

21、行该进程 ( (尚未同意尚未同意) ) 因为资源有限因为资源有限 1）创建（）创建（New）状态：）状态： 一个进程刚刚建立，还一个进程刚刚建立，还 未将它送入就绪队列时的状态。未将它送入就绪队列时的状态。 图图2-13 进程的进程的5状态转换模型状态转换模型 图图2-14 2-14 进程的进程的7 7状态转换模型状态转换模型 活动活动 挂起挂起 事件事件 发生发生 事件事件 发生发生 等待等待 事件事件 挂起挂起 调度调度 超时超时 释放释放 活动活动 挂起挂起 2.1.5 2.1.5 进程控制块进程控制块PCBPCB 进程控制块进程控制块PCB是进程实体的一部分，是操作系统中是进程实体的一

22、部分，是操作系统中 最重要的记录型数据结构。最重要的记录型数据结构。 PCB是进程存在的唯一标志是进程存在的唯一标志。 PCB必须常驻内存。必须常驻内存。 PCB是是OS中最重要的数据结构，中最重要的数据结构， 涉及调度、资源涉及调度、资源 分配、中断处理等。分配、中断处理等。 为了描述和控制进程的运行，系统为为了描述和控制进程的运行，系统为每个进程定义了一个每个进程定义了一个 数据结构数据结构进程控制块进程控制块PCB 当当OS要调度某进程执行时，要先从该进程的要调度某进程执行时，要先从该进程的PCB中查出中查出 其现行状态及优先级；其现行状态及优先级； 在调度到某进程后，要根据其在调度到某

23、进程后，要根据其PCB中所保存的处理机状中所保存的处理机状 态信息，设置该进程恢复运行的现场，并根据其态信息，设置该进程恢复运行的现场，并根据其PCB中中 的程序和数据的内存始址，找到其程序和数据；的程序和数据的内存始址，找到其程序和数据； 进程在执行过程中，当需要和与之合作的进程实现同步、进程在执行过程中，当需要和与之合作的进程实现同步、 通信或访问文件时，也都需要访问通信或访问文件时，也都需要访问PCB； 当进程由于某种原因而暂停执行时，又须将其断点的处当进程由于某种原因而暂停执行时，又须将其断点的处 理机环境保存在理机环境保存在PCB中。中。 1 1、PCBPCB的作用的作用 2. PC

24、B2. PCB中的信息中的信息 1）进程标识符信息：）进程标识符信息： 内部标识符：为方便系统使用而设置内部标识符：为方便系统使用而设置 的序号，用整数表示。的序号，用整数表示。 外部标识符：由创建者提供，用户访外部标识符：由创建者提供，用户访 问该进程时使用。问该进程时使用。 2)处理机状态信息：处理机状态信息：有处理机的各寄存器中有处理机的各寄存器中 的内容组成。的内容组成。 3)进程进程调度调度信息信息 进程状态进程状态 进程优先级进程优先级 进程调度所需的其它信息，它们与进程调度所需的其它信息，它们与 所采用的调度算法有关。所采用的调度算法有关。 事件：事件：有执行状态转为阻塞状态所有

25、执行状态转为阻塞状态所 等待发生的事件，即阻塞原因。等待发生的事件，即阻塞原因。 4)进程控制信息进程控制信息 程序和数据的地址程序和数据的地址 进程同步和通信机制进程同步和通信机制 资源清单资源清单 链接指针链接指针 3.PCB3.PCB的组织方式的组织方式 PCB表：表：系统把所有系统把所有PCB组织在一起，并把它们放在内组织在一起，并把它们放在内 存的固定区域，就构成了存的固定区域，就构成了PCB表。表。 PCB表的大小表的大小决定了系统中最多可同时存在的进程个数，决定了系统中最多可同时存在的进程个数， 称为系统的并发度（注：多道程序中的多道与系统并发称为系统的并发度（注：多道程序中的多

26、道与系统并发 度不同）度不同） PCB表组织成进程队列：表组织成进程队列：不同状态进程分别组成队列。不同状态进程分别组成队列。 如：运行队列、就绪队列、等待队列等。如：运行队列、就绪队列、等待队列等。 PCBPCB的组织方式的组织方式 1 1）线性方式）线性方式 ：进程较少适用。：进程较少适用。 2 2）索引方式：）索引方式：对具有相同状态的进程，分别设置对具有相同状态的进程，分别设置 各自的各自的PCBPCB索引表，表明索引表，表明PCBPCB在在PCBPCB表中的地址。表中的地址。 3 3）链接方式链接方式 索引方式、链接方式索引方式、链接方式-进程较多适用进程较多适用 缺点：需要扫描整个

27、表。如图：缺点：需要扫描整个表。如图： PCB 1 PCB 2 PCB 3 PCB 4 . PCB n 将所有的将所有的PCB部分状态组织在一个连续表（部分状态组织在一个连续表（PCB表）中。表）中。 该方式的优点是简单，且不需要额外的开销，适用于数目不该方式的优点是简单，且不需要额外的开销，适用于数目不 是很多的系统。如是很多的系统。如UNIX系统系统 1.1.线性方式线性方式 2. 2. 索引方式索引方式 对于具有相同状态的进程，分别设置各自的对于具有相同状态的进程，分别设置各自的 PCBPCB索引表，表目为索引表，表目为PCBPCB在在PCBPCB表（线性表）中的表（线性表）中的 地址，

28、就构成了就绪索引表和等待索引表地址，就构成了就绪索引表和等待索引表. . 执行指针执行指针 就绪表指针就绪表指针 等待表指针等待表指针 . PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCBn-1 PCBn 就绪索引表就绪索引表 等待索引表等待索引表 如图：如图： 3.3.链接方式链接方式 对于具有相同状态的进程的对于具有相同状态的进程的PCBPCB，通过，通过PCBPCB链链 接字构成一个队列（链接字是指出本队列下一接字构成一个队列（链接字是指出本队列下一 PCBPCB在在PCBPCB表中的编号或地址）编号为表中的编号或地址）编号为0 0表示队尾，表示队尾， 队首由内存固定单

29、元中相应的队列指针表示。如队首由内存固定单元中相应的队列指针表示。如 此就形成了就绪队列和等待队列。此就形成了就绪队列和等待队列。 2.2 2.2 进程控制进程控制P43P43 2.2.1 进程的创建进程的创建 2.2.2 进程的终止进程的终止 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒 2.2.4 进程的挂起与激活进程的挂起与激活 本节学习目标本节学习目标: (1)掌握处理机的两种执行状态；掌握处理机的两种执行状态； (2)熟记原语的定义；熟记原语的定义； (3)了解进程的创建和终止原因；了解进程的创建和终止原因； (4)了解进程的阻塞与唤醒过程；了解进程的阻塞与唤醒过程； (5)了解进程

30、的挂起与激活过程。了解进程的挂起与激活过程。 通常将处理机的执行状态分成通常将处理机的执行状态分成系统态系统态和和用户态用户态。 OS内核内核通常是运行在通常是运行在系统态系统态的；的； 而进程控制是由而进程控制是由OS内核实现内核实现的。的。 （1）系统态：）系统态：又称为核心态、管态。它具有较高的特权，又称为核心态、管态。它具有较高的特权， 能执行一切指令，访问所有寄存器和存储区。能执行一切指令，访问所有寄存器和存储区。 （2）用户态：）用户态：又称目态。具有较低特权的执行状态，它只又称目态。具有较低特权的执行状态，它只 能执行规定的指令，访问指定的寄存器和存储区。能执行规定的指令，访问指

31、定的寄存器和存储区。 概概 述述 操作系统内核操作系统内核 通常将一些与硬件紧密相关的模块如中断处理程序、各通常将一些与硬件紧密相关的模块如中断处理程序、各 种常用设备的驱动程序、运行频率较高的模块等都安排种常用设备的驱动程序、运行频率较高的模块等都安排 在紧靠硬件的软件层次中，并使它们常驻内存，以便提高在紧靠硬件的软件层次中，并使它们常驻内存，以便提高 操作系统的运行效率，并对它们加以特殊的保护。操作系统的运行效率，并对它们加以特殊的保护。 -通常把这一部分称为通常把这一部分称为OS的内核。的内核。 操作系统内核常驻内存：低址部分（如显示器、键操作系统内核常驻内存：低址部分（如显示器、键 盘

32、驱动程序）。盘驱动程序）。 内核通常是一些原语，原语是通过内核通常是一些原语，原语是通过屏蔽中断屏蔽中断来实现的。来实现的。 原原 语语 是由若干条指令组成的，是用于完成一定功能的一个过程。是由若干条指令组成的，是用于完成一定功能的一个过程。 原语是原子操作：原语是原子操作：一个操作中的所有动作要么全做，要么一个操作中的所有动作要么全做，要么 全不做。（操作不可中断）全不做。（操作不可中断） 原子操作在系统态下执行，常驻内存。原子操作在系统态下执行，常驻内存。 原语的作用原语的作用是为了实现进程的通信和控制，系统对进程的是为了实现进程的通信和控制，系统对进程的 控制如不使用原语会造成其状态的不

33、确定性，达不到进程控制如不使用原语会造成其状态的不确定性，达不到进程 控制的目的。控制的目的。 2.2.1 2.2.1 进程的创建进程的创建 1.进程进程 图图 A B C DEF G H 进程树进程树 注意：注意： 1）子进程可以继承父进程的所有资源。子进程可以继承父进程的所有资源。 2）根进程是由引导进程创建的。根进程是由引导进程创建的。 3）撤销父进程时必须回收资源，否则子进程撤销父进程时必须回收资源，否则子进程 游离不可控，引起资源浪费，太多子进程游离不可控，引起资源浪费，太多子进程 游离会引起死锁。游离会引起死锁。 2.引起创建进程的事件引起创建进程的事件 1) 用户登录用户登录 2

34、) 作业调度作业调度 3) 提供服务提供服务 4) 应用请求应用请求 3.进程的创建进程的创建 由创建原语由创建原语Creat()完成，具体如下：完成，具体如下： （1）申请空白申请空白PCB （2）为新进程分配资源为新进程分配资源 （3）初始化进程控制块，初始化进程控制块，主要主要包括包括： 初始化标识符信息；初始化标识符信息； 初始化处理机状态信息；初始化处理机状态信息； 初始化处理机控制信息初始化处理机控制信息 （4）将新进程插入就绪队列（就绪状态）将新进程插入就绪队列（就绪状态） 2.2.2 2.2.2 进程的终止进程的终止 1.引起进程终止的事件引起进程终止的事件 1） 正常结束（调

35、用正常结束（调用Halt指令）指令） 2） 异常结束异常结束 3） 外界干预外界干预 包括：包括：（ （1）操作员或操作系统干预）操作员或操作系统干预 如发生死锁如发生死锁 （2）父进程请求）父进程请求 （3）父进程终止）父进程终止 异异 常常 事事 件件 （1）越界错误。越界错误。 （2）保护错。保护错。 如试图去写一个只读文件。如试图去写一个只读文件。 （3）特权指令错。特权指令错。 （4）非法指令错。非法指令错。 （5）运行超时。运行超时。 （6）等待超时。等待超时。 （7）算术运算错。算术运算错。 （8）I/O故障。故障。 2.进程的终止过程进程的终止过程 （1）根据被终止进程的标识符

36、，从根据被终止进程的标识符，从PCB集合中检索出该集合中检索出该 进程的进程的PCB，从中读出该进程的状态；，从中读出该进程的状态； （2）若被终止进程正处于执行状态，应立即终止该进程的若被终止进程正处于执行状态，应立即终止该进程的 执行，执行，并设置调度标志为真并设置调度标志为真，用于指示该进程被终止后应，用于指示该进程被终止后应 重新进行调度，选择一新进程，把处理机分配给它。重新进行调度，选择一新进程，把处理机分配给它。 （3）若该进程还有子孙进程，还应将其子孙进程予以终止，若该进程还有子孙进程，还应将其子孙进程予以终止， 以防它们不可控。以防它们不可控。 （4）将该进程所拥有的全部资源，

37、或者归还给其父进程，将该进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。或者归还给系统。 （5）将被终止进程从所在队列中移出，等待其它程序来将被终止进程从所在队列中移出，等待其它程序来 收集信息。收集信息。 2.进程的终止过程（续）进程的终止过程（续） 2.2.3 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒 1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 1） 请求系统服务请求系统服务 2） 启动某种操作启动某种操作 3） 新数据尚未到达新数据尚未到达 4） 无新工作可做无新工作可做 2 .2 .进程阻塞过程进程阻塞过程(block)(block) 进程的阻塞是进程自身的一

38、种主动行为。进程的阻塞是进程自身的一种主动行为。 阻塞过程阻塞过程： （1）将）将PCB中的中的“执行执行”改为改为“阻塞阻塞”，插入到阻塞队列；，插入到阻塞队列； （2）重新调度，将处理机分配给另一就绪进程，并进行切换。）重新调度，将处理机分配给另一就绪进程，并进行切换。 3.3.进程唤醒过程进程唤醒过程(wakeup)(wakeup) 唤醒过程：唤醒过程： 1）把被阻塞进程从等待该事件的阻塞队列中移，把被阻塞进程从等待该事件的阻塞队列中移， 将其将其PCB中的现行状态，由阻塞改为就；中的现行状态，由阻塞改为就； 2）将该进程插入到就绪队列中。将该进程插入到就绪队列中。 BlockBlock

39、原语和原语和WakeupWakeup原语原语: : Block原语和原语和Wakeup是一对作用相反的原语；是一对作用相反的原语； 若在某进程中调用了阻塞原语，则必须在若在某进程中调用了阻塞原语，则必须在 与之合与之合 作的另一进程中安排唤醒源于来唤醒阻塞的进程；作的另一进程中安排唤醒源于来唤醒阻塞的进程； 否则：否则：被阻塞的进程将会因不能被唤醒而长期处于被阻塞的进程将会因不能被唤醒而长期处于 阻塞状态，从而无法继续运行。阻塞状态，从而无法继续运行。 2.2.4 2.2.4 进程的挂起与激活进程的挂起与激活 1. 进程的挂起过程进程的挂起过程(suspend) 当出现引起进程挂起的事件时，进

40、程将自己挂起，过程如下：当出现引起进程挂起的事件时，进程将自己挂起，过程如下： 1）检查被挂起进程的状态，若正处于活动就绪状态，便将其检查被挂起进程的状态，若正处于活动就绪状态，便将其 改为静止就绪；将活动阻塞改为静止阻塞。改为静止就绪；将活动阻塞改为静止阻塞。 2）将该进程的将该进程的PCB复制到指定的内存区域。复制到指定的内存区域。 3）如被挂起的进程正在执行，则重新调度。如被挂起的进程正在执行，则重新调度。 2. 进程的激活过程进程的激活过程(active) 当发生激活进程的事件时，进程激活过程如下：当发生激活进程的事件时，进程激活过程如下： 1）将进程从外存调入内存，检查该进程的现行状

41、态；将进程从外存调入内存，检查该进程的现行状态； 2）假如采用抢占调度策略，则应检查是否重新调度假如采用抢占调度策略，则应检查是否重新调度。 本节主要内容：本节主要内容： 2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念 2.3.2 2.3.2 信号量机制信号量机制 2.3.3 2.3.3 信号量的应用信号量的应用 2.3.4 2.3.4 管程机制管程机制 2.3 2.3 进程同步进程同步P47P47 本节学习目标本节学习目标: (1)熟练掌握进程同步的基本概念；熟练掌握进程同步的基本概念； (2)掌握信号量机制；掌握信号量机制； (3)掌握信号量的应用；掌握信号量的应用； (4)

42、了解管程机制。了解管程机制。 返回返回 首先回顾进程的一个特征：首先回顾进程的一个特征：异步性异步性（每个（每个 进程按照各自的速度向前推进）进程按照各自的速度向前推进） 并发进程的异步性会使得进程的执行结果并发进程的异步性会使得进程的执行结果 具有不可再现性具有不可再现性 解决的机制：解决的机制：进程同步进程同步 概概 述述 在在OS引入进程后，虽然提高了资源的利用率和系引入进程后，虽然提高了资源的利用率和系 统的吞吐量，但由于统的吞吐量，但由于进程的异步性进程的异步性，也会给系统，也会给系统 造成混乱，尤其是在他们争用临界资源时。造成混乱，尤其是在他们争用临界资源时。 例例1：当多个进程去

43、争用一台打印机时，有可能当多个进程去争用一台打印机时，有可能 使多个进程的输出结果交织在一起，难于区分。使多个进程的输出结果交织在一起，难于区分。 例例2：当多个进程去争用共享变量、表格、链表当多个进程去争用共享变量、表格、链表 时，有可能致使数据处理出错。时，有可能致使数据处理出错。 -用进程同步解决。用进程同步解决。 概概 述述 实例1 某储户分别使用银行卡和存折同时在某储户分别使用银行卡和存折同时在ATMATM和柜台办和柜台办 理两笔存款业务，银行卡存理两笔存款业务，银行卡存20002000元，元，ATMATM存存10001000元；元； 该储户账户原有该储户账户原有50005000元；

44、元； 由两个进程负责办理这两笔业务，分别将余额修改由两个进程负责办理这两笔业务，分别将余额修改 为为70007000（5000+20005000+2000）和和60006000（5000+10005000+1000）； 最后，储户的账户余额可能是最后，储户的账户余额可能是70007000，也可能是，也可能是60006000 （看哪个执行的慢），显然不正确（正确余额应该（看哪个执行的慢），显然不正确（正确余额应该 为为80008000），），储户吃亏储户吃亏； 如果是取钱呢？如果是取钱呢？ 其原因是两个进程同时修改同一数据，而没有进行其原因是两个进程同时修改同一数据，而没有进行 有效控制；有效控

45、制； 正确的做法：一次仅允许一个进程完成读数据和修正确的做法：一次仅允许一个进程完成读数据和修 改数据（储户账户作为临界资源）改数据（储户账户作为临界资源） 进程同步的主要任务进程同步的主要任务P47 : : 1) 1) 对多个相关进程在对多个相关进程在执行次序执行次序上进行协调上进行协调; ; 2) 2) 使并发执行的诸进程之间能有效地使并发执行的诸进程之间能有效地共享资共享资 源源和和相互合作相互合作; ; 3) 3) 使程序的执行具有使程序的执行具有可再现性可再现性。 1. 1. 两种形式的制约关系两种形式的制约关系 （1 1）相关进程与无关进程）相关进程与无关进程 相关进程：相关进程：

46、指多个并发进程在逻辑上有某指多个并发进程在逻辑上有某 种联系。种联系。 无关进程无关进程：在逻辑上无任何联系的进程。：在逻辑上无任何联系的进程。 2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念 间接相互制约关系：间接相互制约关系：进程间要通过某种中介发生联进程间要通过某种中介发生联 系，是无意识安排的，可发生在相关进程之间，也系，是无意识安排的，可发生在相关进程之间，也 可发生在无关进程之间可发生在无关进程之间（共享资源，如（共享资源，如CPUCPU、I/OI/O）。 直接相互制约关系：直接相互制约关系： 进程间的相互联系是有意识的进程间的相互联系是有意识的 安排的，直接作用只发

47、生在相关进程间安排的，直接作用只发生在相关进程间（相互合（相互合 作）。作）。 （2 2）并发进程的制约关系）并发进程的制约关系 （1 1）进程的同步（直接相互制约关系）进程的同步（直接相互制约关系） 进程的同步：进程的同步：指系统中多个进程中发生的事件指系统中多个进程中发生的事件 存在某种存在某种时序时序关系，需要相互合作，共同完成关系，需要相互合作，共同完成 一项任务。一项任务。 实例：实例： 说明：互斥是一种特殊的同步说明：互斥是一种特殊的同步 司机司机 P1 售票员售票员 P2 while (true) while (true) 启动车辆；启动车辆； 关门；关门； 正常运行；正常运行；

48、 售票；售票； 到站停车；到站停车； 开门；开门； 直接相互制约关系的具体实例：直接相互制约关系的具体实例： 关门关门启动启动 停车停车开门开门 同步：按照固定的次序同步：按照固定的次序 定义：定义：由于各进程要求共享资源，而有些由于各进程要求共享资源，而有些 资源需要资源需要互斥使用互斥使用，因此各进程间竞争使，因此各进程间竞争使 用这些资源。用这些资源。 -进程的这种关系为进程的这种关系为进程的互斥进程的互斥。 （2 2）进程的互斥（间接相互制约关系）进程的互斥（间接相互制约关系） a := a -1 print (a) a := a +1 print (a) P1 互斥互斥 P2 互斥互

49、斥 If a 0 then a := a +1 else a:= a-1 P3 互斥互斥 进程的互斥举例：在进程的互斥举例：在3个进程中，个进程中，a 是临界资源是临界资源 进程互斥：进程互斥：是指分布在不同进程之间的若干是指分布在不同进程之间的若干程序程序 片断片断，当，当某个进程某个进程运行其中一个程序片段运行其中一个程序片段时时，其，其 它进程不能运行，只能等到它进程不能运行，只能等到该进程该进程运行完这个程运行完这个程 序片段后才可以运行；序片段后才可以运行； 进程同步：进程同步：是指分布在不同进程之间的若干程序是指分布在不同进程之间的若干程序 片断，它们的运行必须严格按照规定的某种片

50、断，它们的运行必须严格按照规定的某种先后先后 次序运行次序运行，这种先后次序依赖于要完成的特定的，这种先后次序依赖于要完成的特定的 任务。任务。 注意：进程同步与进程互斥的关系注意：进程同步与进程互斥的关系 临界资源互斥访问： 例如：例如：A，B两个程序共享变量两个程序共享变量n，A对对n执行加执行加1操作，操作，B对对 n执行减执行减1操作，用机器语言实现：操作，用机器语言实现： A：register1:=n;（a1） register1:= register1+1;（a2） n:= register1;(a3) 临界资源：临界资源：（定义见（定义见P16) 描述：描述：系统中某些资源一次只

51、允许一个进程使用，称这系统中某些资源一次只允许一个进程使用，称这 样的资源为样的资源为临界资源临界资源或或互斥资源互斥资源 2.临界资源 设当前设当前n的值为的值为5，由于，由于A，B异步运行，可能会异步运行，可能会 产生序列：产生序列：a1,a2,b1,b2,a3,b3-执行结果为执行结果为4。 而先而先A、后、后B的正确答案是的正确答案是5。 因此必须因此必须互斥地互斥地访问访问n ！ B：register2:=n;(b1) register2:= register2-1;(b2) n:= register2;(b3) 临界区是临界区是一个程序片段的集合，这些程序片段一个程序片段的集合，这

52、些程序片段 可以分散在不同的进程中，对某个共享的数据可以分散在不同的进程中，对某个共享的数据 结构（共享资源）进行操作。结构（共享资源）进行操作。 或者或者：把每个进程中访问临界资源的那段代码把每个进程中访问临界资源的那段代码 称为临界区。称为临界区。（简称（简称CS) 3.3.临界区（临界区（CSCS，互斥区）：，互斥区）：critical section 3.临界区（临界区（CS） 结论：结论：若能保证每个进程互斥的进入自己若能保证每个进程互斥的进入自己 的临界区，便可实现各个进程对的临界区，便可实现各个进程对临界资源临界资源 的互斥访问。的互斥访问。 每个进程互斥的进入自己的临界区的方法

53、：每个进程互斥的进入自己的临界区的方法： 每个进程在进入临界区之前，先对欲访问的每个进程在进入临界区之前，先对欲访问的 临界资源进行检查，看它是否正被访问。临界资源进行检查，看它是否正被访问。 一个访问临界资源的循环进程描述如下（格式）：一个访问临界资源的循环进程描述如下（格式）： repeat Entry section Critical Section; Exit section Remainder section; until false; -进入区进入区 -临界区（临界区（CS） -退出区退出区 -剩余区剩余区 4. 同步机制应遵循的原则同步机制应遵循的原则 空闲让进空闲让进 忙则等待

54、忙则等待 有限等待有限等待 让权等待让权等待 为实现为实现进程进程互斥地进入自己的互斥地进入自己的临界区临界区，在系统中设置专门，在系统中设置专门 同步机构来协调各进程间的运行。同步机构来协调各进程间的运行。 所有同步机制都应遵循下述四条准则：所有同步机制都应遵循下述四条准则： 2.3.2 2.3.2 信号量机制信号量机制 信号量机制是行之有效的信号量机制是行之有效的进程同步工具进程同步工具 学习时注意：学习时注意： 1 1）各种信号量的定义各种信号量的定义 2 2）信号量的应用：）信号量的应用：解决同步问题和互斥解决同步问题和互斥 问题问题. . 整型信号量定义为一个整型量，除初始化外初始化

55、外，仅能通过两 个标准的原子操作wait(s)wait(s)和和signal(s)signal(s)来访问，通常称为 P、V操作 wait(s)：while s=0 do no_op s:=s-1; signal(s)：s:=s+1; 1.整型信号量 早期早期OS常用常用 P 操作操作 V 操作操作 2 2）信号量的使用：信号量的使用： 必须置一次且只能置一次初值，并且初值不必须置一次且只能置一次初值，并且初值不 能为负数。能为负数。 只能执行只能执行P P、V V操作操作。 整型信号量的缺点：整型信号量的缺点：未遵循同步机制的未遵循同步机制的“让权等让权等 待待”，一直判断是否处理完，占用处

56、理机。，一直判断是否处理完，占用处理机。 1 1）P P、V V操作为原语操作操作为原语操作-不可中断不可中断 说明：说明： 2.记录型信号量 记录型信号量机制的提出是为了解决整型信号量机制记录型信号量机制的提出是为了解决整型信号量机制 不遵循不遵循“让权等待让权等待”这一准则。这一准则。 记录型信号量采用记录型信号量采用记录型的数据结构记录型的数据结构，描述如下：描述如下： type semaphore=record value:integer; L:list of process; end 资源信号量值资源信号量值 进程等待队列进程等待队列 procedure wait(S) var S:

57、semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L) end procedure signal(S) var S:semaphore; begin S.value:=S.value+1; if S.value0S.value0表示有表示有S.valueS.value个资源可用个资源可用; ; S.value=0S.value=0表示无资源可用表示无资源可用. . P.VP.V操作讨论操作讨论 P(S)P(S)：表示申请一个资源表示申请一个资源 V(S)V(S)：表示释放一个资源。表示释放一个资源。 若若S.value0

58、S.value0，则，则| S .value| S .value|表示表示S S等待队列中的进程个数。等待队列中的进程个数。 2）P.V操作的优缺点操作的优缺点 优点：优点：简单，而且表达能力强简单，而且表达能力强（用（用P.V操作可解操作可解 决任何同步互斥问题）决任何同步互斥问题） 缺点：缺点：不够安全；不够安全；P.V操作使用不当会出现操作使用不当会出现死锁死锁； 遇到复杂同步互斥问题时实现复杂遇到复杂同步互斥问题时实现复杂. 3.AND型信号量 设有两个进程设有两个进程A和和B，它们都要求访问共享数据，它们都要求访问共享数据D和和E。因此设。因此设 两个互斥的信号量两个互斥的信号量Dm

59、utex和和Emutex，令初值为，令初值为1。则有：。则有： process A: wait(Dmutex); wait(Emutex); process B: wait(Emutex); wait(Dmutex); 若进程A和B按下述次序交替执行wait操作： process A:wait(Dmutex); process B: wait(Emutex); process A: wait(Emutex); process B: wait(Dmutex); 产生死锁。产生死锁。 将进程在整个运行过程中需要的所有资源，一次性全部将进程在整个运行过程中需要的所有资源，一次性全部 地分配给进程，待

60、进程使用完后再一起释放。只要尚有地分配给进程，待进程使用完后再一起释放。只要尚有 一个资源未能分配给进程，其它所有可能为之分配的资源，一个资源未能分配给进程，其它所有可能为之分配的资源， 也不分配给它。也不分配给它。 ANDAND同步机制的基本思想是：同步机制的基本思想是： place the process in the waiting queue associated with the first Si found with Si= ti；即当资源 数量低于ti时，便不予分配） 占用值为占用值为d di i（表示资源的申请量，即Si = Si - di） 对应的P、V原语格式为： Swai