进程描述与控制1.ppt

第二章 进程描述与控制,认识进程 前趋图和程序设计 进程 进程间的相互作用 进程间的通信 进程调度（CPU调度） 线程,认识进程（Unix/Linux中的进程）,进程标识符PID （Process IDentifier）：系统中每个进程的一个编号 两个基本的系统调用：fork()和getpid() Fork()返回值：返回值0表示子进程，否则把子进程的标识符返回给父进程 Getpid：获得进程标识符,认识进程（简单程序）,include #include Main() printf(“PID before fork():%dn”,(int)getpid); if(fork() printf(“Parent PID :%dn”,(int)getpid) else printf(“Child PID :%dn”,(int)getpid),认识进程（输出结果）,一种可能的输出结果： $ forktest PID before fork():490 Parnet PID:490 Child PID:491,2.1 前趋图和程序设计,前趋图的定义 程序顺序执行 并发程序执行 多道程序设计,2.1.1 前趋图的定义,前趋图(procedence graph)是一个有向无环图DAG (directed acyclic graph)。图中的每一个顶点可表示一条语句、一个程序段或进程, 弧则表示两顶点之间的偏序(partial order)或前趋关系(procedence relation)。无前趋的顶点为初始顶点,无后继的顶点称为终止顶点, 每个顶点还有一个权值, 它表示顶点执行所需的时间。如,它的每一种拓扑排序都是顺序执行时正确得到结果的顺序,有路经的两顶点必须按前趋关系顺序执行,无路经的两顶点则可以并发执行,2.1.2 程序顺序执行,程序顺序执行： 程序执行时, 必须按某种先后次序, 只有当前操作完成后才能执行后继操作, 它体现了某种算法。如： S1: a:=x+y; S2: b:=a-5; S3: c:=b+1; 各程序段与此相同, 以 I C P分别代表输入计算和输出, 则前趋图：,前趋图,S1,S2,S3,I1,C1,P1,I2,C2,P2,程序顺序执行的特征： 程序执行的顺序性:严格按所规定的顺序执行 程序执行的封闭性 独占资源,执行过程和结果不受其它程序的影响 程序结果的可再现性(结果的确定性) 只要初始状态相同,程序多次重复运行,其结果与程序执行速度无关(连续或间断),结果都应相同。,2.1.3 程序并发执行,多个程序并发执行： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。宏观上同时处于运行状态微观上各程序交替地间断运行。,前趋关系: IiCi , PiPi+1 CiPi , IiIi+1 CiCi+1,Ii+1, Ci, Pi-1 是重叠的,举例说明: 假如系统中有两道程序AA和BB： program AA; program BB; begin begin AN BN N:=N+1; AA+1 N:=N+1; BB+1 NA NB End; end; int N=1; 是AA和BB都能访问的外部公共变量,这两个程序在并发执行, N:=N+1;可分解为3条机器指令,它们的执行顺序不同有可能导致N的值结果不同。,时间 T0 T1 T2 T3 T4 T5,程序,A,AN,AA+1,NA,程序,B,BN,BB+1,NB,N的值 1 1 2 2 2 3,(a) 顺序 执行,时间 T0 T1 T2 T3 T4 T5,程序,A,程序,B,N的值 1 1 1 1 2 2,(b) 交叉 执行,时间 T0 T1 T2 T3 T4 T5,程序,A,程序,B,N的值 1 1 1 1 2 2,(c) 交叉 执行,NB,BB+1,BN,AN,AA+1,NA,AN,NA,AA+1,NB,BB+1,BN,并发执行特征： （1）在并发环境下程序的执行是间断性的 执行停执行 （2）失去封闭性 资源共享,执行过程和结果受其它程序的影响（3）程序结果的不可再现性 并发程序执行的结果不可再现, 与其执行的相对速度有关，是不确定的 （4）相互作用和制约性 进程之间可相互作用（相互制约） 可分为直接作用和间接作用,(5) 程序与CPU执行的活动之间不再一一对应 程序与CPU执行的活动, 这是两个不同的概念; 程序是完成某一特定功能的指令序列, 是静态的概念; 而CPU执行的活动是一个动态概念, 它是程序的执行过程。程序在顺序执行(即单道运行)时,程序与CPU执行的活动是一一对应的,而在程序并行执行(即多道程序)时, 这种关系不再存在。,2.2 进程,进程的概念 进程的状态及其转换 进程控制块（Process Control Block） 进程的特征,2.2.1 进程的概念,进程是程序的一次执行 进程是可以和别的计算并发执行的计算 进程是一个数据结构及能在其上进行操作的程序 进程是某程序及其数据在处理机上顺序执行的过程 进程是程序在某一数据集合上的运行过程 进程的定义：Process 进程是可以并发执行的程序在某个数据集合上的运 行过程，是系统进行资源分配和调度的独立单位,2.2.1 进程的概念,动态性 进程是程序的执行过程, 它由创建而产生, 由调度而执行,因某事件而暂停, 由撤销而消亡。在生命周期内, 进程在三种基本状态之间动态转换 并发性 多个进程同时存于内存中,一起向前推进,并发执行 独立性 进程是独立获得资源和独立调度的基本单位 异步性 各进程都各自独立的不可预知的速度向前推进 结构性： 由程序+数据+进程控制块组成, 称之为进程映像,进程的特征,程序与进程之间的区别： 进程更能真实地描述并发，而程序不能 进程是由程序、数据和进程控制块三部分组成的 程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有,进程的基本状态及其转换,进程的三种基本状态： 运行态(Running): 进程占有CPU，并在CPU上运行。 就绪态(Ready): 进程已经具备运行条件, 但由于CPU忙而暂时不能运行的状态(当调度给其CPU时, 立即可以运行)。 阻塞态(Blocked): 等待态、封锁态、冻结态 进程因等待某种事件的发生而暂时不能运行的状态。(即使CPU空闲, 该进程也不可运行)。 进程在生命期内处于且仅处于三种基本状态之一 不同系统设置的进程状态数目不同。,运行,就绪,阻塞,进程的状态及其转换,状态转换,就绪 运行 调度程序选择一个新的进程运行 运行 就绪 运行进程用完了时间片, 运行进程被中断, 在抢占调度方式中, 因为一高优先级进程进入就绪状态 运行 阻塞 当一进程发生I/O请求或等待某事件时 阻塞 就绪 当I/O完成或所等待的事件发生时,2.2.3 进程控制块,1. 进程控制块的作用： 系统为管理进程设置一个专门的数据结构进程控制块(Process Control Block), 用它来记录进程的外部特征，描述进程的运动变化过程 (从结构的观点上看, 程序与进程的区别就在于有没有PCB)。 进程与PCB一一对应, 在进程的整个生命期内, PCB随进程的创建而产生随进程的终止而消失, 系统利用PCB来控制和管理进程, 系统根据PCB感知进程的存在, 所以PCB是进程存在的唯一标志。存放控制进程所需的数据(进程属性)。,2. PCB中的信息： 进程标识信息 处理器状态信息(现场信息) 进程调度信息 进程控制信息 记录了进程的全貌，作为进程调度和进程控制的依据和操作对象。,1) 进程标识符 (在PCB中),进程标识符用于唯一地标识一个进程 外部标识符 由创建者提供，由字符、数字组成 内部标识符 为了方便系统而设置，OS中，每个进程有唯一的标识符（PID）,2) 处理器状态信息(现场信息),进程走走停停必须保存处理器的状态信息即处理器现状, 它由处理器寄存器内容组成。 通用寄存器(8 32个, RISC结构中超过100个) 指令计数器(下一条指令的地址) 状态寄存器(程序状态字 PSW,如:EFLAGS寄存器) 用户栈指针(过程和系统调用参数及地址),3) 进程调度信息,调度信息 进程状态 (如: 运行，就绪，阻塞.) 进程优先级 该进程在等待的事件 (阻塞原因) 调度所需其它信息 (如: 等待总时间, 执行总时间),4) 进程控制信息,程序和数据的地址 程序和数据所在的内存(段/页表指针)或外存地址 进程间同步和通信机制 需要的消息队列指针和信号量等 所需的和已分配到的资源清单及使用情况 除CPU外的资源: 文件，I/O设备. 它们的时间使用史 数据结构信息 进程可能需要有指向其他PCB的指针, 父-子进程关系及其它结构,3. 进程控制块的组织方式 PCB表: 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度 （注: 多道程序中的道数与系统并发度不同） PCB表组织方式有两种： 链接方式、索引方式,1) 链接方式： 对具有相同状态的进程，分别各自链接起来组成进程PCB链队列： 运行队列、就绪队列、阻塞队列、空闲队列,2) 索引方式： 对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址,空闲指针,运行指针,就绪指针,等待1指针,等待2指针,进程队列,就绪队列无优先级,2.3 进程控制,处理机的执行状态分为两种 系统态(核心态、管态)： 有特权, 能执行所有指令, 能访问所有寄存器和存储区。 用户态(目态)： 无特权, 只能执行规定指令,只能访 问指定的寄存器和存储区。 用户程序运行在用户态，它不能执行OS指令不能访问OS区域，防止对OS的破坏。 OS内核运行在系统态。进程控制包含在OS的内核中，它常驻内存，执行效率高。,进程控制用原语操作实现。 原语操作是不可分割的操作，创建、撤消进程及完成进程各状态之间的转换。由以下原语完成： 进程创建原语 进程撤消原语 阻塞原语、唤醒原语 挂起原语、激活(解挂)原语,1.进程图 进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源。,2.3.1 进程的创建,2.进程何时创建? 引起创建进程的事件： 用户登录、作业调度、提供服务、应用请求 用户登录时, 由OS为合法终端创建一个进程 调度到某个批处理作业时,由作业调度程序创建 运行程序请求提供服务(如:打印文件),由OS创建 运行中进程因自己的需要,由它自己创建子进程 如：某应用程序为了加速程序的执行，创建键盘输入进程、通信进程、计算进程、显示进程等,3.进程的创建过程 一旦发现了要求创建新进程的事件,OS便调用创建原语, 按以下过程创建新进程。,分配一个唯一的进程标识符,索取一个空白PCB 为新进程的程序和数据分配内存空间 初始化进程控制块 初始化标识符信息(填入)、处理机的状态信息(指令指针, 栈指针)和控制信息(状态,优先级.) 设置相应的链接 如: 把新进程加到就绪队列的链表中,1. 进程何时终止? 正常结束 批处理系统中,进程已运行完成遇到 Halt 指令 分时系统中, 用户退出登录 异常结束 本进程发生出错和故障事件 存储区越界、保护性错(如:写只读文件)、特权 指令错、非法指令(如:程序错转到数据区)、算 术运算错、运行超时、等待超过时、I/O 失败、 外界干预 操作系统干预、父进程请求、父进程终止,2.3.2 进程的终止(撤消),2. 进程的终止过程 一旦发生终止进程的事件,OS便调用撤消原语,按以下过程终止该进程。 从PCB中读取进程的状态 若进程处于执行态, 应立即终止该进程的执行,并置调度标志为真(以便该进程终止后系统重新进行调度,将处理机分配给新选择的进程) 若有子孙进程则将它们全部终止,以防它们失控 将该进程所占有的全部资源还给父进程或系统 将该进程的PCB从所在队列中移出,2.3.3 进程的阻塞、唤醒、挂起与激活,1.进程的阻塞,运行状态的进程, 在运行过程中期待某事件发生, 如: 请求系统服务、等待键盘输入、等待其它进程发送的数据、某系统进程完成任务等待新任务; 当期待请求发生时, 由进程调用阻塞原语(block), 将自己阻塞。 阻塞原语使处于运行态的进程停止运行, 将运行现场保存在其 PCB 的CPU 现场保护区, 然后将 PCB中的现行状态由运行态变为阻塞态, 并并将该进程插入到相应事件的阻塞队列中。最后,转进程调度程序重新调度, 将处理机分配给一个就绪进程, 按新进程 PCB 中的处理机状态设置CPU环境, 使它投入运行。,2. 进程的唤醒 当被阻塞进程期待的事件到来时, 由中断处理进程或其它产生该事件的进程调用唤醒原语(wakeup), 将期待该事件队列中的进程唤醒。 唤醒原语执行时, 将被阻塞进程从相应等队列中移出, 并将其 PCB中的现行状态由阻塞改为就绪态, 然后将该进程插入就绪队列中。 若事件是等待 I/O 完成, 则由硬件提出中断请求, CPU响应中断, 暂停当前进程的执行, 转去中断处理。检查有无等待该 I/O完成的进程。若有, 则将它唤醒。然后结束中断处理。返回被中断进程或重新调度。 若事件是等待某进程发一个信息, 则由发送进程把该等待进程唤醒。,3. 进程的挂起 当进程请求将自己挂起或父进程请求将子进程挂起时, 调用挂起原语(suspend), 将指定进程挂起。 执行过程: 检查要挂起进程的状态, 若处于活动就绪态就将其改为静止就绪态, 对于活动阻塞态的进程则将其改为静止阻塞态。如果被挂起的进程正在执行则还要转到调度程序重新调度。 4. 进程的激活 要激活指定进程时,调用激活原语(active)将它激活 执行过程: 将要激活的进程调入内存, 并检查它的状态, 若是静止就绪态则将其改为活动就绪态,若为静止阻塞态就将其改为活动阻塞态。如果采用的是抢占调度策略,被激活的进程优先级高则引起重新调度。,1.并发执行新特征： 间断性、失去封闭性和可再现性、相互制约性 2. 进程的基本特征: