页表的三种常见结构
在前面的帖子中，我曾简单介绍了内存管理的分页式管理。我们都知道，每一个页面都是通过页表进行管理的。
而在前面的帖子中，我只简单讲述了下一级页表的结构。实际上，页表的结构有很多种，包括：分层分页、哈希页表和倒置页表等结构。
在这里，我跟大家简单谈谈分层分页、哈希页表和倒置页表这三种常见的页表结构，希望能对大家有所帮助。
分层分页
分层分页，即多级页表。以二级页表为例，将页表再进行分页，创建一个二级页表，里面存放的是二级页表项（类似于页表中存放的页表项），每一个二级页表项指向一个页表。（更高级的页表类似）
优点
由于多级页表在每一级中使用的页表项往往只是一部分（尤其是高级别的页表），因而高级页表中没有使用到的页表项不用再为其分配低级的页表，因此分层分页的页表结构可以大大节省页表所占用的空间。
缺点
查找和存储页表项时可能需要访问多个级别页表，消耗更多的时间。
哈希页表
页表中的每一项存放一个链表（会有多个不同的页号指向同一个页表项），链表中的每一个元素包括：页号、映射到物理内存的帧码（即物理地址基地址）、指向该链表的下一个元素的指针。
当要访问内存时：
1）首先根据逻辑地址的页号p找到页表中对应的页表项；
2）在该页表项的链表中寻找对应页号的元素；
3）将该元素的帧码base +逻辑地址的页偏移d（位的拼接），得到物理地址，进而访问内存。
优点
页表项的查找和存储时间大大缩短。
缺点
需要解决哈希冲突以及固定的哈希大小问题。
倒置页表
标准页表是每一个进程都有属于自己的一个页表；当进程数量多时，需要创建大量的页表，占用大量的内存。为了减少内存的消耗，引入倒置页表，所有进程共用一个倒置页表。倒置页表的每一项包含：进程id、页号；倒置页表是按照物理内存从小到大排序的。
在倒置页表的机制下，虚拟地址表示为一个三元组：进程id，页号，页偏移。
当要访问内存时：
1）首先根据逻辑地址的进程id和页号，在倒置页表中寻找与之相同的进程id和页号所在的页表项；
2）寻找到的页表项的索引即为物理内存的帧号（因为倒置页表是按物理帧从小到大排的）；
3）将找到的帧号+逻辑地址的页偏移p（位的拼接），得到物理内存地址，进而访问物理内存。
优点
减少了多个页表占用的内存。
缺点
页表项的数目与物理内存的帧数相同，而且查找页表项时要一个一个遍历，无法快速查询，耗费大量的时间。
以上便是本次帖子的全部内容。由于楼主对于该方面知识了解得也不够多，因此只作了简单的介绍。如果有讲得不正确的地方，欢迎大家指出
。
#操作系统##面试题目#。 
查看11道真题和解析
美团一面2072人在聊