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