计算机操作系统_第2章(2016-2017-1)

就绪队列指针
阻塞队列指针
空闲队列指针
…
第二章 进 程 管 理
4. 进程控制块的组织方式
索引方式。根据所有进程状态的不同，建立几张索引表，
并把各索引表在内存的首地址记录在内存的一些专用单
元中。
执行指针 就绪索引表 就绪表指针 阻塞索引表 阻塞表指针 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7
第二章 进 程 管 理
第二章 进程的描述与控制
2.1 前趋图和程序执行
2.2 进程的描述
2.3 进程控制
2.4 进程同步 2.5 经典进程的同步问题
2.6 进程通信
2.7 线程的基本概念
2.8 线程的实现
第二章 进 程 管 理
2.1 前驱图和程序执行
2.1.1 前趋图
前趋图是一个有向无循环图，记为DAG(Directed Acyclic
第二章 进 程 管 理
2.3.1 操作系统内核
OS内核包含两大功能： 支撑功能。中断处理、时钟管理、原语操作
中断处理是内核最基本的功能，是整个OS赖以活动的
基础；原语 (Primitive) 是由若干条指令组成的，用于完
成 一 定 功 能 的 一 个 过 程 。 原 语 是 “ 原 子 操 作 (Action Operation)”，不可分割、不允许中断、常驻内存。
Graph)，用于描述进程或程序段之间执行的前后顺序。
P2 P5 P1 P3 P6 P4 P7 (a ) 具有九个结点的前趋图 P8 P9 S2 S1
图中每个结 点描述一个程
序段、进程或 一条语句。
S3
(b ) 具有循环的前趋图
第二章 进 程 管 理
2.1.1 前趋图
图 2-1(a)所示前趋图的前趋关系：
独立性。一个能独立运行、独立获得资源和独立接受调
度的基本单位。 异步性 。进程按各自独立的、不可预知的速度向前推进。
OS必须保证进程并发执行的结果是可再现的。
第二章 进 程 管 理
2.2.2 进程的基本状态及转换
1. 进程的三种基本状态 就绪(Ready)状态 进程已分配到除CPU以外的所有必要资源，只要再获得 CPU，便可立即执行。 执行(Running)状态 进程已获得CPU，其程序正在执行的状态。
指程序在执行时独占系统的全部资源。
3）可再现性 只要初始条件相同，一个程序的多次重复 执行得到相同的结果。
第二章 进 程 管 理
2.1.3 程序并发执行
1. 程序的并发执行
I1 I2 I3 I4
图 2-3 程序并发
C4
C1
C2
C3
执行时的前趋图
P1
P2
P3
P4
Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之 间，可以并发执行。
第二章 进 程 管 理
2.2.4 进程管理中的数据结构
2. 进程控制块PCB的作用 使得一个在多道程序环境下不能独立运行的程序成为
一个能独立运行的基本单位。
作为独立运行基本单位的标志。
能实现间断性运行方式。
提供进程管理所需要的信息。 提供进程调度所需要的信息。 实现与其它进程的同步与通信。
第二章 进 程 管 理
OS 中 配 置 了 一 个 专 门 的 数 据 结 构 ， 称 为 进 程 控 制 块 (Process Control Block, PCB)。系统利用PCB来描述进程 的基本情况和活动过程，进而控制和管理进程。
第二章 进 程 管 理
2.2.1 进程的定义与特征
由程序段、相关的数据段和PCB三部分构成进程实体。 较典型的进程定义有： (1) 进程是程序的一次执行。
P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
也可表示为：
P={P1, P2, P3, P4, P5, P6, P7, P8, P9}
={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9)} 注意，前趋图中必须不存在循环，否则必然会产生不可 能实现的前趋关系。如图 2-1(b)所示的前趋关系： S2→S3, S3→S2
第二章 进 程 管 理
2.1.2 程序顺序执行
1. 程序的顺序执行
指若干个程序或程序段之间必须严格按照某种先后次序来执
行，仅当前一操作(程序段)执行完后，才能执行后继操作。 S1: a=x+y; S2: b=a-5; S3: c=b+1;
2. 程序顺序执行时的特征
1）顺序性
2）封闭性
处理机严格按照程序所规定的顺序执行
程便处于终止状态；相关信息被收集走之后，PCB将被释
放，该进程才被系统删除。
第二章 进 程 管 理
2.2.3 挂起操作和进程状态的转换
1. 挂起操作的引入
终端用户的需要。当终端用户在其程序运行期间发
现有可疑问题，希望暂停程序的运行。 父进程请求。父进程挂起子进程，以便考察和修改。 负荷调节的需要。当实时系统中的工作负荷较重。 操作系统的需要。 “挂起”是使进程不能继续执行，即使挂起后的进程 处于就绪状态，它也不能参与CPU的竞争。被挂起的 进程处于静止状态，没被挂起的进程则处于活动状态。
阻塞
I/O请求
执行
图 2-5 进程的三种基本状态及其转换
第二章 进 程 管 理
2.2.2 进程的基本状态及转换
3. 创建状态和终止状态 创建状态
一个正被创建的进程，在创建工作尚未完成之前将处
于创建状态。处于创建状态的进程，当获得了所需的资 源和初始化完其PCB，便可由创建状态转入就绪状态。 终止状态 一个进程已结束运行，系统已回收了除PCB之外的资源， 等待其他进程从它的进程控制块中收集有关信息时，该进
资源管理功能。进程管理、存储器管理、设备管理
4. 进程控制块的组织方式 线性方式。所有的PCB都组织成一张线性表。 链接方式。把具有相同状态进程的PCB分别通过PCB 中的链接字链接成一个进程队列。可以形成就绪队 列、若干个阻塞队列、空白队列。
执行指针 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 PCB9 4 3 0 8 7 9 0 1
第二章 进 程 管 理
3. 进程控制块中的信息 2) 处理机状态 处理机状态信息主要是由处理机中各种寄存器的内容组 成，用于CPU切换时保存现场信息和恢复现场信息。 3) 进程调度信息 在PCB中存放的一些与进程调度和进程对换有关的信息。
包括：进程状态、进程优先级、事件（进程由执行状态转变
为阻塞状态发生的事件，即阻塞原因）以及进程调度所需的 其它信息。
第二章 进 程 管 理
2.2.3 挂起操作和进程状态的转换
2. 引入挂起操作后三个进程状态的转换 进程控制一般是由OS内核中的原语来实现。 原语 (Primitive) 是由若干条指令组成的，用于完成一定
功能的一个过程。原语是“原子操作(Action Operation)”， 不可分割、不允许中断、常驻内存。 OS 通过使用挂起 原语Suspend和激活原语Active来实现挂起和激活操作。
第二章 进 程 管 理
1. 程序的并发执行 对于具有下述四条语句的程序段：
S1: a=x+2
S4: d=c+b
S1 S3 S2
S2: b=y+4
S3: c=a+b
S4
第二章 进 程 管 理
2.1.3 程序并发执行
2. 程序并发执行时的特征 间断性。 程序的运行过程出现“执行-暂停-执行”现象。 失去封闭性。程序本身的执行环境受到外界程序的影响。 不可再现性。一个程序的多次重复执行可能会得到不同 的结果。 例如，有两个循环程序 A和 B，它们共享一个变量 N 。 程序A每执行一次时，都要做N=N+1操作；程序B每执行 一次时，都要执行Print(N)操作，然后再将N置成“0”。 程序A和B以不同的速度运行。 思考：假定某时刻变量N的值为n，分析其执行结果？
释 放
执行
请 求 I/O
起 挂
激活 活动 就绪 激活 挂起 静止 就绪
释 放
活动 阻塞
挂起
静止 阻塞
第二章 进 程 管 理
课前复习： 思考：
1. 在操作系统中为什么要引入进程概念？它会产生
什么样的影响？ 2. 试比较进程与程序的异同。
第二章 进 程 管 理
2.2.4 进程管理中的数据结构
OS 常将计算机中的各类资源抽象为相应的各种数据结
(1) 活动就绪→静止就绪。(2) 活动阻塞→静止阻塞。
(3) 静止就绪→活动就绪。(4) 静止阻塞→活动阻塞。
第二章 进 程 管 理
2.2.3 挂起操作和进程状态的转换
• 处于静止状态的进程，只有通过“激活”，才能转换 成活动状态。 3. 引入挂起操作后五个进 程状态的转换 NULL →创建 创建→活动就绪 创建→静止就绪 执行→终止
第二章 进 程 管 理
3. 进程控制块中的信息 4) 进程控制信息 进程控制信息包括：① 程序和数据的地址，是指进程 的程序和数据所在的内存或外存地 (首)址；② 进程同步
和通信机制；③ 资源清单；④ 链接指针，它给出了本进
程(PCB)所在队列中的下一个进程的PCB的首地址。
第二章 进 程 管 理
第二章 进 程 管 理源自2.3 进 程 控 制• 进程控制是进程管理中最基本的功能，主要包括创建 和终止进程以及负责进程运行过程中的状态转换等功 能。进程控制由OS内核中的原语来实现。