57第2章进程管理

第二章进程管理2.1进程的基本概念2.2进程的控制2.3进程互斥与同步2.4经典进程同步问题2.5管程机制2.6进程通信2.7线程2.1进程的基本概念程序的顺序执行及特征前趋图与前趋关系程序的并发执行及特征进程的特征与状态进程控制块1、程序顺序执行的特征(1)程序的顺序执行语句1语句2语句3语句4语句5I1C1P1I2C2P2程序1程序2(2)特征①顺序性②封闭性③可再现性2、前趋图与前趋关系(1)前趋图(PrecedenceGraph)一个有向无循环图描述程序或程序段之间执行的前后关系(2)前趋关系“”P1P2P3P8P6P5P7P4P93、程序的并发执行I1C1P1I2C2P2I3C3P3I4C4P4输入计算打印对于下述四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4并发执行时的特征①间断性——“停停走走”②失去封闭性——原因：多个程序共享资源③不可再现性程序A{n=n+1;}程序B{print(n);n=0;}主程序{n=0;parbeginA;B;parend;}共享变量n，会产生3种执行结果：打印n值最后的n值100100并发执行的条件：达到封闭性和可再现性程序P(i)针对共享变量的读集和写集R(i)和W(i)条件：任意两个程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;并发执行失去封闭性的原因是共享资源的影响，因而需要去掉这种影响。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。）前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。现在的问题是这个条件不好检查。进程的定义它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收；引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了OS的复杂性。进程定义：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。进程是并发程序的一次执行过程。是系统进行资源分配和调度的独立单位。进程是可以和别的计算并发执行的计算。进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。4、进程的特征与状态动态性：“它由创建而产生，由调度而执行，由撤销而消亡”。进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块PCB的生成和删除）独立性：进程是一个能独立运行、独立分配资源和独立调度的基本单位。各进程的地址空间相互独立。并发性：引入进程的目的正是为了使其程序能和其他进程的程序并发执行；异步性：进程按各自独立的、不可预知的速度向前推进结构性：进程由程序段、数据段及PCB三部分组成，称为“进程映像”PCB程序段数据段进程结构进程控制块动态特征的集中反映描述要完成的功能操作对象及工作区进程的基本状态及其转换(1)就绪状态（Ready）得到了除CPU以外的所有必要资源。就绪队列(2)执行状态（Running）已获得CPU，程序正在被执行。(3)阻塞状态（Blocked）(等待状态，睡眠状态)因等待某事件发生而暂时无法继续执行，从而放弃处理机，使程序执行处于暂停状态。阻塞队列引起阻塞的事件：请求I/O，申请缓存进程3种基本状态转换（3-4）就绪阻塞执行进程调度I/O请求I/O完成时间片完成进程的挂起状态（静止状态）引入父进程考查和修改、协调子进程间的活动操作系统协调资源使用或进行记账终端用户的请求，希望自己的程序暂时静止下来负荷调节的需要，如实时紧急任务，由系统把一些不重要的进程挂起内存外存活动静止进程的挂起状态（5-9）静止就绪静止阻塞活动就绪执行活动阻塞挂起I/O请求挂起激活挂起调度释放激活释放唤醒时间片到PCB(ProcessControlBlock)PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。OS是根据PCB来对并发执行的进程进行控制和管理的。是进程存在的唯一标志。PCB可被操作系统中的多个模块读或修改，如被调度程序、资源分配程序、中断处理程序以及监督和分析程序读或修改。PCB经常被系统访问，故应常驻内存。5、进程控制块(1)进程标识符(2)处理机状态(3)进程调度信息：(4)进程控制信息：(1)内部标识（OS使用，数字编号）(2)外部标识（由创建者提供，由字母，数字组成）(1)通用寄存器R(2)指令计数器PC(3)程序状态字PSW(4)用户栈指针(1)进程状态(2)进程优先级(3)与调度算法有关信息(4)等待事件（阻塞原因）(1)程序和数据的地址(2)同步和通信机制(3)资源清单(4)链接指针PCB中的信息(1)链接方式把具有同一状态的PCB，用其链接字链接成一个队列就绪队列、若干个阻塞队列、空队列(2)索引方式系统根据所有进程的状态建立相应的索引表就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。进程控制块的组织方式执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911……PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……执行指针就绪队列指针阻塞队列指针PCB链接队列示意图按索引方式组织PCB就绪索引表阻塞索引表2.2进程的控制进程管理中最基本功能是进程控制。进程控制一般由操作系统的内核来实现。OS内核：把一些与硬件紧密相关的模块或运行频率较高的模块以及为许多模块公用的一些基本操作，安排在靠近硬件的层次中，以提高OS的运行效率。OS内核是常驻内存的程序和数据。内核是通过执行各种原语操作来实现各种控制和管理功能的。原语：由若干条指令构成的“原子操作(atomicoperation)”过程，作为一个整体而不可分割－－要么全都完成，要么全都不做。许多系统调用就是原语。进程控制原语：进程创建、进程撤消、进程阻塞、进程唤醒、进程挂起与激活。进程图ABCDEFGH进程之间的关系：父、子进程与祖先进程；“父”创建“子”、父撤子消子进程可以继承父进程所拥有的资源；当子进程撤销时，将获得的资源归还父进程1、进程创建引起创建进程的事件用户登录、作业调度、提供服务、应用请求原语Creat()按下述步骤创建一个新进程(1)申请空白PCB：若无空闲PCB,则创建失败(2)为新进程分配资源：内存大小——用户提供（作业说明书）；应用进程提供；系统默认分配(3)初始化PCB：ppid、uid;程序计数器=程序入口地址；将进程状态设置为就绪状态或静止就绪状态；设置优先级(4)插入就绪进程队列2、进程撤消引起进程终止的事件正常结束：执行到最后的结束指令，产生中断异常结束：出现错误或因故障而被迫终止（如等待超时）外界干扰：进程应外界的请求而终止运行（父进程终止）进程撤消的过程(1)从PCB集合中检索该进程的PCB，从中读出该进程的状态。(2)若处于执行状态，终止该进程的执行，并置调度标志为真，重新调度。(3)若有子孙进程，将所有子孙进程终止。(4)将进程全部资源归还其父进程或系统。(5)将其PCB从所在队列中移出。3、进程阻塞引起阻塞的事件请求系统服务、启动某种操作、新数据尚未到达、无新工作可做（系统进程阻塞自己）进程的阻塞是进程自身的一种主动行为。进程阻塞的过程（由阻塞原语BLOCK()完成）保存当前进程的CPU现场入口置该进程状态进入等待队列转入进程调度程序4、进程唤醒引起唤醒的事件---与引起阻塞的事件相对应：I/O完成，所期待的数据已经到达进程唤醒的过程（由唤醒原语WAKEUP()完成）阻塞原语与唤醒原语要匹配使用，以免造成“永久阻塞”从阻塞队列中移出被唤醒进程入口置该进程为就绪状态将PCB插入就绪队列转进程调度程序或返回5、进程挂起与激活进程挂起（由挂起原语SUSPEND()完成）引起挂起的事件：如用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起过程：检查被挂进程的状态，改为相应的挂起状态；把进程的PCB复制到指定的区域；最后，转向调度程序重新调度。进程激活（由激活原语ACTIVE()完成）发生激活的事件：如父进程或用户进程请求激活进程过程：先将进程从外存调入内存；检查该进程的现行状态，改为相应的活动状态；根据优先级确定是否需要重新调度。同步现象公共汽车上司机与售票员的合作司机售票员关车门启动汽车行使售票停车开车门互斥现象火车到站的调度火车1火车2火车3…站台轨道2.3进程同步同步：进程间共同完成一项任务时直接发生相互作用的关系进行协作－－等待来自其他进程的信息是一种直接制约关系互斥：进程竞争同一共享资源产生相互制约的关系，进行竞争－－独占分配到的部分或全部共享资源，是一种间接制约关系2、临界区（临界段）临界资源：一段时间内只允许一个进程访问的资源如：打印机、磁带机等临界区：每个进程中访问临界资源的代码段各进程互斥地进入临界区，可实现互斥访问临界资源repeat进入区临界区退出区剩余区Untilfalse检查临界资源是否能访问将临界区标志设为未访问同步机制应遵循的规则空闲让进：当无进程处于临界区时，允许一个请求进入临界区的进程立即进入自己的临界区忙则等待：当已有进程进入自己的临界区时，所有其它试图进入临界区的进程必须等待有限等待：对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免进入“死等”状态让权等待：当进程不能进入自己的临界区时，应释放CPU，以免进程陷入“忙等”软件方法实现的同步机制有两个进程Pi,Pj竞争使用临界资源单标志法:设立一个公用整型变量turn，用于描述允许进入临界区的进程标识缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区进程PiWhile(turn==i)criticalsectionturn=j;remaindersection软件方法实现的同步机制双标志法：设立一个标志数组flag[2]，用于描述进程是否在临界区，初值均为FALSE先检查、后修改：可能导致Pi和Pj同时进入临界区先修改、后检查：可能导致Pi和Pj都进入不了临界区while(flag[j]==FALSE)flag[i]=TRUE;flag[i]=TRUE;while(flag[j]==FALSE)criticalsectioncriticalsectionflag[i]=FALSE;flag[i]=FALSE;remaindersectionremaindersection先修改、后检查先检查、后修改OS实现的同步机制——信号量前面的软件方法实现的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。1965年，信号量由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。3、信号量（灯）机制1965年，荷兰人Dijkstra首先提出信号量机制信号量（Semaphores）用于表示资源数目或请求使用某一资源的进程个数的数据结构。信号量是一个被保护的变量，它的值只能通过初始化和两个wait、signal原语来操作——作为OS核心代码执行。wait操作（P原语）——进程申请使用资源的操作（或申请进入临