操作系统OS02进程管理课件.ppt

第二章 进 程 管 理 1第二章进程管理n 重点：n 进程的定义、进程控制的基本概念。n 进程PCB的基本结构，作用及进程的状态转换。n 进程同步与互斥的基本概念和解决方法。n 几个经典的进程同步与互斥问题及算法。n 线程的基本概念及状态。n 难点：n 进程的同步与互斥第二章 进 程 管 理 2第二章进程管理主要内容：2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程第二章 进 程 管 理 32.1.进程的基本概念2.1.1程序的顺序执行及其特征2.1.2前趋图2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块第二章 进 程 管 理 42.1.1 程序的顺序执行及特征1、程序的顺序执行例1：数据计算时要经过I:输入操作C:计算操作P:打印操作:例2：如下三条语句的执行 S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2、特征n 顺序性、封闭性、可再现性I1C1P1I2C2P2语句 语句S1 S1语句 语句S2 S2语句 语句S3 S3第二章 进 程 管 理 52.1.2 前趋图1、前趋图(PrecedenceGraph)n 一个有向无循环图n 描述进程之间执行的前后关系2、前趋关系“”n=(Pi,Pj)|PimustcompletebeforePjmaystartn 如果：(Pi,Pj)，也可以写成：Pi Pjn 则称：Pi是Pj的直接前趋,Pj是Pi的直接后继n 初始结点：没有前趋n 终止结点：没有后继n 每个结点还具有一个权或重量(Weight)，表示该结点的程序量或执行时间。P1 P2P3P1 P2P3第二章 进 程 管 理 6 其前趋关系表示为：P=P1，P2，P3，P4，P5，P6，P7=（P1,P2）,（P1,P3）,（P1,P4）,（P2,P5）,（P3,P5）,（P4,P6）,（P5,P7）,（P6,P7）P1P4P3P2P6P5P7具有7个结点的前驱图第二章 进 程 管 理 72.1.3 程序的并发执行及其特征I1C1P1I2C2P2I3C3P3I4C4P4输入程序计算程序打印程序1、在对一批程序进行处理时，可以并发执行。例1：输入、计算、打印三个程序对一批作业进行处理时存在前趋关系：前驱关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1第二章 进 程 管 理 82.1.3程序的并发执行及其特征例2：对于下述四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4前驱关系第二章 进 程 管 理 9n 又如：三个程序的执行顺序如图：P1：a:=1P2：x:=a+1P3：y:=a+12.1.3程序的并发执行及其特征P1P2P3前驱关系第二章 进 程 管 理 10程序并发执行条件（Bernstein条件）将任一语句划分为两个变量的集合R(Si)和W(Si):读集R(Si)=a1，a2，am写集W(Si)=b1，b2，bn如对语句S1和S2有：R(S1)W(S2)=W(S1)R(S2)=W(S1)W(S2)=成立，则语句S1和S2可并发执行。第二章 进 程 管 理 11程序并发执行条件（Bernstein条件）例1语句c=ab和w=c+1R（c=ab）=a,bW（c=ab）=cR（w=c+1）=cW（w=c+1）=wR（w=c+1）W（c=ab）=c语句c=ab和w=c+1不能并发执行。第二章 进 程 管 理 122、程序并发执行时的特征n 间断(异步)性：“执行暂停执行”，一个程序可能走到中途停下来，失去原有的时序关系。n 失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。n 不可再现性：失去封闭性失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。第二章 进 程 管 理 13程序并发执行时的不可再现性例如:有两个循环程序A和B，共享一个变量N。程序A每执行一次时，都要做N:=N+1;程序B每执行一次时，都要执行print(N),然后将N置成0。程序A和B以不同的速度运行。可能出现的情况如下(某时刻变量N的值为n)：1、N:=N+1在print(N)和N:=0之前，2、N:=N+1在print(N)和N:=0之后，3、N:=N+1在print(N)和N:=0之间，得到的N值为n+1,n+1,0得到的N值为n,0,1得到的N值为n,n+1,0第二章 进 程 管 理 142.1.4进程的特征与状态1.进程的特征与定义2.进程的三种基本状态3.挂起状态4.创建状态和终止状态第二章 进 程 管 理 15进程特征n 结构特性(PCB-ProcessControlBlock)n 进程实体程序段相关的数据段PCBn 动态性n 由创建而产生，由调度而执行，由撤销而消亡n 并发性n 独立性n 独立运行、独立分配资源、独立接受调度n 异步性第二章 进 程 管 理 16进程定义n 进程的典型定义：（1）进程是程序的一次执行（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动（3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。n 传统OS中进程定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。第二章 进 程 管 理 17进程与程序的区别：（如同“演出”与“剧本”）进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。进程更能真实地描述并发执行，可以揭示OS的内部特征，而程序不能。进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）；程序仅是代码的有序集合。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可涉及到多个程序的执行。进程具有创建其他进程的功能，父进程创建子进程而形成进程树，而程序不能。第二章 进 程 管 理 18进程的基本状态n 三种基本状态：n 就绪状态n 执行状态n 阻塞状态进程状态转换阻塞状态就绪状态执行状态调度I/O请求进程唤醒时间片到第二章 进 程 管 理 19第二章 进 程 管 理 20挂起状态n 引入挂起状态的原因：n 终端用户请求n 父进程请求:考查、修改或协调各子进程时；n 负荷调节的需要：缓和内存紧张的情况；n 操作系统的需要：改善系统运行性能，调节负荷；n 增加的状态：n 挂起状态（静止状态）n 非挂起状态（活动状态）第二章 进 程 管 理 21具有挂起状态的进程状态图活动阻塞执行状态活动就绪静止就绪静止阻塞调度唤醒I/O请求激活激活挂起挂起挂起唤醒第二章 进 程 管 理 22创建状态和终止状态n创建状态n创建一个进程过程：1.为一个新进程创建PCB，并填写必要的管理信息2.把该进程转入就绪状态并插入就绪队列之中n引入创建状态，为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。第二章 进 程 管 理 23创建状态和终止状态n 终止状态n 进程终止过程n 首先，等待操作系统进行善后处理n 然后，将其PCB清零，并将PCB空间返还系统n 当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其它有终止权的进程所终结，它将进入终止状态。第二章 进 程 管 理 24创建状态和终止状态时间片完许可释放进程调度I/O完成I/O请求创建 终止就绪 执行阻塞进程的五种基本状态及转换第二章 进 程 管 理 25创建状态和终止状态（续）激活许可挂起调度挂起释放释放I/O请求激活挂起静止就绪静止阻塞活动就绪执行活动阻塞创建终止许可具有创建、终止和挂起状态的进程状态图第二章 进 程 管 理 262.1.5 进程控制块（PCB）1.PCB的作用2.PCB中的信息3.PCB的组织方式第二章 进 程 管 理 271.PCB的作用n PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。是进程存在的唯一标志。n 作用：使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。n PCB常驻内存，系统将所有的PCB组成若干链表或队列，存放在OS中专门开辟的PCB区内第二章 进 程 管 理 28 2.PCB中的信息l 进程标识符：唯一的标识一个进程 内部标识（方便系统使用）外部标识（由创建者提供，由字母数字组成）l 处理机状态：由CPU的各种寄存器中的内容组成 通用寄存器；指令计数器；程序状态字PSW；用户栈指针进程控制信息pid status schedual control处理机状态信息进程标识符进程调度信息第二章 进 程 管 理 29n 进程调度信息：进程状态；进程优先级；其它信息；等待事件（阻塞原因）n 进程控制信息：程序和数据的地址；同步和通信机制；资源清单；链接指针；进程控制信息pid status schedual control处理机状态信息进程标识符进程调度信息2.PCB中的信息第二章 进 程 管 理 303.PCB的组织方式n PCB数目n 一个系统中的PCB数目可为数十个、数百个甚至数千个n 链接方式n 把具有同一状态的PCB，用其链接字链接成一个队列n 就绪队列、若干个阻塞队列、空队列n 索引方式n 系统根据所有进程的状态建立相应的索引表n 就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。第二章 进 程 管 理 313、PCB的组织方式（续）执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14 PCB14PCB23 PCB23PCB30 PCB30PCB48 PCB48PCB5 PCB5PCB67 PCB67PCB79 PCB79PCB80 PCB80PCB911 PCB911 PCB1 PCB1PCB2 PCB2PCB3 PCB3PCB4 PCB4PCB5 PCB5PCB6 PCB6PCB7 PCB7PCB8 PCB8PCB9 PCB9 执行指针就绪队列指针阻塞队列指针3572496PCB链接队列示意图按索引方式组织PCB就绪索引表阻塞索引表第二章 进 程 管 理 32思考题1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？解答：在单处理机系统中，处于运行状态的进程最多为1个，最少为0个；处于就绪进程最多为N-1个，最少为0个；处于等待的进程最多为N个，最少为0个。第二章 进 程 管 理 33思考题2.有没有这样的状态转换，为什么？等待运行；就绪等待第二章 进 程 管 理 342.2进程控制主要内容：1.进程创建2.进程撤消3.进程阻塞4.进程唤醒5.进程挂起与激活第二章 进 程 管 理 352.2进程控制n 进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。n 进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。无有消亡运行等待就绪等待等待唤醒创建 撤消状态转换第二章 进 程 管 理 36n 内核：加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建进程、撤消进程、进程通信、资源管理的功能。n 原语(primitive)：由若干条指令构成的“原子操作(atomicoperation)”过程，作为一个整体而不可分割，要么全都完成，要么全都不做。原子操作在管态下执行，常驻内存。n 原语的作用：实现进程的通信和控制，系统对进程的控制如不使用原语，就会造成其状态的不确定性，从而达不到进程控制的目的。第二章 进 程 管 理 37处理机运行时的两种状态n 用户态（目态）时不可直接访问受保护的OS代码。n 核心态（管态）时执行OS代码，可以访问全部进程空间。裸机（硬件）裸机（硬件）内核 内核客 客 户 户进 进 程 程客 客 户 户进 进 程 程进程 进程服务器 服务器存储器 存储器服务器 服务器文件 文件服务器 服务器请求应答核心态用户态第二章 进 程 管 理 38进程树PDPBPEPCPFPAPIPHPGPJPKPLPMPN2.2.1进程的创建1、进程图是用于描述一个进程的家族关系的有向树。n 结点代表进程n 有向边代表父子关系n 进程之间的关系：n 父、子进程与祖先进程：PCB中设置家族关系表项n 继承归还资源：“父”创建“子”、“父”撤消“子”第二章 进 程 管 理 392、引起创建（create）进程的事件l 用户登录（分时系统）l 作业调度（批处理系统）l 提供服务（操作系统提供服务）l 应用请求（由现有进程派生）第二章 进 程 管 理 403、进程的创建(Creat()原语)过程：申请空白PCB、为新进程分配资源、初始化PCB、插入就绪进程队列HD就绪队列指针PCB15PCB2PCB3PCB4PCB513PCB60PCB7PCB89PCB912PCB10PCB11PCB1225PCB136空PCB队列指针RAM程序+数据PCB80PCB68第二章 进 程 管 理 412.2.2进程的终止1、引起进程终止事件n 正常结束（Holt指令，Logsoff）n 异常结束n 越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障n 外界干预n 操作员或操作系统干预n 父进程请求n 父进程终止第二章 进 程 管 理 422、进程的终止过程n 根据被终止的进程的标识符，检索出该进程的PCB，读出该进程的状态。n 若该进程处于执行状态，立即终止其执行，置调度方式为真，指示该进程终止后应重新进行调度。n 若该进程有子孙进程，终止其所有子孙进程。n 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。n 将被终止进程的PCB从所在队列中删除。第二章 进 程 管 理 432.2.3进程的阻塞与唤醒1、引起进程阻塞和唤醒的事件n 请求系统服务n 启动某种操作n 新数据尚未到达n 无新工作可做第二章 进 程 管 理 442、进程阻塞的过程n 进程调用阻塞原语block()把自己阻塞，阻塞是进程自身的一种主动性为。n 先停止进程的执行，将PCB中的现行状态由执行改为阻塞。n 并将其PCB插入具有相同事件的阻塞队列。n 转调度程序进行重新调度，将处理机分配给另一就绪进程，保留被阻塞进程的处理机状态。第二章 进 程 管 理 453、进程唤醒的过程n 期待事件出现，相关进程调用唤醒原语wakeup()n 把被阻塞的进程从等待该事件的阻塞队列中移出。n 将其PCB中的现行状态由阻塞改为就绪。n 将该PCB插入就绪队列。n 阻塞与唤醒要匹配使用，以免造成“永久阻塞”n block()和wakeup()要成对出现第二章 进 程 管 理 462.2.4进程的挂起与激活n 调用挂起原语suspend()n 检查被挂起进程的状态，处于活动就绪，便改为静止就绪；处于活动阻塞，便改为静止阻塞；若进程正在执行，则转向调度程序。n 调用激活原语active()n 若进程在外存则将其调入内存，检查进程的状态，处于静止就绪，便改为活动就绪；处于静止阻塞，便改为活动阻塞。第二章 进 程 管 理 472.3进程同步n 进程同步的主要任务：对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。主要内容：2.3.1进程同步的基本概念2.3.2信号量机制2.3.3信号量的应用第二章 进 程 管 理 482.3.1进程同步的基本概念1、两种形式的制约关系：n 间接相互制约关系n 进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。n 直接相互制约关系n 进程同步：合作完成同一个任务的多个进程，在执行速度或某些时序点上必须相互协调的合作关系。前进示例示例第二章 进 程 管 理 49民航售票系统主机A窗口 B窗口C窗口 D窗口每个进程执行的操作：设x表示某航班的票数。ifx0thenx:=x-1;在某时刻x=1，有a、b两人分别去A、B窗口买票，分析售票情况：时间片到a b第二章 进 程 管 理 50进程同步举例：司机售票员司机：P1while(true)启动车辆；正常运行；到站停车；售票员：P2while(true)关门；售票；开门；正确运行过程While(true)（司机）启动车辆；（售票员）关门；（司机）正常运行；（售票员）售票；（司机）到站停车；（售票员）开门；第二章 进 程 管 理 512、临界资源n 临界资源：一次仅允许一个进程访问的资源称为临界资源（互斥资源或共享变量）。n 物理设备：打印机，扫描仪n 例1：两个进程A、B共享一台打印机，若不加以控制，两个进程的输出结果可能交织在一起，很难区分。n 软件资源：全局变量，队列等n 例2：飞机订票问题n 设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对全局变量x加1。第二章 进 程 管 理 52 两个进程共享一个变量x时，两种可能的执行次序：A：p1：r1:=x；r1:=r1+1；x:=r1；p2：r2:=x；r2:=r2+1；x:=r2；B：P1：r1:=x;r1:=r1+1；x:=r1；p2：r2:=x;r2:=r2+1;x:=r2；设x的初值为10，两种情况下的执行结果：情况A：x=10+2情况B：x=10+1第二章 进 程 管 理 53例3：生产者-消费者问题产品outin01n-1缓冲池in:=(in+1)mod nout:=(out+1)mod n第二章 进 程 管 理 54例3：生产者-消费者问题n 缓冲池满：(in+1)modn=outn 缓冲池空：in=outn 引入整型变量：countern 初值：0n 生产：counter+1；n 消费：counter-1。第二章 进 程 管 理 55例3：生产者-消费者问题生产者消费者进程共享下面的变量：varn:integer;typeitem=;varbuffer:array0,1,n-1ofitem;in,out:0,1,n-1;counter:0,1,n;第二章 进 程 管 理 56例3：生产者-消费者程序：producer:repeat produceaniteminnextp;whilecounter=ndono-op;bufferin:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeat whilecounter=0dono-op;nextc:=bufferout;out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;第二章 进 程 管 理 57例3：生产者-消费者程序机器语言实现：生产者：register1:=counter;register1:=register1+1;counter:=register1;假设counter的当前值为5；并发执行时按如下顺序执行：register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;消费者：register2:=counter;register2:=register2-1;counter:=register2;(register1=5)(register1=6)(register2=5)(register2=4)(counter=6)(counter=4)程序的执行失去了再现性！第二章 进 程 管 理 58repeatuntil false临界区剩余区剩余区3、临界区（criticalsection）n 临界区：进程中访问临界资源的一段代码。n 进入区：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，设置相应“正在访问临界区”标志。n 退出区：用于将“正在访问临界区”标志清除。n 剩余区：代码中的其余部分。进入区退出区循环进程第二章 进 程 管 理 593、临界区（续）P1：a:=a+1print(a)互斥P2：a:=a-1print(a)互斥P3：ifa0thena:=a+1elsea:=a-1互斥程序中的临界区第二章 进 程 管 理 604、同步机制应遵循的规则n 为实现进程互斥地进入临界区，可用软件或专门的同步机构实来现同步机制。n 所有同步机制都应遵循四条准则：n 空闲让进：无进程处于临界区。n 忙则等待：已有进程处于其临界区。n 有限等待：等待进入临界区的进程不能“死等”。n 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）。第二章 进 程 管 理 612.3.2信号量机制n 1965年，荷兰人Dijkstra首先提出信号量机制n 信号量（Semaphores）n 仅能被两个原语操作wait(S)-signal(S)修改的整型变量，表示一类资源的物理实体。n 信号量的值表示资源数量，只能由wait(S)和signal(S)原子操作改变。第二章 进 程 管 理 622.3.2信号量机制n 信号量分类：n 互斥的信号量：它的wait(S)-signal(S)在同一个进程中n 同步的信号量：它的wait(S)-signal(S)在不同的进程中n 信号量机制包括：n 整型、记录型、AND型、信号量集机制。第二章 进 程 管 理 631.整型信号量n S是一个整型量，除初始化外仅能通过2个原子操作wait(S)和signal(S)来访问。n wait(S)和signal(S)长时间以来被称为 P、V 操作-荷兰语的proberen(test)和verhogen(increment)