nachos源码分析

计算机科学与技术学院

2009－2010 学年第一学期

《 操作系统》课程设计

题目： Nachos线程模块分析 班级： 070341 B 学号： 070341221 姓名： 阮 琳 琳 教师： 杨 志 娴 成绩：

1. 题目分析

本次课程设计中，我将遵循课本上进程部分的章节组织来分析Nachos中线程模块。我想这样会使分析的思路更加清晰，系统性和理论性更强。 分析目的：

通过阅读nachos代码，了解一个最基本的操作系统是如何工作运转起来的。结合书本上的知识，理解nachos中的源码，并使在书本上学到的知识得到巩固。以使我对操作一同这门课有更深入的理解。 Nachos相关知识概述 一、Nachos的线程管理

Nachos广泛采用线程的概念，是多线程操作系统。线程是Nachos处理机调度的单位，在Nachos中线程分成两类，一类是系统线程。所谓系统线程是只运行核心代码的线程，它运行在核心态下，并且占用宿主机的资源，系统线程共享Nachos操作系统本身的正文段和数据段；一个系统线程完成一件独立的任务。Nachos的设计者认为，教授并发性的最好方法是让读者能够直观地看到程序的并发行为。

Nachos的另一类线程同Nachos中的用户进程有关。Nachos中用户进程由两部分组成，核心代码部分和用户程序部分。用户进程的进程控制块是线程控制块基础上的扩充。每当系统接收到生成用户进程的请求时，首先生成一个系统线程，进程控制块中有保存线程运行现场的空间，保证线程切换时现场不会丢失。该线程的作用是给用户程序分配虚拟机内存空间，并把用户程序的代码段和数据段装入用户地址空间，然后调用解释器解释执行用户程序；由于Nachos模拟的是一个单机环境，多个用户进程会竞争使用Nachos唯一的处理机资源，所以在Nachos用户进程的进程控制块中增加有虚拟机运行现场空间以及进程的地址空间指针等内容，保证用户进程在虚拟机上的正常运行。

系统线程竞争使用宿主机的CPU资源，而用户进程的用户程序部分竞争使用的是虚拟机的CPU和寄存器。所以用户进程在被切换下处理机时，需要保存其系统线程部分的现场，同时还需要保存虚拟机部分的现场。当线程运行终止时，由于当前线程仍然运行在自己的栈空间上，所以不能直接释放空间，只有借助其他的线程释放自己。

Nachos和实际的进程管理有以下的不同： ? 不存在系统中所有线程的列表

在一般的操作系统中，进程的数目总是有限的，但是Nachos中的线程数目可以是无限的（当然，用户进程的数目应该也是有限的。当虚拟机内存以及虚拟内存都耗尽时，就不能产生新的用户线程）。这是因为，线程的控制结构和系统线程的运行是占用宿主机的。能够开多少线程完全由宿主机条件限制，理论上是无限的。 ? 线程的调度比较简单

在启动了时钟中断的情况下，当时钟中断到来时，如果就绪线程队列中有就绪线程，就必须进行线程切换；当没有启动时钟中断的情况下，Nachos使用非抢占式调度。

? 没有实现父子线程的关系

可以说，所有的Nachos线程都是Nachos的一个子线程。但是Nachos线程之间的父子关系没有实现。这样产生的混乱体现在线程的空间释放上，一个线程空间的释放是由下一个被切换的线程也即兄弟线程进行的，而这两个线程可以是没有任何关系的。这样的情况对以后进一步进行系统扩充是不利的。

2. 源码分析

Thread类的对象既用作线程的控制块，相当于进程管理中的PCB，作用是保存线程状态、进行一些统计，又是用户调用线程系统的界面。 线程的产生

用户生成一个新线程的方法是: Thread* newThread = new Thread(\// 生成一个线程类 newThread->Fork(ThreadFunc，ThreadFuncArg); // 定义新线程的执行函数及其参数

Fork方法分配一块固定大小的内存作为线程的堆栈，在栈顶放入ThreadRoot的地址。当新线程被调上CPU时，要用SWITCH函数切换线程图像，SWITCH函数返回时，会从栈顶取出返回地址，于是将ThreadRoot放在栈顶，在SWITCH结束后就会立即执行ThreadRoot函数。ThreadRoot是所有线程的入口，它会调用Fork的两个参数，运行用户指定的函数；Yield方法用于本线程放弃处理机。Sleep方法可以使当前线程转入阻塞态，并放弃CPU，直到被另一个线程唤醒，把它放回就绪线程队列。在没有就绪线程时，就把时钟前进到一个中断发生的时刻，让中断发生并处理此中断，这是因为在没有线程占用CPU时，只有中断处理程序可能唤醒一个线程，并把它放入就绪线程队列。

线程要等到本线程被唤醒后，并且又被线程调度模块调上CPU时，才会从Sleep函数返回。有趣的是，新取出的就绪线程有可能就是这个要睡眠的线程。例如，如果系统中只有一个A线程，A线程在读磁盘的时候会进入睡眠，等待磁盘操作完成。因为这时只有一个线程，所以A线程不会被调下CPU，只是在循环语句中等待中断。当磁盘操作完成时，磁盘会发出一个磁盘读操作中断，此中断将唤醒A线程，把它放入就绪队列。这样，当A线程跳出循环时，取出的就绪线程就是自己。这就要求线程的正文切换程序可以将一个线程切换到自己， Nachos的线程正文切换程序SWITCH可以做到这一点，于是A线程实际上并没有被调下CPU，而是继续运行下去了。

Nachos为线程提供的功能函数有:

1. 生成一个线程(Fork) 2. 使线程睡眠等待(Sleep) 3. 结束线程(Finish)

4. 设置线程状态(setStatus) 5. 放弃处理机(Yield)

线程系统的结构如所示:

用户进程 信号量 模拟中断 条件变量 Thread类 正文切换 线程调度 锁 一、 工具模块分析（文件list.cc list.h utility.cc utility.h）

工具模块定义了一些在Nachos设计中有关的工具函数，和整个系统的设计没有直接的联系，所以这里仅作一个简单的介绍。

List类在Nachos中广泛使用，它定义了一个链表结构，有关List的数据结构和实现如下所示：

class ListElement { // 定义了List中的元素类型 public:

ListElement(void *itemPtr, int sortKey); // 初始化方法 ListElement *next; // 指向下一个元素的指针 int key; // 对应于优先队列的键值 void *item; // 实际有效的元素指针 };

其中，实际有效元素指针是(void *)类型的，说明元素可以是任何类型。

class List { public: List(); // 初始化方法 ~List(); // 析构方法 void Prepend(void *item); // 将新元素增加在链首 void Append(void *item); // 将新元素增加在链尾 void *Remove(); // 删除链首元素并返回该元素 void Mapcar(VoidFunctionPtr func); // 将函数func作用在链中每个元素上 bool IsEmpty(); // 判断链表是否为空 void SortedInsert(void *item, int sortKey); // 将元素根据key值优先权插入到链中 void *SortedRemove(int *keyPtr); // 将key值最小的元素从链中删除， // 并返回该元素 private:

ListElement *first; // 链表中的第一个元素 ListElement *last; // 链表中的最后一个元素 };

二、 线程启动和调度模块分析（文件switch.s switch.h）

线程启动和线程调度是线程管理的重点。在Nachos中，线程是最小的调度单位，在同一时间内，可以有几个线程处于就绪状态。Nachos的线程切换借助于宿主机的正文切换，由于这部分内容与机器密切相关，而且直接同宿主机的寄存器进行交道，所以这部分是用汇编来实现的。由于Nachos可以运行在多种机器上，不同机器的寄存器数目和作用不一定相同，所以在switch.s中针对不同的机器进行了不同的处理。

ThreadRoot函数

Nachos中，除了main线程外，所有其它线程都是从ThreadRoot入口运行的。它的语法是：

ThreadRoot (int InitialPC, int InitialArg, int WhenDonePC, int StartupPC)

其中，InitialPC指明新生成线程的入口函数地址，InitialArg是该入口函数的参数；StartupPC是在运行该线程是需要作的一些初始化工作，比如开中断；而WhenDonePC是当该线程运行结束时需要作的一些后续工作。在Nachos的源代码中，没有任何一个函数和方法显式地

调用ThreadRoot函数，ThreadRoot函数只有在线程切换时才被调用到。一个线程在其初始化的最后准备工作中调用StackAllocate方法，该方法设置了几个寄存器的值（InterruptEnable函数指针，ThreadFinish函数指针以及该线程需要运行函数的函数指针和运行函数的参数） ，该线程第一次被切换上处理机运行时调用的就是ThreadRoot函数。其工作过程是：

1. 调用 StartupPC 函数； 2. 调用 InitialPC 函数； 3. 调用 WhenDonePC 函数；

这里我们可以看到，由ThreadRoot入口可以转而运行线程所需要运行的函数，从而达到生成线程的目的。

SWITCH函数

Nachos中系统线程的切换是借助宿主机的正文切换。SWITCH函数就是完成线程切换的功能。SWITCH的语法是这样的： void SWITCH (Thread *t1, Thread *t2);

其中t1是原运行线程指针，t2是需要切换到的线程指针。线程切换的三步曲是：

1. 保存原运行线程的状态 2. 恢复新运行线程的状态

3. 在新运行线程的栈空间上运行新线程

三、 线程模块分析（文件thread.cc thread.h）

Thread类实现了操作系统的线程控制块，同操作系统课程中进程程管理中的PCB (Process Control Block) 有相似之处。

Thread线程控制类较PCB为简单的多，它没有线程标识 (pid)、实际用户标识 (uid)等和线程操作不是非常有联系的部分，也没有将PCB分成proc结构和user结构。这是因为一个Nachos线程是在宿主机上运行的。无论是系统线程和用户进程，Thread线程控制类的实例都生成在宿主机而不是生成在虚拟机上。所以不存在实际操作系统中proc结构常驻内存，而user结构可以存放在盘交换区上的情况，将原有的两个结构合并是Nachos作的一种简化。

Nachos对线程的另一个简化是每个线程栈段的大小是固定的，为4096-5个字 (word)，而且是不能动态扩展的。所以Nachos中的系统线程中不能使用很大的栈空间，比如： void foo () { int buff[10000]; ...}

可能会不能正常执行，如果需要使用很大空间，可以在Nachos的运行堆中申请： void foo () { int *buf = new int[10000]; ...}

如果系统线程需要使用的栈空间大于规定栈空间的大小，可以修改StackSize宏定义。

Thread类的定义和实现如下所示： class Thread { private: int* stackTop; // 当前堆栈指针 int machineState[MachineStateSize]; // 宿主机的运行寄存器 public: Thread(char* debugName); // 初始化线程 ~Thread(); // 析构方法

void Fork(VoidFunctionPtr func, int arg); // 生成一个新线程，执行func(arg) void Yield(); // 切换到其它线程运行 void Sleep(); // 线程进入睡眠状态 void Finish(); // 线程结束时调用 void CheckOverflow(); // 测试线程栈段是否溢出 void setStatus(ThreadStatus st); // 设置线程状态 char* getName() { return (name); } // 取得线程名（调试用） void Print() { printf(\ // 打印当前线程名（调试用） private: int* stack; // 线程的栈底指针 ThreadStatus status; // 当前线程状态 char* name; // 线程名（调试用） void StackAllocate(VoidFunctionPtr func, int arg); // 申请线程的栈空间 #ifdef USER_PROGRAM int userRegisters[NumTotalRegs]; // 虚拟机的寄存器组 public: void SaveUserState(); // 线程切换时保存虚拟机寄存器组 void RestoreUserState(); // 线程切换时恢复虚拟机寄存器组 AddrSpace *space; // 线程运行的用户程序 #endif }

线程控制类中的stackTop栈指针变量，machineState机器寄存器数组变量的位置必须是固定的，因为这两个变量和线程的切换有密切的关系，在SWITCH函数中： void SWITCH (Thread *t1, Thread *t2);

(int *)(*t1)实际上指向原有线程的栈空间，而 (int)(*(t1+1))开始则同宿主机的寄存器组一一对应。这样使SWITCH的实现比较简单。

四、 几种重要的方法 Fork 方法

void Fork (VoidFunctionPtr func, int arg) func: 新线程运行的函数 arg: func函数的参数

线程初始化之后将线程设置成可运行的

StackAllocate 方法

void StackAllocate (VoidFunctionPtr func, int arg) func: 新线程运行的函数 arg: func函数的参数

为一个新线程申请栈空间，并设置好准备运行线程的条件。 void Thread::StackAllocate (VoidFunctionPtr func, int arg) { stack = (int *) AllocBoundedArray(StackSize * sizeof(int));

// 申请线程的栈空间 stackTop = stack + StackSize - 4; // 设置栈首指针 *(--stackTop) = (int)ThreadRoot; // 线程准备好运行后进行线程切换，会切换到ThreadRoot函数。ThreadRoot函数 // 将会开中断，并调用func(arg)成为一个独立的调度单位。 *stack = STACK_FENCEPOST; // 设置栈溢出标志

machineState[PCState] = (int) ThreadRoot; // 设置PC指针，从ThreadRoot开始运行 machineState[StartupPCState] = (int) InterruptEnable; machineState[InitialPCState] = (int) func; machineState[InitialArgState] = arg;

machineState[WhenDonePCState] = (int) ThreadFinish; // 以上是为ThreadRoot作好准备，ThreadRoot将分别调用InterruptEnable， // func(arg)和ThreadFinish。 }

Yield 方法 void Yield ()

当前运行强制切换到另一个就绪线程运行

Sleep 方法 void Sleep ()

线程由于某种原因进入阻塞状态等待一个事件的发生（信号量的V操作、开锁或者条件变量的设置）。当这些条件得到满足，该线程又可以恢复就绪状态。

五、 线程调度算法模块分析（文件scheduler.cc scheduler.h）

该模块的作用是进行线程的调度。在Nachos系统中，有一个线程就绪队列，其中是所有就绪线程。调度算法非常简单，就是取出第一个放在处理机运行即可。由于Nachos中线程没有优先级，所以线程就绪队列是没有优先级的。 Run方法：

void Run (Thread *nextThread)

nextThread: 需要切换运行的线程

当前运行强制切换到nextThread就绪线程运行

Scheduler类的定义和实现如下： class Scheduler { public: Scheduler(); // 初始化方法 ~Scheduler(); // 析构方法

void ReadyToRun(Thread* thread); // 设置一个线程为就绪态， 将参数指向的进程放到队列后面。 Thread* FindNextToRun(); void Run(Thread* nextThread); void Print(); private:

// // //

找出下一个处于就绪态的线程 切换到nextThread执行

打印出处于就绪态的所有线程

List *readyList; // 线程就绪队列 };

所有Scheduler中定义的方法都有一个前提条件：必须是原子操作，不允许中断。

六、 Nachos主控模块分析（文件main.cc system.cc system.h） int main (int argc, char **argv) { 对命令行参数进行处理，并且初始化相应的功能 currentThread -> Finish (); return (0); // 此行执行不到。 }

七、 信号量 ( Semaphore )

Nachos已经实现了Semaphore，它的基本结构如下所示： class Semaphore { public:

void P(); 核心操作：

//禁止中断，并保存初始中断状态。因为开始时中断也可能处于被禁止//状态，所以操作结束后要恢复到初始状态而不是使能中断。

IntStatus oldLevel = interrupt->SetLevel(IntOff);

//当信号量为0时，将当前进程放到等待队列里面，并设置为睡眠模式， //参数值为FALSE表示，进程没有正常结束而要被挂起。

void V();

核心操作： //禁止中断

IntStatus oldLevel = interrupt->SetLevel(IntOff);

//如果队列不为空说明有当前进程因为要临界资源被别的进程访问而挂//起，所以V操作首先应将当前进程设置为READY状态，以继续运行并//访问临界资源

private:

int value; // 信号量值 ( >=0) List *queue; // 线程等待队列 };

信号量的私有属性有信号量的值，它是一个阀门。线程等待队列中存放所有等待该信号量的线程。信号量有两个操作：P操作和V操作，这两个操作都是原子操作。 P操作

1. 当value等于0时，

1.1. 将当前运行线程放入线程等待队列。

1.2. 当前运行线程进入睡眠状态，并切换到其它线程运行。 2. 当value大于0时，value--。 V操作

1. 如果线程等待队列中有等待该信号量的线程，取出其中一个将其设置成就绪态，准备运

行。 2. value++;

八、 锁机制

锁机制是线程进入临界区的工具。一个锁有两种状态，BUSY和FREE。当锁处于FREE态时，线程可以取得该锁后进入临界区，执行完临界区操作之后，释放锁；当锁处于BUSY态时，需要申请该锁的线程进入睡眠状态，等到锁为FREE态时，再取得该锁。

锁的基本结构如下所示： class Lock { public:

Lock(char* debugName); // 初始化方法 ~Lock(); // 析构方法 char* getName() { return name; } // 取出锁名（调试用） void Acquire(); // 获得锁方法 void Release(); // 释放锁方法 bool isHeldByCurrentThread(); // 判断锁是否为现运行线程拥有 private:

char* name; // 锁名（调试用） };

九、 条件变量

条件变量和信号量与锁机制不一样，它是没有值的。（实际上，锁机制是一个二值信号量，可以通过信号量来实现）当一个线程需要的某种条件没有得到满足时，可以将自己作为一个等待条件变量的线程插入所有等待该条件变量的队列；只要条件一旦满足，该线程就会被唤醒继续运行。条件变量总是和锁机制一同使用，它的基本结构如下：

class Condition { public:

Condition(char* debugName); //初始化方法 ~Condition(); // 析构方法

char* getName() { return (name); }//取出条件变量名（调试用） void Wait(Lock *conditionLock); //线程进入等待 void Signal(Lock *conditionLock); //唤醒一个等待该条件变量的线程

void Broadcast(Lock *conditionLock);// 唤醒所有等待该条件变量的线程 private:

char* name;//条件变量名（调试用） };

总体来说，条件变量有三个操作Wait、Signal以及BroadCast，所有的这些操作必须在当前线程获得一个锁的前提下，而且所有对一个条件变量进行的操作必须建立在同一个锁的前提下。

3. 实验总结

本次课程设计主要围绕nachos线程模块做了分析，觉得nachos虽小但是它是一个完整的基本的操作系统，各个模块的实现虽然简单，但是它们之间相互协作能够形成一个系统，我觉得这就是操作系统的精髓，正如积小流以成江河的道理一样。真正的做一个操作系统，我认为不在于其算法有多优秀，而在于其算法有多适用，算法的适用都是因不同的环境而定的。这次课程设计，我阅读了不少的代码，从实践的角度了解了操作系统，我觉得我的收获很大。操作系统不仅仅是一门理论性很强的课程，我觉得应该更看重它的实用性。有些东西本来是很通俗易懂的，拿到理论的层面上，便变得很枯燥、很难懂。Nachos利用其简单易懂的设计使我们对课本上的概念有了更深刻的理解。

在这次试验中，我遇到了很多的困难，本来是想做nachos二次开发的，结果在linux上面装g++编译器时出现了问题，由于我的电脑的光驱坏了，导致我的linux的依赖包无法安装，所以改作源码分析了，还请老师谅解。最后，谢谢老师指导！

本文来源：https://www.bwwdw.com/article/ciut.html