在分页基础上建立的请求分页式虚拟存储器系统，是以页面为单位进行换入、换出的。而在分段基础上所建立的请求分段式虚拟存储器系统，则是以分段为单位进行换入、换出的。

在段表项中，有以下这些字段：

请求分段存储管理系统中的段表项

• 存取方式：用于标识本分段存取属性是只执行、只读还是允许读/写。
• 存在位P：用于指示该段是否已调入内存。
• 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页在最近多长时间未被访问。
• 修改位M：表示该段在调入内存后是否被修改过。
• 外存地址：本段在外存上的地址，即起始盘块号。
• 增补位：用于表示本段在运行过程中是否做过动态增长。

 

1.缺段中断机构

因为段是不定长的，对缺段中断的处理要比对缺页中断的处理复杂。

 

2.地址变换机构

因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。为此，在地址变换机构中又增加了某些功能，如缺段中断的请求及处理等。

 

3.分段的共享和保护

共享进程计数count：记录当前有多少个进程在共享该段，当count为0时，系统将内存回收。

存取控制字段：为不同的进程赋予不同的存取权限。

段号：对于同一个共享段，不同的进程内部的段号不一样，进程根据自己的段号去访问该共享段。

 

课后习题

 

1. 【2012统考真题】下列关于虚拟存储器的叙述中，正确的是（ ）。

A. 虚拟存储只能基于连续分配技术

B. 虚拟存储只能基于非连续分配技术

C. 虚拟存储容量只受外存容量的限制

D. 虚拟存储容量只受内存容量的限制

【答案】B

【解析】装入程序时，只将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，也无法从逻辑上扩大内存容量，因此虚拟内存的实现只能建立在离散分配的内存管理的基础上。有以下三种实现方式：① 请求分页存储管理；② 请求分段存储管理；③ 请求段页式存储管理。虚拟存储器容量既不受外存容量限制，又不受内存容量限制，而是由CPU的寻址范围决定的。

 

2. 【2011统考真题】在缺页处理过程中，操作系统执行的操作可能是（ ）。

Ⅰ.修改页表           Ⅱ.磁盘I/O           Ⅲ.分配页框

A . 仅 I、II                             B . 仅 II

C . 仅 Ⅲ                               D. Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】缺页中断调入新页面，肯定要修改页表项和分配页，所以Ⅰ、Ⅲ可能发生，同时内存没有页面，需要从外存读入，会发生磁盘I/O。

 

3. 【2013统考真题】若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是（ ）。

Ⅰ.处理越界错            Ⅱ. 置换页           Ⅲ.分配内存

A . 仅 Ⅰ、Ⅱ

B . 仅 II、III

C . 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】用户进程访问内存时缺页，会发生缺页中断。发生缺页中断时，系统执行的操作可能是置换页面或分配内存。系统内没有越界错误，不会进行越界出错处理。

 

4. 导致LRU算法实现起来耗费高的原因是（ ）。

A .需要硬件的特殊支持                 B .需要特殊的中断处理程序

C .需要在页表中标明特殊的页类型       D .需要对所有的页进行排序

【答案】D

【解析】LRU算法需要对所有页最近一次被访问的时间进行记录，查找时间最久的进行替换，这涉及排序，对置换算法而言，开销太大。为此需要在页表项中增加LRU位，选项A可看作是“耗费高”这一结果，选项D才是造成选项A的原因。

 

5.【2011统考真题】当系统发生抖动时，可以采取的有效措施是（ ）。

I . 撤销部分进程               Ⅱ.增加磁盘交换区的容量

III.提高用户进程的优先级

A .仅 I                              B . 仅 II

C .仅 III                             D . 仅 I、II

【答案】A

【解析】在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。抖动现象是指刚刚被换出的页很快又要被访问，为此又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上，导致系统性能下降。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。

 

6. 【2014统考真题】下列措施中，能加快虚实地址转换的是（ ）。

Ⅰ.增大快表（TLB）容量                Ⅱ.让页表常驻内存

III .增大交换区（swap ）

A. 仅 I                                 B .仅 II

C . 仅 I、II                             D . 仅 II、III

【答案】C

【解析】虚实地址转换是指逻辑地址和物理地址的转换。增大快表容量能把更多的表项装入快表，会加快虚实地址转换的平均速率；让页表常驻内存可以省去一些不在内存中的页表从磁盘上调入的过程，也能加快虚实地址转换；增大交换区对虚实地址转换速度无影响，因此I、II正确，选 C。

 

7. 【2014统考真题】在页式虚拟存储管理系统中，采用某些页面置换算法会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是( )。

I. LRU算法 Ⅱ. FIFO算法

Ⅲ. OPT算法

A . 仅 II                              B . 仅 I、II

C . 仅 I、III                           D . 仅 II、III

【答案】A

【解析】只有FIFO算法会导致Belady异常，选 A。

 

8. 【2016统考真题】某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。A = 0 表示页最近没有被访问，A = 1表示页最近被访问过。M = 0表示页未被修改过，M = 1 表示页被修改过。按( 4 奶所有可能的取值，将页分为(0, 0),(1, 0),(0,1)和(1,1)四类，则该算法淘汰页的次序为(   )。

A. (0, 0), (0, 1), (1, 0), (1, 1)                B. (0, 0), (1, 0), (0, 1), (1, 1)

C. (0, 0), (0, 1), (1, 1), (1, 0)                D. (0, 0) ,(1, 1), (0,1), (1, 0)

【答案】A

【解析】改进型CLOCK置换算法执行的步骤如下：

1） 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧（A = 0, M = 0 ）用于替换。

2） 若第1）步失败，则重新扫描，查找（A=0，M=1） 的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，将其使用位设置成0。

3） 若第2）步失败，则指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第 1）步，并在有必要时重复第2）步，这样将可以找到供替换的帧。

因此，该算法淘汰页的次序为（0,0）,（0,1）,（1,0）,（1,1）, 即 A 正确。

 

9. 【2015统考真题】在请求分页系统中，页面分配策略与页面置换策略不能组合使用的是(  )。

A .可变分配，全局置换                  B.可变分配，局部置换

C .固定分配，全局置换                  D .固定分配，局部置换

【答案】C

【解析】对各进程进行固定分配时页面数不变，不可能出现全局置换。而 A、B、D 是现代操作系统中常见的3种策略。

 

10. 【2015统考真题】系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0,2, 9, 3,4,2,8,2,4,8,4,5。若进程要访问的下一页的页号为7 , 依据LRU算法，应淘汰页的页号是 ( )。

A. 2

B. 3

C. 4

D. 8

【答案】A

【解析】可以采用书中常规的解法思路，也可以采用便捷法。对页号序列从后往前计数，直到数到4（页框数）个不同的数字为止，这个停止的数字就是要淘汰的页号（最近最久未使用的页），题中为页号2。

 

11. 【2016统考真题】某进程访问页面的序列如下所示。

若工作集的窗口大小为6 , 则在f时刻的工作集为( )o

A. {6, 0, 3, 2}                   B. {2, 3, 0, 4}

C. {0, 4, 3, 2, 9}                  D.{4, 5, 6, 0, 3, 2}

【答案】A

【解析】在任一时刻都存在一个集合，它包含所有最近左次（该题窗口大小为6）内存访问所访问过的页面。这个集合w(k, t)就是工作集。题中最近6次访问的页面分别为6, 0, 3, 2, 3, 2 , 去除重 复的页面，形成的工作集为｛6, 0, 3, 2｝。

 

12. 【2019统考真题】某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了 4 个页框，进程P 访问页号的序列为0,1,2,7,0,5,3,5,0,2,7,6,则进程访问上述页的过程中，产生页置换的总次数是(   )。

A. 3               B. 4           C. 5          D. 6

【答案】C

【解析】最近最久未使用（LRU） 算法每次执行页面置换时会换出最近最久未使用过的页面。第一次访问5页面时，会把最久未被使用的1页面换出，第一次访问3 页面时，会把最久未访问的2 页面换出。具体的页面置换情况如下图所示。

需要注意的是，题中问的是页置换次数，而不是缺页次数，所以前4 次缺页未换页的情况不考虑在内，答案为 5 次，因此选C。

 

13. 【2009统考真题】请求分页管理系统中，假设某进程的页表内容如下表所示。页面大小为4KB, 一次内存的访问时间是100ns,―次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns （ 已含更 新 TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用（LRU）置换算法和局部淘汰策略。假设：①TLB初始为空；②地址转换时先访问TLB，若 TLB未命中，再访问页表（忽略访问页表后的TLB更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚

地址访问序列2362H, 1565H, 25A5H,请问：

1） 依次访问上述三个虚拟地址，各需多少时间？给出计算过程。

2 ） 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

【解析】

1） 根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB ，即2¹²得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P 如下 （十六进制的一位数字转换成二进制的4 位数字，因此十六进制的低三位正好为页内位移，最高位为页号）：

2362H：P = 2 , 访问快表10ns,因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存 100ns,共计 10ns + 100ns + 100ns = 210ns。

1565H：P = l , 访问快表10ns,落空，访问页表100ns落空，进行缺页中断处理10⁸ns, 访问

快表 10ns，合成物理地址后访问主存100ns，共计 10ns + 100ns + 108ns + 10ns + 100ns = 100000220ns。

25A5H：P = 2 , 访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址,访问主存100ns，共计 10ns + 100ns = 110ns。

2） 当访问虚地址1565H时，产生缺页中断，合法驻留集为2 , 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0 号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

 

14. 【2012统考真题】某请求分页系统的页面置换策略如下：从 0 时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计）且本轮未被访问过的页框将被系统回收，并放入空闲页框链尾，其中内容在下一次分配之前不清空。当发生缺页时，若该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框忽略其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页的页框号依次为32, 15, 21, 41。进程P依次访问的〈虚拟页号，访问时刻〉为<l, 1>, <3, 2>, <0, 4>, <0, 6>, <1, 11>, <0, 13>, <2, 14> 请回答下列问题：

1) 当虚拟页为<0, 4>时，对应的页框号是什么？

2) 当虚拟页为<1, 11>时，对应的页框号是什么？说明理由。

3) 当虚拟页为<2, 14>时，对应的页框号是什么？说明理由。

4) 这种方法是否适合于时间局部性好的程序？说明理由

【解析】

1) 页框号为21。因为起始驻留集为空，而 0 页对应的页框为空闲链表中的第三个空闲页框(21),其对应的页框号为21。

2) 页框号为32。理由：因 11 > 10 ,因此发生第三轮扫描，页号为1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。

3) 页框号为41。理由：因为第2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41 ，页框号为41。

4) 合适。理由：程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。

 

15. 【2010统考真题】设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6 页（Page）数据存储空间，页的大小为1KB,操作系统采用固定分配局 部置换策略为此进程分配4 个页框（Page Frame）, 见下表。在装入时刻260前，该进程的访问情况也见下表（访问位即使用位）。

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。回答下列问题：

1） 该逻辑地址对应的页号是多少？

2） 若采用先进先出（FIFO）置换算法，则该逻辑地址对应的物理地址是多少？要求给出计算过程。若采用时钟（Clock）置换算法，则该逻辑地址对应的物理地址是多少？ 要求给出计算过程。设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如下图所示。

【解析】

1）由于该计算机的逻辑地址空间和物理地址空间均为64KB = 2¹⁶B, 按字节编址，且页的大小为1K = 2¹⁰, 因此逻辑地址和物理地址的地址格式均为

17CAH = 0001 0111 1100 1010B,可知该逻辑地址的页号为 000101B = 5。

2） 采用FIFO置换算法，与最早调入的页面即0 号页面置换，其所在的页框号为7 ,于是对应的物理地址为 0001 1111 1100 1010B = 1FCAH。

3） 采用CLOCK置换算法，首先从当前位置（2号页框）开始顺时针寻找访问位为0 的页面，当指针指向的页面的访问位为1 时，就把该访问位清“0”, 指针遍历一周后，回到2号页框，此时2号页框的访问位为6，置换该页框的页面，于是对应的物理地址为0000 1011 1100 1010B = 0BCAH。

 

16. 【2015统考真题】某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所示：

请回答下列问题：

1） 页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？

2） 若页目录项和页表项均占4 B ,则进程的页目录和页表共占多少页？写出计算过程。

3） 若某指令周期内访问的虚拟地址为0100 0000H和 0111 2048H,则进行地址转换时共访问多少个二级页表？说明理由。

【解析】

1） 页和页框大小均为4KB。进程的虚拟地址空间大小为2³² / 2¹²= 2²⁰页。

2） （2¹⁰×4）/ 2¹²（ 页目录所占页数）+ （2²⁰×4）/ 2¹²（ 页表所占页数）= 1025页。

3） 需要访问一个二级页表。因为虚拟地址0100 0000H和 0111 2048H的最高10位的值都是4 ,访问的是同一个二级页表。

 

17. 【2018统考真题】某计算机采用页式虚拟存储管理方式，按字节编址，CPU进行存储访问的过程如下图所示，回答下列问题。

1） 某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？

2） 寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时, PDBR的内容是否会变化？说明理由。

3） 为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段?

【解析】

1） 由图可知，地址总长度为32位，高20位为虚页号，低 12位为页内地址，且虚页号高10位为页目录号，低 10位为页号。展开成二进制表示为

因此十六进制表示为0180 6008H。

2） PDBR为页目录基址地址寄存器（Page-Directory Base Register） , 其存储页目录表物理内存基地址。进程切换时，PDBR的内容会变化；同一进程的线程切换时，PDBR的内容不会变化。每个进程的地址空间、页目录和PDBR的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新PDBR。同一进程中的线程共享该进程的地址空间， 其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR的内容也不变。

3） 改进型CLOCK置换算法需要用到使用位和修改位，所以需要设置访问字段（使用位）和修改字段（脏位）。