目录

一、知识点

1、计算机体系结构/内存层次

1.1、计算机体系结构

1.2、地址空间&地址生成

1.3、伙伴系统（Buddy System）

2、非连续内存分配

2.1、段式存储

2.2、页式存储

2.3、快表和多级页表

2.4、段页式存储

3、X86的特权级与MMU

3.1、段机制和页机制概述

3.2、分段

3.3、特权级检查

3.4、X86特权级切换

3.5、分页

二、练习解答

1、实现first-fit连续物理内存分配算法

2、实现虚拟地址对应的页表项

3、释放某虚地址所在的页并取消对应二级页表项的映射

---

一、知识点

下面介绍物理内存存储的相关知识点。

1、计算机体系结构/内存层次

计算机系统中，除了处理能力之外，还有存储能力。存储能力指的是有一系列的存储介质，在存储介质中存储代码和数据。体系结构中就约束了哪些地方存储数据，既包括寄存器，也包括内存和外存。这些存储介质的速度、性能不同，为了组织合理的结构，采用层次结构。针对层次结构下的存储单元，操作系统需要对其管理。

1.1、计算机体系结构

针对内存的管理要求，在系统结构中哪些因素对其有影响？计算机系统结构中包括CPU、内存、I/O设备，见图1-1。

图1-1计算机体系结构

对计算机体系结构进一步的分解，得到内存层次结构，见图1-2。CPU中的存储介质有L1缓存、L2缓存，它的访问速度较快，但价格昂贵。

图1-2 内存层次结构

L1缓存和L2缓存是由硬件MMU管理。如果L1缓存、L2缓存已经存在所需数据，那么CPU直接从缓存中获取数据。如果高速缓存中没有命中数据，那么就访问内存。内存中也访问不到，就采用缺页处理访问外存。对于内存和外存的管理，由操作系统管理。

操作系统管理内存和外存，需要达到什么目标？在下图中，程序的介质是内存、外存。通过地址总线访问存储空间，在32位的计算机中，一次访存的数据量是4Byte。用户希望每个进程是独立的，有独立的地址空间，用户也希望进程可以共享操作系统内核。不同的内存、外存具有不同的物理地址空间，显然跟用户期望的进程地址空间不同。在进程和操作系统内核中，地址空间称为逻辑地址空间，逻辑地址需要经过MMU单元转换成物理地址。根据以上对用户特点、内存外存特点分析，可以总结出操作系统内存管理的目标：1）抽象，每个进程具备相同的逻辑地址空间。2）保护，每个进程具备独立的地址空间。3）共享，每个进程可以共享相同的内存。4）虚拟化，虽然物理内存大小有限，但是经过虚拟内存管理，给用户看到的地址空间大。

图1-3 操作系统的内存管理

为了达到操作系统内存管理的目标，有哪些内存管理方式呢？第一种办法是重定位relocation，将内存整块的搬移到物理地址空间中，每个地址用段地址加偏移表示。第二种办法是分段segmentation，用户有时候期望是不连续的区域，如数据、代码、堆栈，这个时候采用分段方式。第三种办法是分页paging，在分段的时候，仍然要求一段是连续的。这个时候需要用最小的单位来构建连续的区域，这个单位是一页，通常是4KB。第四种办法是虚拟存储virtual memory，用户希望程序存储到磁盘上，这样进程的逻辑地址空间可能比实际的物理内存地址空间还大。

1.2、地址空间&地址生成

从程序里写的符号到最后总线上出现的物理地址，这中间存在一个转换的过程。接下来看看地址空间的定义。

物理地址空间。机器总线上看到的地址是物理地址，所有物理地址所构成的空间叫做物理地址空间。物理地址是唯一的，然而对于编写程序是非常不方便的。因为在编写程序之前，并不清楚程序应该放在哪一个地址中。在这个时候，程序需要用到的是逻辑地址。

逻辑地址空间。逻辑地址是CPU运行的时候进程看到的地址，通常情况下是可执行文件对应的那个区域。例如程序mov %eax,$0xfffa620e，这个地址从进程地址空间中来。

逻辑地址的生成。逻辑地址的生成有如下的步骤，1）编译，高级语言程序，通过编译生成了CPU能够识别的指令的汇编码，但仍然用的是符号名字。2）汇编，通过汇编将汇编源代码变成二进制的代码，这时候变成CPU能够识别的指令。3）链接，通过链接器，把多个模块、函数库合并在一起，排列成一个线性序列，它是按照从0开始的大小排列的。4）程序加载，通过操作系统提供的加载器将程序的地址整体平移，形成CPU能够看懂的进程地址。

图1-4 逻辑地址生成

地址生成的时机和限制。1）编译时，假设起始地址已知，如果起始地址改变，必须重新编译。假设使用的是功能机，他的程序都是编译好的，但是不允许装新软件。2）加载时，如编译时起始位置未知，编译器需要生成可重定位的代码（relocatable code），在加载的时候生成绝对地址。比如智能手机，买到智能手机后，往里面添加自己的程序。编写程序的人没有办法知道这个程序最后加载到手机的什么位置。3）执行时，执行时代码可以移动，需要地址转换（映射）硬件支持。即前面使用的时候一直是相对地址，执行到这条指令的时候，才知道它确切访问的地方，这种情况出现在我们使用虚拟存储的系统中。这样的好处是程序执行的指令在物理位置中可以挪，灵活性高。前两种存在运行起来之后，不能变更地址的问题。

图1-5 地址转换与寻址

地址检查。一条movl %eax,$0xfffa620e，在执行的过程中，会产生逻辑地址。比如这个逻辑地址$0xfffa620e是访问数据段数据，数据段有一个段长度和段基址。如果逻辑地址（偏移）超过了段长度，这时候访问非法。如果检查结果合法，它就会和段基地址叠加到一起，然后访问物理地址。

图1-6 地址检查

1.3、伙伴系统（Buddy System）

在给进程分配一个不小于指定大小的连续物理内存区域问题中，一个著名的分配方式就是Buddy System。

Buddy System的思路。整个可以分配的分区大小一定是。如果需要的分区大小满足时，就把整个块(大小)分配给该进程。1）如果，将大小为的当前空闲分区划分成两个大小为的空闲分区。2）重复划分过程，直到，并把一个空闲分区分配给该进程。

Buddy System的数据结构。在该系统中，空闲块由大小和起始地址构成。初始状态，只有一个大小为的空闲块。

Buddy System的分配过程。由小到大的在空闲块数组中找到最小的可用空闲块。如果空闲块过大，就对可用空闲块进行二等分，直到得到合适的可用空闲块。

Buddy System的释放过程。把释放的块放入空闲块数组中，合并满足合并条件的空闲块。

在下图中是基于Buddy System的分配和释放过程。Request 100K时，会将1M空间的块，重复二等分，直到分到128K，满足分配条件64K<100K<=128K，于是将该128K分配给A。Release C时，先将C释放掉，然后C与相邻的64KB合并成新的空闲块。

图1-7 Buddy System分配与释放

Buddy System的合并条件。

1）大小相同的块，大小为。

2）地址相邻。

3）低地址空闲块起始地址为的位数。

关于Buddy System的合并条件如何理解？在下图中，是一个Buddy System内存块分配的例子，通过这个例子，可以用来解释合并条件。

图1-8 Buddy System内存块分配

空闲块可以表示成如下的序列，其中每个序列用块大小和块开始地址表示。

A(128,0) C(64,2^7) 64(64,2^7+2^6) 256(256,2^8) D(256,2^9) 256(256,2^9+2^8)

其中块C(64,2^7)和块64(64,2^7+2^6)是地址相邻的，因为他们的开始地址最高位相同，都是2^7。其中块C低地址块，它的起始地址为的位数。

2、非连续内存分配

在连续分配中，虽然分配的方式简单，但是也存在很多的缺点。连续分配要求分配给程序的物理内存必须连续，即使是连续分配，也存在外碎片和内碎片的问题。一旦程序加载到内存中，内存分配的动态修改变得困难。此外也很难有足够的连续内存给进程，内存的使用效率低。此时，非连续分配的目标就是提高内存利用效率和管理效率，具体而言是，1）进程不在要求连续的物理地址空间。2）允许进程之间共享代码和数据。3）支持动态加载和动态链接。

在实现上述的目标中，存在如下的现实问题。1）如何解决虚拟地址到物理地址的转换？一个逻辑地址在不连续分配的策略中，会转换到另一个不连续的空间中。这种转化存在两种方式，一种是硬件，另外一种是软件。硬件实现地址转换开销小，但是容量有限。而操作系统软件实现开销大，但是容量相对大很多。2）非连续分配硬件机制中，如何选择非连续分配中的内存块大小？这里分配内存大小的方式存在两种，一种是段式存储管理（Segmentation），另一种是页式存储管理（Paging）。段式存储分配的空间大，以一个段为单位，但是要求内存空间连续。段与段之间可以放在不同的区域。页式存储分配的单元是Page，大概4KB，要求空间不连续。

2.1、段式存储

段地址空间。进程的段地址空间由多个段构成。虽然逻辑地址空间段与段是连续排列的，但是在物理地址空间，段与段之间是不连续的。逻辑地址空间的段地址，需要转换成物理地址空间的地址，如何转换就是段式存储管理。

图2-1 段地址空间

段地址访问方式。段表示的是访问方式和存储数据属性是一致的地址空间，它对应一个连续的内存“块”，若干个段构成进程的地址空间。段的访问可以由二元组（段号s，段内偏移addr）构成。

图2-2 段地址访问方式

段的访问硬件机制如下。1）CPU访问程序的逻辑地址，逻辑地址由段号和偏移构成。CPU通过段号查找段表，获得该段的基地址及该段的长度。段表是可以通过操作系统软件设置。2）将段的长度和偏移做比较，如果偏移地址合法，那么偏移加上段的基地址构成物理地址。

图2-3 段的访问硬件机制

2.2、页式存储

页式存储的基本概念。1）页帧（frame）。在页式存储中，把物理的页面分成大小相同的基本分配单元。为了地址对齐，通常式2的n次方，如512，4096，8192。 2）页面（Page）。在逻辑地址空间中，也要把地址空间划分成相同大小的基本分配单位。帧和页的大小必须相等。3）页面到页帧的转换。这里需要将逻辑地址转换成物理地址，而页表中存储了地址转换关系。为了加快这种转换，采用硬件MMU/TLB。

页帧。页帧用二元组（f，o）表示，f表示帧号，一共有F位，表示共有个帧。o表示帧内偏移，一共有S位，表示共有个字节。那么物理地址=f*+o。

图2-4 页帧表示

页。页用二元组（p,o）表示，p表示页号，一共有P位，表示共有个页。o表示页内偏移，一共有S位，表示每页共有个字节。通常页号不等于帧号，而页内偏移等于帧内偏移。

图2-5 页表示

有了页和页帧，那么此时需要进行逻辑地址到物理地址的转换，需要页号到帧号的转换。这个转换在逻辑地址空间式连续的，在物理地址空间是不连续的。在转换的过程中，不是所有的页号都有对应的帧号。

页式存储的地址转换。页号转换成帧号，是通过页表完成的。1）CPU访问逻辑地址（p+o），通过页号p查找页表，获得帧号f。2）根据查找的数据帧号f，计算物理地址。

图2-6 页地址转换

页表。每一个进程都对应一个页表。在页表中，每一个物理页面对于一个页表项，它完成逻辑页号到物理页号的转换。页表项中的内容会随着进程的运行而动态的改变。这个表存放在页表基址寄存器中。

图2-7 页表

2.3、快表和多级页表

快表是通过缓存的方式减少对内存的访问，从而提高速度。而多级页表是通过间接引用的方式来减少页表的长度。

快表（TLB）。就是把CPU近期访问过的页表项存放到CPU中。1）CPU在访问逻辑地址（p+o），首先访问TLB。2）因为之前没有访问过该物理帧号，所以在TLB中没有命中，此时CPU访问内存。3）访存完成后将页号和帧号对应关系缓存到TLB中。4）下次再次访问逻辑地址（p+o），访问TLB，从而获得帧号，并计算出物理地址。

图2-8 快表访问

二级页表。1）将20位的地址总线切分成三段（p1,p2,o），CPU访问逻辑地址（p1,p2,o）。2）通过固定寄存器CR3和p1，获取一级页表项内容。3）通过一级页表项内容和p2，获得二级页表项内容f。4）计算物理地址f*+o。

图2-9 二级页表访问

2.4、段页式存储

段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。段式存储、页式存储能否结合？答案是在段的基础上给每个段加一级页表。

图2-10 段页式存储

3、X86的特权级与MMU

操作系统加上CPU给应用程序提供了一个隔离空间，这里需要一种保护机制，此外应用程序不能够随便的访问操作系统的空间。操作系统利用CPU的硬件机制建立逻辑地址向物理地址的映射关系，这实际上是内存管理的重要内容。

3.1、段机制和页机制概述

在X86系统中，正好支持分段和分页这两种机制。将逻辑地址转换成线程地址空间的过程，称为分段，而将线性地址转换成物理地址空间的过程称为分页。分段和分页的过程如下图所示。

图3-1 分段和分页

分段提供一种划分处理器地址内存空间成更小的保护地址空间，这种地址空间称为段。段可以用来维持一个程序的代码、数据、堆栈。或者用来维持一个系统的数据结构，如TSS、LDT。

3.2、分段

为了更好的解释分段的概念，需要弄清楚段寄存器、段选择子、全局描述符表。

段寄存器。为了减少地址转换时间和代码的复杂程度，处理器提供寄存器，最多可以容纳6个段选择子，见下图。每个段寄存器支持一种特定的内存引用（代码、堆栈、数据）。对于任何的一种程序执行，至少代码段CS、数据段DS、堆栈段SS寄存器必须载入有效的段选择子。处理器也会提供三种额外的段寄存器（ES、FS、GS），这些寄存器可以做额外的数据段选择。

图3-1 段寄存器

段选择子。一个逻辑地址由段选择子和段偏移构成。一个段选择子由16bit的标志符构成，它并不直接指向那个段，但是定义那个段的段描述符。一个段选择子包括以下的项目。

Index。(Bits 3 到15)--一共有8192个描述符在GDT或者LDT中，选择其中一个描述符，处理器将index乘以8（段描述符中的字节数，每一个段描述符占用8字节，这样才能查找相应的段描述符），然后加上GDT或者LDT的基地址（基地址相应的来自GDTR或者LDTR寄存器）。

TI（table indicator）flag。Bit2--表示描述表的用途：清除这一位表示选中GDT；设置这一位表示选中LDT。

Requested Privilege Level(RPL)。（Bits0 和Bits1）--描述选择子的特权级，特权级的凡是是0到3，其中0是最高的特权级。

图3-2 段选择子

在bootasm.S文件中，如下是一段设置段选择子的代码，其中“ljmp $PROT_MODE_CSEG, $protcseg”设置了CS的段选择子，并切换为32位代码段模式，其中“movw %ax, %ds”设置了DS的段选择子。

.set PROT_MODE_CSEG,        0x8                     # kernel code segment selector
.set PROT_MODE_DSEG,        0x10                    # kernel data segment selector
//1、bootasm.S设置代码段和数据段选择子
finish_probe:
    # Switch from real to protected mode, using a bootstrap GDT
    # and segment translation that makes virtual addresses
    # identical to physical addresses, so that the
    # effective memory map does not change during the switch.
    lgdt gdtdesc
    movl %cr0, %eax
    orl $CR0_PE_ON, %eax
    movl %eax, %cr0
    # Jump to next instruction, but in 32-bit code segment.
    # Switches processor into 32-bit mode.
    ljmp $PROT_MODE_CSEG, $protcseg

.code32                                             # Assemble for 32-bit mode
protcseg:
    # Set up the protected-mode data segment registers
    movw $PROT_MODE_DSEG, %ax                       # Our data segment selector
    movw %ax, %ds                                   # -> DS: Data Segment
    movw %ax, %es                                   # -> ES: Extra Segment
    movw %ax, %fs                                   # -> FS
    movw %ax, %gs                                   # -> GS
    movw %ax, %ss                                   # -> SS: Stack Segment

在操作系统启动之前，设置了段描述符表，它是通过“lgdt gdtdesc”实现的。bootloader和kernel的段开始地址是0，结束地址是0xffffffff，特权级均是0级别。可以观察到，先是通过lgdt指令加载段描述符，然后通过其他指令加载段选择子。也可以观察到段描述符的序号和段寄存器的段选择子序号需要一一对应。

.data
# Bootstrap GDT
.p2align 2                                          # force 4 byte alignment
gdt:
    SEG_NULLASM                                     # null seg
    SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff)           # code seg for bootloader and kernel
    SEG_ASM(STA_W, 0x0, 0xffffffff)                 # data seg for bootloader and kernel

gdtdesc:
    .word 0x17                                      # sizeof(gdt) - 1
    .long gdt                                       # address gdt

段描述符。段描述符是GDT或者LDT中的一种数据结构，它能够提供一个段的大小和位置，还有访问控制，以及状态信息。段描述符通常由编译器，链接器，加载器，或者操作系统创造，但不是应用程序。

图3-3 段描述符

中断/陷入门描述符。中断门描述符会包含三种门描述符号中的其中一种。1）任务门描述符。2）中断门描述符。3）陷入门描述符。下图显示了任务门，中断门，陷入门描述符的格式。在GDT或者LDT中，任务门的格式是相同的。这三种门描述符均放在中断描述符表格中，每个门描述符占用4字节。

图3-4 中断/陷入门描述符

当中断或者陷入发生的时候，程序的运行情况见下图。一个中断门或者陷入门引用了一个异常或者中断处理程序，该程序运行的环境是当前执行程序的上下文。门描述符中的段选择子指向GDT或者LDT中的段描述符。门描述符中的偏移字段指向异常或者中断程序执行的开始位置。

图3-5 中断响应过程

中断描述符表的初始化，在全局描述符初始化之后。在ucore OS中，一共有256个门描述符，有关初始化的代码如下：

/* *
 * Interrupt descriptor table:
 *
 * Must be built at run time because shifted function addresses can't
 * be represented in relocation records.
 * */
static struct gatedesc idt[256] = {{0}};

static struct pseudodesc idt_pd = {
    sizeof(idt) - 1, (uintptr_t)idt
};

/* idt_init - initialize IDT to each of the entry points in kern/trap/vectors.S */
void
idt_init(void) {
     /* LAB1 YOUR CODE : STEP 2 */
     /* (1) Where are the entry addrs of each Interrupt Service Routine (ISR)?
      *     All ISR's entry addrs are stored in __vectors. where is uintptr_t __vectors[] ?
      *     __vectors[] is in kern/trap/vector.S which is produced by tools/vector.c
      *     (try "make" command in lab1, then you will find vector.S in kern/trap DIR)
      *     You can use  "extern uintptr_t __vectors[];" to define this extern variable which will be used later.
      * (2) Now you should setup the entries of ISR in Interrupt Description Table (IDT).
      *     Can you see idt[256] in this file? Yes, it's IDT! you can use SETGATE macro to setup each item of IDT
      * (3) After setup the contents of IDT, you will let CPU know where is the IDT by using 'lidt' instruction.
      *     You don't know the meaning of this instruction? just google it! and check the libs/x86.h to know more.
      *     Notice: the argument of lidt is idt_pd. try to find it!
      */
	//1)where are the entry addrs of each Interrupt Service Routine
	extern uintptr_t __vectors[];//reference to array __vectors from kern/trap/vector.S
	int i;
	//2)setup the entries of ISR in IDT
	for(i=0;i<sizeof(idt)/sizeof(struct gatedesc);i++){//idt is 256*8=2048Bytes
		//SETGATE in mm/mmu.h
		//Code segment selector GD_KTEXT
		//Offset in code segment __vectors[i],which means Interrupt Service Routine entry
		//Descriptor Privilege Level DPL_KERNEL
		//set kernel interrupt,ring 0
		SETGATE(idt[i],0,GD_KTEXT,__vectors[i],DPL_KERNEL);
	}
	//3)let cpu know where is the IDT
	//set user interrupt,ring 3
	SETGATE(idt[T_SWITCH_TOK], 0, GD_KTEXT, __vectors[T_SWITCH_TOK], DPL_USER);
	//load all user/kernel interrupt description
	lidt(&idt_pd);
}

3.3、特权级检查

在代码执行的过程中，特权级的检查是一个重要的问题。特权级检查中，主要比较的是段选择子中的CPL/RPL与段描述符中的DPL，见下图中段选择子和段描述符。

图3-6 段选择子和段描述符

比较的规则见下图。例如：“movw $30,%ax”指令执行的时候，CPU访问的是CS:IP代码段，同时由于访问内存$30（数据段），CPU也会访问数据段DS:BX。那么指令“movw $30,%ax”执行的时候，既访问了代码段，又访问了数据段。所以特权级检查的权限是MAX(CPL,RPL)<=DPL[段]。

图3-7 特权级检查规则

例如：“int 0x80”指令执行的时候，这个指令期望的是用户态的代码访问内核态相关代码执行。在用户态的时候，访问了代码段CS:IP，此时CPL=03。要让程序能够访问门，必须保证请求的CPL<=DPL[门]，通过门之后，进入内核代码段，此时请求的CPL>=DPL[段]。达到以上的两个检查之后，用户态应用程序就可以跳转访问内核态的代码了。

3.4、X86特权级切换

特权级的切换，是由中断或者异常触发的。在ucoreOS中，可以从ring0切换到ring3，也可以从ring3切换到ring0。

从ring0切换成ring3，在之前就已经将SS(RPL=3)和CS(RPL=3)压入栈内存中。当IRET指令执行的时候，栈内存中的这些数据退栈，数据恢复到相关的寄存器中。

图3-8 ring0切换到ring3

从ring3切换到ring0，需要将若干寄存器的值压入到栈内存中，其中SS(RPL=3)和CS(RPL=3)。

图3-9 ring3切换到ring0

有关用户态和内核态特权级切换的中断执行过程详细解释，见《X86中断栈执行过程分析》。

在特权级切换后，切换到另一个特权级后，程序怎么知道CS/SS位于什么地方呢？它的CS和EIP表明了它的地址，地址可以通过IDT描述符表，里面建好了当产生某个中断，然后跳转到某个地方执行，有关具体的细节见3.2节分段--中断/陷入门描述符。SS的具体位置在TSS段中，该段保存了ring0，ring3的SS/ESP，具体的位置见下图。

图3-10 TSS段

ucoreOS设置esp的代码如下：

/* task state segment format (as described by the Pentium architecture book) */
struct taskstate {
    uint32_t ts_link;       // old ts selector
    uintptr_t ts_esp0;      // stack pointers and segment selectors
    uint16_t ts_ss0;        // after an increase in privilege level
    uint16_t ts_padding1;
    uintptr_t ts_esp1;
    uint16_t ts_ss1;
    uint16_t ts_padding2;
    uintptr_t ts_esp2;
    uint16_t ts_ss2;
    uint16_t ts_padding3;
    uintptr_t ts_cr3;       // page directory base
    uintptr_t ts_eip;       // saved state from last task switch
    uint32_t ts_eflags;
    uint32_t ts_eax;        // more saved state (registers)
    uint32_t ts_ecx;
    uint32_t ts_edx;
    uint32_t ts_ebx;
    uintptr_t ts_esp;
    uintptr_t ts_ebp;
    uint32_t ts_esi;
    uint32_t ts_edi;
    uint16_t ts_es;         // even more saved state (segment selectors)
    uint16_t ts_padding4;
    uint16_t ts_cs;
    uint16_t ts_padding5;
    uint16_t ts_ss;
    uint16_t ts_padding6;
    uint16_t ts_ds;
    uint16_t ts_padding7;
    uint16_t ts_fs;
    uint16_t ts_padding8;
    uint16_t ts_gs;
    uint16_t ts_padding9;
    uint16_t ts_ldt;
    uint16_t ts_padding10;
    uint16_t ts_t;          // trap on task switch
    uint16_t ts_iomb;       // i/o map base address
} __attribute__((packed));
/* *
 * load_esp0 - change the ESP0 in default task state segment,
 * so that we can use different kernel stack when we trap frame
 * user to kernel.
 * */
void
load_esp0(uintptr_t esp0) {
    ts.ts_esp0 = esp0;
}
/* gdt_init - initialize the default GDT and TSS */
static void
gdt_init(void) {
    // set boot kernel stack and default SS0
    load_esp0((uintptr_t)bootstacktop);
    ts.ts_ss0 = KERNEL_DS;
    // initialize the TSS filed of the gdt
    gdt[SEG_TSS] = SEGTSS(STS_T32A, (uintptr_t)&ts, sizeof(ts), DPL_KERNEL);
    // reload all segment registers
    lgdt(&gdt_pd);
    // load the TSS
    ltr(GD_TSS);
}

3.5、分页

页式管理将线性地址分成三部分（图中的 Linear Address 的 Directory 部分、Table 部分和 Offset 部分）。ucore 的页式管理通过一个二级的页表实现。一级页表的起始物理地址存放在 cr3 寄存器中，这个地址必须是一个页对齐的地址，也就是低 12 位必须为 0。目前，ucore 用boot_cr3（mm/pmm.c）记录这个值。

图3-11 ucoreOS中的分页

二、练习解答

1、实现first-fit连续物理内存分配算法

在实现first fit 内存分配算法的回收函数时，要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时，需要按照空闲页块起始地址来排序，形成一个有序的链表。可能会修改default_pmm.c中的default_init，default_init_memmap，default_alloc_pages，default_free_pages等相关函数。请仔细查看和理解default_pmm.c中的注释。

default_init()函数分析：

static void
default_init(void) {
    list_init(&free_list);
    nr_free = 0;
}

default_init_memmap()函数分析，该函数的主要作用是清空每页，并设置每一页的属性。并将空闲页添加到空闲列表中（free_list，nr_free）。

static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(PageReserved(p));
        p->flags = p->property = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    nr_free += n;
    list_add_after(&free_list, &(base->page_link));
}

default_alloc_pages()函数分析：

default_free_pages()函数分析：

在first-fit连续物理内存分配中，页号是按照从小到大的顺序排列的，每一个page使用16字节定义。

2、实现虚拟地址对应的页表项

通过设置页表和对应的页表项，可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。本练习需要补全get_pte函数 in kern/mm/pmm.c，实现其功能。请仔细查看和理解get_pte函数中的注释。get_pte函数的调用关系图如下所示：

下图中，是ucoreOS中通过一级页表、二级页表查到到页的物理地址过程。根据这样的一个过程，实现了线性地址转换成物理地址。

有关页表项建立的程序，可以根据上图的过程进行建立。页表项建立的函数如下：

//get_pte - get pte and return the kernel virtual address of this pte for la
//        - if the PT contians this pte didn't exist, alloc a page for PT
// parameter:
//  pgdir:  the kernel virtual base address of PDT
//  la:     the linear address need to map
//  create: a logical value to decide if alloc a page for PT
// return vaule: the kernel virtual address of this pte
pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
   int i=0;
    // (1) find page directory entry
    uint32_t pde_index = PDX(la);
    //we need get content from an entry of page directory
	pde_t *pdep = &pgdir[pde_index];
	// (2) we get second page table base address
    //maybe pde is not present,we consider create the whole page table through 'create' params
	if(!(*pdep&PTE_P))
	{
		struct Page *page = NULL;
		//2.1.we don't need create it
		if(!create){
			return NULL;
		}
		//2.2.malloc page failed
		if((page=alloc_page())==NULL)
		{
			return NULL;
		}
		//2.3.config second page
		//set page reference,show this physical memory area service condition
		set_page_ref(page, 1);
		//clear page content using memset
		//the real continus area comes from below result(set operation on virtual address)
		uintptr_t pa = page2pa(page);
		memset(KADDR(pa), 0x0, PGSIZE);
		//set physical address of 4-KBytes aligned page table referenced by this entry
		*pdep = pa | (PTE_P | PTE_U | PTE_W);
	}

	//(3) return page table entry's virtual address
	uintptr_t pte_virtual_address = KADDR(PDE_ADDR(*pdep));
	pte_t *pte = &((pte_t *)pte_virtual_address)[PTX(la)];
	return pte;
}

3、释放某虚地址所在的页并取消对应二级页表项的映射

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除处理，使得此物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除。请仔细查看和理解page_remove_pte函数中的注释。为此，需要补全在kern/mm/pmm.c中的page_remove_pte函数。page_remove_pte函数的调用关系图如下所示：

释放页表项相对简单许多，只需要查找到相应的页表项，并解引用，并清空，并解引用。相关的实现代码如下：

//page_remove_pte - free an Page sturct which is related linear address la
//                - and clean(invalidate) pte which is related linear address la
//note: PT is changed, so the TLB need to be invalidate 
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
	//(1) check if ptep is valid
	if(*ptep&PTE_P)
	{
		struct Page *page = NULL;
		//(2) find corresponding page
		page = pte2page(*ptep);
		//(3) decrease page reference
		if(page_ref_dec(page)==0)
		{
			//(4) and free this page when page reference reachs 0
			free_page(page);
		}
		//(5) clear second page table entry
		*ptep = 0;
		//(6) flush tlb,TLB must is the same as page table
		tlb_invalidate(pgdir,la);
	}
	
}