1.作业内容
假设某系统的进程虚拟地址为32位，使用12位=4KB长度的页面，页表也是分页存储管理，每个页表表目占4 Bytes。请你：
1）设计一个页表管理的数据结构；
2） 根据用户进程要访问的虚拟空间地址
x
x
x，同时假设要访问的页面已在内存，设计一个查找该虚拟地址对应的内存物理页框号
b
b
b和物理地址
y
y
y的算法，并试分析算法的复杂度。要求页表结构尽量简洁，查找算法开销小。
2.解答
1）设计一个页表管理的数据结构
| 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |
|---|---|---|---|---|---|
状态位P：指示该页是否已经调入内存。
访问字段A：记录本页在一段时间内的访问次数，供置换算法换出页面时参考。
修改位M：标识该页在调入内存后是否被修改过。如果应淘汰的页在执行中没有被修改过，不必调出，直接装入一个新页覆盖。若修改过，则需要调出到外存。
外存地址：指出该页在外存上的地址，通常是物理块号。
按字节编址，使用32位虚拟地址。每个进程有的
2
32
B
=
4
G
B
2^{32}B=4GB
232B=4GB虚拟地址空间，使用
2
12
B
=
4
K
B
2^{12}B=4KB
212B=4KB的页面，
2
32
/
2
12
=
2
20
2^{32}/2^{12}=2^{20}
232/212=220，即一个进程可以用
2
20
2^{20}
220个页面，需要
≥
20
/
8
=
3
B
\ge 20/8=3B
≥20/8=3B的表目，题目中取页表表目
4
B
4B
4B。则每个进程页表空间
2
22
B
=
4
M
B
2^{22}B=4MB
222B=4MB。
22
+
12
>
32
22+12>32
22+12>32,所以页表不能全装在主存，需要用到二级页表。
低12位为页内偏移量，高20位采用二级页表。每个小页表可以放
2
10
=
1
K
2^{10}=1K
210=1K个页表表目，共
2
10
=
1
K
2^{10}=1K
210=1K个小页表。
2
10
∗
2
10
∗
2
12
=
2
32
2^{10}*2^{10}*2^{12}=2^{32}
210∗210∗212=232，正好填满
32
32
32位地址。为了对
1
K
1K
1K个小页表进行查找，需要一个页表表目，页表表目有
1
K
1K
1K个，共
10
10
10位，为
31
31
31~
22
22
22位。小页表占
10
10
10位，为二级页号，为
21
21
21~
12
12
12位。页面内的偏移量为
12
12
12位，对应
4
K
B
4KB
4KB的页面，为
11
11
11~
0
0
0位。
| 一级页号 | 二级页号 | 页内偏移量 |
|---|---|---|
| 31 31 31~ 22 22 22位 | 21 21 21~ 12 12 12位 | 11 11 11~ 0 0 0位 |
2）算法
先取地址的高
10
10
10位(
31
31
31~
22
22
22位)，在一级页表中查找而应页框号所在位置页表
x
31..22
x_{31..22}
x31..22。即
x
31..22
=
x
/
2
22
x_{31..22}=x/2^{22}
x31..22=x/222。访问
x
31..22
x_{31..22}
x31..22，得到虚拟页号的物理页表起始地址
b
1
b_1
b1。再取
x
x
x的
21
21
21~
12
12
12位，得到二级页号
x
21..12
=
(
x
m
o
d
2
22
)
/
2
12
x_{21..12}=(x \mod 2^{22})/2^{12}
x21..12=(xmod222)/212。将
b
1
b_1
b1与
x
21..12
x_{21..12}
x21..12相加得到新地址，访问该地址，得到物理页框号
b
b
b。取
x
x
x的低12位页内偏移量
x
11..0
x_{11..0}
x11..0，将物理页框号
b
b
b与页内偏移量
x
11..0
x_{11..0}
x11..0拼接，得到物理地址
y
=
b
∗
2
12
+
x
11..0
y=b*2^{12}+x_{11..0}
y=b∗212+x11..0。
算法的流程图如下：
算法时间复杂度分析：需要访问三次主存，一次访问页目录，一次访问页表，最后访问数据所在的物理地址，时间复杂度为
O
(
1
)
O(1)
O(1)。
算法空间复杂度分析：以空间换时间。虚拟地址本身为32位，为4GB。根据一级页号查找页框号，这个页框号为20位，为1MB。
算法正确性、有效性分析：算法会检测越界中断与缺页中断，在没有越界和缺页的错误时能正常运行。
伪代码
int x31_22=x>>22;//位运算，右移22位
if (flag[x31_22]==1){//要访问的页是否在主存
b1←x31_22地址内容;
x21_12=(x>>12)/(1<<22);//位运算，取x的21~12位
addr=x21_12+b1;
if (addr<(1<<20)-1);{//判断是否越界
b←addr地址内容;
y=(b<<12)+x%(1<<12);//拼接b与x的低12位
}
else 越界中断
}
else 缺页中断