操作系统 第2章

1、第二章第二章 进程的描述与控制进程的描述与控制2.1 前趋图和程序执行前趋图和程序执行2.2 进程的描述进程的描述2.3 进程的控制进程的控制2.4 线程的基本概念线程的基本概念2.1 前趋图和程序执行前趋图和程序执行一、前趋图的定义一、前趋图的定义 有向无循环图DAG，包括： 结点：可表示一个语句、程序段或进程； 包括 初始结点：无前趋 终止结点：无后继 有向边：两结点间的前趋关系； pipj：pi必须在必须在pj开始执行之前完成开始执行之前完成 pi为为pj的直接前趋，的直接前趋， pj为为pi的直接后继。的直接后继。注：前趋图中必须不存在循环！注：前趋图中必须不存在循环！ 正确例子：正确

2、例子：P=p1,p2,p3,p4,p5=(p1,p2),(p1,p3),(p2,p4),(p3,p5),(p4,p5)错误例子：错误例子：s2s3, s3s2p1p2p3p4p5s1s2s32.1 前趋图和程序执行前趋图和程序执行二、程序顺序执行二、程序顺序执行 一个程序由若干程序段组成，这些程序段的执行必须是顺序的；同时程序与程序之间也必须顺序执行。例：例：特征：特征： 1. 顺序性： 2. 封闭性：程序的执行结果不受外界因素的干扰。 3. 可再现性：只要程序执行时的环境和初始条件相同，其执行结果 必然相同。 C1P1I1I2C2P2I为输入操作；为输入操作；C为计算操作；为计算操作；P为打

3、印操作。为打印操作。 程序程序1 程序程序2 2.1 前趋图和程序执行前趋图和程序执行三、程序并发执行三、程序并发执行 多个程序同时在系统中运行，这些程序的执行在时间上是重叠的，即前一程序的执行尚未结束，后一程序的执行已经开始。例：例： 程序与程序之间、程序段与程序段之间均可并发执行。C1P1I1I2C2P2程序段之间顺序执行；程序段之间顺序执行；程序之间并发执行。程序之间并发执行。2.1 前趋图和程序执行前趋图和程序执行特征：特征： 1. 间断性：程序执行有“执行-暂停-执行”的活动规律。 2. 失去封闭性：某程序执行时，必然受到参与并发执行的其它程序 的影响。 3. 不可再现性 ：计算结果

4、与并发程序执行速度有关。即同一程序， 使用相同输入、在相同环境下运行，却可能获得完 全不同的结果。 2.1 前趋图和程序执行前趋图和程序执行不可再现性的例子：不可再现性的例子：两个并发执行的程序A和B，如下所示： A：N:=N+1； B：print（N）； N:=0；分析：1）并发：A、B交替占用CPU执行；2）异步性 打印结果：打印结果： 9 8 89 8 8N N的值：的值： 0 1 00 1 0导致：导致： CPU交替执行交替执行A、B的语句时顺序可能不同的语句时顺序可能不同！1) N:=N+1; print(N); N:=0;2) print(N); N:=0; N:=N+1; 3)

5、print(N); N:=N+1; N:=0; 设某次循环前，N的值为8CPU执行顺序2.2 进程的描述进程的描述多道程序环境下，必须引入进程的例子：多道程序环境下，必须引入进程的例子： 编译程序C编译源程序1，执行到a时因某种原因无法继续，致使CPU空闲，此时转去编译源程序2，执行到b。 begin - b:- - a:- - end编译程序编译程序C源程序源程序1 1数据部分数据部分源代码源代码1目标代码目标代码1 源程序源程序2 2数据部分数据部分源代码源代码2目标代码目标代码22.2 进程的描述进程的描述问题问题1 1：谁占用谁占用CPU执行？源程序执行？源程序1和和2以什么身份出现以

6、什么身份出现？问题问题2 2：程序计数器程序计数器PC中记录的是中记录的是a 还是还是 b？答案答案1 1：占用占用CPU执行的是编译程序执行的是编译程序C 。 源程序源程序1和和2是编译程序是编译程序C的数据对象。的数据对象。答案答案2 2：说不清：说不清程序计数器程序计数器PC中记录的是中记录的是a 还是还是 b。引入进程后：引入进程后：答案答案1：占用：占用CPU执行的是分别是进程执行的是分别是进程1和进程和进程2。 源程序源程序1和和2分别是进程分别是进程1和进程和进程2的数据对象。的数据对象。答案答案2：进程：进程1占用占用CPU执行时，执行时，PC中记录的是中记录的是a； 进程进程

7、2占用占用CPU执行时，执行时，PC中记录的是中记录的是 b。2.2 进程的描述进程的描述 引入进程：引入进程： 进程进程2 2 进程进程1 1 begin - b:- - a:- - end编译程序编译程序C源程序源程序1 1数据部分数据部分源代码源代码1目标代码目标代码1 源程序源程序2 2数据部分数据部分源代码源代码2目标代码目标代码22.2 进程的描述进程的描述一、进程的定义与特征一、进程的定义与特征定义：定义： 进程：可并发执行的程序在一个数据集合上的运行过程。一个进程的物理实体包括：一个进程的物理实体包括： 程序部分 数据部分 进程控制块PCB特征：特征：1. 动态性 4. 异步性

8、2. 并发性 5. 结构特征3. 独立性2.2 进程的描述进程的描述程序与进程的对应关系程序与进程的对应关系1 1：一个程序对应两个进程：一个程序对应两个进程 进程进程2 2 进程进程1 1 begin - b:- - a:- - end编译程序编译程序C源程序源程序1 1数据部分数据部分源代码源代码1目标代码目标代码1 源程序源程序2 2数据部分数据部分源代码源代码2目标代码目标代码22.2 进程的描述进程的描述程序与进程的对应关系程序与进程的对应关系2 2：一个进程对应多个程序：一个进程对应多个程序Main( )-open( )-Open( )-return系统调用系统调用进程进程1 1（

9、用户态）（用户态） 用用户户栈栈进程进程1 1（核心态）（核心态）核核心心栈栈2.2 进程的描述进程的描述二、进程的状态二、进程的状态基本状态：基本状态：1.就绪就绪状态（ready）：进程等待分配CPU。 系统中同时处于就绪状态的进程会排成就绪队列。 2.执行执行状态（running）：进程正占用CPU执行其程序中的指令。 在单处理机系统中，任何时刻至多只有一个进程处于执行状态。3.阻塞阻塞状态（blocked）：进程在等待某个事件的发生，故也 称为等待状态（waiting）。 处于阻塞状态的进程会按等待原因进入不同的阻塞队列。4.新新状态（new）：进程正被创建。5.终止终止状态（term

10、inated）：进程已经结束执行。2.2 进程的描述进程的描述基本状态间的转换：基本状态间的转换： 进程的状态是在不断变换的。 执 行 状执 行 状态态就 绪 状就 绪 状态态阻 塞 状阻 塞 状态态新状态新状态终 止 状终 止 状态态接收接收进程调度进程调度退出退出中断中断等待等待I/O或事件或事件I/O或事件发生或事件发生2.2 进程的描述进程的描述三、进程控制块三、进程控制块PCB（Process Control Block）关于关于PCB：定义：定义：存放进程的管理和控 制信息的数据结构，是OS 感知进程存在的唯一标志。 创建进程时，为其建立PCB，并伴随进程运行的全过程，直到进程撤消

11、而回收。 不同OS，PCB大小不同，包含信息不同。PCB中的信息中的信息进程标识符进程标识符进程状态进程状态进程优先级进程优先级进程队列指针进程队列指针执行程序和数据的内存开始地址执行程序和数据的内存开始地址程序计数器程序计数器CPU寄存器寄存器CPU现场保护区现场保护区进程通信进程通信家族联系家族联系占有资源清单占有资源清单栈指针栈指针I/O状态信息状态信息打开文件表打开文件表2.2 进程的描述进程的描述三、进程控制块三、进程控制块PCB（Process Control Block）说明：说明： PCB只能由OS访问，不允许用户进程访问。 一个系统中的PCB数目是一定的，它规定了该系统 可同

12、时拥有的最大进程数目。 每个PCB是系统PCB表中的一个表目。 PCB表常驻内存，存放于OS中专门开辟的PCB区。2.3 进程控制进程控制进程是动态的，有它的开始和结束。在它的生命周期中，在进程是动态的，有它的开始和结束。在它的生命周期中，在 几种不同的状态之间转换。几种不同的状态之间转换。OS提供一些程序段实现这些转换。这些程序段必须用机器提供一些程序段实现这些转换。这些程序段必须用机器 语言书写，且在执行中不可被中断。语言书写，且在执行中不可被中断。原语（原语（Primitive）：指用机器语言书写的、在执行中不可被）：指用机器语言书写的、在执行中不可被 中断的程序段。中断的程序段。原语属

13、于原语属于OS内核（内核（Kernal）。）。完成进程控制的原语有：创建完成进程控制的原语有：创建(Create)、终止、终止(Termination)、 阻塞阻塞(Blocked)、唤醒、唤醒(Wakeup)等。等。2.3 进程控制进程控制一、进程的创建（一、进程的创建（Creation）导致创建新进程的事件：导致创建新进程的事件：1.批处理系统中，接收了一个新作业。批处理系统中，接收了一个新作业。2.分时系统中，用户登录。分时系统中，用户登录。3.运行中的用户程序提出某种服务请求。运行中的用户程序提出某种服务请求。4.基于应用进程自身的需要。基于应用进程自身的需要。 OSOS作为创建者作为

14、创建者说明：说明：1）一个应用进程在其执行期间，通过执行创建进程系统调）一个应用进程在其执行期间，通过执行创建进程系统调 用命令（例如用命令（例如fork），可以创建几个新进程。），可以创建几个新进程。2）而最终进程的创建，是由进程创建原语）而最终进程的创建，是由进程创建原语create( )实现的。实现的。应用进程作为创建者应用进程作为创建者2.3 进程控制进程控制一、进程的创建（一、进程的创建（Creation）3）创建者是父进程，被创建的新进程是子进程。子进程可以）创建者是父进程，被创建的新进程是子进程。子进程可以 创建子子进程，如此轮流下去，构成一棵进程家族树。创建子子进程，如此轮流下

15、去，构成一棵进程家族树。4）父、子进程的执行有两种可能性：）父、子进程的执行有两种可能性： - 父进程和子进程并发执行；父进程和子进程并发执行； - 父进程等待，直到子进程结束。父进程等待，直到子进程结束。2.3 进程控制进程控制Create（）工作流程：（）工作流程：入口入口填写填写PCBPCB的相关项的相关项将将PCBPCB链入就绪队列链入就绪队列返回返回出错出错申请内存空间申请内存空间装入程序和数据装入程序和数据申请空白申请空白PCBPCB分配其它资源分配其它资源申请到申请到申请到申请到申请不到申请不到申请不到申请不到2.3 进程控制进程控制二、进程的终止（二、进程的终止（ Termin

16、ation ）当最后一条语句运行结束时，一个进程终止。此时它使当最后一条语句运行结束时，一个进程终止。此时它使 用相应的系统调用命令（如用相应的系统调用命令（如exit）请求）请求OS将其撤消。将其撤消。在许多系统中，若一个进程终止，则其子孙进程也必须在许多系统中，若一个进程终止，则其子孙进程也必须 同时被终止同时被终止。终止原语的主要操作包括：终止原语的主要操作包括： 1）按照被终止进程的标识符找到其）按照被终止进程的标识符找到其PCB； 2）将其运行的结果信息返给其父进程；）将其运行的结果信息返给其父进程； 3）将其所占资源或归还系统，或还给其父进程；）将其所占资源或归还系统，或还给其父进

17、程； 4）将其）将其PCB置为空；置为空； 5）若被终止进程处于执行状态，则引发进程调度；）若被终止进程处于执行状态，则引发进程调度； 6）若被终止进程有子孙进程，则将其子孙进程同时终止。）若被终止进程有子孙进程，则将其子孙进程同时终止。2.3 进程控制进程控制三、进程的阻塞（三、进程的阻塞（blocked）和唤醒（）和唤醒（wakeup）执行状态进程遇到下列典型事件时，调用执行状态进程遇到下列典型事件时，调用blocked（）原语（）原语 将自己阻塞：将自己阻塞： 1.没有申请到资源；没有申请到资源； 2.启动了启动了I/O操作；操作； 3.运行所需数据尚未到达。运行所需数据尚未到达。当阻塞

18、进程所等待的事件发生时，就会被唤醒。当阻塞进程所等待的事件发生时，就会被唤醒。阻塞过程：阻塞过程： 1）进程状态置为阻塞状态，并移入相应的阻塞队列；）进程状态置为阻塞状态，并移入相应的阻塞队列； 2）引发进程调度。）引发进程调度。唤醒过程：唤醒过程： 进程状态置为就绪状态，并移入就绪队列。进程状态置为就绪状态，并移入就绪队列。总结：总结： 进程控制原语与进程状态转换的对应：进程控制原语与进程状态转换的对应： 执 行 状执 行 状态态就 绪 状就 绪 状态态阻 塞 状阻 塞 状态态新状态新状态终 止 状终 止 状态态create进程调度进程调度termination 中断中断blockedwak

19、eup2.3 进程控制进程控制2.3 进程控制进程控制UNIX系统实例：系统实例：1-进程家族树进程家族树initloginshellloginloginshell终端终端2 2cp终端终端1 1终端终端0 01.1.系统初启后，由系统核心程序建立init进程。init进程读取文件/etc/ttys，该文件告诉系统共有几个终端并提供每个终端的说明。init进程将为每个终端生成一个子进程，然后将自己挂起直到有子进程结束。2.每个子进程等待用户登记（login）使用系统，接着执行shell命令解释程序。3.上图系统中有三个终端。运行在终端0上的子进程仍在等待用户登录；在终端1上的子进程已成功登录了

20、用户，正运行shell等待命令输入；在终端2上的子进程也成功登录了用户，该用户正运行cp程序，cp是shell的子进程，shell 则等待该进程结束。cp结束后，shell再接收输入，创建新进程执行新输入命令。2.3 进程控制进程控制UNIX系统实例：系统实例：2-相关系统调用相关系统调用1. fork系统调用： 功能：建立子进程 返回值：fork对子进程返回0，对父进程返回子进程的标识符。 具体描述：子进程是父进程的一个副本，这就允许父进程可以很容易地 与子进程通信。父子进程都从fork后的那条指令继续执行。2. exec系统调用： 输入参数：新程序名， 功能：以指定程序覆盖当前进程的程序代

21、码。3. wait系统调用： 输入参数：进程号 功能：等待指定进程结束。2.3 进程控制进程控制UNIX系统实例：系统实例：3-shell的内部部分代码的内部部分代码 显示命令提示符 等待用户输入命令行 对命令行分析和解释，得到要运行的程序（例如cp）及其运行参数 if (pid=fork( )0 ) /*父进程代码，典型地如：*/ wait ( pid ); /*等待该子进程结束*/ 显示下一个命令提示符 else /*子进程代码，典型地如：*/ exec(cp, ); 2.4 线程的基本概念线程的基本概念一、线程的引入一、线程的引入引入进程：使多个程序并发运行。进程：1.拥有资源的独立单位

22、； 2.独立调度和分派的基本单位。 进程是可独立运行的基本单位，这正是并发的基础。 但也由于1和2，使系统在创建、撤消进程及进行进程切换 时须付出较大的时空开销。 系统会限制参与并发运行的进程数目及切换频率。 限制了更高程度上的并发。2.4 线程的基本概念线程的基本概念一、线程的引入一、线程的引入引入线程：减少程序并发执行时的时空开销，使并发性更好。将进程的两个属性分开。 进程：拥有资源的独立单位； 线程：进程中的一个实体，是独立调度和分派的基本单位。 -轻型进程线程包含一个线程ID、一个程序计数器、一组寄存器和栈； 它可与其它线程共享所属进程的全部资源。 2.4 线程的基本概念线程的基本概念

23、一、线程的引入一、线程的引入传统操作系统中使用的是单线程（单线程（single-threaded）方法，即每个 进程中只包含一个线程，因而线程的概念不被认识。例， MS-DOS：每次只允许一个进程运行，该进程中含一个线程。 UNIX：允许多个进程并发运行，每个进程中只有一个线程。多线程多线程指操作系统支持在同一进程中的多个线程的并发运行。Windows NT、Solaris和OS/2等操作系统使用支持多个进程并发 运行，且支持同一进程中多个线程并发运行的方法。许多在现代台式PC机上运行的软件包也是多线程的。例如一个字 处理软件可以有一个线程去显示图形，另一线程去读用户键入的 字符，第三个线程在后台执行拼写和语法检查。2.4 线程的基本概念线程的基本概念二、用户级线程和内核支持线程二、用户级线程和内核支持线程线程目录线程目录进程进程用户空间用户空间P P