内存管理
习题
一.选择题
1、设备分配问题中，算法实现时，同样要考虑安全性问题，防⽌在多个进程进⾏设备请求时，因相互等待对⽅释放所占设备所造成的（D）现象。
A．瓶颈 B．碎⽚ C．系统抖动 D．死锁
2、主存与辅存间频繁的页⾯置换现象被称为（C）。
A．请求调页 B．碎⽚整理 C．系统抖动 D．输⼊输出
3、在可变分区存储管理中，最差适应分配算法要求对空闲区表项按（ C）进⾏排列
A．地址从⼤到⼩ B．地址从⼩到⼤ C．尺⼨从⼤到⼩ D．尺⼨从⼩到⼤
若为最优适应分配算法则D
最优适应分配算法可把空闲区按长度以递增顺序登记在空闲区表中。分配时顺序查找空闲区表，由于查找时每次总是从分区中的最小的一个区开始，所以，找到的第一个能满足作业要求的分区，一定是所有能满足作业要求的分区中的最小的一个分区。
4、段页式存储管理汲取了页式管理和段式管理的长处，其实现原理结合了页式和段式管理的基本思想，即（ B ）。
A、⽤分段⽅法来分配和管理物理存储空间，⽤分页⽅法来管理⽤户地址空间。
B、⽤分段⽅法来分配和管理⽤户地址空间，⽤分页⽅法来管理物理存储空间。
C、⽤分段⽅法来分配和管理主存空间，⽤分页⽅法来管理辅存空间。
D、⽤分段⽅法来分配和管理辅存空间，⽤分页⽅法来管理主存空间。
段页式存储管理兼有页式管理和段式管理的优点，采用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。
5、下列措施中，能加快虚实地址转换的是：
I. 增⼤快表（TLB） II. 让页表常驻内存 III. 增加交换区
A. 仅 I B. 仅 II C. 仅I,II D. 仅II,III
C
增大TLB，是为了避免去内存中匹配页表。TLB本身就在***里，而且能并行计算。把页表都放在内存里，也是可以的，但一般页表很大，可以经过多级页表和反置页表处理后再放在内存里。交换区是内存不够用时的解决手段，增大交换区能腾出更多地方。
6、在页式存储管理系统中，采⽤某些页⾯置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加⽽增加。下列算法中，可能出现Belady异常现象的是：
I. LRU 算法 II. FIFO 算法 III. OPT 算 法
A. 仅II B.仅 I,II C. 仅I,III D. 仅II,III
A
7、下列选项中，属于多级页表优点的是：D
A.加快地址变换速度 B.减少缺页中断次数
C. 减少⼀个页表项所占字节数 D.减少页表所占的内存空间
8、下列关于虚拟存储器的叙述中，正确的是 B
A. 虚拟存储器只能基于连续分配技术 B. 虚拟存储器只能基于⾮连续分配技术
C. 虚拟存储器只受外存容量的限制 D. 虚拟存储器只受内存容量的限制
虚拟存储器(Virtual Memory)是为了给用户提供更大的随机存取空间而采用的一种存储技术。它将内存与外存(辅存)结合使用，好像有一个容量极大的内存储器，工作速度接近于主存，每位的成本又与辅存相近，在整机形成多层次存储系统。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。 虚拟存储器是由硬件和操作系统自动实现存储信息调度和管理的，其工作过程包括6个步骤： ①中央处理器将访问主存的逻辑地址分解成组号a和组内地址b，并对组号a进行地址变换，即以a为索引查地址变换表，以确定该组信息是否在主存中。 ②若该组号已在主存，则转而执行④；否则检查主存中是否有空闲区，便将某个暂时不用的组调出送往辅存，以便将需要的这组信息调入主存。 ②从辅存读出所要的组，并送到主存空闲区，并登记在地址变换表中。 ③从地址变换表读出与逻辑组号a对应的物理组号a。 ⑤从物理组号a和组内字节地址b得到物理地址。 ⑥根据物理地址从主存中存取需要的信息。
9、在⼀个请求分页系统中，采⽤ LRU 页⾯转换算法时，加⼊⼀个作业的页⾯⾛向为：
1，3，2，1，1，3，5，1，3，2，1，5.当分配给该作业的物理块数分别为 3 和 4 时，在访问过程中所发⽣的缺页率为 C
A. 25%，33% B. 50%，25% C.50%,33% D. 50%，75%
M=3
1 3 2
请求5 缺页 1 3 5
请求2 缺页 1 3 2
请求5 缺页 1 5 2
6/12 = 25%
M=4
1 3 2 5
4 / 12 = 33%
9-2
在一个请求分页系统中，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别是3和4时，分别采用LRU和FIFO面替换算法，计算访问过程中所发生的缺页次数和缺页率，比较所得结果。
当M=3时，采用LRU替换算法
缺页次数为10次，缺页率为：(10/12)×00%=83%。
当M=3时，采用FIFO替换算法
缺页次数为9次，缺页率为：(9/12)×100%=75%。
(2) 当M=4时，采用LRU替换算法
缺页次数为8次，缺页率为：(8/12)×100%=67%。
当M=4时，采用FIFO替换算法，
缺页次数为10次，缺页率为：(10/12)×100%=83%。
通过以上缺页次数和缺页率的分析计算，可以看出，对于LRU算法，增加物理块数，可以减少缺页次数，降低缺页率；而对FIFO算法，增加物理块数，不一定能减少缺页次数。
9-3
在一个请求分页系统中,假如一个作业的也面走向为:4,3,2,1,5,4,3,2,4,5,当分配给该作业的物理块数为4时,试分别计算采用最佳（optimal)置换算法和最近最久未使用（lru)置换算法时,访问过程中所发生的缺页次数
最佳置换,置换掉最长时间内不会在用的页；最近最久未使用,置换掉当前最久没有被使用的页
1：最佳置换
序列：4 3 2 1 5 4 3 2 4 5
内存页有4 3 2 1
请求5时,缺页,置换掉1,因为1不会再被使用了；内存页有4 3 2 5
请求4 3 2 4 5时,都不缺页；
缺页次数为1
2：最近最久未使用
序列：4 3 2 1 5 4 3 2 4 5
内存页有4 3 2 1
请求5时,缺页,置换掉4,因为4最早进内存,最久未被使用；内存页有5 3 2 1
请求4时,缺页,置换掉3,理由同上；内存页有5 4 2 1
请求3时,缺页,置换掉2,理由同上,内存页有5 4 3 1
请求2时,置换1,内存页有5 4 3 2；
请求4,5时不缺页；
缺页次数为4
这题和前面的题缺页次数基准好像不同,不过大多数题目都是跟9-2一样
一个请求分页系统中，假设系统分配给 某进程的物理块数为 3 ，开始时内存为空，执行如下访问页号序列：
1 ， 2 ， 3 ， 4 ， 1 ， 2 ， 5 ， 1 ， 2 ， 3 ， 4 ， 5
试说明采用先进先出 (FIFO) 、最近最少使用（ LRU ）和最佳置换算法 (OPT) 进行页面置换时，缺页次数各是多少？
（ 1 ） FIFO: 9 次
（ 2 ） LRU ： 10 次
（ 3 ） OPT ： 7 次
10、 设有 8 页的逻辑空间，每页有 1024B,它们被映射到 32 块的物理存储区中。那么， 逻辑地址的有效位是 位，物理地址⾄少是 位。(C)
A. 10、11 B. 12、14 C. 13、15 D. 14、16
8 = 2^3 32 = 2^5
逻辑 10+3=13
物理 10+5=15
11、 某基于动态分区存储管理的计算机,其主存容量为 55M B(初始为空闲),采⽤最佳适配(Best Fit)算法,分配和释放的顺序为:分配 15M B,分配 30M B,释放 15M B,分配 8M B, 分配 6M B,此时主存中最⼤空闲分区的⼤⼩是 B 。
若为WF 选 A
A.7MB B.9MB C.10MB D.15MB
- 某作业的逻辑地址空间为4页，页⾯⼤⼩为2048，已知页表如下所⽰，则逻辑地址
4865（⼗进制）对应的物理地址为（C）。
页号 0 1 2 3
块号 2 4 6 8
A、4865 B、8961 C、13057 D、6865
4865 = 1301H = 0001001100000001
2对应6
11001100000001 = 13057
ok
13、若⽤户进程访问内存时产⽣缺页，则下列选项中，操作系统可能执⾏的操作是 B
I.处理越界错 II.置换页 III.分配内存
A.仅I、II B.仅II、III C. 仅I、III D. I、II和III
用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统会执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
14、 可以被多个进程在任意时刻共享的代码必须是 C。
A. 顺序代码 B. 机器语⾔代码 C.不能⾃⾝修改的代码 D. ⽆转移指令代码
15、 假设变址寄存器 R 的内容为 1000H，指令中的形式地址为 2000 H；地址 1000H 中的内容为 2000H，地址 2000H 中的内容为 3000H，地址 3000 H 中的内容为 4000H，则变址寻址⽅式下访问到的操作数是： D
A. 1000H B. 2000H C. 3000H D. 4000 H
16、 有⼀个整数矩阵为 100 ⾏*200 列，即 a[100][200]。在⼀个虚拟系统中，采⽤ LRU 算法，系统分给该进程 5 个页⾯来存储数据（不包含程序），设每页可存放 200 个整数，该程序要对整个数组初始化，数组存储时是按⾏存放的。试计算下列两个程序各⾃的缺页次数（假定所有页都以请求⽅式调⼊）。 B
A. 100,200 B. 100,20000 C. 200,100 D. 20000,100
程 序 一 ：
for(i=0;i<99;i++)
for(j=0;j<=199;j++)
a[i][j]=i*j;
程 序 二 ：
for(j=0;j<=199;j++)
for(i=0;i<99;i++)
a[i][j]=i*j;
17、 考虑页⾯置换算法，系统有 m 个物理块供调度，初始时全空，页⾯引⽤串长度为p，包含了 n 个不同的页号，⽆论⽤什么算法，缺页次数不会少于（C）
A、m B 、 p C 、 n D 、 min(m,n)
无论采用什么置换算法,每种页面第一次访问时不可能在内存中.必然发生缺页.
18、 总体上说，“按需调页”（Demand-Paging）是个很好的虚拟内存管理策略。但是， 有些程序设计技术并不适合于这适种环境。例如（D）
A、堆栈 B、线性搜索 C、⽮量运算 D、⼆分法搜索
因为二分法搜索地址是不连续的、跳跃的，不在同一页面，需要不断地调页。
- 把进程地址空间中使⽤的逻辑地址变成内存中物理地址的过程称为：A
A、重定位 B、物理化 C、逻辑化 D、加载
由程序中逻辑地址组成的地址范围叫做逻辑地址空间，或简称为地址空间。而由内存中的一系列存储单元所限定的地址范围称为内存空间，也称为物理空间或者绝对空间。
程序和数据装入内存时需对目标程序中的地址进行修改。这种把逻辑地址转变为内存的物理地址的过程叫重定位。
对程序进行重定位的技术按重定位的时机可分为两种：静态重定位和动态重定位。
二.计算题
某操作系统中，进程的逻辑地址空间和系统的物理地址空间均为 64KB，按字节编址。某进程最多需要 8 页（Page）数据存储空间，页的⼤⼩为 2KB，操作系统采⽤固定分配局部置换策略为此进程分配 6 个页框（Page Frame），采⽤⽼化算法（aging）进⾏页⾯置换，每个页⾯使⽤ 8bits 记录使⽤情况。在每个 clock tick 结束时，6 个页⾯的 R 位如下所⽰：
页⾯ 0 页⾯ 1 页⾯ 2 页⾯ 3 页⾯ 4 页⾯ 5
clock tick 0 0 1 0 1 0 1
clock tick 1 1 1 1 0 0 0
clock tick 2 0 0 1 1 1 0
clock tick 3 1 0 0 1 0 0
此时的页表如下所⽰：
页号 页框号 是否在内存中（P 位） 是否在 TLB（快表）中
00H 08H 1 是
01H 07H 1 是
02H 04H 1 是
03H 1EH 1 是
04H 15H 1 是
05H 0FH 1 是
06H --- 0 否
07H --- 0 否
页表存放在主存中，对主存的⼀次存取需要100ns，对TLB表的查找时间为10ns，处理
⼀次缺页中断需要108 ns（10的8次⽅ns，含更新TLB和慢表的时间）。
-
如果现在程序执⾏时遇到逻辑地址1AC5H，这次访问耗费时间为 C 。
A. 108+220ns B. 100ns C. 110ns D. 210ns -
然后，程序执⾏时遇到逻辑地址32C5H，这次访问耗费时间为 。
A. 108+220ns B. 100ns C. 110ns D. 210ns -
32C5H对应的物理地址为 D 。
A.7AC5H B. 22C5H C. 3AC5H D. F2C5H
物理 16
逻辑 16
页内偏移 11
1AC5H = 11 ... 在快表中
32C5H 缺页
置换页面5 因为1的访问计数器0011值最小
物理地址为
0111 1010 1100 0101 = 7AC5
某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页⾯⼤⼩为 4KB，页表项⼤⼩为 4 字节。请回答下列问题。
- 若使⽤⼀级页表的分页存储管理⽅式，逻辑地址结构为：
|页号(20位) | 页内偏移量（12 位）|
此时页表最⼤占⽤空间为 C。
A. 4KB B. 1MB C. 4MB D. 32MB
- 若使⽤⼆级页表的分页存储管理⽅式，逻辑地址结构为：
|页⽬录号（10 位）| 页表索引（10 位）| 页内偏移量（12 位）
若该进程共⽤到了10000个页，则此时此⼆级页表占⽤的总空间最⼩为 C 。
A. 4KB B. 11KB C. 44KB D. 11MB
4KB/4B = 1024
需要11个页表
11 * 4KB
某操作系统的内存管理器采⽤请求式分页，页⾯⼤⼩为 1KB，逻辑地址空间为 32 位， 物理地址空间⼤⼩为 4 GB，按字节编址。页表采⽤多级页表，⼀个页表项⼤⼩为 4B。TLB（快表）采⽤全相联映射，有 4 个页表项，内容如下表所⽰。
有效位 页号 页框号 …
0 FF180H ------ …
1 3FFF1H 0F035H …
1 FFFC6H 3054CH …
1 03FFFH 0C153H …
34、该系统的页表项中，最多可以保存 B位标志位。
A．8 B．10 C．12 D．16
35、若采⽤多级页表，要求每级页表均可以装⼊⼀个页⾯内，则应该采⽤ D 级页表较合适。
A．0 B．1 C．2 D．3
36、对逻辑地址3FFF1880H转换为物理地址的结果是 A 。
A. 0C153080H B. 0F035880H C. TLB 缺失 D.缺页
此题目 难在 页面大小为1K
大同小异
某请求页式存储管理，允许⽤户空间为 32 个页⾯（每页 2KB），主存为 16KB，如有⼀个⽤户程序有 10 页长，且某时刻该⽤户进程的页表如下表所⽰
页号 物理块号 是否在 TLB 中
0 8 是
1 7 是
2 4 否
3 9 否
4 5 否
5 3 是
6 2 是
其它 not valid
逻辑地址 5+11=16
页内偏移11位
物理 14位
37、 如果程序执⾏时遇到逻辑地址1AC5H，则它对应的物理地址为 B 。
A. 7AC5H B. 4AC5H C. 3AC5H D. 缺 页
38、 页表存放在主存中，对主存的⼀次存取需要100ns，对TLB表的查找时间为10ns， 这次访问耗费时间为 D。
A. 10ns B. 100ns C. 110ns D. 210ns
10+100+100=210
39、 如果不考虑缺页的情况，对于已经载⼊内存的页⾯，快表命中率为80%，则访问内存中数据的平均有效访问时间是 B。
A．20ns B．30ns C．70ns D．90ns
100.8 + (10+100)0.2=8+22=30ns
某操作系统的内存管理器采⽤请求式分页，页⾯⼤⼩为 4KB，逻辑地址空间为 32 位， 物理地址空间为 36 位，⼀个页表项⼤⼩为 4B。⼀次快表（TLB）的访问时间是 10ns，⼀次内存的访问时间是 100ns，处理⼀次缺页的平均时间 10^8 ns（已含更新 TLB 和页表的时间）。进程的驻留集⼤⼩固定为 2,采⽤最近未使⽤置换算法(NRU)和局部淘汰策略。假设（1） TLB 初始为空;（2）地址转换时先访问 TLB,若 TLB 未命中,再访问页表(忽略访问页表之后的 TLB 更新时间);（3）有效位为 0 表⽰页⾯不在内存,产⽣缺页中断,缺页中断处理后,返回到产⽣缺页中断的指令处重新执⾏。进程的部分页表如下所⽰：
页号 页框(Page Frame)号 P存在位 R访问位 M修改位
00000H ------ 0 - -
00001H 007F61H 1 0 0
00002H 101254H 1 0 0
00003H ------ 0 - -
40、 该系统的页表项中，最多可以保存 V位标志位。
A．4 B．8 C．12 D．16
页表项32位, (36-12)算出页框号
所以32 - (36- 12) = 8
41、若采⽤多级页表，要求每级页表均可以装⼊⼀个页⾯内，则应该采⽤ C级页表较合适。
A．0 B．1 C．2 D．3
ok
42、 如果不考虑缺页的情况，对于已经载⼊内存的页⾯，快表命中率为90%，则访问内存中数据的平均有效访问时间是 A。
A．20ns B．110ns C．120ns D．320ns
100.9+1100.1=20ns
43、 ⾸先，访问逻辑地址00001618H，则读⼊所需数据需要的总时间是 D。
A．约 10^8ns B．110ns C．200ns D．210ns
内存是P位
10 + 100 +100
44、 然后，访问逻辑地址00000FA6H，则读⼊所需数据需要的总时间是 A 。
A．约 10^8ns B．110ns C．200ns D．210ns
缺页中断了.
45、 最后，访问逻辑地址0000126CH，则读⼊所需数据需要的总时间是 B 。
A．约 10^8ns B．110ns C．200ns D．210ns
页表1 在快表中了
46、 在依次访问完上述三个逻辑地址后，页框101254H对应的页号为 A。
A．00000H B．00001H C．00002H D．00003H
(这题我也没太理解)是不是访问00000FA6H时候缺页中断 置换了页表2
答案:(1) 4KB (2) 4MB (3) (LA>>22)&0x000003FF (4) (LA>>12)&0x000003FF (5) 4×4K
(6) 00200020H (7) 00200040H (8) 00900H (9) 00901H (10)00901000H
解答:
2362H: 页号是2 先访问快表 再内存 再读内存
10 +100 +100 =210ns
物理地址:254362H
1565H: 页号1 快表,内存,缺页处理,快表,读内存
10+100+10^8+10+100 ns
置换页面0 物理地址为 101565H
25A5: 快表,内存
10+100 =110ns
物理地址 2545A5H
解答:
页号是 5
LRU 淘汰掉未使用时间最长的一个 所以是 0
17CAH
101 1111001010
111 1111001010
物理地址为1FCAH
三、简答题
1、 在虚拟存储管理中，分段式内存管理⽅式解决了分页式内存管理中的什么问题，又带来了什么问题呢？
解决了分页式机械化的分页(功能可能不同)导致颠簸现象?
分段式由内在逻辑来分, 不过段大 类似于动态分区会产生外碎片 导致内存利用率低
2、 在页⾯淘汰算法中，为什么说⽼化(Aging)算法只是 LRU 的⼀个近似实现？
(1老化算法 无法区分用了多少次
(2)老化算法的计数器只能有有限位数,限制了对以往页面的记录
老化算法只有有限位的存储，记录最近若干次页面使用情况，更早的使用情况会丢失。另外，老化算法没有记录在一个时间周期内页面的使用频度和时间等，所以与 LRU 相比只是一个近似实现。
3、 LRU页⾯置换算法是⼀种⽐较优秀的算法但是较难实现，为什么？试给出⼀种可⾏的近似算法作为LRU的取代⽅案。
每次访问内存都必须更新整个链表,在链表中找到一个页面,删除它.然后再把它移动到表头
老化算法:在R位被加进去之前先将计数器右移一位,
其次,将R位加到计数器的最左端的位而不是最右端的位置
4、 单纯的分段式和分页式内存管理各有什么缺点？为什么段页式可以避免这些缺点？ 为什么段页式内存管理没有被⼴泛采⽤呢？
分段式,段太大,倒是产生外碎片, 内存利用率低
分页式机械化的分页(功能可能不同)导致 颠簸现象
段页式存储管理兼有页式管理和段式管理的优点，采用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。
段页式实现起来太麻烦了.
分段管理逻辑地址, 分页管理物理地址
5、 为什么内存管理⽅式中，可变分区管理中有最差适应（worst fit)分配算法，⽽固定分区管理中没有这个算法？分区管理中的交换技术（swap）和段式管理中的请求式分段技术有什么区别？请求式分段与覆盖技术（overlay）又有什么区别？
瞎编的
WF是按找照尺寸从大到小求对空闲区表项排序
固定分区：系统将内存划分为若干固定的分区，当作业申请内存时，系统为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，浪费了一些存储空间。可变分区：是指在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等。引入可变分区方法，使内存分配有较大的灵活性，也提高了内存利用率。但是可变分区会引起碎片的产生。Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
分区管理中的交换技术（swap）和段式管理中的请求式分段技术有什么区别？
不知道呢
6、 页⾯置换（淘汰）的时机是什么？哪种算法最理想同时也不可能实现？为什么说LRU算法很有效但是很难实现？什么是Belady异常？哪种算法存在Belady异常现象？
内存中找不到页表
OPT
很难知道;每次访问内存都必须更新整个链表,在链表中找到一个页面,删除它.然后再把它移动到表头
采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象
FIFO存在Belady异常现象
7、 请讨论⼀下页⾯置换算法中⼯作集（Working Set）置换算法的⼯作原理。
一个进程当前正在使用的页面的集合称为它的工作集。
页面置换算法详解（10种）
基于工作集的页面置换算法就是找出一个不在工作集中的页面并淘汰它,每个表项至少包含两条信息：上次使用该页面的近似时间和R（访问位）。
8、 在内存管理的⽅法中，分段式管理⽐分页式管理有什么优势？段页式与其他⽅式相
⽐有什么好处？
分段式不会出现抖动的情况,
段页式:先分段再分页
既有了分段的好处又有了分页的好处,(不会出现外碎片吧?)
9、 为了同时抢占⾼端和中低端市场，CPU ⼚商常常在同⼀⽣产线上⽣产主频和制作⼯艺相同的⾼端和低端CPU，如Intel 曾经同时⽣产相同主频和制作⼯艺的“奔腾 4”和“赛扬”，价格上相差很⼤，据称主要区别在⼆级缓存的⼤⼩。请问缓存（Cache）有 什么⽤，什么地⽅会⽤到它？
cache是存在于主存与CPU之间的一级存储器， 由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多， 接近于CPU的速度。
作用：缓和中央处理器(CPU)和主存储器(内存)之间速度不匹配的矛盾。
原理：当中央处理器存取主存储器某一单元时，计算机硬件就自动地将包括该单元在内的那一组单元内容调入高速缓冲存储器，中央处理器即将存取的主存储器单元很可能就在刚刚调入到高速缓冲存储器的那一组单元内。
效果：中央处理器绝大多数存取主存储器的操作能为存取高速缓冲存储器所代替，计算机系统处理速度就能显著提高。
10、 为什么要使⽤倒排页表？倒排页表⾯临的最⼤的问题是什么？如何解决？
最差情况下需要搜索整个倒排索引表才能找到映射关系
倒排页表节省大量的空间.(物理地址)
从虚拟地址到物理地址的转换变得很困难
解决:使用TLB,用TLB记录所有频繁使用的页,
建立一张散列表,用虚拟地址来散列.
程序局部性原理，是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。
局部性原理又表现为：时间局部性和空间局部性。
时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。
空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。
另外，根据程序的局部性理论，Denning提出了工作集理论。所谓工作集是指进程运行时被频繁访问的页面集合。显然我们知道只要使程序的工作集全部集中在内存中，就可以大大减少进程的缺页次数；否则会使进程在运行过程中频繁出现缺页中断，从而出现频繁的页面调入/调出现象，造成系统性能的下降，甚至出现“抖动”。
划分工作集可以按定长时间或定长页面两种方法进行划分。当颠簸现象发生时，说明系统的负荷过大，通常采用处理器均衡调度。另一种是控制缺页率，当缺页率达到上限时，则增加内存分配量；当缺页率达到下限时，就减少内存的分配量。
工作集就是最近k次内存访问过所使用过的页面的集合
相关知识
强烈推荐阅读此文请求分页存储管理方式