OS实验汇总

北航OS实验总结，关于具体实现可能说得会少一些，主要是对整体思路流程和难点的梳理。

各种常量、函数和宏定义

  • BY2PG：一页的字节数，等于4096
  • PPN(x)/VPN(x)：查询在第几页，即除以一页的大小
  • npage：物理页数
  • memsize：总物理内存的字节数
  • alloc(n, align, clear)：分配n字节的空间，并且以align字节对齐，clear表示是否清零
    • 函数中的extern char end[];是Lab1中kernel.lds中的end，对应虚拟地址0x80400000，对应的物理地址为0x00400000。我们管理的物理内存也就是0x00400000~memsize-1
  • freemem：物理内存分配到哪个地方了
  • ULIM：0x80000000
  • PADDR(kva)：将内核的虚拟地址（kseg0）转化为物理地址，即减ULIM
  • KADDR(pa)：将物理地址转化为内核的虚拟地址，即加ULIM
  • pages[0]…pages[npages-1]：Page类型的页控制块（单个大小为12B）
  • page2ppn(struct Page *pp)：从Page指针到物理页数的转换，即这个指针是第几个pages
  • page2pa(struct Page *pp)：从Page指针到物理地址的转换；实现方式为先用page2ppn得到这是第几个控制块/物理页，再将页数左移12位
  • page2kva(struct Page *pp)：从Page指针到内核虚拟地址的转换；实现方式为KADDR(page2pa(pp))
  • pa2page(u_long pa)：查询地址pa所在页的pages指针
  • ROUND(freemem, width)：对齐
  • PDX(va)：获取一级页表项偏移
  • DTX(va)：获取二级页表项偏移
  • PTE_ADDR(va)：获取表项中的地址，即 将表项中的权限位 置零
  • PTE_V：有效位
  • PTE_D：可写位
  • panic_on(expr)：如果expr不等于0，则报错
  • Elf32_Ehdr：ELF头信息
  • Elf32_Phdr：段头表
  • ELF_FOREACH_PHDR_OFF(ph_off, ehdr)：循环枚举段头表的每一项，ehdr是ELF头信息，ph_off存当前偏移位置，_ph_idx存当前是第几项；ph_off需要自己额外定义，类型为size_t
  • STATUS_xxx：SR寄存器的每一位，可以参考预习教程中的图

Lab2 - 内存管理

内核程序启动

  • mips_detect_memory()：已经得到了物理内存的字节数memsize，除以物理页大小BY2PG得到页数npage

  • mips_vm_init()：通过alloc()分配npage个结构体Page的空间（注意这里分配的是管理结构的空间，不是页的空间）

    alloc(n, align, clear)表示分配n字节、以align对齐、是否清零，它是基于kseg0段、用memset直接操作的

    freemem存的是当前虚拟地址分配到什么位置了，最开始从end即虚拟内存0x80400000、物理内存0x400000开始分配

  • page_init()：初始化pages数组和空闲链表

页管理

Page的结构

1
2
3
4
5
6
7
Page {
	Page_LIST_entry_t {
		Page *le_next;
		Page **le_prev;
	} pp_link;
	u_short pp_ref;
}

Page_list结构：

1
2
3
Page_list {
    Page* lh_first;
}

需要注意的是，le_next指向的是下一个Page，而le_prev指向的是上一个Page的le_next。

pp_ref表示被引用了几次（也就是有多少个虚拟页映射到了这个物理页），如果引用次数为0就说明没有被占用。

Page_list仅包含一个Page指针，指向链表头。

关于链表的各种操作的实现此处不再赘述，关于Exercise 2.2需要补写的LIST_INSERT_AFTER也并不难。

管理方式

page_free_list是空闲链表，存的是所有空闲的页控制块。

  • 需要分配内存时，将空闲链表头部的页控制块从链表取出并分配
  • 当某页的引用次数为0时，将页控制块插入空闲链表头部

回顾上一节的page_init

主要干了这么几件事：

  • 初始化page_free_list

  • 以按页面大小对齐后的freemem为界限

    前面是已经被内核和管理结构使用的物理页，需要指定它们的pp_ref为1

    后面是还未被使用的物理页，它们的pp_ref是0，并且需要被插入page_free_list

关于Page管理的其它函数

int page_alloc(Page **new)：从空闲链表头部取出元素并分配（如果链表为空则报错），用page2kva获得该页管理的虚拟地址并清零。需要注意的是，这里并不需要修改pp_ref。

void page_free(Page *pp)：将pp插入空闲链表

void page_decref(Page *pp)：将pp_ref减一，如果减到0，就调用page_free

页表相关

页目录项类型名为Pde，页表项类型名为Pte，其本质都是u_long

函数中页目录的基地址一般叫pgdir，类型为Pde*，将pgdir加上PDX(va)即可得到所在的页目录项。在实现二级页表检索的函数pgdir_walk中，我们需要判断该目录项是否有效，根据要求判断是否需要调用page_alloc进行分配。接着通过页目录项pgdir_entryp找到对应页表(Pte*)KADDR(PTE_ADDR(*pgdir_entryp))（通过KADDR将物理地址转换成kseg0段的虚拟地址以便访问）

page_lookup：找到虚拟地址va的所在页，返回Page*，并将页表项存入*ppte；若va没有映射到任何页，则返回NULL

page_remove：取消虚拟地址va对物理页的映射，调用page_decref，最后更新TLB表项（TLB相关内容将会在后文进行说明）

page_insert：将虚拟地址va映射到pp控制的物理页，并将权限设置为perm（判断以前已经存在映射，如果以前的映射不一样，那么page_remove后正常执行；否则调用tlb_invalidate并修改权限位后直接返回）

不同地址的区分与转化

kseg0段

Page->物理页号：看数组下标（指针相减）即可；物理页号->Page：取对应下标的数组；

物理页号->物理地址：将页数左移12位；物理地址->物理页号：将页数右移12位；

物理地址->虚拟地址：+ULIM；虚拟地址->物理地址：-ULM；

我们实验中的物理内存大小为64MB，即0x00000000~0x03999999，对应的kseg0段上的虚拟地址是0x80000000~0x83999999（从0x84000000开始为“Invalide Memory”）

我们在内核态对物理内存进行修改时，都是通过kseg0段处理的。

kuseg段（两级页表）

  • 虚拟地址：

    • 31-22位为一级页表项偏移量，通过PDX(va)获取
    • 21-12位为二级页表项偏移量，通过PTX(va)获取
    • 11-0位为页内偏移量

  • 页表项：

    • 31-12位为物理页号
    • 11-0位为标志位，定义规范与EntryLo相同，除了有效位PTE_V和可写位PTE_D，其它位在本次Lab中不会涉及

    一个页表项为32位即4B，一页是4KB，故一级页目录中有1024个页表项，对应着1024个页表，每个页表占一页即4KB，故这些页表映射了4MB空间，对应用户空间的0x7fc00000~0x7fffffff。（0x7fc00000即mmu.h的地图中UVPT的位置；另外，图中PDMAP等于$4\times 1024\times 1024$，表示⼀个⼀级页表所映射的1024个⼆级⻚表的⼤⼩）

    在这个范围内，有1024个页表，对应着整个0x00000000~0xffffffff，而其中有一个页表映射的空间刚好是从0x7fc00000开始的，这个页表的编号是0x7fc00000>>12，而这个页表实际上就是页目录，对应着0x7fc00000~0x7fffffff范围内的所有页表项，这也就是页目录的自映射。

TLB

CP0寄存器中的EntryHi和EntryLo分别对应着TLB的Key和Data：

  • EntryHi即TLB的Key：由VPN（Virtual Page Number）（20位，由页目录偏移和页表偏移组成）和ASID（Address Space IDentifier）（用于区分不同的地址空间）组成
  • EntryLo即TLB的Data：由PFN（Physical Frame Number）（20位，物理页框号）和各种有效位组成，和页表项的格式一致

旧表项无效化

tlb_invalidate：更新页表项时，需要调用它进行旧表项无效化；具体来说就是将旧表项的Key写入EntryHi并通过tlbp指令查找对应旧表项，若存在，则将其清零（在EntryHi和EntryLo中写0并调用tlbwi）

TLB重填

do_tlb_refill：从BadVAddr中取出引发 TLB 缺失的虚拟地址，从EntryHi的 6~11 位取出当前进程的 ASID，根据虚拟地址和 ASID 查找页表，得到包含物理地址的页表项；将物理地址存入 EntryLo, 并执行tlbwr将此时的EntryHi与EntryLo写入到 TLB 中。

Lab3 - 进程与异常

进程

进程控制块Env

struct Env用于实现进程控制块PCB，各成员变量在指导书中已详细介绍、此处不再赘述；值得注意的是，结构体中有两个用于队列链接的成员，env_link控制空闲进程链表env_free_list，env_sched_link控制调度队列env_sched_list，其中env_sched_list是另外一种链表实现方式：TAILQ，即双端队列，可以在queue.h中查看对应的宏的使用方式。

Exercise 3.1即初始化两个队列：调度队列直接INIT即可；空闲队列在INIT之后还需要插入envs数组中的元素，由于题目要求编号更小的进程控制块被优先分配，所以需要将这NENV个元素倒序插入。

在env_init函数中除了Exercise 3.1的对两个队列进行初始化，还用page_alloc申请了一页物理内存作为页目录，并求出页目录基地址对应的内核虚拟地址base_pgdir，接着将内核中的页控制块pages数组和进程控制块envs数组映射到用户空间的 UPAGES 和 UENVS 处（可以在mmu.h的图中回顾UPAGES和UENVS的位置分布）。上述“映射”过程用map_segment函数实现，即Exercise 3.2的实验内容，将每页的内容分别用page_insert添加映射即可。这一部分内容是每一个进程共享的只读空间，之后在创建进程的时候，我们会将它们拷贝到每个进程的页目录中，让每一个用户进程都可以读取这部分内容。

进程标识ASID

在Lab2中提过，ASID，Address Space IDentifier，⽤于区分不同的地址空间，同⼀虚拟地址在不同的地址空间中通常映射到不同的物理地址。

ASID对进程具有唯一标识性，有6个bit，即只有64个可用的ASID，在本实验中用位图法管理，即asid_bitmap数组。

设置Env

流程：

  1. 从env_free_list中取出一个空闲控制块

  2. 填写进程信息，其中env_id用mkenvid分配，env_asid用asid_alloc分配

  3. 初始化页目录（env_setup_vm）

    用page_alloc申请一个物理页，作为页目录，并得到基地址对应的内核虚拟地址env_pgdir，然后将我们初始化时以base_pgdir为基地址的页目录中的UPAGES段和UENVS段（即地图中UTOP到UVPT这一段）拷贝到当前进程。

  4. 从链表中摘出

加载文件并创建进程

（我们目前没有实现文件系统，所以实验中暂时用的是数组）

下面是相关的各个文件及函数：

  • kern/env.c
    • static int load_icode_mapper(void *data, u_long va, size_t offset, u_int perm, const void *src, size_t len)：申请一个新的物理页，将src填在offset处，并将进程env=(struct Env*)data下的虚拟地址va映射到此页
    • static void load_icode(struct Env *e, const void *binary, size_t size)：先用elf_from将binary强转并存入ehdr，枚举段头表的每一项，调用elf_load_seg分别分配文件需要的空间和内存需要的空间。分配时有两段，一段是长度为bin_size的.text和.data，另一段是长度为sg_size-bin_size的.bss，加载地址布局可参考P85图3.2；最后，env_tf.cp0_epc表示恢复运行时PC的位置，这里指到程序入口e_entry
    • struct Env *env_create(const void *binary, size_t size, int priority)：先env_alloc，设置一些信息，然后调用load_icode并插入调度队列env_sched_list
  • include/elf.h
    • struct Elf32_Ehdr
    • struct Elf32_Phdr
    • ELF_FOREACH_PHDR_OFF(ph_off, ehdr)：循环枚举段头表的每一项，ehdr是ELF头信息，ph_off存当前偏移位置，_ph_idx存当前是第几项
  • lib/elfloader.c
    • const Elf32_Ehdr *elf_from(const void *binary, size_t size)：将binary强转为Elf32_Ehdr*类型，并判断size和魔数，如果合法则返回Elf32_Ehdr结构体，否则返回NULL
    • int elf_load_seg(Elf32_Phdr *ph, const void *bin, elf_mapper_t map_page, void *data)

调用结构：env_create调用load_icode，load_icode将load_icode_mapper作为参数调用elf_load_seg

进程的运行

env_run：运行新进程前需要保存旧进程的上下文（进程执行时所有寄存器的状态，也就是Trapframe），即curenv->env_tf=*((struct Trapframe *)KSTACKTOP - 1)；然后调用env_pop_tf恢复新进程的上下文。

中断与异常

流程：异常产生->异常分发->时钟中断

异常分发

在kern/entry.S中，exc_gen_entry用于异常分发，作用是保存上下文、取出Cause寄存器的2-6位、在exception_handlers数组（异常向量组，位于kern/traps.c）中找到对应的异常处理函数并调用。

时钟中断

区分中断和异常：

  • 异常：包括0号中断异常，1号存储异常等
  • 中断：（在本次实验中我们认为）属于异常的一种，包括4号时钟中断（IM4）等

Exercise 3.11需要在kern/kclock.S的kclock_init函数中设置时间片轮转的频率为200。

进程调度（时间片轮转）

对于调度链表，每次存储上下文后取出头部进程来调度。

Lab4 - 系统调用与 fork

系统调用

允许内核执行用户程序的代码不安全，因此需要一系列内核空间中的函数，当用户进程需要进行这些操作时，会引发特定的异常以陷入内核态，由内核调用对应的函数，从而安全地为用户进程提供受限的系统级操作。

补充：用户态和内核态由CP0SR寄存器中KUc位的值标志

关于syscall的实现，参考图4.1，Thinking4.1的第三问是关于参数的传递，需要对MIPS中函数调用中参数的传递进行理解，关于栈帧的更详细的内容在OSome网站的预习教程中有：http://os.buaa.edu.cn/tutorial。

fork

fork流程：

在运行过程中，如果遇到tlb mod异常，则会根据cow_entry()进行处理

写时复制COW

简单来说，就是不在一开始全部复制，而是将需要复制的页面的PTE_V标成0，PTE_COW标成1，到时候要写的时候由于PTE_V为0、触发异常，再分配新物理页。

Lab5 - 文件系统

磁盘空间布局

磁盘被分成若干个磁盘块（磁盘块是虚拟概念），在本实验中每个磁盘块大小为4096Byte；盘中有NBLOCK=1024个块。

第一个磁盘块当作引导扇区和分区表。

第二个磁盘块为超级块Super Block，用来描述文件系统的基本信息，包括：

  • s_magic：魔数，常量，用于标识文件系统
  • s_nblocks：磁盘块数量，本实验中为1024
  • s_root：根目录，类型为File，File具体内容在下一小节，其中f_type为FTYPE_DIR，fname为"/"

之后的一些块用位图管理磁盘资源，值得注意的是，1表示空闲，0表示占用；最后剩下的块就是用来存目录和文件的。

具体实现中（tools/fsformat.c的init_disk()），第0、1个块已经被占用，我们就从第2个块开始分配，需要 $\texttt{nbitblock}=\lceil \frac{\texttt{NBLOCK}}{\texttt{BIT2BLK}}\rceil$ 个块来作为位图（即 BLOCK_BMAP 类型），真正的数据从 $\texttt{nbitblock+2}$ 即 nextbno 的初值开始。我们指定这些作为位图的块的类型并将所有位都赋为 1，如果位图最后有一些由于不能整除而产生的无意义的边角料，我们把边角料对应的位赋为 0。最后对超级块赋值。

文件系统结构

（struct File的定义在user/include/fs.h）

需要注意的是 f_direct[NDIRECT] 表示各个数据块在磁盘上的位置，每个块是 4KB，最多10个块即40KB。

若超过40KB，则用 f_indirect 指向间接磁盘块：磁盘块大小仍是4KB，每一项32位即4B，为了方便我们前10个项留空，也就是共4KB/4B=1024个项，每项对应一个4KB大的磁盘块，即单个文件大小最大是4MB。

f_dir 表示父目录；f_pad用于使控制块占满 256B。

块缓存

文件系统服务也是一个进程，同样拥有 4GB 虚拟内存；我们将 DISKMAP 到 DISKMAP+DISKMAX 这一段作为缓冲区，映射磁盘空间。

DISKMAX 大小为 1GB，可以容纳 256 个大小为 4MB 的磁盘块。

文件系统的用户接口

这一部分涉及的文件和函数特别多，这里用偷来的一张图总结：

Lab6 - 管道和命令解释程序

最后一次实验没有上机，我**直接抄抄抄抄抄抄

挑战性实验（Lab4）

大致思路

如何传递信号

对于每个进程，我们维护一个待处理信号队列；

对于kill函数，我们只需通过系统调用、将这个信号丢到目标进程的待处理信号队列中即可。

何时处理信号

每次从内核态返回用户态都需要恢复现场，在ret_from_exception的前面对于待处理信号进行检查是一个不错的选择。

1
2
3
4
5
6
7
8
FEXPORT(ret_from_exception)
	move    a0, sp
	addiu   sp, sp, -8
	jal     do_signal
	nop
	addiu   sp, sp, 8
	RESTORE_SOME

如何处理信号

仿照do_tlb_mod的方式写出do_signal，如果选出一个可以被屏蔽的信号，就将信号码和处理函数传到入口函数，然后我们对于信号进行判断，根据需要调用信号处理函数。值得注意的是，我们在处理信号期间使用的掩码应该是信号的掩码而不是进程的掩码，我们需要对当前掩码进行备份、将进程掩码修改为信号掩码，等处理完毕，再用备份掩码修改回来。其中入口函数的写法可以模仿cow_entry。

其它需要注意的事情

  • 题目要求子进程继承父进程的sigaction，核心态比较方便进行操作，于是我们可以直接在sys_exofork()中将需要继承的信息传下去
  • 对于SIGSEGV，我们只需要在passive_alloc中的if判断中加上sys_kill(0, SIGSEGV)即可

具体实现及相关细节

信号集相关操作

这里是比较简单的部分，只涉及简单的位运算，故不做赘述。

进程控制块Env需要增加的内容

1
2
3
4
5
6
7
struct Env {
    u_int env_sig_handler_entry; //信号处理入口
	sigset_t env_signal_blocked; //进程掩码
	struct Env_pending_sig env_pending_sig; //待处理信号序列
	struct sigaction env_sig_handler[64]; //不同信号的掩码及处理函数
	u_int latest_time; //当前处理栈内最晚的时间戳
};

各成员的作用已在注释中标明。

对于其中的待处理信号序列，我用的是现成的TAILQ的队列操作，跟进程控制块的env_list和env_sched_list类似，我们可以创建一个env_free_sig，并对每一个进程创建一个env_pending_sig分别表示空闲的信号控制块和该进程待处理的信号控制块。

系统调用

  • syscall_sigaction()：sigaction()的系统调用，用于修改当前进程对应信号的struct sigaction
  • syscall_sigprocmask()：sigprocmask()的系统调用，用于对进程掩码进行各种修改
  • syscall_get_env_mask()：获取进程掩码
  • syscall_get_sig_mask()：获取信号掩码
  • syscall_kill()：传信号，即将信号码丢进对应进程的待处理信号队列
  • syscall_set_sig_entry()：在最开始（libos.c中）进行调用，设置初始进程的入口函数（在sys_exofork()中会将入口函数下传）
  • syscall_set_time_stamp()：更新对应进程的信号处理栈的最新时间戳

问题及解决方案

我们是在ret_from_exception处进行的检查，这意味着每次系统调用都会进行检查、发现可处理的信号就进行处理。（举个例子，我们在处理某个信号时时间片结束，当我们再次切换到这个进程时，经过ret_from_exception时则会暂时不管当前信号处理过程而对于另一个信号进行处理）

此外，（在多次询问助教后）我得知关于更详细的信号处理的顺序应该是这样的：信号是可重入的，我们可能会在处理A信号时收到B信号、开始处理B信号后又收到C信号，然后开始处理C信号……一方面，我们只需要考虑当前信号的掩码，也就是在处理C信号时无需考虑A、B信号和进程本身的掩码；另一方面，在A、B信号处理过程中收到并被阻塞的信号即使在C中不在屏蔽集中，仍然需要被屏蔽。一个进程只有一个待处理队列，我们需要想办法区分和处理之前已经被屏蔽的信号和当前不被屏蔽的信号。

我的解决方法是，对于信号记录一个时间戳。每有一个新的信号，我们就记录一次时间戳（全局变量），我们把一个进程的可重入信号看作是栈，那么这个栈需要内部元素的时间戳是单调递增的。也就是说我们在判断掩码等条件时，同样需要判断当前信号的时间戳是否大于栈顶元素的时间戳，满足条件才能处理该信号。

由于获取和修改时间戳本身是需要陷入内核的，因此我们需要实现得较为精细。我们可以通过一次系统调用同时修改时间戳并进行备份，具体系统调用函数如下：

1
2
3
4
5
6
7
void sys_set_time_stamp(u_int envid, int *stamp) {
	struct Env *e;
	envid2env(envid, &e, 0);
	int t = e -> latest_time;
	e -> latest_time = *stamp;
	*stamp = t;
}

具体处理过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
sigset_t mask_new, mask_backup;
int stamp_backup = cstamp;
syscall_set_time_stamp(0, &stamp_backup);
mask_new.sig[0] = syscall_get_sig_mask(0, num, 0);
mask_new.sig[1] = syscall_get_sig_mask(0, num, 1);
mask_backup.sig[0] = syscall_get_env_mask(0, 0);
mask_backup.sig[1] = syscall_get_env_mask(0, 1);
sigprocmask(SIG_SETMASK, &mask_new, NULL);
sa_handler(num);
sigprocmask(SIG_SETMASK, &mask_backup, NULL);
syscall_set_time_stamp(0, &stamp_backup);
int r = syscall_set_trapframe(0, tf);
user_panic("syscall_set_trapframe returned %d\n", r);