第3章进程管理(1)

1第三章进程管理2主要内容3.1进程的基本概念3.2进程的描述3.3进程的基本状态3.4进程控制3.5实例研究:UNIXSVR4的进程管理3.6进程同步3.7死锁3.8线程33.1进程的基本概念3.1.1程序的并发执行一、前驱图（ProcedenceGraph）是一个有向无循环图。用来描述程序各部分间的依赖关系或一个大的计算各子部分间的因果关系。•前趋图中的元素：结点：表示一个语句、程序段、进程有向边：表示结点间的偏序关系（前驱关系）→={(Pi,Pj)|PimustcompletebeforePjmaystart}若(Pi,Pj)∈→，可写成Pi→Pj，称Pi是Pj的直接前驱，而Pj是Pi的直接后继。4存在下面的前驱关系：P1→P2,P1→P3，P1→P4,P2→P5，P3→P5,P4→P6，P5→P7,P6→P7或表示为：P＝{P1,P2,P3,P4,P5,P6,P7}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,p5),(P4,P6),(P5,P7),(P6,P7)}23167455注意：前驱图中不存在循环。S2S3，S3S2显然这种前驱关系是不可能满足的，S3的执行要依赖于S2的执行结果，S2的执行结果又要依赖于S3的执行结果，这种程序是不可能执行下去的。6例：下述四条语句的程序段画出前驱图S1：a：＝x+2S2：b：＝y＋4S3：c：＝a＋bS4：d：＝c＋6S1S2S4S37一个较大的程序通常都是由若干个程序段组成。在程序执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。例如：在进行计算时，总是先输入用户的程序和数据，然后才能计算，计算完成后再将结果打印出来。二、程序的顺序执行8I1C1P1P2I2C1程序顺序执行时的前驱图对于一个程序段中的多条语句来说，也有一个执行顺序的问题。如果对于下述三条语句的程序段：S1：a：＝x＋yS2：b：＝a－5S3：C：＝b＋1(其中S2必须在a被赋值以后才能执行；同样S3也只能在b被赋值以后才能执行)9程序顺序执行时的特征（1）顺序性处理机的操作，严格按照程序所规定的顺序执行，即只有前一操作结束后，才能执行后继操作。（2）封闭性（失去交换性）程序是在封闭的环境下运行的。即程序在运行时，它独占全机资源，因而机内各资源的状态（除初始状态外），只有程序才能改变它。程序一旦开始运行，其执行结果不受外界因素的影响。（3）可再现性只要程序执行时的环境和初始条件都相同，不论它是从头到尾的不停顿的执行，还是“走走停停”地执行，都将获得相同的结果。10三、多道程序系统中，程序执行环境的变化计算机能够同时处理多个具有独立功能的程序（批处理系统，分时系统、实时系统、网络与分布式系统）。这样的执行环境具有三个特点：独立性随机性资源共享硬件资源：CPU、输入输出设备，存储器软件资源：各种例行程序、各种共享的数据多道程序环境下执行程序的道数计算机系统中CPU的个数单CPU中，则有N－1道程序处在等待CPU的状态输入输出设备有限将导致这些设备被共享、内存有限将导致内存被共享11四、程序的并发执行I1I2I4I3C1C2C3P1C4P4P3P2程序并发执行时的前驱图12在上图中存在下属的前驱关系：IiCi，IiIi＋1，CiPi，CiCi＋1，PiPi＋1Ii＋1和Ci及Pi－1是可以并发执行的。13程序并发执行：一组逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行，尚未结束，另一个程序段的执行已经开始的这种执行方式。即时间段的并行。14程序并发执行时的特征间断性–程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。(I、C、P是三个相互合作的程序，当计算程序完成Ci－1的计算后，如果输入程序I尚未完成对Ii的处理，则计算程序无法进行Ci处理，致使计算程序暂停运行。)失去封闭性–程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。15不可再现性–程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。例如：有两个循环程序A和B，共享一个变量N。程序A:N：＝N＋1；程序B:print（N）；N=0；（假定某时刻变量N的值为n）（1）N：＝N＋1在print（N）和N：＝0之前，此时得到的N值分别为n＋1，n＋1，0（2）N：＝N＋1在print（N）和N：＝0之后，此时得到的N值分别为n，0，1（3）N：＝N＋1在print（N）和N：＝0之间，此时得到的N值分别为n，n＋1，016程序并发执行的条件1966年，Bernstein提出了相邻语句S1，S2可以并发执行的条件。如果并发执行的各程序段中语句或指令满足Bernstein的三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生影响。17将程序中任一语句Si划分为两个变量的集合R（Si）和W（Si）其中R（Si）＝{a1,a2,……am}是语句Si在执行其间必须对其进行读写的变量W（Si）＝{b1，b2，……bn}是语句Si在执行其间必须对其进行修改，访问的变量如果对于语句S1和S2，有①R(S1)∩W(S2)＝{Φ}②W(S1)∩R(S2)＝{Φ}③W(S1)∩W(S2)={Φ}同时成立即：R(S1)∩W(S2)∪W(S1)∩R(S2)∪W(S1)∩W(S2)＝{Φ}则语句S1和S2是可以并发执行的。18例：若有两条语句C＝a－b和W＝c＋1，判断它们是否可以并发执行？解：它们的“读集”和“写集”分别为R（C：＝a－b）＝{a，b}；R（W：＝c＋1）＝{c}W（C：＝a－b）＝{c}；W（W：＝c＋1）＝{w}R（C：＝a－b）∩W（W：＝c＋1）={Φ}R（W：＝c＋1）∩W（C：＝a－b）={c}所以：两条语句不能并发执行。19程序的顺序执行、程序的并发执行特征比较程序的顺序执行程序的并发执行1顺序性1间断性2封闭性2失去封闭性3可再现性3不可再现性203.1.2进程的引入多道程序系统的特点是并行性。为了充分利用系统资源，在主存中同时存放多道作业运行，所以各作业之间是并行的各程序由于同时存在于主存中，它们之间必定会存在相互依赖，相互制约的关系。（间接制约关系、直接制约关系）在多道程序系统所带来的复杂环境中，程序具有了并行、制约、动态的特性，原来的程序概念，难以刻画系统中的情况了。–程序本身完全是静态的概念–程序概念也反映不了系统中的并行特性21进程的定义进程有许多各式各样的定义（1）进程是可以并发执行的计算部分（2）进程是一个独立的可以调度的活动（3）进程是一个抽象的实体，当它执行某个任务时，将要分配和释放各种资源（4）行为的规则叫程序，程序在处理机上执行的活动称为进程。（5）一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程。进程：一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。（在这里，程序指一组操作序列，而数据集则是接受程序规定操作的一组存储单元的内容。）22比较进程和程序的区别：1进程是一个动态的概念，进程的实质是程序的一次执行过程，动态性是进程的基本特征，同时进程是有一定的生命期的；而程序只是一组有序指令的集合，本身并无运动的含义，是静态的。2并发性，并发性是进程的重要特征，引入进程的目的正是为了使其程序和其它程序并发执行；而程序(没有建立进程)是不能并发执行的。3独立性，是指进程一个能独立运行、独立分配资源和独立调度的基本单位；凡未建立进程的程序，都不能作为一个独立的单位参加运行。４不同的进程可以包含同一个程序，同一个程序在执行中也可以产生多个进程。23作业和进程的关系（区别）1作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行；而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。2一个作业可由多个进程组成，且必须至少由一个进程组成。3作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的多道系统中。243.2进程的描述3.2.1进程的特征1．动态性动态性是进程最基本的特征。2.并发性指多个进程实体，同时存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也是为了使该进程的程序能和其它进程的程序并发执行。253.独立性进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。没有建立进程的程序，不能作为一个独立的单位参加运行。4.异步性进程按各自独立的、不可预之的速度向前推进5.结构特性从结构上看，进程是由程序段、数据段及进程控制块三部分组成。263.2.2进程的结构特征进程的静态描述：由三部分组成PCB、有关程序段和该程序段对其进行操作的数据结构集。各部分的作用：1进程控制块：用于描述进程情况及控制进程运行所需的全部信息。2程序段：是进程中能被进程调度程序在CPU上执行的程序代码段。3数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行后产生的中间或最终数据。27进程控制块中的信息进程控制块中主要包括四个方面用于描述和控制进程运行的信息。1.进程标识符信息进程标识符用于唯一的标识一个进程。外部标识符。由创建者提供，通常是由字母、数字组成，往往是用户（进程）访问该进程使用。如：计算进程、打印进程、发送进程、接收进程等。内部标识符：为了方便系统使用而设置的。在所有的OS中，都为每一个进程赋予一个唯一的整数，作为内部标识符。通常就是一个进程的符号，为了描述进程的家族关系，还应该设置父进程标识符以及子进程标识符。还可以设置用户标识符，来指示该进程由哪个用户拥有。282、处理机状态信息处理机状态信息主要是由处理机各种寄存器中的内容所组成。通用寄存器。又称为用户可视寄存器，可被用户程序访问，用于暂存信息。指令寄存器。存放要访问的下一条指令。程序状态字PSW。其中含有状态信息。（条件码、执行方式、中断屏蔽标志等）用户栈指针。每个用户进程有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。293.进程调度信息在PCB中还存放了一些与进程调度和进程兑换有关的信息。（1）进程状态。指明进程当前的状态，作为进程调度和对换时的依据。（2）进程优先级。用于描述进程使用处理机的优先级别的一个整数，优先级高的进程优先获得处理机。（3）进程调度所需要的其他信息。（进程已等待CPU的时间总和、进程已执行的时间总和）（4）事件。这是进程由执行状态转变为阻塞状态所等待发生的事件。（阻塞原因）30PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度31PCB的组织方式常用的组织方式有两种：链接方式、索引方式。1、链接方式：具有相同状态的PCB，用其中的链接字，链接成一个队列。这样就可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按照进程优先权的大小排列，把优先权高的进程的PCB排在队列前面。32执行指针就绪队列指针阻塞队列指针空闲队列指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879011……332、索引方式：系统根据所有进程的状态，建立几张索引表。例如：就绪索引表、阻塞索引表。把各索引表在内存的首地址记录在内存中的一些专用单元中。每个索引表的表目中，记录具有相同状态的某个PCB在PCB表中的地址。34执行指针就绪表指针阻塞表指针就绪索引表阻塞索引表PCB3PCB4PCB5PCB7PCB6PCB2PCB1按索引方式组织PCB353.2.3进程上下文进程上下文：是进程执行活动全过程的静态描述。包括计算机系统中与执行该进程有关的各种寄存器的值、程序段在经过编译之后形成