资源描述
会计学1第1页/共49页3第2页/共49页4第3页/共49页5第4页/共49页度6第5页/共49页比较严格的实时系统中，不宜采用这种调度方式。7第6页/共49页8第7页/共49页9第8页/共49页10要求服务时间要求服务时间等待时间优先权优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 要求服务时间响应时间要求服务时间要求服务时间等待时间优先权高响应比优先调度算法高响应比优先调度算法 第9页/共49页n(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。11第10页/共49页计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。12第11页/共49页13第12页/共49页产生死锁的必要条件产生死锁的必要条件 (1)互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (4) 环路等待条件 第13页/共49页处理死锁的基本方法处理死锁的基本方法(1)预防死锁。 (2) 避免死锁。 (3) 检测死锁。 (4) 解除死锁。 第14页/共49页4. 银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 图 3-15 T0时刻的资源分配表 第15页/共49页(1) T0时刻的安全性： 图 3-16 T0时刻的安全序列 第16页/共49页 (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 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。 第17页/共49页图 3-17 P1申请资源时的安全性检查 第18页/共49页 (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 所示。 第19页/共49页图 3-18 为P0分配资源后的有关资源数据 第20页/共49页22第21页/共49页23第22页/共49页24第23页/共49页25第24页/共49页26第25页/共49页分页的地址结构分页的地址结构 分页地址中的地址结构如下： 页号P位移量W3112110 对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： MODLAdLAINTP第26页/共49页地址变换机构地址变换机构 1. 基本的地址变换机构基本的地址变换机构 图 4-12 分页系统的地址变换机构 页表寄存器页表始址页表长度页号(3)页内 地 址逻辑地址L越界中断1块号b页表页号012物理地址3第27页/共49页具有快表的地址变换机构具有快表的地址变换机构 图 4-13 具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内 地 址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址第28页/共49页两级页表两级页表(Two-Level Page Table) 逻辑地址结构可描述如下： 第29页/共49页图 4-15 具有两级页表的地址变换机构 外部页号P1P2外部页内地址 页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址第30页/共49页分段系统的基本原理分段系统的基本原理 分段分段 分段地址中的地址具有如下结构： 段号段内地址31 16 15 0第31页/共49页图 4-16 利用段表实现地址映射 作业空间(MAIN) 0030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段长 基址段号(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表内存空间0123第32页/共49页控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址图 4-17 分段系统的地址变换过程 3. 地址变换机构 第33页/共49页分页和分段的主要区别分页和分段的主要区别 (1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头， 提高内存的利用率。或者说， 分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。 (2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名， 又需给出段内地址。 第34页/共49页段页式存储管理方式段页式存储管理方式 1. 基本原理基本原理 图 4-20 作业地址空间和地址结构 04K8K12K15K16K子 程 序 段04K8K数 据 段04K8K10K12K(a)段 号 (S)段 内 页 号 (P)段 内 地 址 (W)(b)主 程 序 段第35页/共49页图 4-21 利用段表和页表实现地址映射 段号 状态页表大小页表始址0111213041页号 状态存储块#0111213041操作系统主存页表段表段表大小 段表始址段表寄存器第36页/共49页地址变换过程地址变换过程 图 4-22 段页式系统中的地址变换机构 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度第37页/共49页请求分页存储管理方式请求分页存储管理方式 请求分页中的硬件支持请求分页中的硬件支持 页表机制页表机制 页号 物理块号 状态位P 访问字段A 修改位M外存地址 第38页/共49页内存分配策略和分配算法内存分配策略和分配算法 最小物理块数的确定最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、 功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器， 其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。第39页/共49页页面置换算法页面置换算法 最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1. 最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。 第40页/共49页 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：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页框(物理块）203图 4-25 利用最佳页面置换算法时的置换图 第41页/共49页2. 先进先出先进先出(FIFO)页面置换算法页面置换算法 引用率70770170122010323104430230321013201770201页框2304204230230127127011图 4-26 利用FIFO置换算法时的置换图 第42页/共49页最近最久未使用最近最久未使用(LRU)置换算法置换算法 1. LRU(Least Recently Used)置换算法的描述置换算法的描述 图 4-27 LRU页面置换算法 引用率70770170122010320304403230321132201710701页框402432032102第43页/共49页理也是应用了页式管理方案，同样也会产生业内碎片。答案选择B45第44页/共49页调出内存，降低效率，所以才引入了虚拟存储器。C46第45页/共49页47第一级页号（16位）第二级页号（20位）页内地址（12位）第46页/共49页48段号（16位）段内页号（20位）页内地址（12位）第47页/共49页49第48页/共49页
展开阅读全文