本文根据慕课资料进行粗略学习操作系统的知识，选择性地写一下lab练习
ucore课程文档
课程地址
其他大佬的lab答案地址
推荐博客1
推荐博客2
建议先阅读《编码：隐匿在计算机软硬件背后的语言》和《X86汇编语言-从实模式到保护模式》

CPU加电后会进行初始化，然后在内存读第一条指令。内存有一部分是ROM、一部分是RAM。断电后RAM信息会消失，但是ROM内容一直都在。
读的第一个指令是CS:IP指向的地址（值应该是默认的），刚加电的CPU处于16位实模式下，寻址空间大小为2的20次方（1MB），CS、IP都是16位的。CS*16+IP（0xFFFF0）是第一条指令的地址，同时CS:IP要在2的20次方的寻址空间内。第一条指令在最底下的1MB空间内。这第一条指令及其跟着的指令就是BIOS，它要提供一些服务，然后CPU才能访问磁盘设备。

BIOS从磁盘读引导扇区（512字节）里的加载程序，将其写到内存0x7c00，然后CS:IP跳到那里去执行加载程序（bootloader）。
详细一点说，BIOS只能在实模式下运行，它先是检查硬件，进行设备初始化。修电脑时，显示器不工作，可以猜测内存有问题。因为BIOS先检查到内存有问题，后面它就不用检查了，也不启动系统了。然后检查插入的U盘、磁盘什么的。检查产生的信息成为BIOS数据。虽然ROM数据不会消失，但是因为每次插入的硬件不一样，所以BIOS会改这些数据。最后读我们磁盘的第一个扇区。BIOS先读磁盘的主引导扇区（512字节）。因为这个东西提供的信息可以帮我们选择启动磁盘里的哪个操作系统。根据主引导扇区的信息来选择并读取活动分区（分区引导扇区）。先执行分区引导扇区的跳转指令，跳转到启动代码启动到加载程序。

加载程序把磁盘的ucore操作系统数据和代码加载到内存，再跳到ucore起始地址。把控制权交给操作系统。
详细地说，加载程序会先从文件系统中读取启动配置信息，依据这些信息决定怎么加载内核，这个地方如果我们可以弄一个选项在显示屏（启动菜单），可以改参数就很好。最后跳到内核。

知道这些还是很粗糙，如果写实际程序，还要根据CPU手册、BIOS规范（从哪里读第一条，上文是0xFFFF0）。所以自己写操作系统还是要查很多资料的。

BIOS

这里的主引导扇区的硬盘分区表只有四个分区信息，每个分区信息16字节（BIOS-MBR）。BIOS-GPT则支持超过四个分区。PXE是网络启动，从服务器下载资料到磁盘来启动，此时BIOS要有网络下载功能，BIOS变复杂了。前面说的是在本地磁盘启动。

UEFI

在所有平台一致地启动操作系统。启动磁盘的任何系统。为了安全，检查引导记录是否可信。只读取满足签名的引导记录。

查资料

知乎BIOS与UEFI区别

加载程序（bootloader）先定义全局描述符表，然后让CPU从实模式进入保护模式，最后加载内核文件。

我们知道，为了让程序在内存中能自由浮动而又不影响它的正常执行，处理器将内存划分成逻辑上的段，并在指令中使用段内偏移地址。在保护模式下，对内存的访问仍然使用段地址和偏移地址，但是，在每个段能够访问之前，必须先进行登记。
《X86汇编语言-从实模式到保护模式》

每个段由8字节的段描述符描述，描述表存放描述符。
最主要的描述表是全局描述表（Global Descriptor Table，GDT）。还有一个是局部描述表。
CPU有一个48位全局描述表寄存器（GDTR）。它分为32位的线性地址和16位的边界。GDTR 的线性地址部分保存的是全局描述符表在内存中的起始线性地址。边界保存的是全局描述表的边界，其在数值上等于表的大小（总字节数）减一。

GDT最大大小是16位（216字节），由于在实模式下只能访问1MB 的内存，所以GDT 通常都定义在1MB 以下的内存范围中。

bootasm.S

asm.h里面是实现如何创建GDT，不清楚原理

练习2：使用qemu执行并调试lab1中的软件

下载上面的lab答案，进入lab1_result目录，执行

练习5：实现函数调用堆栈跟踪函数 （需要编程）

我们要实现kern/debug/kdebug.c里面的print_stackframe()
堆栈跟踪函数就是把寄存器信息打印一下

由于显示完整的栈结构需要解析内核文件中的调试符号，较为复杂和繁琐。代码中有一些辅助函数可以使用。例如可以通过调用print_debuginfo函数完成查找对应函数名并打印至屏幕的功能。具体可以参见kdebug.c代码中的注释
《ucore_os_docs》

那就很方便了

概念

物理地址就是总线看见的地址，逻辑地址是进程看到的地址

逻辑地址生成

程序源代码经过编译和汇编后得到预备的地址，再链接添加函数库地址，当加载到内存时会重定向地址。相当于加载之前是确定内部各个指令的相对位置，加载后再确认绝对位置。
上面是加载时生成，还有编译时生成、执行时生成

逻辑地址处理

CPU如果见到一个指令的地址，CPU里面的MMU就把它翻译成物理地址，CPU就找这个地址并结合处理信号来处理。如果逻辑地址访问非法，产生异常。

为了方便，内存分配大小设计为2的整数次幂

内存碎片

不能利用的内存空间（太小了）

外部碎片和内部碎片

动态内存分配

根据内存占用情况进行分配。方法有最先匹配、最佳匹配、最差匹配
空闲分区列表储存空闲分区
释放分区时合并临近地址的空闲内存分区，调整空闲分区列表

最先匹配

思路：需要分配内存时按从低到高顺序寻找第一个可以满足的空闲内存空间，空闲分区列表按地址顺序排序
优点：简单、在高地址空间有大块的空闲分区
缺点：外碎片多，导致寻找大块时要遍历更多次，寻找大块时较慢

最佳匹配

思路：寻找满足需求中最小的内存分区，空闲分区列表按大小顺序排序（可以由小到大，都行）
优点：大部分分配的尺寸较小时效果好、避免大的空闲分区被拆分、可减小外部碎片大小、相对简单
缺点：内外部碎片更小，更加不能利用

最差匹配

思路：寻找满足需求中最大的内存分区，空闲分区列表按大小顺序排序（可以由大到小，都行）
优点：中等大小的分配较多时，效果最好，小碎片少
缺点：后续大内存分配难

下面是碎片整理的一些方法

紧凑

把进程占用内存压到一起，不过需要指令内容的地址要变，也就是应用程序可以动态重定向。这个操作要在进程处于等待时进行。

分区对换

进程处于等待时把它的数据放到外存

假设可分配分区大小为2的u次幂，需要分配内存空间为m。如果两倍m大于2的u次幂且m小于等于2的u次幂就分配，否则把2的u次幂分一半，继续跟m比。
合并时注意大小是2的整数次幂。

合并条件

大小相同（2的i次幂）、地址相邻、起始地址较小的块的起始地址必须是2的i+1次幂的倍数

如果最大的连续内存都不够，可以继续非连续内存分配。段式分配的单位内存大，页式小。可以把段式和页式结合起来成为段页式。

非连续内存分配设计目标

提高内存利用效率和管理灵活性
允许一个程序的使用非连续的物理地址空间
允许共享代码与数据
支持动态加载和动态链接

概念

段表示访问方式和存储数据等属性相同的一段地址空间
进程的段空间由多个段组成：主代码段、子模块代码、公用库代码段、堆栈段（stack）、堆数据（heap）、初始化数据段、符号表等

段访问及实现

概念

物理地址空间基本单位叫页帧（Frame），大小为2的n次方。虚拟地址空间基本单位叫页面（Page）

页帧

如上图，F=7，S=9，f=3，o=3

页面

逻辑空间地址被划分为大小相等的页
页内偏移等于帧内偏移
通常页号大小不等于帧号，因为页号经过转换后不一定对应相等的帧号
虚拟地址表示：页号（p）和偏移量（o）
虚拟地址=p+o

通过页找到帧

页表

每个进程都有一个页表，每个页面对应一个页表项。页表随进程运行状态动态变化。页表基址寄存器（PTBR）可以告诉我们页表基址。PTBR的值是通过CR3寄存器获取的。

页表项组成

页表由帧号、页表项标志组成
页表项标志：存在位、修改位、引用位
存在位：一个逻辑页号是否存在一个物理帧与它相对应，如果有则为1
修改位：页面内容是否修改
引用位：页面是否有过被引用、被访问

页式储存管理优化

缓存：把一次获取的页表项的后面几项缓存起来，可能下次用
间接访问：多级页表，把一个页表分多个，方便找

快表（TLB）和多级页表

反置页表

如果页表级数过多，访问页表次数增加，很繁琐，所以有了反置页表。
反置页表是页表与物理地址相对应，所有进程共同使用一张页表

页寄存器

每个帧与一个页寄存器关联，寄存器内容包括：使用位、占用页号（逻辑页号p）、保护位（访问方式，比如：可读，可写）
优点：页表大小相对于物理内存很小、页表大小与逻辑地址空间大小无关
缺点：页表信息对调后，需要依据帧号可找页号、在页寄存器中搜索逻辑地址中的页号困难

页寄存器中的地址转换

对逻辑地址的p和进程ID（PID）的数字之和进行哈希算法，用哈希表映射，减少搜索访问，解决哈希冲突。检查页号和页表的PID跟请求的页号和页表的PID是否一样，其他步骤跟前面一样

反置页表的哈希冲突

用得到的哈希值H（即页表第H条）在页表查时发现对应的PID和页号跟哈希前不一样，没关系，页表还提供下一个PID和页号之和哈希值为H的地址

段式存储管理基础

逻辑地址由s（段号）、p（页号）、o（偏移）组成
物理地址由f（帧号）、o（偏移）
先根据s找段表的对应段表项，再根据p找页表中对应的页表项，最后根据o得到具体物理地址。
通过指向相同的页表基址，可以实现进程间的段共享

了解x86保护模式中的特权级

特权级范围是从0到3级
ucore和Linux都只有ring0级（内核级）和ring3级（用户级）

段选择子

上图的RPL（描述特权级大小）与数据段相关，后面讲的的CPL与代码段相关，与段描述符的DPL（描述段特权级是ring0还是其他什么）比较，RPL象征的权限大于大于DPL才能执行、访问或者中断。中断门（Interrupt Gate）、陷入门（Trap Gate）也有DPL。
段寄存器DS,ES,FS,GS里面有RPL
段寄存器CS,SS里面有CPL
访问门时：CPL<=门的DPL（也就是门特权级低）&CPL>=段的DPL
为什么CPL>=段的DPL？这就体现了ring3应用程序访问ring0级服务的情况
访问段时：MAX（CPL,RPL）<=段的DPL

了解特权级切换过程

通过中断切换特权级
产生中断时，把当前状态保存在属于ring0的栈里面

ring0到ring3的切换

把属于ring0的栈里面的CS的CPL改为3（ring3），SS的RPL改为3，EIP看情况改

ring3到ring0的切换

把属于ring0的栈里面的CS的CPL改为0（ring0），CS指向地址也改，SS和ESP清除，不要ring3的栈了，EIP改

任务状态段（Task-State Segment）

它保存了寄存器的特权信息，ring3到ring0的切换需要的新栈（SS、ESP在栈里面的信息已经清除）相关的寄存器设置就是根据TSS来的
TSS描述符（保存TSS地址等信息）也放在全局描述表里面
对于ucore，就利用TSS里面的SS、ESP信息
Task Register寄存器会缓存TSS地址信息，方便查找

了解段页表

段寄存器

段寄存器一部分内容是index，作为一个索引来找到全局描述符表中的一个项（段描述符）
如果没有开启页基址，CS:IP等就是物理地址，但还是要通过段描述符来映射

段选择子中的隐藏部

GDT因为占空间大所以放在内存里面，硬件会把GDT的段描述符的关键信息放在段寄存器的隐藏部分（用来缓存）

映射

虚拟地址比线性地址（逻辑地址到物理地址变换之间的中间层）大0xC0000000（7个0）
选择页机制为主

了解UCORE建立段/页表

线性地址由32位组成，0到11位是offset，12到21是table，22到31是directory（页目录）。根据directory从page directory（页目录表）找到对应的项PDE，比如directory就表示查表的第directory项，后面也是一样。PDE记录的是二级页表里面的起始地址。根据table从page table找到对应的项PTE（page table entry），PTE存的是线性地址对应的页的起始地址。PTE左移三位加上offset作为最终物理地址。
CR3寄存器保存页目录表的起始地址。

页表或者页目录表包含哪些信息

除了关注页表或者页目录表中的基址信息，还有关注它们的属性。
比如是否可读，是否ring3级别能访问等。

使能页机制

CR0第0位（PE）如果置1，则enable保护模式，第31位（PG）如果置1，就代表使能了页机制

存储器速度排行

虚拟储存需求

内存空间不够时，有两种方法
覆盖：应用程序手动把需要的指令和数据分时间段在内存中保存和清除
交换：操作系统自动把暂时不能执行的程序保存到外存中
虚拟储存：在有限容量的内存中，以页为单位自动装入更多更大的程序

覆盖技术

交换技术

以进程为单位，将暂时不能运行的程序放到外存，程序在换入时要重定位
交换时机：只有当内存空间不够或者可能不够时换出

局部性原理

时间局部性：一条指令两次执行或者一个数据的两次访问都集中在一个较短时期内
空间局部性：邻近的指令和数据集中在一个较小区域内
分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置，比如循环，重复跳到循环第一句

虚拟存储的基本概念

思路：将不常用的部分内存块暂存到外存
原理：装载程序时，只将当前指令执行需要的部分页面或段装在内存内。如果指令执行中需要的指令或数据不在内存（缺页或者缺段），处理器通知操作系统将对应的页面或段调入内存。操作系统将内存中暂时不用的页面或段保存到外存。
实现方式：虚拟页式存储、虚拟段式存储
特征：不连续性，物理内存分配非连续，虚拟地址空间使用非连续。大用户空间，提供给用户的虚拟内存可大于实际的物理内存。部分交换，虚拟存储只对部分虚拟地址空间进行交换

虚拟页式存储地址转换

地址转换和页式存储的地址转换一样

页表项结构

缺页异常

CPU读取一条指令，会去找这条指令所对应的页表项，如果这一项是无效的，会发生缺页异常，缺页异常服务例程执行。