搜索
第三章进程管理2/117第三章进程管理概述进程的描述进程控制线程进程互斥和同步进程间通信死锁问题进程其他方面的举例为了描述程序在并发执行时对系统资源的共享，需要一个描述程序执行时动态特征的概念，这就是进程。本章将讨论进程概念、进程控制和进程间关系。3/117第三章进程管理前趋图：是一个有向无循环图。前趋图用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系“→”。P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图节点概述：4/117第三章进程管理图2－1(a)中存在着这样的前趋关系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9图2-1前趋图5/117第三章进程管理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)}应当注意，前趋图中必须不存在循环，但在图2-1(b)中却有着下S2→S3,S3→S2图2-1前趋图6/117第三章进程管理3.1.1程序的顺序执行7/117第三章进程管理图2-2程序的顺序执行S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;试想S1、S2、S3三条语句以何顺序执行？3.1.1程序的顺序执行8/117第三章进程管理程序顺序执行时的特征(1)顺序性：按照程序结构所指定的次序(2)封闭性(运行时候独占处理机资源，运行结果不受外界影响)－程序可再现性：(3)可再现性(初始条件相同，结果相同)9/117第三章进程管理3.1.2程序的并发执行及其特征10/117第三章进程管理3.1.2程序的并发执行程序并发执行的目的：提高计算机的处理能力提高资源利用率分为两种形式：多道程序环境下的多道程序的并发执行在某道程序的几个程序段中，包含可同时执行或可颠倒顺序执行的代码。11/117第三章进程管理3.1.2程序的并发执行定义：程序的并发执行是指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠，即一个程序或程序段的执行尚未结束，另一个程序（段）的执行已经开始的执行方式。并发：在一段时间内的同时并行并行：在同一物理时刻的同时12/117第三章进程管理3.1.2程序的并发执行CPU外设请求带输入启动带磁带输入结束中断中断处理请求磁盘输入启动盘结束中断中断处理CPU外设请求盘输入启动盘，调度B请求带输入启动带结束中断中断处理调度A结束中断中断处理调度B时间t用户程序监督程序磁盘设备磁带设备用户程序A用户程序B监督程序磁盘设备磁带设备13/117第三章进程管理3.1.2程序的并发执行图2-3并发执行时的前趋图P1P2P3P4I1I2I3I4C1C2C3C4Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。如何实现并发执行？14/117第三章进程管理S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b请画出前趋关系图。S1S2S3S415/117第三章进程管理3.1.2程序并发执行时的特征1)间断性(相互制约性)－“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；2)失去封闭性：多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变,致使程序的运行已失去了封闭性。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。3)不可再现性：程序在并发执行时，由于失去了封闭性，也将导致失去其可再现性下面看个小例子：16/117第三章进程管理例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N∶=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。(1)N∶=N+1在Print(N)和N∶=0之前，此时得到的N值分别为n+1,n+1,0。(2)N∶=N+1在Print(N)和N∶=0之后，此时得到的N值分别为n,0,1。(3)N∶=N+1在Print(N)和N∶=0之间，此时得到的N值分别为n,n+1,0。17/117第三章进程管理结论：程序在并发执行时，由于失去了封闭性，其计算结果已经和并发执行速度有关，从而使程序失去了可再现性，亦即，程序经过多次执行后，虽然他们执行时的环境和初始条件相同，但得到的结果却不相同。18/117第三章进程管理顺序执行:并发执行：程序具有封闭性程序失去封闭性独享资源共享资源(互为存在条件)可再现性程序与“计算”不再一一对应有相互制约19/117第三章进程管理3.1概述3.1.1程序的顺序执行和并发执行——程序的并发执行并发执行的条件：达到封闭性和可再现性并发执行失去封闭性的原因是共享资源的影响，去掉这种影响即可。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。）。程序P(i)针对的读变量集和写变量集为R(i)和W(i)。任意两个程序P(i)和P(j)可并发的条件：R(i)W(j)=W(i)R(j)=保证一个程序的两次读之间数据不变化W(i)W(j)=保证写的结果不丢掉现在的问题是这个条件不好检查。怎么办？20/117第三章进程管理3.1概述3.1.1程序的顺序执行和并发执行——程序的并发执行程序活动不再处于一个封闭系统中，呈现了独立性、并发性、动态性以及它们之间的相互制约性。“程序”这个静态概念已经不能如实地反映程序活动的这些特征，为此，引入“进程”这一动态概念来描述系统和用户的程序活动。程序进程21/117第三章进程管理3.1概述3.1.2进程的定义进程是程序的一次执行；一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。简言之，进程是程序的一次执行活动进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位；进程是一个程序及其数据在处理机上顺序执行时所发生的活动；22/117第三章进程管理3.1概述3.1.2进程的定义——进程的特征动态性：进程对应程序的执行进程是动态产生：创建运行消亡进程在其生命周期内，在三种基本状态之间转换独立性：各进程的地址空间相互独立，除非采用进程间通信手段;并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行;异步性：每个进程都以其相对独立的不可预知的速度向前推进;结构化：进程=代码段+数据段+PCB;23/117第三章进程管理3.1概述3.1.2进程与程序的区别进程是动态的，程序是静态的：炒菜菜谱进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程具有并行特征，程序没有。进程是竞争计算机资源的基本单位。24/117第三章进程管理程序与进程的类比程序进程唱歌的曲谱或音乐乐器的乐谱演出或演奏剧本演出火车列车25/117第三章进程管理1、判断题：进程是一个程序在某数据集上的一次执行，所以不同进程对应不同的程序。分析：进程是程序在某数据集上得一次执行，但是不同进程可以对应同一程序。2、程序顺序执行与并发执行有什么不同？3、用户程序必须在进程中运行。正确4、判断题：两次打开Word字处理程序，编辑同一篇文章，因为程序一样(Word2003)，数据一样(同一篇文章)，所以系统中运行的这两个Word字处理程序是同一个进程。错误，运行的是2个不同的进程26/117第三章进程管理3.1概述3.1.2进程的定义——进程与程序的区别用户作业由用户创建由用户指定由系统创建作业步作业步…..线程线程…..进程进程…..27/117第三章进程管理3.2.1进程的组成进程=程序+数据+进程控制块PCB有人把这三部分称为”进程映像”.程序是进程的不可缺少的组成部分；如果一个程序段允许被共享，则它应该是可重入的，或纯代码段数据是进程处理的对象进程控制块是进程的控制结构，包含了进程的描述信息、控制信息和资源信息以及现场保护区，是进程的唯一标识，系统通过PCB管理和控制进程。•通常的程序是不能并发执行的,为使程序能并发执行,应为之配置一进程控制块,即PCB;•所谓创建进程是指创建进程实体中的PCB，撤销亦如此。28/117第三章进程管理3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)进程控制块是由OS维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构包含了进程的描述信息、控制信息和资源信息以及现场保护区PCB是进程动态特性的集中反映系统通过PCB感知进程的存在，通过PCB中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的29/117第三章进程管理3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)PCB结构的全部或部分常驻内存；PCB随进程的创建而填写，随进程的撤消而释放,有生命周期；系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的30/117第三章进程管理3.2.3进程控制块的内容（数据结构很复杂）•进程标识符：–内部进程标识符(processID)，唯一，通常是一个整数；–进程名(外部标识符)，通常基于可执行文件名（不唯一）；–用户标识符(userID)；进程组关系(processgroup)•进程控制信息：–当前状态；–优先级(priority)；–代码执行入口地址；–程序的外存地址；–运行统计信息（执行时间、页面调度）；–进程间同步和通信；阻塞原因•进程调度信息：进程状态、进程优先级、资源信息等•处理机状态：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）31/117第三章进程管理3.2.4PCB的组织方式•链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表–各状态的进程形成不同的链表：就绪链表、阻塞链表•索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表–各状态的进行形成不同的索引表：就绪索引表、阻塞索引表PCBTableReadyBlockedPCBTableIndexTableReadyBlocked32/117第三章进程管理OS是根据PCB来对并发执行的进程进行控制和管理的。简单题：进程控制块的作用（要扩展）？判断题：进程控制块是进程存在的唯一标志。33/117第三章进程管理运行Running就绪Ready等待Blocked3.2进程的描述3.2.5进程的状态及其转换——进程的三种基本状态基本状态间的转换34/117第三章进程管理图2-5进程的三种基本状态及其转换(教材讲5种)就绪阻塞执行时间片完进程调度I/O完成I/O请求结束新进程接纳完成35/117第三章进程管理作业后备队列进程就绪队列外存内存作业调度一些处理器(CPU)阻塞队列阻塞队列处理机调度器（进程调度）:是操作系统中的一段代码，它完成如下功能：1）把处理机从一个进程切换到另一个进程；2）防止某进程独占处理机36/117第三章进程管理3.2.5进程的三种基本状态1）就绪(Ready)状态：已分配到除CPU以外的所有必要的资源，只要能再获得处理机，便可立即执行的状态。多个排成一队称为就绪队列。2)执行状态：指进程已获得处理机，其程序正在执行;在单处理机系统中，只能有一个进程处于执行状态;在多处理机系统中，则可能多个进程处于执行状态。3)阻塞状态：进程因发生某事件(如请求I／O、申请缓冲空间等)而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种