第二章进程的描述与控制 os的基本任务是对“进程”的管理; 多个进程可以并发执行 进程在系统中有多种状态,状态间 可转换; 进程与线程的区别。 2.1前趋图和程序执行 作>前趋图的定义 前趋图 (Procedence grap h)是一个有向 无循环图DAG( Directed Acyclic Graph)。 结点:语句、程序段或进程。 描 初始节点 终止节点 控 边:执行顺序。 2>重量:程序量或执行时间 CUIT徐红
1 第二章 进程的描述与控制 OS的基本任务是对“进程”的管理； 多个进程可以并发执行； 进程在系统中有多种状态，状态间 可转换； 进程与线程的区别。 操 作 系 统 | 进 程 的 描 述 与 控 制 2 CUIT 徐虹 2．1 前趋图和程序执行 ¾前趋图的定义 ¾前趋图（Procedence Graph）是一个有向 无循环图DAG（Directed Acyclic Graph）。 ¾结点：语句、程序段或进程。 ¾初始节点 ¾终止节点 ¾边：执行顺序。 ¾重量：程序量或执行时间
例:有7个结点的前趋图。 P={P1,P2,P3,P4,P5,P6,P7} 操→={(P1,P2),(P1,P3),(P1,P4),(P2,P5), 系(P3,P5),(P4,P6),(P5,P7),(P6,P7)} 3 CUIT徐红 >程序的顺序执行 个复杂的程序通常可以分为若干程序 段,并且必须按照某种先后次序来执行。 例1:输入计算打印 作系统|进程的描述与控 例2:语句执行顺序 >SI: a:=x+y S2: b 5 S3:c:=b+1 CUIT徐红
2 操 作 系 统 | 进 程 的 描 述 与 控 制 3 CUIT 徐虹 1 2 3 4 5 6 7 例：有7个结点的前趋图。 P = { P1，P2，P3，P4，P5，P6，P7 } → = {（P1，P2），（P1，P3），（P1，P4）， （P2，P5）， （P3，P5），（P4，P6），（P5，P7），（P6，P7）} 操 作 系 统 | 进 程 的 描 述 与 控 制 4 CUIT 徐虹 ¾程序的顺序执行 ¾一个复杂的程序通常可以分为若干程序 段，并且必须按照某种先后次序来执行。 ¾例1：输入——计算——打印 ¾例2：语句执行顺序 ¾S1：a ：= x + y ¾S2：b ：= a – 5 ¾S3：c ：= b + 1
>顺序执行程序的特点 程序的顺序性。 操作系统|进程的描述与 >程序在运行时独占主机资源。 >程序的执行结果与其执行速度无关。 程序执行时的初始条件相同,其结 果必相同。 CUIT徐红 程序的并发执行 程序执行环境 >独立性,逻辑上是独立的。 作系统|进程的描述与控 随机性:输入和执行开始时间都是随机的。 资源共享:资源共享导致对进程执行速度 的制约。 6 CUIT徐红
3 操 作 系 统 | 进 程 的 描 述 与 控 制 5 CUIT 徐虹 ¾顺序执行程序的特点： ¾程序的顺序性。 ¾程序在运行时独占主机资源。 ¾程序的执行结果与其执行速度无关。 ¾程序执行时的初始条件相同，其结 果必相同。 操 作 系 统 | 进 程 的 描 述 与 控 制 6 CUIT 徐虹 ¾程序的并发执行 ¾程序执行环境 ¾独立性，逻辑上是独立的。 ¾随机性：输入和执行开始时间都是随机的。 ¾资源共享：资源共享导致对进程执行速度 的制约
>程序的并发执行 并发执行是指两个程序执行时间上是重叠 的。凡是能由一组并发程序完成的任务,都 操能由相应的单个程序完成。 系统|进程的描述与控制 统例1:有一批程序,而每个程序需输入,计算, 打印三项操作。其程序段并发执行的前趋图: C1→C2→C3→C4→ CUIT徐红 P1→P2→P3→P4→ y 152. Begin integer N:=0 Cobegin Program a: begin Program b: begin LI: N: =N+I L2: Print(N; N: =0; 作系统|进程 Goto LI; Goto L2 End End Coend 描当N=5时,如果N=N+在 print(N)和N:=0 前 中间 后 控 打印 执行后N=0 0 CUIT徐红
4 操 作 系 统 | 进 程 的 描 述 与 控 制 7 CUIT 徐虹 ¾程序的并发执行 并发执行是指两个程序执行时间上是重叠 的。凡是能由一组并发程序完成的任务，都 能由相应的单个程序完成。 例1：有一批程序，而每个程序需输入，计算， 打印三项操作。其程序段并发执行的前趋图: I1 → I2 → I3 → I4 → ↘↘↘↘ C1 → C2 → C3 → C4 → ↘↘↘↘ P1 → P2 → P3 → P4 → 操 作 系 统 | 进 程 的 描 述 与 控 制 8 CUIT 徐虹 例2．Begin integer N:=0; Cobegin Program A : begin Program B : begin L1 : N:=N+1; L2 : Print (N); N:=0; Goto L1； Goto L2； End End Coend End 当N=5时，如果 N=N+1 在 print（N）和 N:=0 前 中间 后 打印 655 执行后N= 0 0 1
⑧例3.设有堆栈S,栈指针p,栈中存放相应的数 据块地址,程序 getaddr(top)从栈中取地址 reladdr(bk)将地址放入栈S中 Procedure getaddr(top) Procedure reladdr (blk) 统 Begin begin Local top+l top r blk->(top) top-l top en 与 return(r) end 先执行 reladdr的top=top+1,接着执行 getaddr的(top CUIT徐红 >程序并发执行过程及条件 ( Bernstein条件) Cobegin Sl;S2;S3;…;Sn; Coend 描 Sn+1; 控 S1、S2、…Sn可以由同一程序段 中的不同语句组成。 CUIT徐红
5 操 作 系 统 | 进 程 的 描 述 与 控 制 9 CUIT 徐虹 例3．设有堆栈S，栈指针top ，栈中存放相应的数 据块地址，程序 getaddr（top）从栈中取地址， reladdr（blk）将地址放入栈S中。 Procedure getaddr (top) Procedure reladdr(blk) Begin begin Local r top+1——> top (top)——> r blk ——> (top) top-1——> top end return (r) end 先执行 reladdr 的top=top+1，接着执行getaddr的(top)—> r 操 作 系 统 | 进 程 的 描 述 与 控 制 10 CUIT 徐虹 ¾程序并发执行过程及条件 （Bernstein条件） S0; Cobegin S1；S2；S3；……；Sn; Coend Sn+1; S1、S2、……、Sn可以由同一程序段 中的不同语句组成
将任一语句划分为两个变量的集合R (Si)和W(Si) 读集R(Si)={al,a2,…,am} 操作系统|进程的描述与 写集W(Si)={b1,b2,……,bn} 如对语句S1和S2有: R(S1)nW(S2)={} w(S1)∩R(S2)={Φ} w(S1)∩W(S2)={Φ} 制 成立,则语句S1和s2可并发执行。 CUIT徐红 例1.语句c=a-b和w=c+1 R (c=a-b)=fa, b) W(e=a-b)=fc 作系统|进程的描述与控制2 R(w=c+1)={c} (w=c+1)={w R(w=c+1)nw(c=a-b)=c 语句c=a-b和w=c+1不能并发执行。 CUIT徐红
6 操 作 系 统 | 进 程 的 描 述 与 控 制 11 CUIT 徐虹 将任一语句划分为两个变量的集合R （Si）和W（Si）: 读集R（Si）= {a1，a2，……，am} 写集W（Si）= {b1，b2，……，bn} 如对语句S1和S2有： R（S1）∩ W（S2） = {Ф} W（S1）∩ R（S2） = {Φ} W（S1）∩ W（S2）= {Φ} 成立，则语句S1和S2可并发执行。 操 作 系 统 | 进 程 的 描 述 与 控 制 12 CUIT 徐虹 例1． 语句 c = a – b 和 w = c + 1 R（c = a – b ）= {a, b } W（c = a – b ）= { c } R（w = c + 1 ）= { c } W（w = c + 1 ）= { w } R（w = c + 1 ）∩ W（c = a – b ）= { c } 语句 c = a – b 和 w = c + 1 不能并发执行
例2.S1:a=x+y S3:c=a-b s4:w=c+1 操R(S1)={x,y} (S1)={a} 系R(S2)={z} S2)={b} R(S3)={a,b} W(S3)={c} 程R(S4)={c} W(S4)={w} 语句S和S2能并发执行。 与语句S1和S3,S2和S3,S3和s4不能并发执行。 SI IT翻 资源共享 >资源共享是指系统中的硬件资源和 软件资源不再由单个用户所独占,而 为n个用户共同使用。 作系统|进程的描述与控 由系统进行统一分配(硬件)和由 程序自行使用(数据基,变量、队列 等) >程序共行执行与资源共享之间互为 存在条件。 CUIT徐红
7 操 作 系 统 | 进 程 的 描 述 与 控 制 13 CUIT 徐虹 例2． S1 : a = x + y S2 : b = z + 1 S3 : c = a – b S4 : w = c + 1 R（S1）= { x , y } W（S1）= { a } R（S2）= { z } W（S2）= { b } R（S3）= { a ,b } W（S3）= { c } R（S4）= { c } W（S4）={w } 语句 S1 和 S2 能并发执行。 语句 S1 和 S3，S2 和S3，S3 和S4 不能并发执行。 S1 S3 → S4 S2 操 作 系 统 | 进 程 的 描 述 与 控 制 14 CUIT 徐虹 ¾资源共享 ¾资源共享是指系统中的硬件资源和 软件资源不再由单个用户所独占，而 为 n 个用户共同使用。 ¾由系统进行统一分配（硬件）和由 程序自行使用（数据基，变量、队列 等） ¾程序共行执行与资源共享之间互为 存在条件
程序并发执行的特点 失去程序的封闭性和可再现性 程序与计算不再一一对应 操作系统|进程的描述与 程序并发执行的相互制约 执行暂停执行 CUIT徐红 2.2进程的概念 >进程的定义 进程的定义:进程是程序在一个数据集 作系统|进程的描述与控 合上的运行过程,是系统进行资源分配 和调度的一个独立的基本单位 进程的特征 动态性 并发特征 独立特征 异步特征 6 机构特征 CUIT徐红
8 操 作 系 统 | 进 程 的 描 述 与 控 制 15 CUIT 徐虹 ¾程序并发执行的特点 ¾失去程序的封闭性和可再现性 ¾程序与计算不再一一对应 ¾程序并发执行的相互制约 ¾执行——暂停——执行 操 作 系 统 | 进 程 的 描 述 与 控 制 16 CUIT 徐虹 2．2 进程的概念 ¾进程的定义 ¾进程的定义: 进程是程序在一个数据集 合上的运行过程，是系统进行资源分配 和调度的一个独立的基本单位。 ¾进程的特征 ¾动态性 ¾并发特征 ¾独立特征 ¾异步特征 ¾机构特征
进程与程序的关系 操 进程 程序 概念 动态实体 静态实体 强调执行过程 是指令的有序集合 进特征 并发性、独立性、无并行特征 异步性 是静止的 是竞争计算机系统 的描述与控制1 资源的基本单位 两者联系不同的进程可以共享同一个程序 只要对应的数据集不同 CUIT徐红 2.3进程状态及其转换 操>进程状态 个进程的生命期可以划分为一组状 作系统|进程的描述与控制8 态,这些状态刻画了这个进程。系统根据 PCB结构中的状态值控制进程。 >就绪状态( Ready) 执行状态 等待状态(阻塞状态) 新(New)状态 终止状态( Terminated) CUIT徐红
9 操 作 系 统 | 进 程 的 描 述 与 控 制 17 CUIT 徐虹 ¾进程与程序的关系 进程 程序 概念 动态实体， 静态实体， 强调执行过程 是指令的有序集合 特征 并发性、独立性、 无并行特征， 异步性， 是静止的 是竞争计算机系统 资源的基本单位 两者联系 不同的进程可以共享同一个程序， 只要对应的数据集不同 操 作 系 统 | 进 程 的 描 述 与 控 制 18 CUIT 徐虹 2．3 进程状态及其转换 ¾进程状态 一个进程的生命期可以划分为一组状 态，这些状态刻画了这个进程。系统根据 PCB结构中的状态值控制进程。 ¾就绪状态（Ready） ¾执行状态 ¾等待状态（阻塞状态） ¾新（New）状态 ¾终止状态（Terminated）
挂起状态( Suspend) 把一个进程挂起使之处于静止状 态,以便研究它的执行情况获对它进 操作系统|进程的描述与控制9 行修改。 用户终端需要; 进程的需要:考查、修改获协调各子 进程时; OS的需要:改善系统运行性能,调节负 荷 对换的需要:缓和内存紧张的情况; CUIT徐红 进程状态转换 Release New Readi Event Occurs Event Blocked Five-State Process Model CUIT徐红
10 操 作 系 统 | 进 程 的 描 述 与 控 制 19 CUIT 徐虹 ¾挂起状态（Suspend） 把一个进程挂起使之处于静止状 态，以便研究它的执行情况获对它进 行修改。 ¾用户终端需要； ¾父进程的需要：考查、修改获协调各子 进程时； ¾OS的需要：改善系统运行性能，调节负 荷； ¾对换的需要：缓和内存紧张的情况； 操 作 系 统 | 进 程 的 描 述 与 控 制 20 CUIT 徐虹 ¾进程状态转换