1.作业内容

假设某系统的进程虚拟地址为32位，使用12位=4KB长度的页面，页表也是分页存储管理，每个页表表目占4 Bytes。请你：
1）设计一个页表管理的数据结构；
2） 根据用户进程要访问的虚拟空间地址$x$，同时假设要访问的页面已在内存，设计一个查找该虚拟地址对应的内存物理页框号$b$和物理地址$y$的算法，并试分析算法的复杂度。要求页表结构尽量简洁，查找算法开销小。

2.解答

1）设计一个页表管理的数据结构

状态位P：指示该页是否已经调入内存。
访问字段A：记录本页在一段时间内的访问次数，供置换算法换出页面时参考。
修改位M：标识该页在调入内存后是否被修改过。如果应淘汰的页在执行中没有被修改过，不必调出，直接装入一个新页覆盖。若修改过，则需要调出到外存。
外存地址：指出该页在外存上的地址，通常是物理块号。
按字节编址，使用32位虚拟地址。每个进程有的$2^{32}B=4GB$虚拟地址空间，使用$2^{12}B=4KB$的页面，$2^{32}/2^{12}=2^{20}$，即一个进程可以用$2^{20}$个页面，需要$\ge 20/8=3B$的表目，题目中取页表表目$4B$。则每个进程页表空间$2^{22}B=4MB$。$22+12>32$,所以页表不能全装在主存，需要用到二级页表。
低12位为页内偏移量，高20位采用二级页表。每个小页表可以放$2^{10}=1K$个页表表目，共$2^{10}=1K$个小页表。$2^{10}\ast 2^{10}\ast 2^{12}=2^{32}$，正好填满$32$位地址。为了对$1K$个小页表进行查找，需要一个页表表目，页表表目有$1K$个，共$10$位，为$31$~$22$位。小页表占$10$位，为二级页号，为$21$~$12$位。页面内的偏移量为$12$位，对应$4KB$的页面，为$11$~$0$位。

2）算法

先取地址的高$10$位($31$~$22$位)，在一级页表中查找而应页框号所在位置页表$x_{\mathrm{31..22}}$。即$x_{\mathrm{31..22}}=x/2^{22}$。访问$x_{\mathrm{31..22}}$，得到虚拟页号的物理页表起始地址$b_1$。再取$x$的$21$~$12$位，得到二级页号$x_{\mathrm{21..12}}=(x\mathrm{mod}{2}^{22})/2^{12}$。将$b_1$与$x_{\mathrm{21..12}}$相加得到新地址，访问该地址，得到物理页框号$b$。取$x$的低12位页内偏移量$x_{\mathrm{11..0}}$，将物理页框号$b$与页内偏移量$x_{\mathrm{11..0}}$拼接，得到物理地址$y=b\ast 2^{12}+x_{\mathrm{11..0}}$。
算法的流程图如下：

算法时间复杂度分析：需要访问三次主存，一次访问页目录，一次访问页表，最后访问数据所在的物理地址，时间复杂度为$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 缺页中断