00_Class_2

第二章 进程管理,多道程序设计 进程 进程间的相互作用 进程间的通信 进程调度（CPU调度） 死锁 线程,2.1 多道程序设计,顺序程序 并发程序 多道程序设计,2.1.1 顺序程序,程序： 指令或语句序列，体现了某种算法，所有程序是顺序的 顺序环境： 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响,特征： 程序执行的顺序性 程序执行的封闭性 独占资源，执行过程中不受外界影响 程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同,2.1.2 并发程序,并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的,特征： （1）程序结果的不可再现性 并发程序执行的结果与其执行的相对速度有关，是不确定的 （2）在并发环境下程序的执行是间断性的 执行停执行,（3）资源共享 系统中资源被多个进程使用 （4）独立性和制约性 独立的相对速度、起始时间 进程之间可相互作用（相互制约） 可分为直接作用和间接作用 （5）程序和计算不再一一对应 （计算：一个程序的执行）,2.1.2 并发程序,引入并发的目的： 引入并发是为了提高资源利用率，从而提高系统效率。 并发与并行概念的区别： concurrency,parallel,在顺序环境下 CPU利用率= 40/80 = 50% DEV1利用率= 18.75% DEV2利用率= 31.25%,例：,例：,在并发环境下 CPU利用 = 89%,DEV1并发环境下利用 = 33%,DEV2并发环境下利用 = 66%,2.1.3 多道程序设计,定义：Multiprogramming 多道程序设计是指允许多个程序同时进入内存并运行 （引入目的是为了提高系统效率） 与并发不完全是一个概念，但效果相似,考虑因素： 在多道程序环境下如何向用户提供服务 在并发程序之间如何正确传递消息（通讯） 如何对CPU进行调度，保证每个用户相对公平地得到CPU （CPU是一个只可调度，不可分配的资源）,如何管理其他资源 当各用户对资源使用上发生冲突时，如何处理竞争 对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请分配使用回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候,2.1.4 与时间有关的错误,一个飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: . . Read(x); Read(x); if x=1 then if x=1 then x:=x-1; x:=x-1; write(x); write(x); . .,Cobegin get; copy; put; Coend,复制一个记录,f s t g 初始状态 3,4,.,m 2 2 (1,2) g,c,p 4,5,.,m 3 3 (1,2,3) g,p,c 4,5,.,m 3 3 (1,2,2) c,g,p 4,5,.,m 3 2 (1,2,2) c,p,g 4,5,.,m 3 2 (1,2,2) p,c,g 4,5,.,m 3 2 (1,2,2) p,g,c 4,5,.,m 3 3 (1,2,2) 设信息长度为m，有多少种可能性？,并行环境下程序间的制约关系,2.2 进程 进程的概念 进程的状态及其转换 进程控制块（Process Control Block） 进程的特征,OS 对进程的要求,OS 必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间 OS 必须将资源分配给进程，同时避免死锁 OS必须支持进程间通信以及用户进程创建,2.2.1 进程的概念,定义：Process 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位,进程何时创建?,提交一个批处理作业 用户登录 由OS创建，用以向一用户提供服务( 如：打印文件) 由已存在的一进程创建 一个用户程序可创建多个进程,批处理作业发出暂停（Halt）指令 用户退出登录 进程执行一中止服务请求 出错及失败因素,进程何时中止?,进程中止的原因,正常结束 给定时限到 缺少内存 存储器出界 保护性出错 例子: 写只读文件 算术错 超出时间 进程等待超过对某事件的最大值,进程中止的原因,I/O 失败 无效指令 如试图执行数据 特权指令 操作系统干预 如当死锁发生时 父进程请求中止某一子进程 父进程中止，所以子进程也中止,程序与进程之间的区别： 进程更能真实地描述并发，而程序不能 进程是由程序和数据两部分组成的 程序是动态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有,进程的分类： 系统进程 用户进程 （系统进程优先于用户进程）,2.2.2 进程的基本状态及其转换,进程的三种基本状态： 进程在生命消亡前处于且仅处于三种基本状态之一 不同系统设置的进程状态数目不同,运行态（Running）： 进程占有CPU，并在CPU上运行 就绪态（Ready）： 一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行） 等待态（Blocked）：阻塞态、挂起态、封锁态 冻结态、睡眠态 指进程因等待某种事件的发生而暂时不能运行的状态 （即使CPU空闲，该进程也不可运行）,运行,就绪,等待,进程的状态及其转换,进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换 就绪运行 运行就绪 运行等待 等待就绪,进程转换,就绪 运行 时间一到，调度程序选择一个新的进程运行 运行 就绪 运行进程用完了时间片 运行进程被中断，因为一高优先级进程处于就绪状态,运行 阻塞 当一进程所需的东西必须等待时 OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O 且必须等待结果 等待某一进程提供输入 (IPC) 阻塞 运行 当所等待的事件发生时,进程转换,其他状态： 创建状态，终止状态 挂起状态 （调节负载，对换，父进程，操作系统，终端用户）,创建( 新new)状态 OS 已完成为创建一进程所必要的工作 已构造了进程标识符 已创建了管理进程所需的表格 但还没有允许执行该进程 (尚未同意) 因为资源有限,终止（退出exit)状态 中止后进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 例子: 为处理用户帐单而累计资源使用情况的财务程序 当数据不再需要后，进程(和它的表格)被删除,五状态进程模型,准备退出：父进程可中止子进程,新状态转换 (中期调度),阻塞 阻塞挂起 当所有进程都阻塞，OS会安排空间让一就绪进程进入内存 阻塞挂起 就绪挂起 当等待的事件发生时 (状态信息已在OS中) 就绪挂起就绪 当内存中没有就绪进程时 就绪就绪挂起 (较少见) 当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时,七状态进程模型,2.2.3 进程控制块 （Process Control Block）,概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的,进程映象 (进程要素),用户程序 用户数据 栈 用于过程调用和参数传递 进程控制块PCB (执行上下文) 控制进程所需的数据(进程属性)，包括: 进程标识符信息 处理器状态信息 进程控制信息,PCB的内容： 调度信息： 进程名；进程的内部标识；用户名；进程状态；进程优先级；进程的存储信息（起始地址，长度）；进程资源清单；进程家族关系；进程的队列指针；进程的消息队列指针；进程当前打开的文件 . 现场信息： 记录了重要的寄存器；(虚)时钟等内容,进程标识符 (在PCB中),可使用一些数字标识符 统一进程标识符 (必然的) 索引至 (直接或间接) 主进程表 用户标识符 与某个作业对应的用户 创建本进程的某个进程的标识符,处理器状态信息 (在PCB中),处理器寄存器内容 用户可见寄存器 控制和状态寄存器 栈指针 程序状态字 (PSW) 包含状态信息 例子: 在Pentium机中的EFLAGS寄存器,进程控制信息 (在PCB中),调度和状态信息 进程状态 (如: 运行，就绪，阻塞.) 进程优先级 该进程在等待的事件 (若被阻塞) 数据结构信息 进程可能需要有指向其他PCB的指针, 父-子进程关系及其它结构,进程间通信 IPC可能需要标志和信号 进程特权 如: 访问特定的内存地址. 存储管理 指向赋予该进程的段/页表的指针 所拥有的资源和使用情况 使用中的资源: 打开的文件，I/O设备. (CPU , I/O.)的时间使用史,进程控制信息 (在PCB中),执行的方式,为了提供对PCB (和OS其它数据)的保护，多数处理器支持至少两种执行方式: 特权方式 (又称作系统方式，内核方式，管理方式,控制方式) 操作控制寄存器,基本 I/O指令， 存储管理. 用户方式 为此， CPU提供一个(或一些)方式位，这些二进制位只能被中断、陷阱或OS调用所设置,PCB表： 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度 （注：多道程序中的多道与系统并发度不同）,进程控制块（Process Control Block）,PCB表组织方式：,常用索引方式，对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址 （其他方式：线性表或链表） 进程队列：不同状态进程分别组成队列 运行队列、就绪队列、等待队列,2.2.4 进程控制,创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 挂起原语 激活（解挂）原语,进程的创建,创建一个PCB 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 许多默认值 (如: 状态为 New，无I/O设备或文件.) 设置相应的链接 如: 把新进程加到就绪队列的链表中,进程撤消,收回进程所占有的资源 撤消该进程的PCB,进程阻塞,处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态 进程唤醒,2.2.5 进程的特征,并发性 任何进程都可以同其他进程一起向前推进 动态性 进程对应程序的执行 进程是动态产生，动态消亡的 进程在其生命周期内，在三种基本状态之间转换,独立性 进程是CPU调度的一个独立单位 交互性 指进程在执行过程中可能与其它进程产生直接或间接的关系 异步性 每个进程都与其相对独立的不可预知的速度向前推进,结构性： 进程的组成：程序+数据+PCB 可再入程序： 可被多个进程同时调用的程序，具有下列性质： 它是纯代码的，即在执行过程中自身不改变，调用它的进程应该提供数据区,【思考题】：,1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？ 2. 有没有这样的状态转换，为什么？ 等待运行； 就绪等待 3. 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能 4. 举3个日常生活中类似进程的例子,2.3 进程间的相互作用,进程间的联系 进程的同步机制信号量及P.V操作（解决进程同步互斥问题）,2.3.1 进程间的联系,相交进程与无关进程 相交进程：指多个并发进程在逻辑上有某种联系 无关进程（不相交进程）：在逻辑上无任何联系的进程,直接作用和间接作用 直接作用： 进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间 间接作用： 进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间,进程的同步（直接作用）,进程的同步：synchronism 指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态,例: 司机 P1 售票员 P2 REPEAT REPEAT 启动 关门 正常运行 售票 到站停 开门 UNTIL FALSE UNTIL FALSE,进程的互斥（间接作用）mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥,临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量,临界区（互斥区）：critical section 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫临界区,a := a -1 print (a),a := a +1 print (a),进程的互斥 （间接作用）,进程的互斥（间接作用）,使用互斥区的原则： 有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 无空等待：不允许两个以上的进程同时进入互斥区 有限等待：任何进入互斥区的要求应在有限的时间内得到满足,使用互斥区的原则： 前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定 解决方法： 硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高） 软件（用编程解决，但常常忙等待 ）,软件解法 (1) free: 表示临界状态 true: 无进程在临界区(初值) false:有进程在临界区 L: if free then begin free:=false; 进入临界区 end else goto L; free:=true,软件解法 (2) turn: true P进入临界区 false Q进入临界区 P: repeat until turn; 进入临界区 turn:=flase; Q: repeat until not turn; 进入临界区 turn:=true;,软件解法：(3) pturn,qturn: 初值为false P进入临界区的条件: pturn not qturn Q进入临界区的条件: not pturn qturn P Q . pturn:=true; qturn:=ture; repeat until not qturn; repeat until not pturn 进入临界区 进入临界区 pturn:=false; qturn:=false . .,软件解法(4) Dekker算法: 在解法(3)基础上引入turn枚举类型 初值任意 P : Repeat pturn:=true; while qturn do if turn=2 then begin pturn:=false; while turn=2 do； ； pturn:=true end; 进入临界区 turn:=2; pturn:=false; . Until false,(4) Dekker算法: Q : Repeat qturn:=true; while pturn do if turn=1 then begin qturn:=false; while turn=1 do qturn:=true end; 进入临界区 turn:=1; qturn:=false; . Until false,软件解法的缺点： 1. 忙等待 2. 实现过于复杂，需要高的编程技巧,硬件解法 (1) “测试并建立”指令,Function Test_and_Set (var target:boolean):boolean begin Test_and_Set:=target; target:=true end,硬件解法 (1),Var lock:boolean; 进入临界区前执行： While Test_and_Set(lock) do skip; 离开临界区后执行： lock:=false;,硬件解法 (2) “交换”指令,Function Swap(var a,b:boolean) Var temp:boolean; begin temp:=a; a:=b; b:=temp end,每一组共享变量定义一个全局变量,Var lock:boolean; 每个进程定义一个局部变量 Var key:boolean; 进入临界区前执行： key:=true; repeat swap(lock,key); until key=false; 离开临界区后执行：lock:=false;,硬件解法 (3) “开关中断”指令,进入临界区前执行： 执行“关中断”指令 离开临界区后执行： 执行“开中断”指令,2.3.2 进程的同步机制 信号量及P.V操作（解决进程同步）,同步机制： 信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中） 会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）,同步机制应满足的基本要求： * 描述能力 * 可以实现 * 效率高 * 使用方便,信号量：semaphore 是一个数据结构，定义如下： TYPE semaphore= RECORD Value：integer Queue：Pointer_PCB END 信号量说明： VAR：S：semaphore,P.V操作,P操作 P(s) : s . Value : = s . Value - 1; IF s . Value 0 then 将该进程状态置为等待状态 然后将该进程的PCB插入相应的等待队列末尾,P.V操作,V操作 V(s) : s .Value : = s .Value + 1; IF s .Value = 0 then 唤醒相应等待队列中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列,P、V操作为原语操作 原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性 即原语的执行必须是连续的，在执行过程中不允许被中断 实现：开关中断,信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作,用P.V操作解决进程间互斥问题,经典的生产者消费者问题,消费者,生产者,缓冲区,经典的生产者消费者问题,同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为S1 Q进程不能从“空”的缓冲区中取产品，设置信号量S2,P： Q： Repeat Repeat 生产一个产品； P(s2); 送产品到缓冲区； 从缓冲区取产品； V(s2); V(s1); P(s1) 消费产品 Until false; Until false;,S1初值为0，S2初值为0,P： Repeat P(s1); 生产一个产品； 送产品到缓冲区； V(s2) Until false;,S1初值为1，S2初值为0,【思考题】要不要对缓冲区（临界资源）进行互斥操作？,P： I:= 0 REPEAT 生产产品； P(S1) 往Buffer I中放产品； V(S2) I:=(I+1) mod n UNTIL false,Q： J:= 0 REPEAT P(S2) 从BufferJ取产品； V(S1) 消费产品 J:=(J+1) mod n UNTIL false,P.V操作讨论 1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于0,2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要,3）P.V操作的优缺点 优点： 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题） 缺点： 不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂,【作业】,1.用P.V操作解决下图之同步问题:,get,copy,put,f,s,t,g,2.用P.V操作解决司机与售票员的问题,2.3.3 IPC经典问题,1.读者写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,第一类：读者优先,如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,读者与写者问题,2.哲学家就餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,Repeat 思考； 取forki;取fork(i+1) mod 5； 进食； 放forki;放fork(i+1) mod 5； Until false;,为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿,state:array04 of (思考，饥饿，进食）； ph: array04 of semaphore; mutex:semaphore; i:04;,Procedure philosopher(i: 04) Begin Repeat 思考； statei :=饥饿； P(mutex); test(i); V(mutex); P(ph i ); 拿左筷子； 拿右筷子； 进食； 放左筷子； 放右筷子；,P(mutex) state i :=思考； test(i-1mod5); tset(i+1mod5); V(mutex); until fales End state I =思考 ph I =0 mutex=1,【作业】,1. 推广例子中的消息缓冲问题。 消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次,2.第二类读者写者问题： 写者优先 条件： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行） 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）,3.有一个系统，定义P、V操作如下： P(s): s:=s-1; if s0 then 将本进程插入相应队列末尾等待； V(s)： s:=s+1; if s=0 then 从相应等待队列队尾唤醒一个进程，将其插入就绪队列；,问题： 1）这样定义P、V操作是否有问题？ 2）用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。 3）对于2）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？,4.理发师睡觉问题 理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子 如果没有顾客,则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先唤醒理发师 如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开,2.3.2 进程的同步机制管程,管程的提出 采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中,缺点： （）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序,（）不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局,（）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的,管程：一种同步机制 (管程-类程-进程) 管程定义: 指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作,系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性,管程：集中式同步机制，它的基本思想是将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，一个操作系统或并发程序由若干个这样的模块所构成，由于一个模块通常较短，模块之间关系清晰，提高了可读性，便于修改和维护，正确性易于保证,管程的形式 TYPE monitor_name = MONITOR; 共享变量说明 define 本管程内所定义、本管程外可调用的过程（函数）名字表 use 本管程外所定义、本管程内将调用的过程（函数）名字表,PROCEDURE 过程名（形参表）； 过程局部变量说明； BEGIN 语句序列； END; ,FUNCTION 函数名（形参表）：值类型； 函数局部变量说明； BEGIN 语句序列； END; BEGIN 共享变量初始化语句序列； END;,管程的三个主要的特性： （一）模块化，一个管程是一个基本程序单位，可以单独编译,（二）抽象数据类型，管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码,（三）信息掩蔽，管程是半透明的，管程中的外部过程（函数）实现了某些功能，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的,管程有如下几个要素： （一）管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量,（二）为了保证管程共享变量的数据完整性，规定管程互斥进入,（三）管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作,问题：多个进程出现在管程中 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程,处理方法有三种： 等待继续，直到退出或等待 等待继续，直到等待或退出 规定唤醒为管程中最后一个可执行的 操作,因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列,如果进程唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级,由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量。 称作条件变量： VAR C:condition;,对于条件型变量，可以执行wait和signal操作： wait（c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程的PCB入c链尾部,signal（c）：如果c链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部,管程的实现 两个主要途径： * 直接构造 * 间接构造，即用某种已经实现的同步机制去构造 前者效率高 例子：用PV操作构造管程,管程的四个组成部分： 名称 数据结构说明 对该数据结构进行操作的一组过程/函数 初始化语句,TYPE one_instance=RECORD mutex:semaphore;（初值1） urgent:semaphore;（初值0） urgent_count:integer;（初值0） END; TYPE monitor_elements=MODULE; define enter,leave,wait,signal;,mutex（入口互斥队列） urgent（紧急等待队列） urgent_count（紧急等待计数）,PROCEDURE enter(VAR instance:one_instance);,BEGIN P(instance.mutex) END;,PROCEDURE leave(VAR instance:one_instance);,BEGIN IF instance.urgent_count 0 THEN BEGIN instance.urgent-; V(instance.urgent) END ELSE V(instance.mutex) END;,PROCEDURE wait(VAR instance:one_instance;VAR s:semephore;VAR count:integer); BEGIN count+; IF instance.urgent_count0 THEN BEGIN instance.urgent_count-; V(instance.urgent) END ELSE V(instance. mutex); P(s); END;,PROCEDURE signal(VAR instance:one_instance;VAR s:semaphore;VAR count:integer); BEGIN IF count0 THEN BEGIN count-; instance.urgent_count+; V(s); P(instance.urgent) END END;,例子：一个信息缓冲区是一个共享资源 抽象成一个数据结构：数组 构造一些操作（过程或函数） 发送：向缓冲区发消息 接收：从缓冲区取消息 隐藏了内部的数据结构和实现细节,例子：读者-写者问题,TYPE r_and_w=MODULE; VAR instance:one_instance; rq,wq:semaphore; r_count,w_count:integer; reading_count,write_count:integer; define start_r,finish_r,start_w,finish_w; use monitor_elements.enter, monitor_elements.leave, monitor_elements.wait, monitor_elements.signal;,PROCEDURE start_r; BEGIN monitor_elements.enter(instance); IF write_count0 THEN monitor_elements.wait (instance,rq,r_count); reading_count+; monitor_elements.signal (instance,rq,r_count); monitor_elements.leave(instance); END;,PROCEDURE finish_r; BEGIN monitor_elements.enter(instance); reading_count-; IF reading_count=0 THEN monitor_elements.signal (instance,wq,w_count); monitor_elements.leave(instance); END;,PROCEDURE start_w; BEGIN monitor_elements.enter(instance); write_count+; IF (write_count1) OR(reading_count0) THEN monitor_elements.wait (instance,wq,w_count); monitor_elements.leave(instance); END;,BEGIN reading_count:=0; write_count:=0; r_count:=0; w_count:=0; END;,读者的活动： r_and_w.start_r; 读操作； r_and_w.finish_r; 写者的活动： r_and_w.start_w; 写操作； r_and_w.finish_w;,管程和进程的异同点： （1）设置进程和管程的目的不同 （2）系统管理数据结构 进程：PCB 管程：等待队列 （3）管程被进程调用 （4）管程是操作系统的固有成分，无创建和撤消,2.4 进程通信,概述 消息缓冲通信方式,2.4.1 概述,P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息 如果要在进程间传递大量信息则要用Send / Receive原语（高级通讯原语）,2.4.1 概念,进程通信的方式 共享内存： 相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换 这种通信模式需要解决两个问题？,进程通信的方式,消息传递： 系统为进程提供了两个高级通讯原语send和receive send： 当要进行消息传递时执行send receive： 当接收者要接收消息时执行receive,共享文件模式：,管道通信,消息传递模式,消息缓冲 在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区 信箱通信,直接方式：,发送进程发消息时要指定接收进程的名字， 反过来，接收时要指明发送进程的名字 Send(receiver,message) Receiver(sender,message) * 对称形式：一对一 * 非对称形式：多对一 （顾客/服务员） 有缓冲（有界，无界），无缓冲,间接方式：,发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信 发送原语：send(MB,Message) 接收原语：receive(MB,Message),2.4.2 消息缓冲,（有界缓冲区原理）： 在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行,2.4.2 消息缓冲,（有界缓冲区原理）： 在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行,消息缓冲区结构： 消息长度 消息正文 发送者 消息队列指针,用P.V操作来实现Send原语: Send（R，M） P(m-mutex); Begin 把缓冲区挂到接收进程 根据R找接收进程， 的消息链链尾; 如果没找到出错返回; V(m-mutex); 申请空缓冲区P（s-b）； V(s-m); P(b-mutex); END 摘空缓冲区; V(b-mutex); 把消息从M处copy到空缓冲区; 其中s-b初值:n ;s-m初值:0,管道通信方式 Pipe 也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质,2.5 进程调度（CPU调用）,要解决的问题 WHAT：按什么原则分配CPU进程调度算法 WHEN：何时分配CPU进程调度的时机 HOW： 如何分配CPUCPU调度过程 （进程的上下文切换）,何时切换进程?,只要OS取得对CPU的控制，进程切换就可能发生，如，当: 超级用户调用 来自程序的显式请求 (如：打开文件)， 该进程多半会被阻塞 陷阱 最末一条指令导致出错，会引起进程移至退出状态 中断 外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）,中断的例子 时钟 进程用完其时间片，被转换至就绪状态 I/O 先前等待该事件的进程被转换为就绪(或就绪挂起)状态 然后重新运行该进程或选择一更高优先级的进程 存储器因素 内存地址是在虚拟存储器中，它必须把对应的存储块调入主存 于是相应的进程成为阻塞状态(等待I/O完成),方式切换,在中断没有引起进程切换时，方式切换可能发生 控制可只返回给中断程序 然后只有处理器状态信息需要保存在栈中 这称为方式切换 (当进入IH时，用户方式转到内核方式) 较少过载：不需要象进程切换那样更新PCB,在进程（上下文）中切换的步骤,保存处理器的上下文，包括程序计数器和其它寄存器 用新状态和其它相关信息更新正在运行进程的PCB 把移至合适的队列-就绪、阻塞 选择另一个要执行的进程 更新被选中进程的PCB 从被选中进程中重装入 CPU 上下文,2.5.1 进程调度算法,1进程调度 进程调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,2确定算法的原则,具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量,3各种进程调度算法,先进先出进程调度算法（FIFO） 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级,基于优先数的调度 （HPFHighest Priority First）,优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定,确定优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,两种占用CPU的方式,可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式Nonpreemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去,时间片轮转程序调度算法 (RRRound Robin),把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行,分时系统中常用时间片轮转法,时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力,多队列反馈调度算法：,将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列,* 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 * 一个新进程就绪后进入第一级队列,* 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列,2.5.2 进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待状态（等待I/O） 分时系统中时间片到,2.5.2 进程调度的时机,当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）,2.5.3 CPU调度过程,* 保存现场：顺序保存，最后一步保存PSW * 选择要运行的程序 （如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其他进程时该进程一直运行,在执行过程中可接收中断） * 恢复现场：最后一步恢复选中进程的PSW,2.6 系统核心,系统核心： 向上提供多个无中断的虚拟机器 在核心内不允许中断 特点：* 为进程运行提供一个舞台 * 核心常驻内存 * 设计短小精焊,2.6.1 核心的组成,中断处理 进程管理: 调度 控制 通讯 互斥 同步等 原语管理: 在核心中提供一系列原语，同步,通信，创建，撤消等,队列管理:,队列数据结构:指向队首的表指针 三个队列: 运行，就绪，等待队列 排队方式: 排队首 排队尾 插 队 出队方式: 队首出队/队中出队 队列管理: 中断之后，进程调度之前,现场管理:,保存现场;注意顺序,中断之后第一步 恢复现场:恢复时机，进程调度最后一步 时钟管理: 以固定频率 +1 -1 用途:进入绝对时钟 间隔时钟 进行分析比较,虚时钟:,每个进程分配给一个虚时钟来记录CPU时间,这个时钟称为虚时钟 虚时钟存放在PCB中，属于现场的一部分，进程运行时，将虚时钟放入内存开辟的专门单元，离开CPU则放在 PCB中,2.6.2 核心处理流程,进入核心的唯一入口:中断 中断后进入核心，由硬件完成,2.6.3 内核的执行特点,由中断驱动的