操作系统第2章

1、第2章 进程的描述与控制1第 2 页操作系统第第2 2章章 进程的描述与控制进程的描述与控制2.1 前趋图和程序执行前趋图和程序执行2.2 进程的描述进程的描述2.3 进程控制进程控制2.4 进程同步进程同步2.5 经典进程的同步问题经典进程的同步问题2.6 进程通信进程通信2.7 线程线程(Threads)的基本概念的基本概念2.8 线程的实现线程的实现2第 3 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行 前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用

2、于描述进程之间执行的前后关系。 图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。 在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。2022-6-212.1.1 前趋图和顺序执行前趋图和顺序执行第

3、4 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行 前趋图中每个结点还具有一个重量(Weight)，权重用于表示该结点所含有的程序量或结点的执行时间。 用户和计算机硬件的操作接口，方便用户使用；管理计算机硬件资源使之效率更高2022-6-21P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示为：P=P1, P2, P3, P4, P5, P6, P7, P8, P9= (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P

4、3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 对于左图所示的前趋图， 存在下述前趋关系： 第 5 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行注意注意：前趋图中必须不存在循环，但在下图中却有着下述的前趋关系：这种前趋关系是不能满足的。S2S3, S3S2 用户和计算机硬件的操作接口，方便用户使用；管理计算机硬件资源使之效率更高2022-6-21第 6 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图

5、和程序执行 单道批处理系统中进行计算时，先运行输入程序I，用于输入用户的程序和数据；然后运行计算程序C，对所输入的数据进行计算；最后才是运行打印程序P，打印计算结果。 三个程序段的前趋关系：Ii Ci Pi有效管理计算机硬件，方便用户使用2. 1.2 程序程序的顺序执行的顺序执行2022-6-21顺序执行的前趋图第 7 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行 单道批处理系统中，一个程序段执行时，也存在执行顺序问题： S1: a =x+y; S2: b =a-5; S3: c =b+1;1. 程序的顺序执行程序的顺序执行2022

6、-6-21前趋图:前趋关系：S1 S2 S3第 8 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行程序程序指令或语句序列，体现了某种算法，所有程序是顺序的。顺序环境顺序环境 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。2022-6-212. 程序顺序执行时的特征程序顺序执行时的特征第 9 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行程序程序顺序执行时的特征顺序执行时的特征(1)顺序性：处理机严格地按照程序所规定的顺序执行，即每一操作必须

7、在下一个操作开始之前结束。(2) 封闭性：独占资源，执行过程中不受外界影响(3) 可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果,即程序执行结果的确定性。2022-6-21顺序环境中，程序运行顺序环境中，程序运行结果与程序执行速度无关，只要初始状态相同，结果与程序执行速度无关，只要初始状态相同，结果应结果应相同。相同。但顺序执行时，系统资源的利用率低。但顺序执行时，系统资源的利用率低。第 10 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行202

8、2-6-212.1.3 程序的并发程序的并发执行执行 多道程序设计是指允许多个程序同时进入内存并运行，引入目的是为了提高系统效率CPUCPU是一个只可调度，不可分配的是一个只可调度，不可分配的资源资源在顺序环境下 CPU利用率= 40/80 = 50%DEV1利用率= 15/80=18.75%DEV2利用率= 25/80=31.25% 第 11 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行2022-6-21在并发环境下 CPU利用 = 40/45= 89%DEV1并发环境下利用 = 15/45= 33%DEV2并发环境下利用 =25

9、/45= 56%A AB BCPUCPUDEV1DEV1DEV2DEV2CPUCPUCPUCPU10101515202030304040 t(s)t(s)2525DEV1DEV1CPUCPU35354545DEV2DEV2CPUCPUDEV2DEV2第 12 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行2022-6-21P1P2P3P4I1I2I3I4C1C2C3C4在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，不

10、存在前趋关系，可以并发执行。第 13 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行2022-6-21S1S2S3S4图 2-4 四条语句的前趋图对于具有下述四条语句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 由前趋图可看出：S3必须在a和b被赋值后方能执行；S4必须在S3之后执行；但S1和S2可以并发执行，因为它们彼此互不依赖。第 14 页第2章进程的描述与控制 进程的描进程的描述与控制述与控制2.1 2.1 前趋图和程序执行前趋图和程序执行程序并发执行时的特征程序并发执行时的

11、特征2022-6-211)1) 间断性：间断性：每个程序段都具有执行执行暂停暂停执行执行的特点的特点2)2) 失去封闭性：失去封闭性：程序之间相互影响3)3) 不可再现性：不可再现性：并发并发程序执行的结果与其执行的相对速度有关，是不确定的程序执行的结果与其执行的相对速度有关，是不确定的 例如，有两个循环程序A和B，它们共享一个变量N（初始值为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。

12、(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。 程序运行结果与程序执行速度有关，虽然初始状态相同，程序运行结果与程序执行速度有关，虽然初始状态相同，结果可能不相同结果可能不相同系统资源管理不当，会出现系统资源管理不当，会出现与执行时间有关的错误与执行时间有关的错误第 15 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2.2.1 2.2.1 进程的定于与特征进程的定于与特征1.1.与与时间有

13、关的错误时间有关的错误例1：为了了解某单行道的交通流量，在路口安放一个监视器，功能是有车通过该路段时，就向计算机发送一个信号。为计算机系统设计两个程序：程序A的功能是接收到监视器的信号时，就在计数单元COUNT上加1；程序B的功能是每隔半小时，将计数单元COUNT的值打印输出，然后清零。COUNT初始时为0，两个程序的描述如图所示。假如程序A和程序B的执行顺序如下：A1A2B1B2A1A2B3，则会出现什么情况呢？第 16 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制例2：某展示厅设置一个自动计数系统，以计数器count表示在

14、场的人数，可见count是动态变化的，若有一个人进展厅，进程pin对计数器count加1，当有一个人退出展厅时，进程pout实现计数器减1。Begincount : integer ;count ：=0；cobeginprocess pin R1:integer; beginR1:=count;R1:=R1+1;count:=R1; end;process poutR2: integer ;beginR2:=count;R2:=R2-1;count:=R2;end；coend;end;第 17 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与

15、控制述与控制若某一时刻展厅的人数为n,即计数器count=n,此刻有一个人要进入，同时另一人要退出，那么进程pin和pout都要执行，以便实现正确计数。若执行过程中pin被中断，pin和pout的执行顺序如下，则：占有cpu执行过程进程执行的操作countpinR1:=countR1:=R1+1nPin被中断，由pout占用CPU并执行结果R2:=countR2:=R2-1count:=R2n-1Pin继续执行count:=R1n+1第 18 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制占有cpu执行过程进程执行的操作coun

16、tpinR1:=countR1:=R1+1nPin被中断，由pout占用CPU并执行结果R2:=countR2:=R2-1nPout被打断，Pin占用 count:=R1n+1Pin被打断，Pout占用 count:=R2n-1pin和pout两个并发进程执行结束后，count的终值不能保持为n，而成为n+1，这样的运算结果显然是错误的。如果两个进程的执行过程中又发生如下的中断和继续执行至结束，执行次序见下表：第 19 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制与时间有关的错误：在并发执行的进程中，因为缺乏对进程执行的顺序的

17、控制，从而造成并发执行结果的错误，这种错误称为与时间有关的错误。第 20 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-21对于进程的定义，从不同的角度可以有不同的定义，其中较典型的进程定义有： (1)进程是程序的一次执行。 (2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 (3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。进程：为了描述程序在并发执行时对系统资源的共享而建立的一个描述程序执行时动态特征的概念2. 进程的定义进程的定义第 21 页2.2 进程的描述进

18、程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-213. 进程进程的的特征特征 动态性：进程是执行的过程，具有生命周期 并发性：多个进程同时存在于内存并发 独立性：进程各自都是一个执行的单位，独自占有资源，独自调度。 异步性：各自运行，运行速度不可预知进程虽具有异步性，但要保证进程并发执行结果的正确性，可配置进程同步机制。第 22 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-212.2.2进程的基本状态和转换进程的基本状态和转换1. 进程进程的三种基本状态的

19、三种基本状态 1) 就绪(Ready)状态：一个进程已经具备运行条件，但由于无一个进程已经具备运行条件，但由于无CPUCPU暂时不能运行的状态（当调度给其暂时不能运行的状态（当调度给其CPUCPU时，立即可以运行）时，立即可以运行） 2) 执行(Running)状态：进程占有进程占有CPUCPU，并在，并在CPUCPU上运行上运行3) 阻塞(Block)状态：阻塞态、封锁态、睡眠态阻塞态、封锁态、睡眠态指进程因等待某种事件的发生而暂时不能运行的状态（即使指进程因等待某种事件的发生而暂时不能运行的状态（即使CPUCPU空闲，该进程也不可运行）空闲，该进程也不可运行）第 23 页2.2 进程的描述

20、进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-21图 2-5 进程的三种基本状态及其转换 2.2.进程状态转换进程状态转换 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换 就绪运行 运行就绪 运行等待(阻塞) 等待（阻塞）就绪第 24 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-21 就绪就绪 - - 运行运行 调度程序选择一个新的进程运行调度程序选择一个新的进程运行 运行运行 - - 就绪就绪 运行进程

21、用完了时间片运行进程用完了时间片 运行进程被中断，因为一高优先级进程处于就绪状态运行进程被中断，因为一高优先级进程处于就绪状态 运行运行 - - 等待等待 OSOS尚未完成其它服务尚未完成其它服务 对一资源的访问尚不能进行对一资源的访问尚不能进行 初始化初始化I/O I/O 且必须等待结果且必须等待结果 等待某一进程提供输入等待某一进程提供输入 (IPC)(IPC) 等待等待 - - 就绪就绪 当所等待的事件发生时当所等待的事件发生时进程的状态在生命周期中不断变化，其变化的根本原因是并发程序共享系统资源并相互影响第 25 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与

22、控制章 进程的描进程的描述与控制述与控制2022-6-21【思考题】1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2. 有没有这样的状态转换，为什么？ 等待运行； 就绪等待3. 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能第 26 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制3. 进程的进程的五五种状态种状态 创建态：创建态：进程正在创建过程中，操作系统正在为该进程建立相应的实体，分配地址空间和其他资源并放到就绪队列中去。终止态：终止态：进程已经结

23、束运行，通常是在执行完最后一条指令时从执行态转变为终止态。第 27 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-211.引入引入挂起状态的原因挂起状态的原因 (1) 终端用户的请求。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。 2.2.3引入挂起之后进程的五种状态引入挂起之后进程的五种状态 2022-6-21挂起：强行使进程从内存换到外存。挂起：强行使进程从内存换到外存。第 28 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制

24、述与控制2.进程状态的转换进程状态的转换 (1) 活动就绪静止就绪。 (2) 活动阻塞静止阻塞。 (3) 静止就绪活动就绪。 (4) 静止阻塞活动阻塞。 图 2-7 具有挂起状态的进程状态图 掌握进程的状态定义、状态之间的转换以及转换原因第 29 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制293.3.挂起挂起进程的特征进程的特征该进程不能立即被执行挂起进程可能会等待一个事件，但所等待的事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行结束进程挂起状态的命令只

25、能通过操作系统或父进程发出第 30 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-214. 引入挂起之后进程的七种状态引入挂起之后进程的七种状态 引入创建状态和终止状态后具有挂起状态的进程状态要增加考虑下面的几种情况：(1) NULL创建：(2) 创建活动就绪：(3) 创建静止就绪：(4) 执行终止：图2-8 具有创建、终止和挂起状态的进程状态图 第 31 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-212.2.4 进程管理中的数据结

26、构进程管理中的数据结构1.进程进程控制块概念控制块概念 进程包括三部分：程序、数据、进程控制块（PCB）。 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的第 32 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-21 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。1）作为独立运行的基本单位的标志

27、2）能实现间断性运行方式3）提供进程管理所需要的信息4）提供进程调度所需要的信息5）实现与其它进程的同步与通信2. 进程控制块的作用进程控制块的作用 第 33 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制3. 进程控制块中的信息进程控制块中的信息 1) 进程标识符进程标识符用于唯一的标识一个进程。一个进程通常有两种标识符： 内部标识符。在所有的操作系统中，都为每一个进程赋予一个唯一的数字标识符，它通常是一个进程的序号。 设置内部标识符主要是为了方便系统使用。 外部标识符。它由创建者提供，通常是由字母、数字组成。为了描述进程的家

28、族关系， 还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。设置外部标识符主要是为了方便用户对进程的访问。第 34 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-212) 处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。 通用寄存器:又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息； 指令计数器:存放要访问的下一条指令的地址； 程序状态字PSW:其中含有状态信息，如条件码、执行方式、中断屏蔽标志等； 用户栈指针， 指每个用户进程都有一个或若干个与之相关的系

29、统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。 第 35 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-213) 进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息，包括： 进程状态，指明进程的当前状态， 作为进程调度和对换时的依据； 进程优先级，用于描述进程使用处理机的优先级别的一个整数， 优先级高的进程应优先获得处理机； 进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、 进程已执行的时间总和等； 事件，是指进程由执行状态转变为阻塞状态所等

30、待发生的事件，即阻塞原因。 第 36 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-214) 进程控制信息 程序和数据的地址， 是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据； 进程同步和通信机制，指实现进程同步和进程通信时必需的机制， 如消息队列指针、信号量等，它们可能全部或部分地放在PCB中； 资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链接指针， 它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址

31、。 第 37 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制4. 进程控制块的组织进程控制块的组织方式方式为对数量庞大的进程进行有效的管理，应用适当的方式将这些PCB组织起来。目前常用的组织方式有以下三种： 1) 线性方式 将系统中所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。 该方式实现简单、开销小，但每次查找时都需要扫描整张表 适合进程数目不多的系统 第 38 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制PCB14PCB2PCB3

32、PCB4PCB5PCB6PCB7PCB8PCB93087901执 行 指 针就 绪 队 列 指 针阻 塞 队 列 指 针空 闲 队 列 指 针2) 链接方式 把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。 对就绪队列而言，往往按进程的优先级将PCB从高到低进行排列，将优先级高的进程PCB排在队列的前面。 把处于阻塞状态进程的PCB根据其阻塞原因的不同，排成多个阻塞队列，如等待I/O操作完成的队列和等待分配内存的队列等。 第 39 页2.2 进程的描述进程的描述-进程控制块进程控制块第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2022-6-213) 索引方式

33、系统根据所有进程状态的不同，建立几张索引表 把各索引表在内存的首地址记录在内存的一些专用单元中。 在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。 执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针PCB-进程控制块是进程存在的唯一标志第 40 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制 为达到多进程高效率并发执行和协调、实现资源共享的目的 进程控制是进程管理中最基本的功能，主要包括 创建新进程 终止已完成的进程 完成进程各状态间之间的转换 进程控制一般是由OS的内

34、核中的原语来实现的第 41 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制 原语：为了对进程进行有效的管理和控制，操作系统要提供若干基本的操作，并且为了保证执行时的绝对正确，要求这些基本操作以一个整体出现，不可分割。也就是说，一旦启动了它们的程序，就要保证做完，中间不能插入其他程序的执行序列。在操作系统中，把具有这种特性的程序被称为“原语”。 利用屏蔽中断的方法来保证原语操作的不可分割性。第 42 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制1、内核 与硬件紧密联系的软件模块部分，包括中断处理

35、程序、设备驱动程序、时钟管理、进程调度等，称为OS内核。常驻内存。2、处理机运行的状态 系统态：能执行所有指令，访问所有寄存器和存储区，级别较高。OS在系统态运行。 用户态：仅执行规定的指令，一般是用户应用程序指令，访问指定的寄存器和存储区。有效管理计算机硬件，方便用户使用2.3.1 操作系统内核第 43 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制3、OS内核两大功能 支撑功能 (1) 中断处理(2) 时钟管理(3) 原语操作 资源管理功能(1) 进程管理(2) 存储器管理(3) 设备管理 第 44 页2.3 进程控制进程控制第第2 2章章

36、进程的描述进程的描述与控制与控制的描的描述与控制述与控制2.3.2进程进程的创建的创建1. 进程图(Process Graph) 用于描述进程间关系的一棵有向树 结点代表进程 Pi指向pj的有向边描述进程间的父子关系 创建父进程的进程称为祖先进程图 2-13 进程树 第 45 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制2. 引起创建进程的事件引起创建进程的事件 为使程序之间能并发运行，应先为它们分别创建进程。 导致一个进程去创建另一个进程的典型事件有四类：(1) 用户登录。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。 第 4

37、6 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制3. 进程的进程的创建创建原语原语(Creation of Progress) (1)申请空白PCB。 (2)为新进程分配资源。 (3)初始化进程控制块。 (4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列。 第 47 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制2.3.3进程进程的终止的终止 1. 引起进程终止引起进程终止(Termination of Process)的的事件事件 1) 正常结束在任何计算

38、机系统中，都应有一个用于表示进程已经运行完成的指示。 2) 异常结束在进程运行期间，由于出现某些错误和故障而迫使进程终止。常见的异常事件有： 越界错误。 运行超时。 保护错。 等待超时。 非法指令。 算术运算错。 特权指令错。 I/O故障。3) 外界干预指进程应外界的请求而终止运行。这些干预有： 操作员或操作系统干预。 父进程请求。 父进程终止。第 48 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制 2. 进程的终止过程进程的终止过程 (1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。 (2) 若被终止

39、进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。 (3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4) 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。 (5) 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。 第 49 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制2.3.4 进程进程的阻塞与唤醒的阻塞与唤醒1. 引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 (1) 向系统请求共享资源失败。(2)

40、 等待某种操作的完成。(3) 新数据尚未到达。(4) 等待新任务的到达。 第 50 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制 2. 进程阻塞过程进程阻塞过程 正在执行的进程，当发现阻塞事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。进程的阻塞是进程自身的一种主动行为。 阻塞原语执行的过程是：进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞

41、(等待)队列 调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。 第 51 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制 3. 进程唤醒过程进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒。 唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就

42、绪，然后再将该PCB插入到就绪队列中。 第 52 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制2.3.5进程进程的挂起与激活的挂起与激活 1. 进程的挂起进程的挂起 当出现了引起进程挂起的事件时，系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程是： 首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。 最后，若被挂起的进程正在执行，则转向调度程序重新调度。

43、第 53 页2.3 进程控制进程控制第第2 2章章进程的描述进程的描述与控制与控制的描的描述与控制述与控制 2. 进程的激活过程进程的激活过程 当发生激活进程的事件时，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。 激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。 假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低

44、，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。 进程控制，包括了对进程的状态的转变与控制第 54 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制并发进程间的联系并发进程间的联系相交进程与无关进程 相交进程：指多个并发进程在逻辑上有某种联系 无关进程（不相交进程）：在逻辑上无任何联系的进程第 55 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2.4.1 进程同步的基本概念进程同步的基本概念1. 并发进程之间两种形式的制约关系并发进程之间两种形式的制约关系(1) 间接相互制约关系：

45、进程间要通过进程间要通过某种中介某种中介发生联系，是无意识安发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间排的，可发生在相交进程之间，也可发生在无关进程之间。表现为进程资源进程。(2) 直接相互制约关系：进程间的相互联系是进程间的相互联系是有意识的安排的有意识的安排的，直接作，直接作用只发生在相交进程用只发生在相交进程间间,表现为进程进程。第 56 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制2.进程的同步（直接作用）同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。

46、具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于阻塞状态，获得消息后被唤醒进入就绪状态第 57 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制日常生活中的例子1: 司机 P1 售票员 P2 while (true) while (true) 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； 第 58 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制例子2:编写一个复制n个记录的程序，它把文件F中的每一个记录依次先读到输入缓冲区R，再从R拷贝到输出缓冲区T，最后写到

47、文件G中。假定R和T的大小正好存放一个记录，如图所示。可以编写三个子程序来完成这一工作。GET：负责从文件F中按照顺序读出一个记录，然后送入输入缓冲区R。COPY：负责把输入缓冲区R中的记录拷贝到输出缓冲区T中。PUT：负责从输出缓冲区T中读出一个记录，然后依照顺序写入文件G。 第 59 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制第 60 页操作系统60（1）COPYPUTGET（2）COPYGETPUT（3）PUTCOPYGET（4）PUTGETCOPY（5）GETCOPYPUT（6）GETPUTCOPYGETCOPYPUTGETCOPYPUT第

48、 61 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制在上面的例子中，GET、COPY、PUT三者之间呈现的是一种特殊关系。 即只有GET先于COPY工作，COPY的工作才有意义； 只有COPY取走了R中的内容，GET进入下一步工作才有意义。 COPY与PUT之间也有这种类似的关系，这是进程之间由于协同工作而产生的一种直接关系。 第 62 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制例3：生产者-消费者(producer-consumer)问题 有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。

49、 为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中； 消费者进程可从一个缓冲区中取走产品去消费。 不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。 第 63 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制 用一个数组来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。 用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，

50、每当消费者进程取走一个产品后，输出指针加1。缓冲池是组织成循环缓冲的，故应把输入指针加1表示成 in =(in+1)mod n；输出指针加1表示成out =(out+1) mod n。当(in+1) mod n=out时表示缓冲池满；而in=out则表示缓冲池空。 引入了一个整型变量counter, 其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时， 使counter减1。第 64 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制 生产者和消费者两进程共享下面的变量：Var n, inte

51、ger;type item=;var buffer:array0, 1, , n-1 of item;in, out: 0, 1, , n-1;counter: 0, 1, , n; 指针in和out初始化为1。 在生产者和消费者进程的描述中，no-op是一条空操作指令，while condition do no-op语句表示重复的测试条件(condication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止。在生产者进程中使用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc,用于存放每次要消费的产品。 第 65 页

52、2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制producer: repeat produce 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; counter =counter-1; consumer the item in n

53、extc; until false; 虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。 register 1 =counter; register 2 =counter; register1 =register 1+1; register 2 =register 2-1; counter =register 1; counter =register 2; 第 66 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制 假设：counter

54、的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句， 则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行：（由于并发的进程之间的走与停都是随机的，下述情况都可能发生） register 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =counter; (register 2=5) register 2 =register

55、2-1; (register 2=4) counter =register 1; (counter=6) counter =register 2; (counter=4) 第 67 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制进程同步的特点： 具有同步关系的进程需要在某点（同步点）上协调相互的动作，谁先到达谁后到达具有顺序要求的； 进程之间应该了解对方的工作，对方不存在或任何一方单独运行就会出现错误； 一方或双方的运行会直接地依赖于对方所产生的信息或发出的消息。 可能会出现死锁或饿死现象。第 68 页2.4 进程同步进程同步 第2章 进程的描述与控制

56、章 进程的描进程的描述与控制述与控制3.进程的互斥（间接作用） 互斥：由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 临界资源：critical resource：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量 临界区：一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。在进程中涉及到临界资源的程序段叫临界区，多个进程的临界区称为相关临界区第 69 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制互斥进程的特点 具有互斥关

57、系的进程并不关心对方的存在性，即使对方不存在，自己也能够正确的运行，不会受到它存在与否的影响； 具有互斥关系进程的临界区，虽然都是针对同一个共享变量的程序段，但在其上的操作可以相同也可以不同； 进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间不存在互斥关系。 互斥进程之间可能会造成死锁或饿死现象。第 70 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制4. 同步机制应遵循的规则同步机制应遵循的规则 (1) 空闲让进当无进程在互斥区时，任何有权使用互斥区的进程可进入。(2) 忙则等待 不允许两个以上的进程同时进入互斥区(3) 有限等待 任

58、何进入互斥区的要求应在有限的时间内得到满足(4) 让权等待 处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权第 71 页2.4 进程同步进程同步 第2章 进程的描述与控制章 进程的描进程的描述与控制述与控制进程互斥的解决有两种做法由竞争各方平等协商由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用引入进程管理者，由管理者来协调竞争各方对互斥资源的使用并发进程的同步和互斥是现代操作系统中必须解决的问题第 72 页操作系统72补充知识：互斥软件解决软件方法解决了在具有一个处理器或共享主存的多处理器上执行并发进程的问题。即对内存中同一位置的同时访问将被排

59、序，而访问的顺序并不预先指定。1、Dekker算法第1种途径第 73 页操作系统补充知识：互斥软件解决73缺点：进程必须严格地轮流执行它们的临界区，因此，执行的速度由进程中较慢的一个决定。一个进程发生意外，另一个进程将被永久阻塞。解决方法：每个进程应该有使用临界区的钥匙，以使一个进程发生意外后，其它的进程仍能访问临界区。共享全局变量第 74 页操作系统第2种途径每个进程都可查看另一进程的状态（用布尔数组flag 表示），但不能修改它。一个进程试图进入临界区之前，应首先查看其它进程的状态如果没有其它的进程处于临界区，该进程将进入临界区（置自己的flag =true）补充知识：互斥软件解决第 75

60、 页75共享的全局变量是：varvar flag: arrayarray0.1ofof boolean;它被初始化为false缺点: 不能保证互斥，因为两个进程可能同时存在各自的临界区；一个进程在临界区中发生意外或在刚把flag置为true还没有进入其临界区之前发生意外，则其它的进程将会被永远阻塞。解决方法: 进程在进入临界区之前，设置自己的flag补充知识：互斥软件解决第 76 页操作系统第3种途径查看其它进程状态之前，先将自己的flag置于true如果在将自己的flag置于true时，看到其他进程在临界区中，则进程阻塞直到其它进程退出临界区。补充知识：互斥软件解决第 77 页操作系统补充知