计算机操作系统(2)第2章 进程管理

第二章进程管理重点理解进程的含义理解和掌握同步的概念及经典进程同步问题，是本课程的重点之一难点会写进程同步问题的算法知识点进程、线程、进程的特征、PCB、进程控制、进程状态转换、进程同步、进程通信第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程2.1进程的基本概念程序的顺序执行及其特征程序的顺序执行通常可以把一个应用程序分成若干个程序段，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。顺序执行实例S1:a:=x+y；S2:b:=a-5；S3:c:=b+1；其中，语句S2必须在语句S1之后(即a被赋值)才能执行；同样，语句S3也只能在b被赋值后才能执行。程序的顺序执行及其特征Ii→Ci→Pi和S1→S2→S3程序的顺序执行(a)程序的顺序执行I1C1P1I2C2P2(b)三条语句的顺序执行S1S2S3程序的顺序执行及其特征顺序性：按照程序结构所指定的次序（可能有分支或循环）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系(PrecedenceRelation)“→”→={(Pi,Pj)|Pj开始前Pi必须完成},如果(Pi,Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)前趋图实例每个结点还具有一个重量(Weight,权值)，用于表示该结点所含有的程序量或结点的执行时间。P1P3P8P9P4P2P5P6P7(a)具有九个结点的前趋图(b)具有循环的前趋图S1S2S3前趋图实例P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9或表示为：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，P9)，(P8，P9)}注意：前趋图中必须不存在循环，但右图中却有着下述的前趋关系：S2→S3，S3→S2S1S2S3程序的并发执行及其特征程序的并发执行P1P2P3P4I1I2I3I4C1C2C3C4前趋：Ii→Ci，Ci→Pi,Ii→Ii+1,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。程序的并发执行及其特征对于具有下述四条语句的程序段S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+bS1S2S3S4程序并发执行时的特征间断(异步)性走走停停，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。失去可再现性失去封闭性－失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征并发执行实例程序AN:=N+1程序BPrint(N)N:=0N例，程序A和B，共享变量N，它们的功能如下：N：n程序A：N∶=N+1;//N==n+1程序B：Print(N);//N=n+1N∶=0;//N==0程序切换N：n程序B：Print(N);//N=nN∶=0;//N==0程序A：N∶=N+1;//N==1程序切换N：n程序B：Print(N);//N=n程序切换程序A：N∶=N+1;//N==n+1程序切换程序B：N∶=0;//N==0注意：A、B程序得到的共享变量结果不同，失去封闭性、不可再现性；要得到良好的控制，系统必须要进行管理——进程控制管理并发执行实例程序并发执行时的特征并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。）程序P(i)针对共享变量的读集和写集R(i)和W(i)条件：任意两个程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。程序并发执行的条件若两个程序P1和P2满足下述条件，便能并发执行且有可再现性：R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}“读集”R(Pi)为程序Pi在执行期间所需参考的所有变量的集合。“写集”W(Pi)为程序Pi在执行期间所需改变的所有变量的集合。例如：S1:a:=x+yS2:b:=z+1S3:c:=a-bS4:d:=c+1S1:a:=x+yR(S1)={}W(S1)={}S2:b:=z+1R(S2)={}W(S2)={}S3:c:=a-bR(S3)={}W(S3)={}S4:d:=c+1R(S4)={}W(S4)={}语句S1、S2______并发，因为______________________。语句S1、S3______并发，因为______________________。语句S2、S3______并发，因为______________________。语句S3、S4______并发，因为______________________。语句S2、S4______并发，因为______________________。x,yazba,bccd可以R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}不能R(S3)∩W(S1)={a}≠{}不能不能可以R(S3)∩W(S2)={b}≠{}R(S4)∩W(S3)={c}≠{}程序并发执行的条件2.1.4进程的特征与状态何谓进程（Process）描述性定义：计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。如何理解进程概念？进程与程序有何差别？2.1.4进程的特征与状态主妇阅读菜谱准备原料烹制菜肴饭菜阅读洗衣机手册准备衣服、洗衣粉设定参数，洗衣服干净衣服程序输入运行输出程序输入运行输出分时切换洗衣进程做饭进程2.1.4进程的特征与状态进程的核心思想进程是某种类型的一个活动，它有程序、输入、输出和状态。在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。2.1.4进程的特征与状态进程的特征和定义结构特征采用机制：进程控制块，PCB(ProcessControlBlock)。进程实体：程序段、相关的数据段和PCB。注：在早期的UNIX中，把这三部分总称为“进程映像”。在许多情况下所说的进程，实际上是指进程实体。2.1.4进程的特征与状态进程的特征和定义动态性进程的实质：进程实体的一次执行过程，因此，动态性是进程的最基本的特征。它由创建而产生，由调度而执行，由撤消而消亡。进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存放于某种介质上，其本身并不具有运动的含义，因而是静态的。2.1.4进程的特征与状态进程的特征和定义并发性指多个进程实体同存于内存中，且能在一段时间内同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行；而程序(没有建立PCB)是不能并发执行的。独立性在传统的OS中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。2.1.4进程的特征与状态进程的特征和定义异步性指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。进程概念进程是一个程序及其数据在处理机上顺序执行时所发进程是程序在一个数据集合上运行的过程，它是系统在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序进程的三种基本状态就绪(Ready)状态可运行，已获得除CPU外的所需资源，等待分配CPU一个系统中多个处于就绪状态的进程排成就绪队列执行(Running)状态占用CPU运行；处于此状态的进程的数目=CPU的数目没有其它进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）阻塞(Blocked)状态等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行通常阻塞进程也排成一个阻塞队列就就就就就就就就就就就就就就I/O就就I/O就就进程的三种基本状态及转换挂起状态挂起/激活挂起(进程)：暂时被淘汰出内存的进程。在资源不足的情况下，OS对在内存中的程序进行合理的安排，其中有的进程被暂时调离出内存。激活：当条件允许的时候，会被操作系统再次调回内存。内内内内内内内内挂起状态目的提高处理机效率：就绪进程表为空时，要提交新进程，以提高处理机效率；为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）挂起状态引入挂起状态的原因终端用户的请求当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时将自己的程序静止下来父进程请求父进程需要考查和修改子进程负荷调节的需要在实时系统中为了调整工作负荷可将不重要的进程挂起操作系统的需要如检查运行中的资源使用情况挂起状态挂起就绪静止就绪挂起阻塞静止阻塞挂起执行激活激活活动就绪活动阻塞挂起状态转换事件出现(EventOccurs)：进程等待的事件出现，如：操作完成、申请成功等；可能的情况有：阻塞到就绪：针对内存进程的事件出现；阻塞挂起到就绪挂起：针对外存进程的事件出现；收容(Admit)：收容一个新进程，进入就绪状态或就绪挂起状态。进入就绪挂起的原因是系统希望保持一个大的就绪进程表（挂起和非挂起）；就就就就就就就就就就就就就就就就就就就就就就就就就就就就就就就就就就I/O就就具有挂起状态的进程状态创建状态和终止状态创建状态为一个新进程创建PCB，并填写必要的管理信息；把该进程转入就绪状态并插入就绪队列之中。终止状态等待操作系统进行善后处理；将其PCB清零，并将PCB空间返还系统。就就就就就就就就就就就就I/O就就就就I/O就就就就就就就就就就进程的五种基本状态及转换就就就就就就就就就就就就就就就就就就就就就就就就就就就就I/O就就就就就就就就就就就就就就就就具有创建、终止和挂起状态的进程状态需要增加考虑的种情况(1)NULL→创建：一个新进程产生时，该进程处于创建状态。(2)创建→活