详解操作系统分页

一、分段与分页

1.1 动机(MOTIVATION)

• Solution to fragmentation：permit the logical address space of processes to be noncontigunous

  分段和分页作为碎片问题的一个解决方案，允许进程的逻辑空间地址不是连续的

• The view of momory is different between

  • logical(programmer’s)：a variable-sized segments
  • physical：a linear array of bytes

  在开发人员眼中，内存就是一系列大小不等的段(包含变量、函数等)，对应于逻辑地址，而从物理地址的角度看，内存就是一个线性的字节数组

• The hardware could provide a memory mechanism that mapped the logical view to the actual physical memory

  需要硬件提供一种机制，将逻辑试图映射成实际的物理内存

1.2 分段(可变分区)

从开发人员角度看，程序由主函数和一组其他函数构成，包含各种数据结构(变量、结构体、对象、数组等)，所有的模块都是通过名字来引用的。

每个模块对应内存中大小不等的段，每个段有专门的用途，段的大小和用途相关

段和段之间不必连续存放(离散)

假设一个程序有A、B、C三个函数，将这三个函数分成3段，每个段内指令的逻辑地址都是从0开始，但是每一段的基址却是不同的

分段硬件：段基址(base register)、段限长(limit register)、段表

其中段表包含了段号、基址和限长

逻辑地址由段号和段内位移构成

地址转换的时候，根据逻辑地址的段号找到段表里面的记录，然后判断段内位移是否查过限长，如果不超过则计算物理地址

1.3 分页(固定分区)

• 基本方法

分页是基于连续内存分配中固定分区实现的，只不过分页是将内存分成较小的大小一致的分区，每个分区称为帧或页框

然后操作系统将应用程序分成多个与页框大小相等的页，然后给应用程序的每页分配一个页框的内存，同时用一张页表记录来记录程序的页号与内存页框号的映射关系

• 逻辑地址

  分页中的逻辑地址使用页号和页内位移来表示

• 物理地址

  首先根据逻辑地址的页号找到页表中对应的页框号，因为内存中每个页框的大小是固定的，可以直接判断程序指令逻辑地址对应的页内偏移是否超过限长，然后再进行地址转换

  物理地址 = 页框号*页框大小 + 页内位移

  physical address = frame_no * pagesize + offset

• 页面大小

  • 页大小(或页框大小)是由硬件定义的，每页的大小是2的幂次方，在512字节和1GB之间变化，依赖于电脑结构。常用大小为4K字节

  • 页的大小选择为2的幂次方是为了方便地址转换，不用进行算术运算

  • 如果一个程序的逻辑地址空间大小为2^{m，页的大小为2}n字节，那么一个逻辑地址高位的m-n比特表示页号，低位的n比特表示页内位移

    

1.4 分页与分段的区别

二、页表

2.1 PAGE TABLE

• The operating system maintains a copy of the page table fro each process

• This copy is used to translate logical address to physical address

• It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocate the CPU

  当进程被分配CPU时，CPU的调度程度使用它来定义硬件页表

• Paging therefore increase the context-switch time

  分页将造成进程上下文切换的一个开销，进程被分配CPU后，每次CPU都需要调入页表

2.2 分页

2.2.1 逻辑地址

在分页里面介绍了分页的逻辑地址是由页号和页内位移组成，但它是一个一维的结构

假设：page_size = 4 byte，程序有8条指令，每个指定对应一个字节，操作系统会将程序分成两个页，页号分别0和1，页内位移从0到3

从上面的图可以看出，分页后的逻辑地址对应的值与分页前程序每条指令对应的逻辑地址是一样的，整个程序的逻辑地址可以从0开始表示

2.2.2 Frame Table

在分页中，操作系统会维护一张页框状态表Frame Table，记录哪些页框已经被用，哪些可用

2.2.3 Page Table

页表Page Table是使用一个一维数组进行存储，其中数组的下标表示页号，索引值表示页框号

2.2.4 Page Size

如前面1.3分页中讲到的页面大小，如果逻辑地址长度为mbits，页面大小：2^nBytes

• 页内位移：n bits
• 页号：m-n bits

获取Linux系统页大小的命令：

lizhi@Dog-li:~$ uname -m
x86_64
lizhi@Dog-li:~$ getconf PAGESIZE
4096
#对应的页面大小的相关数值
m = 64  n = 12   
理论上页号占52bits，实际操作系统页号占 48-12=36bits

2.3 快表

2.3.1 PTBR

• The page table is kept in main memory,and a page-table base register(PTBR) points to the page table

  把页表存在主存里面，然后用一个页表基址寄存器存一个指向进程页表的指针

• Changing page tables requires changing only this one register,substantially reducing context-switch time

  每次进程上下文切换时，不需要来回加载保存和加载页表信息，只需要更改页表基址寄存器的指针即可

• With this scheme,two memory accesses are needed to access a byte(one for the page-table entry,one for the byte)

  用这种方案，每获取一个指令的需要访问两次内存，一次是获取页表，另一次是根据页表转换后的物理地址获取指令

2.3.2 TLB(快表)

• TLB(Translation Look-aside Buffer) is a kind of small,fast-lookup hardware cache.It is used with page tables in the following ways

  TLB是一种很小、查询速度很快的专用硬件缓存，配合页表使用

  • The TLB contains only a few of the page-table entries

    TLB只包含一个进程一部分页表内容

  • When a logical address is generated by the CPU,its page number is presented to the TLB

    当CPU为程序生成一个逻辑地址时，CPU将首先检查TLB种是否有对应的页号

  • If the page number is found,its frame number is immediately available and is used to access memory

    如果TLB中有这个页号，则对应的页框号当即可用去访问内存中的指令

  • If TLB miss,a memory reference to the page table must be made

    如果TLB中没有这个页号，则需要访问内存获取页框号，然后再访问内存中对应的指令(需要访问两次内存)

• PAGING TLB

  通过TLB计算物理地址的过程：

  

• TLB HIT RATIO(TLB命中率)

  The percentage of times that the page number of interest is found in the TLB is called the hit ratio

  从TLB中找到页号次数的备份比称为命中率

  An 80-percent hit ratio,for example,means that we find the desired page number in the TLB 80 percent time,If it takes 100 nanoseconds to access memory,find the effective memory-access time

  effective access time = 0.8 * 100 + 0.2 * 200 = 120ns

  访问TLB就能获取页号的概率为80%，则平均内存访问时间就是120ns

2.4 基于页的保护与共享

2.4.1 保护

为了防止地址转换(CPU计算程序页号)时出现异常，可在页表的每个条目设置一个“valid-invalid”比特位，用于表示该页的有效性

这个方法可以扩展以提供更好的保护级别，如：”只读“、”读写“、”可执行“

2.4.2 共享(pure code)

对于某些只读的代码，多个应用程序都会用到，则没必要在每个程序进程中为这些代码维护一份页表信息，只需要在内存中为这些代码维护一份页表信息即可，但这些页表项是只读的

2.5 多级页表

页表大小

假设CPU是32bits，采用的逻辑地址是32bits，那么进程的逻辑地址空间大小为2^32Bytes，即4GB

• 若页面大小是4K Bytes，则一个进程最多被分成1M个页面，也就是说进程的页表最多有1M个页表项
• 若每个页表项占用4Bytes，则每个页表最多占用4MBytes连续内存空间(1K个连续页框)

因为我们需要把页表也放在内存的页框中，但又没有这么大的连续内存空间，只能把页表进行拆分后放入页框中，那么我们就需要记录哪些页表存放在了那个页框里面，如上面的假设，每个页框大小为4KBytes，而每个页表项又占用4Bytes，那么一个页框可以存放1K个页表项，于是，就将页表项以1000个为单位分成页表页，即每个页表页存放1000个页表项，页表页的序号从0开始

页表页的结构如下：

逻辑地址

计算物理地址时，根据页表页号从页表页中找到对应的页框号，根据页框号，将页表从内存中取出，在根据页号从页表中找到对应的页框号，根据页框号和页内位移计算出物理地址

因为页表页也需要存放在页框中,如果页表页所需要的连续空间大小超过了页框大小,需要再对页表页进行拆分,形成三级页表

x86-64架构CPU采用的四级页表方案：

正如我们在2.2.4Page Size中说到的，Linux操作系统采用36bits来表示页号，36bits已经完全够用了