lab1-中断

首先将所有的.c文件编译成.o文件，之后的命令如下：

# 链接内核
ld -m elf_i386 -nostdlib -T tools/kernel.ld -o bin/kernel obj/kern/init/init.o obj/kern/libs/readline.o obj/kern/libs/stdio.o obj/kern/debug/kdebug.o obj/kern/debug/kmonitor.o obj/kern/debug/panic.o obj/kern/driver/clock.o obj/kern/driver/console.o obj/kern/driver/intr.o obj/kern/driver/picirq.o obj/kern/trap/trap.o obj/kern/trap/trapentry.o obj/kern/trap/vectors.o obj/kern/mm/pmm.o  obj/libs/printfmt.o obj/libs/string.o

# 链接bootblock
ld -m elf_i386 -nostdlib -N -e start -Ttext 0x7C00 obj/boot/bootasm.o obj/boot/bootmain.o -o obj/bootblock.o

# 查看elf文件信息
objdump -S obj/bootblock.o > obj/bootblock.asm
objdump -t obj/bootblock.o | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > obj/bootblock.sym

# 去掉elf文件中的elf header和section
objcopy -S -O binary obj/bootblock.o obj/bootblock.out

# 用bin/sign保证主引导扇区程序长度为512字节，且最后两个字节为55AA
bin/sign obj/bootblock.out bin/bootblock

# 写入虚拟硬盘
dd if=/dev/zero of=bin/ucore.img count=10000
dd if=bin/bootblock of=bin/ucore.img conv=notrunc
dd if=bin/kernel of=bin/ucore.img seek=1 conv=notrunc

# 启动qemu
qemu-system-i386 -parallel stdio -hda bin/ucore.img -serial null

CPU加电之后CS和EIP会有被设置为CS:EIP= F000:FFF0,这个逻辑地址所对应的物理地址为FFFF0H,这个物理地址在BIOS中，所以CPU加电后执行的第一条指令在BIOS中，主要做了：

将主引导扇区里的内容读进内存
跳转到0x7c00执行

从0x7c00启动主引导程序，这部分是汇编写的。bootloader的段基址是0，而我们要操作的地址为0x7c00,为了让汇编地址从0开始，可以让更改vstart的值为0x7c00。主要做了：

建立gdt表
切换到32位保护模式
跳转到c语言

c语言中：

读取elf header
根据elf header中的信息，把内核从1号扇区读0x00100000，代码中0x00100000由ph->p_va & 0xFFFFFF计算得到，ph->p_va是第一个段的虚拟地址0xC0100000，和0xFFFFFF做与运算得到0x00100000
跳转到elf header中入口地址执行

中断向量表在vectors.S中，所有中断发生后都调用trap()函数，trap()又会调用trap_dispatch()函数，在这个函数中，会根据不同的中断号做不同的处理。

应用程序运行的时候一般不会自己停止，操作系统想夺回CPU的控制权必须靠中断。实际上，今后学习的很多内容的入口都在中断里。

static void
trap_dispatch(struct trapframe *tf) {
    switch (tf->tf_trapno) {
        //在这里根据不同的中断号，进行相应的处理
    }
}

lab2-分页机制

内核的entry.S文件中自带了页目录表及页表，将物理内存的0～4M映射到了虚拟内存的高位，所以进入内核后可以直接开启分页机制：

接下来ucore会获取BIOS的e820中断关于内存的信息，这些信息被保存在物理地址0x8000处：

 size   , [begin,       end-1], 1为可用2不可用
---------------------------------------------
0009fc00, [00000000, 0009fbff], type = 1.
00000400, [0009fc00, 0009ffff], type = 2.
00010000, [000f0000, 000fffff], type = 2.
07ee0000, [00100000, 07fdffff], type = 1.
00020000, [07fe0000, 07ffffff], type = 2.
00040000, [fffc0000, ffffffff], type = 2.

我们发现仅有很少的内存是可用的，这是因为默认情况qemu仅分配给虚拟机128MB的内存。每4k内存被看作是一个物理页，每一个物理页都有一个Page结构与之对应：

空闲物理页会放到一个双向链表中，只需遍历这个链表就可以查找到所有空闲内存。对于连续的内存，可以用一个Page结构描述，这样可以提高效率：

在这之后为页目录表添加了自映射机制，将页目录表的最后一项改为页目录表的物理地址，这样只要虚拟地址的前20位都是1，访问的就是页目录表本身，方便遍历页目录表和页表：

进入保护模式一直用的是bootloader的GDT，内核在这里又重新定义了一下GDT。

static struct segdesc gdt[] = {
    SEG_NULL,
    [SEG_KTEXT] = SEG(STA_X | STA_R, 0x0, 0xFFFFFFFF, DPL_KERNEL),
    [SEG_KDATA] = SEG(STA_W, 0x0, 0xFFFFFFFF, DPL_KERNEL),
    [SEG_UTEXT] = SEG(STA_X | STA_R, 0x0, 0xFFFFFFFF, DPL_USER),
    [SEG_UDATA] = SEG(STA_W, 0x0, 0xFFFFFFFF, DPL_USER),
    [SEG_TSS]   = SEG_NULL,
};

我们发现，内核的数据段、代码段，用户的数据段、代码段都在GDT中定义。并且他们的界限都是0x0～0xFFFFFFFF，任何程序都可以访问任何内存。这么做相当于uCore放弃使用段机制，内存权限完全由页机制来限制的。

本节中有个page2kva函数比较难以理解。它的用途是根据物理页Page结构计算其对应的虚拟地址。

static inline void *
page2kva(struct Page *page) {
    return KADDR(page2pa(page));
}

static inline ppn_t
page2ppn(struct Page *page) {
    return page - pages;
}

static inline uintptr_t
page2pa(struct Page *page) {
    return page2ppn(page) << PGSHIFT;
}

由lab2可知，内核的页表项与物理页是按顺序排列的。所以只需要计算出物理页的个数，就可以知道页表项的个数，又因为页表项是从0地址开始映射的，所以知道页表项个数就可以计算出虚拟地址。当然，这种方法只对内核有效。

对于线性地址，前20位用来确定页表项，代码中用PPN(la)获取前20位。PPN(la)还可以代表从0地址开始到la有几个页表项(等于物理页个数)。

+--------10------+-------10-------+---------12----------+
| Page Directory |   Page Table   | Offset within Page  |
|      Index     |     Index      |                     |
+----------------+----------------+---------------------+
 \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
 \----------- PPN(la) -----------/

lab3-虚拟内存

现在我们的应用程序越来越大，比如matlab有20G，操作系统肯定不可能把这么多数据一下子全部加载到内存中，而是动态的把用到的物理页加载到内存，把不用的物理页放到硬盘中。

为此，启动qemu的时候多加了一块swap虚拟硬盘，用户虚拟内存：

dd if=/dev/zero of=bin/ucore.img count=10000
dd if=bin/bootblock of=bin/ucore.img conv=notrunc
dd if=bin/kernel of=bin/ucore.img seek=1 conv=notrunc
dd if=/dev/zero of=bin/swap.img bs=1024k count=128

qemu-system-i386 -parallel stdio -hda bin/ucore.img -drive file=bin/swap.img,media=disk,cache=writeback -serial null

当程序访问被换出的内存页时，会产生缺页异常，操作系统会在中断程序中将内存页再换进内存。

页表项的P位为1时，代表所映射的物理页存在，访问正常；而P位为0时，代表不存在，整个页表项的其它位都没有意义了，此时可以用高24位作为在磁盘交换扇区中的偏移索引：

换入是在触发中断时进行的，调用流程为trap--> trap_dispatch-->pgfault_handler-->do_pgfault-->swap_in。

每次分配物理页的时候都会进行换出，调用流程为操作系统为应用程序分配内存->alloc_pages->swap_out。

操作系统的换出算法是非常复杂的，uCore为了方便教学仅实现了FIFO(先进先出)算法，即最先被创建的页面，最先被换出去。

uCore没有使用段机制来限制权限，而是使用页机制来限制权限。页表空间有限，而且页表是“离散”的，不利于搜索。所以很有必要为虚拟内存创建一个数据结构。

在本节中，pmm.c文件中实现了一个重要函数kmalloc。他是Kernel memory allocation的缩写，在linux内核代码中，需要内存分配时都会使用这个函数，所以我们需要捋一遍这个函数的过程：

从空闲物理页链表中，取出物理页
根据相应的内存交换算法，将长时间未使用的物理页移到硬盘中
使用page2kva函数将Page结构地址转化为虚拟地址

lab4-内核线程管理

系统启动后，只有一个程序在运行，我们把这个程序叫做idle，之后fork出了一个init线程。因为init与idle都在内核空间，有着相同的内存，所以他们属于线程。

idle线程、init线程和当前线程太过重要，内核中有专门的全局指针，在后面的lab中，访问当前线程的数据结构，只需要访问全局指针current即可：

// idle proc
struct proc_struct *idleproc = NULL;
// init proc
struct proc_struct *initproc = NULL;
// current proc
struct proc_struct *current = NULL;

lab5-用户进程管理

lab5的工作流程如下图所示：

内核空间的都属于线程，因为他们都有着共同的内存。但是用户空间的程序我们不能给它和和内核一样的内存。所以需要为每个进程分配mm_struct。

uCore的做法是先fork出一个user_main内核线程，然后替换掉user_main的mm_struct结构，使之变为一个用户进程。

Linux系操作系统创建进程时先fork父进程，这是因为linux多用于服务器，当大量用户请求服务器时会产生大量相似的进程，fork父进程可以与父进程共用只读的内存页(copy on write机制)，这样可以提高内存利用率。Windows主要面向个人电脑，不存在大量相似进程，所以进程是直接创建的。

lab6-调度器

初学者可能会有这样的疑问：一个进程需要执行1分钟，另一个进程也需要执行1分钟，共需2分钟。采用调度机制后，在这两个进程间切换着执行，总时间也应该是两分钟才对呀？

CPU的运行速度比I/O速度快得多，他们的速度差距好比天上一日地上一年。进程的绝大部分时间都在等待I/O的结束，所以利用等待的这段时间执行一下别的工作，等别的工作执行完回来，I/O有可能还没结束呢。

从操作系统的角度，当前运行进程的指针只有一个，操作系统只承认当前进程指针所指的进程正在运行，I/O操作的时候进程会被放到等待队列，此时进程不算正在运行，上图三个进程为并发运行。因为I/O的速度与CPU的速度有数量级的差距，进程大多数时间都在等待I/O，所以如果进程数量不是太多，并发并不比并行慢。

调度器有一个全局的指针：

static struct sched_class *sched_class;

它的结构如下：

struct sched_class {
    // 调度类的名字
    const char *name;
    // 初始化就绪队列
    void (*init)(struct run_queue *rq);
    // 将一个线程加入就绪队列(调用此方法一定要使用队列锁调用(lab6中直接关中断来避免并发))
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
    // 将一个线程从就绪队列中移除(调用此方法一定要使用队列锁调用(lab6中直接关中断来避免并发))
    void (*dequeue)(struct run_queue *rq, struct proc_struct *proc);
    // 调度框架从就绪队列中选择出下一个可运行的线程
    struct proc_struct *(*pick_next)(struct run_queue *rq);
    // 发生时钟中断时，调度器的处理逻辑
    void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc);
};

uCore在进程调度时，只需调用sched_class中的函数。至于这几个函数，不同的算法有不同的实现方法。在sched_init函数中，sched_class被初始化为default_sched_class，即用default_sched_class作为调度器：

sched_class = &default_sched_class;

如果想换用其他的调度器，只需在这里将sched_class全局指针改为其他的调度类即可。

uCore的默认调度算法为时间片轮转调度算法，非常无趣，这里就不介绍了。相比之下我更喜欢多级反馈队列算法。

lab7-同步互斥

多个线程同时做一件事，可能会出现单线程时没有的错误。这是因为有些内容是要一口气做完的(原子操作)，如果做到一半调度到另一个线程，而另一个线程也在操作相同的资源，当再调度回去后数据变了，程序就很可能出错。

原子操作按顺序执行叫同步，原子操作不同时执行叫互斥。同步互斥问题主流的办法是使用操作系统的信号量和管程机制。

信号量就是一个整型变量，变量的值代表资源数，当信号量大于0时，允许访问临界区(会产出同步互斥问题的代码)，否则不允许进入等待队列，执行系统调度让其他线程占用CPU。信号量的关键在于先关中断，再对信号量进行增减和查询，之后再打开中断，这样可以保证信号量的同步互斥，从而用信号量保护的临界区也实现了同步互斥。

信号量很好用，但是大量使用信号量时容易造成混乱，更重要的是如果使用不当会造成死锁。

为了解决这个问题，则有了管程这个概念。管程只是对很多个信号量打了个包，这样信号量可以统一管理，最重要的是使用管程不会造成死锁：

lab8-文件系统

lab8启动时又多了一块sys.img虚拟硬盘：

dd if=/dev/zero of=bin/ucore.img count=10000
dd if=bin/bootblock of=bin/ucore.img conv=notrunc
dd if=bin/kernel of=bin/ucore.img seek=1 conv=notrunc
dd if=/dev/zero of=bin/swap.img bs=1M count=128
dd if=/dev/zero of=bin/sfs.img bs=1M count=128

qemu-system-i386 -serial stdio -hda bin/ucore.img -drive file=bin/swap.img,media=disk,cache=writeback -drive file=bin/sfs.img,media=disk,cache=writeback -parallel null

lab8启动后运行了第一个用户程序sh.c，它是一个类似于bash的进程，可以根据用户输入执行相应的命令。例如，输入ls，就会列出当前目录中的文件。

ls和sh都是用户程序，他们向下调用的层次结构如下：

虚拟文件系统的目的是把不同的文件系统封装起来，为上层提供统一的接口。它将常规文件、目录、设备文件抽象成inode，上层对文件操作都转化为使用inode_ops对inode的操作。这里的inode_ops就是统一的接口。

不同的inode对于inode_ops的实现不同：

static const struct inode_ops dev_node_ops = {
    .vop_magic                      = VOP_MAGIC,
    .vop_open                       = dev_open,
    .vop_close                      = dev_close,
    .vop_read                       = dev_read,
    .vop_write                      = dev_write,
    .vop_fstat                      = dev_fstat,
    .vop_ioctl                      = dev_ioctl,
    .vop_gettype                    = dev_gettype,
    .vop_tryseek                    = dev_tryseek,
    .vop_lookup                     = dev_lookup,
};

static const struct inode_ops sfs_node_dirops = {
    .vop_magic                      = VOP_MAGIC,
    .vop_open                       = sfs_opendir,
    .vop_close                      = sfs_close,
    .vop_fstat                      = sfs_fstat,
    .vop_fsync                      = sfs_fsync,
    .vop_namefile                   = sfs_namefile,
    .vop_getdirentry                = sfs_getdirentry,
    .vop_reclaim                    = sfs_reclaim,
    .vop_gettype                    = sfs_gettype,
    .vop_lookup                     = sfs_lookup,
};

static const struct inode_ops sfs_node_fileops = {
    .vop_magic                      = VOP_MAGIC,
    .vop_open                       = sfs_openfile,
    .vop_close                      = sfs_close,
    .vop_read                       = sfs_read,
    .vop_write                      = sfs_write,
    .vop_fstat                      = sfs_fstat,
    .vop_fsync                      = sfs_fsync,
    .vop_reclaim                    = sfs_reclaim,
    .vop_gettype                    = sfs_gettype,
    .vop_tryseek                    = sfs_tryseek,
    .vop_truncate                   = sfs_truncfile,
};

在虚拟文件系统层面，看到的都是一些inode，所有操作都是调用inode_ops对inode操作。

因为inode_ops的不同，对inode操作就会转化为对设备的操作，和对simple文件系统中的inode操作。

simple文件系统也比较简单，sfs_inode存储着每个文件数据块的位置，root-dir sfs_inode存储着根目录文件的sfs_inode：

当一个进程打开一个文件时，会返回一个文件描述符，这其实是current->fs_struct->filemap[]这个数组的索引值，进程打开的所有文件都会存储在这个数组中。数组项是file结构体，里面存储了文件的权限等信息和虚拟文件系统的inode指针。

附录-ATA标准

ATA(Advanced Technology Attachment)是用于连接存储设备的接口标准。一般说来，ATA是一个控制器技术，而IDE(Integrated Drive Electronics)是一个匹配它的磁盘驱动器技术，但是两个术语经常可以互用。

ATAPI（ATA Packet Interface）是一种ATA协定，允许使用ATA连接到更多的周边装置，不仅限于连接硬盘。

详细内容可以参考标准手册AT Attachment with Packet Interface。

简单简要来说，硬盘控制器有8个端口0x1f0~0x1f7，先要将读取参数根据要求设置到寄存器中，然后再从相应端口读数据。

static void
readsect(void *dst, uint32_t secno) {
    // 等待硬盘准备就绪
    while ((inb(0x1F7) & 0xC0) != 0x40)

    // 设置要读取的扇区数
    outb(0x1F2, 1);

    // 设置起始LBA扇区号
    outb(0x1F3, secno & 0xFF);
    outb(0x1F4, (secno >> 8) & 0xFF);
    outb(0x1F5, (secno >> 16) & 0xFF);
    outb(0x1F6, ((secno >> 24) & 0xF) | 0xE0);

    // 读命令
    outb(0x1F7, 0x20);

    // 等待硬盘准备就绪
    while ((inb(0x1F7) & 0xC0) != 0x40)

    // 读数据
    insl(0x1F0, dst, SECTSIZE / 4);
}

附录-内存安全

uCore没使用段机制，只使用了页机制，那么它是如何保证内存安全的？

假如一个木马程序想获取其他程序的登陆密码，即便木马程序知道目标程序密码所在的内存地址也访问不了，因为有分页机制的存在，所有的程序都运行在独立的用户空间，只能访问到自己的页表中的地址。

木马程序不能更改页表，因为它没有写权限和特权级。在页表中有两个标志位：

Read/Write标志位页表的读写权限
User/Supervisor标志访问页表所需的特权级

访问页表是硬件自动完成的，这个过程会判断相应的权限，如果权限不符就会报缺页异常，从而保证了一个程序的数据不被其他程序恶意盗取。

uCore操作系统学习笔记