第二章进程的描述与控制 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可以由同一程序段 中的不同语句组成