课件第二章进程管理

1、 Process Management 在传统操作系统中，资源分配和独立运行的基本单在传统操作系统中，资源分配和独立运行的基本单位是位是。OSOS的四大特征也都是基于进程而形成的。的四大特征也都是基于进程而形成的。 的主要功能是把处理机分配给进程以及协的主要功能是把处理机分配给进程以及协调各个进程之间的相互关系。由调各个进程之间的相互关系。由进程调度进程调度程序和程序和进程控进程控制制程序两部分内容组成。程序两部分内容组成。 第二章第二章 进程管理进程管理 进程的基本概念进程的基本概念 进程控制进程控制 进程同步进程同步 经典进程同步问题经典进程同步问题 管程机制管程机制 进程通信进程通信 线

2、程线程第二章第二章 进程管理进程管理2.1 2.1 进程的基本概念进程的基本概念 The basic concept of process一、前趋图一、前趋图 (Precedence Graph) 有向有向（DAG）。结点表示一条语句、一个程序段）。结点表示一条语句、一个程序段或进程。或进程。 结点间的有向边表示结点间存在的结点间的有向边表示结点间存在的偏序偏序(Partial Relation)或前趋关系或前趋关系(Precedence Relation) ” 。 例：例：Fig2-1 前趋图示例前趋图示例第二章第二章 进程管理进程管理 二、程序顺序执行二、程序顺序执行(Sequential

3、 Execution of Program) 程序执行时，仅当前一操作完成后，才能执行后继操作。程序执行时，仅当前一操作完成后，才能执行后继操作。2.1 2.1 进程的基本概念进程的基本概念 The basic concept of processC1P1I2C2P2I1特点：特点：顺序性顺序性(Sequential) 封闭性封闭性(Closeness)（只有程序本身的动作才能改变运行环境）只有程序本身的动作才能改变运行环境） 可再现性可再现性(Recurrence) 第二章第二章 进程管理进程管理三、程序并发执行三、程序并发执行(Concurrent Execution of Program

4、 )1 思想：思想：以输入、计算、打印三个操作为例：以输入、计算、打印三个操作为例： 对于某一作业的三个操作必存在顺序关系，但多个作对于某一作业的三个操作必存在顺序关系，但多个作业之间并不一定。其前趋图可表示为：业之间并不一定。其前趋图可表示为： I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 由此图可以看出，多个此类作业是可以并发执行的。由此图可以看出，多个此类作业是可以并发执行的。2.1 2.1 进程的基本概念进程的基本概念 The basic concept of process第二章第二章 进程管理进程管理 例：例：s1：a:=x+2 s2：b:=y+1 s3：

5、 c:=a+b s4：d:=c+6 S1S4S3S22 特征特征：间断性；：间断性； 失去封闭性；失去封闭性； 不可再现性。不可再现性。S1、S2可并发执行可并发执行第二章第二章 进程管理进程管理例：有程序例：有程序A：N=N+1； B: print(N)； N=0；设某时刻；设某时刻N的初值为的初值为n，则：则：若：若：N=N+1；PRINT(N)； N=0 若：若：PRINT(N)；N=N+1；N=0若：若：PRINT(N)；N=0；N=N+1不可再现性举例不可再现性举例N变化结果为：变化结果为：n+1 n+1 0N变化结果为：变化结果为：n n+1 0N变化结果为：变化结果为：n 0 1

6、第二章第二章 进程管理进程管理2.1 2.1 进程的基本概念进程的基本概念 The basic concept of process四、并发执行条件四、并发执行条件(Bernstein条件条件) 设设R(Pi)=a1,a2,am：表示程序：表示程序Pi在执行期间需参考的在执行期间需参考的所有变量集，称所有变量集，称“读集读集”； W(Pi)=b1,b2, bn： 表示表示Pi在执行期间要改变的所有在执行期间要改变的所有变量的集合。称变量的集合。称“写集写集”。例：例： c:=a-b w:=c+1 x:=x+1 R()=a,b W() =c R()W()= R()= c W()=w R()W()

7、= R()W()=x第二章第二章 进程管理进程管理 Bernstein条件条件：若两个程序（进程）若两个程序（进程）p1、p2能满足下述条能满足下述条件，则它们便能并发执行，且具有可再现性：件，则它们便能并发执行，且具有可再现性： R(p1)W(p2)R(p2) W(p1) W(p1) W(p2) = n可理解为：可理解为： 两程序互不把对方的结果作为输入，且两程序互不把对方的结果作为输入，且不改变同一个量。不改变同一个量。例例第二章第二章 进程管理进程管理（一）进程的引入（一）进程的引入 用户角度看，作业由若干子任务组成，只有子任务被执行时才能用户角度看，作业由若干子任务组成，只有子任务被执

8、行时才能体现任务的功能。体现任务的功能。 “任务任务”和和“任务的执行任务的执行”截然不同。前者是任务的静态描述，截然不同。前者是任务的静态描述，后者体现了任务的动态行为。后者体现了任务的动态行为。同一段正文（同一段正文（2kB），分别加工两批（），分别加工两批（8kB，4kB）不同的数据，）不同的数据，执行两次。第执行两次。第1次执行用打印机报告某些出错信息，占用次执行用打印机报告某些出错信息，占用10kB内存；内存；第第2次执行中无出错数据，不用打印机，但至少需要次执行中无出错数据，不用打印机，但至少需要6kB主存。主存。 五、进程的描述五、进程的描述 (The description o

9、f process)2.1 2.1 进程的基本概念进程的基本概念 The basic concept of process第二章第二章 进程管理进程管理r 一个任务的一个任务的一次执行一次执行对应对应一个进程一个进程。第二章第二章 进程管理进程管理r (dynamic) ：是进程最基本的特征。进程有一定生命周期。是进程最基本的特征。进程有一定生命周期。程序是指一组有序指令集合，是静态实体。程序是指一组有序指令集合，是静态实体。r (concurrent) ：一段时间内，多个进程实体在内存中可同时一段时间内，多个进程实体在内存中可同时运行。引入进程的目的是为了能并发。程序不能并发。运行。引入进程

10、的目的是为了能并发。程序不能并发。r 独立性独立性(independent) ：进程是一个能独立运行、独立获得资源、独进程是一个能独立运行、独立获得资源、独立调度的基本单位。程序不能做为一个独立单位。立调度的基本单位。程序不能做为一个独立单位。r 异步性异步性(asynchronism) ：进程是按各自独立、不可预知的速度前进，进程是按各自独立、不可预知的速度前进，该特性将导致程序执行的不可再现性。该特性将导致程序执行的不可再现性。r 结构特征结构特征(structure feature) ：为正确执行并发，每一个进程配置为正确执行并发，每一个进程配置一个数据结构，称为进程控制块（一个数据结构

11、，称为进程控制块（PCB）。）。如：键盘键入命令如：键盘键入命令 $date（二）（二） 进程的特征进程的特征动态性动态性并发性并发性第二章第二章 进程管理进程管理1 三种基本状态：三种基本状态： 1）就绪状态）就绪状态(Ready )：进程已分配到除：进程已分配到除CPU外的所有资源。外的所有资源。只等只等CPU便可运行。可组成就绪队列。便可运行。可组成就绪队列。 2）执行状态）执行状态(Running)：已获得：已获得CPU正在运行。在单处理机正在运行。在单处理机系统中只能有一个。系统中只能有一个。 3）阻塞状态）阻塞状态(Blocked) ：因发生某事件（如：因发生某事件（如I/O、申请

12、缓冲区、申请缓冲区等）而暂停执行。（等待、睡眠）。可有多个此状态进程组等）而暂停执行。（等待、睡眠）。可有多个此状态进程组成一个或多个（由阻塞原因划分）阻塞队列。成一个或多个（由阻塞原因划分）阻塞队列。（三）进程的基本状态（三）进程的基本状态 (The basic states of process )第二章第二章 进程管理进程管理1）新建状态）新建状态(New state) ：指进程刚被建立，尚未送入就绪指进程刚被建立，尚未送入就绪队列的状态。处于此状态的进程是不完全的，当创建新进队列的状态。处于此状态的进程是不完全的，当创建新进程的所有工作（分配进程控制块、分配内存空间、对程的所有工作（分

13、配进程控制块、分配内存空间、对PCB初始化等）完成后，操作系统就把该进程送入就绪队列。初始化等）完成后，操作系统就把该进程送入就绪队列。 2）终止状态）终止状态(terminal state) ：指进程已经结束（正常、异指进程已经结束（正常、异常）常）释放了除释放了除PCB之外的其他资源，之外的其他资源， OS已将它从就绪队列已将它从就绪队列中移出时的状态。处于该状态的进程不能再被调度执行，中移出时的状态。处于该状态的进程不能再被调度执行，2 新状态和终止状态新状态和终止状态第二章第二章 进程管理进程管理新进程新进程终止终止接纳接纳完成完成进程调度进程调度(时间片到时间片到)I/O完完成成等等

14、I/O请请求求等等中断中断执行执行阻塞阻塞就绪就绪3 进程状态的转换进程状态的转换(The conversion of process state)第二章第二章 进程管理进程管理三种基本状态的变换体现了三种基本状态的变换体现了OS的资源管理作用。的资源管理作用。进程的核心思想在于进程的核心思想在于CPU资源的分配。资源的分配。通常进程从执行态到阻塞态是通常进程从执行态到阻塞态是进程从阻塞态到就绪态是进程从阻塞态到就绪态是。不可能出现的状态转换：不可能出现的状态转换： n 第二章第二章 进程管理进程管理1） 进程挂起的原因进程挂起的原因（reasons for process suspenson

15、）4 进程的挂起状态进程的挂起状态(The suspended state of process) 第二章第二章 进程管理进程管理2) 状态的转换状态的转换 引入挂起状态后，原状态称为引入挂起状态后，原状态称为 “活动活动” (active) ，挂起，挂起后称为后称为“静止静止” (static) 。有：。有：执行执行、活动就绪活动就绪、活动阻塞活动阻塞、静止就绪静止就绪、静止阻塞静止阻塞几种状态。由几种状态。由“活动活动”到到“静止静止”的操的操作称为作称为“挂起挂起”，由，由“静止静止”到到“活动活动”的操作称为的操作称为“激激活活”。见见P32 图图2-6 Fig 2-6 Process

16、 State Transition Diagram with Suspend States第二章第二章 进程管理进程管理第二章第二章 进程管理进程管理六、进程控制块六、进程控制块( Process Control Block)（一）（一）PCB的作用的作用作用：作用： 2.1 2.1 进程的基本概念进程的基本概念 The basic concept of processpid进程状态进程状态现场现场优先级优先级阻塞原因阻塞原因程序地址程序地址同步机制同步机制资源清单资源清单链接指针链接指针第二章第二章 进程管理进程管理暂停暂停（断点的处理（断点的处理机环境保存）机环境保存）调度调度（查（查PC

17、B的优先的优先级及现场状态）级及现场状态）执行执行（查（查PCB中处理机的状中处理机的状态信息，恢复现场）态信息，恢复现场）执行中执行中查数据、程序的地查数据、程序的地址及与其他进程合作址及与其他进程合作理理 解：解：在进程的整个生命周期中，在进程的整个生命周期中，OS根据根据PCB对进程进行控制管对进程进行控制管理。创建理。创建(分配分配PCB)、调度、运行、同步、通信、暂停、阻塞、结、调度、运行、同步、通信、暂停、阻塞、结束束(回收回收PCB)。第二章第二章 进程管理进程管理1）进程标识信息：）进程标识信息：用于唯一地标识一个进程。用于唯一地标识一个进程。 外部标识符：用户，用字母、数字构

18、成，便于记忆。外部标识符：用户，用字母、数字构成，便于记忆。 内部标识符：系统，唯一整数，通常就是进程的序号。内部标识符：系统，唯一整数，通常就是进程的序号。还可根据需要设置父进程、子进程、用户标识符。还可根据需要设置父进程、子进程、用户标识符。2）处理机状态信息：）处理机状态信息：存储处理机中各种寄存器的内容，用于恢存储处理机中各种寄存器的内容，用于恢复现场。可有通用寄存器、指令计数器、程序状态字复现场。可有通用寄存器、指令计数器、程序状态字PSW、用户、用户栈指针。栈指针。 3）进程调度信息：）进程调度信息：与进程调度和进程对换有关的内容。进程状与进程调度和进程对换有关的内容。进程状态、进

19、程优先级、事件、与调度算法有关的其他信息。一般常包括态、进程优先级、事件、与调度算法有关的其他信息。一般常包括进程已等待的时间和已使用的处理器时间等进程已等待的时间和已使用的处理器时间等 。（二）进程控制块中的信息（二）进程控制块中的信息(Information in PCB)第二章第二章 进程管理进程管理4）进程控制信息：）进程控制信息：程序数据的地址、进程同步和通信机制程序数据的地址、进程同步和通信机制（消息队列和信号量）、资源清单（除（消息队列和信号量）、资源清单（除CPU外进程所需的全外进程所需的全部资源及已分配的资源）、链接指针（本进程所在队列的下部资源及已分配的资源）、链接指针（本

20、进程所在队列的下一个进程的一个进程的PCB首址）。首址）。说明：说明：r 1）PCB是操作系统中最重要的数据结构是操作系统中最重要的数据结构 记录进程的记录进程的属性信息；属性信息； 标志进程的存在。标志进程的存在。r 2）进程的）进程的PCB与进程同时建立，同时撤消。与进程同时建立，同时撤消。第二章第二章 进程管理进程管理 由于由于PCB经常被系统访问，尤其是被运行频率很高的进经常被系统访问，尤其是被运行频率很高的进程调度及分派程序访问，故程调度及分派程序访问，故PCB应常驻内存应常驻内存。系统将所有的。系统将所有的PCB组成若干链表（或队列），存放在组成若干链表（或队列），存放在OS中专门

21、开辟的中专门开辟的PCB区内。区内。 在一个系统中，常常含有固定数目的在一个系统中，常常含有固定数目的PCB。对它们要进行。对它们要进行有效的组织与管理。有效的组织与管理。 常用的方式为：常用的方式为：r 链接方式链接方式r 索引方式索引方式（三）（三） PCB的组织方式的组织方式(The organization way of PCB )第二章第二章 进程管理进程管理1）链接方式）链接方式：相同状态的：相同状态的PCB链接成一个队列。链接成一个队列。阻塞队列指针阻塞队列指针就绪队列指针就绪队列指针执行指针执行指针空闲队列指针空闲队列指针PCB2PCB3PCB4PCB5PCB1PCB6PCB7

22、PCB8PCB943091708第二章第二章 进程管理进程管理2）索引方式）索引方式：相同状态的：相同状态的PCB建立一张索引表。建立一张索引表。执行指针执行指针就绪表指针就绪表指针阻塞表指针阻塞表指针PCB1PCB7PCB2PCB3PCB4PCB5PCB6就绪索引表就绪索引表阻塞索引表阻塞索引表第二章第二章 进程管理进程管理2.2 进程控制进程控制Process Control 进程控制的职能就是对系统中的全部进程实行有效的进程控制的职能就是对系统中的全部进程实行有效的管理，是进程管理中最基本的功能。管理，是进程管理中最基本的功能。 其主要表现为：进程的创建、撤销以及进程运行中的其主要表现为

23、：进程的创建、撤销以及进程运行中的状态转换。状态转换。 进程控制一般是由进程控制一般是由中的中的实现。实现。 第二章第二章 进程管理进程管理2.2 进程控制进程控制Process Control一一二二三四第二章第二章 进程管理进程管理一、进程创建一、进程创建（The creating of ProcessThe creating of Process）（reasons for process creation） 用户登录（如分时系统中）；用户登录（如分时系统中）； 作业调度（如批处理系统中）；作业调度（如批处理系统中）； 提供服务（运行中的用户程序提出某种请求，则系统提供服务（运行中的用户程

24、序提出某种请求，则系统创建进程以完成请求，创建进程以完成请求，如：打印文件如：打印文件）；）； 应用请求（应用进程根据需要，为自己创建进程）应用请求（应用进程根据需要，为自己创建进程）第二章第二章 进程管理进程管理 用于描述进程家族关系（创建关系）的有向树。结点代表用于描述进程家族关系（创建关系）的有向树。结点代表进程，边代表父子关系。父进程、子进程、祖父进程、祖先。进程，边代表父子关系。父进程、子进程、祖父进程、祖先。 子进程可以继承父进程所拥有的资源，但子进程被撤消子进程可以继承父进程所拥有的资源，但子进程被撤消时，必须归还。撤消父进程时，须先撤消其所有的子进程。时，必须归还。撤消父进程时

25、，须先撤消其所有的子进程。PCB中有家族关系表项，以标识自己的父、子进程。中有家族关系表项，以标识自己的父、子进程。（Process Graph）第二章第二章 进程管理进程管理0#1#p1p2p3p4Pn是系统引导自动是系统引导自动生成的进程生成的进程Linux系统中的进程树系统中的进程树 Linux内核被加载内存后，初始内核被加载内存后，初始化系统，创建系统中的第一个内核化系统，创建系统中的第一个内核态进程（态进程（idle进程进程，0号进程）。号进程）。m 0#是所有进程的祖先。由它执行是所有进程的祖先。由它执行cpu_idle()函数，当没有其他进程处函数，当没有其他进程处于于TASK_

26、RUNNING的时候，调度程的时候，调度程序会选择序会选择0号进程运行号进程运行。0号进程创号进程创建建第一个用户态进程第一个用户态进程init进程进程(1#进程进程)m1# 它创建和监控其他进程的活动它创建和监控其他进程的活动。使用宏。使用宏INIT-TASK定义了进程控定义了进程控制块，实现了进程模型。制块，实现了进程模型。第二章第二章 进程管理进程管理 由进程由进程创建原语创建原语Creat（）（）(fork()完成。完成。 输入参数输入参数：进程名、优先数、构成进程名、优先数、构成PCB的其他必要参数的其他必要参数 返回返回：进程号进程号 功能功能：创建一个具有指定标识符的进程。构造创

27、建一个具有指定标识符的进程。构造PCB，使该，使该PCB进入就绪队列，使用进入就绪队列，使用Creat原语的进程即为新进程的父进程。原语的进程即为新进程的父进程。 步骤步骤：1）申请空白）申请空白PCB：分配唯一标识符，并从：分配唯一标识符，并从PCB集合中索取一集合中索取一空白空白PCB； 2）为新进程分配资源：为数据、程序、用户栈分配内存；）为新进程分配资源：为数据、程序、用户栈分配内存； 3）初始化）初始化PCB；(标识信息、处理机状态信息、处理机控制信息标识信息、处理机状态信息、处理机控制信息) 4）插入就绪队列。）插入就绪队列。程序描述为：程序描述为：（The creating of

28、 Process）第二章第二章 进程管理进程管理q 正常结束（有一条表示进程结束的指令）；正常结束（有一条表示进程结束的指令）；q 异常结束（运行中出现错误或故障。如越界错误、申异常结束（运行中出现错误或故障。如越界错误、申请的内存超过了系统所能提供的最大量等。）；请的内存超过了系统所能提供的最大量等。）；q 外界干预（应外界的请求而终止。如操作员或操作系外界干预（应外界的请求而终止。如操作员或操作系统干预、父进程请求、父进程终止）统干预、父进程请求、父进程终止）二、进程的终止二、进程的终止(Termination of Process)(Termination of Process)第二章第

29、二章 进程管理进程管理由进程由进程终止原语终止原语Destroy（）（）完成。完成。输入参数：输入参数：进程号进程号返回：返回：成功或失败标记成功或失败标记功能：功能：撤销指定进程的撤销指定进程的PCB，收回该进程拥有的全部资源。，收回该进程拥有的全部资源。步骤：步骤：n1）由标识符，在）由标识符，在PCB集中检索其集中检索其PCB，读取状态；，读取状态；n2）若）若“执行执行”则终止运行，并进行进程调度。则终止运行，并进行进程调度。n3）查其子孙进程，若有则对其）查其子孙进程，若有则对其Destroy（）；（）；n4）归还资源给父进程或系统；）归还资源给父进程或系统；n5）将被终止进程的）将

30、被终止进程的PCB从所在队列中移出；从所在队列中移出；第二章第二章 进程管理进程管理u 请求系统服务。若请求请求系统服务。若请求未满足，则阻塞；当资源可以满足未满足，则阻塞；当资源可以满足时，由释放该资源的进程将阻塞进程唤醒；时，由释放该资源的进程将阻塞进程唤醒；u 启动某种操作启动某种操作。等待其完成。等待其完成。u 新数据未到达。多进程合作时，本进程要用的其它进程的新数据未到达。多进程合作时，本进程要用的其它进程的结果尚未到来。结果尚未到来。u 无新工作可做。某些系统进程，等待工作的到达。无新工作可做。某些系统进程，等待工作的到达。三三、进程的阻塞与唤醒、进程的阻塞与唤醒(TheThe b

31、lock and wakeup of Process )第二章第二章 进程管理进程管理由由阻塞原语阻塞原语Block（）（）实现。实现。正在执行的进程本身调用正在执行的进程本身调用BlockBlock，n1）停止进程的执行；）停止进程的执行；n2）改状态）改状态“执行执行”为为“阻塞阻塞”，插入相应阻塞队列；，插入相应阻塞队列；n3）重新调度（进行切换，即保留现场，重设现场）。）重新调度（进行切换，即保留现场，重设现场）。 BLOCK( ) 输入参数：输入参数：无无 返回：返回：转进程调度转进程调度 功能：功能：将现行进程的将现行进程的PCB置成置成“阻塞阻塞”状态后列入阻塞队状态后列入阻塞队

32、列列第二章第二章 进程管理进程管理 由由唤醒原语唤醒原语Wakeup（）（）实现。实现。 由和由和的进程执行唤醒。的进程执行唤醒。n 1）从阻塞队列中移出；）从阻塞队列中移出；n 2）改）改“阻塞阻塞”为为“就绪就绪”；n 3）插入就绪队列。）插入就绪队列。 WAKEUP( )输入参数：输入参数：进程号进程号返回：返回：成功或失败标记成功或失败标记功能：功能：把指定进程的把指定进程的PCB从阻塞队列摘下，改状态为就绪，从阻塞队列摘下，改状态为就绪，插入就绪队列插入就绪队列第二章第二章 进程管理进程管理第二章第二章 进程管理进程管理由由挂起原语挂起原语Suspend（）（）实现。实现。q 1）检

33、查、修改状态。）检查、修改状态。“活动就绪活动就绪”“静止就绪静止就绪”；“活动活动阻塞阻塞” “静止阻塞静止阻塞”；q 2）若原状态为）若原状态为“执行执行”，则，则“执行执行” “静止就绪静止就绪”，并调，并调用进程调度程序重新调度。用进程调度程序重新调度。q 3）复制）复制PCB到内存某区域到内存某区域;由由激活原语激活原语Active（）（）实现。实现。q 1）将进程调入内存，改状态。）将进程调入内存，改状态。“静止静止” “活动活动”;q 2）若新状态为）若新状态为“活动就绪活动就绪”则根据情况，看是否需重新调度则根据情况，看是否需重新调度（抢占调度策略）。（抢占调度策略）。四、进程

34、的挂起与激活四、进程的挂起与激活(The Suspend and Active of Process)第二章第二章 进程管理进程管理2.3 进程同步进程同步 Process Synchronization 进程同步的主要任务是使并发执行的诸进程进程同步的主要任务是使并发执行的诸进程间能有效地共享资源和相互合作，从而使程序的间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。执行具有可再现性。第二章第二章 进程管理进程管理 同处于一个系统中的进程间可能存在两种关系：同处于一个系统中的进程间可能存在两种关系：1）间接相互制约关系：间接相互制约关系：因多进程共享某资源而产生。此时进因多进程共

35、享某资源而产生。此时进程同步要保证进程能互斥地访问临界资源。为此资源要由系统程同步要保证进程能互斥地访问临界资源。为此资源要由系统统一分配。统一分配。 进程互斥时他们的执行顺序是可以任意的，通过共享资源进程互斥时他们的执行顺序是可以任意的，通过共享资源实现相互制约实现相互制约。进程资源进程进程资源进程。相互之间不一定清楚其它相互之间不一定清楚其它进程情况。进程情况。第二章第二章 进程管理进程管理2）直接相互制约关系：直接相互制约关系：因多进程内容上的联系而产生。此因多进程内容上的联系而产生。此时进程同步要保证进程在执行次序上的协调。时进程同步要保证进程在执行次序上的协调。 进程同步指进程同步指

36、并发进程，其各自执行结果互为对方的执并发进程，其各自执行结果互为对方的执行条件，从而限制各进程执行速度。行条件，从而限制各进程执行速度。进程进程。进程进程。相互清相互清楚对方的存在及其作用，交换信息。楚对方的存在及其作用，交换信息。计算进程计算进程A缓冲区缓冲区打印进程打印进程B第二章第二章 进程管理进程管理同步与互斥比较同步与互斥比较同同 步步互互 斥斥进程进程 -进程进程进程进程 -资源资源 - 进程进程时间次序上受到某种限制时间次序上受到某种限制竞争到某一物理资源时不允许进程竞争到某一物理资源时不允许进程工作工作相互清楚对方的存在及作用，相互清楚对方的存在及作用，交换信息交换信息不一定清

37、楚其进程情况不一定清楚其进程情况往往指有几个进程共同完成一往往指有几个进程共同完成一个任务个任务往往指多个任务多个进程间通讯制往往指多个任务多个进程间通讯制约约例：例：发送与接受之间，供者与发送与接受之间，供者与用者之间，用者之间，4100米接力，米接力，工厂流水线。工厂流水线。例：例：交通十字路口，篮球抢篮板，交通十字路口，篮球抢篮板，进程争抢打印机。进程争抢打印机。第二章第二章 进程管理进程管理第二章第二章 进程管理进程管理 若多进程共享某临界资源，则应对其进行同步控制，以若多进程共享某临界资源，则应对其进行同步控制，以实现对临界资源的互斥访问。实现对临界资源的互斥访问。 临界资源可有硬、

38、软资源。临界资源可有硬、软资源。 硬件资源如：打印机等。硬件资源如：打印机等。诸进程要互斥使用这些资源。诸进程要互斥使用这些资源。 软件资源如：共享变量等。软件资源如：共享变量等。对共享变量应作为临界资源对共享变量应作为临界资源处理。即要对它进行互斥访问。处理。即要对它进行互斥访问。 （一）临界资源（一）临界资源 ( Critical resource) 第二章第二章 进程管理进程管理 进程进程A：生产一个数据。用：生产一个数据。用count计数，计数，count=count+1 进程进程B：消费一个数据。则：消费一个数据。则count=count-1对对count的操作可细化为：（的操作可细

39、化为：（R表示寄存器，设表示寄存器，设count初值为初值为1）例例1： 两个并发执行的进程两个并发执行的进程A、B。A：R1=count R1=R1+1 count=R1B：R2=count R2=R2-1 count=R2n若执行次序为：若执行次序为：A(1) A(2) A(3) B(1) B(2) B(3) 则则count=1n若执行次序为：若执行次序为：A(1) B(1) A(2) A(3) B(2) B(3) 则则count=0n若执行次序为：若执行次序为：A(1) B(1) B(2) B(3) A(2) A(3) 则则count=2第二章第二章 进程管理进程管理栈指针为栈指针为to

40、p，设有两个程序段设有两个程序段getaddr(top) 和和 putaddr(blk)，从给定栈中取出相应的内存数据块地址，从给定栈中取出相应的内存数据块地址，将内存数据块地址将内存数据块地址blk放入椎栈中。放入椎栈中。例例2：设有堆栈设有堆栈S S，栈中存放内存中相应的数据块地址。，栈中存放内存中相应的数据块地址。第二章第二章 进程管理进程管理abef a b e f随机 a b e f第二章第二章 进程管理进程管理 对对临界资源，多进程必须互斥访问。把每个进程临界资源，多进程必须互斥访问。把每个进程的那段的那段称为称为CS。 对临界资源的互斥访问即为多进程互斥进入各自的临对临界资源的互

41、斥访问即为多进程互斥进入各自的临界区操作。为保证互斥访问，在进入前必需先检测临界资界区操作。为保证互斥访问，在进入前必需先检测临界资源的状态。源的状态。(Entry section) ：进程中在临界区前用于检查临界：进程中在临界区前用于检查临界资源是否正被访问的代码。资源是否正被访问的代码。(Exit section) ：进程中在临界区后的一段代码，用：进程中在临界区后的一段代码，用于标记该临界资源已被释放。于标记该临界资源已被释放。 （二）（二） 临界区临界区 (Critical Section)第二章第二章 进程管理进程管理Entry sectionExit section remaind

42、er section;until false;访问临界资源的循环进程描述如下访问临界资源的循环进程描述如下：repeatcritical section;为实现进程互斥进入为实现进程互斥进入自己的临界区，采用自己的临界区，采用进行协调。进行协调。第二章第二章 进程管理进程管理 OS利用同步机制提供互斥工具才能保证进程互斥的进入临界利用同步机制提供互斥工具才能保证进程互斥的进入临界区，互斥工具应能保证如下几点：区，互斥工具应能保证如下几点：1）：若临界资源空闲，则允许一个请求进程进入自己的临界区。若临界资源空闲，则允许一个请求进程进入自己的临界区。2）：若临界资源正被使用，则其它申请该资源的进程

43、应该等待。若临界资源正被使用，则其它申请该资源的进程应该等待。3）：保证进程可在有限时间内进入自己的临界区，防止保证进程可在有限时间内进入自己的临界区，防止“死等死等”。4）：当进程需临界资源不能满足而等待时，应释放当进程需临界资源不能满足而等待时，应释放CPU，防止，防止“忙等忙等” 互斥工具有软件、硬件和信号量几种方法。互斥工具有软件、硬件和信号量几种方法。（三）同步机制应遵循的原则（三）同步机制应遵循的原则第二章第二章 进程管理进程管理设两个进程设两个进程PiPi、 PjPj并发执行，共享某临界资源。描述为：并发执行，共享某临界资源。描述为： beginbegin parbegin pa

44、rbegin Pi Pi； PjPj； parendparend end end 利用软件方法解决进程互斥问题，方法之一利用软件方法解决进程互斥问题，方法之一 -。第二章第二章 进程管理进程管理 。检查锁状态，若为关。检查锁状态，若为关闭，则等待其打开；若已打开，闭，则等待其打开；若已打开，则将其关闭，执行。则将其关闭，执行。 。进入临界区，执行操。进入临界区，执行操作。作。 ，将锁打开，退出临界，将锁打开，退出临界区。区。 关锁关锁lock(W):lock(W): while(W=1); while(W=1); W=1; W=1; 开锁开锁unlock(W): unlock(W): W=0;

45、 W=0;为为每类临界区每类临界区设置一把设置一把“锁锁”，有，有打开打开和和关闭关闭两种状态。可两种状态。可用变量表示锁（软件锁），值为用变量表示锁（软件锁），值为0表示打开，为表示打开，为1表示关闭。表示关闭。第二章第二章 进程管理进程管理例：例：利用锁变量方法实现两个进程利用锁变量方法实现两个进程A A、B B互斥互斥共享共享打印机打印机。进程进程ALock(W);打印信息打印信息S；/*CS区区*/Unlock(W);进程进程BLock(W);打印信息打印信息S；/*CS区区*/Unlock(W);：简单；：简单；：不安全，因为关锁和开锁操作不具有不安全，因为关锁和开锁操作不具有原子性

46、原子性。 出现出现“忙等忙等”，软件算法不能完全解决多个进程互斥问题，算法复杂，效率较软件算法不能完全解决多个进程互斥问题，算法复杂，效率较低。低。以变量以变量W表示锁，置初值表示锁，置初值为为0。两个进程的部分代码如下。两个进程的部分代码如下。Perterson算法算法 第二章第二章 进程管理进程管理 1）指令：）指令：boolean TS(boolean *lock) boolean old; old = lock; lock = TRUE; return old;lock值表示资源使用情况。值表示资源使用情况。false，表示，表示空闲（初值）；空闲（初值）；true，则表示正用。，则表

47、示正用。 利用硬件方法解决进程互斥问题有利用硬件方法解决进程互斥问题有和和两种常见方式。两种常见方式。第二章第二章 进程管理进程管理2）利用）利用TS实现进程互斥实现进程互斥while TS(lock) do skip CSlock:=false注：注：若资源可用，则若资源可用，则lock 为为false，则，则TS(lock)为为false，进入，进入CS，否则，否则继续检测。退出临界区，继续检测。退出临界区，重设资源可用。重设资源可用。缺点缺点：不能：不能“让权等待让权等待”，是一种是一种“忙等忙等” 更好的方法是当临界资源不可用时，就阻塞该进程，直更好的方法是当临界资源不可用时，就阻塞该

48、进程，直到临界资源可用时继续。到临界资源可用时继续。 该指令的具体实现该指令的具体实现第二章第二章 进程管理进程管理 信号量（信号量（Semaphore）方法是荷兰学者）方法是荷兰学者Dijkstra1965年提年提出的解决进程同步、互斥的通用工具，在出的解决进程同步、互斥的通用工具，在THE(荷兰文荷兰文Tchnische Hoogeschool Eindhov)操作系统中实现。操作系统中实现。第二章第二章 进程管理进程管理（四）信号量机制（四）信号量机制（Integer Semaphore） wait(s)： while s0表示一个或多表示一个或多个资源，个资源，0没有资源。没有资源。r

49、 信号量操作的信号量操作的： 信号量可以初始化为一个非信号量可以初始化为一个非负值；负值；除初始化外，仅能由除初始化外，仅能由wait( )和和signal( )访问信号量访问信号量。即即P和和V操作。操作。signal(s): s:=s+1第二章第二章 进程管理进程管理 其他进程可获得处理机，会出现多个进程等待访问同一临其他进程可获得处理机，会出现多个进程等待访问同一临界资源。界资源。 放弃处理机放弃处理机“阻塞阻塞”等待，等待，“让权等待让权等待”。整型信号量的整型信号量的： 未遵循未遵循“让权等待让权等待”，出现，出现“忙等忙等”。第二章第二章 进程管理进程管理（Record-type

50、Semaphore） 记录型信号量所含内容记录型信号量所含内容（1 1）代表资源数目的整型量代表资源数目的整型量（2 2）进程链表，接纳所有等待进程。进程链表，接纳所有等待进程。type semaphore=record value：integer; L：list of process; -L为一个进程链表为一个进程链表 end第二章第二章 进程管理进程管理procedure signal(s) var s:semaphore; begin s.value:=s.value+1 if s.value=0 then wakeup(s.L) endprocedure wait(s)var s :s

51、emaphore;begin s.value:=s.value-1； if s.value0 then block(s.L)；end第二章第二章 进程管理进程管理例：系统有两台打印机，有多个需要执行打印操作的进例：系统有两台打印机，有多个需要执行打印操作的进程，描述各个进程的执行。程，描述各个进程的执行。 s第二章第二章 进程管理进程管理 1）s.value的的。s.L表示该表示该资源的阻塞队列。资源的阻塞队列。 2）wait()表示请求一个单位的资源。表示请求一个单位的资源。s.value-1表示该资源表示该资源数减数减1。若。若s.value0，则资源已用完，调用阻塞原语。此时的，则资源已

52、用完，调用阻塞原语。此时的s.value值不再是资源数量，而是值不再是资源数量，而是。 3）signal()表示释放一个单位的资源。表示释放一个单位的资源。 s.value+1表示该资表示该资源数加源数加1。若。若s.value1时，可看作一般的记录型信号量。当时，可看作一般的记录型信号量。当S=1时，即为互斥时，即为互斥信号量。信号量。l 3）Swait（S，1，0）下限为）下限为1，每次分配，每次分配0个资源。这是个资源。这是一种特殊的可作为开关的信号量。当一种特殊的可作为开关的信号量。当S1时，允许多个进程时，允许多个进程进入。当进入。当S1（S=0）时，阻止任何进程进入。）时，阻止任何

53、进程进入。几种特殊情况：几种特殊情况：第二章第二章 进程管理进程管理r 一个临界资源一个临界资源var mutex:semaphore:= parbegin process1: wait(mutex) CS signal(mutex) process2: wait(mutex) CS signal(mutex) parendl 1、识别临界资源，一看是、识别临界资源，一看是否否共享共享，二看是否，二看是否排他排他。l 2、wait(mutex)和和signal(mutex)必须必须成对出现成对出现，并分别紧靠并分别紧靠临界段的头尾部临界段的头尾部。（五）信号量应用之一（五）信号量应用之一缺少缺

54、少wait，则？缺少，则？缺少signal，则？，则？一个互斥信号量一个互斥信号量mutex实现进程实现进程P1和和P2互斥的描述为：互斥的描述为：第二章第二章 进程管理进程管理实例：三个进程执行中要共享变量实例：三个进程执行中要共享变量count。count属于临界资源，对其应互斥访问。属于临界资源，对其应互斥访问。 until false;end Var mutex:semaphore:=1;Begin parbegin process1:begin repeat until false; end process3:begin repeat until false; endParendEn

55、dprocess2:begin repeat -2.1P下一条语句下一条语句第二章第二章 进程管理进程管理（六）信号量应用之二（六）信号量应用之二 利用信号量可以控制进程执行的先后次序，以描述程序利用信号量可以控制进程执行的先后次序，以描述程序或语句间的前趋关系。或语句间的前趋关系。mutex第二章第二章 进程管理进程管理 parbegin begin S1；signal(a)；signal(b)；end； begin wait(a)；S2；signal(c)；signal(d)；end； begin wait(b)；S3；signal(e)；end； begin wait(c)；S4；sig

56、nal(f)；end； begin wait(d)；S5；signal(g)；end； begin wait(e)；wait(f)；wait(g)；S6；end； parendendvar a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0beginS1S5S2S3S6S4S3abcdfge第二章第二章 进程管理进程管理第二章第二章 进程管理进程管理例如：例如：计算进程计算进程、打印进程打印进程实现合作。实现合作。计算进程计算进程不断把每次计算结不断把每次计算结果果放入放入buf中，中，打印进程打印进程则则取出取出buf中的数据打印输出，若不采取任中的数据打印输出，若

57、不采取任何制约措施，这两个进程的起始执行时间和执行速度彼此独立，相何制约措施，这两个进程的起始执行时间和执行速度彼此独立，相应的控制段描述为：应的控制段描述为：Pc: A：local buf1计算计算Repeat buf1buf Until buf1=空空 Buf计算结果计算结果GoTo APp:B：local pri Repeat pribuf Until pri空空 打印打印buf中的数据中的数据 消除消除buf中的数据中的数据GoTo B问问 题：题：CPU时间的极大浪费时间的极大浪费（一）问题的提出（一）问题的提出第二章第二章 进程管理进程管理直接制约的进程互给对方进程直接制约的进程互

58、给对方进程，一旦收到制约进程发来的信号即由等待开始执行。，一旦收到制约进程发来的信号即由等待开始执行。 当当Pc将计算结果送入将计算结果送入buf后，后，给给Pp进程发送一个进程发送一个buf满信号满信号，Pp进程等到满信号即从进程等到满信号即从buf中取出结果去打印中取出结果去打印;当当Pp进程把进程把buf中数据取出打印后，中数据取出打印后，给给Pc进程发送一个进程发送一个buf空信号空信号，Pc等到空信号即可把下一个计算结果送入缓冲区。等到空信号即可把下一个计算结果送入缓冲区。 把各进程之间发送的信号作为信号量看待。即把各进程之间发送的信号作为信号量看待。即buf满信号满信号，buf空信

59、号空信号可用信号量表示。可用信号量表示。（二）问题分析（二）问题分析同同 步步 机机 制制第二章第二章 进程管理进程管理 S Sempty empty ：是是PpPp进程运行结束发送的信号量，是进程运行结束发送的信号量，是PcPc运行运行需要等待的信号量，用于判断需要等待的信号量，用于判断BufBuf是否为空。若空则为是否为空。若空则为1 1，否则为，否则为0 0。 S Sfullfull：是是PcPc进程运行结束发送的信号量，是进程进程运行结束发送的信号量，是进程PpPp运行需要使用的信号量，用于判断运行需要使用的信号量，用于判断BufBuf中是否有数据。中是否有数据。有数据为有数据为1 1

60、，无数据为，无数据为0 0。 初始：初始： S Sempty empty 1 1， S Sfullfull 0 0设置两个信号量：设置两个信号量：Sempty 和和 Sfull第二章第二章 进程管理进程管理计算进程计算进程C打印进程打印进程P计计 算算P(Sempty)送缓冲区送缓冲区V(Sfull)从从Buffer中取数中取数P(Sfull)打印打印V(Sempty)第二章第二章 进程管理进程管理进程进程关系中，直接制约进程之间发送的关系中，直接制约进程之间发送的信号量，只与制约进程及被制约进程有关。信号量，只与制约进程及被制约进程有关。 一个进程一个进程PiPi的私有信号量是从制约进程的私