分页和动态页面分配

01. 保护模式下的段式虚拟内存管理

任务的划分实际上是内存空间的划分

内存空间的访问时依靠分段机制进行的，是通过将内存划分为段来进行的。现在描述符表中定义每个段的描述符，然后通过描述符来访问其对应的内存段。

程序中先将段选择子送入段寄存器sreg中，再使用jmp、call指令进行跳转。其中段选择子的TI = 0表示描述符再GDT中，TI = 1表示在LDT中。

每个任务的描述符索引是13位，最多2^13 = 8192个，段内偏移是32位的，段的最大长度是2^32 = 4GB，则任务的全局部分为2^13 * 2^32 = 2^45 = 32TB，任务的私有部分为2^13 * 2^32 = 2^45 = 32TB，则一个任务的理论总大小为64TB。在一个多任务系统中，还有其他多个任务。但是32跟地址线最多能寻址4GB的物理内存空间。

上图中，任务的全局部分占用物理内存的高2G字节，任务的私有部分占用物理内存的低2G字节

开始将所有段的P位清零，表示暂时不在内存中，把要访问的段P位置1，将其调入物理内存中

将段1置换到外部磁盘、将段1的P位清零、将段3置换到物理内存、将段3的P位置1

下次访问段1，发现P = 0，首先将其置换到物理内存中、再将段3的P位清零、再将段1的P位置1.使用上述这种方式实现段式虚拟内存管理策略。

实际中，段有大有小当内存空间不足时需要进行段的换入换出，置换出当前使用最少的段。在描述符中有一个特殊的位A，表示以访问位。当处理器访问一个段时，自动将A置1，根据A位被改变的频次可以知道哪些段是是用最少的，就能对其进行置换。

如上图，由于段的长度不同，在进行段的换入换出之后，虽然内存中剩余容量足够，但是内存不连续，也导致不能被使用。就如段5无法被调入内存。x86使用了内存分页技术解决这个问题，将物理内存分为大小相同的页，并将长度不同的段映射近长度相同的页。

02. 每个任务独立的虚拟内存

每个任务都分配一个4GB的虚拟内存空间低一半0x00000000 ~ 0x7FFFFFFF为私有部分，高一半0x80000000 ~ 0xFFFFFFFF为全局部分。

在多任务系统中，任务的全局部分共有，私有部分独立：

重新规划任务的内存空间：全局部分和私有部分各有2GB，如下，若私有部分有5个段，分别映射到2GB字节虚拟内存中。

03. 物理内存的分页以及段到页的拆分

任务对应为一些文件，最主要的可执行文件包含代码段、数据段、栈段以及段的实际内容，其他文件可以是工作文档、图像、视频文件等等，可以被加载到数据段中进行处理。

内核有自己的可执行文件和其它文件，是所有任务共享的，每个任务都有自己的可执行文件和其他文件。

当任务执行时，要把可执行文件都映射到自己的虚拟内存，映射就是计算每个段在虚拟内存中的起始位置和长度，然后创建和安装其描述符。

映射之后，下一步工作是将段进行切分，然后加载到物理内存。物理内存是4G字节，每一部分都是一个页，页的最小长度是4KB。之后就是将虚拟内存中的段进行4K字节的拆分映射到物理内存中

如上图，在虚拟内存中的12606字节的段被划分到占3个4096字节完整的页 + 1个占318字节的页中。即使不足4KB也要按照4KB进行映射

段是连续的，页不需要是连续的。在内存中闲置的页和被占用的页是随机交错存在的，无法保证哪些页被释放哪些页被占用。也就无法保证分配的页在什么位置

对内存的分页是逻辑上的、而不是物理上的。同时页的起始位置也有要求，对于4KB的页来说，起始位置必须是4096字节（即0x1000)的整倍数。

课后练习题：

04. 处理器的段部件和页部件

分页（paing：名词，表示以页为基础的内存管理模式），开启分页机制后，在程序执行前，要把可执行文件中的段映射到虚拟内存，然后再把段中的内容加载到物理内存中的页。

为什么要引入虚拟内存、要把程序映射到虚拟内存呢？
Intel处理器是按照分段机制工作的，只不过在分页模式下，段是安排在虚拟内存的。将程序映射到虚拟内存就是规划所有段在虚拟内存中的布局和位置。并根据这些信息来创建段描述符

如上图，处理器只是规划可执行文件在虚拟内存中的布局，并不会把代码加载进虚拟内存中。

在没有开启分页机制时，段部件输出的地址就是物理地址

开启分页机制后，段部件输出的地址就是线性地址，线性地址是虚拟内存中的地址，要传送给页部件，页部件用来将线性地址转换为物理地址

页部件将段部件传送来的线性地址转换为物理地址。页部件将线性地址拆分成页地址和页内偏移，再将页地址修改为真实的物理页地址即可。如线性地址0x00201000，页部件将页地址转换为0x00004000、偏移为0xCC，则转换后的地址就是0x000040CC。

05. 从线性地址到物理地址的转换过程

线性地址到物理地址的转换：

线性地址的前20位对应物理地址的前20位。

每个表项占4个字节，所以访问表项时，使用虚拟页地址的高20位乘以4

段描述符的基地址 + 指令中的偏移量传送给段部件
段部件输出线性地址0x0020010C8
线性地址的高20位乘以4去访问表项取出物理页地址的高20位
线性地址的低12位和上一步取出物理页地址的高20位结合形成物理地址
使用这个物理地址访问内存各个任务都有自己独立的4GB虚拟内存空间和独立的页映射表。

课后作业：

06. 页目录和页表及其地址转换过程

页映射表需要4MB大小

页映射表必须一开始就完全定义，而且会占用4MB内存空间。

层次化的分页结构，即不采用单一的页映射表，使用页目录表和页表替代。
页表中每个页表项占据4个字节（32位）用来存放物理页地址，共可保存1024个物理页地址，即每个页表大小为4KB。

CR3存放当前任务页目录的物理地址，也叫做页目录基址寄存器

没有开启分页机制时，段部件发出的地址就是物理地址0x00801050
开启分页机制：

段部件发出线性地址，处理器将其分为三部分（高10位、中间10位、低12位）
处理器从当前任务状态段TSS中取出CR3寄存器的值，里面存放的是当前任务所用的页目录物理基地址
接着将线性地址高10位乘以4得到页目录中的偏移，从页目录的这个地址中取出页表的物理基地址
接着将线性地址的中间10位乘以4得到其在页表中的偏移，从页表的这个地址中取出线性地址对应的物理基地址
接着使用这个基地址加上线性地址的低12位形成物理地址，这样就把段部件发出的线性地址转换为物理地址了

其中乘以4时因为页目录和页表中每一项都是占据4个字节的，所以需要乘以4才能得到每一项在表中对应的偏移。

这种变化是事先安排好的，当程序加载时操作系统先创建虚拟的段，根据段地址的高20位来判断需要用到哪些页目录项和页表项，之后在物理内存中寻找空闲的页，并将页的物理地址填写到对应的页表项中，之后程序就可以按照这些值把线性地址转换为物理地址。

07. 设计内核的页目录和页表

本章程序：
引导程序：c13_mbr0.asm
内核程序：c31_core0.asm
用户程序1：c30_app0.asm
用户程序2：c30_app1.asm

系统中的执行顺序为：

先创建页目录和页表、在虚拟内存中规划每个段的位置并创建段描述符
处理器的页部件从段部件输出的线性地址中提取前20位作为索引来访问页目录表和页表，看对应的物理页是否存在
如果页不存在，则在物理内存中搜索这个物理页，并将页的物理地址填写在页表中，这样就可以访问这个物理页
如果页存在，则直接访问这个页找到对应的物理地址以此访问这个页

内核程序中，显示处理器品牌信息之后开始准备打开分页机制。但是此时内核是都开启页功能之前加载的，其内容在内存中的位置已经固定。此时要想当前执行流程在开启分页之后还能继续进行，就必须让段部件发出的线性地址等于页部件发出的物理地址

我们内核处于低端1MB，对低端1MB的内存特殊处理，让这部分的线性地址等于页部件转换之后的物理地址即可。那么这样做之后内核就不需要做任何变动就可以在分页机制下正常工作

一个页表可以管理4MB内存，那么对于这个内核只需要一个页表即可。页目录和页表放在任何有效的物理内存地址都可，如上，放在0x00020000处。

08. 页目录项和页表项的组成格式

目的对于低端1MB内存，段部件发出的线性地址和页部件发出的物理地址相同。

创建页目录，将其清零：

    ;创建系统内核的页目录表PDT
    mov ecx,1024                       	;1024个目录项
    mov ebx,0x00020000                  ;页目录的物理地址
    xor esi,esi							;页目录表清零
.b1:
    mov dword [es:ebx+esi],0x00000000  	;页目录表项清零
    add esi,4
    loop .b1

页目录项、页表项的组成格式：在页目录中只保存了页表物理地址的高20位、在页表中只保存了页物理地址的高20位。因为页表和页目录要求是4K字节对齐，所以低12位为0

P位（Present）：1表示页表或页目录存在于内存中、0表示不在内存中，需要创建或从磁盘调入
R/W位（Read/Write）：0页目录或页表只读、1表示可读可写
US位（User/Supervisor）：1时表示所有特权级别的程序访问，0表示只有特权级0、1、2特权级的程序可以访问
PWT位（Page Level Write-Through）：页级通写位，和高速缓存有关、通写是高速缓存的一种方式，0表示不允许使用此种方式提升页面访问效率、1表示允许
PCD位（Page-Level Cache Disable）：高速缓存禁止位，0表示不使用高速缓存策略、1表示使用
A位（Accessed）：由处理器固件设置，0表示此页未被访问过，1表示被访问过，操作系统定期将此位清零，通过此位被置1的次数了解此页的使用频率
D位（Dirty）：由处理器固件设置，用来指示此表项的页已经写过数据。
PAT位（Page-Attribute Table）：页属性表支持位，只对页表项起作用，页目录项中此位置0，和页高速缓存有关
G位（Global）：指示该表项所指示的页是否为全局性质的，若页是全局的，他将会在高速缓存中一直保存，意味着地址转换的速度会很快
AVL位（Available）：被处理器忽略，程序可以使用

09. 创建内核的页表并初始化低端1MB对应的页表项

    ;将页目录表的物理地址登记在它自己的最后一个页目录项内
    ;页目录也可以容纳1024个，从0到3FF，最后一项的偏移为3FF X 4 = 0xFFC = 4092
    mov dword [es:ebx+4092],0x00020003

程序前1MB占据一个页目录项和页表的前256个表项。修改页目录项的内容使其指向页表，填写的内容是页表的物理地址：0x00021000，该页位于内中，可读可写，但是不允许特权级别为3的程序访问，所以最终要填写0x00021003。

修改页目录中第一个表项的内容，使其指向页表：

    ;在页目录内创建与线性地址0x00000000对应的目录项
    mov dword [es:ebx+0],0x00021003    ;写入目录项（页表的物理地址和属性）

将低端1MB字节所包含的哪些页的物理地址按顺序填写到页表中：

    ;创建与上面那个目录项相对应的页表，初始化页表项
    mov ebx,0x00021000                 ;页表的物理地址
    xor eax,eax                        ;起始页的物理地址
    xor esi,esi
.b2:
    mov edx,eax
    or edx,0x00000003
    mov [es:ebx+esi*4],edx             ;登记页的物理地址
    add eax,0x1000                     ;下一个相邻页的物理地址
    inc esi
    cmp esi,256                        ;仅低端1MB内存对应的页才是有效的
    jl .b2
.b3:                                   ;其余的页表项置为无效
    mov dword [es:ebx+esi*4],0x00000000
    inc esi
    cmp esi,1024
    jl .b3

开启分页功能之后，页表和物理地址的映射关系：

10. 设置控制寄存器CR3和CR0开启分页功能

开启分页：

    ;令CR3寄存器指向页目录，并正式开启页功能
    mov eax,0x00020000  ;PCD=PWT=0
    mov cr3,eax
    
    cli		;开启分页之前需要重新设置内核，不能发生中断，先关闭
    
    mov eax,cr0
    or eax,0x80000000
    mov cr0,eax			;开启分页机制
                        ;从这条指令开始，段部件产生的就是线性地址不是物理地址

对控制寄存器使用MOV指令，和普通的MOV 指令不同，操作码不同

CR0寄存器的位31，PG位，0表示关闭分页、1表示开启分页。CR0的位0，PE位，0表示位于实模式、1表示位于保护模式。分页只能在保护模式下开启

11. 在调试器中观察页目录表和页表

写入程序：

分页之前：

使用info tab命令查看可知，此时分页是关闭的。其中CR0的PG位是小写，为0。PE位大写为1，处于保护模式。

开启分页：

GDT内第二个描述符的线性地址为0x00007E08

12. 准备将内核映射到虚拟内存的高端

页目录的高2G字节指向内核的页表、低2G字节指向任务的页表。

若页目录的高2GB不是指向内核的页表时，当从任务的私有部分转到内核执行时，段部件发出的地址一定是高于0x80000000的，此时就找不到内核所在的物理地址，无法完成地址转换。因此需要将内核映射到虚拟地址的高端

内核映射到虚拟地址高端之后的内存布局。内核是位于虚拟内存，现在只是让段部件发出的地址位于虚拟地址的高端。

13. 在分页机制下访问页目录表自身

上图，现在需要在页目录中添加一个表项，使其指向内核原先的位置

页部件从CR3寄存器取出页部件的物理基地址，定位到页目录表
段部件发出的地址是0xFFFFF800
取出高10位乘以4，作为页目录表内偏移，从页目录表中取出页表的物理地址，此时发现通过页目录表找到的页表仍然是页目录表自身的基址，即把页目录表当成页表使用
接着从线性地址中间10位取出页表内的偏移，取出页的物理基地址
再加上线性地址的低12位构成物理地址，去访问内存
将其设置为原先的值，这就将内核从虚拟内存的低端映射到了高端

代码如下：

    ;在页目录内创建与线性地址0x80000000对应的目录项
    ;mov ebx,0xfffff000                 ;页目录自己的线性地址
    ;mov esi,0x80000000                 ;映射的起始地址
    ;shr esi,22                         ;线性地址的高10位是目录索引
    ;shl esi,2
    ;mov dword [es:ebx+esi],0x00021003  ;写入目录项（页表的物理地址和属性）
                             			;目标单元的线性地址为0xFFFFF200
    mov dword [es:0xfffff800], 0x00021003

14. 使内核在虚拟内存高端的映射生效

修改与内核有关的段描述符，以及GDT自己的线性地址

只需要修改内核所有段描述符的最高位，将其置1即可（等于加上0x80000000)，代码如下：

    ;将GDT中的段描述符映射到线性地址0x80000000
    sgdt [pgdt]
    
    mov ebx,[pgdt+2]
    
    or dword [es:ebx+0x10+4],0x80000000;处理保护模式下初始代码段描述符
    or dword [es:ebx+0x18+4],0x80000000;处理内核的栈段描述符
    or dword [es:ebx+0x20+4],0x80000000;处理显示缓冲区描述符
    or dword [es:ebx+0x28+4],0x80000000;处理公共例程段描述符
    or dword [es:ebx+0x30+4],0x80000000;处理内核数据段描述符
    or dword [es:ebx+0x38+4],0x80000000;处理内核代码段描述符
    
    add dword [pgdt+2],0x80000000      ;GDTR也用的是线性地址
    
    lgdt [pgdt]							;使得修改生效

修改中断描述符表IDTR，因为中断描述符表已经被映射到虚拟内存的高端

    ;修改IDTR，将中断描述符表映射到线性地址高端
    sidt [pidt]
    add dword [pidt+2],0x80000000      ;IDTR也用的是线性地址
    lidt [pidt]

段寄存器由段选择器和描述符高速缓存器组成，处理器执行指令时，不会每次都加载段选择器，而是使用段描述符高速缓存器中的基地址访问内存。

所以当修改了GDT的基地址或段描述符之后，这些修改不会立即反映到段描述符高速缓存器，对程序的运行没有任何影响。

但是当执行一个段间转移指令、或向段寄存器里加载一个新的段描述符选择子时，处理器会访问GDT或LDT，将刷新段寄存器的描述神高速缓存器中的内容

因此为了使处理器转移到内存高端执行，需要显示的刷新段寄存器内容，代码段CS的刷新需要用转移指令完成：

    jmp core_code_seg_sel:flush        ;刷新段寄存器CS，启用高端线性地址
    ;导致处理器使用新的段选择子core_code_seg_sel来访问GDT；
    ;从中取出修改后的代码段描述符，并加载到CS描述符高速缓存器中；
    ;这直接导致处理器从虚拟地址高端取指令执行
    
flush:
    mov eax,core_stack_seg_sel		;刷新SS，同时刷新其描述符高速缓存器
    mov ss,eax						;物理地址没有改变，改变的是线性地址
    
    mov eax,core_data_seg_sel		;刷新DS，同时刷新其描述符高速缓存器
    mov ds,eax						;物理地址没有改变，改变的是线性地址

即使是在分页机制下，显存的基地址部分加上了0x80000000，例程put_string和put_char也没有做任何修改。

尽管显存基地址已经映射到0x800B8000，但是向这个虚拟的地址写数据时，页部件将会把它转换为真实的显存位置0x000B8000.

15. 为内核任务创建任务控制块TCB

接上一节，为系统服务例程安装门描述符，没有修改，因为门描述符的创建只涉及目标代码段的选择以及例程在段内的偏移量，不受内存映射的影响。

接下来创建内核任务，内核任务有自己的动态空间TCB，而且它的空间不是动态分配的，是明确指定的的。由于内核被映射到高端字节，所以内核TCB的线性地址也变为0x8001F800.代码如下：

    ;对门进行测试 
    mov ebx,message_2
    call far [salt_1+256]              ;通过门显示信息(偏移量将被忽略) 
    
    ;开始创建和确立内核任务
    mov ecx,core_lin_tcb_addr          ;移至高端之后的内核任务TCB线性地址
    mov word [es:ecx+0x04],0xffff      ;任务的状态为“忙”
    mov dword [es:ecx+0x46],core_lin_alloc_at
                                     ;登记内核中可用于分配的起始线性地址
    call append_to_tcb_link            ;将内核任务的TCB添加到TCB链中
    
    mov esi,ecx

若之前分配过地址，在虚拟地址的低端1MB，之后就是建立虚拟地址和物理地址的映射；若要再分配内存，那就需要从0x100000开始分配，需要将上一个TCB的尾部结构修改为这次分配的地址起始位置，即0x100000。

16. 为内核任务的TSS分配内存空间

    ;为内核任务的TSS分配内存空间。所有TSS必须创建在内核空间
    mov ecx,104                        ;为该任务的TSS分配内存
    call sys_routine_seg_sel:allocate_memory	;创建TSS所需内存是动态分配的
                                                ;必须在内核的虚拟地址空间中
    mov [es:esi+0x14],ecx              ;在内核TCB中保存TSS基地址

例程allocate_memory：

allocate_memory:			;在当前任务的地址空间中分配内存
                     	 	;输入：ECX=希望分配的字节数
                      		;输出：ECX=起始线性地址 
    push eax
    push ebx
    
    push ds
    
    ;得到TCB链表首节点的线性地址
    ;因为是在当前任务的虚拟线性空间中分配，所以需要搜索TCB链表
    ;找到当前TCB，从中取得可用于分配的线性地址，从这个地址处开始分配
    mov eax,core_data_seg_sel
    mov ds,eax
    
    mov eax,[tcb_chain]                ;EAX=首节点的线性地址
    
    mov ebx,mem_0_4_gb_seg_sel
    mov ds,ebx
    
    ;搜索状态为忙（当前任务）的节点
.s0:
    cmp word [eax+0x04],0xffff
    jz .s1				;找到忙的节点，EAX=节点的线性地址
    mov eax,[eax]
    jmp .s0
    
    ;开始分配内存
.s1:
    mov ebx,eax			;找到忙的节点，EAX=节点的线性地址
    call sys_routine_seg_sel:task_alloc_memory
    
    pop ds
    
    pop ebx
    pop eax
    
    retf

其中例程task_alloc_memory：

task_alloc_memory:		;在指定任务的虚拟内存空间中分配内存
                        ;并不一定是在当前任务的虚拟内存空间中分配
          				;输入：EBX=任务控制块TCB的线性地址
          				;      ECX=希望分配的字节数
          				;输出：ECX=已分配的起始线性地址
    push eax
    
    push ds
    
    push ebx                           ;to A
    
    ;获得本次内存分配的起始线性地址
    mov ax,mem_0_4_gb_seg_sel
    mov ds,ax
    
    mov ebx,[ebx+0x46]                 ;获得本次分配的起始线性地址
    mov eax,ebx
    add ecx,ebx                        ;本次分配，最后一个字节之后的线性地址
    
    push ecx                           	;To B
                                        ;下一次可以分配的线性地址，需要压栈保护
    ;为请求的内存分配页
    and ebx,0xfffff000		;线性地址低12位没有用，将其清零
    and ecx,0xfffff000
.next:
    call sys_routine_seg_sel:alloc_inst_a_page
          								;安装当前线性地址所在的页
    add ebx,0x1000                     	;+4096
    cmp ebx,ecx
    jle .next
    
    ;将用于下一次分配的线性地址强制按4字节对齐
    pop ecx                            	;B
                                        ;原先保存下一次内存分配可以使用的起始线性地址
                                        ;弹出之后要保存到TCB中，这里要先对齐
    test ecx,0x00000003                ;线性地址是4字节对齐的吗？
    jz .algn                           ;是，直接返回
    add ecx,4                          ;否，强制按4字节对齐
    and ecx,0xfffffffc
    
.algn:
    pop ebx                            ;A
    
    mov [ebx+0x46],ecx                 ;将下次分配可用的线性地址回存到TCB中
    mov ecx,eax
    
    pop ds
    
    pop eax
    
    retf

17. 处理与线性地址对应的页目录项和页表项

接上一节，知道本次内存分配涉及哪些线性地址，这是一个连续的线性地址范围区间，通过循环反复调用alloc_inst_a_page来安装与这些线性地址对应的物理页。

其中例程task_alloc_memory：

task_alloc_memory:
。。。
    ;为请求的内存分配页
    and ebx,0xfffff000		;线性地址低12位没有用，将其清零
    and ecx,0xfffff000
.next:
    call sys_routine_seg_sel:alloc_inst_a_page
          								;安装当前线性地址所在的页
    add ebx,0x1000                     	;+4096
    cmp ebx,ecx
    jle .next

其中例程alloc_inst_a_page用来为指定的线性地址分配一个物理页

    alloc_inst_a_page:	;分配一个页，并安装在当前活动的
                        ;层级分页结构中
                        ;输入：EBX=页的线性地址
    push eax
    push ebx
    push ecx
    push esi
    push ds
    
    mov eax,mem_0_4_gb_seg_sel
    mov ds,eax		;后面用线性地址访问页目录表和页表自身做准备
    
    ;线性地址的高10位是页目录表索引
    ;用它来检查该线性地址所对应的页表是否存在
    mov esi,ebx
    and esi,0xffc00000                 ;清除页表索引和页内偏移部分
    shr esi,20                         ;将页目录索引乘以4作为页内偏移
    or esi,0xfffff000                  ;页目录自身的线性地址+表内偏移
    
    test dword [esi],0x00000001        ;P位是否为“1”。检查该线性地址是
    jnz .b1                            ;否已经有对应的页表
    
    ;页目录项不存在，就创建一个新的页表，并将页表的地址写入这个页目录项
    ;创建并安装该线性地址所对应的页表
    call allocate_a_4k_page		;分配一个页做为页表
                                ;这个物理地址只保留前20位
                                ;后12位是页的属性值，为0x07
    or eax,0x00000007			;US位是1，即特权级3也可以访问
                                ;现在是在为内核人物的TSS分配内存
                                ;TSS只能由特权级0的内核任务访问，其所在的页也只能有
                                ;特权级0的内核任务访问，但是这里为什么允许特权级3的内存访问呢？
                                ;
                                ;原则上是不允许的，但是这个例程是通用的，3特权级要求US位是1，
                                ;0特权级要求US位是0，
                                ;为了省事就把US位置1了
    mov [esi],eax               ;在页目录中登记该页表,将页目录项的内容修改为页表的物理地址
    
    ;清空当前页表，把页表当成普通的页来用
    mov eax,ebx
    and eax,0xffc00000	;清空低22位
    shr eax,10			;右移10次
    or eax,0xffc00000	;将高10位设置成0x3FF
    mov ecx,1024		;之后用循环访问页表内的全部页表项
.cls0:
    mov dword [es:eax],0x00000000
    add eax,4			;加4得到下一个页表项
    loop .cls0
    
.b1:
    ;检查该线性地址对应的页表项（页）是否存在
    mov esi,ebx
    and esi,0xfffff000                 ;清除页内偏移部分
    shr esi,10                         ;将页目录索引变成页表索引，页表索引乘以4作为页内偏移
    or esi,0xffc00000                  ;得到该线性地址对应的页表项
    
    test dword [esi],0x00000001        ;P位是否为“1”。检查该线性地址是
    jnz .b2                            ;否已经有对应的页
    
    ;创建并安装该线性地址所对应的页
    call allocate_a_4k_page            ;分配一个页，这才是要安装的页
    or eax,0x00000007
    mov [esi],eax
    
.b2:
    pop ds
    pop esi
    pop ecx
    pop ebx
    pop eax
    
    retf

其中把页目录表当成页表使用：

即页目录表的高10位右移到最右端，再左移两位补0，其余补1.这个线性地址就可以把页目录表当成一个页来用，即访问页目录表自身。

其中把页表当成普通的页来用：

18. 根据需要分配物理页并设置页表项

接上一节，其中例程alloc_inst_a_page：用来为指定的线性地址分配一个物理页

alloc_inst_a_page:

    ......
    
      .b1:
         ;检查该线性地址对应的页表项（页）是否存在
         mov esi,ebx
         and esi,0xfffff000                 ;清除页内偏移部分
         shr esi,10                         ;将页目录索引变成页表索引，页表索引乘以4作为页内偏移
         or esi,0xffc00000                  ;得到该线性地址对应的页表项

         test dword [esi],0x00000001        ;P位是否为“1”。检查该线性地址是
         jnz .b2                            ;否已经有对应的页

         ;创建并安装该线性地址所对应的页
         call allocate_a_4k_page            ;分配一个页，这才是要安装的页
         or eax,0x00000007
         mov [esi],eax

  .b2:
         pop ds
         pop esi
         pop ecx
         pop ebx
         pop eax

         retf

要想判断与线性地址对应的页表项是否有效，需要访问页表自身，将页表当成一个普通的页来访问。

此时图中第三行的线性地址就是我们要访问的那个页表项的线性地址

如上图，访问过程。

19. 物理内存的页面管理和页映射位串

无论分配页表还是物理页，都要调用例程allocate_a_4k_page，这个例程用来分配物理页，对于每个任务来说内存分配包括两个互相连续的部分：首先是在任务自己的虚拟内存空间中分配，然后将其映射到物理内存中的页。

物理页的数量是有限的，是所有任务共享的，若物理页空间不足，还需要执行内存换入换出操作。操作系统需要在上电之后就检测实际的物理内存数量，并建立一张表格登记每个页的基本信息，包括页的物理地址以及是否空闲。4GB共可分配1048576个页，为了简单起见，使用位串指定页的位置和分配情况。

比特的位置决定页的位置，比特位的值决定了页的分配情况，0表示此页空闲、1表示此页被占用。

在本章中没有检测实际内存的代码，仅仅假定我们只有2MB的物理内存空间可用，2MB = 512KB，需要512个位串，使用连续的字数据来声明位串，在内核数据段中：

第一个字节0xff的位0对应物理地址为0的页，位1对应物理地址为0x1000的页；
第二个字节0xff的位0对应物理地址为0x8000的页，位1对应物理地址为0x9000的页；
把比特在比特串中的序号乘以0x1000就得到其所对应的物理页的地址（0x1000递增）。
前32字节对应内存最低端1MB中的页，共256个页。这一部分已经整体划归内核使用，没有被内核占用的部分也大多被外围硬件占用，包括ROM-BIOS。

其中前32个字节中有两个0x55，对应48~63，16进制是0x30~0x3F，乘以0x1000之后对应物理页范围是0x30000~0x3F000共64KB，可以划分为16个页。为了表明页的分配是随机的，即连续的线性地址空间不必对应连续的页，有意将页在物理上分开，0x55 = 01010101，表示空闲页和已经分配的页是交替出现的。

但是将0x55对应的16个页作为空闲页分配未必合理，因为低端1MB内存已经分配给内核，在内核的页表中，已经有页表项指向这16个页，若在将其分配给其他任务，那么其他任务的页表项有势必指向这16个页，即重复分配。但是线性地址到物理页的映射可以是重复的，内核也不会使用这16个页，分配给其他任务也无妨。

20. 空闲页的搜索和BTS指令

接上一节，查看例程allocate_a_4k_page：

    allocate_a_4k_page:			;分配一个4KB的页
                                ;输入：无
                                ;输出：EAX=页的物理地址
                                ;每个页的状态可以从页映射位串中获得
    push ebx
    push ecx
    push edx
    push ds
    
    mov eax,core_data_seg_sel
    mov ds,eax		;指向内核数据段，以便指向页映射位串
    
    xor eax,eax		;循环，从头开始搜索位串，查找空闲的页
                    ;从页映射位串中找到第一个为0的比特
                    ;记下在整个位串中的位置
.b1:
    bts [page_bit_map],eax	;搜索位串，寻找第一个为0的比特
    jnc .b2
    inc eax
    cmp eax,page_map_len*8
    jl .b1
    
    mov ebx,message_3
    call sys_routine_seg_sel:put_string
    hlt					;没有可以分配的页，停机
    
.b2:
    shl eax,12			;乘以4096（0x1000）
    
    pop ds
    pop edx
    pop ecx
    pop ebx
    
    ret

测试位串中的某个比特，用该比特的值设置标志寄存器的进位标志CF，然后将位串中的比特置1
目的操作数：16、32、64位的通用寄存器，或者是用于指定位串起始位置的内存地址，若是寄存器，则指定的位串就是该寄存器的内容
源操作数：16、32、64位的通用寄存器，用于指定待测试比特在位串中的位置，索引
目的操作数和源操作数若都为通用寄存器，则长度必须是一致的

目的操作数是通用寄存器：

EDX是待测试位串，ECX包含那个待测试比特的索引。如果目的操作数是寄存器，则根据目的操作数的长度，处理器先求得源操作数除以16、32、64的余数，并将其作为待测试比特的索引，然后从待测试位串中取得该比特，并传送到标志寄存器的CF位，最后将该比特置1。
在这里就是将ecx除以32取余，将余数作为索引在edx中找到对应的比特位查看是0还是1，并将其写入EFLAGS的CF位，然后不管是0还是1都要将在edx中找到的对应比特位置1。

目的操作数是内存地址：

目的操作数给出的是该位串在在内存中的第一个字节的地址，源操作数指定了可以访问的串的最大长度，若源操作数是16位的，则目的操作数即位串最大可以达到2^16个比特。

21. 空闲页搜索和分配的具体过程

接上一节，查看例程allocate_a_4k_page：

SECTION core_data vstart=0                  ;系统核心的数据段

    ......
    ......
    
    page_bit_map    db  0xff,0xff,0xff,0xff,0xff,0xff,0x55,0x55
                    db  0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
                    db  0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
                    db  0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
                    db  0x55,0x55,0x55,0x55,0x55,0x55,0x55,0x55
                    db  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
                    db  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
                    db  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
    page_map_len	equ		$-page_bit_map

    ......
    ......
    ......

    allocate_a_4k_page:			;分配一个4KB的页
                                ;输入：无
                                ;输出：EAX=页的物理地址
                                ;每个页的状态可以从页映射位串中获得
    push ebx
    push ecx
    push edx
    push ds
    
    mov eax,core_data_seg_sel
    mov ds,eax		;指向内核数据段，以便指向页映射位串
    
    xor eax,eax		;循环，从头开始搜索位串，查找空闲的页
                    ;从页映射位串中找到第一个为0的比特
                    ;记下在整个位串中的位置
.b1:
    bts [page_bit_map],eax	;搜索位串，寻找第一个为0的比特
                            ;每次搜索的比特位的值都会传送到CF位
                            ;并且位串中的这个比特位被置1
    jnc .b2		;若CF=0，表示找到了空闲的页面，转到 .b2处执行，
                ;若CF=1，表示当前比特对应的页面被分配过了，还得继续查找。
    inc eax
    cmp eax,page_map_len*8		;page_map_len是位串的字节长度
                                ;乘以8换算成二进制比特位的数量
    jl .b1		;若没有超过，小于关系成立，转移到标号 .b1 处重新查找空闲页
                ;若超过了位串最大长度，小于关系不成立，打印文本，停机
    mov ebx,message_3
    call sys_routine_seg_sel:put_string
    hlt					;没有可以分配的页，停机
    
.b2:					;一旦找到空闲页，到达此处
                        ;EAX保存代表空闲页的那个比特位的索引号
                        ;将这个索引号乘以0x1000、4096就得到所应对的那个页的物理地址
    shl eax,12			;乘以4096（0x1000）
    
    pop ds
    pop edx
    pop ecx
    pop ebx
    
    ret

内存分配的全过程：

22. 确立内核任务并开始创建用户任务

接上一节，回到内核start流程中
在TSS中登记必要项：

         ;在程序管理器的TSS中设置必要的项目
         mov word [es:ecx+0],0              ;反向链=0
         mov eax,cr3
         mov dword [es:ecx+28],eax          ;登记CR3(PDBR)
         mov word [es:ecx+96],0             ;没有LDT。处理器允许没有LDT的任务。
         mov word [es:ecx+100],0            ;T=0
         mov word [es:ecx+102],103          ;没有I/O位图。0特权级事实上不需要。
                                            ;不需要0、1、2特权级堆栈。0特级不
                                            ;会向低特权级转移控制。

其中TSS还有其他信息没有填写，这些信息会在处理器进行第一次任务切换时自动填写。
接着创建TSS描述符、加载当前任务到TR寄存器中。
接着创建用户任务的TCB并加载到TCB的链表中、接着使用例程load_relocate_program创建用户任务相关内容。

23. 用户任务的内存分配策略

创建用户任务的第一步就是分配内存，将用户任务的程序加载进来。

当前正在执行内核的页目录表和页表，也就无法通过用户任务的页目录表和页表来访问内存，也不能切换到用户任务的页目录表和页表，切换之后内核就不能执行下去了。

先给出内核任务、用户任务如何将虚拟地址空间映射到物理地址空间的：

其中内核与内核任务是共享高2GB空间的，所以在所有任务的页目录的高端都是一样的，在内核的页表中，既包含了内核所占用的物理页面，也包含了内核任务私有的物理页面。不过没有关系，因为只有内核任务才会使用页目录表的高2GB的表项，用户任务只会使用页目录低2GB的表项。

在内核任务的虚拟内存的低2GB是未使用的，那么对应内核任务的页目录中低一半的表项也是未使用的。

那么在创建用户任务时可以先在内核任务的虚拟空间的低一半分配内存，即使用页目录的低一半创建页目录表项，同时也会创建一些与这部分对应的页表并分配物理页。

因为是在创建用户任务，所以还会从硬盘中读出用户任务，写入分配来的这些物理页中。

等这些工作完成之后，将内核任务的页目录表复制一份，作为被创建的用户任务的页目录表。此时用户任务的高一半指向内核的页表，低一半指向刚才创建的用户任务的页表。再复制之后，将内核任务的低一半页目录表清空。

24. 清空内核任务页目录表的前半部分并刷新TLB

接上一节，进入例程load_relocate_program，加载重定位用户程序，并创建用户任务。本节代码如下：

load_relocate_program:                      ;加载并重定位用户程序
                                            ;输入: PUSH 逻辑扇区号
                                            ;      PUSH 任务控制块基地址
                                            ;输出：无 
         pushad
      
         push ds
         push es
      
         mov ebp,esp                        ;为访问通过堆栈传递的参数做准备
      
         mov ecx,mem_0_4_gb_seg_sel
         mov es,ecx

         ;清空当前页目录的前半部分（对应低2GB的局部地址空间）
         mov ebx,0xfffff000
         xor esi,esi
  .clsp:
         mov dword [es:ebx+esi*4],0x00000000
         inc esi
         cmp esi,512
         jl .clsp

         mov ebx,cr3                        ;刷新TLB
         mov cr3,ebx

开启页部件时，页部件使用页目录和页表将线性地址转换为物理地址。而访问页目录表和页表是耗时的，因此把页表项提前存放到处理器中可以加快地址转换的速度，为此在处理器内部特地构造了一个高速缓存装置（Transaction Lookaside Buffer）。

处理器用线性地址的高20位查找TLB中的行，查找标记相同的行。找到之后就使用其数据部分的页物理地址转换当前线性地址
若查找不成功，则处理器还要访问内存中的页目录表和页表，找到对应的页表项，将其填写到TLB中。

TLB的容量不大，若装满之后还需要置换掉那些使用较少的条目。TLB中的属性位来自于页表项如D位。访问权来自于页目录项，如RW位、US位，具体取页目录项还是页表中的值，若页目录的RW = 0、页表项的RW = 1，按照RW = 0执行，即取最严格的权限执行（等于是将访问权进行与操作）。

处理器仅仅缓存那些P位 = 1的页表项，而且TLB的工作和CR3寄存器的PCD、PWT无关，另外对于页表项的修改不会同时反映到TLB中。

如果内存表中的页表项已经修改，对应TLB中的条目还没有被更新，那么转换后的物理地址必定是错误的。

在本章里，内核任务页目录表的前一半用于创建用户任务，所以是频繁更新的，在创建用户任务时，必须先清除这一部分页目录项并刷新TLB。否则处理器将使用缓存的页表项访问内存，将会产生错误。

TLB的内容或条目不可由软件直接访问的，所以不能直接更改或刷新它的内容，但是有其它办法刷新，比如将CR3的内容读出再原样写入，这样就会使得TLB中的所有条目失效。当任务切换时因为需要从新任务的TSS中加载CR3，这样会隐式的导致TLB的所有条目无效并重新刷新。

上述方法对那些G位 = 1的表项是无效的，被设置为全局的页表项应该始终被缓存在TLB中，在前面我们已经清空了页目录表的前半部分，为了使TLB的条目失效，需要重新加载CR3.

25. 为用户任务分配内存并创建LDT

接上一节，在清空内核任务页目录表的前半部分并刷新了TLB之后，就可以分配内存并加载用户程序了，本节代码如下：

mov esi,[ebp+11*4]                 ;从堆栈中取得TCB的基地址

         ;以下申请创建LDT所需要的内存
         mov ebx,esi
         mov ecx,160                        ;允许安装20个LDT描述符
         call sys_routine_seg_sel:task_alloc_memory
         mov [es:esi+0x0c],ecx              ;登记LDT基地址到TCB中
         mov word [es:esi+0x0a],0xffff      ;登记LDT初始的界限到TCB中

申请内存：

情况1：

对于任何一个正在执行的任务，若要申请额外的内存空间，可以调用例程allocate_memory
例程allocate_memory需要调用task_allocate_memory，需要当前任务自己的TCB作为参数，所以例程allocate_memory需要获得当前任务控制块TCB
例程task_allocate_memory需要访问TCB，来确定本次内存分配器始于哪个线性地址，并根据分配的内存数量确定一个地址范围
若当前任务是内核任务，那么这个线性地址范围一定位于虚拟线性地址的高端、普通任务则位于虚拟线性地址的低端
确定线性地址范围之后，调用alloc_inst_a_page来分配和安装与线性地址相关的物理页。首先检查当前任务的页目录表和页表，看一下表项是否存在。存在说明之前分配过，直接返回
不存在，则调用例程allocate_a_4k_page在物理页中查找并返回空闲的物理页地址
无论如何，例程alloc_inst_a_page都是在当前任务的页目录和页表中登记线性地址与物理页的对应关系。

情况2：
在一个任务被创建并开始执行之前，需要先创建这个任务自己的虚拟内存空间，并在这个虚拟内存空间里分配用来加载这个任务的代码和数据。用户任务的创建是内核任务的工作，所以需要有内核任务代替用户任务来完成内存的创建和分配。

因为这个原因，需要借用内核任务页目录的前半部分来分配内存，内存分配完成用户任务创建之后，再将内核任务的页目录表复制一份给用户任务就可以了

有内核任务代替用户任务分配内存时，内核任务需要拿着用户任务的TCB来调用例程task_allocate_memory。毕竟内存分配是在用户任务自己的虚拟空间中进行，需要从用户任务自己的TCB中取得本次分配需要的线性地址。虽然是为用户任务分配内存，但却是在内核任务的页目录表中登记了页目录表项，这没关系后面直接复制一份即可。

26. 用户程序的加载和重定位

上一节已经为LDT分配了内存，接下来就是从硬盘读取用户程序

加载用户程序头部读取用户程序总字节数、将用户程序总字节数换算为总扇区数、循环读取用户程序剩余部分、建立用户程序的段描述符：

用户程序的SALT在用户程序头部段中，但是用户程序头部段暂时不能访问，因为当前任务是内核任务而不是用户任务

现在考虑一下用户程序什么能访问、什么不能访问，我们现在是在内核虚拟空间的低2GB虚拟空间里分配内存并加载用户程序，所以加载之后的内容是可以访问到的，不过现在是借助内核地址空间来访问的。

现在创建了用户程序的段选择子和段描述符，但是不能使用，因为这些段位于用户任务的LDT中，只有LDTR寄存器指向这个LDT才能访问这些段。但是当前是在内核任务中，是没有LDT的

之后重定位SALT、创建用户程序调用门0、1、2特权级的栈、在GDT中登记LDT描述符、创建用户程序的TSS、登记基本的TSS表格内容、访问用户程序头部段，获取数据填充TSS、在GDT中登记TSS描述符、创建用户任务的页目录，最后返回调用者。

27. 用户任务页目录表的创建和访问以及INVLPG指令

接上一节，当用户任务的加载和创建结束时，需要将内核任务的页目录表复制给用户任务。代码如下：

         ;创建用户任务的页目录
         ;注意！页的分配和使用是由页位图决定的，可以不占用线性地址空间
         call sys_routine_seg_sel:create_copy_cur_pdir
         mov ebx,[es:esi+0x14]              ;从TCB中获取TSS的线性地址
         mov dword [es:ebx+28],eax          ;填写TSS的CR3(PDBR)域

例程create_copy_cur_pdir：

create_copy_cur_pdir		;创建新页目录，并复制当前页目录内容
                      		;输入：无
                          	;输出：EAX=新页目录的物理地址
    push ds
    push es
    push esi
    push edi
    push ebx
    push ecx
    
    mov ebx,mem_0_4_gb_seg_sel     ;指向4G字节的段，为访问两个
    mov ds,ebx                     ;页目录表做准备
    mov es,ebx
    
    call allocate_a_4k_page
    mov ebx,eax		;EAX时这个页的基地址
    or ebx,0x00000007
    mov [0xfffffff8],ebx
    
    invlpg [0xfffffff8]		;刷新处理器的TLB中的条目
                            ;这个页目录项位于内核任务的页目录表中 
                            ;每当我们创建一个新的用户任务时，都用它来指向新任务的页目录表
                            ;修改这个表项时，修改的是内存中的，其在TLB中还有一个缓存
                            ;这个缓存的内容通常指向上一个任务的页目录表，因为我们在反复创建新任务
                            ;所以需要强制刷新这个缓存，与当前内存中的表项保持一致
                            
    mov esi,0xfffff000		;ESI->当前页目录的线性地址
    mov edi,0xffffe000		;EDI->新页目录的线性地址
    mov ecx,1024			;ECX=要复制的目录项数
    cld						;传送方向为正，从底到高
    repe movsd     			;需要使用两个段寄存器
                            ;movsd表示每次传送一个字
                            ;源操作数位于DS、目的操作数位于ES中
    
    pop ecx
    pop ebx
    pop edi
    pop esi
    pop es
    pop ds
    
    retf

为了能访问到这个4K字节页，把其物理地址登记到当前页目录表的倒数第二个表项中，即表内偏移0xFF8地址处。这个表项的线性地址为：

所以程序中，将附加了属性的页地址登记到这个线性地址处mov [0xfffffff8], ebx。

其中指令invlpg(Invalidate TLB Entry)用于刷新TLB中的单个条目。TLB是一个附加的硬件机构，只有处理器正常访问内存时才会导致它的填充和更新。

这条指令是特权指令，在保护模式下执行的特权级必须是0，此指令不影响任何标志位。

为什么新页目录表的线性地址是0xFFFFE000呢？

28. 第二个用户任务的创建和分页模式下的任务切换

在加载和创建用户任务之后，处于就绪状态，随时可以执行。在本章中任务切换是自动进行的，是由一个实时时钟信号驱动的，时钟芯片每秒钟发出一个中断信号，中断发生时处理器执行设置好的中断处理过程。这个中断处理过程就用于执行任务切换。

中断处理过程就是rtm_0x70_interrupt_handle例程，调用initiate_task_switch从TCB链表中找到当前状态为忙的任务将其状态改为就绪、再找到后面第一个就绪的任务将其状态设置为忙，切换任务执行。

一旦内核任务重新执行时，将执行后续指令：

    push dword 50                      	;用户程序位于逻辑50扇区
    push ecx                           	;压入任务控制块起始线性地址 
    call load_relocate_program
    call append_to_tcb_link            	;将此TCB添加到TCB链中
                                        ;此时有2个任务轮流执行
    
    
    ;可以创建更多的任务，例如：
    mov ecx,0x4a
    call sys_routine_seg_sel:allocate_memory
    mov word [es:ecx+0x04],0           	;任务状态：空闲
    mov dword [es:ecx+0x46],0          	;任务内可用于分配的初始线性地址
    
    push dword 100                     	;用户程序位于逻辑100扇区
    push ecx                           	;压入任务控制块起始线性地址
    
    call load_relocate_program
    call append_to_tcb_link            	;将此TCB添加到TCB链中
                                        ;此时有2个任务轮流执行
    
.do_switch:
    mov ebx,core_msg2
    call sys_routine_seg_sel:put_string
    
    ;清理已经终止的任务，并回收它们占用的资源
    call sys_routine_seg_sel:do_task_clean
    
    hlt			;停机之后，任何时候发生中断
                ;处理器将会被唤醒继续执行任务切换
    
    jmp .do_switch

用户程序和上一章相同：用户程序1打印，，，，，，…、用户程序2打印cccccc…

SECTION code vstart=0
start:
    ;任务启动时，DS指向头部段，也不需要设置堆栈 
    mov eax,ds
    mov fs,eax
    
    mov ax,[data_seg]
    mov ds,ax
    
.do_prn:
    mov ebx,message_1
    call far [fs:PrintString]
    jmp .do_prn
    
    call far [fs:TerminateProgram]      ;退出，并将控制权返回到核心 
    
code_end:

29. 分页模式下多任务切换的演示和调试

加载程序：

Virtual Box虚拟机：

Bochs虚拟机：
设置断点：b 0x7c00
执行：c
设置断点：modebp，会在模式切换时停下
设置断点在进入内核的时候：

设置断点在创建第一个用户程序之前：

当前分页功能是关闭的：

执行到创建第一个用户程序这个断点之前：

page命令解析线性地址是如何映射的：

PDE行：第一行是该线性地址在页目录表中对应的表项，该表项填写了该线性地址对应页表的物理地址是0x21000，后面的023是属性信息，大写是1、小写是0
PTE行：第二行是该线性地址在页表内的登记项，页的物理地址是0、属性信息是3
从这两行直到线性地址中0对应的物理地址也是0

再看一下高端线性地址的对应：

页表物理地址是0x21000
这个物理页对应的物理页地址为0，之前把内核从低端映射到高端，那么这个地址就是高端的起始地址

进入例程load_relocate_program：

设置断点在ret 8处：

前面是内核任务为用户任务设置的地址对应关系。

此时用户任务的线性地址0被映射为0x35000：

blist命令查看设置过的断点信息：

第二个任务创建之后，线性地址0被映射为0x101000

即对于不同的线性地址会被映射到不同的页中，其物理地址是不同的。

执行信息：

xiaoeryu