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

NetworkOptimizationExpertTeam第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程NetworkOptimizationExpertTeam教学目的:掌握进程的概念，进程的控制过程掌握进程的同步与通信掌握进程同步与互斥算法熟悉线程的基本概念和通信机制重点与难点：进程的同步互斥算法与通信NetworkOptimizationExpertTeam2.1进程的基本概念2.1.1前趋图2.1.2程序的顺序执行及其特征2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块NetworkOptimizationExpertTeam2.1.1前趋图（PrecedenceGraph）是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。P1P2P3P4P5P6P7P8P9结点有向边直接前驱直接后继初始结点终止结点重量例：具有九个结点的前趋图PiPj前趋关系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9NetworkOptimizationExpertTeamS1S2S3前驱图中不能存在循环关系。如：NetworkOptimizationExpertTeam2.1.2程序的顺序执行及其特征程序：源代码程序、目标代码程序、可执行程序程序执行：编辑、编译、链接、执行程序的结构：顺序结构、分支结构、循环结构NetworkOptimizationExpertTeam程序的顺序执行举例：–例1：输入I，计算C，打印PI1C1P1I2C2P2S1S2S3例2：S1，S2，S3S1：a:＝x＋yS2：b:＝a－5S3：c:＝b＋1NetworkOptimizationExpertTeam程序顺序执行的特征：顺序性：处理机的操作严格按照程序结构所指定的次序执行。封闭性：程序一旦开始执行，其计算结果不受外界因素影响。可再现性：只要程序执行时的环境和初始条件相同，每次重复执行都将获得相同的结果。NetworkOptimizationExpertTeamI1I2I3I4C1C2C3C4P1P2P3P42.1.3程序的并发执行及其特征1.程序的并发执行所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。NetworkOptimizationExpertTeam一个程序段的多条语句的并发执行：S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S2NetworkOptimizationExpertTeam2、程序并发执行的特征间断性由于资源共享和相互合作，并发执行的程序间形成了相互制约关系，导致程序的运行过程出现“执行—暂停—执行”的现象。失去封闭性程序在并发执行时，是多个程序共享系统中的资源，因此这些资源的状态将由多个程序来改变。不可再现性由失去封闭性导致。同样的初始条件，一个程序的多次重复执行，可得到不同的结果。NetworkOptimizationExpertTeam并发执行示例1（与时间有关的错误）因为这种错误和相对执行速度有关，因此称为与时间有关的错误。…a=nif(a=1){a=a-1;n=a;}……//n表示剩余的票数//售出一张票…a=nif(a=1){a=a-1;n=a;}……//n表示剩余的票数//售出一张票NetworkOptimizationExpertTeam并发程序示例2例：程序A、B，共享变量N。代码如下：程序ABEGINREPEAT……N：=N+1……UNTILFALSEEND程序BBEGINREPEAT……PRINT(N)N:=0…UNTILFALSEENDNetworkOptimizationExpertTeam两个程序以不同速度运行，可能出现三种情况：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程序的并发执行使得程序的执行情况不可预见，其结果不再唯一，成为一个动态的过程。而程序是一个静态的概念，不再能切实反映程序执行的各种特征（独立性、并发性、动态性）。所以我们提出了新的概念——进程NetworkOptimizationExpertTeam3、程序并发执行引发的问题：协调各程序的执行顺序：例如：当输入的数据还未全部输入内存时，计算进程必须等待。多个执行程序共享系统资源，程序之间可能会互相影响，甚至影响输出结果。选择哪些、多少个程序进入内存执行？内存中的执行程序谁先执行，谁后执行？内存如何有效分配？NetworkOptimizationExpertTeam4、并发执行的条件：并发执行的条件：达到封闭性和可再现性。并发执行失去封闭性的的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。将程序中任一语句或程序段Pi划分为两个变量的集合，R(pi)和W(pi)。其中，R(pi)={a1,a2,…an}，程序pi在执行期间引用的（读的）变量集，称为“读集”。W(pi)={b1,b2,…bm}，程序pi在执行期间改变的（写的）变量集，称为“写集”。NetworkOptimizationExpertTeamBernstein条件:如果对于语句p1、p2，如果同时满足以下三个条件：R(p1)∩W(p2)={}R(p2)∩W(p1)={}W(p1)∩W(p2)={}则语句p1、p2可以并发执行。NetworkOptimizationExpertTeam例如，有如下四条语句：S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1其中：R(S1)={x,y}W(S1)={a}R(S2)={z}W(S2)={b}R(S3)={a,b}W(S3)={c}R(S4)={c}W(S4)={w}对于S1和S2，有：R(S1)∩W(S2)={}，R(S2)∩W(S1)={}，W(S1)∩W(S2)={}结论：语句S1和S2满足Bernstein条件，可以并发执行。其他语句之间自己分析。NetworkOptimizationExpertTeam2.1.4进程的特征与状态1.进程的定义进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念，所有多道程序设计操作系统都建立在进程的基础上。NetworkOptimizationExpertTeam较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。(4)进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。(5)进程是一个具有一定独立功能的程序关于某个集合的一次运行活动。(我国78年庐山研讨会)1.进程的定义NetworkOptimizationExpertTeam2.进程同程序的比较：进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序是永久的：进程是一个状态变化的过程，是有一定生命期的；而程序可以作为一种软件资料长久保存。进程与程序的组成不同：进程是由程序和数据、进程控制块三部分组成的。进程与程序的对应关系：同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程；一个进程的执行也可以涉及到一个或几个程序（调用）。DiskMemoryNetworkOptimizationExpertTeam3.进程的特征：结构特征：由程序段、数据段、进程控制块三部分组成（进程实体）；动态性：进程的实质是程序的一次执行过程；并发性：多个进程可同存于内存中，能在一段时间内同时运行；独立性：独立运行的基本单位，独立获得资源和调度的基本单位；异步性：各进程按各自独立的不可预知的速度向前推进。NetworkOptimizationExpertTeam4.进程的三种基本状态不同系统设置的进程状态数目不同。进程的三种基本状态是：1)就绪状态：进程已获得除CPU以外的所有必要资源，只要得到CPU，便可立即执行。2)执行状态：进程已得到CPU，其程序正在CPU3)阻塞状态：正在执行的进程因某种事件(如I/O请求)的发生而暂时无法继续执行，只有等相应事件完成后，才能去竞争CPU。NetworkOptimizationExpertTeam进程/线程的执行运行Running被调度时间片用完，中断资源释放或事件完成阻塞Blocked等待资源和事件进程占有处理机，处理机正在执行该进程的程序。进程已获得除处理机外的所需资源，等待分配处理机执行。也叫等待、挂起、睡眠态，此时进程因等待某种条件（如I/O操作或进程同步）无法运行。引起进程阻塞的原因很多，系统将根据不同的阻塞原因将进程插入某个相应的阻塞队列中。就绪Ready三种状态进程模型NetworkOptimizationExpertTeam4、五种状态进程模型创建就绪阻塞执行终止许可I/O请求释放I/O完成时间片完进程调度NetworkOptimizationExpertTeam5、七种状态进程模型创建终止执行活动就绪活动阻塞静止阻塞静止就绪许可许可请求I/O释放激活挂起释放挂起激活挂起释放引入挂起状态的原因：终端用户的请求父进程请求负荷调节的需要操作系统的需要NetworkOptimizationExpertTeam“挂起”的实质是使进程不能继续执行，即使挂起后的进程处于就绪状态，它也不能参与对CPU的竞争。因此，称被挂起的进程处于静止状态，相反，没被挂起的进程则处于活动状态。而且，处于静止状态的进程，只有通过“激活”动作，才能转换成活动状态。进程挂起后,程序代码和数据集被调出到外存的交换区中,腾出来的内存空间供其它进程使用。NetworkOptimizationExpertTeam就绪态（ready）:进程在内存且可立即进入运行状态。阻塞态（blocked）:进程在内存并等待某一个事件的出现。挂起就绪态（readysuspend）:进程在外存,但只要进入内存,即可运行。挂起阻塞态（blockedsuspend）:进程在外存并等待某一个事件的出现。【思考题】有没有这样的状态转换，为什么？阻塞—运行就绪—阻塞NetworkOptimizationExpertTeam6、进程的组成PCB•ProcessControlBlock是灵魂，进程存在的唯一标志。数据程序•程序：描述了进程要完成的功能，是进程执行时不可修改的部分。•数据：进程执行时用到的数据（用户输入的数据、常量、静态变量）。工作区•工作区：参数传递、系统调用时使用的动态区域（堆栈区）。实体NetworkOptimizationExpertTeam2.1.5进程控制块（ProcessControlBlock，PCB）1.进程控制块的作用进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。进程与PCB是一一对应的。PCB应常驻内存。NetworkOptimizationExpertTeam进程名当前状态优先级现场保留区资源清单进程起始地址家族关系其他指示处于同一状态进程的链指针进程标志符进程调度信息进程控制信息2.进程控制块中的信息NetworkOptimi