第2章进程管理上2.1-2.2-1

1•在传统的操作系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位都是进程。操作系统所具有的四大特征也都是基于进程而形成的，并可从进程的观点来研究操作系统。显然，在操作系统中，进程是一个及其重要的概念。因此本章专门来讨论进程。进程的引入2第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程3第二章进程管理•教学重点：进程的定义及特征，进程与程序的异同，进程的状态及引起状态转换的典型原因。临界资源的定义及操作原则，同步与互斥的概念，用信号量描述进程同步，经典进程同步算法的理解。•教学难点：进程的状态及引起进程状态转换的典型原因。用信号量描述进程互斥与同步，判断对临界区操作算法的正确性。•教学目的与要求：本章的学习目的是使学生建立起进程的概念。进程是OS中最重要的基本概念，本章是全书中最重要的一章。要求掌握进程的概念，进程的状态及其转换，进程控制原语，用P、V操作解决进程同步问题，了解进程间的通信，了解线程的概念。4§2.1进程的基本概念多道程序设计操作系统允许多个程序并发执行,因此这种操作系统都是建立在进程的基础上.第一章所述的操作系统的四大特征也都是基于进程而形成的.可见,进程是操作系统中最基本、重要的概念,是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念。5§2.1进程的基本概念◆程序的顺序执行及其特征◆程序的并发执行及其特征62.1.1程序的顺序执行及其特征一个有四条语句的程序段：S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;§2.1进程的基本概念7s1s2s3s4§2.1进程的基本概念2.1.1程序的顺序执行及其特征8程序顺序执行的特征•顺序性•封闭性•可再现性§2.1进程的基本概念2.1.1程序的顺序执行及其特征9•顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一个操作必须在下一操作之前结束。•封闭性：程序在封闭环境下执行，结果不受外界因素影响。•可再现性：只要环境和初始条件相同，程序重复执行时总得到相同结果。§2.1进程的基本概念2.1.1程序的顺序执行及其特征10一个有四条语句的程序段：S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+b;§2.1进程的基本概念2.1.2程序的并发执行及其特征11•程序的并发执行s1s2s3s4§2.1进程的基本概念12§2.1进程的基本概念程序的并发执行的特征(1)间断性在多道程序设计的环境下，程序并发执行，以及为完成一项任务而相互合作，这些程序之间要共享系统的资源，形成了相互制约的关系。共享、合作、制约导致：相互制约导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。(2)失去封闭性主要由共享资源引起，使某程序的运行受到其它程序的影响。例如：当处理机被某个程序占有时，另一程序必须等待。13§2.1进程的基本概念(3)不可再现性程序在并发执行时，失去封闭性导致其失去可再现性。相同环境和初始条件，重复执行结果不同。例：讨论共享公共变量的两个程序，它们执行时可能产生的不同结果。设：程序A每执行一次都要做N加1的操作程序B每隔一定时间打印出N值，并将它重新置为零。（假定某时刻变量N的值为n）程序A:N:=N+1程序B的两个语句:Print(N);N=0N值N值N的最终值之前n+1n+10之后n01之间nn+1014§2.1进程的基本概念2.1.3前趋图•有向无循环图•表示方式：（1）p1---p2（2）---={(p1,p2)|p1必须在p2开始前完成}•（图2-2P35）•节点表示：一条语句，一个程序段，一进程。•名词：初始结点、终止结点、重量（表示执行时间等）P1P1P1P1有向边表示偏序或前趋关系直接前趋直接后继15§2.1进程的基本概念P2P6P5P1P4P3P7P8P9前趋关系：P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P916§2.1进程的基本概念或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)}注意：前趋图中必须不存在循环S3S2S1前趋关系：S2S3，S3S2，不可能满足17§2.1进程的基本概念2.1.4进程的特征与定义为了描述程序在计算机系统内的执行情况，引入进程的概念◆进一步讨论引入进程的原因:–从理论角度看，是对正在运行的程序过程的抽象；–从实现角度看，是一种数据结构，目的在于清晰地刻划动态系统的内在规律，有效管理和调度进入计算机系统主存储器运行的程序。18§2.1进程的基本概念进程的特征描述٭结构特征：进程控制块(PCB)+程序段+相关的数据段=进程实体٭动态性：最基本的特征。进程的实质是进程实体的一次执行过程，有生命周期，由创建而产生，由调度而执行,由撤销而消亡的。٭并发性：多个进程实体同存于内存中,且能在一段时间内同时运行。٭独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；٭异步性：指进程按各自独立的、不可预知的速度向前推进进程定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。19结构特征•进程结构PCB进程控制块程序段数据段动态特征的集中反映描述要完成的功能操作对象及工作区20§2.1进程的基本概念进程的定义(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。21进程和程序的关系（1）进程是一个动态概念，程序是一个静态概念。（2）进程具有并行特征，程序没有。（3）进程是竞争资源的基本单位（4）一个程序对应多个进程，一个进程为多个程序服务。§2.1进程的基本概念22§2.1进程的基本概念进程的三种基本状态进程执行的间断性,决定了进程可能具有多种状态,运行中的进程可能有以下三种基本形态:•就绪状态（Ready）等待分配处理器,只要获得CPU,便立即执行。•执行态（Running）,又叫运行态.占有处理器(CPU)运行•阻塞状态（Blocked）又叫等待态.是指进程因等待某个事件发生（例如等待I/O操作完成，等待其他进程发来的信号）而暂时不能运行的状态，也就是说，处于阻塞状态的进程尚不具备运行条件，即使CPU空闲它也无法使用。23§2.1进程的基本概念就绪阻塞执行时间片完进程调度I/O请求I/O完成图2－5进程的三种基本状态及其转换思考:哪些是不可能发生的状态转换?24§2.1进程的基本概念引起进程状态转换的具体原因执行态→阻塞态：等待使用资源或某事件发生；阻塞态→就绪态：资源得到满足或事件发生；运行态→就绪态：运行时间片到；出现有更高优先权进程。就绪态→运行态：CPU空闲时选择一个就绪进程,即获得CPU25§2.1进程的基本概念•挂起状态（被换出内存的状态）٭引入原因▪终端用户请求▪父进程请求▪负荷调节需要▪操作系统需要挂起状态静止状态非挂起状态活动状态26§2.1进程的基本概念٭进程状态的转换(图2-6)▪活动就绪静止就绪▪活动阻塞静止阻塞▪静止就绪活动就绪▪静止阻塞活动阻塞▪活动就绪:Readya▪静止就绪:Readys▪活动阻塞:Blockeda▪静止阻塞:Blockeds执行活动就绪静止就绪活动阻塞静止阻塞激活挂起激活挂起释放释放挂起请求I/O调度27§2.1进程的基本概念•例题：1．如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；阻塞进程最多几个，最少几个？[解答]：在单处理机系统中，处于运行状态的进程最多为1个，最少为0个；处于就绪进程最多为N-1个，最少为0个；处于阻塞的进程最多为N个，最少为0个。2.有没有这样的状态转换，为什么？（1）阻塞—执行；（2）就绪—阻塞28§2.1进程的基本概念创建状态与终止状态为了管理的需要，还存在着这两种比较常见的状态。创建状态：首先创建PCB，其次把该进程转入就绪状态并插入到就绪队列中。如图P40（2-7）终止状态：首先等待操作系统进行善后处理，然后将PCB清零，并将PCB空间返还系统。如图P40（2-8）292.1.5进程的描述——进程控制块1.进程控制块的作用进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。OS是根据PCB来对并发执行的进程进行控制和管理的。PCB是OS中最重要的记录型结构。PCB是进程存在的唯一标志。进程与PCB是一一对应的。JCB是作业存在的唯一标志。PCB常驻内存。OS专门开辟PCB区将所有的PCB组织成若干个链表或队列。§2.1进程的基本概念30§2.1进程的基本概念（1）进程标识符（ID）（2）进程状态（3）现场保留区（4）程序、数据的地址（5）同步、通信机构（6）资源清单（7）优先级（8）链接字（9）家族关系PCB基本信息31§2.1进程的基本概念1)内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。(1)进程标识符（ID）32处理机状态信息主要是由处理机的各种寄存器中的内容组成的。①通用寄存器②指令计数器③程序状态字PSW（ProgramStatusWord），其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；④用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。§2.1进程的基本概念(2)（现场保留区）33在PCB中还存放一些与进程调度和进程对换有关的信息，包括：①进程状态，指明进程的当前状态，作为进程调度和对换时的依据；②进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；③进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。§2.1进程的基本概念(3)进程调度信息34进程控制信息包括：①程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；②进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；③资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；④链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。§2.1进程的基本概念(4)进程控制信息35§2.1进程的基本概念3.PCB的组织方式٭链接（p42图2-9）٭索引(p43图2-10)36§2.1进程的基本概念1)链接方式把具有统一状态的PCB用其中的链接字链接成一个队列。就绪队列若干个阻塞队列空白队列执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB93637§2.1进程的基本概念2)索引方式:系统根据所有进程的状态建立几张索引表，把各表的内存首地址记录在内存的专用单元中。索引表的表目中记录了具有相应状态的某个PCB在PCB表中的地址。PCB7PCB