1.作业内容

假设某系统的进程虚拟地址为32位，使用12位=4KB长度的页面，页表也是分页存储管理，每个页表表目占4 Bytes。请你：

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

2） 根据用户进程要访问的虚拟空间地址x xx，同时假设要访问的页面已在内存，设计一个查找该虚拟地址对应的内存物理页框号b bb和物理地址y yy的算法，并试分析算法的复杂度。要求页表结构尽量简洁，查找算法开销小。

2.解答

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

状态位P：指示该页是否已经调入内存。

访问字段A：记录本页在一段时间内的访问次数，供置换算法换出页面时参考。

修改位M：标识该页在调入内存后是否被修改过。如果应淘汰的页在执行中没有被修改过，不必调出，直接装入一个新页覆盖。若修改过，则需要调出到外存。

外存地址：指出该页在外存上的地址，通常是物理块号。

2）算法

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