nachos代码阅读--xq

1. 宏总结：

?

/threads/thread.h

#define MachineStateSize 18 #define StackSize (4 * 1024) ? ? ?

/userprog/addrspace.h #define UserStackSize /userprog/bitmap.h #define BitsInByte 8 #define BitsInWord 32 ?

/userprog/syscall.h #define SC_Halt #define SC_Exit #define SC_Exec #define SC_Join #define SC_Create #define SC_Open #define SC_Read #define SC_Write #define SC_Close #define SC_Fork #define SC_Yield 10

#define ConsoleInput 0 #define ConsoleOutput 1 ?

/machine/disk.h #define SectorSize #define NumTracks per disk ?

/machine/disk.cc

#define MagicNumber 0x456789ab #define MagicSize ?

/machine/machine.h

#define PageSize SectorSize // set the page size equal to the disk sector size, for simplicity

#define NumPhysPages 32

#define MemorySize (NumPhysPages * PageSize)

sizeof(int)

#define DiskSize (MagicSize + (NumSectors * SectorSize))

128 // number of bytes per disk sector 32 // number of tracks per disk

(SectorsPerTrack * NumTracks) // total # of sectors

#define SectorsPerTrack 32 // number of sectors per disk track #define NumSectors

0 1 2 3 4 5 6 7 8 9

1024

/threads/thread.cc

#define STACK_FENCEPOST 0xdeadbeef

#define StackReg 29 // User's stack pointer #define RetAddrReg #define HiReg #define LoReg #define PCReg

31 // Holds return address for procedure calls

#define NumGPRegs 32 // 32 general purpose registers on MIPS

32 // Double register to hold multiply result 33

34 // Current program counter

#define NextPCReg 35 // Next program counter (for branch delay) #define PrevPCReg 36 // Previous program counter (for debugging) #define LoadReg

37 // The register target of a delayed load.

#define LoadValueReg 38 // The value to be loaded by a delayed load. #define BadVAddrReg 39 // The failing virtual address on an exception #define NumTotalRegs 40 ?

/machine/mipssim.h #define OP_???? ?

/filesys/directory.h #define FileNameMaxLen <= 9 characters long ?

/filesys/filehdr.h #define NumDirect ?

/filesys/filesys.cc #define FreeMapSector

0

#define DirectorySector 1

#define FreeMapFileSize (NumSectors / BitsInByte) #define NumDirEntries

10

(sizeof(DirectoryEntry) * NumDirEntries)

#define DirectoryFileSize ?

2. /nachos-3.4/code/

A. Makefile.dep:

GNU-Makefile的一部分，指定了Makefile系统环境中相互依赖的部分，还指定了平台，此处为Linux； # also, Linux HOST = -DHOST_i386 LDFLAGS =

B. Makefile.common：

1) 包含了nachos提供的所有的基本程序（baseline code），无论何时需要添加 .h

和 .cc 文件，都需要在相应的_H、_C和_O列表中修改； 2) 任务的依赖关系有： /filesys/fstest.cc

#define TransferSize 10 // make it small, just to be difficult

((SectorSize - 2 * sizeof(int)) / sizeof(int))

#define MaxFileSize (NumDirect * SectorSize)

9

// for simplicity, we assume file names are

#define TransferSize 10 // make it small, just to be difficult

a) threads在所有程序之前； b) userprog在vm之前运行；

c) userprog可在filesys之前或之后运行，但是如果先运行userprog，必须定

义filesys_stub；

3) 当修改程序的架构时，应该在相应的子文件夹下执行make depend，程序会自动

修改Makefile并更新依赖性；

4) CFLAGS = -g -Wall -Wshadow $(INCPATH) $(DEFINES) $(HOST) –DCHANGED：

-g：在可执行程序中包含标准调试信息；

-Wall：允许发出Gcc提供的所有有用的报警信息；

-Wshadow：当局部变量遮蔽(shadow)了参数、全局变量或其他局部变量时，该选项会给我们警告信息； -DCHANGED：

5) Depend函数：

6) –DTHREADS：Dthreads is an efficient deterministic multithreading system for unmodified

C/C++ applications that replaces the pthreads library.

C. Makefile：

1) Lpr：将档案或是由标准输入送进来的资料送到打印机贮列之中，打印机管理程序

lpd 会在稍后将这个档案送给适当的程序或装置处理。lpr 可以用来将料资送给本地或是远端的主机来处理。； 2) Make nachos： D.

3. /nachos-3.4/code/threads/

A. Makefile：

和线程任务有关的Makefile，首先必须完成线程任务。 B. Utility.cc：

调试代码，通过命令行参数允许用户控制是否打印调试信息；

1) DebugInit（）：只能打印flaglist的调试信息，即确定打印调试信息的部分； 2) Debug（）：打印调试信息； C. Main.cc：

初始化操作系统内核的引导程序代码。允许直接调用内部的操作系统函数来简化调试和测试。实际上，这些引导程序代码只是初始化数据结构，然后开启一个用户线程来打印注册提示。 1) 相关编译选项：

nachos -d -rs

-s -x -c -f -cp

-p -r -l -D -t

-n -m -o -z

-d causes certain debugging messages to be printed (cf. utility.h) -rs causes Yield to occur at random (but repeatable) spots -z prints the copyright message

USER_PROGRAM

-s causes user programs to be executed in single-step mode -x runs a user program -c tests the console

FILESYS

-f causes the physical disk to be formatted -cp copies a file from UNIX to Nachos -p prints a Nachos file to stdout

-r removes a Nachos file from the file system -l lists the contents of the Nachos directory -D prints the contents of the entire file system -t tests the performance of the Nachos file system

NETWORK

-n sets the network reliability

-m sets this machine's host id (needed for the network)

-o runs a simple test of the Nachos network software

备注：直到完成相关任务时这些选项才会起作用

2) Main():操作系统内核的启动代码，工作有检查命令行参数，初始化数据结构，以

及选择性地调用测试程序；

3) Main（）函数最后调用CurrentThread->Finish（）函数，是因为nachos相对于

宿主机来说只是一个程序，直接exit(0)会导致nachos退出，但是nachos系统中可能有等待线程，所以我们切换到这些线程告诉它们主线程已经结束，防止它们返回。

D. system.h：

定义了nachos所用的全局变量； E. system.cc：

1) 定义了所有的全局数据结构，并进行初始化和分配空间；

Thread *currentThread; Scheduler *scheduler; Interrupt *interrupt; Statistics *stats; Timer *timer;

// the thread we are running now // the ready list // interrupt status // performance metrics // the hardware timer device, // for invoking context switches

Thread *threadToBeDestroyed; // the thread that just finished

2) 定义了Nachos两个函数：Initialize（）和Cleanup（）；

a) Initialize（）：初始化nachos的全局数据结构，诠释命令行参数； b) Cleanup（）：终止nachos，释放全局数据结构；

3) TimerInterruptHandler（）：Timer device周期性（每个TimerTicks一次）中

断CPU，然后每次会调用此函数，同时关闭中断。直接调用Yield（）会挂起interrupt handler，而不是被中断的线程。不同的是，我们设置一个flag，所以当完成interrupt handler时，看起来就像是被中断的线程在中断时刻调用了

Yield（）。参数Int dummy（虚拟/假的）是因为interrupt handler都需要一个参数，无论是否需要；

F. thread.cc（h）：

1) 管理线程的数据结构，一个现场的状态包括pc、寄存器和执行栈；

a) 为每个栈分配固定的空间，所以要防止栈溢出，动态分配数据结构空间； b) 调试是否是栈空间太小导致segmentation fault，可以增加占空间

ThreadStackSize；

c) Fork一个线程包括：先分配一个数据结构空间，然后调用fork（）函数； 2) 线程状态（ThreadStatus）包括：刚创建、运行中、准备好、阻塞； 3) 线程控制块（class Thread）：表示一个线程的执行状况，包括：

a) 一个执行栈，用来保存活跃记录，以及不运行的时候保存CPU寄存器； b) 某些用户线程包括一个用户地址空间，内核线程的地址空间为NULL； c) 基本操作包括：Fork（调用内置函数stackAllocate（））、Yield、Sleep、

Finish、CheckOverflow、setStatus、getName、Print；

d) 用户线程包括两套CPU寄存器，分别保存执行用户和内核代码的状态； 4) Thread（）：初始化一个线程控制块，之后就可以调用Fork函数，参数为线程名

字，是一个任意字符串，用来调试；

5) ~Thread（）：释放一个线程空间，参数是线程名字。但是current线程不能直接

删除自己，因为它运行在我们将要删除的栈空间。同时主线程不能删除栈空间，因为主线程空间是我们自动获取的，它是启动nachos的一部分；

6) Fork（）：调用（*func）（arg），使得caller和callee可以并发执行。虽然arg

只是一个int型变量，但是可以把想要传递的参数打包成一个数据结构，然后把它的指针作为int参数。执行步骤包括： a) 分配栈空间；

b) 初始化栈使得switch函数可以运行此程序； c) 将线程放入就绪队列；

7) CheckOverflow（）：nachos不会捕获所有的溢出情况，所以程序仍然可能因为溢

出挂掉。

8) Finish（）：当一个fork线程执行完毕被ThreadRoot调用。但是我们没有立即释

放线程数据结构空间，因为该线程仍在运行切还在其栈空间。相反，我们设置“threadToBeDestroyed”，使得我们在不同的线程上下文环境时，调度器可以调用析构函数。我们关闭中断，使得设置“threToBeDestroyed”和sleep之间没有时间片；

9) Yield（）：当有其它就绪线程时刻放弃CPU资源，并把当前线程放入就绪队列队

首使得可以被再次调度。如果没有就绪队列则立即返回。关闭中断，使得检查就绪线程队列和切换上下文可以原子操作完成。返回之后，立即设置中断到之前状态，以免被其他中断操作影响；

10) Sleep（）：等待一个同步变量而挂起并让出CPU。最后，某个线程会唤醒此线程，

并放入就绪队列可以被再次调度。没有就绪线程则调用Interrupt：：Idle函数，表明CPU空闲，直到IO中断使得某个线程再次运行。关闭中断保证取出就绪队列线程和切换上下文是原子操作；

11) ThreadFinish、InterruptEnable和ThreadPrint函数都是伪函数，因为C++不允

许指针指向成员函数。所以，创建伪C函数可以使用指针调用成员函数； 12) StackAllocate（）：分配和初始化执行栈，为ThreadRoot函数的栈框架，使得可

以开中断、调用（*func）（arg）以及调用Thread：：Finish函数； 13) SaveUserState/RestoreUserState：在上下文切换时保护/恢复CPU状态； G. Threadtest.cc：

工作机制是创建两个线程，通过调用Yield（）函数频繁切换上下文，显示内部线程的工作过程；

1) SimpleThread（）：循环5次，让出CPU给其它准备好的线程，参数int which是

为了调试用；

2) ThreadTest1（）：在两个线程之间设置ping-pong，fork一个线程调用

SimpleThread（）函数，再自己调用SimpThread（）函数；

3) ThreadTest（）：通过检查参数int testnum是否是1决定是否调用测试代码，即

调用ThreadTest1（）函数；

H. Scheduler.h：

线程分发器和调度器的数据结构，包括一个就绪队列； I. Scheduler.cc：

选择下一个要运行的线程，并且调度该线程。这些代码假设中断已关来实现互斥。在这里我们不能使用锁来提供互斥机制，因为我们需要等待一个锁，而且这个锁是被占用的，我们最后会调用FindNextToRun（），这会使我们进入一个无限的循环。 1) Scheduler（）：初始化就绪队列为空； 2) ~scheduler（）：删除就绪线程队列；

3) ReadyToRun（）：标记一个线程为ready，放入就绪队列末尾；

4) FindNextToRun（）：返回下一个将要运行的线程，没有则返回NULL，同时从就绪

队列删除该线程；

5) Run（）：把CPU分发给下一个运行线程。调用switch代码以保存旧线程状态，同

时加载新线程状态；

a) 保存当前线程指针为oldThread；

b) 如果是用户程序，则保存用户的CPU寄存器；

c) 检查oldThread是否栈溢出（因为不是时刻检查栈段溢出，所以这时线程的

运行可能已经出错）；

d) 当前线程置为传进来的参数nextThread； e) 当先线程状态设为Running；

f) 调用switch，切换新旧线程的状态（之前运城在当先线程的栈空间，之后运

行在nextThread的栈空间）；

g) 如果旧线程因为结束放弃运行，即被赋给threadToBeDestroyed，则删除旧

线程；

h) 如果是用户程序，则恢复当前线程的地址空间；

6) Print（）：打印调度器的状态，即就绪队列的内容，用于调试； J. Switch.s：

与机器有关的上下文切换代码。说是机器相关的，是因为需要保存的寄存器、设置初始的调用函数栈空间等对于每一个处理器架构都是特别的。此处为每种架构设计了两段代码：

1) ThreadRoot（InitialPC, InitialArg, WhenDonePC, StartupPC）：

a) InitialPC：将要运行的线程的入口函数的地址； b) InitialArg：入口函数的参数；

c) WhenDonePC：当该线程运行结束时要调用的代码；

d) StartupPC：运行该线程需要调用的代码，即要做的一些初始化工作； e) 在nachos源代码中，没有函数和方法显式调用此函数，ThreadRoot函数只

有在线程切换时才被调用。线程在初始化的最后准备工作要调用StackAllocate方法，该方法设置了几个寄存器的值，该线程第一次被切换时调用的就是ThreadRoot函数。其工作流程为： [1]. 清除帧指针；

[2]. 调用StartupPC函数；

[3]. 设置InitialArg参数，调用InitialPC函数，主程序； [4]. 调用WhenDonePC函数，结束时调用clean up程序；

f) 由此，ThreadRoot入口可以转而运行线程所要运行的函数，从而生成一个新

的线程；

2) SWITCH(oldThread, newThread)：

a) oldThread：当前运行的线程，需要保存其CPU寄存器状态； b) newThread：将要运行的线程，需要加载其CPU寄存器状态；

c) 在Makefile.dep下定义了HOST = -DHOST_i386，所以只需看最下面的汇编

代码； d) 工作流程是：

[1]. 保存当前线程的状态：栈指针、被调用者保存的寄存器、帧指针、返回

地址；

[2]. 加载将要运行的线程状态：栈指针、被调用者保存的寄存器、帧指针、

返回地址；

[3]. 跳转到新运行的线程的栈空间运行新线程；

K. Synch.h：

同步线程的数据结构。这里定义了三种类型：信号量、锁和条件变量。已经实现了信号量，且给出了锁和条件变量的接口。此处每个同步对象都有一个name便于调试。 1) Class Semaphore：

定义了一个非负整数value，包括一个在P处的等待队列queue。还有一个函数bool isHeldByCurrentThread（），检查如果是currentThread持有该锁则返回true，用于检查Release时用。只有两个原子操作P和V： a) P（）：等待直到value>0。然后减1； b) V（）：加1，唤醒一个正在P()等待的线程；

此处不允许直接读信号量的值，即使读也是旧的值，不知道最新的值是多少，因为从寄存器读取时，可能发生了上下文切换，也可能有其它线程修改了信号量的值。

2) Class Lock：

锁机制是线程进入临界区的工具。一个锁有busy和free两种状态，当锁处于free时，线程可以申请取得锁进入临界区，执行完临界区代码后释放锁；当锁处于busy时，需申请该锁的线程进入睡眠态，等到锁为free时再申请取得锁。包含两个原子操作Acquire和Release，而且只有得到锁的线程才可以释放它：

a) Acquire（）：锁为busy时进入睡眠等待；锁为free时，线程获得锁设置为

busy继续运行；

b) Release（）：设置锁为free，如有等待线程，唤醒其中一个线程进入就绪态； 和信号量类似，不允许直接读锁的值value，因为读过之后马上就可能改变。另外，在这里可以添加需要实现锁自定义的变量。

3) Class Condition：

条件变量没有值，当一个线程需要的某种条件没有满足时，可作为一个等待条件变量的线程插入所有等待该条件变量的队列，只要条件满足就会被唤醒继续运行。条件变量总是和锁机制一同使用，在条件变量上有三个操作（所有这些操作必须在currentThread持有一个锁的前提下，且所有对一个条件变量进行的操作必须建立在同一个锁的前提下，保证访问该条件变量的线程之间的互斥）：

a) Wait（）：释放锁，放弃CPU进入睡眠等待直到接收到信号，然后再次申请锁。

其中，释放锁和进入睡眠都是原子操作；

b) Signal（）：唤醒一个等待该条件变量的线程（如果存在）； c) Broadcast（）：唤醒所有等待该条件变量的线程（如果存在）；

在nachos中，所有的条件变量默认是遵循Mesa规范——当调用Signal或者Broadcast唤醒一个线程时，该线程置于等待链表，该线程调用Wait等待再次获得锁。不同于Hoare规范——发送信号的线程放弃锁和CPU给唤醒的线程，唤醒的线程立即运行，然后在运行至临界区之外时将锁给先前发送信号的线程。 使用Mesa规范导致在被唤醒的线程得到机会运行之前，可能有其它线程得到这个锁并且改变数据结构。

L. Synch.cc：

线程同步的代码。关于同步代码的实现需要一些原语的原子操作。我们假定nachos运行在单处理器上，因此原子操作可以通过关中断来实现。关闭中断后，没有上下文切换，currentThread确保一直占用CPU，直到中断打开。

一些代码调用时中断可能已关闭（比如信号量的V操作），我们直接重设中断状态到它原来的状态，而不是在原子操作的最后打开中断。 1) Class Semaphore：

a) Semaphore（char* debugName, int initialValue）：构造函数，初始化一个

信号量；

b) ~Semaphore()：当没有线程等待该信号量时，删除该信号量；

c) P（）：关中断，循环判断value的值，如果等于0则插入该信号量的等待队

列queue，然后调用sleep进入睡眠状态并切换到其它线程运行，唤醒之后继续检查value的值。检查到value>0，则跳出循环将value减1，然后恢复中断至原来的状态；

d) V（）：关中断，如果线程等待队列中有等待该信号量的线程，取出队首线程，

不为空则设为ready准备运行，然后立即将value加1，最后恢复中断状态；

2) 关于Lock和Condition的函数需要后面完善； M. Synchlist.h：

定义了对一个链表同时访问时的数据结构。通过在抽象链表数据结构前后添加同步代码来完善。

Class SynchList定义了同步的链表，该链表满足约束条件： 1) 试图从链表删除一个元素，必须等待链表中含有一个元素； 2) 每个时刻只有一个线程可以访问链表数据结构；

私有变量包括list链表（一个未同步的链表）、lock锁（保证对链表的互斥访问）、listEmpty条件变量（链表为空时在Remove处等待）。 N. Synchlist.cc：

用管程monitor的方式实现——每个程序都用一个锁的获得和释放对维护，同时利用条件变量的Signal和Wait来同步。

1) SynchList（）：为一个同步链表分配和初始化一个数据结构，初始链表为空； 2) ~ SynchList（）：删除为一个同步链表分配的资源；

3) Append（）：在链表末尾添加一个元素item，并唤醒所以等待添加元素的线程，

item是将要放进链表的东西，也可以是一个指针。执行过程是尝试申请取得锁（保证互斥访问）->添加元素item->唤醒等待的线程->释放锁；

4) Remove（）：删除链表的开头元素，若链表为空等待，最后返回删除的元素。执行

过程为尝试申请取得锁->循环检查链表为空则等待->链表不为空，则删除开头元素->释放锁->返回该元素；

5) Mapcar（）：将函数应用于链表的每个元素，遵循互斥的限制。执行过程为尝试申

请取得锁->调用List类的Mapcar->释放锁；

O.

4. /nachos-3.4/code/machine：

A. Timer.h：

定义了模拟硬件时钟的数据结构。一个硬件时钟每x毫秒，这可以用来给时间分片，或者让一个线程睡眠一定长的时间段。

此处模拟硬件时钟的思路是每次TimerTicks使得变量stats->totalTicks增加就产生一个终端。为了在时间分片上产生一定的随机性，可以设置变量‘doRandom’，然后在随机的ticks之后产生中断。

不能改编代码，因为这是机器模拟的一部分。 Timer.cc：

只是为了模拟一个nachos运行的硬件，并不是nachos系统的部分。所以不要改变： 1) static void TimerHandler(int arg)：伪处理中断的函数；

a) 在Timer的初始化函数中，调用此内部函数；

b) 不直接使用初始化函数中的timeHandler参数作为中断处理函数的原因：如

果直接使用

timeHandler

作为时钟中断处理函数，

(int)

this,

interrupt->Schedule(TimerHandler, TimeOfNextInterrupt(),

TimerInt)是将一个时钟中断插入等待处理中断队列，一旦中断时刻到来则立即处理中断，处理结束后没有机会将下一个时钟中断插入等待处理的中断队列。而时钟中断时刻到来，调用TimerHandler内部函数，TimerHandler则调用TimerExpired成员函数，该函数可以将新的中断插入到等待处理的中断队列，然后再调用真正的时钟中断处理函数；

c) 不讲TimerExpired函数作为时钟中断在Timer的初始化函数中调用的原因：

C++不能直接引用一个类成员函数的指针，所以借用TimerHandler内部函数，也因此将TimerExpired设置为public属性；

2) Timer：初始化一个硬件时钟设备，每次中断，保存要调用的地址，然后安排时钟

开始产生中断；

3) TimerExpired（）：模拟产生中断的代码。调度下一次中断，并且调用中断处理函

数；

4) TimeOfNextInterrupt（）：返回下一次时钟中断的时间。如果设置了随机查宿，

则产生一个伪随机的延迟；

B. Interrupt.h：

定义模拟底层中断硬件的数据结构。硬件提供了代码来开关中断，可以设置SetLevel。为了模拟硬件，我们需要记录硬件设备将要产生的中断，以及它们什么时候应该产生。

这个模块也要记录模拟时间。只有一下三种情况才会增加时间：

? ? ?

再次开中断； 执行一条用户指令； 就绪队列为空；

因此，不同于真实的硬件，中断不能在关闭中断的代码中产生。这意味着不正确的同步代码可能在硬件模拟器上正常工作，但是在真实的硬件上则不然。 不能改变此处的代码，这是机器模拟的一部分。 1) IntStatus：枚举变量，包括开/关中断；

2) MachineStatus：枚举变量，包括空闲/系统/用户模式；

3) IntType：枚举变量，记录了产生中断的硬件设备，包括时钟、磁盘、控制台、网

络接收和发送；

4) PendingInterrupt：类定义了未来要产生的中断，内部数据结构均为public属性，

便于操作，包括产生中断时要调用的函数指针、传递的参数、产生的中断时间，以及初始化中断的函数；

5) Interrupt：类定义了模拟硬件中断的数据结构。记录中断是否打开，以及未来所

以的硬件中断； Interrupt.cc：

1) PendingInterrupt：：PendingInterrupt（）：初始化未来要调度的硬件设备中断； 2) Interrupt：：Interrupt（）：初始化硬件设备中断，即中断关闭，清楚inHandler

标志，初始为系统态，同时初始化等待处理的中断队列；

3) Interrupt：：~ Interrupt（）：删除模拟中断所需的数据结构，循环释放等待处

理的中断队列中每个中断占用的空间资源；

4) Interrupt：：ChangeLevel（）：改变中断类型为开/关，同时模拟时间不能增加，

是一个内置函数；

5) Interrupt：：SetLevel（）：设置中断为开/关，而且如果设置打开中断，通过调

用OneTick（）使得模拟时间增加。最后返回之前的中断开/关状态；

6) Interrupt：：Enable（）：打开中断，不关心之前的状态，在ThreadRoot中用于

启动一个线程时打开中断；

7) Interrupt：：OneTick（）：模拟时间增加一个单位，根据当前状态为用户态/系统

态时钟分别前进一个用户态时间单位/系统态时间单位，并更新nachos用户态和系统态运行的时间，同时检查当前是否还有中断发生，有则进行处理。有两种情况会调用此函数：

? ?

再次打开中断； 执行一条用户指令；

执行的过程如下： a) 保存旧状态；

b) 前进和前进时间单位； c) 关中断；

d) 等待将要发生的中断；

e) 如果yieldOnReturn为true，表示要切换上下文，则切换到内核模式，当前

线程调用Yield（）函数让出CPU；

8) Interrupt：：YieldOnReturn（）：在一个中断处理程序内部被调用，返回时在被

中断的线程引发一个上下文切换。在这里不能切换上下文，否则会置换掉中断处理函数，而我们想要置换被中断的线程。此函数内部设置yieldOnReturn标志；

9) Interrupt：：Idle（）：就绪队列为空调用的代码。检查当前等待处理的中断队列

是否有待处理的中断，如果有将系统时钟前进到下一个被调度的中断进处理。然后处理在新的时刻其他需要发送的中断。如果没有等待的中断，则无事可做，调用Halt（）停止；

10) Interrupt：：Halt（）：关掉nachos系统，打印性能数据，最后调用cleanup（）

函数；

11) Interrupt：：Schedule（）：安排CPU在某个模拟的时刻被中断，nachos的内核

不能直接调用，只有硬件设备模拟可以调用此代码；

12) Interrupt：：CheckIfDue（bool advanceClock）：检查一个中断是否要被调度发

生，如果是，则发射中断，并返回true；参数advanceClock是时钟前进标志，为true表示就绪队列为空，系统处于Idle状态，我们应该增加时间到下一个要发射的中断。如果要发生的中断为时间片守护进程，则系统退出： a) 保存旧的状态；

b) 确保中断关闭，以调用中断处理程序； c) 寻找下一个要发生的中断；

d) 如果没有要发生的中断，返回false；

e) 设置了advanceClock，时钟前进到要发生的中断的时刻；

f) 未设置advanceClock，不能前进时钟，则取出的中断放回原处，返回false； g) 当前为空闲模式，要发生的为时钟中断，且等待中断队列没有其他类型的中

断，则将该中断放回原处等待一会处理，返回false； h) 发生中断：

[1]. InHandler设置为true，表示正在进行中断处理程序； [2]. Status设置成系统态，说明中断处理程序是系统态的； [3]. 进行中断处理程序的处理，直到处理结束； [4]. 恢复机器状态，即恢复inHandler和status标志； [5]. 返回true；

13) PrintPending（）：打印一个将被调度的中断的相关信息，包括时间、地点和原因

（类型）；

14) Interrupt：：DumpState（）：打印完整的中断状况，包括状态和将要发生的 C. Machine.h:

1) 模拟运行在nachos上的用户程序的数据结构。用户程序被加载到主存——在

nachos看来，类似于一个byte数组。Nachos的内核也在主存中，但是在现在的很多机器上，内核被加载到一个和用户程序不同的一块内存，而且对内核的访问也不翻译或者分页。

2) 在nachos，用户程序一次执行一条指令。每次对内存的访问都会被翻译和查错。 3) Machine类用来模拟计算机主机。它提供的功能有：读写寄存器。读写主存、运

行一条用户程序的汇编指令、运行用户程序、单步调试用户程序、显示主存和寄存器状态、将虚拟内存地址转换为物理内存地址、陷入 Nachos 内核等等。 4) Machine类实现方法是在宿主机上分配两块内存分别作为虚拟机的寄存器和物理

内存。运行用户程序时，先将用户程序从 Nachos 文件系统中读出，写入模拟的物理内存中，然后调用指令模拟模块对每一条用户指令解释执行。将用户程序的读写内存要求，转变为对物理内存地址的读写。Machine类提供了单步调试用户程序的功能，执行一条指令后会自动停下来，让用户查看系统状态，不过这里的单步调试是汇编指令级的，需要读者对R2/3000指令比较熟悉。如果用户程序想

使用操作系统提供的功能或者发出异常信号时，Machine调用系统异常陷入功能，进入Nachos的核心部分。

5) Nachos寄存器组模拟了全部32个MIPS机（R2/3000）的寄存器，同时加上有关

Nachos系统调试用的8个寄存器，以期让模拟更加真实化并易于调试。 6) class Instruction：模拟机的机器指令由操作代码和操作数组成的;

class Machine: 定义Machine类的目的是为了执行用户程序，如同许多其它系统一样，用户程序不直接使用内存的物理地址，而是使用自己的逻辑地址，在用户程序逻辑地址和实际物理地址之间，就需要一次转换，系统提供了两种转换方法的接口：线性页面地址转换方法和TLB页面地址转换方法。

enum ExceptionType: 在用户程序运行过程中，会有很多系统陷入核心的情况。系统陷入有两大类原因：进行系统调用陷入和系统出错陷入。系统调用陷入在用户程序进行系统调用时发生。系统调用可以看作是软件指令，它们有效地弥补了机器硬件指令不足；系统出错陷入在系统发生错误时发生，比如用户程序使用了非法指令以及用户程序逻辑地址同实际的物理地址映射出错等情况。不同的出错陷入会有不同的处理，比如用户程序逻辑地址映射出错会引起页面的重新调入，而用户程序使用了非法指令则需要向用户报告等等。

7) 另外，由于Nachos可以在多种平台上运行，各种运行平台的数据表达方式不完全

一样，有的是高位在前，有的是高位在后。为了解决跨平台的问题，特地给出了四个函数作数据转换，它们是WordToHost、ShortToHost、WordToMachine和ShortToMachine。

D. Machine.cc:

1) Machine：初始化用户程序执行的模拟（此处实现tlb和linear page table不可

同时使用）；

2) ~Machine：释放数据空间，包括maimMemory和tlb；

3) Static void CheckEndian：检查宿主机是大端以便存储（nachos是大端存储）； 4) Machine::RaiseException：由于用户程序的系统调用或者发生异常，将控制从用

户模式转换到nachos的内核模式。当系统检查到出错陷入时调用，通过调用ExceptionHandler来处理陷入。（见exception.cc）ExceptionHandler目前对所有的陷入都不进行处理，需要进一步加强。如上面提到的，如果使用TLB表时，应该对PageFaultError作出处理；

5) Machine::Debugger：用户程序的调试工具。注意不可以用gdb，因为gdb没有运

行在nachos上。这里主要是允许单步运行，然后打印内存的内容；

6) Machine::DumpState：打印用户的CPU状态。但是打印主存的内容杀伤力比较大； 7) Machine::ReadRegister/ WriteRegister：读取或者写用户程序寄存器的内容； E. Mipssim.h:

1) 内部的模拟MIPS指令集的数据结构。opCode的名字直接取自MIPS手册，除了

OP_UNIMP（该指令合法但是还未被执行），OP_RES（保留的opcode，体系不支持）； 2) struct OpInfo：包括opCode和format，包括I、J、R； 3) opTable：确定指令的opCode和format； 4) specialTable：结合opCode翻译funct域； 5) struct OpString：为了调试打印每条指令的信息； F. Mipssim.cc:

1) 模拟了MIPS R2/3000 进程。这段代码摘自Ousterhout的MIPSSIM包。字节排列

是小端法，所以和Dec的RISC系统兼容；

2) Machine::Run：模拟nachos上用户级程序的执行，当程序开始的时候被内核调用，

从不返回。这段代码是可重入的，因为它可以被同时多次调用，然后每个线程执行各自的用户代码；

3) static int TypeToReg：检索一条指令的寄存器编号； 4) Machine::OneInstruction：执行用户级程序的一条指令；

5) Machine::DelayedLoad：模拟执行一次延迟载入的效果。注意RaiseException和

CheckInterrupts必须调用此函数，因为任何延迟的载入都必须在我们陷入内核前申请；Instruction::Decode：对一条MIPS指令译码；

6) static void Mult：模拟R2000的乘法，指针hiPtr和loPtr在保存double长度

的结果时被重写；

G. Translate.h:

1) 管理虚拟页号到物理页号的翻译，代表页号程序管理物理内存。且此处的数据结

构既用于page table，又用于tlb，条目的格式是<虚拟页号，物理页号>。 2) class TranslationEntry：无论是线性页面地址转换还是TLB页面地址转换，都

需要一张地址转换表，地址转换表是由若干个表项（Entry）组成的。每个表项记录程序逻辑页到内存实页的映射关系，和实页的使用状态、访问权限信息。

H. Translate.cc:

1) 此处支持两种翻译——linear page table， Translation lookaside buffer 2) linear page table：虚拟页号用于到此表的索引，用于查找物理页号； 3) Translation lookaside buffer：和条目的虚拟页号进行匹配，找到的话直接翻

译，否则陷入软件异常；

4) TLB转换页表是硬件来实现的，表的大小一般较实际的用户程序所占的页面数要

小，所以一般TLB表中只存放一部分逻辑页到物理页的转换关系。这样就可能出现逻辑地址转换失败的现象，会发生PageFaultException异常。在该异常处理程序中，就需要借助用户进程空间的线性页面转换表来计算出物理页，同时TLB表中增加一项。如果TLB表已满，就需要对TLB表项做LRU替换；

5) 使用TLB页面转换表处理起来逻辑较线性表为复杂，但是速度要快得多。由于TLB

转换页表是硬件实现的，所以指向TLB转换页表的指针应该是只读的，所以Machine类一旦实例化，TLB指针值不能改动；

6) 在实际的系统中，线性页面地址转换和TLB页面地址转换只能二者取一，目前为

简便起见，Nachos选择了前者；

7) WordToHost/ShortToHost/WordToMachine/ShortToMachine：转换word和short

word使得模拟机器的小端存储。

8) Machine::ReadMem(int addr, int size, int *value)：从用户逻辑地址读出size

个字节，转换成相应的类型，存放在value所指向的空间中；

9) Machine::WriteMem(int addr, int size, int value)：将value表示的数值根

据size大小转换成相应的机器类型存放在add用户逻辑地址中；

10) Machine::Translate(int virtAddr, int* physAddr, int size, bool writing)：

将用户的逻辑地址转换成实际的物理地址，同时需要检查对齐等各种错误

5. /nachos-3.4/code/userprog/：

A. addrspace.h:记录用户程序执行过程的数据结构。用户级CPU状态在执行用户程序的

线程中保存和恢复。UserStackSize定义用户栈空间大小为1024，必须的话可以增加； B. addrspace.cc：

1) 为了运行一个用户程序：

a) 有-N –T 0选项；

b) 运行coff2noff把对象文件转换为nachos的格式（nachos的对象代码格式

就是一个UNIX可执行代码格式的版本）； c) 加载NOFF文件到nachos的文件系统；

2) static void SwapHeader：当在一个小端存储的机器上生成代码且正运行在大端

机器上，完成小端到大端的转换工作；

3) AddrSpace::AddrSpace：初始化用户程序空间。从可执行文件加载程序然后设置

开始执行用户指令。先设置从程序存储到物理内存的翻译，nachos最初实现很简单（1:1），因此我们只能是单程序，而且有一个未分段的unsegmented 页表； 4) AddrSpace::~AddrSpace：释放一个地址空间，目前只是删除pageTable； 5) AddrSpace::InitRegisters：设置用户寄存器组的初始值。我们直接写进机器寄

存器，然后就可以直接跳转到用户代码；

6) AddrSpace::SaveState：在上下文切换时保存机器状态，特别是地址空间，目前

什么都不做；

7) AddrSpace::RestoreState：在上下文切换时恢复机器状态，以便于运行地址空间。

目前只是告诉机器如何找到pageTable；

C. bitmap.h:定义了一个bitmap——一个bit数组，每一位可以是on或者off。代表一

个unsigned int数组，用于取模运算找到感兴趣的bit。在管理一些数组元素的分配有用。

在Nachos的文件系统中，是通过位图来管理空闲块的。Nachos的物理磁盘是以扇区为访问单位的，将扇区从0开始编号。所谓位图管理，就是将这些编号填入一张表，表中为0的地方说明该扇区没有被占用，而非0位置说明该扇区已被占用。这部分内容是用BitMap类实现的。

D. progtest.cc:用于测试nachos可以加载一个用户程序并且执行它。也可以测试控制台

的硬件设备。

1) StartProcess：运行一个用户程序。打开可执行文件，加载到主存然后跳转执行。 2)

E. exception.cc：

从用户程序进入nachos内核的入口，有两个事件会导致控制转移给内核：

? syscall：用户代码显式调用内核程序，现阶段只支持halt指令，即系统调用； ? exceptions：用户执行一些CPU不能解决的事情，比如访问不存在的主存，即系

统出错陷入；

中断也可以将控制从用户转到内核，但是在他处处理。

? ExceptionHandler：系统调用用其它异常陷入的入口处理函数，陷入的类型为

SyscallException，且在test目录下的start.s模块中描述了具体的系统调用过程。start.s同ExceptionHandler()配合使用，完成整个调用过程；

? 函数的参数which指明异常类型。函数内部，先取出系统调用的类别码（读第2

个寄存器）放在变量type中，然后如果是系统异常且是SC_Halt，则调用Halt函数，否则出错返回。

F. syscall.h:

nachos系统调用的接口这些函数可以被用户程序调用陷入内核。是nachos内核必须支持的，使得可以运行用户程序。

用户程序只是简单的调用这些程序，汇编语言把系统调用的代码放进寄存器，然后陷入内核。然后调用exception.cc在系统调用的入口处做一些错误检查，最后调用

nachos内核的内核程序。 G.

6. /nachos-3.4/code/filesys/:

A. Filesys.h:

在Nachos中，实现了两套文件系统，它们对外接口是完全一样的：一套称作为FILESYS_STUB，它是建立在UNIX文件系统之上的，而不使用Nachos的模拟磁盘，它主要用于读者先实现了用户程序和虚拟内存，然后再着手增强文件系统的功能；另一套是Nachos的文件系统，它是实现在Nachos的虚拟磁盘上的。当整个系统完成之后，只能使用第二套文件系统的实现。

虽然说 FileSystem中的Create、Open以及Remove方法类似于UNIX操作系统中的creat、open和unlink系统调用。但是在Nachos中，打开和创建文件没有给出打开和创建方式。这是因为在目前的Nachos文件系统中，没有用户分类的概念，也就没有同组用户和其它用户的概念。一个线程打开文件以后，就获得了对该文件操作所有的权利。大多数实用文件系统都提供对文件存取进行保护的功能，保护的一般方法是将用户分类、以及对不同类的用户规定不同的存取权。读者在Nachos提供的文件系统基础上，完全可以添加自己设计和实现的文件保护机制。 B. Filesys.cc:

1) FileSystem：参数format是是否进行格式化的标志。此函数的功能是在同步磁盘

的基础上建立一个文件系统。当format标志设置时，建立一个新的文件系统；否则使用原来文件系统中的内容。

2) Create：在当前的文件系统中创建一个固定大小的文件，在以下4种情况会失败：

? 根目录中已经存在该文件名 ? 文件头 file header 申请不到空间 ? 在目录文件中申请不到文件条目空间 ? 申请不到数据块空间

显然，在Nachos的文件系统中，对目录对象和位图对象的操作应该是临界区操作。因为如果两个线程同时需要向同一个目录中写入一个文件，可能会出现两个线程同时申请到同一个目录项；在分配空闲块时，也会出现相类似的情况。但是目前Nachos没有对此进行处理。

3) Open：在当前的文件系统中删除一个已有的文件。为了打开一个文件，首先在根

目录下查找该文件的 file header，将 header加载到内存。

4) Remove：在当前的文件系统中删除一个已有的文件。需要删除根目录下对应条目，

header 占用空间，数据块占用空间。最后需要把对位图和目录的修改写回磁盘。 5) List：列出文件系统中所有的文件，即根目录下所有文件。

6) Print：打印文件系统的位图、根目录、所有的文件以及文件的 header和数据内

容。

C. filehdr.h:

文件头实际上就是UNIX文件系统中所说的inode结构，它给出一个文件除了文件名之外的所有属性，包括文件长度、地址索引表等等（文件名属性在目录中给出）。所谓索引表，就是文件的逻辑地址和实际的物理地址的对应关系。

Nachos的文件头可以存放在磁盘上，也可以存放在宿主机内存中。在磁盘上存放时一个文件头占用一个独立的扇区。文件头被简单的组织为一个指向数据块的指针表。 Nachos文件头的索引表只有直接索引，没有间接寻址，所以限制文件的最大长度为4K bytes。

在Nachos中，每个扇区的大小为128个字节。每个inode占用一个扇区，共有30个直接索引。所以Nachos中最大的文件大小不能超过3840个字节。

没有构造函数，可以在为一个新文件分配数据块的时候或者从磁盘加载时进行初始化。 D. filehdr.cc:

和真实的文件系统不同的是，nachos没有在文件头中记录文件的permission、ownership、最后一次修改日期等信息。

1) Allocate：通过文件大小初始化文件头，并根据文件大小申请磁盘空间。 2) Deallocate：将一个文件占用的数据空间释放（未释放文件头占用空间）。 3) FetchFrom：从磁盘读出文件头的内容。 4) WriteBack：把文件头的修改内容写回磁盘。

5) ByteToSector：文件逻辑地址向物理地址的转换，返回文件中某个字节保存的山

区号。

E. directory.h:

目录是一张表，将字符形式的文件名与实际文件的文件头相对应。这样用户就能方便地通过文件名来访问文件。这里的互斥由caller保证。

每个条目是一个 pairs ，另外有一个inUse标记该目录项是否在使用。

Nachos中的目录结构非常简单，它只有一级目录，也就是只有根目录；而且根目录的大小是固定的，整个文件系统中只能存放有限个文件。 F. directory.cc:

1) Directory：构造函数初始化一个目录。，size限制了目录中可存放的文件的最大

数目。

2) ~ Directory：释放数据结构，即目录表table。 3) FetchFrom：从磁盘读目录的内容。 4) WriteBack：把对目录的任何修改写磁盘。

5) FindIndex：根据文件名返回文件头在目录表中的位置。 6) Find：在目录中根据文件名返回文件头存放的扇区编号。 7) Add/Remove：在目录中加入/删除一个文件。 G. openfile.h:

该模块定义了一个打开文件控制结构。当用户打开了一个文件时，系统即为其产生一个打开文件控制结构，以后用户对该文件的访问都可以通过该结构。打开文件控制结构中的对文件操作的方法同UNIX操作系统中的系统调用。

针对FileSystem结构中的两套实现，这里的打开文件控制结构对应的同样有两套实现 H. openfile.cc:

1) OpenFile：打开一个nachos文件进行读写操作，文件打开时把文件头加载到内存。 2) ~OpenFile：关闭nachos文件，释放内存中的数据结构。 3) Seek：改变打开的文件的当前位置，即下一个读写开始的位置。

4) Read/Write：从文件的当前位置 seekPosition 读写文件的一部分，返回实际读

写的字节数。同时，会改变文件内部的当前位置 seekPosition。

5) ReadAt/WriteAt：从传进来的参数的位置开始进行读写，返回实际读写的字节数，

不会改变文件的当前位置 seekPosition。

这里不能保证文件的读写请求是起始或者结束于偶数字节扇区，但是磁盘只知道如何一次写入一块扇区，因此：

对于ReadAt，每次将从position开始的扇区内容读入一个临时的缓冲区，然后

只复制需要的部分数据到into缓冲区；对于WriteAt，首先读入所有需要写入的扇区，将首尾扇区不能修改的内容读入到一个临时缓冲区，然后拷贝from缓冲区需要的数据到临时缓冲区，最后再将临时缓冲区的数据写入磁盘。

I. Synchdisk.h：

Nachos模拟的磁盘是异步设备。当发出访问磁盘的请求后立刻返回，当从磁盘读出或写入数据结束后，发出磁盘中断，说明一次磁盘访问真正结束。

Nachos是一个多线程的系统，如果多个线程同时对磁盘进行访问，会引起系统的混乱。所以必须限制：同时只能有一个线程访问磁盘，且当发出磁盘访问请求后，必须等待访问的真正结束。这两个限制就是实现同步磁盘的目的。

这个类提供了一个抽象，即任何一个独立的线程发出请求，等会等待直到操作结束才会返回。 J. Synchdisk.cc：

1) DiskRequestDone：磁盘中断时调用的处理函数，这里调用disk的成员函数

RequestDone。

2) ReadSector：读一个磁盘扇区到一个缓冲区，直到数据读完才返回一次。执行过

程如下： ? ? ? ?

加锁（一次只允许一个磁盘I/O） 对磁盘进行读访问请求 等待磁盘中断 释放锁（访问结束）

3) WriteSector：类比ReadSector。

4) RequestDone：磁盘中断的处理函数，唤醒任一等待磁盘请求结束的线程。 K.

7. /nachos-3.4/code/test/：

A. start.s:

在test目录下的start.s模块中描述了具体的系统调用过程，以Halt系统调用为例：

.globl Halt

.ent

Halt

//在r2寄存器中存放系统调用的类别码SC_Halt，

Halt:

addiu $2,$0,SC_Halt syscall j

8.

$31 Halt

.end

即Halt系统调用

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