在操作系统中分页-实现算法解析

分页是一种内存管理方案, 它消除了对物理内存连续分配的需求。此方案允许进程的物理地址空间不连续。

• 逻辑地址或虚拟地址(以位表示)：CPU生成的地址
• 逻辑地址空间或虚拟地址空间(以字或字节表示)：程序生成的所有逻辑地址的集合
• 物理地址(以位表示)：内存单元上实际可用的地址
• 物理地址空间(以字或字节表示)：对应于逻辑地址的所有物理地址的集合

例子：

• 如果逻辑地址= 31位, 则逻辑地址空间= 231字= 2 G字(1 G = 230)
• 如果逻辑地址空间= 128 M个字= 27* 220字, 然后逻辑地址=日志2227= 27位
• 如果物理地址= 22位, 则物理地址空间= 222字= 4 M字(1 M = 220)
• 如果物理地址空间= 16 M字= 24* 220字, 然后物理地址=日志2224= 24位

从虚拟地址到物理地址的映射是由作为硬件设备的内存管理单元(MMU)完成的, 这种映射称为分页技术。

• 物理地址空间在概念上分为许多固定大小的块, 称为镜框.
• 逻辑地址空间也分为固定大小的块, 称为页数.
• 页面大小=框架大小

让我们考虑一个例子：

• 物理地址= 12位, 然后物理地址空间= 4 K个字
• 逻辑地址= 13位, 然后逻辑地址空间= 8 K个字
• 页面大小=框架大小= 1 K个字(假设)

CPU生成的地址分为

• 页数(p)：表示逻辑地址空间或页码中的页面所需的位数
• 页面偏移量(d)：表示页面中特定字或逻辑地址空间的页面大小或页面或页面偏移量的字数所需的位数。

物理地址分为

• 帧号(f)：表示物理地址空间或帧号的帧所需的位数。
• 帧偏移(d)：表示帧中特定字的位数或物理地址空间的帧大小或帧或帧偏移的字数。

页表的硬件实现可以通过使用专用寄存器来完成。但是只有页表较小时, 页表寄存器的使用情况才令人满意。如果页表包含大量条目, 那么我们可以使用TLB(转换后备缓冲区), 这是一种特殊的, 小型的, 快速查找的硬件缓存。

TLB是关联的高速内存。

TLB中的每个条目都由两部分组成：标签和值。

当使用该内存时, 一个项目与所有标签同时进行比较, 如果找到该项目, 则返回相应的值。

主存储器访问时间= m

如果页表保存在主存储器中,

有效访问时间= m(用于页表)+ m(用于页表中的特定页)

GATE关于分页的问题：

GATE CS 2001问题46

本文的贡献者：维卡什·库马尔(Vikash Kumar)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。