前言
操作系统是一种复杂的系统软件。本书通过介绍操作系统的基本概念和原理，并结合操作系统原理来分析一个小型但全面的操作系统xv6，并进一步进行各种基于xv6操作系统的实验，来让读者了解和掌握操作系统的设计与实现。xv6是一个运行在基于x86架构的计算机系统上的类似UNIX的教学用操作系统。xv6起源于MIT。在2002年秋季，Frans Kaashoek, Josh Cates, and Emil Sit在MIT开设了一门新的实验型课程“操作系统工程”，英文名称是“Operating Systems Engineering”，课程代号是“6.097”，后改为“6.828”，在此课程上，一开始采用了“莱昂氏UNIX源代码分析”（英文书名是“Lion'Cornmentary on UNIX 6th Edition With Source Code”）作为参考资料。此参考资料描述的UNIX v6（简称V6）是运行在古老的PDP-11计算机系统上。为了让学生更好地理解V6的实现，Frans Kaashoek等从2006年夏季开始，参考V6的架构，在x86计算机系统上重新实现了一个支持多处理器计算机系统的类似UNIX的教学用操作系统，称为为xv6。在目前的MIT本科生课程“6.828: Operating Systems Engineering”中，xv6主要用于讲课，而另一个基于exokernel架构的JOS主要用于做试验。 目前xv6在MIT的网址在 http://pdos.csail.mit.edu/6.828/xv6/
第零章 安装使用
如果是Linux初学者，请看附录F，了解如何安装、使用Ubuntu Linux，如何在Ubuntu Linux下编程。
编译[need update]
安装Ubuntu Linux 8.10，具体安装方法可以参考附录C。并通过apt工具进一步安装相关软件包
$ sudo apt-get install gcc binutils libc 6-dev gdb
然后解压xv6软件包，到某一目录，然后到此目录下执行
$make
就可以生成相关执行文件和镜像，包括xv6.img(包含bootloader和xv6 kernel)和fs.img(包含应用程序)
运行[need update]
安装Ubuntu Linux 8.10，并通过apt工具进一步安装相关软件包
$sudo apt-get install qemu bochsbios vgabios libsdl1.2debian kvm
如果通过qemu执行，可执行如下命令
qemu -smp 4 -parallel stdio -hdb fs.img -hda xv6.img
如果通过kvm执行，可执行如下命令
kvm -smp 4 -parallel stdio -hdb fs.img xv6.img
qemu和kvm的相关运行参数的含义可参考附录B。
调试[need update]
对qemu而言，可以同时实现qemu内嵌的debugger调试（需要打陈渝老师扩展的patch并重新编译生成新的qemu，特点是简单，可控制硬件的手段多，缺点是不是C源码级调试）和通过gdb远程调试（特点是是可进行C源码级调试，缺点是可能会有奇怪的问题，对硬件控制不够）。
1 用gdb远程调试的方法如下： a qemu调试方式启动
qemu -S -s -smp 2 -monitor stdio -hdb fs.img -hda xv6.img
b gdb启动并调试
gdb kernel
(gdb) target remote :1234 (gdb) break FUNCTION-NAME (gdb) continue ...
(gdb) quit
2 用qemu internal debugger调试 a qemu启动命令
qemu -smp 2 -monitor stdio -hdb fs.img -hda xv6.img
然后在qemu的monitor中可执行如下命令进行调试分析 x /fmt addr -- virtual memory dump starting at 'addr' info cpus -- show infos for each CPU info registers -- show the cpu registers
singlestep singlestap_enabled -- toggle singlestep mode breakpoint_insert addr -- insert breakpoint breakpoint_remove addr -- remove breakpoint breakpoint_show -- show breakpoint
watchpoint_insert addr type -- insert watchpoint type 0=read 1=write watchpoint_remove addr -- remove watchpoint watchpoint_show -- show watchpoint where -- show calls stack
第一章 总体结构和系统组成
本章将给出xv6启动实现的概貌。读者将学习以下一些内容:
? 操作系统是什么？ ? xv6是如何产生的？ ? xv6的总体结构是什么？
? xv6包含哪些重要的组成部分？
操作系统是一种软件，操作系统没有一个精确和统一的定义。操作系统是一种比较复杂的软件，我们可以从多种角度来了解操作系统。从操作系统的任务来看，操作系统的任务主要是控制和管理计算机系统中的硬件资源并对应用软件和用户提供各种方便使用计算机的功能。通过操作系统，能有效地组织和管理计算机系统中的硬件资源和其他软件资源，向用户和应用软件提供各种服务功能，使得用户和应用软件能 够灵活、方便、有效地使用计算机，并使整个计算机系统能高效地运行。从操作系统在计算机系统中的实现层次上看，操作系统位于计算机硬件之上，应用软件之下。由于操作系统是一个复杂的软件系统，为了能够更好地设计和实现操作系统，我们可以从功能上对操作系统进行分解，可把操作系统分解为系统调用、进程调度、内存管理、中断处理、文件系统和设备管理等功能模块，在具体实现上可采用模块化、层次化和面向对象等设计方法来设计实现操作系统。一个OS组成结构图[need to update]。要了解xv6，首先我们需要了解操作系统的一些基本概念(请参考附录A)。 xv6（基于xv6-rev2版本）是一个支持对称多处理器(SMP)的类Unix系统。它包含操作系统一些最基本的要素，包括系统调用、进程调度、内存管理、中断处理和文件系统等。 xv6总体设计思路
xv6基于典型的UNIX操作系统设计思路。简单地说，xv6是一种能区分内核态和用户态，基于扁平内存管理的层次型单体内核，应用程序和操作系统是处于不同的特权状态和地址空间。代表应用程序的用户态进程运行在CPU的用户态（又称非特权模式，用户模式），无法直接访问系统硬件和操作系统中的系统数据，而操作系统运行在CPU的核心态（又称特权模式，内核模式），可以访问系统硬件和核心数据。下面分别从系统调用接口、进程/线程管理、内存管理、文件系统、I/O管理等几个方面进行总体分析。
系统调用是应用程序访问操作系统的接口。在系统调用接口上，通用操作系统与基于此操作系统的应用程序处于两个不同的CPU特权态，操作系统处于核心态，而应用程序处于用户态。在核心态可以执行CPU特权指令，而用户态无法执行特权指令，且只能通过特定的指令或中断来访问操作系统提供的各种功能。这在一定程度上保证了系统整体的安全，避免应用程序对操作系统可能的破坏。
在内存管理方面，通用操作系统采用了虚拟内存管理方式，这样可以让内存需求超过实际物理内存的进程/线程能够执行，其主要思想是把重要和常用的数据和执行代码放在物理内存中，把不常用的数据和执行代码放到二级存储（这里主要指的是硬盘等可在掉电后保存数据的存储介质），随时根据系统执行情况替换放在内存中的数据和代码。而且通过虚存管理可以实现对不同内存区域的保护，不同进程之间，或者应用程序和操作系统之间的地址空间相对隔离。这样一般情况下不同进程的地址空间不能直接访问，且应用程序不能直接访问内核地址空间。所以一个与错误的应用程序不会导致系统的崩溃，从而增加了系统的可靠性。xv6操作系统没有采用虚拟内存管理，而是采用了简单的基于X86段模式的单一地址空间管理方式。在内存分配和释放的管理上，xv6相对实现得比较简单，采用基于可变分区分配的首次适配算法，容易产生内存碎片。
在进程/线程管理方面，当前通用操作系统结合虚存管理，采用进程和线程结合的管理方式。进程代表了一个程序执行的过程以及其所占用的计算机资源（包括CPU、内存、文件等），进程的执行流可用线程来表示。操作系统的调度单位可以是进程或线程。一个进程可以包含多个线程，属于同一进程的多个线程共享进程管理的资源，比如属于同一进程的多个线程共享进程所管理的内存，这样这些线程可以直接访问属于进程的全局地址空间。 xv6操作系统实现了一个基于进程（没有实现线程）的简单进程管理机制。
在文件系统管理方面，当前通用操作系统结合虚存管理，实现了多种复杂、高效且可靠的文件系统，且建立了一个统一的虚拟文件系统层，屏蔽不同文件系统的差异，对上层提供统一的接口。且与用户管理和进程管理结合，可实现安全管理，保证对文件的安全访问。xv6操作系统实现了一个相对简单的基于inode索引方式的文件系统。
在I/O管理方面，xv6操作系统与通用操作系统（特别是类UNIX操作系统）差别不是特别大，都把设备“看成”是一种特殊的设备文件，有设备号，用文件的访问接口来进行打开、关闭、读、写和控制等操作。在灵活性方面，xv6驱动程序不能象通用操作系统那样根据硬件情况动态加载，而是在编译时候就静态确定的。
xv6总体架构
从操作系统模型上来看，xv6是一个单地址空间的层次式单体内核，不是微内核（microkernel）模型的操作系统（如Mach，QNX），与通用操作系统（如Linux）的架构在地址空间和特权模式上也有一定的差别。下面主要分进程调度、内存管理、同步互斥、文件系统几方面对xv6进行介绍。
? 同步互斥
由于在SMP架构中，内存磁盘等硬件资源在所有CPU中都是共享的，所以在需要某种机制对资源进行互斥访问控制。在xv6中，通 过实现了spinlock，从而可以对共享资源加锁来限制同时访问此资源的CPU数量。 ? 内存管理
在内存管理方面, xv6采用了段式虚拟内存的管理方式。每个用户进程所占用的内存都是在一个连续的段中。用户进程内存的分布为： 代码段、静态变量段、固定大小的栈和可变大小的堆空间。由于进程内存是按照段管理的，因此在每次分配进程内存时，xv6将找一片 正好能放下整段的连续内存块进行放置。 ? 进程管理
因为是基于SMP架构，操作系统中的多个进程会占用计算机系统中的多个CPU执行其具体功能，由于进程数量大于CPU数量，这就涉及到进程如何分时共享CPU的操作系统管理问题，具体包括如果创建进程、如何删除进程、选 择哪个进程占用哪个CPU，何时进行进程切换，进程能够持续占用CPU的时间片段的大小设定等。在xv6中，首先其进程是基于时间片来调度的。每次进程的 调度是由时钟中断产生的，或者是因当前进程主动放弃。 其次，每个CPU之间都共享一个进程池（具体实现为一个全局数组），其中有所有待运行的进程。在每个时间片中，CPU将当前运行的进程放回进程池，然后从 进程池中选取另一个待运行的进程进行执行。 ? 文件系统
? ?
xv6中提供了一个简单的文件系统，这个文件系统提供了大多数POSIX标准的接口。由于这个文件系统比较简单，其中一个文件最多由(12+128)个组成， 所以文件的大小也被限制在(12+128)*512Bytes。在这个文件系统中提供了一个Buf层，用来缓存磁盘上的数据。但是此文件系统是写直达的，因此每次更新都会直接写到磁盘上。 中断管理和系统调用管理[NTU] 外设管理[NTU]
第二章 启动流程(boot)
1.概述
本章将给出xv6启动实现的概貌。读者将学习以下一些内容:
? bootloader是什么？
? bootloader做了哪些事情？ ? xv6是如何被加载并启动的？
? xv6的初始内存管理是如何实现的？ ? xv6的初始中断管理是如何实现的？ ? xv6如何实现内核态到用户态的转变的？ ? xv6启动用户态进程前需要完成哪些事情？ ? xv6如何创建并启动第一个用户态进程？
当计算机加电后，一般不直接执行操作系统，而是执行引导加载程序。简单地说，引导加载程序就是在操作系统内核运行之前运行的一段小程序。通过这段小程序，我们可以初始化硬件设备、建立系统的内存空间映射图，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用操作系统内核准备好正确的环境。最终引导加载程序把操作系统内核映像加载到RAM中，并将系统控制权传递给它。
对于绝大多数计算机系统而言，操作系统和应用软件是存放在磁盘（硬盘/软盘）、光盘、EPROM、ROM、Flash等可在掉电后继续保存数据的存储介质上。计算机启动后，CPU一开始会到一个特定的地址开始执行指令，这个特定的地址存放了系统软件（不仅是操作系统，还可能是引导加载程序等）。 引导加载程序(bootloader)是系统加电后运行的第一段软件代码。对于PC386的体系结构而言，PC机中的引导加载程序由BIOS (Basic Input Output System，即基本输入/输出系统，其本质是一个固化在主板Flash/CMOS上的软件)和位于软盘/硬盘引导扇区中的OS Boot Loader一起组成。BIOS实际上是被固化在计算机ROM（只读存储器）芯片上的一个特殊的软件，为上层软件提供最底层的、最直接的硬件控制与支持。更形象地说，BIOS就是PC计算机硬件与上层软件程序之间的一个\桥梁\，负责访问和控制硬件。
以PC386为例，计算机加电后，CPU从物理地址0xFFFFFFF0（由初始化的CS：EIP确定，此时CS和IP的值分别是0xF000和0xFFF0)）开始执行。在0xFFFFFFF0这里只是存放了一条跳转指令，通过跳转指令跳到BIOS例行程序起始点。BIOS做完计算机硬件自检和初始化后，会选择一个启动设备（例如软盘、硬盘、光盘等），并且读取该设备的第一扇区(即启动扇区)到内存一个特定的地址0x7c00处，然后CPU控制权会转移到那个地址继续执行。至此BIOS的初始化工作做完了，进一步的工作交给了xv6。
整个xv6系统的启动流程大致是这样的：做为多处理系统，启动是首先从一个CPU的启动进行的。第一个CPU的启动过程与其他在单核上启动操作系统的过程是十分类似的。 首先BIOS将把OS的Boot Loader从磁盘上（一般是位于第一个扇区）拷贝到内存当中。当BIOS将基本的初始化程序完成后，将跳转到Boot Loader所在内存的位置继续执行。 Boot Loader将把OS的内核从磁盘上拷贝到然后运行。这样第一个CPU就完成了启动。那么第一个CPU将把启动代码拷贝到内存中，然后唤起其他CPU执行这一段代码， 完成它们的初始化过程。 在xv6的源码中，整个启动过程主要牵涉到如下几个文件：
? bootloader
o bootasm.S
o bootmain.c
? xv6初始化模块
o main.c
o bootother.S
下面将针对这些文件进行分析，对启动过程分成两部分进行介绍。
2.代码分析
bootloader代码分析
bootloader的组成
在makefile中50行~56行有如下语句
50： bootblock: bootasm.S bootmain.c
51： $(CC) $(CFLAGS) -O -nostdinc -I. -c bootmain.c 52： $(CC) $(CFLAGS) -nostdinc -I. -c bootasm.S
53: $(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 -o bootblock.o bootasm.o bootmain.o 54: $(OBJDUMP) -S bootblock.o > bootblock.asm 55: $(OBJCOPY) -S -O binary bootblock.o bootblock 56: ./sign.pl bootblock
从中可以看出bootloader包含两个文件，bootasm.S和bootmain.c。生成的bootloader会写到一个主引导扇区上面。作为主引导扇区，其位置在软盘或硬盘的第一个扇区，其大小为512个字节，在此扇区的最后两个字节是一个主引导扇区特征码为”55AA”。Makefile的51行和52行是通过gcc把 bootmain.c和bootasm.S编译成目标文件bootmain.o和bootasm.o。Makefile的53行是通过ld程序把目标文件bootmain.o和bootasm.o链接成目标文件
bootblock.o，且定义了起始执行的点（也称入口点）为start函数，具体的代码段起始地址为0x7C00。［Q］大家还记得0x7C00这个特殊的地址的含义吗？Makefile的54行是通过
objdump程序把bootblock.o反汇编成bootlock.asm。Makefile的55行是通过objcopy程序把bootblock.o变成二进制码bootlock。[Q]bootlock的大小可以大于512字节吗？Makefile的56行是通过sign.pl程序把bootlock扩展到512个字节，并把最后两个字节写成”55AA”。
［小实验］把最后的xv6.img的前512个字节取出来，反汇编它的内容，并与 bootasm.S和bootmain.c的内容（可以用bootblock.asm）进行比较,观察前512个字节的最后两个字节的内容是否是“55AA”
代码分析
bootloader的启动主要涉及到bootasm.S、bootmain.c。其中bootasm.S的主要作用是从实模式转化到保护模式。 bootmain的作用是把内核从磁盘拷贝到内存中。
bootasm.S
在进入实模式向保护模式切换之前，首先需要把中断关闭(\，保证转换过程不被硬件中断打断。
在19～22行中，将DS, ES, SS进行清零。
在20~42行 (打开A20地址线)
[历史]
在8086年代，8086提供了20跟地址线,那么提供的可寻址空间范围即0~2^20(00000H~FFFFFH)的 1M空间，而由于8086的数据处理位宽位16位,所以8086提供了段地址加偏移地址的地址转换机制，就是我们常见的”段地址:偏移地址(或有效地址)”,实际的计算方法为:”段地址*10H+偏移地址”，作为段地址的数据是放在段寄存器中的(16位)，而座位偏移地址的数据则是通过8086提供的寻址方式来计算而来的(16位)。而“段值：偏移”这种表示法能够表示的最大内存为
10FFEEh(FFFF0 + FFFF)，所以当寻址到超过1MB的内存时，会发生“回卷”（不会发生异常）。但是到了80286 提供了24根地址线,cpu的寻址范围变为 2^24=16M,同时也提供了保护模式，真的可以访问到1MB以上的内存了，此时如果遇到“寻址超过1MB”的情况，系统不会再