一、分页系统

1、段页式系统

段页式内存管理的模型中，逻辑地址（虚拟地址）先根据分段系统转换成线性地址，然后线性地址在分页系统中查询，Linux中弱化了分段机制，只在80x86处理器中使用分段。$Linux$采用了4级分页模型来适应多种硬件环境，但在80x86处理器中（IA-32架构）中使用二级分页模型，即页目录表和页表结合，将第2、3级页表整合进了页全局目录中。在64位体系结构中，2级页表不再适用，因此IA-64体系结构采用了3级页表，64位地址中39位（9+9+9+12）来寻址。

2、自己做的页目录表和页表

这是我本科做实验时自己做的页目录和页表。其中用户程序使用$\verb+0x00~~0xcfffffff+$这3GB逻辑地址空间，系统程序使用$\verb+0xc0000000~~0xffffffff+$这1GB逻辑地址空间。在物理内存中，$\verb+0x00~~0xfffff+$这1MB空间留给BIOS、MBR、Loader、中断向量表，页目录表位于内存$\verb+0x100000~~0x100fff+$，大小共1KB，含1024个页目录项。页表紧跟着页目录表后面，页表0的地址为$\verb+0x101000~~0x101fff+$，页表1的地址为$\verb+0x102000~~0x102fff+$，依次类推。
页目录表中的第$\verb+0~~767+$页目录项映射到低3GB逻辑内存中，而第$\verb+768~~1022+$页目录项映射到高1GB逻辑内存中，1023号页目录项指向页目录表自己，而768号页目录项指向页表0，769号页目录项指向页表1，以此类推。页表0的第一个页表项指向地址$\verb+0x00+$为起始的4KB物理页（最上面的物理页0）。

注意所有用户的页目录表的$\verb+768~~1022+$项完全相同，因为都指向共享的内核空间。创建进程时从页目录表的第$\verb+768~~1022+$拷贝即可（图片中写错字了，应该是页目录表而不是页表）。

二、Linux内存管理

这里以一个用户程序$\verb+abc.c+$为例来探究Linux系统的内存管理策略。程序如下：

#include <string.h>
#include <stdlib.h>

char bar[3968]="\n";
char foo[4096]="this is not a test\n";

void output_loop(char * str)
{
  int i;
  for(i=0; i<20; i++){
    write(2, str, strlen(str));
    sched_yield();
  }
}

void main(){
  int pid1, pid2, status;

  write(2, foo, strlen(foo));
  strcpy(foo, "you are modified\n");
  write(2, foo, strlen(foo));
    
  if (!(pid1 = fork())){
    output_loop("B  ");
    exit(0);
  }

  if (!(pid2 = fork())){
    output_loop("C  ");
    exit(0);
  }

  output_loop("A  ");
  waitpid(pid1, &status, 0);
  waitpid(pid2, &status, 0);
  write(2, "\n", 1);

  while(1);

  exit(0);
}

1、进程地址空间

abc程序的逻辑地址空间（右侧）如下图所示。其中用户程序使用$\verb+0x00-0xcfffffff+$这3GB逻辑地址空间，$\verb+abc+$程序的代码段为$\verb+0x08048000-0x080e8fff+$这161个页面，代码段为$\verb+0x080e9000-0x080ecfff+$这4个页面。数据段只包含$bar$和$foo$这两个变量对应的字符串，$bar$的地址为$\verb+0x080e9000+$，虽然只有3968个字节，但是也分配了2个页面（4096个字节），占用数据段中的第0、1个页面，$foo$的地址为$\verb+0x080eb000+$，占用数据段中的第2、3个页面。$\verb+task_struct+$为Linux的进程控制块PCB，里面包含指向内存控制块$\verb+mm_struct+$（所有内核进程的$\verb+mm_struct+$全部内容均为0）的指针。$\verb+mm_struct+$包含指向页目录表的指针$\verb+pgd+$以及指向$\verb+vm_area_struct+$线性区结构的指针$\verb+mmap+$，结构体$\verb+vm_area_struct+$描述的对应逻辑段的起始和结束逻辑地址等信息。所有$\verb+vm_area_struct+$组织成一棵红黑树。
Linux分页系统以及abc程序的地址空间
$foo$字符串的逻辑地址为$\verb+0x080eb000+$，高10位$\verb+0x20+$表示从页目录表的第$\verb+0x20+$项（对应的偏移为$\verb+0x80+$，一个页表项4个字节）取出页表地址，注意该处的$\verb+0x07518067+$的低12位为标志，不表示地址，页表的单位为4KB，故页表地址的低12位总是0。然后从$foo$字符串的中间10位$\verb+0xeb+$对应的偏移$\verb+0x3ac+$从页表中取出页帧的起始地址$\verb+0x065c6000+$，最后与$foo$字符串低12位页内偏移$\verb+0x000+$直接相加就可以得到$foo$字符串的物理地址。

2、Linux的页描述符和页高速缓存

内存中的一个页称为页帧($page\ frame$)，一个页帧对应一个32字节的页描述符$\verb+struct page+$来描述，页帧描述符数组$\verb+struct page mem_map[]+$来描述所有的页帧，占整个内存空间的$\frac{32}{4096}=\frac{1}{128}$。
为了更快速的读取文件，Linux在$\verb+abc+$程序刚开始运行时，数据段还没有被访问前就已经把文件中的数据段缓存入了内存中，但是页目录表和页表并没有内容指向这部分缓存，Linux只会在访问数据段中的变量时才会分配页目录项和页表项（这也叫做“请求调页”），缓存的页框称为页高速缓存。页高速缓存的每一个页框对应一个页描述符，页描述符用基树组织起来，如下图所示。

本例中$\verb+abc+$程序的基树如下图所示：

图中数据段的页描述符的偏移为$\verb+0xa0+$，应该位于第2个基树叶子节点的第32个槽，该槽中的指针指向对应的$\verb+struct page+$，再指向对应的页帧缓存。

三、Linux缺页处理

1、缺页处理流程

这里以$\verb+abc+$程序中的三个函数来分析缺页处理。

1
2
3

write(2, foo, strlen(foo));
strcpy(foo, "you are modified\n");
write(2, foo, strlen(foo));

执行第一个write系统调用

数据段包含$\verb+bar+$和$\verb+foo+$字符串，$\verb+foo+$字符串的起始地址为$\verb+0x080eb000+$，占2个页帧。程序执行到$\verb+write+$函数前一刻，数据段作为页高速缓存，缓存在了内存中，但是页目录项和页表项均为0，没有指向这个页缓存。程序在内核态往虚拟地址0x080ecf20(数据段第4页)写内容，（我也不知道写的是什么内容，可能是初始化的信息），发现页目录项为0。
第一次缺页时的初始状态
此时引发缺页异常，执行$\verb+__do_page_fault+$缺页处理函数，执行$\verb+do_cow_fault+$写时复制，修改页目录项，但页表项仍然全0，再从$\verb+0x065c9000+$拷贝数据到另一片内存$\verb+0x01b35000+$中，并修改第4个页表项为$\verb+0x01b35067+$(最低位为7表示该页面可写)，指向拷贝的内存。最后回到引发缺页的指令，重启该指令往逻辑地址$\verb+0x080e9fc4+$（也就是物理地址$\verb+0x01b35000+$处）写内容。
注意，页表项不能直接指向页缓存$\verb+0x065d1000+$处并向该地址写内容，必须先拷贝内容到另一块内存中，否则页缓存$\verb+0x065d1000+$成为脏页面，脏页面的内容会写回磁盘中，从而引起磁盘上程序内容的改变。
第一次缺页处理
然后程序在用户态往$\verb+0x080e9fc4+$(数据段第1页)写内容，发现页帧不存在，开始缺页处理，执行$\verb+do_cow_fault+$函数，从$\verb+0x065c6000+$拷贝数据到另一片内存中$\verb+0x01b34000+$，并修改第一个页表项指向拷贝的内存。
第二次缺页处理
随后是第3次缺页异常，在用户态往$\verb+0x80ea040+$(数据段第2页)读内容，发现页帧不存在，引发缺页处理，执行$\verb+do_read_fault+$函数，因为只是读该页面，不需要写页面，所以修改第2、3个页表项指向第2、3个页帧缓存$\verb+0x065cf000+$和$\verb+0x065d0000+$即可，页表项的最低4位为5表示该页面只读。

之后是第4次缺页异常，程序在用户态往$\verb+0x80ea040+$(数据段第2页)写内容，发现该页面只读，执行$\verb+do_wp_page+$函数，从第2个页表项指向的$\verb+0x065cf000+$拷贝内容到新的内存地址$\verb+0x07d85000+$并修改页表项指向拷贝的新页帧。我发现程序往这个地址写的竟然是空字符串””。

此时程序刚刚进入$main$函数，然后终端打印$\verb+foo+$字符串，$\verb+write+$结束。全局的视角看起来应该是这样：

执行strcpy函数

$\verb+strcpy+$函数将$\verb+foo+$字符串的内容改写成”you are modified.”。此时$\verb+foo+$字符串所在的地址为第3个页表项指向的页面缓存。在用户态往$\verb+0x80eb000+$(第3页，即foo字符串地址)写内容，发现该页面只读，执行$\verb+do_wp_page+$函数，从第3个页表项指向的$\verb+foo+$字符串地址$\verb+0x065d0000+$拷贝字符串到内存$0x01b3a000$处并修改页表项指向新拷贝的内存地址，再往新的页帧写字符串$\verb+”you are modified”+$。

$\verb+strcpy+$函数结束时4个页表项都将最低为从7改为5，此时页面只读，不可写，然后$\verb+strcpy+$结束，执行$\verb+write+$函数，打印新的字符串。

2、回写脏页面

若在执行$\verb+strcpy+$函数之前，把第3个页表项标志位改为7结尾，页面变为可写，在执行$\verb+strcpy+$函数时，新字符串的将会被写入第3个页表项指向的$\verb+foo+$字符串地址$\verb+0x065d0000+$中，该页帧成为脏页面，回写到磁盘上，磁盘上的程序内容也会被更改，下次执行abc程序时直接输出新字符串。

下次执行程序时的结果：

两次打印的都是修改后的字符串。

A CS Student's Odyssey

操作系统内存管理