第二章 习题解答.ppt

某系统采用动态分区存储管理技术 某时刻内存中有三个空闲区 它们的首地址和大小分别为 空闲区1 100KB 10KB 空闲区2 200KB 30KB 空闲区3 300KB 15KB 1 画出该时刻内存分配图 2 用首次适应法和最佳适应法画出此时的空闲分区链 3 有如下作业序列 作业1需求15KB 作业2需求16KB 作业3需求10KB 用哪种算法能将该作业序列装入内存 给出简要分配过程 100K 1 110K 200K 230K 300K 315K 2 首次适应法 最佳适应法 3 首次适应法 最佳适应法 若在一分页存储管理系统中 某作业的页表如下所示 已知页面大小为1024字节 试将逻辑地址1011 2148 3000 5012转化为相应的物理地址 注 此处块号即为页面号 为了描述方便 设页号为P 页内位移为W 逻辑地址为A 内存地址为M 页面大小为L 则P int A L W AmodL对于逻辑地址1011P int 1011 1024 0W 1011mod1024 1011A 1101 0 1101 查页表第0页在第2块 所以物理地址为M 1024 2 1101 3059 对于逻辑地址为2148P 2148 1024 2W 2148mod1024 100A 2148 2 100 查页表第2页在第1块 所以物理地址为M 1024 1 100 1124 对于逻辑地址为3000P 3000 1024 2W 3000mod1024 952A 3000 2 952 查页表第2页在第1块 所以物理地址为M 1024 1 952 1976对于逻辑地址5012P 5012 1024 4W 5012mod1024 916因页号超过页表长度 该逻辑地址非法 某段式存储管理系统中 有一作业的段表 SMT 如下表所示 求逻辑地址 0 65 1 55 2 90 3 20 对应的主存地址 按十进制 其中方括号中的第一个元素为段号 第二个元素为段内地址 逻辑地址 0 65 对应的主存地址为600 65 665 逻辑地址 1 55 因段内地址超过段长 所以产生段地址越界中断 逻辑地址 2 90 对应的主存地址为1000 90 1090 逻辑地址 3 20 因为状态位为0 即该段在辅存中 所以产生缺段中断 考虑一个由8个页面 每页1K字节组成的逻辑空间 把它映射到由32个物理块组成的存储器 问 1 有效的逻辑地址有多少位 2 有效的物理地址有多少位 解此题的关键是要知道在分页管理中 页 和 块 是一样大小的 这样才知道物理存储器是32K 1 逻辑地址有13位 2 物理地址有15位 考虑一个分页存储器 其页表存放在内存 1 若内存的存取周期为0 6us 则CPU从内存取一条指令 或一个操作数 需多少时间 2 若使用快表且快表的命中率为75 则内存的平均存取周期为多少 1 因为页表放在内存 故取一条指令 或一个操作数 须访问两次内存 所以需0 6us 2 1 2us的时间 2 这里假定访问快表的时间可以忽略不计 命中快表时取数只要一次访存 故此时的平均存取周期为0 6us 0 75 1 2us 1 0 75 0 75us关键 要知道访问快表的时间可以忽略不计和平均存取周期的概念 有一计算机系统 内存容量为512K 辅存容量为2G 逻辑地址形式为 段号29 20bit段内地址19 0bit求其虚拟存储器的实际容量 虚拟内存的实际大小由系统的逻辑地址结构 主存辅存容量共同决定 虚拟内存容量的理论值是210 220 1G 最大段内地址为220 1M 远大于内存容量 其段长超过512K的内存容量 故最大实际段长为512k而不是1M 所以可计算虚拟存储容量为210 512K 210 0 5M 0 5G 0 5G 2G 因此虚拟存储器的实际容量是0 5G 有一计算机系统 内存容量为512K 辅存容量为2G 逻辑地址形式为 段号29 20bit段内地址19 0bit 求其虚拟存储器的实际容量 在分页存储管理系统中 存取一次内存的时间是8us 查询一次快表的时间是1us 缺页中断的时间是20us 假设页表的查询与快表的查询同时进行 当查询页表时 如果该页在内存但快表中没有页表项 系统将自动把该页页表项送入快表 求对某一数据进行一次存取可能需要的时间 现连续对同一页面上的数据进行4次连续读取 求每次读取数据可能需要的时间 当系统对数据进行存取时 有3种可能性 1 所存取的数据的页面在内存 其页表项已经存储到快表 此时存取数据的时间是 查询快表的时间 存取内存数据的时间 1us 8us 9us2 所存取的数据的页面在内存 但是其页表项没有存储到快表 没有命中快表 此时存取数据的时间是 查询页表的时间 存取内存数据的时间 8us 8us 16us3 所存取的数据的页面不在内存 发生缺页中断 此时存取数据的时间是 查询页表的时间 缺页中断的时间 查询页表的时间 存取内存数据的时间 8us 20us 8us 8us 44us 当对某一数据进行4次连续读取时 第1次可能的时间为 1us 8us 9us 8us 8us 16us 8us 20us 8us 8us 44us 第2次时 对应页面的页表项已经交换到快表中 因为存取是连续的 不存在页面被淘汰的可能性 所以第2次 第3次 第4次的存取时间是一样的 消耗的时间为1us 8us 9us 某虚拟存储器的用户空间共有32个页面 每页1KB 主存16KB 试问 1 逻辑地址的有效位是多少 2 物理地址需要多少位 3 假定某时刻系统用户的第0 1 2 3页分别分配的物理块号为5 10 4 7 试将虚地址0A5C和093C变换为物理地址 1 程序空间的大小为32KB 因此逻辑地址的有效位数是15位 2 内存储空间的大小是16KB 因此物理地址至少需要14位 3 当页面为1KB时 虚地址0A5C表示页号为00010 页内地址是1001011100 该页在内存的第4块 即块号为0100 因此0A5C的物理地址是01001001011100 即125CH 4 用同样的方法可以求得 093C的物理地址是113CH 考虑一个有快表的请求分页系统 设内存的读写周期为1us 内外存之间传送一个页面的平均时间为5ms 快表的命中率为80 页面失效率为10 求内存的有效存取时间 内存的有效存取时间EAT EfficentAccessTime 也叫平均存取时间AAT AverageAccessTime 其计算公式如下 EAT 命中快表时的存取时间 快表命中率 命中内存时的存取时间 内存命中率 页面失效时的存取时间 页面失效率将题中的已知条件代入可得EAT 1us 80 2us 10 5000us 2us 10 0 8us 0 2us 500 2us 501 2us说明 解此题除了要了解 有效存取时间 的计算公式外 还应了解在命中快表 命中内存和页面失效三种情况下存取时间的计算方法 特别是 当页面失效时 除了页面传送时间 还应加上2次访问内存的时间 因为页面失效的前提是不命中快表 对于一个使用快表的页式虚存 设快表的命中率为70 内存的存取周期为1us 缺页处理时 若内存有可用空间或被置换的页面在内存未被修改过 则处理一个缺页中断需8ms 否则需20ms 假定被置换的页面60 是属于后一种情况 则为了保证有效存取时间不超过2us 问可接受的最大缺页率是多少 设可接受的最大缺页率为p 则有1us 0 7 2us 1 0 7 p 0 4 8ms 0 6 20ms p 2us即0 7 0 6 2p 3200p 1200p 215198p 0 7p 0 000046 在某分页虚存系统中 测得CPU和磁盘的利用率如下 试指出每种情况下的问题和措施 1 CPU的利用率为15 盘利用率为95 2 CPU的利用率为88 盘利用率为3 3 CPU的利用率为13 盘利用率为5 1 可能已出现了抖动现象 应减少系统的进程数 2 系统比较正常 可考虑适当增加进程数以提高资源利用率 3 CPU和磁盘的利用率都较低 必须增加并发进程数 在分页存储管理系统中 存取一次内存的时间是8us 查询一次快表的时间是1us 缺页中断的时间是20us 假设页表的查询与快表的查询同时进行 当查询页表时 如果该页在内存但快表中没有页表项 系统将自动把该页页表项送入快表 一个作业最多可保留3个页面在内存 现开始执行一作业 系统连续对作业的 5 7 6 4 2各页面的数据进行1次存取 如分别采用FIFO算法和最优页面置换算法 求每种算法下存取这些数据需要的总时间 LRU第2页面 20 8 3第4页面 20 8 3第5页面 20 8 3第2页面 8 1第7页面 20 8 3第6页面 20 8 3第4页面 20 8 3第8页面 20 8 3因此总的时间是 20 8 3 7 8 1 OPT第2页面 20 8 3第4页面 20 8 3第5页面 20 8 3第2页面 8 1第7页面 20 8 3第6页面 20 8 3第4页面 8 1第8页面 8 1因此总的时间是 20 8 3 5 8 1 3 为什么要引入逻辑地址 1 使用物理地址的程序只有装入程序所规定的内存空间上才能正确执行 如果程序所规定内存空间不空闲或不存在 程序都无法执行 2 使用物理地址编程意味着由程序员分配内存空间 程序员无法事先协商每个程序所应占的内存空间的位置 这在多道程序系统中 势必造成程序所占内存空间的相互冲突 3 在多道程序系统中 系统无法保证程序执行时 它所需的内存空间都空闲 基于上述原因 必须引入一个统一的 在编程时使用的地址 它能够在程序执行时根据所分配的内存空间将其转换为对应的物理地址 这个地址就是逻辑地址 逻辑地址的引入为内存的共享 保护和扩充提供方便 试比较静态重定位和动态重定位 重定位 实际上指的是相互联系的两件事情 一是确定一个待执行程序在内存中的位置 二是将程序中的逻辑地址转换成物理地址 后一件事情是由前一件事情决定的 试比较静态重定位和动态重定位 静态重定位的特点实现容易 无需增加硬件地址变换机构 一般要求为每个程序分配一个连续的存储区 在重定位过程中 装入内存的代码发生了改变 在程序执行期间不再发生地址的变换 在程序执行期间不能移动 且难以做到程序和数据的共享 其内存利用率低 动态重定位特点 实现要依靠硬件地址变换机构 且存储管理软件算法较复杂 程序代码是按原样装入内存的 在重定位的过程中也不发生变化 重定位产生的物理地址存放在内存地址寄存器中 同一代码中的同一逻辑地址 每执行一次都要重定位一次 只要改变基地址 就可以很容易地实现代码在内存中的移动 动态重定位可以将程序分配到不连续的存储区中 所以 尽管动态重定位需要硬件支持 但支持程序浮动 便于利用零散的内存空间 利于实现信息共享和虚拟存储 所以现代计算机大都采用动态重定位 另外 实现虚拟存储器需要动态重定位技术的支持 在实存管理上 管理方法主要分成哪两种类型 实存管理的方法主要分成 1 连续 用户程序需要占用连续的内存空间 如分区存储管理 2 离散 用户程序不需要占用连续的内存空间 如分页 分段 段页等管理 一个用户程序在内存可能是不连续的 如果它有不只一页或一段的话 为什么在分页和分段管理下取一条指令或一个操作数通常需两次访存 如何解决这一问题 因为用于地址变换的页表或段表也是存放在内存的 为了将CPU给出的逻辑地址变成物理地址 首先就要访问内存的页表和段表 然后 根据形成的物理地址再取指令或数据 这就要两次访存 解决这一问题的办法是提供一个称之为 快表 的硬件 用以存放当前运行进程的页表或段表的部分内容 快表 的访问时间很快 因此可以节约访问页表和段表的时间 存储器访问具有时间和空间的 局部性 因此快表的命中率一般可达70 到90 页表和段表是在系统执行过程中 每时每刻都需要访问的 因此 访问时间的微小缩短 其累计节约的时间却可以达到很大 段页式存储系统中 为了获得一条指令或数据 需几次访问内存 在段页式系统中 为了获得一条指令或数据 需三次访问内存 第一次访问 是访问内存中的段表 从中取得页表始址 第二次访问 是访问内存中的页表 从中取出逻辑页面对应的内存物理块号 并将该块号与页内地址一起形成指令或数据的物理地址 第三次访问 才是真正从第二次访问所得的地址中 取出指令或数据 为什么分段管理下的程序共享和保护比分页管理更有意义 因为段是一个有意义的逻辑整体 如主程序 子程序 数据表格 工作空间等 就如书本上的一章或一个自然段 而页只是一个物理尺寸 不一定有完整的意义 如书本上的一页 程序共享当然希望被共享的对象是一个有意义的整体 如一个子程序 至于程序保护 指的是每个进程都应按所拥有的存取权访问不同的程序 而存取权 R W E等 当然对一个有完整意义的对象才更有意义 所以就共享和保护而言 分段管理比分页管理更有意义 说明什么是置换算法的异常现象 解页面置换算法的异常现象 也叫Belady异常 是在局部置换前提下的一种现象 所谓局部置换 指的是当一进程创建时 分给其一定数量的页面 例如8页 然后 在运行过程中 若该进程需调入新页且须置换一个页面时 则只能置换其自己的一个页面而不能置换别的进程的页面 页面置换的异常现象 是指在一定置换算法和一定页面走向下 分给进程的页面数增多其页面失效率反而增加这样一种情况 这种异常 只在一定的算法和一定的页面走向下才会出现 许多算法 如OPT和LRU 在任何情况下都不会有异常现象 LRU之所以不会有 异常 是因为最近的过去使用的n个页面一定在最近的过去使用的n 1个页面之中 什么是抖动现象 如何消除这种现象 抖动现象 是在虚存管理下 用于页面 在内 外存之间 对换的时间比程序的有效运行时间还要多的这样一种现象 它可以是一进程内部的局部性抖动 也可以是整个系统的全局性抖动 造成这种情况固然与置换算法和页面走向有关 但其根本原因是多道系统内的进程数太多 从而分给每个进程的页面数太少 因此 解决这一问题的最有效的办法是减少系统内的进程数 Denning于1980年提出了 L S准则 即调整系统内的进程数 使得产生缺页的平均间隔时间 L 等于系统处理进程缺页的平均时间 S 理论和实践表明 此时的CPU利用率最高 在内存管理中 内零头 和 外零头 各指的是什么 在固定式分区分配 可变式分区分配 页式虚拟存储系统 段式虚拟存储系统中 各会存在何种零头 为什么 内零头 又称内部碎片 给一个作业分配的存储块长度为n 在其中存储的作业长度为m 则剩下的长度为 n m 的空间 成为该存储块的内部碎片 若存储块长度为n 在该系统所采用的调度算法下 较长时间内无法选出一道长度不超过该块的作业 则称该块为外零头 外部碎片 在固定式分区分配中两种零头均会存在 因为空间划分是固定的 无论作业长短 存储单元均不会随之变化 若作业短而存储块长则产生内零头 若作业长而存储块短则产生外零头 在可变式分区分配中只有外零头而无内零头 因为空间划分是依作业长度进行的 是要多少给多少 但剩下的部分太短而无法再分 则称为外零头 页式虚存中会存在内零头而无外零头 因存储空间与作业均分为等长单元 所以不存在无法分配的单元 但作业长度并不刚好为页面大小的整数倍 因此在最后一页会有剩余空间 即为内零头 段式虚存中会存在外零头而无内零头 因段式的空间划分类似于可变分区分配 根据段长分配 要多少给多少 但会剩余小空间无法分配 则为外零头 覆盖技术的基