搜索
操作系统重难点串讲讲师：翔高教育一级培训师地点：上海第三章处理机调度与死锁重难点导航三级调度之间的比较和含义常见的调度算法的比较用常见的调度算法调度当前系统，并计算平均周转周期、平均加权周转时间、平均等待时间用死锁发生的必要条件来分析系统是否会发生死锁，提出解决方案用银行家算法判断系统是否处于安全状态，是否应该同意一个进程的资源申请3处理机调度的基本概念及比较高级调度中级调度低级调度4高级调度(HighScheduling)在每次执行作业调度时，都须做出以下两个决定1)接纳多少个作业2)接纳哪些作业5中级调度中级调度又称中程调度(Medium-TermScheduling)。引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度6低级调度(LowLevelScheduling)在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。7常见的调度算法总结与比较先来先服务和短作业(进程)优先调度算法最简单的一种调度算法8短作业(进程)优先调度算法SJ(P)F(1)该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。9高优先权优先调度算法10要求服务时间要求服务时间等待时间优先权优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：要求服务时间响应时间要求服务时间要求服务时间等待时间优先权高响应比优先调度算法(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。111.在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。12多级反馈队列调度算法应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。图3-5是多级反馈队列算法的示意。13产生死锁的必要条件(1)互斥条件(2)请求和保持条件(3)不剥夺条件(4)环路等待条件处理死锁的基本方法(1)预防死锁。(2)避免死锁。(3)检测死锁。(4)解除死锁。4.银行家算法之例假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-15T0时刻的资源分配表(1)T0时刻的安全性：图3-16T0时刻的安全序列(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图3-15中的圆括号所示。④再利用安全性算法检查此时系统是否安全。图3-17P1申请资源时的安全性检查(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)Available(2,3,0)，让P4等待。(4)P0请求资源：P0发出请求向量Requst0(0，2，0)，①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。图3-18为P0分配资源后的有关资源数据经典例题解析【例1】一种既有利于短小作业又兼顾到长作业的作业调度算法是_____。【中科院2004】A．先来先服务B．轮转C．最高响应比优先D．均衡调度解析：最高响应比优先是一种既有利于短小作业又兼顾长作业的调度算法。22【例2】在操作系统中引入并发可以提高系统效率。若有两个程序A和B，A程序执行时所做的工作按次序需要用CPU：10秒；DEV1：5秒；CPU：5秒；DEV2：10秒；CPU：10秒。B程序执行时所做的工作按次序需要用DEVl：10秒；CPU：10秒；PEV2：5秒；CPU：5秒；DEV2：10秒。如果在顺序环境下执行A、B两个程序，CPU的利用率为①；如果在并发环境下执行A，B两个程序，假设A程序先执行，则CPiJ的利用率为②【中科院2006】A．30％B．40％C．50％D．60％E．99%F．89％G．79％H．69％解析：CPU利用率=CPU运转时间／程序运行总时间。答案CF23【例3】若系统中有5台同类设备，有多个进程均需要使用2台，则至多允许____个进程参与竞争，才不会发生死锁。【上海交大2007】A．1B．2C．3D．4解析：设线程数为x，首先使得一个线程得以满足，其他线程只申请到一个资源，为2+x-1＝5，得4。D24第四章存储器管理25重难点导航内部碎片和外部碎片逻辑地址与物理地址内存分配策略分页的地址变换，页表的使用分页和分段的优缺点虚拟存储器概念页面置换算法和缺页率26分页的地址结构分页地址中的地址结构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：MODLAdLAINTP][地址变换机构1.基本的地址变换机构图4-12分页系统的地址变换机构页表寄存器页表始址页表长度＞页号(3)页内地址＋逻辑地址L越界中断1块号b页表页号012物理地址3图4-13具有快表的地址变换机构页表寄存器页表始址页表长度＞页号页内地址＋逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址两级页表(Two-LevelPageTable)逻辑地址结构可描述如下：图4-15具有两级页表的地址变换机构外部页号P1P2外部页内地址页内地址d逻辑地址＋外部页表寄存器外部页表＋db页表页表物理地址……分段系统的基本原理分段分段地址中的地址具有如下结构：段号段内地址3116150图4-16利用段表实现地址映射作业空间(MAIN)＝0030K(X)＝1020K(D)＝2015K(S)＝3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)＝030K(X)＝120K(D)＝215K(S)＝310K040K80K120K150K段表内存空间0123控制寄存器段表始址段表长度＞2100＋段号S越界1K段长600段号01236K4K5002008K9200基址位移量W＋82928K82928692主存物理地址有效地址图4-17分段系统的地址变换过程3.地址变换机构(1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。(2)页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。(3)分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。段页式存储管理方式1.基本原理图4-20作业地址空间和地址结构04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号(P)段内地址(W)(b)主程序段图4-21利用段表和页表实现地址映射段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器地址变换过程图4-22段页式系统中的地址变换机构段表寄存器段表始址段表长度＞段号S页号P＋段超长段表0123＋页内地址页表0123b块号b块内地址页表始址页表长度请求分页存储管理方式请求分页中的硬件支持页表机制页号物理块号状态位P访问字段A修改位M外存地址内存分配策略和分配算法最小物理块数的确定是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。页面置换算法1.最佳(Optimal)最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。引用率70770170122010320304243230321201201770101页框(物理块）2