第4-5章作业
1、“整体对换从逻辑上也扩充了内存，因此也实现了虚拟存储器的功能”这种说法是否正确？请说明理由。
答：上述说明法是错误的。整体对换将内存中暂时不用的某个程序及其数据换出至外存，腾出足够的内存空间以装入在外存中的、具备运行条件的进程所对应的程序和数据。虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统，是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统，它的实现必须建立在离散分配的基础上。虽然整体对换和虚拟存储器均能从逻辑上扩充内存空间，但整体对换不具备离散性。实际上，在具有整体对换功能的系统中，进程的大小仍受到实际内存容量的限制。
2、什么叫静态重定位，什么叫动态重定位，它们分别与何种装入方式相对应？
答：把作业装入内存中随即进行地址变换的方式称为静态重定位，在作业执行期间，当访问到指令或数据时才进行地址变换的方式称为动态重定位。它们分别和可重定位 、 动态运行时装入方式相对应。
3、虚拟存储器有哪些特征？其中最本质的特征是什么？
答：虚拟存储器具有离散性、多次性、对换性和虚拟性的特征。其中最本质的特征是离散性，在此基础上又形成了多次性和对换性，所表现出来的最重要的特征是虚拟性。
4、某系统采用页式存储管理策略，拥有逻辑空间32页，每页为2KB，拥有物理空间1MB。1）写出逻辑地址的格式。
2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？ 3）如果物理空间减少一半，页表结构应相应作怎样的改变？
答：1）该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位来描述，而每页为2KB，
因此，页内地址必须用11位来描述。这样，可得到它的逻辑地址格式如下： 15 11 10 0 页内地址 页号
2）每个进程最多有32个页面，因此，进程的页表项最多为32项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块号。1MB的物理空间可分成29个内存块，故每个页表项至少有9位。
3）如果物理空间减少一半，则页表中项表项数仍不变，但每项的长度可减少1位。
5、对于下表所示的段表，请将逻辑地址（0，137）、（1，4000）、（2，3600）、（5，230）转换成物理地址。
段 表
段号 0 1 2 3 4 内存地址 50K 60K 70K 120K 150K 段长 10KB 3KB 5KB 8KB 4KB 答：[0,137]：50KB+137=51337；
[1，4000]：段内地址越界；
[2，3600]：70KB+3600=75280； [5，230]：段号越界。
6、在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？
答：请求分页的页表项如下：页号、物理块号、状态位P、访问字段A、修改位M、外存地址。
? 状态位P：指示该页是否已调入内存；
? 访问字段A：记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间
未被访问，供选择换出页面时参考；
? 修改位M：该页在调入内存后是否被修改过，供置换页面时参考； ? 外存起址：指出该页在外存上的地址，供调入该页时参考。
7、在一个请求分页系统中，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时，访问过程中所发生的缺页次数和缺页率，并比较所得结果。 （选做括号内的内容：根据本题的结果，请查找资料，说明什么是Belady现象，在哪种置换算法中会产生Belady现象，为什么？）
答：1）使用OPT算法时，访问过程中发生缺页的情况为：当M=3时，缺页次数为7，缺
页率为7/12；当M=4时，缺页次数为6，缺页率为6/12。可见，增加分配给作业的内存块数，可减少缺页次数，从而降低缺页率。
访问过程中的缺页情况（M=3，OPT算法）
页面引用 物 理 块 缺页 置换 页面引用 物 理 块 缺页 置换 4 4 × 4 4 × 3 4 3 × 3 4 3 × 2 4 3 2 × 2 4 3 2 × 1 4 3 1 × √ 1 4 3 2 1 × 4 4 3 3 5 5 3 4 × √ 5 4 3 2 5 × √ 4 4 3 3 2 5 2 4 × √ 2 1 5 2 1 × √ 1 1 3 2 5 × √ 5 5 访问过程中的缺页情况（M=4，OPT算法） 2）使用LRU算法时，访问过程中发生缺页的情况为：当M=3时，缺页次数为10，缺页率为10/12；当M=4时，缺页次数为8，缺页率为8/12。可见，增加分配给作业的内存块数，可减少缺页次数，从而降低缺页率。
访问过程中的缺页情况（M=3，LRU算法） 页面引用 物 理 块 缺页 4 4 × 3 4 3 × 2 4 3 2 × 1 1 3 2 × 4 1 4 2 × 3 1 4 3 × 5 5 3 4 × 4 3 2 2 3 4 × 1 2 3 1 × 5 2 5 1 × 置换 页面引用 物 理 块 缺页 置换 4 4 × 3 4 3 × 2 4 3 2 × √ 1 4 3 2 1 × √ 4 √ 3 √ 5 4 3 5 1 × √ 4 3 √ 2 4 3 5 2 × √ √ 1 4 3 1 2 × √ √ 5 5 3 1 2 × √ 访问过程中的缺页情况（M=4，LRU算法） 3）使用FIFO算法时，访问过程中发生缺页的情况为：当M=3时，缺页次数为9，缺页率为9/12；当M=4时，缺页次数为10，缺页率为10/12。可见，增加分配给作业的内存块数，反而增加了缺页次数，提高了缺页率，这种现象被称做Belady现象。
访问过程中的缺页情况（M=3，FIFO算法） 页面引用 物 理 块 缺页 置换 页面引用 物 理 块 缺页 置换 4 4 × 4 4 × 3 4 3 × 3 4 3 × 2 4 3 2 × 2 4 3 2 × 1 1 3 2 × √ 1 4 3 2 1 × 4 1 4 2 × √ 4 3 1 4 3 × √ 3 5 5 3 2 1 × √ 5 5 4 3 × √ 4 5 4 2 1 × √ 4 3 3 5 4 3 1 × √ 2 5 2 3 × √ 2 5 4 3 2 × √ 1 5 2 1 × √ 1 1 4 3 2 × √ 5 5 1 5 3 2 × √ 访问过程中的缺页情况（M=3，FIFO算法）
8、现有一请求调页系统，页表保存在寄存器中。若一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，则处理一个缺页中断需要20ms。内存存取时间为1us，访问页表的时间可忽略不计。假定70%被替换的页被修改过，为保证有效存取时间不超过2us，可接受的最大缺页率是什么？
答：如果用p表示缺页率，则有效访问时间不超过2us可表示为 （1-p）×1us+p×(0.7×20ms+0.3×8ms+1us)≦2us， 因此可计算出：p≦1/16400≈0.00006， 即可接受的最大缺页率为0.00006。
操作系统第4-5章作业2015讲解
