xv6操作系统整体报告41页

1、前言 操作系统是一种复杂的系统软件。本书通过介绍操作系统的基本概念和原理.并结合操作系统原理来分析一个小型但全面的操作系统xv6.并进一步进行各种基于xv6操作系统的实验.来让读者了解和掌握操作系统的设计与实现。xv6是一个运行在基于x86架构的计算机系统上的类似UNIX的教学用操作系统。xv6起源于MIT。在2002年秋季.Frans Kaashoek, Josh Cates, and Emil Sit在MIT开设了一门新的实验型课程“操作系统工程”.英文名称是“Operating Systems Engineering”.课程代号是“6.097”.后改为“6.828”.在此课程上.一开始采

2、用了“莱昂氏UNIX源代码分析”（英文书名是“LionCornmentary 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主要用于讲课.而另一个基于exokern

3、el架构的JOS主要用于做试验。 目前xv6在MIT的网址在 /6.828/xv6/第零章 安装使用如果是Linux初学者.请看附录F.了解如何安装、使用Ubuntu Linux.如何在Ubuntu Linux下编程。编译need update安装UbuntuLinux 8.10.具体安装方法可以参考附录C。并通过apt工具进一步安装相关软件包$ sudo apt-get install gcc binutils libc 6-devgdb然后解压xv6软件包.到某一目录.然后到此目录下执行$make就可以生成相关执行文件和镜像.包括xv6.im

4、g(包含bootloader和xv6 kernel)和fs.img(包含应用程序)运行need update安装UbuntuLinux 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.imgqemu和kvm的相关运

5、行参数的含义可参考附录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.imgb gdb启动并调试gdb kernel(gdb) target remote :1234(gdb) br

6、eak FUNCTION-NAME(gdb) continue.(gdb) quit2 用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 addrinfo cpus - show infos for each CPUinfo registers - show the cpu registerssinglestep single

7、stap_enabled - toggle singlestep modebreakpoint_insert addr - insert breakpointbreakpoint_remove addr - remove breakpointbreakpoint_show - show breakpointwatchpoint_insert addr type - insert watchpoint type 0=read 1=writewatchpoint_remove addr - remove watchpointwatchpoint_show - show watchpointwher

8、e - show calls stack第一章总体结构和系统组成本章将给出xv6启动实现的概貌。读者将学习以下一些内容: 操作系统是什么？ xv6是如何产生的？ xv6的总体结构是什么？ xv6包含哪些重要的组成部分？ 操作系统是一种软件.操作系统没有一个精确和统一的定义。操作系统是一种比较复杂的软件.我们可以从多种角度来了解操作系统。从操作系统的任务来看.操作系统的任务主要是控制和管理计算机系统中的硬件资源并对应用软件和用户提供各种方便使用计算机的功能。通过操作系统.能有效地组织和管理计算机系统中的硬件资源和其他软件资源.向用户和应用软件提供各种服务功能.使得用户和应用软件能 够灵活、方便、

9、有效地使用计算机.并使整个计算机系统能高效地运行。从操作系统在计算机系统中的实现层次上看.操作系统位于计算机硬件之上.应用软件之下。由于操作系统是一个复杂的软件系统.为了能够更好地设计和实现操作系统.我们可以从功能上对操作系统进行分解.可把操作系统分解为系统调用、进程调度、内存管理、中断处理、文件系统和设备管理等功能模块.在具体实现上可采用模块化、层次化和面向对象等设计方法来设计实现操作系统。一个OS组成结构图need to update。要了解xv6.首先我们需要了解操作系统的一些基本概念(请参考附录A)。 xv6（基于xv6-rev2版本）是一个支持对称多处理器(SMP)的类Unix系统。

10、它包含操作系统一些最基本的要素.包括系统调用、进程调度、内存管理、中断处理和文件系统等。xv6总体设计思路 xv6基于典型的UNIX操作系统设计思路。简单地说.xv6是一种能区分内核态和用户态.基于扁平内存管理的层次型单体内核.应用程序和操作系统是处于不同的特权状态和地址空间。代表应用程序的用户态进程运行在CPU的用户态（又称非特权模式.用户模式）.无法直接访问系统硬件和操作系统中的系统数据.而操作系统运行在CPU的核心态（又称特权模式.内核模式）.可以访问系统硬件和核心数据。下面分别从系统调用接口、进程/线程管理、内存管理、文件系统、I/O管理等几个方面进行总体分析。 系统调用是应用程序访问

11、操作系统的接口。在系统调用接口上.通用操作系统与基于此操作系统的应用程序处于两个不同的CPU特权态.操作系统处于核心态.而应用程序处于用户态。在核心态可以执行CPU特权指令.而用户态无法执行特权指令.且只能通过特定的指令或中断来访问操作系统提供的各种功能。这在一定程度上保证了系统整体的安全.避免应用程序对操作系统可能的破坏。 在内存管理方面.通用操作系统采用了虚拟内存管理方式.这样可以让内存需求超过实际物理内存的进程/线程能够执行.其主要思想是把重要和常用的数据和执行代码放在物理内存中.把不常用的数据和执行代码放到二级存储（这里主要指的是硬盘等可在掉电后保存数据的存储介质）.随时根据系统执行情

12、况替换放在内存中的数据和代码。而且通过虚存管理可以实现对不同内存区域的保护.不同进程之间.或者应用程序和操作系统之间的地址空间相对隔离。这样一般情况下不同进程的地址空间不能直接访问.且应用程序不能直接访问内核地址空间。所以一个与错误的应用程序不会导致系统的崩溃.从而增加了系统的可靠性。xv6操作系统没有采用虚拟内存管理.而是采用了简单的基于X86段模式的单一地址空间管理方式。在内存分配和释放的管理上.xv6相对实现得比较简单.采用基于可变分区分配的首次适配算法.容易产生内存碎片。 在进程/线程管理方面.当前通用操作系统结合虚存管理.采用进程和线程结合的管理方式。进程代表了一个程序执行的过程以及

13、其所占用的计算机资源（包括CPU、内存、文件等）.进程的执行流可用线程来表示。操作系统的调度单位可以是进程或线程。一个进程可以包含多个线程.属于同一进程的多个线程共享进程管理的资源.比如属于同一进程的多个线程共享进程所管理的内存.这样这些线程可以直接访问属于进程的全局地址空间。xv6操作系统实现了一个基于进程（没有实现线程）的简单进程管理机制。 在文件系统管理方面.当前通用操作系统结合虚存管理.实现了多种复杂、高效且可靠的文件系统.且建立了一个统一的虚拟文件系统层.屏蔽不同文件系统的差异.对上层提供统一的接口。且与用户管理和进程管理结合.可实现安全管理.保证对文件的安全访问。xv6操作系统实现

14、了一个相对简单的基于inode索引方式的文件系统。 在I/O管理方面.xv6操作系统与通用操作系统（特别是类UNIX操作系统）差别不是特别大.都把设备“看成”是一种特殊的设备文件.有设备号.用文件的访问接口来进行打开、关闭、读、写和控制等操作。在灵活性方面.xv6驱动程序不能象通用操作系统那样根据硬件情况动态加载.而是在编译时候就静态确定的。xv6总体架构 从操作系统模型上来看.xv6是一个单地址空间的层次式单体内核.不是微内核（microkernel）模型的操作系统（如Mach.QNX）.与通用操作系统（如Linux）的架构在地址空间和特权模式上也有一定的差别。下面主要分进程调度、内存管理、

15、同步互斥、文件系统几方面对xv6进行介绍。 同步互斥由于在SMP架构中.内存磁盘等硬件资源在所有CPU中都是共享的.所以在需要某种机制对资源进行互斥访问控制。在xv6中.通 过实现了spinlock.从而可以对共享资源加锁来限制同时访问此资源的CPU数量。 内存管理在内存管理方面, xv6采用了段式虚拟内存的管理方式。每个用户进程所占用的内存都是在一个连续的段中。用户进程内存的分布为： 代码段、静态变量段、固定大小的栈和可变大小的堆空间。由于进程内存是按照段管理的.因此在每次分配进程内存时.xv6将找一片 正好能放下整段的连续内存块进行放置。 进程管理因为是基于SMP架构.操作系统中的多个进程

16、会占用计算机系统中的多个CPU执行其具体功能.由于进程数量大于CPU数量.这就涉及到进程如何分时共享CPU的操作系统管理问题.具体包括如果创建进程、如何删除进程、选 择哪个进程占用哪个CPU.何时进行进程切换.进程能够持续占用CPU的时间片段的大小设定等。在xv6中.首先其进程是基于时间片来调度的。每次进程的 调度是由时钟中断产生的.或者是因当前进程主动放弃。 其次.每个CPU之间都共享一个进程池（具体实现为一个全局数组）.其中有所有待运行的进程。在每个时间片中.CPU将当前运行的进程放回进程池.然后从 进程池中选取另一个待运行的进程进行执行。 文件系统xv6中提供了一个简单的文件系统.这个文

17、件系统提供了大多数POSIX标准的接口。由于这个文件系统比较简单.其中一个文件最多由(12+128)个组成. 所以文件的大小也被限制在(12+128)*512Bytes。在这个文件系统中提供了一个Buf层.用来缓存磁盘上的数据。但是此文件系统是写直达的.因此每次更新都会直接写到磁盘上。 中断管理和系统调用管理NTU 外设管理NTU第二章启动流程(boot)1.概述本章将给出xv6启动实现的概貌。读者将学习以下一些内容: bootloader是什么？ bootloader做了哪些事情？ xv6是如何被加载并启动的？ xv6的初始内存管理是如何实现的？ xv6的初始中断管理是如何实现的？ xv6如

18、何实现内核态到用户态的转变的？ xv6启动用户态进程前需要完成哪些事情？ xv6如何创建并启动第一个用户态进程？ 当计算机加电后.一般不直接执行操作系统.而是执行引导加载程序。简单地说.引导加载程序就是在操作系统内核运行之前运行的一段小程序。通过这段小程序.我们可以初始化硬件设备、建立系统的内存空间映射图.从而将系统的软硬件环境带到一个合适的状态.以便为最终调用操作系统内核准备好正确的环境。最终引导加载程序把操作系统内核映像加载到RAM中.并将系统控制权传递给它。对于绝大多数计算机系统而言.操作系统和应用软件是存放在磁盘（硬盘/软盘）、光盘、EPROM、ROM、Flash等可在掉电后继续保存数

19、据的存储介质上。计算机启动后.CPU一开始会到一个特定的地址开始执行指令.这个特定的地址存放了系统软件（不仅是操作系统.还可能是引导加载程序等）。引导加载程序(bootloader)是系统加电后运行的第一段软件代码。对于PC386的体系结构而言.PC机中的引导加载程序由BIOS (Basic Input Output System.即基本输入/输出系统.其本质是一个固化在主板Flash/CMOS上的软件)和位于软盘/硬盘引导扇区中的OS Boot Loader一起组成。BIOS实际上是被固化在计算机ROM（只读存储器）芯片上的一个特殊的软件.为上层软件提供最底层的、最直接的硬件控制与支持。更形

20、象地说.BIOS就是PC计算机硬件与上层软件程序之间的一个桥梁.负责访问和控制硬件。以PC386为例.计算机加电后.CPU从物理地址0xFFFFFFF0（由初始化的CS：EIP确定.此时CS和IP的值分别是0xF000和0xFFF0)）开始执行。在0xFFFFFFF0这里只是存放了一条跳转指令.通过跳转指令跳到BIOS例行程序起始点。BIOS做完计算机硬件自检和初始化后.会选择一个启动设备（例如软盘、硬盘、光盘等）.并且读取该设备的第一扇区(即启动扇区)到内存一个特定的地址0x7c00处.然后CPU控制权会转移到那个地址继续执行。至此BIOS的初始化工作做完了.进一步的工作交给了xv6。 整个

21、xv6系统的启动流程大致是这样的：做为多处理系统.启动是首先从一个CPU的启动进行的。第一个CPU的启动过程与其他在单核上启动操作系统的过程是十分类似的。 首先BIOS将把OS的Boot Loader从磁盘上（一般是位于第一个扇区）拷贝到内存当中。当BIOS将基本的初始化程序完成后.将跳转到Boot Loader所在内存的位置继续执行。 Boot Loader将把OS的内核从磁盘上拷贝到然后运行。这样第一个CPU就完成了启动。那么第一个CPU将把启动代码拷贝到内存中.然后唤起其他CPU执行这一段代码. 完成它们的初始化过程。在xv6的源码中.整个启动过程主要牵涉到如下几个文件： bootloa

22、dero bootasm.So bootmain.c xv6初始化模块o main.co bootother.S下面将针对这些文件进行分析.对启动过程分成两部分进行介绍。2.代码分析bootloader代码分析bootloader的组成在makefile中50行56行有如下语句50： bootblock: bootasm.S bootmain.c51： $(CC) $(CFLAGS) -O -nostdinc -I. -c bootmain.c52： $(CC) $(CFLAGS) -nostdinc -I. -c bootasm.S53: $(LD) $(LDFLAGS) -N -e sta

23、rt -Ttext 0x7C00 -o bootblock.o bootasm.o bootmain.o54: $(OBJDUMP) -S bootblock.o bootblock.asm55: $(OBJCOPY) -S -O binary bootblock.o bootblock56: ./sign.pl bootblock从中可以看出bootloader包含两个文件.bootasm.S和bootmain.c。生成的bootloader会写到一个主引导扇区上面。作为主引导扇区.其位置在软盘或硬盘的第一个扇区.其大小为512个字节.在此扇区的最后两个字节是一个主引导扇区特征码为”55AA

24、”。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变成二进制码

25、bootlock。Qbootlock的大小可以大于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的作用是把内核从磁盘拷贝到内存中

26、。bootasm.S在进入实模式向保护模式切换之前.首先需要把中断关闭(cli at line 15).保证转换过程不被硬件中断打断。在1922行中.将DS, ES, SS进行清零。在2042行 (打开A20地址线)历史在8086年代.8086提供了20跟地址线,那么提供的可寻址空间范围即0220(00000HFFFFFH)的1M空间.而由于8086的数据处理位宽位16位,所以8086提供了段地址加偏移地址的地址转换机制.就是我们常见的”段地址:偏移地址(或有效地址)”,实际的计算方法为:”段地址*10H+偏移地址”.作为段地址的数据是放在段寄存器中的(16位).而座位偏移地址的数据则是通过8

27、086提供的寻址方式来计算而来的(16位)。而“段值：偏移”这种表示法能够表示的最大内存为10FFEEh(FFFF0 + FFFF).所以当寻址到超过1MB的内存时.会发生“回卷”（不会发生异常）。但是到了80286 提供了24根地址线,cpu的寻址范围变为224=16M,同时也提供了保护模式.真的可以访问到1MB以上的内存了.此时如果遇到“寻址超过1MB”的情况.系统不会再“回卷”了.这就造成了向上不兼容。为了保持完全的兼容性.IBM决定在PC AT系统上加个逻辑.来模仿以上的回绕特征。他们的方法就是把A20和键盘控制器的一个输出进行AND.这样来控制A20的打开和关闭。一开始时A20是被屏

28、蔽的（总为0）.直到系统软件去打开它。注意A20而非A20A31被控制.所以在A20关闭时会发生一些有趣的副作用。就是在访问奇数M地址空间的时候.实际的地址会减少1M。例如访问1M2M-d1时实际访问的是01M-1；访问3M4M-1时为2M3M-1.等等。当A20 Gate禁止时.则程序就像在8086中运行.100000h100FFEFh的地是不可访问的。在保护模式下A20 Gate是要打开的。为了使能所有地址位的寻址能力,必须向键盘控制器8042发送一个命令。键盘控制器8042将会将它的的某个输出引脚的输出置高电平,作为 A20 门的输入。一旦设置成功之后,内存将不会再被绕回(memory

29、wrapping),这样我们就可以寻址整个 286 的 16M 内存,或者是寻址 80386级别机器的所有 4G 内存了。8042键盘控制器的IO端口是0x600x6f.实际上IBM PC/AT使用的只有0x60和0x64两个端口（0x61、0x62和0x63用于与XT兼容目的）。8042通过这些端口给键盘控制器或键盘发送命令或读取状态。输出端口P2用于特定目的。位0（P20引脚）用于实现CPU复位操作.位1（P21引脚）用户控制A20信号线的开启与否。系统向输入缓冲（端口0x64）写入一个字节.即发送一个键盘控制器命令。可以带一个参数。参数是通过0x60端口发送的。命令的返回值也从端口 0x

30、60去读。图Intel8042芯片或其兼容芯片的逻辑示意图2831行.等待I/O端口 0x64空闲.读I/O端口 0x64. 如果返回值的第1位（最低位为第0位）的值不为0.表示端口0x64为busy.需要再次重复测试.直到第1位为0为止。3334行.把0xd1写入I/O端口 0x64；0xd1命令是写输出端口.bit 0 是复位,bit 1 是Gate A20.3639行.等待I/O端口 0x64空闲.即读I/O端口 0x64. 如果返回值的第1位（最低位为第0位）的值不为0.表示端口0x64为busy.需要再次重复测试.直到第1位为0为止。4142行.把0xdf写入I/O端口 0x60；0

31、xdf命令是使能 A20至此.A20地址线已经使能。在第48行.lgdt gdtdesc 将新的全局段描述符表进行加载。注意到gdtdesc中给出了新段表有效大小.和所在地址(gdt)。 在gdt中给出了三个段的描述. 第0段默认是空段. 第1段是代码段.第2段是数据段。由于现在只是做模式切换之用.因此第1、2段的范围都是0x00xffffffff。在第4951行中.通过将CR0的第0位置1.把保护模式设置为打开。但此时段模式并没有真正运行。只有当执行完55行的ljmp后.段模式才真正的启动。 此时cs变成$PROT_MODE_CSEG所指向的段（即83=1, 为gdt的第1段.即代码段）。在

32、完成ljmp后.机器进入32位模式。在5965行在将其他段寄存器置成数据段即gdt中的第2段.即数据段。在第68行.将栈顶指针指向$start坐在位置即(0x7c00)。然后在第69调用bootmain过程.进行内核的加载。bootmain.c在这个文件中主要有四个函数：bootmain、waitdisk、readsect和readseg。其中bootmain是加载内核.其余三个都是对磁盘进行访问的程序。首先来看一下waitdisk、readsect和readseg。 readseg函数的作用是从磁盘的offset处开始读取count个字符到va处。在读取数据时是通过调用readsect以扇区

33、为单位进行的。因此在88行保证va是从一个扇区起始位置开始.因此要对va进行对齐。readsect是对磁盘进行读取.在读取之前每次调用waitdisk等待磁盘的准备过程.一旦磁盘准备好后就可以进行读取了。然后看一下bootmain过程。bootmain的目的是从磁盘中加载内核到内存中.其中内核是以ELF执行文件格式存在磁盘上的。首先将从磁盘读取一页大小(8*512B=4KB)的信息.其中包含了ELF执行文件格式的头。从中可以知道读取镜像的大小以及存放的位置 (见3437行）。当完成拷贝后.bootmain获取内核入口程序的地址(见4041行）.然后进入该入口 (即main.c中的main函数)

34、。操作系统初始化模块代码分析操作系统的启动部分包含如下文件main.cbootother.Smain.cmain.c的作用是进行对系统各方面的初始化工作.然后唤起其他CPU的初始化。 首先我们看一下main过程。 在这个过程将进行一系列的初始化过程。第一步是对BSS段进行初始化 (18行）。在20行将调用函数mp_init将获取所有cpu的信息.其中bcpu将指定BOOTSTRAP CPU的编号（即第一个启动的CPU的编号）。接下2436行是一系列的初始化过程.涉及 process table buffer cache PIC interrupt controller IOAPIC inter

35、rupt controller physical memory allocator trap vectors file table inode cache console device & interrupt IDE device & interrupt timer （only for uniprocessor） first user process这些将在后面的文章具体介绍。在初始话内存、中断表、文件系统、I/O设备等之后.第一个CPU将启动调用 bootothers()去启动其他的CPU。 在调用函数bootothers()之前.第一个用户进程将通过userint()进行初始化。在初始化其

36、他AP后.将进入scheduler()过程。scheduler过程是对单个CPU的进行进程调度的.这将在以后进行讨论。然后.我们看一下bootothers()过程。 在这个过程中将对除bootstrap CPU之外每个CPU进行启动。 启动时这样进行的.首先把bootother.S的代码拷贝到0x7000起始的这块内存里。 然后在0x7000-4、0x7000-8两个内存单元记录下bootother.S中将要进行跳转的内核栈位置以及mpmain的入口地址。 这样当CPU运行完bootother.S中的代码之后将进入mpmain过程。在mpmain中.每个CPU将进行中断表和段表的初始化.然后打

37、开中断进入scheduler()过程。bootother.Sbootother.S完成启动其他CPU的启动工作.根据Makefile的5862行：58： bootother: bootother.S59： $(CC) $(CFLAGS) -nostdinc -I. -c bootother.S60： $(LD) $(LDFLAGS) -N -e start -Ttext 0x7000 -o bootother.out bootother.o61： $(OBJCOPY) -S -O binary bootother.out bootother62： $(OBJDUMP) -S bootother

38、.o bootother.asm可以了解到：Makefile的59行是通过gcc把bootother.S编译成目标文件bootother.o。Makefile的60行是通过ld把bootother.o进行地址重定位,设定其起始入口点为start.起始地址位0x7000.并生成执行文件bootother.out。Makefile的61行是通过objcopy把bootother.out转变成二进制代码bootother。Makefile的62行是通过objdump把bootother.o反汇编成bootother.asm。bootother.S的执行内容十分类似之前的bootasm.S。在这个文件

39、中晚启动的CPU将会进行从实模式到保护模式的转化（4249行）。然后重设段寄存器（5459行）。完成后.便设置kernel栈.跳转进入mpmain过程 （61-63行）。Q这个栈的内容是什么？第三章 同步互斥与锁机制 (spinlock)1.概述本章将给出xv6同步互斥实现的概貌。读者将学习以下一些内容: 什么是竞争状态？ 什么是互斥？ 什么是同步？NUD xv6中的临界区代码是什么？ xv6是怎样处理临界区代码的？ 当两个或多个线程在执行一些关键性的临界区代码时（如对共享资源的访问）.如何确保它们不会相互妨碍？当线程之间存在着某种依存关系时.如何来调整它们的运行次序？当线程经常需要与其它线程

40、进行通信.那么如何根据需要提供有效的通信手段？这实际上需要操作系统提供同步互斥与通信的手段才能解决上述问题。 任何为进程所占用的实体都可称为资源。资源可以是CPU、内存.也可以是I/O设备.还可以是一个变量.一个结构或一个数组等。可以被一个以上进程使用的资源叫做共享资源。为了防止数据被随意访问（特别是执行写操作）.每个进程在与共享资源打交道时.必须独占该资源。这叫做互斥（mutual exclusion）。需要互斥访问的共享资源称为临界资源。如果两个或多个进程对同一共享资源同时进行读写操作.而最后的结果是不可预测的.该结果取决于各个进程具体运行情况。则称此状态为竞争状态（race condit

41、ion）。对共享资源的访问.可能导致竞争状态的出现。我们把可能出现竞争态的程序片断称为程序临界区。程序临界区在处理时不可以被中断.要保证其操作的原子性。为确保临界区程序执行过程中不被中断.在进入临界区之前要屏蔽中断.而临界区代码执行完以后要立即使能中断.以减少对中断处理延迟的影响。 Spinlock的引入是为了进行资源的互斥访问。在SMP架构下.每个CPU的权限都是相同的.但是某些情况下.一个CPU需要对资源进行独占.此时就可以通过spinlock来进行。spinlock是通过一条CPU原子指令xchg完成的。具体的实现方法如下。2.代码分析spinlock.h文件中给出了spinlock结构

42、的定义如下：struct spinlock uint locked; / Is the lock held? / For debugging: char *name; / Name of lock. int cpu; / The number of the cpu holding the lock. uint pcs10; / The call stack (an array of program counters) / that locked the lock.;可以看到.起作用的主要是locked变量.这个用来表示当前锁是否被锁上。其他的变量name, cpu 和 pcs都是其调试作用的。

43、其中name记录锁的用途.cpu记录了那个cpu取得了这把锁.pcs记录了获得这把锁时的栈的内容。spinlock.cspinlock.c文件中包含了对spinlock的各种操作：初始化、获取锁.释放锁等。我们依次阅读文件中的每个过程。初始化锁initlock过程是对所进行初始化.即初始化name、locked和cpu三个域。cpu被置成0xffffffff.表示不被任何cpu所有。获取锁acquire过程是获取锁(变量lock)的过程。 在2829行.通过pushcli屏蔽中断.检查当前锁是否已经被当前CPU所占有。此时.用cli指令把当前CPU的中断关闭(注意其他CPU的中断并不受到影响.

44、而且其他软中断也并没有被关闭）。在程序35行的while将直到成功获取锁为止。在35行通过cmpxchg去获取锁。其指令格式为：xchg(va ,newvalue)。作用是交换内存地址va中的值和newvalue.返回值为内存地址va中运行xchg之前的值。因为locked=0表示这把锁没有人获取.此时xchg(va,1)便能返回0.跳出while循环.否则在while循环中打转。跳出while表示获得了锁.42行是记录获得锁的CPUID。43行是调用函数getcallerpcs记录获得锁时的函数调用栈。释放锁release过程十分简单.首先判断是否当前CPU拿到这把锁.如果不是.则报错；如果

45、是.那么就把锁进行释放.并清除获得锁的CPU记录和函数调用栈。同时如果当前CPU已经没有拿任何锁.那么通过popcli将中断打开。第四章 内存管理1.概述本章将给出xv6内存管理实现的概貌。读者将学习以下一些内容: xv6如何进行内存管理初始化的？ xv6的静态内存分配的空间包括什么？ xv6的动态内存分配的空间包括什么？ xv6的动态内存分配是如何实现的？ 如何使用xv6的动态内存分配的空间？ 内存管理机制是实时操作系统的重要组成部分。xv6不支持虚拟存储管理.不支持复杂的段页式的保护机制.而采用线性编址方式.即逻辑地址和物理地址一一对应的平面模式。这样没有虚拟存储管理提供的不受限于物理内存

46、大小的大地址空间、地址保护等功能。 xv6同时支持静态内存分配和动态内存分配两种管理方式。静态内存分配是指在编译或链接时将应用所需的内存空间分配好。采用这种分配方案的xv6内核映像所占内存空间（代码段和数据段等）的大小一般在编译时就能够确定.中断向量表等其它区域所占用的内存空间大小是个定值。这样采用静态的内存分配机制.在编译时就可以确定xv6所需内存的大小。而动态内存分配是指系统运行时根据应用需要动态地分配内存。动态内存分配的实现机制灵活.给程序实现带来极大的方便.有的应用环境中动态内存分配甚至是必不可少的。 xv6目前采用的是基于段模式的寻址方式。首先在xv6.img所在内存的末尾开始.增加

47、一块1MB的空闲动态内存空间。然后通过一种链表的方式来管理这1MB内存空间的在xv6中动态分配和释放。在初始化完动态内存空间后的内存布局如下：2.代码分析kalloc.c动态内存管理初始化内存空间初始化工作由函数kinit完成.执行完kinit后.内存布局如下所示：内核首先会被bootloader加载到x0x10000.然后main初始化总控函数通过kalloc.c文件中的kinit函数对内存进行初始化。其执行流程如下：1.调用initlock函数初始化用于内存管理互斥的kalloc_lock（32行）2.得到代码段数据段之后的最后地址指针end.并把它赋值给start指针变量.并把start

48、指针页对齐.把start指针指向的地址作为xv6所管理的空闲区域的起始地址（3334行）3.设置可使用的内存空间为256个4K大小的页.并调用kfree函数对start指针指向的地址为首地址.大小为256*41024个字节的空间进行空闲设置处理。（3537行）动态内存分配与释放kalloc.c中是对内存空间进行管理.kfree是回收一段内存.而kalloc是分配一段内存。xv6的内存管理是十分简单的。由于内存分配是以连续的段的方式进行的.通过单链表方式链接空闲的段。因此经过一定时间的分配.空闲空间将由一个个地址不连续的段组成。xv6用freelist将其按起始地址从左至右排列串起来。每次回收时

49、.将回收的段加入段序列 中。如果发现新加入段之后能够合并.则将其合并成一个段。当进行分配时.则遍历整个链表.直到找到一个比需求大的段.则将相应的段分配出去。初始化后第一次分配第N次分配和释放后第五章 进程管理与调度1.概述本章将给出xv6进程管理实现的概貌。读者将学习以下一些内容: 什么是进程？ xv6的进程管理数据结构（进程控制块.PCB）包含哪些内容？ xv6是如何组织进程管理数据结构？ xv6如何进行进程管理初始化的？ xv6怎样启动多进程的(即需要做哪些初始化工作)？ xv6何时进行进程调度？ xv6是如何调度进程的（如何选择进程占用CPU运行）？ xv6是如何完成进程切换的？ xv6

50、如何启动并执行用户态的进程的？进程的概念程序与进程的概念是不可分的。当用户在计算机上运行一个程序时.此程序对应的进程就诞生了.并实际完成各种程序提供的功能.而用户关闭一个程序时.进程也随之终止。程序是为了完成某项任务编排的语句序列.它要告诉计算机如何执行.因此程序是需要通过CPU来运行的.且在程序的运行过程中需要占有计算机的各种资源（比如内存等）才能运行下去。如果计算机系统在任一时刻限制只有一个程序在运行.则程序在整个运行过程中独占计算机中的全部资源.这样整个程序运行和管理就简单了。就象在一个家中只住了一个人A.他想看书就到书房去看书.想睡觉就到睡房的床上去睡觉.想看电视就到电视厅看电视.想吃

51、饭就去餐厅吃饭.没人和他抢占资源。但为了提高计算机系统的资源利用率.需要支持多个程序并发执行。这就会带来许多新的问题.如资源的共享与竞争.同步与互斥等。比如此人与B成家并有了小孩C.那就是三口之家同时住一套房.当A想去看足球比赛直播电视节目的时候.如果发现电视厅已经有B在坐着看连续剧电视节目了.A就得等待或干别的事情。除非A在买一个电视.并在另外一个房间看他的球比赛直播。由于程序是静态的.我们看到的程序是存储在存储介质（如硬盘、光盘等）上的.它无法反映出程序执行过程中的动态特性.而且程序在执行过程中会不断申请资源或释放资源.这样让程序作为共享资源的基本单位是不合适的.所以需要引入一个概念.它能

52、描述程序的执行过程而且可以作为共享资源的基本单位.这个概念就是进程。简单地说.一个进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。每个进程都是整个应用的某一部分。操作系统在逻辑上维护了进程的运行状态信息.即与进程运行直接相关的CPU寄存器和栈空间（只有这样才能实现进程切换）。操作系统根据当前进程的情况设置进程的状态.并根据进程的状态（比如优先级）进行选择一个进程占用CPU并运行.这个过程成为调度。进程的状态进程从诞生到死亡要经历若干个阶段.也会有生老病死。简单地说.进程有三种状态：就绪、执行、等待。多种原因可以导致创建一个进程.比如.当操作系统把一个程序从硬盘调入内存后.在

53、开始执行前.操作系统就要为此程序创建一个对应的进程。又比如.一个进程可以自己创建一个子进程.子进程被创建后就是在内存中.处于就绪态.所谓就绪态就是万事具备.只欠CPU这个东风了；一旦进程占有了CPU.就可以执行实际的工作了.其状态就变成了执行态；进程在执行中如果需要等待某个资源（如等硬盘输入数据）.则进程会放弃CPU.且其状态就变为等待态.这时操作系统又会从处于就绪态的另一个进程中挑选一个进程占有CPU.则这另一个进程的状态就变成了执行态。当前一个进程所等到数据到来后.处于等待态的前一个进程又被唤醒.并把状态变成为就绪态。在实际的操作系统中.进程的状态往往多于三种.比如找xv6中.进程具有多种

54、状态.包括：EMBRO, SLEEPING, RUNNABLE, RUNNING和ZOMBIE。定义在proc.h文件中：enum proc_state UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE ;状态的含义如下： UNUSED：进程未被创建（即进程控制块空闲）时的状态； EMBRYO：需要分配一个进程控制块且找到一个处于UNUSED状态的进程控制块时.把此进程控制块状态设置为要使用的状态； SLEEPING：进程由于等待某资源等原因无法执行.进入睡眠状态.即等待态； RUNNABLE：进程获得了除CPU之外的所有资源.处于可运行状

55、态.即就绪态； RUNNING：进程获得CPU.正在运行的状态.即执行态； ZOMBIE：进程结束的状态 这几个状态之间的转化如图5.1（左）所示。 由于是SMP架构.因此每个CPU获取进程调度的权利是相同的。CPU在scheduler里面进行轮询操作.每次从线程池中选择一个RUNNABLE的进程进行运行。直到运行完毕.或一单位时间片结束.或者进程主动yield或sleep。CPU与进程池的关系如图5.1（右）所示。图5.1 状态转换的过程即哪些事件促使了状态的转换 TODO进程控制块 程序的运行是通过进程体现的.操作系统对进程进行管理和控制.那么操作系统怎么了解到进程的状态并掌握进程占有的资源分配呢.而且进程做状态转换时CPU的现场保存在那呢？这实际是通过进程控制快（Process Control Block, 简称PCB）。PCB是进程 的唯一标志.在其中记录了进程的全部信息.相当于进程的档案。操作系统通过PCB感知进程的存在.通过PCB了解进程和控制 进程的运行。在xv6中.所有的CPU共享一个进程控制块池.即