1、第二章 进程的描述与控制主要内容前趋图和程序执行前趋图和程序执行进程的描述进程的描述进程控制进程控制线程的基本概念线程的基本概念一、知识点归纳1.前趋图和程序执行前趋图和程序执行1.1 前趋图的定义前趋图的定义 前趋图前趋图(Procedence Graph)使一个有向无循环使一个有向无循环图图DAG(Directed Acyclic Graph)。图中的每个。图中的每个结点可用于表示一条语句、一个程序段或进程；结点可用于表示一条语句、一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序结点间的有向边则表示在两结点之间存在的偏序(partial order)或前趋关系或前趋关系(pro
2、cedence relation)”,=(pi,pj)|pi must complete before pj may start 如果如果(pi,pj),可写成可写成pi pj,称称pi是是pj的前趋，的前趋，而而pj是是pi的直接后继。的直接后继。1.2程序顺序执行一、程序顺序执行 程序在执行时,必须按照某种先后次序逐个执行,仅当前一操作执行后,才能执行后继操作.I1C1P1I2C2P2 程序顺序执行时的前趋图如对于以下三条语句的程序段：P1:a=x+yP2:b=a+1P3:c=b-6 其中的语句其中的语句P2P2必须在必须在a a被赋值后才能执行。被赋值后才能执行。同样同样,P3,P3也只
3、能在也只能在b b被赋值后才能执行被赋值后才能执行 二、程序顺序执行时的特征1.顺序性 处理机的操作，严格按照程序所规定的顺序执行。2.封闭性 程序在运行时，它独占全机资源，因而机内各资源的状态（除初始状态外），只有本程序才能改变它。程序一旦运行，执行结果不受外界因素的影响。3.可再现性 只要程序执行时的环境和初始条件相同，当程序多次重复执行，不论是“走走停停”还是“不停顿”，都获得相同的结果。1.3 程序并发执行 一、程序并发执行 在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作与第二个程序的输入操作并发执行。I1I2I3I4C1C2C4C3P1P2
4、P3P4画出这四条语句的前趋图：画出这四条语句的前趋图：S1：a:=x+2 S2:b:=y+4 S3:c:=a+b S4:d:=c+6二、程序并发执行时的特征二、程序并发执行时的特征 间断性间断性 程序在并发执行时，由于共享资源，或者为完成同一任务而相互合作，致使在并发程序间形成了相互制约的关系。失去封闭性失去封闭性 程序在并发执行时，是多个程序共享系统中的各种资源，所以这些资源的状态可以由多个程序来改变，使其失去了封闭性。不可再现性不可再现性 程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。1.4 程序并发执行的条件程序并发执行的条件 定义符号：R(pi)=a1,a2,.,an，用
5、以表示程序pi在执行期间所需参考的所有变量的集合，称为“读集”；W(pi)=b1,b2,.,bn，是程序pi在执行期间要改变的所有变量的集合，称为“写集”。若两个程序p1和p2能满足下述条件，它们便能并发执行，且具有可再现性。该条件在1966年首先由Bernstein提出，又称为Bernstein条件。R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=例如，四条语句：S1:a=x+y S2:b:=z+1 S3:c:=a-b S4:w:=c+1 写出它们的读集和写集。读集和写集分别为：R(S1)=x,y W(S1)=aR(S2)=z W(S2)=bR(S3)=a,b W(S3)=cR
6、(S4)=c W(S4)=w2.进程的描述进程的描述2.1 进程的定义与特性进程的定义与特性一、进程的定义 “进程”这一术语，在60年代初期，首先在美国MIT的MULTICS系统和IBM公司的CTSS/360系统中引入。其中能反映进程实质的定义有：（1）进程是程序的一次执行。（2）进程是可以和其他计算并发执行的计算。（3）进程是一个程序及其数据在处理机上顺序执行时发生的活动。（4）进程是程序在一个数据集合上的运行过程，是系统进行资源分 配和调度的一个独立单位。（5）进程是进程实体的一次活动。进程是可并发执行的程序在一个数据集合上的运行过程或进程实体的运行过程。二、进程的特征及和程序的区别二、进
7、程的特征及和程序的区别(1)动态性动态性：生命周期。即它由系统“创建”而诞生，因被“调度”而执行，因得不到资源而暂停，最后因被“撤消”而消亡。(2)并发性并发性：是指不同进程的动作在时间上可以重叠，即系统内的多个进程是可以并发执行的。(3)独立性独立性：指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调动的基本单位。(4)异步性异步性：指进程按各自独立的、不可预知的速度向前推进(5)结构特性结构特性：从结构上看，每个进程都由程序段、数据段和一个PCB三部分组成。进程与程序的区别进程与程序的区别(1)从定义上看，进程是程序处理数据的过程，而程序是一组从定义上看，进程是程序处
8、理数据的过程，而程序是一组指令的有序集合；指令的有序集合；(2)进程具有动态性、并发性、独立性和异步性等，而程序不进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性；具有这些特性；(3)从进程结构特性上看，它包含程序（以及数据和从进程结构特性上看，它包含程序（以及数据和PCB）；）；(4)进程和程序并非一一对应。进程和程序并非一一对应。2.2 进程的基本状态一、进程的三种基本状态1.就绪状态就绪状态 当进程已分配到除CPU以外的所有必要的资源后,只要能再获得处理机,便可立即执行.2.执行状态执行状态 在单处理机系统中,只能有一个进程处于执行状态.在多处理机中,则可能多个进程处于执行
9、状态.3.阻塞状态阻塞状态 正在执行的进程，由于等待某事件发生而无法执行时，便放弃处理机而处于暂停状态。二、新状态和终止状态二、新状态和终止状态在不少系统中，又增加了这两种基本状态在不少系统中，又增加了这两种基本状态。引入新状态和终止状态的原因：引入新状态和终止状态的原因：由于OS在建立一个新进程时，通常分为2步：第一步是为新登录的用户程序（分时系统）创建进程，并为他分配资源，此时进程即处于新状态。第二步是把新创建的进程送入就绪队列，一旦进程进入就绪队列，它便由新状态变为就绪状态。一个结束了的进程，其退出系统的过程也分为两步：第一步是将该进程从就绪队列中移出，使之成为一个不可能再运行的进程，相
10、应的进程处于终止状态。此时系统并不立即撤销它，而是将它暂时留在系统中，以便其它进程去收集该进程的有关信息。接纳接纳完成完成新进程新进程就绪就绪执行执行结结束束阻塞阻塞I/O完完成或等成或等待的事待的事件发生件发生I/O请求请求或或等待某事等待某事件件2进程五种基本状态进程五种基本状态 接纳接纳完成完成新进程新进程就绪就绪执行执行结结束束阻塞阻塞I/O完完成或等成或等待的事待的事件发生件发生I/O请求请求或或等待某事等待某事件件中断中断进程调度进程调度三、进程状态的转换1.新 就绪状态2.就绪 执行状态3.执行 就绪状态4.执行 阻塞状态5.执行 终止状态2.3 进程的挂起状态一、挂起状态的引入
11、引入挂起状态可能基于下述需要：1)终端用户的需要2)父进程的需求3)操作系统的需要4)对换的需要5)负荷调节的需要二、进程状态的转换引入挂起状态后，又将增加从挂起状态到非挂起状态的转换，或者相反。可以有以下几种情况：1）活动就绪到静止就绪；2）活动阻塞到静止阻塞；3）静止就绪到活动就绪；4）静止阻塞到活动阻塞2.4 进程控制块PCBl PCBPCB是系统为了描述和控制进程的运行而为进程定义的一种数据结构，是系统为了描述和控制进程的运行而为进程定义的一种数据结构，l 它是进程实体的一部分，它是进程实体的一部分，是进程存在的唯一标志是进程存在的唯一标志，也是操作系统中最重要的也是操作系统中最重要的
12、结构体类型的数据结构。结构体类型的数据结构。l PCBPCB中存放着操作系统所需的用于描述进程的当前情况以及控制进程运行的全中存放着操作系统所需的用于描述进程的当前情况以及控制进程运行的全部信息。部信息。一、PCB的作用PCB的作用，是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。1）标识进程的存在标识进程的存在2）为系统提供可并发执行的独立单位为系统提供可并发执行的独立单位3）为系统控制和管理进程提供所需的一切信息。为系统控制和管理进程提供所需的一切信息。二、进程控制块的信息二、进程控制块的信息1)进程标识符信息进程标识符信息2)处理
13、机状态信息处理机状态信息3)进程调度信息进程调度信息4)进程控制信息进程控制信息三、三、PCB的组织方式的组织方式1）链接方式）链接方式2）索引方式）索引方式3.进程控制3.1操作系统内核 通常将一些与硬件密切相关的模块，例如，中断处理程序、通常将一些与硬件密切相关的模块，例如，中断处理程序、各种常用设备的驱动程序，以及运行频率较高的模块等安各种常用设备的驱动程序，以及运行频率较高的模块等安排在紧靠硬件的软件层中，并将它们常驻内存，以提高操排在紧靠硬件的软件层中，并将它们常驻内存，以提高操作系统运行效率，并对它们加以特殊的保护。上述这一部作系统运行效率，并对它们加以特殊的保护。上述这一部分程序
14、称为操作系统内核。分程序称为操作系统内核。操作系统的内核是计算机硬件扩充的第一层软件，是在核操作系统的内核是计算机硬件扩充的第一层软件，是在核心态运行的操作系统程序。心态运行的操作系统程序。大多数大多数OSOS的内核都包含下述功能：的内核都包含下述功能：1 1）支撑功能：三种最基本的支撑功能：中断处理、时钟管）支撑功能：三种最基本的支撑功能：中断处理、时钟管理和原语操作。理和原语操作。2 2）资源管理功能：进程管理、存储器管理、设备管理）资源管理功能：进程管理、存储器管理、设备管理 原语操作：原语操作：本身是由若干条指令构成、用于完成特定功能的一个本身是由若干条指令构成、用于完成特定功能的一个
15、过程。过程。：一个操作中的所有动作，与一般过程的区别：一个操作中的所有动作，与一般过程的区别：要么全作，要么全不作。要么全作，要么全不作。即：原子操作是不可分割的，它是机器指令的延伸。即：原子操作是不可分割的，它是机器指令的延伸。3.2进程的创建一、进程图进程图是用于描述进程家族关系的有向树。ABCGFEHDIJKLM二、引起进程创建的事件1）用户登陆2）作业调度3）提供服务4）应用请求三、进程的创建 进程创建的主要步骤：进程创建的主要步骤：申请空白申请空白PCB 为新进程分配资源为新进程分配资源 初始化初始化PCB的内容的内容 将新进程插入就绪队列将新进程插入就绪队列3.3进程的终止（撤销）
16、一、引起进程终止的事件1）正常结束2）异常结束3）外界干预二、进程终止的过程 检索进程当前的状态，结束并置调度标志，撤销检索进程当前的状态，结束并置调度标志，撤销其所有的子进程，归还资源，移出队列其所有的子进程，归还资源，移出队列3.4 进程的阻塞和唤醒进程的阻塞和唤醒一、引起进程阻塞和唤醒的事件一、引起进程阻塞和唤醒的事件1）请求系统服务）请求系统服务2）启动某种操作）启动某种操作3）新数据尚未到达）新数据尚未到达4）无新工作可作）无新工作可作二、进程阻塞的过程二、进程阻塞的过程发现堵塞事件，调用阻塞原语把自己阻塞，停止进程的执行，发现堵塞事件，调用阻塞原语把自己阻塞，停止进程的执行，修改修
17、改PCBPCB的的，将其插入到自己的堵塞队列。最后，将其插入到自己的堵塞队列。最后转调度程序，将处理机分配给另一个就绪进程。转调度程序，将处理机分配给另一个就绪进程。三、进程唤醒过程三、进程唤醒过程把被阻塞进程从等待该事件的阻塞队列中移出，将其把被阻塞进程从等待该事件的阻塞队列中移出，将其PCB的现行状态，的现行状态，由阻塞改为就绪，再将该进程插入到由阻塞改为就绪，再将该进程插入到PCB就绪队列中。就绪队列中。3.5进程的挂起和激活一、挂起的过程当出现了引起挂起的事件时，如为了暂时缓和内存的紧张状态，用户进程请求将自己挂起或者当父进程请求将自己的某个子进程挂起时，系统将利用挂起原语suspen
18、d()将制定的进程或处于阻塞状态的进程挂起。二、激活过程将进程从外存调入内存，检查该进程的状态，改为将进程从外存调入内存，检查该进程的状态，改为相应的活动状态相应的活动状态4.线程的基本概念 在操作系统中引入进程的目的是为了使多个程序并发执行，以改善资源利用率和提高系统的吞吐量，引入线程的目的使为了减少并发的系统开销。一、线程的定义定义定义：线程是进程中的一个实体，是被系统独立调度和线程是进程中的一个实体，是被系统独立调度和分派的基本单位，故又称为轻权（轻型）进程分派的基本单位，故又称为轻权（轻型）进程(Light Weight Process)，它由线程控制表、存储线程上下文，它由线程控制表
19、、存储线程上下文的用户栈以及核心栈组成。的用户栈以及核心栈组成。传统的进程称为重型进程传统的进程称为重型进程(Heavy Weight Process)。二、线程与进程的比较 进程都是拥有资源的一个独立单位，它可以拥有自己的资源。而进程都是拥有资源的一个独立单位，它可以拥有自己的资源。而线程几乎不拥有系统资源线程几乎不拥有系统资源,但它可以访问其隶属进程的资源但它可以访问其隶属进程的资源 以进程为单位进行处理机切换和调度时，处理机切换时间长，资以进程为单位进行处理机切换和调度时，处理机切换时间长，资源利用率降低。以线程为单位进行进行处理机切换和调度时，由于不源利用率降低。以线程为单位进行进行处
20、理机切换和调度时，由于不发生资源变化，特别是地址空间的变化，处理机切换时间较短，从而发生资源变化，特别是地址空间的变化，处理机切换时间较短，从而处理机效率较高。处理机效率较高。在引入线程的操作系统，不仅进程之间可以并发执行，而且线程之间也在引入线程的操作系统，不仅进程之间可以并发执行，而且线程之间也可并发执行，因而使操作系统具有更好的并发性，从而能更有效地利用系统可并发执行，因而使操作系统具有更好的并发性，从而能更有效地利用系统资源，提高系统的吞吐量。资源，提高系统的吞吐量。由于在创建或撤消进程时，系统要为之分配或回收资源，如内存空间、由于在创建或撤消进程时，系统要为之分配或回收资源，如内存空
21、间、I/OI/O设备等，所以操作系统创建进程的开销远大于创建线程的开销。类似地，设备等，所以操作系统创建进程的开销远大于创建线程的开销。类似地，操作系统为进程切换付出的开销也远大于为同一进程内的线程切换付出的开操作系统为进程切换付出的开销也远大于为同一进程内的线程切换付出的开销。另外，由于同一进程内的多个线程具有相同的地址空间，致使它们之间销。另外，由于同一进程内的多个线程具有相同的地址空间，致使它们之间的同步与互斥的实现，也变得比较容易。的同步与互斥的实现，也变得比较容易。线程和进程一样，都有自己的状态，也有相应的同步线程和进程一样，都有自己的状态，也有相应的同步机制，不过由于线程没有单独的数据和程序空间，因此机制，不过由于线程没有单独的数据和程序空间，因此线程不能像进程的数据与程序那样，交换到外存存储空线程不能像进程的数据与程序那样，交换到外存存储空间，从而间，从而线程没有挂起状态线程没有挂起状态。进程的调度、同步等大多由进程的调度、同步等大多由OS内核完成，而线程的内核完成，而线程的控制既可以由控制既可以由OS内核进行，也可以由用户控制。内核进行，也可以由用户控制。二、重点、难点1.进程的相关概念2.线程的基本概念三、典型例题分析 在一个单处理机系统中，若有个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有（）个。
