2015-2016学年下学期月考
2015-2016学年下学期月考试卷（含答案）
说明
- 原卷标题：华东师范大学软件学院月考试卷（二）（2015—2016 学年第二学期）
一、判断题（15 分，每小题 3 分）
判断下列每句话是否正确，如错误请说明理由。
-
当一个操作系统采用连续内存分配方案时，只可能产生外部碎片。
答案：
错，在相同大小连续内存分配方案中也可能会产生内部碎片。
-
在虚存管理时，采用 LRU 页面替换策略可能发生 Belady 异常（即分配页框越多，缺页率反而越高）。
答案：
错，LRU 和 Optimal 算法都不可能发生 Belady 异常；只有 FIFO 可能发生 Belady 异常。
-
从有效内存访问时间来看，基于转换表缓冲区（TLB）的分页策略一定优于纯分页策略。
答案：
错，如果 TLB 的命中率特别低，基于转换表缓冲区的分页策略可能比纯分页策略要差。
-
在按需分页中，通过安装更快的 CPU 可以改善多道程序程度过高而导致的系统颠簸。
答案：
错，颠簸是由于多道程序程度过高，导致缺页率大幅增加，而 CPU 利用率急剧下降。此时，很多进程在等待 I/O，因此即使安装更快的 CPU 也无助于改善系统颠簸。
-
页表由各个进程自己管理，进程可在用户态对页表进行更新。
答案：
错，首先不是所有的页表都是进程自己管理，如反向页表是操作系统管理的；其次，页表的修改只有在内核态进行更新。
二、单项选择题（15 分，每小题 3 分）
-
采用分段式存储管理的系统中，若地址用 24 位表示，其中 8 位表示段号，则允许每段的最大长度是：
A.
B.
C.
D.
答案：
B
-
使用段页式内存管理，段表和页表都存放在主存中，所有要访问的页面都在主存中。页表项可以缓存在转换表缓冲区（TLB）中。一次内存访问的代价为 ，一次 TLB 访问代价为 。假设 TLB 的命中率为 50%，请问进程对内存的有效访问时间（effective access time）是：
A.
B.
C.
D.
答案：
C（）
对于接下来的 3 个问题，假设某作业访问页面的顺序为 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2，分配给该作业三个内存块。
-
采用 FIFO 页面置换算法会产生 次缺页中断。
A. 7
B. 8
C. 9
D. 10
答案：
C
-
采用 LRU 页面置换算法会产生 次缺页中断。
A. 6
B. 7
C. 8
D. 9
答案：
B
-
采用最优页面（OPT）置换算法会产生 次缺页中断。
A. 5
B. 6
C. 7
D. 8
答案：
B
三、辨析题（30 分，每小题 6 分）
分别解释以下每组的两个名词，并列举他们的区别。
-
内部碎片与外部碎片
答案：
内部碎片：某一区域或某一页中，未被占据其位置的作业所使用的区域。直到作业完成，释放页或区域，这个空间才能被系统所利用。
外部碎片：还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。
区别：外部碎片不属于任何一个进程，如果不使用压缩算法直到内存断点为止；而内部碎片隶属于一个进程，随着进程释放内存空间而释放。
-
页式内存管理和段式内存管理
答案：
页式内存管理：将逻辑地址空间和物理地址空间分成同样大小的片，利用页表实现逻辑地址空间向物理地址空间的转换。
段式内存管理：将逻辑地址空间进行分段，每段大小可变，利用段表实现逻辑地址空间向物理地址空间的转换。
区别：分段直接对物理地址空间划分，可能会产生外部碎片和内部碎片，而分页技术同时对逻辑地址空间和物理地址空间进行划分，它只产生外部碎片；帧大小普遍小于段的大小，但是页表通常远远大于段表的大小，从而造成分页的地址转换开销比较大。
-
哈希页表和反向页表
答案：
哈希页表：以虚拟页号为键，物理帧号为值建立哈希页表，发生碰撞的页表项以链表数据结构组织。
反向页表：反向页表对每个物理内存帧才有一个条目，而且每个页表项按照物理内存帧号进行排序。
区别：哈希页表针对某一个进程而建立的多级页表结构，而反向页表是针对整个操作系统而建立页表结构。
-
最优置换和 LRU 置换
答案：
最优置换：按需调页时，置换最长时间不会使用的页。
LRU 置换：按需调页时，置换最长时间没有使用的页。
区别：由于我们未知进程运行需要的页，最优置换算法难以实现，可以使用最长时间没有使用的页来近似最长时间不会使用的页。
-
按需调页和交换
答案：
按需调页：进程执行过程中，在需要时才调入相应的物理页，这种技术称为按需调页，又称为懒惰交换。
交换：把处于等待状态的进程从内存中移到二级存储，并释放该进程占用的内存空间，这一过程称为交换。
区别：按需调页细粒度地实现进程中的某个或某些内存页和二级存储间的交换，而交换是整个进程的所占用内存空间与二级存储间的交换。
四、综合题（40 分）
-
简述缺页中断处理的详细过程（从发生缺页中断开始至页面调度结束），并指明每个步骤中，处理所处的上下文环境和模式。（10 分）
答案：
How does OS handle a Page Fault?:
-
Choose an old page to replace in terms of a page-replacement algorithm
-
If old page modified（“D=1”）, write contents back to disk
-
Change its PTE and any cached TLB to be invalid
-
Load new page into memory from disk
-
Update page table entry, validate TLB for new entry
-
Continue thread from the new location via accessing the page table
-
-
一个 32 位的操作系统，内存大小为 ，采用分页技术进行内存分配，如果每页的大小为 ：（10 分）
a) 请说明各需多少位表示虚拟地址、物理地址、虚拟页号、物理帧号和偏移量（5 分）？
答案：
VA: 32, PA: 31, pages: 20，# frames: 19，offset: 12
b) 如果某进程的页表如下，请在内存中定位下列虚拟地址的物理地址：3187, 7745, 11084, 14267, 18443（5 分）。
PageID FrameID 0 4 1 2 2 5 3 3 答案：
3187 -> 19571, 7745 -> 11841,
11084 -> 23372, 14267 -> 14267
18843 超出了页表长度，非法内存访问
提示题目中为 18443，参考答案写作 18843；此处按参考答案保留。
-
采用按需调页（demand paging），现有 3 个页框，分别存储着页面号 2,3,4 三个页面。已知接下来的页面访问顺序为 1,2,3,4,1,2,5,1,2,3,4,5。使用时钟算法（clock algorithm）作为页面替换算法。（10 分）
a) 请计算会发生的缺页次数（假设初始时在页框内的页面的引用位（reference bit）都是 1，2/3/4 三个页面按序存放，初始时指针指向页面 2）？（7 分）
答案：
9 次缺页
b) 请写出这一内存访问序列所对应的时间段中的工作集（3 分）
答案：
5
-
现有两个进程 P1 和 P2，当前的页面访问序列分别为：
P1: 1, 2, 3, 4, 1, 2, 5
P2: 6, 7, 8, 6, 7, 6, 7
这两个进程总共可有 5 个页框可供使用。假设使用 LRU 替换策略，页框分配采用固定分配（即分配后不可修改），请问如何在两个进程间分配页框可以达到缺页率最低？
a) 请分别写出两个进程的替换序列，并计算总的缺页次数（6 分）。
答案：
2, 3 （10 次缺页）（1+4 也是 10 次，也算正确，答案不唯一）
1, 1, 3, 4, 1, 2, 5
2, 2, 3, 4, 1, 2
6, 6, 6, 6, 6, 6, 6
7, 7, 7, 7, 7, 7
8, 8, 8, 8, 8
b) 并证明这种帧分配对于给定的内存访问序列是最优的（4 分）。
答案：
证明：
a. 给 P2 更多页面不会减少 P2 的缺页率；
b. 给 P1 3 个页面不会减少 P1 的缺页率，但是会增加 P2 的缺页率；
c. 给 P1 4 个页面，P1 的缺页次数为 5，但是 P2 的缺页次数为 7。