NachOS Trace code 筆記

概略

github repos 在此

repos 已經更新過了，這份筆記提到的 code 是在 commit Add TraceCode Note

code 全放在 code 資料夾

Makefile 也推薦高速掃過看一下

最後的章節會以執行流程的方式紀錄整個執行過程，追蹤 userprog/nachos

並會統整一些架構出來，放在中間的章節

Debug

初始化在 threads/main.cc

用參數 -d 設定的字串創造一個 Debug Obj

Debug Class 定義於 lib/debug.h

假設 -d 設定為 ti(e.g. ./userprog/nachos -e test/test2 -d ti)

那 Debug Class 的 enableFlags 會是字串 ti

接著在整個專案的任意處寫類似以下的語句:

DEBUG(dbgThread, "My debug message")

DEBUG 是一個 macro，也定義在 lib/debug.h，會去看 dbgThread 代表的字元 t (同樣也寫在 lib/debug.h) 是否有在剛剛 -d 設定的字串中，有就輸出 My debug message

吃 CLI 參數

看 Trace3

Trace

以下 Trace 在 code 底下執行 ./userprog/nachos -e test/test1 的過程

Trace1

進入點為 threads/main.cc

這裡也設定了 Debug 物件，詳細請看Debug

接著 call kernel = new KernelType(argc, argv);，KernelType 是一個 Macro，定義在 threads/main.h，會根據 define 了以下 symbol 做不一樣的行為

NETWORK
USER_PROGRAM
兩者都沒設

現在來追看看到底什麼 symbol 有被 define

Trace2

因為我們追蹤的是 userprog/nachos，看一下 userprog/Makefile，以下 focus 在跟 define 有關的部分

userprog/Makefile 中有一行

DEFINES = -DTHREADS -DUSER_PROGRAM -DFILESYS_NEEDED -DFILESYS_STUB

再往下一點有兩行

include ../Makefile.common
include ../Makefile.dep

Makefile.common 裡有一行

CFLAGS = -g -Wall $(INCPATH) $(DEFINES) $(HOST) -DCHANGED

Makefile.dep 只有這樣

# CPU = x86, OS = linux
HOST = -Dx86 -DLINUX -DBSD
DISASM = disasm

對於 Makefile 的 = 跟 := 兩個指派運算子的觀念可以看看這篇文，簡單來說，= 是會到要用到的時候才會展開

而 CFLAGS 是 compile 時，會餵給 compiler 吃的參數

最後整個 CFLAGS 是 -g -Wall $(INCPATH這個我們先不考慮) -DTHREADS -DUSER_PROGRAM -DFILESYS_NEEDED -DFILESYS_STUB -Dx86 -DLINUX -DBSD -DCHANGED

這些參數會使 compiler 在 compile 時預先 define

THREADS
USER_PROGRAM
FILESYS_NEEDED
FILESYS_STUB
x86
LINUX
BSD
CHANGED

因為 define 了 USER_PROGRAM，所以前面 Trace1 的 main.h 會 define KernelType 為 UserProgKernel

Trace3

在 threads/main.cc 中執行 kernel = new KernelType(argc, argv);，實際上是創造 UserProgKernel 物件

UserProgKernel 實作於 userprog/userkernel.cc，會先執行父類別 ThreadedKernel 的 Constructor

ThreadedKernel 實作於 threads/kernel.cc，設定 randomSlice = FALSE;會在後續創造 Alarm obj 時用到

回到 UserProgKernel，吃到參數 -e，將 execfile[0] 設為 test/test1，execfileNum 為 1

可以看到 UserProgKernel 的 Constructor 只是吃吃參數而已，真正有做些初始化是在後面

Trace4

在 threads/main.cc 中執行 kernel->Initialize();

執行 userprog/userkernel.cc 中的UserProgKernel::Initialize()

UserProgKernel::Initialize() 會執行

ThreadedKernel::Initialize()
- 請看 Trace4_Init_ThreadedKernel
machine = new Machine(debugUserProg);
- 請看 Trace4_Init_Machine
fileSystem = new FileSystem();
- 請看 Trace4_Init_FileSystem

Trace4_Init_ThreadedKernel

執行 threads/kernel.cc 中的ThreadedKernel::Initialize()

ThreadedKernel::Initialize() 會執行

stats = new Statistics();
- Statistics::Statistics() 實作於 machine/stats.cc 中
- 此元件掌管 Tick Counters 跟其他數據統計
interrupt = new Interrupt;
- Interrupt::Interrupt() 實作於 machine/interrupt.cc 中
- 主要模擬硬體中斷的元件
- 初始化一些 member
  - level = IntOff;
    - disable 中斷
  - pending = new SortedList<PendingInterrupt *>(PendingCompare);
    - 初始化 Pending list
      - 裡面會存放著中斷，後續會再追到
  - inHandler = FALSE;
    - 還未在處裡中斷
  - yieldOnReturn = FALSE;
    - 還沒要進行 context switch
  - status = SystemMode;
    - 正在 kernel mode
scheduler = new Scheduler(type);
- Scheduler::Scheduler(SchedulerType type) 實作於 threads/scheduler.cc 中
- CPU Scheduler
- 初始化 blockedList、readyList
alarm = new Alarm(randomSlice);
- Alarm::Alarm(bool doRandom) 實作於 threads/alarm.cc 中
- 設定 Timer 物件，randomSlice 為 False
- 請看 Trace4_Timer
currentThread = new Thread("main");
- Thread::Thread(char* threadName) 實作於 threads/threads.cc 中
- 初始化大部分參數為 NULL，還需要 call Thread::Fork()
currentThread->setStatus(RUNNING);
- 直接設 main thread 的 status 為 RUNNING
interrupt->Enable();
- 實作於 machine/interrupt.h，直接 call Interrupt::SetLevel(IntOn);
- 中斷元件從不接受中斷改變狀態為接受中斷，會 call 一次 Interrupt::OneTick()
- 請看 Trace4_OneTick()

Trace4_Timer

Timer::Timer(bool doRandom, CallBackObj *toCall) 實作於 machine/timer.cc 中

將 callPeriodically 設定為 toCall

並呼叫 Timer::SetInterrupt()

Timer::SetInterrupt() 中，若 Timer 為 Enable，則呼叫 Interrupt::Schedule
創造一個 PendingInterrupt 物件，紀錄著

什麼要被 call: this Timer
何時要被 call: delay，也就是 TimerTicks
中斷類型: TimerInt

並插入到 Pending list

Trace4_OneTick()

Interrupt::OneTick() 實作於 machine/interrupt.cc

Trace 到此時，還在 kernel mode，totalTicks 會加上 SystemTick
(各種 Ticks 定義在 machine/stats.h 中)

先禁止接受中斷後執行

CheckIfDue(FALSE);
Interrupt::CheckIfDue(bool advanceClock) 簡單來說是檢查 Pending list 有無已經到達預定執行時間的中斷要做，有就呼叫此中斷的 Callback，再呼叫中斷的 Callback 的期間，將 inHandler 設為 True，表示正在處理中斷，回傳值的狀況分為以下狀況
- Pending List 為空，沒有任何中斷要做
  - Return false
- 下一個中斷要處理的時間還沒到，且 advanceClock 為 False
  - Return false
  - 此 function 原本行為是下一個中斷要處理的時間還沒到的話，會快轉到下一個要中斷要處理的時間，但若 advanceClock 為 false，表示告訴這個 function 先不要快轉
- 其餘狀況皆 return true
由於 Pending List 中已經有一個 TimerInt 的中斷，時間還沒到，應該要快轉，但 advanceClock 設 false，所以回傳 false

處理完中斷後，重新開啟接受中斷

看看有無要進行 content switch，有則執行 kernel->currentThread->Yield();不過 Trace 到目前為止是還不會需要 content switch 的。

Trace4_Init_Machine

Machine::Machine(bool debug) 實作於 machine/machine.cc，debug 參數為 false，簡單來說，就是初始化機器的暫存器為 0，清空 mainMemory

Trace4_Init_FileSystem

FileSystem::FileSystem(bool format) 實作於 filesys/filesys.cc，format 預設為 true，這個就先不深追

Trace5

在 threads/main.cc 中執行

CallOnUserAbort(Cleanup); //設定按下 ctrl+c 就 call `Cleanup`

kernel->SelfTest(); // 不是很重要，For debugging
kernel->Run(); // 繼續追蹤這個 function call

main 到此告一段落，Control flow 移轉到 kernel->Run()

Trace6

UserProgKernel::Run() 首先一個 for 迴圈，為每支 userprogram 建立 Thread、分配 AddrSpace，並且執行 Fork

本例子是執行

t[n] = new Thread("test/test1");
t[n]->space = new AddrSpace();
t[n]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[n]);

最後執行 ThreadedKernel::Run();

t[n] = new Thread("test/test1");
- 初始化大部分參數為 NULL，thread status 為 JUST_CREATED
t[n]->space = new AddrSpace();
- AddrSpace::AddrSpace() 實作於 userprog/addrspace.cc
- 目前 pageTable 直接將 virtual address 映射為 physical address
t[n]->Fork((VoidFunctionPtr) &ForkExecute, (void *)t[n]);
- 首先呼叫 StackAllocate(func, arg); 分配一塊 stack
  - 請看 Trace6_StackAllocate
- 將 thread 放到 ready list
  - thread status 變成 READY

Trace6_StackAllocate

Thread::StackAllocate (VoidFunctionPtr func, void *arg)首先執行

stack = (int *) AllocBoundedArray(StackSize * sizeof(int));

AllocBoundedArray(StackSize * sizeof(int)) 實作於 lib/sysdep.cc

首先 call getpagesize() 取得一個 page 多大
創造 pgSize * 2 + size 的空間
將頭尾 2 頁設為不可 rwx
- 這 2 個 page 是為了偵測有無發生 stack overflow
最後 return 實際可用的第 2 頁位址

回到 Thread::StackAllocate，接下來會根據不同架構做不一樣的事情，在 Trace2 我們知道有 define x86，所以會執行

stackTop = stack + StackSize - 4;
*(--stackTop) = (int) ThreadRoot;
*stack = STACK_FENCEPOST;

machineState[PCState] =(void *)ThreadRoot;
machineState[StartupPCState] = (void *)ThreadBegin;
machineState[InitialPCState] = (void *)func;
machineState[InitialArgState] = (void *)arg;
machineState[WhenDonePCState] = (void *)ThreadFinish;

PCState、StartupPCState 那些 define 在 threads/switch.h

#define PCState         (_PC/4-1)
#define FPState         (_EBP/4-1)
#define InitialPCState  (_ESI/4-1)
#define InitialArgState (_EDX/4-1)
#define WhenDonePCState (_EDI/4-1)
#define StartupPCState  (_ECX/4-1)

詳細機制後面會再提

stack 位址是 from high to low，所以將 stackTop 移動到這塊記憶體的最高記憶體位址
將 ThreadRoot push 上去
將 stack 最底設為 STACK_FENCEPOST，用來偵測有無 overflow
- STACK_FENCEPOST 只是一個 const int 0xdedbeef
  - 定義於 threads/thread.cc
- ThreadRoot 先定義於 threads/thread.h
  - 實作於 threads/switch.s
設定一些初始的 Register
- 例如將 machineState[PC] 設定為 ThreadRoot
- 後續會詳談，這邊留個印象就好

目前為止 thread test/test1 的 stack 上的資料大概像

Trace7

回到 UserProgKernel::Run()，for 迴圈跑完後執行 ThreadedKernel::Run();

ThreadedKernel::Run() 裡頭執行 currentThread->Finish();

currentThread 為在 Trace4_Init_ThreadedKernel 設定的 main

Thread main 的 Thread::Finish 執行了

首先關閉接收中斷
呼叫 Sleep(TRUE)

Thread main 的 Thread::Sleep (bool finishing) 執行了

將 thread main status 設為 BLOCKED
尋找下一個在 ready list 的 thread
- 找到 test/test1
執行 nextthread
- 執行 kernel->scheduler->Run(Thread test/test1, TRUE);

Scheduler::Run (Thread test/test1, TRUE) 執行了

將 toBeDestroyed 設為 main
呼叫 thread main 的 CheckOverflow
- 檢查 stack 上是否為 STACK_FENCEPOST
將 kernel->currentThread 設為 thread test/test1
將 thread test/test1 status 設為 RUNNING
執行 SWITCH(main, test/test1)
- 請看 Trace7_SWITCH
執行 CheckToBeDestroyed()
- Delete thread main
  - thread main 的 stack 應該於 SWITCH 中被清除

Trace7_SWITCH

void SWITCH(Thread *oldThread, Thread *newThread);

定義於 threads/thread.h
實作於 threads/switch.s

在 Trace2 我們知道 define 了 x86，所以 switch.s 中的 SWITCH code 為

        .comm   _eax_save,4
        .globl  SWITCH
SWITCH:
        movl    %eax,_eax_save          # save the value of eax
        movl    4(%esp),%eax            # move pointer to t1 into eax
        movl    %ebx,_EBX(%eax)         # save registers
        movl    %ecx,_ECX(%eax)
        movl    %edx,_EDX(%eax)
        movl    %esi,_ESI(%eax)
        movl    %edi,_EDI(%eax)
        movl    %ebp,_EBP(%eax)
        movl    %esp,_ESP(%eax)         # save stack pointer
        movl    _eax_save,%ebx          # get the saved value of eax
        movl    %ebx,_EAX(%eax)         # store it
        movl    0(%esp),%ebx            # get return address from stack into ebx
        movl    %ebx,_PC(%eax)          # save it into the pc storage

        movl    8(%esp),%eax            # move pointer to t2 into eax

        movl    _EAX(%eax),%ebx         # get new value for eax into ebx
        movl    %ebx,_eax_save          # save it
        movl    _EBX(%eax),%ebx         # retore old registers
        movl    _ECX(%eax),%ecx
        movl    _EDX(%eax),%edx
        movl    _ESI(%eax),%esi
        movl    _EDI(%eax),%edi
        movl    _EBP(%eax),%ebp
        movl    _ESP(%eax),%esp         # restore stack pointer
        movl    _PC(%eax),%eax          # restore return address into eax
        movl    %eax,4(%esp)            # copy over the ret address on the stack
        movl    _eax_save,%eax

        ret

(AT&T 語法的組語, src在左, dst在右)

對應 SWITCH(main, test/test1) 的組合語言是

push Thread * test/test1
push Thread * main
call SWITCH

所以執行 nachos 的主機的 stack 上會長這樣

解釋 SWITCH 做的事情

        movl    %eax,_eax_save

先將 eax 的值存到 _eax_save

        movl    4(%esp),%eax            # move pointer to t1 into eax
        movl    %ebx,_EBX(%eax)         # save registers
        movl    %ecx,_ECX(%eax)
        movl    %edx,_EDX(%eax)
        movl    %esi,_ESI(%eax)
        movl    %edi,_EDI(%eax)
        movl    %ebp,_EBP(%eax)
        movl    %esp,_ESP(%eax)         # save stack pointer

這邊要配合 switch.h 看，switch.h 有一段 code 如下

#define _ESP     0
#define _EAX     4
#define _EBX     8
#define _ECX     12
#define _EDX     16
#define _EBP     20
#define _ESI     24
#define _EDI     28
#define _PC      32

還要配合 Thread Class 前半段的定義

class Thread {
private:
    // NOTE: DO NOT CHANGE the order of these first two members.
    // THEY MUST be in this position for SWITCH to work.
    int *stackTop;			 // the current stack pointer
    void *machineState[MachineStateSize];  // all registers except for stackTop

Thread * test/test1 + 0 就會存取到 stackTop
Thread * test/test1 + 4 就會存取到 machineState[0]
Thread * test/test1 + 8 就會存取到 machineState[1]
以此類推

將 eax 的值改為 esp + 4，也就是 Thread * main
將 ebx 存到 [eax + _EBX]，也就是 [eax + 8]，也就是 Thread * main 的 machineState[1]，之後以 machineState[EBX] 形式表示
以此類推
其中，_ESP 為 0，所以改 machineState[ESP] 實際上是改 Thread class 裡的 stackTop

        movl    _eax_save,%ebx
        movl    %ebx,_EAX(%eax)

將剛剛存的 eax 放到 ebx
存放到 Thread * main 的 machineState[EAX]

        movl    0(%esp),%ebx
        movl    %ebx,_PC(%eax)

將 call 完 SWITCH 後要回去的 return address 放到 Thread * main 的 machineState[PC]

到目前為止存好了 Thread * main (oldThread) 各個暫存器的值

esp 為:
PC 為 Return address
- 為 call 完 SWITCH 後的下一個指令位址

        movl    8(%esp),%eax

存取 Thread * test/test1

        movl    _EAX(%eax),%ebx         # get new value for eax into ebx
        movl    %ebx,_eax_save          # save it
        movl    _EBX(%eax),%ebx         # retore old registers
        movl    _ECX(%eax),%ecx
        movl    _EDX(%eax),%edx
        movl    _ESI(%eax),%esi
        movl    _EDI(%eax),%edi
        movl    _EBP(%eax),%ebp
        movl    _ESP(%eax),%esp         # restore stack pointer

將 Thread * test/test1 紀錄的各個暫存器的值恢復
將 eax 先存到 _eax_save
以此類推
其中，取出 _ESP(%eax) 實際上是取出 Thread * test/test1 的 stackTop
- 複習這張圖
- 所以現在機器上的 esp 會指向這一塊記憶體

        movl    _PC(%eax),%eax          # restore return address into eax
        movl    %eax,4(%esp)            # copy over the ret address on the stack
        movl    _eax_save,%eax
        
        ret

將 Thread * test/test1 的 Program Counter 放到 return address
恢復 eax
return，從 esp pop return address 到 PC，也就是跳轉到 ThreadRoot 上，所以現在 stack 長這樣

(pop 只會取值出來放到暫存器，並將 esp + 4，並不會改動值)

Trace8

現在要跳轉到 Thread test/test1 的 Program counter 上

可以回顧 Trace6_StackAllocate，Thread test/test1 machineState[PC] 是 ThreadRoot 的位址

所以 Control flow 現在會跑到 ThreadRoot 上執行

void ThreadRoot()

定義於 threads/thread.h
實作於 threads/switch.s

code 如下

        .globl  ThreadRoot

/* void ThreadRoot( void )
**
** expects the following registers to be initialized:
**      eax     points to startup function (interrupt enable)
**      edx     contains inital argument to thread function
**      esi     points to thread function
**      edi     point to Thread::Finish()
*/
ThreadRoot:
        pushl   %ebp
        movl    %esp,%ebp
        pushl   InitialArg
        call    StartupPC
        call    InitialPC
        call    WhenDonePC

        # NOT REACHED
        movl    %ebp,%esp
        popl    %ebp
        ret

ebp 值初始為 0，push 上去後將 esp 的值放到 ebp
pushl InitialArg
call StartupPC，會 push 下一個指令位址

StartupPC 定義在 threads/switch.h，就是 %ecx

在剛剛的 SWITCH 中，%ecx 的值設定為 Thread * test/test1 的 machineState[ECX]

而 Thread * test/test1 的 machineState[ECX] 的值在 Trace6_StackAllocate 中有設定

machineState[StartupPCState] = (void *)ThreadBegin;

所以現在會呼叫 ThreadBegin

static void ThreadBegin() 實作於 threads/thread.cc

static void ThreadBegin() { kernel->currentThread->Begin(); }

kernel->currentThread 現在為 Thread test/test1

所以會呼叫到 Thread test/test1 的 Begin()

Thread::Begin() 執行

kernel->scheduler->CheckToBeDestroyed();
- Thread * main 在此被砍掉
kernel->interrupt->Enable();
- void Enable() { (void) SetLevel(IntOn); }
- Interrupt::SetLevel(IntStatus now) 中斷從關閉到打開，會 call 一次 OneTick()

Interrupt::OneTick() 執行

還在 SystemMode，計數 sysmtemTicks
關閉中斷
執行 CheckIfDue(FALSE);
- pending list 有元件，但時間未到，又 advanceClock 為 False，故回傳 false
開啟中斷
yieldOnReturn 為 false，不會做事

執行完了 return，從 stack pop 出 return address 到 PC，執行call InitialPC，會 push 下一個要執行的指令

InitialPC 定義在 threads/switch.h，就是 %esi

在剛剛的 SWITCH 中，%esi 的值設定為 Thread * test/test1 的 machineState[ESI]

而 Thread * test/test1 的 machineState[ESI] 的值在 Trace6_StackAllocate 中有設定

machineState[InitialPCState] = (void *)func;

func 為 ForkExecute，所以現在會呼叫 ForkExecute(Thread *t)

實作於 userprog/userkernel.cc
Thread * t 這第一個參數為 esp + 4 的 InitialArg，此時回頭追一下 InitialArg 是什麼
- 在 Trace6 可以看到 Fork 的 arg 是 t[n]
- 進一步在 Trace6_StackAllocate 可以看到
```
machineState[InitialArgState] = (void *)arg;
```
- 所以 InitialArg ，也就是t，是 Thread test/test1
ForkExecute(Thread *t) 執行 t->space->Execute(t->getName());

執行 Thread test/test1 的 space->Execute("test/test1")

AddrSpace::Execute(char *fileName) 實作於 userprog/addrspace.cc，執行了

Load(fileName)
- 將主機(Linux)上的檔案讀進 kernel->machine->mainMemory
this->InitRegisters()
- 裡頭用到的 NumTotalRegs 是定義於 machine/machine.h，為 user program 能用的 CPU registers
- 將 kernel->machine 的所有 registers 先填為 0
  - 包含將 kernel->machine 的 PC register 寫為 0 (user program 的 start，也就是 entry point，要放在 memory address 0)
- 將 kernel->machine 的 NextPC register 寫為 4
- 將 kernel->machine 的 StackReg 寫為最高位址
this->RestoreState()
- 將 kernel->machine 的 pageTable 改為此 Thread 的 AddrSpace 的 pageTable
kernel->machine->Run()
- 定義於 machine/machine.h
- 實作於 machine/mipssim.cc
- 實際上 NachOS 以 MIPS 架構模擬執行 user program 的 function
- 請看下一章節

Trace8_Machine::Run

執行以下事情









nstruction *instr = new Instruction;

kernel->interrupt->setStatus(UserMode);
for (;;) {
    OneInstruction(instr);
    kernel->interrupt->OneTick();
    if (singleStep && (runUntilTime <= kernel->stats->totalTicks))
        Debugger();
}

首先，class Instruction 只是一個用來存放指令的結構
將 kernel->interrupt 設為 UserMode
接下來是無限迴圈
- 執行 OneInstruction
  - 請看 Trace8_OneInstruction
- 執行 kernel->interrupt->OneTick()
  - 請看 Trace8_OneTick
- 下面的 if 是如果有開啟 debug 選項，要求逐行動態 debug
  - 本例沒有啟用

Trace8_OneInstruction

定義於 machine/machine.h
實作於 machine/mipssim.cc

這邊沒有認真追完，但看個大概還是能看得出來執行了什麼

ReadMem(registers[PCReg], 4, &raw)

實作於 machine/translate.cc
從 PCReg 讀一條指令(MIPS 指令皆為 4 bytes)

instr->value = raw;
instr->Decode();

翻譯指令

int pcAfter = registers[NextPCReg] + 4;

先記著 NextPC

switch (instr->opCode)
{
    case OP_xxx:
    ...
    ...
}

依照是什麼指令，選擇要做什麼事情
- 就是一個典型 Virtual Machine
- 其中 OP_SYSCALL 會執行 RaiseException(SyscallException, 0);
  - 請看 Trace8_RaiseException
- 有一些指令會更改 nextLoadReg、nextLoadValue，在待會的DelayedLoad(nextLoadReg, nextLoadValue); 會用到

DelayedLoad(nextLoadReg, nextLoadValue);

執行 registers[registers[LoadReg]] = registers[LoadValueReg];
設定 registers[LoadReg] = nextReg
設定 registers[LoadValueReg] = nextValue;

統整來說，call 了 DelayedLoad(MyReg1, MyValue1);，並不會馬上將 MyValue1 存到 Register MyReg1 上，而是要等下次再 call 到這個 function 才會存過去 (所以叫做 DelayedLoad)

大概猜想創造這個 function 是為了完成 MIPS 的指令，這裡我的猜想極可能有誤

registers[PrevPCReg] = registers[PCReg];
registers[PCReg] = registers[NextPCReg];
registers[NextPCReg] = pcAfter;

更新跟 PC 有關的 Register

Trace8_RaiseException

Machine::RaiseException(ExceptionType which, int badVAddr)

定義於 machine/machine.h
實作於 machine/machine.cc

當執行 user 的 MIPS 程式時，若有 call syscall 或有其他狀況，都會觸發這個 function (寫在 Trace8_OneInstruction 中)

執行了以下事情

registers[BadVAddrReg] = badVAddr;
- 透過 virtual machine 暫存器傳遞參數
DelayedLoad(0, 0);
- 將還沒 Load 的東西 Load 好
kernel->interrupt->setStatus(SystemMode);
- 陷入 SystemMode (KernelMode)
ExceptionHandler(which);
- 執行對應要做的事情
kernel->interrupt->setStatus(UserMode);
- 回到 UserMode

ExceptionHandler(ExceptionType which)

實作於 userprog/exception.cc
這邊就是可以自訂 exception、syscall 的地方了
因為之前完成過自訂 syscall 的作業，對這邊算熟悉，就不細講這邊，這邊不懂的人請另找跟寫 syscall 相關的文章，應該有所幫助

Trace8_OneTick

Interrupt::OneTick()

實作於 machine/interrupt.cc
此時的 OneTick 為 UserMode

在此整理一下 OneTick 被 call 的狀況
第一次 UserMode OneTick 之前會歷經三次 SystemMode OneTick

第一次 SystemMode OneTick
- 在 ThreadedKernel->Initialize() 開啟接受中斷，進而呼叫到
第二次 SystemMode OneTick
- 在 UserProgKernel->Run() 初始化 user program，呼叫到 Fork 時，將 thread 放進 readylist 時有關開一次中斷，進而呼叫到
第三次 SystemMode OneTick
- SWITCH 過後，執行每個 user thread 都會先執行的 Thread::Begin()，裡頭有將中斷開啟，進而呼叫到

在此例中，若後面加上 debug flag -d i，可以看到前三個 Ticks 是一次跳 10，後面則一次跳 1，是因為設定在 machine/stats.h 中的 SystemTick 為 10，UserTick 為 1，而前三次 Ticks 是在 SystemMode 運行，後面的 Ticks 是在 UserMode

Trace9

這邊高速 Trace 一下，以 debug 資訊為輔助

在執行 nachos 的指令後面加上 -d i，可以看到跟 interrupt 有關的 debug 資訊

這邊小小複習一下 Trace8_Machine::Run

裡頭的無限迴圈做的事情就是

執行一行 user program (MIPS) 的指令
- 其中指令有可能會 RaiseException 進而陷入 SystemMode 執行 syscall
call 一次 kernel->interrupt->OneTick()
- 每次 OneTick 就會
  - 增加 Ticks 數
  - 檢查 pending list 有無到期的中斷要執行
  - 若 yieldOnReturn 為 True，則要多做一些事
    - 請看 Trace9_yieldOnReturn

還有整個程式執行完後的部分也還未追到

請看 Trace10_Halt

Trace9_yieldOnReturn

在初始化時，有創造 Timer，並且有註冊在未來 TimerTicks 過後要執行 Timer 的 callback

可以回顧 Trace4_Timer
TimerTicks 定義在 machine/stats.h，為 100
初始化時 totalTicks 為 0，所以這次註冊是註冊在 totalTicks 為 100 時會執行 Timer 的 callback

在剛剛的 Trace9，在無限迴圈時會一直 call OneTick

因為是 UserMode，所以 totalTicks 一次加 UserTick

UserTick 定義在 machine/stats.h，為 1

當 totalTicks 來到 100 時，Interrupt::OneTick() 的執行流程是

執行 CheckIfDue(FALSE);，裡頭執行了
- next = pending->Front();
  - 抓取到 Timer 中斷，且現在為要處理這個中斷的時間點
- kernel->machine->DelayedLoad(0, 0);
  - 將先前有設定要 DelayedLoad 的值正式 load 進去
- inHandler = TRUE; 設定正在處理中斷
- 進入 while 迴圈，處理每個到期的中斷
  - next = pending->RemoveFront();
    - 從 pending list 抓取第一個出來處理
  - next->callOnInterrupt->CallBack();
    - 呼叫 Timer->CallBack()
      - 進一步呼叫 Alarm->CallBack()
        
        若在 IdleMode、Pending list 中沒有其他未來要處理的中段，且符合一些其他條件，則關閉 Timer
        
        若符合某些條件，則呼叫 interrupt->YieldOnReturn();
      - 呼叫 SetInterrupt();，若 Timer 沒被 disable，則設定在未來 100 個 Tick 後要再一次執行 Timer 中斷
- inHandler = FALSE; 設定沒在處理中斷
若 yieldOnReturn 為 True
- 先將 yieldOnReturn 設為 False
- status 進入 SystemMode
- 執行 kernel->currentThread->Yield(); 準備讓出 CPU
  - 請看 Trace9_yield
- status 回到原本的 Mode

所以整個流程可以理解為

下一個 Timer 時間點到了之後，就要執行 Content switch

Trace9_yield

Thread::Yield() 執行的事情是

先關閉中斷
從 readylist 中找下一個要跑的 thread
- 如果 readylist 沒有 thread，就不做 content switch
- 如果有
  - 則執行 ReadyToRun() 把 oldThread 丟進 ready list
  - 再執行 kernel->scheduler->Run(nextThread, FALSE);
    - kernel->scheduler->Run 主要就是做 Content switch
將中斷設為原本的狀態

此例子只有一個 user program，所以這裡不會做 Content switch

Trace10_Halt

這邊在執行 nachos 的指令後面多加一個 flag -d ita，可以多看到跟 Interrupt、Thread、AddrSpace 有關的 debug 資訊

User program 最後會 call syscall SC_Exit

Function call stack:

Machine::Run -> OneInstruction -> RaiseException -> ExceptionHandler
switch case SC_Exit 執行了
- kernel->currentThread->Finish();

kernel->currentThread->Finish(); 執行了

關閉中斷
Sleep(TRUE) 永久睡去(其實就是死了)
- 設定此 thread status 為 BLOCKED
- While Ready list 沒有 thread
  - 呼叫 kernel->interrupt->Idle();
    - 設定系統進入 IdleMode
    - 檢查未來是否還有中斷沒處理
      - 有的，有一個 Timer 預計在 totalTicks 為 200 時執行
      - 將 Ticks 快轉
      - 呼叫 Timer 的 callback
        
        呼叫 Alarm 的 callback
        
        系統在 IdleMode，未來也沒有中斷了，將 Timer disable
        
        呼叫 Timer::SetInterrupt()
        
        Timer 已被 disable，什麼事都不會做
    - 設定系統進入 SystemMode
- Ready list 還是沒有 thread
  - 呼叫 kernel->interrupt->Idle();
    - 設定系統進入 IdleMode
    - 檢查未來是否還有中斷沒處理
      - 沒有
    - 呼叫 Halt() 進行關機