操作系统 (2)

《操作系统 (2)》由会员分享，可在线阅读，更多相关《操作系统 (2)（187页珍藏版）》请在金锄头文库上搜索。

1、第二章 进程管理,2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制 2.6 进程通信 2.7 线程,2.1 进程的基本概念,在无操作系统和单道程序系统中，程序的执行是顺序的。而随着多道程序的出现，系统中程序执行环境变化了，尤其当出现同名程序并发执行时，迫切需要一个实体来描述程序的执行过程。 这个实体就是进程。,2.1.1 程序的顺序执行及其特征,程序是存储在存储介质上的（可执行）文件。 程序是一个在时间上按严格次序前后相继的操作序列，是一个静态的概念。 程序体现了编程人员要求计算机完成所要求功能时应该采取的顺序步骤。 一般用户在编写程序时

2、不考虑在自己的程序执行过程中还有其他用户程序存在。,1. 程序的顺序执行,通常可以将一个程序分成若干段，在各段之间必须按某种顺序执行，仅当前一操作(程序段)执行完后，才能执行后继操作。也就是说先后有顺序关系。 例如，在进行计算时，总须先输入程序和数据，然后进行计算，最后才能打印计算结果。 再如下述三条语句：S1: a=x+y; S2: b=a-5; S3: c=b+1;也必须按顺序执行。,2. 程序顺序执行时的特征,(1) 顺序性： 按程序规定的顺序执行。 (2) 封闭性： 不受外界干扰。 (3) 可再现性： 只要初始条件和环境相同，不论何时执行，结果总是相同的。,2.1.2 前趋图,前趋图（

3、Precedence Graph）是一个有向无循环图，记为DAG（Directed Acyclic Graph），用于描述进程之间执行的前后关系。 图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序（Partial Order）或前趋关系（Precedence Relation）“”。,前趋图及相关概念,=（Pi，Pj）| Pi必须在 Pj开始前执行完毕，如果（Pi，Pj），可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。 在前趋图中，把没有前趋的结点称为初始结点（Initial Node），把没有后继的结点称为终止结点（F

4、inal Node）。 每个节点还具有一个权重（Weight），用于表示该节点所含有程序的执行时间。 前趋图中必须不能有循环。 图2-1中的前趋关系表示为IiCiPi 和 S1S2S3,前趋图的示例,前趋图2-2a存在以下前趋关系： P1P2, 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), (P3, P5), (P4, P6), (P4, P7), (P5

5、, P8), (P6, P8), (P7, P9), (P8, P9) ,2.1.3 程序的并发执行及其特征,1. 程序的并发执行 在图2-1a所示的IiCiPi前趋关系中，ICP必须是顺序执行的，但是并不存在PiIi+1关系，因此对此批程序的处理可以并发进行。 由前趋图可得前趋关系为： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1,并发示例,对于具有下述四条语句的程序段：S1: a :=x+2S2: b :=y+4S3: c :=a+bS4: d :=c+b S3要等待S1和S2执行完毕才能进行，S4要依赖于S3，但S1和S2没有先后关系可以并发。于是可得前趋关系图。,2

6、. 程序并发执行时的特征,设有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时， 都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。可能出现以下不同结果： N=N+1在Print(N)和N=0之前，N为：n+1, n+1, 0 N=N+1在Print(N)和N=0之后，N为：n, 0, 1 N=N+1在Print(N)和N=0之间，N为：n, n+1, 0,2. 程序并发执行时的特征,1) 间断性 2) 失去封闭性 3) 不可再现性,2.1.4 进程的特征与状态,在多道程序环境下，程序的执行将失去其封闭性，从而导

7、致不可再现性。这就决定了程序不能参与并发执行，因此，程序的运行就失去了意义。 于是引入了“进程”的概念。,1. 进程的特征和定义,1) 结构特征：程序段+数据段+PCB（=进程实体）。 2) 动态性：进程刻画的是程序的执行过程。 3) 并发性：进程可以并发执行。 4) 独立性：进程是抢占资源的基本单位，能独立运行、独立申请资源、独立进行调度。 5) 异步性：各并发进程彼此独立，以不可预知的速度向前推进。,较典型的进程定义,(1) 进程是程序的一次执行。 (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 (3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一

8、个独立单位。 在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。,进程的定义举例,(1)进程是可以并行/发执行的计算部分(S.E.Madnick，J.T.Donovan)； (2)进程是一个独立的可以调度的活动(E.Cohen，D.Jofferson)； (3)进程是一抽象实体，当它执行某个任务时，将要分配和释放各种资源(P.Denning)； (4)行为的规则叫程序，程序在处理机上执行时的活动称为进程(E.W.Dijkstra)； (5)一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述

9、进程(Brinch Hansen)。 他们突出了进程是一个动态的执行过程。,2. 进程的三种基本状态,1) 就绪(Ready)状态 2) 执行状态 3) 阻塞状态,3.挂起状态,所谓进程挂起是指暂时将某个进程“冻结”,不让其参与操作系统内部的进程调度而变为静止的状态。,1)引入挂起状态的原因,(1) 终端用户的请求。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。,2) 进程状态的转换,引入挂起状态后，又将增加从挂起到非挂起和从非挂起到挂起状态的转换。几种可能情况如下： (1) 活动就绪静止就绪。 (2) 活动阻塞静止阻塞。 (3) 静止就绪活动就绪。 (4) 静止阻

10、塞活动阻塞。,具有挂起状态的进程状态图,4. 进程的创建和终止,在一个进程的生命周期中，还存在着创建和终止状态。即进程的出生与死亡。,1）创建状态,创建一个进程要分作两步： 为新进程创建一个PCB结构，并填写必要的信息。 其次是为其分配资源 一个进程处于此两步之间时的状态就被称为处于创建状态。 引入创建状态的目的是为了保证进程调度必须在创建完成之后进行，以确保对进程控制块操作的完整性。同时也增加了管理的灵活性。,2）终止状态,当一个进程的执行进入正常结束或非正常结束，或被其它进程所终止，进程进入终止状态。 进程终止也分作两步：释放资源，释放PCB。 当一个进程进入终止状态后，不能再执行，且资源

11、基本上都释放，但还保留着PCB，其中保存着状态码和一些计时和统计信息，供其它进程收集。一旦信息被收集完毕，则删除PCB，进程被彻底清除。,具有创建和终止的进程的状态,具有创建、终止和掛起状态的进程状态转换图,2.1.5 进程控制块,为了描述和控制进程的活动，系统为每个进程定义并增加了个数据结构进程控制块PCB（Process Control Block），它是进程实体的一部分，记录操作系统所需的、用于描述进程资源占用、当前状况以及控制进程运行的全部信息。 PCB集中反映一个进程的动态特征。 当一个进程完成其功能之后，系统则释放PCB，进程也随之消亡。,1. 进程控制块的作用,PCB是OS感知进

12、程存在的唯一实体。 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。 或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。,2. 进程控制块中的信息,PCB包含一个进程的完整的描述信息、控制信息及资源信息，有些系统中还有进程调度、等待所使用的现场保护区等信息。,1) 进程标识符,进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符： (1) 内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号（PID）。 设置内部标识符主要是为了方便系统使用。 (2) 外

13、部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系， 还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。,2) 处理机状态,处理机状态信息主要是由处理机的各种寄存器中的内容组成的。 通用寄存器（又称为用户可视寄存器）：是用户程序可以访问的，用于暂存信息。 在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个； 指令计数器（PC/IP）：存放下一条要访问指令的地址； 程序状态字PSW：含有状态信息，如条件码、执行方式、 中断屏蔽标志等； 用户栈指针：指每个用户进程都有一个

14、或若干个与之相关的栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,3) 进程调度信息, 进程状态：指明进程的当前状态，作为进程调度和对换时的依据； 进程优先级：用于描述进程使用处理机的优先级别的一个整数， 优先级高的进程应优先获得处理机； 进程调度所需的其它信息：它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等； 事件：是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,4) 进程控制信息, 程序和数据的地址：进程的程序和数据所在的内存或外存(首)地址，以便再调度到该进程执行时，能从PCB中找到其程序和数据； 进程同步和通信

15、机制：指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中； 资源清单：是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链接指针：它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,3. 进程控制块的组织方式,1）链接方式 2）索引方式,1）链接方式,2）索引方式,2.2 进 程 控 制,进程和处理机管理的一个重要任务是进程控制。 所谓进程控制，就是系统使用一些具有特殊功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调工作，实现资源共享的目的。 进程控制是原语（Pr

16、imitive）来实现的。,原语,一般地，把系统态下的某些具有特定功能的程序段称为原语。 原语执行的是原子操作（Atomic Operation）。 原语共分为两类： 机器指令级：其特点是执行期间不允许中断，正如在物理学中的原子一样，在OS中它是不可分割的基本单元。 功能级的：其特点是作为原语的程序段不允许并发执行。 这两类原语都是在系统态下执行，且都是为了完成某个系统管理所需要的功能和被高层软件所调用。 在OS中，通常把进程控制用程序段做成原语。用于进程控制的原语有：创建，撤消，阻塞，唤醒等。,2.2.1 进程的创建,进程的创建就要为将要执行的程序在系统中创建一个用于控制的执行实体。,1. 进程关系图,进程关系图(Process Graph)是用于描述系统内进程家族的有向图。在该有向图中，一条从Pi到Pj的有向边说明了他们之间的父子关系。 进程间的父子、祖先、子孙等关系就构成了一颗树。 子进程可以继承父进程的资源，但结束时要归还资源；（父进程被撤销也要撤销其所有的子进程。） 在PCB表设有进程家族标志。,