计算机操作系统(第三版)汤小丹第4章.doc

《计算机操作系统(第三版)汤小丹第4章.doc》由会员分享，可在线阅读，更多相关《计算机操作系统(第三版)汤小丹第4章.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统原理 教材重点习题答案 制作：信息工程学院 操作系统课程组注意：1)“本章要点”部分，用红字标注的不是期末考试出题范围。2)“习题部分”用蓝字标注的是重点习题，期末考试50%的题目是这些习题的原题。红字标注的习题期末考试不考，仅供考研的同学参考。3）大部分习题答案只给出要点，同学们可以自行适当补充，但一定要简明扼要。4）如“本章要点”部分用红字标注的非考试内容，在“习题”部分有相关的重点习题，则对该部分内容只需做该习题即可。-第四章 存储器管理 要点4.1 存储器的层次结构理解P116图4-1的存储器层次结构，知道这种结构从经济上考虑，具有好的性能/价格比。 了解P117-118高速缓

2、存CACHE和磁盘缓存，知道它们使用的淘汰算法与虚拟内存的页面置换算法是基本相同的。4.2 程序的装入和链接 这一小节的内容是一些重要的专业常识。应了解本小节介绍的各种装入和链接方法，要求结合Windows操作系统及C语言的实际去理解上述装入和链接方法（联系实际部分可上网查询）。 4.3 连续分配方式 通用操作系统大都不用连续分配方式，有些嵌入式OS可能使用这种分配方式。 这一小节只需阅读P121-124即可。4.4 基本分页存储管理方式 这是本章最重要的一小节，要求全读。重点理解页面、物理块、页表、页表的访存、物理地址、逻辑地址、快表（TLB）等概念及相互关系。4.5 基本分段存储管理方式

3、阅读4.5.1，知道为什么要分段。阅读4.5.2 知道分段的原理。考研的同学要知道段表、地址变换，知道分段和分页的主要区别。 阅读4.5.3 知道分段有利于信息共享，知道“纯代码”的概念。 阅读4.5.4 知道什么是段页式存储。 需要补充说明的是：教材说过，分段方便编程，主要是指方便汇编语言程序员，和设计高级语言编译器的程序员。对使用高级语言进行应用编程的程序员来说，段是透明的，一般不能用高级语言代码去操作段。 4.6 虚拟存储器的基本概念 这一小节重点是局部性原理。其它内容泛读即可。4.7 请求分页存储管理方式 掌握请求分页的页表、什么是缺页中断。其它内容泛读即可。 4.8 页面置换算法 熟

4、练LRU算法，知道该算法同样也适合于在本章介绍的CPU CACHE、快表、磁盘缓存的置换。其它内容泛读即可。 4.9 请求分段存储管理 考研的同学也可以不看。本章最后提示：实际的通用操作系统，一般使用请求分页（4.7小节）+基本分段（4.5小节）相结合的存储管理方式。请求分页是离散分配（节约内存）且有虚拟内存（扩展性好），基本分段是连续分配（有P136介绍的几个优点，教材认为基本分段也是离散分配似有不妥）。本章习题1 为什么要配备层次式存储器答：不同视角有不同答案。可以从经济上考虑，这种内外搭配、快慢结合的存储体系有利于实现最佳性能价格比。2. 可采用哪几种方式将程序装入内存?它们分别适用于何

5、种场合?答：【P118 4.2.1】对于高级语言程序，首先由编译程序将用户源代码编译成若干目标模块，再由链接程序将编译后形成的目标模块和所需的库函数链接在一起，组成一个装入模块。装入模块的文件格式是与操作系统有关的，比如Windows平台下C/C+生成的.exe文件，其格式只能被Windows操作系统解读。再由装入程序将装入模块装入内存。1）装入模块的方式有：绝对装入方式，可重定位方式和动态运行时装入方式；2）绝对装入方式主要适用于单道程序环境下；但在Windows下的.com程序也是绝对装入方式的，这与这些程序对硬件的访问、中断入口等有关。3）可重定位方式适用于多道程序环境下，比如Windo

6、ws下的.exe程序.4）动态运行时装入方式也适用于多道程序环境下，比如Windows下的.dll程序。 3. 何谓静态链接？何谓装入时动态链接和运行时的动态链接?答：【P120 4.2.2】a. 静态链接是指事先进行链接形成一个完整的装入模块，以后不再拆开的链接方-式；Windows下用C语言编写的.exe程序就是这种链接方式。b. 装入时动态链接是指目标模块在装入内存时，边装入边链接的链接方式；Windows下的.dll程序有些是这种链接方式。c. 运行时的动态链接是将某些目标模块的链接推迟到执行时才进行；Windows下的.dll程序有些是这种链接方式。附注：对于Windows下.exe

7、和.dll更多的知识，可以上网查询。4. 在进行程序链接时，应完成哪些工作?答：P118。主要是将多个源程序生成的多个目标模块、及它们需要的函数库链接起来。静态链接和动态链接的链接时间和方式有所不同，对该问题更深入的了解要学习“编译原理”这门课。5A. 在动态分区分配方式中，可利用哪些分区分配算法?答：P123-124a. 首次适应算法；b. 循环首次适应算法；c. 最佳适应算法. 5. 在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链?答：P123 图4.6。主要使用双向链表，双向链表的优点可参考“数据结构”。操作系统底层数据结构往往借助于链表，在课本上经常可见。 6. 为什么要引入

8、动态重定位?如何实现?答：P127-128。连续分配方式容易造成内存很多小分区（零头）无法使用，有必要进行“紧凑”，而这又会造成程序的物理地址改变，因此要进行动态重定位，即重新计算逻辑地址到物理地址的映射。实现方法是：为了不因重定位而影响效率，需要硬件支持，可在CPU中增加一个重定位寄存器，用它来存放程序在内存中的起始物理地址，程序在执行时，真正访问的内存地址是逻辑地址与重定位寄存器中的物理地址相加而形成的。7. 在采用首次适应算法回收内存时，可能出现哪几种情况?应怎样处理这些情况?答：P125。该题考研的同学也可以不做。8 令buddyK(x)表示大小为2的k次方、地址为x的块的伙伴系统地址

9、，试写出buddyK(x)通用表达式?答：P126。考研的同学可以关注一下。Buddy System是一种经典的内存管理算法，在Unix和Linux操作系统中都有用到， 其作用是减少存储空间中的空洞, 减少碎片, 增加利用率。在有的“数据结构”课本中有算法介绍。 这道题我看不懂其题意，大概是分配内存时x要找的空闲块是: pow(2,k-1)=buddyK(x)=pow(2,k) / pow是乘方函数Buddy System是一种连续的内存管理方法，可以结合离散的分页分配方法使用，有利于为进程分配连续的物理块，以提高分页法的效率和程序的局部性。9 分区存储管理中常用那些管理策略？比较它们的优缺点

10、？答:P121-128。主要有1）静态分配（单一连续分配，固定分区分配），优点是简单易行，缺点是内存利用率高。2）动态分配（动态分区分配，伙伴堆），与静态分配相比，稍复杂，但能提高内存利用率。但上述两类（连续）内存存储管理策略的内存利用率都不够好，所以有了离散的分页存储。10. 在系统中引入对换后带有哪些好处?答：P129。能将内存中暂时不运行的进程或暂时不用的程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程或进程所需的程序和数据换入内存，从而大大地提高了内存的利用率。对换技术也是虚拟内存技术的前身。11 为实现对换，系统应具备哪几方面功能?答：P129。对换空间的管理；进

11、程的换出/换入。 12 在以进程为单位进行对换时，每次是否都将整个进程换出?为什么?答：P129。是，因为被换出的进程处于阻塞态且优先级最低，暂时不能被CPU调度。对换，就是第3章讲的“进程中级调度” 13为实现分页存储管理，需要哪些硬件支持?答：分页是离散存储，效率较低，必需借助硬件提高效率。主要硬件有页表寄存器、联想寄存器（TLB,快表）、地址变换机构。这些硬件在4.4小节有零散介绍。14 较详细的说明引入分段存储管理是为了满足用户哪几方面的需要？答：P136。15 在具有快表的段页式存储管理方式中，如何实现地址变换?答：【P140-141地址变换过程】注意这一小节讲的“三次访存。简单的说

12、，是先查段表，从段表中找到该段的页表，再查页表，找到对应的物理块号，最后利用物理块号+页内地址生成最终的物理地址。16 为什么说分段系统较之分页系统更易于实现信息共享和保护?答：因为分段提供的是用户视角，用户可以把需要保护的数据或代码分别放在不同段中，然后再段表中加上保护或共享属性即可。而分页主要考虑最大限度的使用内存，需要保护或共享的数据或代码离散存放在不同页面，很难按用户视角管理。17 分页和分段存储管理有何区别?答：P138。18 试全面比较连续分配和离散分配方式.答：4.3小节介绍的连续分配主要有单一连续分配、静态分区分配、动态分区分配等，优点是简单高效，缺点是内存利用率不高；而以分页

13、为代表的离散分配方式正好与之相反。这道题在期末考试中不需要“全面比较”，突出要点简单比较即可。19 虚拟存储器有哪些特征？其中最本质的特征是什么?答：P14420 实现虚拟存储器要那些硬件支持?答：除了第13题需要的硬件外，还需要较大容量的外存和缺段中断机构。21 实现虚拟内存需要那几个关键技术？答：除了第20题提到的硬件支持，软件方面还需要好的淘汰算法（比如LRU，但LRU效率也不太好，本身也要必要的硬件支持）22 在请求分页系统中，其页表项中包含那些数据项? 它们的作用是什么?答：P145。教材给出的请求分页页表只是参考性的。23 在请求分页系统中，应从何处将所需页面调入内存?答：P149

14、。1）外存分为文件区和对换区（对换区可认为就是以页面形式组织的虚拟内存区），若系统有足够的对换区空间，可在进程运行前，将与该进程有关的文件拷贝到对换区，需要时从对换区调入；2）若系统缺少足够的对换区空间，则凡是不会被修改的文件，可直接从文件区调入，需换出时，便须调到对换区，以后需要时再从对换区调入. 3）UBIX方式。这道题只知道1）就可以了。24在请求分页系统中，常采用哪几种页面置换算法?答:a. 最佳置换算法；理论上是最佳的，但不实用。b. 先进先出算法；缺页率太高，不使用。c. 最近最久未使用LRU置换算法；最常用的算法d. Clock置换算法; LRU的效率不太好，需要硬件支持。Clo

15、ck是LRU的近似，不需要硬件太多支持。25 在请求分页系统中，通常采用那种页面分配方式?为什么?答：P147-1481）在请求分页系统中，有固定和可变分配两种分配方式；2） 采用固定分配方式是基于进程的类型(交互型)或根据程序员，系统管理员的建议，为每个进程分配一固定页数的内存空间，在整个运行期间不再改变；3）采用可变分配方式有全局置换和局部置换两种，前者易于实现，后者效率高. 26 在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，当分配给该作业的物理块数M分别为3和4时，试计算访问过程中所发生的缺页次数和缺页率?比较

16、所得结果?答：这道题很重要，要按照P150-152的解题方法，对FIFO, LRU和最佳算法各做一遍。 27 实现LRU算法所需的硬件支持是什么?答:P152a. 寄存器，用于记录某进程在内存中各页的使用情况；b. 栈，用于保存当前使用的各个页面的页面号.28 试说明简单的和改进型Clock置换算法的基本原理.答：P153。 29 试说明请求分段系统中的缺页中断处理过程?答：P154图4-32。考研的同学不需做这道题。 30 如何实现分段共享?答：P157。考研的同学只需知道分段易于共享就可以了，不需做这道题。补充习题1. 一个计算机系统的虚拟存储器，其最大容量和实际容量分别由什么决定?答：a

17、. 最大容量由系统寻址能力决定；b. 实际容量由内存决定. 2. 某虚拟存储器的共有32个逻辑页面，每页1KB，主存16KB. 假定某时刻为进程的第0，1，2，3逻辑页分配的物理块号分别为5，10，4，7，试将虚拟地址0A5C和093C变换为物理地址。答：这道题对期末考试和考研都比较重要。首先，我们要知道，分页系统的 逻辑地址=页号+页内偏移量本题存储器的共有32个逻辑页面，意味着需要5位2进制数。每页1KB大小，意味着需要10位2进制数。这样，该系统的 逻辑地址=5位页号+10位页内偏移量a. 将0A5C变换为2进制为: 0000,1010,0101,1100, 后10位是为内偏移量，故页号

18、是10（十进制2），按题意，第2页对应的物理块号为4，物理地址为二进制的000100，1001011100。十六进制的125C;b. 同理，将093C变换为2进制为: 0000,1001,0011,1100，页号也为2，对应的物理块号也为4，此时虚拟地址093C的物理地址为113C. 3 什么是抖动? 产生抖动的原因是什么?答：抖动（颠簸，Thrashing）是考研的一个知识点，教材将其遗漏了。a 抖动就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调出一页程序或数据送磁盘的对换区中，如果算法不适当，刚被换出的页很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页很快又要被访

19、问，因而又需将它调入，如此频繁更换页面，以致花费大量的时间，我们称这种现象为抖动;b 产生抖动的原因是由于CPU的利用率和多道程序度的对立统一矛盾关系引起的，为了提高CPU利用率，可提高多道程序度，但单纯提高多道程序度又会造成缺页率的急剧上升，导致CPU的利用率下降，而系统的调度程序又会为了提高CPU利用率而继续提高多道程序度，形成恶性循环，我们称这时的进程是处于抖动状态。 4 对于四级页表，假定快表TLB的命中率为98%，快表与内存的访问时间分别为20ns和100 ns ，计算其有效访问时间（要求简单解释计算思路）：答：这道题首先要理解，教材提到的一级页表2次访存（第一次访页表、找物理块号、

20、确定物理地址，第二次根据物理地址找操作数或指令），那么4级页表要5次访存。第二要理解，快表TLB存放了最近使用的页表，查找页表时，先在TLB中找，命中后就无需对页表访存了。不命中再对页表访存。这道题的答案是： EAT=98%*（20+100）+2%*（20+4*00+100）=？ ns 当访问快表命中，则由快表可直接访问内存的操作数或指令，故每次访存时间为20ns+100 ns当访问快表不命中，则在内存中找页表，因页表为4级，故页表总计访存4*100=400 ns，再加上访问快表不命中时间20ns和直接访问内存（进行逻辑物理页地址转换）100 ns，故每次通过页表访存时间为400+20+100=520 ns下面是一道相似题目（清华大学2006年考研题，8分）一个三级存储系统，Cache命中率为95%,Cache存取要20ns,内存命中率为80%，内存存取时间为60ns,外存存取要12ms。问:此系统的平均存取时间，要求写出计算过程。答：三级存储为：cache，内存，外存。这道题给出了CACHE的存取时间为20ns，所以无论CACHE是否命中，都要计入20ns。每百次访存95次在CACHE, 无需访问内存，总计95*20ns4次在内存,总计4*(20+60)ns 1次在外存,总计 (20+60)ns+12ms上述三项总计相加,除100即可。