《计算机操作系统(汤小丹)第2章课件》由会员分享，可在线阅读，更多相关《计算机操作系统(汤小丹)第2章课件（141页珍藏版）》请在金锄头文库上搜索。
1、,第二章 进程的描述与控制,2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题 2.6 进程通信 2.7 线程(Threads)的基本概念 2.8 线程的实现 习题,2.1 前趋图和程序执行在早期未配置OS的系统和单道批处理系统中，程序的执行方式是顺序执行，即在内存中仅装入一道用户程序，由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个程序并执行。可见，这种方式浪费资源、系统运行效率低等缺点。,2.1.1 前趋图为了能更好地描述程序的顺序和并发执行情况，我们先介绍用于描述程序执行先后顺序的前趋图。所谓前趋图(Pre
2、cedence Graph)，是指一个有向无循环图，可记为DAG(Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃至一条语句，结点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)。,进程(或程序)之间的前趋关系可用“”来表示，如果进程Pi和Pj存在着前趋关系，可表示为(Pi，Pj)，也可写成PiPj，表示在Pj开始执行之前Pi 必须完成。此时称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial
3、 Node)，把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。,在图2-1(a)所示的前趋图中，存在着如下前趋关系：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, P8), (P6, P8), (P7, P
4、9), (P8, P9),应当注意，前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。如图2-1(b)所示的前趋关系中就存在着循环。它一方面要求在S3开始执行之前，S2必须完成，另一方面又要求在S2开始执行之前，S3必须完成。显然，这种关系是不可能实现的。S2S3，S3S2,图2-1 前趋图,2.1.2 程序顺序执行1. 程序的顺序执行通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。例如，在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据
5、进行计算；最后才是运行打印程序，打印计算结果。我们用结点(Node)代表各程序段的操作(在图2-1中用圆圈表示)，其中I代表输入操作，C代表计算操作，P为打印操作，用箭头指示操作的先后次序。,这样，上述的三个程序段间就存在着这样的前趋关系：IiCiPi，其执行的顺序可用前趋图2-2(a)描述。即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含了三条语句的程序段：S1: a :=x+y；S2: b :=a-5；S3: c :=b+1；其中，语句S2必须在语句S1后(即a被赋值)才能执行，语句S3也只能在b被赋值后才能执行，因此，三条语句存在着这样的前趋关系：S1S2S3，应按前趋图2
6、-2(b)所示的顺序执行。,图2-2程序顺序执行的前趋图,2. 程序顺序执行时的特征由上所述可以得知，在程序顺序执行时，具有这样三个特征： 顺序性：指处理机严格地按照程序所规定的顺序执行，即每一操作必须在下一个操作开始之前结束； 封闭性：指程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响； 可再现性：指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果。程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。,
7、2.1.3程序并发执行1. 程序的并发执行我们通过一个常见的例子来说明程序的顺序执行和并发执行。在图2-2中的输入程序、计算程序和打印程序三者之间，存在着IiCiPi这样的前趋关系，以至对一个作业的输入、计算和打印三个程序段必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行情况如图2-3所示。,图2-3 程序并发执行时的前趋图,由图2-3可以看出，存在前趋关系IiCi，IiIi+1，CiPi，CiCi+1，PiPi+1，而Ii+1和Ci及Pi-1是重叠的，即在Pi-1和Ci以及Ii+1之间，不存在前趋关系，可以并发执行。对于具有下述四条语句的程序段：S1: a :
8、=x+2S2: b :=y+4S3: c :=a+bS4: d :=c+b可画出图2-4所示的前趋关系。可以看出：S3必须在a和b被赋值后方能执行；S4必须在S3之后执行；但S1和S2则可以并发执行，因为它们彼此互不依赖。,图2-4 四条语句的前趋关系,2. 程序并发执行时的特征在引入了程序间的并发执行功能后，虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，以及它们为完成同一项任务而相互合作，致使在这些并发执行的程序之间必将形成相互制约的关系，由此会给程序并发执行带来新的特征。(1) 间断性。(2) 失去封闭性。(3) 不可再现性。,2.2 进程的描述2.2.1 进程的定义和特征1
9、. 进程的定义 在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性，以及其运行结果不可再现性的特征。由此，决定了通常的程序是不能参与并发执行的，否则，程序的运行也就失去了意义。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。,对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有：(1) 进程是程序的一次执行。(2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3) 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,2. 进程的特征进程和程序是两个截然不同的
10、概念，除了进程具有程序所没有的PCB结构外，还具有下面一些特征：(1) 动态性。(2) 并发性。(3) 独立性。(4) 异步性。,2.2.2 进程的基本状态及转换1. 进程的三种基本状态由于多个进程在并发执行时共享系统资源，致使它们在运行过程中呈现间断性的运行规律，所以进程在其生命周期内可能具有多种状态。一般而言，每一个进程至少应处于以下三种基本状态之一：(1) 就绪(Ready)状态。(2) 执行(Running)状态。(3) 阻塞(Block)状态。,2. 三种基本状态的转换进程在运行过程中会经常发生状态的转换。例如，处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，相应地，其状
11、态就由就绪态转变为执行态；正在执行的进程(当前进程)如果因分配给它的时间片已完而被剥夺处理机暂停执行时，其状态便由执行转为就绪；如果因发生某事件，致使当前进程的执行受阻(例如进程访问某临界资源，而该资源正被其它进程访问时)，使之无法继续执行，则该进程状态将由执行转变为阻塞。图2-5示出了进程的三种基本状态，以及各状态之间的转换关系。,图2-5 进程的三种基本状态及其转换,3. 创建状态和终止状态1) 创建状态如前所述，进程是由创建而产生。创建一个进程是个很复杂的过程，一般要通过多个步骤才能完成：如首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息；然后为该进程分配运行时所必
12、须的资源；最后，把该进程转入就绪状态并插入就绪队列之中。但如果进程所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态。,2) 终止状态进程的终止也要通过两个步骤：首先，是等待操作系统进行善后处理，最后将其PCB清零，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对其信
13、息的提取之后，操作系统将删除该进程，即将其PCB清零，并将该空白PCB返还系统。图2-6示出了增加了创建状态和终止状态后进程的五种状态及转换关系图。,图2-6 进程的五种基本状态及转换,2.2.3 挂起操作和进程状态的转换1. 挂起操作的引入引入挂起操作的原因，是基于系统和用户的如下需要：(1) 终端用户的需要。(2) 父进程请求。(3) 负荷调节的需要。(4) 操作系统的需要。,2. 引入挂起原语操作后三个进程状态的转换在引入挂起原语Suspend和激活原语Active后，在它们的作用下，进程将可能发生以下几种状态的转换：(1) 活动就绪静止就绪。(2) 活动阻塞静止阻塞。(3) 静止就绪活
14、动就绪。(4) 静止阻塞活动阻塞。,3. 引入挂起操作后五个进程状态的转换如图2-8示出了增加了创建状态和终止状态后具有挂起状态的进程状态及转换图。如图2-8所示，引进创建和终止状态后，在进程状态转换时，与图2-7所示的进程五状态转换相比较，要增加考虑下面的几种情况：(1) NULL创建：(2) 创建活动就绪：(3) 创建静止就绪：(4) 执行终止：,图2-7具有挂起状态的进程状态图,图2-8 具有创建、终止和挂起状态的进程状态图,2.2.4 进程管理中的数据结构1. 操作系统中用于管理控制的数据结构 在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们称之为资源信
15、息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针，可以将同类资源或进程的信息表，或者同一进程所占用的资源信息表分类链接成不同的队列，便于操作系统进行查找。,如图2-9所示，OS管理的这些数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。,图2-9 操作系统控制表的一般结构,2. 进程控制块PCB的作用(1) 作为独立运行基本单位的标志。(2) 能实现间断性运行方式。 (3) 提供进程管理所需要的信息。(4) 提供进程调度所需要的信息。(5) 实现与其它进程的同步与通信。,3. 进程控制块中的信息在
16、进程控制块中，主要包括下述四个方面的信息。1) 进程标识符进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符：(1) 外部标识符。(2) 内部标识符。,2) 处理机状态处理机状态信息也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成的。,3) 进程调度信息在OS进行调度时，必须了解进程的状态及有关进程调度的信息，这些信息包括： 进程状态，指明进程的当前状态，它是作为进程调度和对换时的依据； 进程优先级，是用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机； 进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等； 事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,4) 进程控制信息是指用于进程控制所必须的信息，它包括： 程序和数据的地址，进程实体中的程序和数据的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据； 进程同步和通信机制，这是实现进程同步和进程通信时必需的
