操作系统 第二章1

OperatingSystemPage12020/2/26OperatingSystemPage22020/2/26第二章进程管理重点理解进程的含义(PCB,进程状态)理解和掌握同步的概念及经典进程同步问题，是本课程的重点之一难点会写进程同步问题的算法知识点进程、线程、进程的特征、PCB、进程控制、进程状态转换、进程同步、进程通信OperatingSystemPage32020/2/26第二章进程描述与控制1.前驱图和程序执行2.进程的描述3.进程控制4.进程同步5.经典进程的同步问题6.进程通信7.线程OperatingSystemPage42020/2/26程序的顺序执行与并发执行单道批处理系统——顺序执行多道程序系统——并发执行在系统中同时存在几个相互独立的程序，这些程序在系统中交叉执行，共享系统中的资源，提高资源利用率。但也会引起一系列的问题，包括：对资源的竞争、程序间的合作与协同、进程间的通信。要解决这些问题，用程序的概念已经不能描述在内存中运行的状态，必须引入新的概念——进程。OperatingSystemPage52020/2/26前驱图和程序执行前趋图——更好的描述程序的顺序/并发执行程序的顺序执行程序的并发执行OperatingSystemPage62020/2/26前趋图前趋图(PrecedenceGraph)是一个有向无循环图，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系(PrecedenceRelation)“→”如果(Pi,Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继,必须Pi执行完成后再执行Pj。没有前趋的结点称为初始结点(InitialNode)，没有后继的结点称为终止结点(FinalNode)OperatingSystemPage72020/2/26前趋图每个结点还具有一个权值(Weight)，用于表示该结点所含有的程序量或结点的执行时间P1P3P8P9P4P2P5P6P7(a)具有九个结点的前趋图S1S2S3(b)具有循环的图，不是前驱图OperatingSystemPage82020/2/26前驱图和程序执行前趋图——更好的描述程序的顺序/并发执行程序的顺序执行程序的并发执行OperatingSystemPage92020/2/26程序顺序执行程序运行的两种方式顺序执行:例如：先输入，再计算，最后输出并发执行OperatingSystemPage102020/2/26程序顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。语句S1,S2,S3必须按顺序执行S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;OperatingSystemPage112020/2/26程序顺序执行Ii→Ci→Pi和S1→S2→S3程序的顺序执行(a)程序的顺序执行I1C1P1I2C2P2(b)三条语句的顺序执行S1S2S3OperatingSystem程序顺序执行顺序执行的特征顺序性：一个操作完成后开始下一个操作封闭性：独占资源，资源的状态只由该程序决定，执行结果不受外界因素影响可再现性：重复执行时，初始条件相同则结果相同，无论“走走停停”还是“不停顿”Page122020/2/26OperatingSystemPage132020/2/26前驱图和程序执行前趋图——更好的描述程序的顺序/并发执行程序的顺序执行程序的并发执行OperatingSystemPage142020/2/26并发执行宏观上同时执行，微观上交替执行。一个程序的执行尚未结束，另一个程序的执行已经开始,实际上某时刻只有一个程序在CPU上运行。程序的并发执行可描述为:S0cobeginS1,S2……SncoendSn+1OperatingSystemPage152020/2/26程序的并发执行及其特征P1P2P3P4I1I2I3I4C1C2C3C4无前驱关系的程序段，可并发执行OperatingSystemPage162020/2/26程序的并发执行及其特征在该例中存在下述前趋关系：Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，无前趋关系（互不依赖），即Ii+1和Ci及Pi-1可以并发执行。OperatingSystemPage172020/2/26程序的并发执行及其特征对于具有下述四条语句的程序段S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+bS1S2S3S4S1S2可并发执行OperatingSystemPage182020/2/26程序的并发执行及其特征并发执行的特征间断(异步)性走走停停，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性共享资源(包括数据)，会受其他程序的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。要使用的资源被其他程序占用。失去可再现性失去封闭性－失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征OperatingSystemPage192020/2/26程序的并发执行及其特征例如有两个循环程序A和B，它们共享一个变量N=n程序A和B以不同的速度运行(失去封闭性，导致不可再现性）N∶=N+1在Print(N)和N∶=0之前，此时得到的N值分别为n+1,n+1,0N∶=N+1在Print(N)和N∶=0之后，此时得到的N值分别为n,0,1N∶=N+1在Print(N)和N∶=0之间，此时得到的N值分别为n,n+1,0程序A：N∶=N+1;程序B：Print(N);N∶=0;OperatingSystemPage202020/2/26程序的并发执行及其特征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程序得到的共享变量结果不同，失去封闭性、不可再现性；要得到良好的控制，系统必须要进行管理——进程控制管理OperatingSystem飞机订票的例子Page212020/2/26一个飞机订票系统，两个终端，运行T1、T2进程T1:T2:......Read(x);Read(x);ifx=1thenifx=1thenx:=x-1;x:=x-1;write(x);write(x);......OperatingSystemPage222020/2/26要得到良好的控制，系统：执行过程要进行管理——进程控制管理需要一个能反映或记录程序执行过程中共享资源/变量的基本单位——进程OperatingSystemPage262020/2/26第二章进程的描述与控制前驱图和程序执行进程的描述进程控制进程同步经典进程的同步问题进程通信线程OperatingSystem进程的描述在多道程序环境下，程序并发执行，执行过程具有间断性，程序已经无法描述这种状况。进程的定义和特征进程的状态及转换进程管理中的数据结构（PCB）Page272020/2/26OperatingSystemPage282020/2/26进程的描述何谓进程（Process）如何理解进程概念？进程与程序有何差别？OperatingSystemPage292020/2/26进程较典型的进程定义有：进程是程序的一次执行；进程是一个程序及其数据在处理机上顺序执行时所发生的活动；进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位；OperatingSystemPage302020/2/26进程与程序有何差别？程序与进程对照程序进程1.唱歌的曲谱演唱2.剧本演出3.菜谱烹饪OperatingSystemPage322020/2/26进程与程序的区别程序是有序指令的集合，是一个静态概念，可以作为程序文件被长久保存，反复使用。进程是一次执行过程，一个动态的概念，具有生命期，可创建和撤销。进程是一个独立的运行单位，可与其他进程并行(或并发)运行，而程序不能。进程是资源分配和处理机调度的基本单位。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序OperatingSystemPage332020/2/26进程的特征结构特征：程序段、数据段和PCB三部分构成进程实体；进程的创建与撤消就是PCB的创建与撤消动态性：一次执行过程，有一定的生命周期并发性：多个进程实体同存于内存中，且能在一段时间内同时运行(并发执行)独立性：独立运行、独立分配资源、独立接受调度异步性：各进程按各自独立的、不可预知的速度向前推进OperatingSystemPage342020/2/26进程的描述进程的定义与特征进程的状态及转换进程控制块OperatingSystemPage352020/2/26进程的状态—进程的三种基本状态就绪(Ready)状态可运行，已获得除CPU外的所需资源，等待分配CPU一个系统中多个处于就绪状态的进程排成就绪队列执行(Running)状态占用CPU运行；处于此状态的进程的数目=CPU的数目没有其它进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）阻塞(Blocked)状态等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行通常阻塞进程也排成一个或多个阻塞队列OperatingSystemPage362020/2/26进程的特征与状态—进程的三种基本状态就绪阻塞执行I/O完成I/O请求进程调度时间片完OperatingSystemPage372020/2/26进程的特征与状态—进程的三种基本状态问题1：为什么不能从阻塞态变为运行态呢？问题2：为什么不能从就绪态变为阻塞态呢？OperatingSystemPage382020/2/26进程的特征与状态—进程的三种基本状态问题1：为什么不能从阻塞态变为运行态呢？问题2：为什么不能从就绪态变为阻塞态呢？状态不能够满足系统和用户需要！！！OperatingSystemPage392020/2/26创建状态和终止状态4)创建状态进程刚建立，创建工作没有完全结束，还未进入就绪队列。5)终止状态进程已（正常或异常）结束，已从就绪队列中移出，但尚未撤销。暂留，以便其他进程收集该进程的有关信息。OperatingSystemPage402020/2/26图2-6进程的五种基本状态及其转换就绪阻塞执行时间片完进程调度I/O完成I/O请求创建终止OperatingSystemPage412020/2/26进程的特征与状态—挂起状态（静止状态）某进程被挂起意味着该进程处于静止状态，不再具有执行条件。相反操作是激活操作。正在执行--暂停执行处于就绪--暂不接受调度OperatingSystemPage422020/2/26进程的特征与状态—挂起状态引起进程挂起的原因有以下几种终端用户的请求当终端用户用于调试，挂起被调试进程研究其执行情况父进程请求父进程需要考查和修改子进程负荷调节的需要为了调整工作负荷或资源紧张情况，可将不重要的进程挂起操作系统的需要如检查运行中的资源使用情况Ope