# OS 2020 HW2 Nachos Report
## Motivation
### System Call
先按照作業的說明操作，在製作sleep list的時候若能依照起床時間排序將會省事不少。
### CPU Scheduling
根據指示，若有實作多個scheduling，則應該要在`threads/main.cc`中設計可以提供選擇的功能。
***threads/main.cc*** :
```C++
...
int
main(int argc, char **argv)
{
int i;
char *debugArg = "";
// before anything else, initialize the debugging system
for (i = 1; i < argc; i++) {
if (strcmp(argv[i], "-d") == 0) {
ASSERT(i + 1 < argc); // next argument is debug string
debugArg = argv[i + 1];
i++;
} else if (strcmp(argv[i], "-u") == 0) {
cout << "Partial usage: nachos [-z -d debugFlags]\n";
} else if (strcmp(argv[i], "-z") == 0) {
cout << copyright;
}
}
debug = new Debug(debugArg);
DEBUG(dbgThread, "Entering main");
kernel = new KernelType(argc, argv);
kernel->Initialize();
CallOnUserAbort(Cleanup); // if user hits ctl-C
kernel->SelfTest();
kernel->Run();
return 0;
}
```
從這邊可以看到debug flag的選擇以及其他執行選項的選擇都在此處理，因此將scheduling的選擇也放在此處理感覺是個合理的選項。至於如何把選擇的結果傳給`scheduler`則是另一個問題。這邊先看到`debug`是一個明顯的選擇後傳遞資訊的部分，這是利用一個全域變數在做資訊的傳遞，因為`debug`的顯示部分相對其他結構是比較獨立的，所以在這邊並沒有太大的問題。但如果傳遞資訊給`scheduler`也使用這種方法可能就造成全域變數的混亂，因此感覺最有可能的方式是透過`kernel->Initialize()`帶入參數。修改`/threads/main.cc`
***main.cc*** :
```C++
...
int
main(int argc, char **argv)
{
int i;
char *debugArg = "";
SchedulerType scheType = RR;
// before anything else, initialize the debugging system
for (i = 1; i < argc; i++) {
if (strcmp(argv[i], "-d") == 0) {
ASSERT(i + 1 < argc); // next argument is debug string
debugArg = argv[i + 1];
i++;
} else if (strcmp(argv[i], "-u") == 0) {
cout << "Partial usage: nachos [-z -d debugFlags]\n";
} else if (strcmp(argv[i], "-z") == 0) {
cout << copyright;
} else if (strcmp(argv[i], "-sche") == 0) {
ASSERT(i + 1 < argc); // next argument is scheduler type string
if (strcmp(argv[i + 1], "RR") == 0) {
cout << "Using Round Robin now." << endl;
scheType = RR;
} else if (strcmp(argv[i + 1], "FCFS") == 0) {
cout << "Using First-Come-First-Service now." << endl;
scheType = FCFS;
} else if (strcmp(argv[i + 1], "SJF") == 0) {
cout << "Using Shortest-Job-First now." << endl;
scheType = SJF;
} else if (strcmp(argv[i + 1], "Priority") == 0) {
cout << "Using Priority now." << endl;
scheType = PRIORITY;
} else {
cout << "No matching scheduler type! Using Round Robin by default.\n";
scheType = RR;
}
i++;
}
}
debug = new Debug(debugArg);
DEBUG(dbgThread, "Entering main");
kernel = new KernelType(argc, argv);
kernel->Initialize(scheType);
CallOnUserAbort(Cleanup); // if user hits ctl-C
kernel->SelfTest();
kernel->Run();
return 0;
}
```
接著因為要實作Priority, SJF, FCFS的關係，必須給每個thread一個priority, CPU burst time, start time的欄位，在`threads/thread.h`中添加這些member以及他們的get, set method。這邊看到其實`Thread`裡面還有分成user code和kernel code的使用部分，我認為scheduling應該是屬於kernel code的部分，所以就沒有把這些欄位放在user program那區。
***threads/thread.h*** :
```C++
...
class Thread {
private:
...
public:
...
int getBurstTime() { return burstTime; }
int getSchePriority() { return schePriority; }
int getStartTime() { return startTime; }
void setBurstTime(int x) { burstTime = x; }
void setStartTime(int x) { startTime = x; }
void setSchePriority(int x) { schePriority = x; }
private:
...
int schePriority; // the execution priority for the thread
// the higher the more important
int burstTime; // the CPU burst time of the thread
int startTime; // the start time of the thread
#ifdef USER_PROGRAM
// A thread running a user program actually has *two* sets of CPU registers --
// one for its state while executing user code, one for its state
// while executing kernel code.
...
#endif
};
...
```
根據助教指示，在`threads/thread.cc`中的`Thread::SelfTest()`加上自己要測試的程式。
***thread.cc*** :
```C++
...
//----------------------------------------------------------------------
// SimulateTimeThread
// Simulate time running causing decrease of the thread's
// burst time.
//----------------------------------------------------------------------
static void
SimulateTimeThread()
{
Thread *t = kernel->currentThread;
while (t->getBurstTime() > 0) {
t->setBurstTime(t->getBurstTime() - 1); // CPU burst time decrease
cout << "*** thread " << t->getName() << ": remaining time " << t->getBurstTime() << endl;
kernel->interrupt->OneTick(); // simulate time (may
// cause context switch)
}
}
...
//----------------------------------------------------------------------
// Thread::SelfTest
// Set up a ping-pong between two threads, by forking a thread
// to call SimpleThread, and then calling SimpleThread ourselves.
//----------------------------------------------------------------------
void
Thread::SelfTest()
{
DEBUG(dbgThread, "Entering Thread::SelfTest");
const int thread_num = 3;
char *name[thread_num] = {"A", "B", "C"};
int priority[thread_num] = {7, 4, 6};
int burst[thread_num] = {5, 19, 3};
int start[thread_num] = {1, 2, 3};
Thread *t;
int i = 0;
for (i = 0; i < thread_num; i ++) {
t = new Thread(name[i]);
t->setSchePriority(priority[i]);
t->setBurstTime(burst[i]);
t->setStartTime(start[i]);
t->Fork((VoidFunctionPtr) SimulateTimeThread, (void *)NULL);
}
}
...
```
## Implementation
### System Call
依照助教指示，在`userprog/syscall.h`之中定義`Sleep`的system call number。
***userprog/syscall.h*** :
```c++
...
#define SC_PrintInt 11
#define SC_Sleep 12 // tu added
...
/* OS HW2
* Let the thread sleep.
*/
void Sleep(int time); //tu add
...
```
再來是在`test/start.s`中準備register。
***test/start.s*** :
```assembly
...
.globl ThreadFork
.ent ThreadFork
ThreadFork:
addiu $2,$0,SC_ThreadFork
syscall
j $31
.end ThreadFork
.globl ThreadYield
.ent ThreadYield
ThreadYield:
addiu $2,$0,SC_ThreadYield
syscall
j $31
.end ThreadYield
.globl PrintInt
.ent PrintInt
PrintInt:
addiu $2,$0,SC_PrintInt
syscall
j $31
.end PrintInt
.globl Sleep
.ent Sleep
Sleep:
addiu $2,$0,SC_Sleep
syscall
j $31
.end Sleep
...
```
組合語言沒有特別研究，但前面的幾個都一樣就跟著做吧。
之後在`userprog/exception.cc`加入`Sleep`的Exception case。
***userprog/exception.cc*** :
```C++
...
case SC_PrintInt:
val=kernel->machine->ReadRegister(4);
cout << "Print integer:" <<val << endl;
return;
case SC_Sleep:
val=kernel->machine->ReadRegister(4);
cout << "Sleep for " << val << endl;
kernel->alarm->WaitUntil(val);
return;
...
```
一樣照抄上面的格式，然後根據助教的提示，利用`kernel->alarm->WaitUntil()`。
依照助教的說明，先看看這份`threads/alarm.h`的註解，裡面寫到此檔案並沒有被完全實作，因此去看看`threads/alarm.cc`，發現裡面只有實作constructer以及`CallBack()`。在開始動手之前，先想想運作情形，以及需要的東西。運作的時候可能會有很多的thread去睡覺，所以應該要有一個List儲存這些睡眠中的thread。而不同的thread起床時間也不一定相同，所以也需要儲存他們各自的起床時間。綜上所述，應該是要有一個class把thread跟他的起床時間包在一起，之後再丟進List裡面儲存。在interrupt的時候，必須要看是哪些thread該起床了，如果讓thread依照起床的時間排序感覺會比較容易實作，所以使用`lib/list.h`中的`SortedList`儲存。
***threads/alarm.h*** :
```C++
...
#include "thread.h"
...
private:
Timer *timer; // the hardware timer device
void CallBack(); // called when the hardware
// timer generates an interrupt
class SleepingThread {
public:
SleepingThread(Thread *t, int x);
Thread *sleepingT;
int wakeTime;
};
SortedList<SleepingThread *> *sleepSer;
static int SleepingCompare(SleepingThread *x,
SleepingThread *y);
};
...
```
***threads/alarm.cc*** :
```C++
...
//----------------------------------------------------------------------
// SleepingCompare
// Compare to sleeping threads based on which should wake up first.
//----------------------------------------------------------------------
int
SleepingCompare (Alarm::SleepingThread *x, Alarm::SleepingThread *y)
{
if (x->wakeTime < y->wakeTime) { return -1; }
else if (x->wakeTime > y->wakeTime) { return 1; }
else { return 0; }
}
//----------------------------------------------------------------------
// Alarm::Alarm
// Initialize a software alarm clock. Start up a timer device
//
// "doRandom" -- if true, arrange for the hardware interrupts to
// occur at random, instead of fixed, intervals.
//----------------------------------------------------------------------
Alarm::Alarm(bool doRandom)
{
timer = new Timer(doRandom, this);
// imitate the 'pending' in /code/machine/interrupt.cc Interrupt()
sleepSer = new SortedList<SleepingThread *>(SleepingCompare);
}
//----------------------------------------------------------------------
// Alarm::~Alarm
// De-allocate the data structures needed by the sleeping thread
// simulation, and release the timer.
// (imitate the '~Interrupt()' in /code/machine/interrupt.cc)
//----------------------------------------------------------------------
Alarm::~Alarm()
{
delete timer;
while (!sleepSer->IsEmpty()) {
delete sleepSer->RemoveFront();
}
delete sleepSer;
}
```
而`SortedList`的宣告及用法則是參考自`machine/interrupt.h`以及`machine/inerrupt.cc`之中`pending`相關的宣告以及method。
***machine/interrupt.h*** :
```C++
...
SortedList<PendingInterrupt *> *pending;
...
```
***machine/interrupt.cc*** :
```C++
...
//----------------------------------------------------------------------
// PendingCompare
// Compare to interrupts based on which should occur first.
//----------------------------------------------------------------------
static int
PendingCompare (PendingInterrupt *x, PendingInterrupt *y)
{
if (x->when < y->when) { return -1; }
else if (x->when > y->when) { return 1; }
else { return 0; }
}
//----------------------------------------------------------------------
// Interrupt::Interrupt
// Initialize the simulation of hardware device interrupts.
//
// Interrupts start disabled, with no interrupts pending, etc.
//----------------------------------------------------------------------
Interrupt::Interrupt()
{
level = IntOff;
pending = new SortedList<PendingInterrupt *>(PendingCompare);
inHandler = FALSE;
yieldOnReturn = FALSE;
status = SystemMode;
}
//----------------------------------------------------------------------
// Interrupt::~Interrupt
// De-allocate the data structures needed by the interrupt simulation.
//----------------------------------------------------------------------
Interrupt::~Interrupt()
{
while (!pending->IsEmpty()) {
delete pending->RemoveFront();
}
delete pending;
}
//----------------------------------------------------------------------
// Alarm::SleepingThread::SleepingThread
// Initializing the information of sleeping thread.
// Including the thread and its sleeping time.
//----------------------------------------------------------------------
Alarm::SleepingThread::SleepingThread(Thread *t, int x)
{
sleepingT = t;
wakeTime = x;
}
...
```
在實作`Waituntil(int x)`的時候遇到一個問題，這個傳入的參數應該是代表幾秒，還是代表interrupt的次數呢？從`interrupt.cc`之中的`SetInterrupt()`找到`TimerTicks`這種東西，同時也找到`Schedule(...)`這個看起來可以當作提示的method。所以接著看Schedule的實作以及註解。
***machine/interrupt.cc*** :
```C++
...
//----------------------------------------------------------------------
// Interrupt::Schedule
// Arrange for the CPU to be interrupted when simulated time
// reaches "now + when".
//
// Implementation: just put it on a sorted list.
//
// NOTE: the Nachos kernel should not call this routine directly.
// Instead, it is only called by the hardware device simulators.
//
// "toCall" is the object to call when the interrupt occurs
// "fromNow" is how far in the future (in simulated time) the
// interrupt is to occur
// "type" is the hardware device that generated the interrupt
//----------------------------------------------------------------------
void
Interrupt::Schedule(CallBackObj *toCall, int fromNow, IntType type)
{
int when = kernel->stats->totalTicks + fromNow;
PendingInterrupt *toOccur = new PendingInterrupt(toCall, when, type);
DEBUG(dbgInt, "Scheduling interrupt handler the " << intTypeNames[type] << " at time = " << when);
ASSERT(fromNow > 0);
pending->Insert(toOccur);
}
...
```
看起來`WaitUntil(int x)`的`x`到底代表的意義，在這個實作中可以得到回答。從這個實作中看起來，原作者的那個`x`代表的應該是tick，所以實作`WaitUntil(int x)`時的邏輯應該與`Schedule(...)`類似。在執行這個`WaitUntil(int x)`的時候比較要小心的事情是，不能讓這個method執行到一半被interrupt，這樣可能會錯過起床的時間，也可能導致起床的時間跟原本預期的不同。
***threads/alarm.cc*** :
```C++
...
//----------------------------------------------------------------------
// Alarm::WatiUntil
// Suspend execution until time > now + x
// This function should not be interrupted.
//----------------------------------------------------------------------
void
Alarm::WaitUntil(int x)
{
// make sure interrupts were disabled
IntStatus oriStat = kernel->interrupt->SetLevel(IntOff);
// get the current thread & calculate wake up time
Thread *currentT = kernel->currentThread;
int wakeTick = kernel->stats->totalTicks + x;
SleepingThread *st = new SleepingThread(currentT, wakeTick);
cout << "A thread goes to sleep." << endl;
// let the thread sleep, and put it to the sleeping series
sleepSer->Insert( st );
currentT->Sleep(false); // cannot reach the program after it?
// let the interrupt status as before
kernel->interrupt->SetLevel(oriStat);
}
...
```
至此，睡覺的功能好像做得差不多了，接著要開始做起床的功能，也就是`CallBack()`的部分了。
***threads/alarm.cc*** :
```C++
...
//----------------------------------------------------------------------
// Alarm::CallBack
// Software interrupt handler for the timer device. The timer device is
// set up to interrupt the CPU periodically (once every TimerTicks).
// This routine is called each time there is a timer interrupt,
// with interrupts disabled.
//
// Note that instead of calling Yield() directly (which would
// suspend the interrupt handler, not the interrupted thread
// which is what we wanted to context switch), we set a flag
// so that once the interrupt handler is done, it will appear as
// if the interrupted thread called Yield at the point it is
// was interrupted.
//
// For now, just provide time-slicing. Only need to time slice
// if we're currently running something (in other words, not idle).
// Also, to keep from looping forever, we check if there's
// nothing on the ready list, and there are no other pending
// interrupts. In this case, we can safely halt.
//----------------------------------------------------------------------
void
Alarm::CallBack()
{
Interrupt *interrupt = kernel->interrupt;
MachineStatus status = interrupt->getStatus();
// detect if any threads need to wake up
bool sleepFlag = true;
ListIterator<SleepingThread *> iter(sleepSer);
while(!iter.IsDone())
{
SleepingThread *st = iter.Item();
if (st->wakeTime <= kernel->stats->totalTicks)
{
sleepFlag = false;
cout << "Thread wake up." << endl;
kernel->scheduler->ReadyToRun(st->sleepingThread);
iter.Next();
sleepSer->Remove(st);
}
else { break; } // because sleepSer is sortedList
}
DEBUG(dbgTu, "# elements in sleep serial: " << sleepSer->NumInList())
if (status == IdleMode && sleepFlag && sleepSer->IsEmpty()) { // is it time to quit?
if (!interrupt->AnyFutureInterrupts()) {
timer->Disable(); // turn off the timer
}
} else { // there's someone to preempt
interrupt->YieldOnReturn(); // context switch
}
}
...
```
### CPU Scheduling
首先先修復在`/threads/main.cc`中修改函式行為所造成的問題。因為`kernel`之中的`Initialize(...)`這個method有了新的參數，因此要去`kernel`之中增加新的method。先觀察一下這個`kernel`的型別，發現他屬於`KernelType *`。而`KernelType`又在`/threads/main.h`之中有定義。
***threads/main.h*** :
```C++
...
#ifdef NETWORK // THREADS && USER_PROGRAM && NETWORK
#include "netkernel.h"
#define KernelType NetKernel
class NetKernel;
#else
#ifdef USER_PROGRAM // THREADS && USER_PROGRAM
#include "userkernel.h"
#define KernelType UserProgKernel
class UserProgKernel;
#else
#include "kernel.h" // THREADS
#define KernelType ThreadedKernel
class ThreadedKernel;
#endif
#endif
...
```
問題是只看`/threads/main.h`沒辦法知道到底是哪一個`Kernel`，所以我直接make，看error message應該就可以知道了。
***error message*** :
```
...
../threads/main.cc:99:32: error: no matching function for call to ‘ThreadedKernel::Initialize(SchedulerType&)’
kernel->Initialize(scheType);
^
../threads/main.cc:99:32: note: candidate is:
In file included from ../threads/main.h:25:0,
from ../threads/main.cc:21:
../userprog/userkernel.h:26:10: note: void ThreadedKernel::Initialize()
void Initialize(); // initialize the kernel -- separated
^
...
```
看來缺的是`ThreadedKernel::Initialize(...)`。
***threads/kernel.h*** :
```C++
...
class ThreadedKernel {
public:
ThreadedKernel(int argc, char **argv);
// Interpret command line arguments
~ThreadedKernel(); // deallocate the kernel
void Initialize(SchedulerType type);
void Initialize(); // initialize the kernel -- separated
// from constructor because
// refers to "kernel" as a global
...
```
***threads/kernel.cc*** :
```C++
...
//----------------------------------------------------------------------
// ThreadedKernel::Initialize
// Initialize Nachos global data structures. Separate from the
// constructor because some of these refer to earlier initialized
// data via the "kernel" global variable. (Bypassing the scheduler
// type)
//----------------------------------------------------------------------
void
ThreadedKernel::Initialize(SchedulerType type)
{
stats = new Statistics(); // collect statistics
interrupt = new Interrupt; // start up interrupt handling
scheduler = new Scheduler(type); // initialize the ready queue
alarm = new Alarm(randomSlice); // start up time slicing
// We didn't explicitly allocate the current thread we are running in.
// But if it ever tries to give up the CPU, we better have a Thread
// object to save its state.
currentThread = new Thread("main");
currentThread->setStatus(RUNNING);
interrupt->Enable();
}
...
```
實作照抄前人的方法，然後make看看有沒有問題。
***error message*** :
```
...
../threads/main.cc:99:32: error: no matching function for call to ‘UserProgKernel::Initialize(SchedulerType&)’
kernel->Initialize(scheType);
^
../threads/main.cc:99:32: note: candidate is:
In file included from ../threads/main.h:21:0,
from ../threads/main.cc:21:
../userprog/userkernel.h:26:10: note: void UserProgKernel::Initialize()
void Initialize(); // initialize the kernel
^
...
```
看來`UserProgKernel`也要改。
***userprog/userkernel.h*** :
```C++
...
class UserProgKernel : public ThreadedKernel {
public:
UserProgKernel(int argc, char **argv);
// Interpret command line arguments
~UserProgKernel(); // deallocate the kernel
void Initialize(SchedulerType type); // initialize the kernel
void Initialize(); // initialize the kernel
...
```
***userprog/userkernel.cc*** :
```C++
...
//----------------------------------------------------------------------
// UserProgKernel::Initialize
// Initialize Nachos global data structures.
//----------------------------------------------------------------------
void
UserProgKernel::Initialize()
{
ThreadedKernel::Initialize(); // init multithreading
machine = new Machine(debugUserProg);
fileSystem = new FileSystem();
#ifdef FILESYS
synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}
//----------------------------------------------------------------------
// UserProgKernel::Initialize
// Initialize Nachos global data structures.
//----------------------------------------------------------------------
void
UserProgKernel::Initialize(SchedulerType type)
{
ThreadedKernel::Initialize(type); // init multithreading
machine = new Machine(debugUserProg);
fileSystem = new FileSystem();
#ifdef FILESYS
synchDisk = new SynchDisk("New SynchDisk");
#endif // FILESYS
}
...
```
老樣子，實作照抄前人的方法。
***error message*** :
```
...
../threads/main.cc:99:32: error: no matching function for call to ‘NetKernel::Initialize(SchedulerType&)’
kernel->Initialize(scheType);
^
../threads/main.cc:99:32: note: candidate is:
In file included from ../threads/main.h:16:0,
from ../threads/main.cc:21:
../network/netkernel.h:26:10: note: void NetKernel::Initialize()
void Initialize(); // initialize the kernel
^
...
```
看起來compiler是每個都會檢查的樣子。
***/network/netkernel.h*** :
```C++
...
class NetKernel : public UserProgKernel {
public:
NetKernel(int argc, char **argv);
// Interpret command line arguments
~NetKernel(); // deallocate the kernel
void Initialize(SchedulerType type); // initialize the kernel
void Initialize(); // initialize the kernel
...
```
***/network/netkernel.cc*** :
```C++
...
//----------------------------------------------------------------------
// NetKernel::Initialize
// Initialize Nachos global data structures.
//----------------------------------------------------------------------
void
NetKernel::Initialize()
{
UserProgKernel::Initialize(); // init other kernel data structs
postOfficeIn = new PostOfficeInput(10);
postOfficeOut = new PostOfficeOutput(reliability, 10);
}
//----------------------------------------------------------------------
// NetKernel::Initialize
// Initialize Nachos global data structures.
//----------------------------------------------------------------------
void
NetKernel::Initialize(SchedulerType type)
{
UserProgKernel::Initialize(type); // init other kernel data structs
postOfficeIn = new PostOfficeInput(10);
postOfficeOut = new PostOfficeOutput(reliability, 10);
}
...
```
遵循古禮，make之後就沒有問題了。
接下來就是開始弄`Scheduler`的部分了。觀察`threads/thread.cc`中的`Thread::Yield()`以及`threads/scheduler.cc`中的`Scheduler::FindNextToRun ()`後，可以發現`Scheduler`決定thread執行的先後順序的方法，就是根據`Scheduler`的`readyList`中的thread順序。那也就是說只要把thread按照某些規則放進`readyList`中，就可以完成Priority, SJF, FCFS。而三者分別是根據priority, CPU burst time, start time的大小決定先後順序，看來該是`SortedList`出馬的時候了。
先在`threads/schdeduler.h`中宣告，然後在`threads/scheduler.cc`中實作後改寫`readyList`的內容。
***threads/schdeduler.h*** :
```C++
...
int PriorityCompare (Thread *a, Thread *b);
int SJFCompare (Thread *a, Thread *b);
int FCFSCompare (Thread *a, Thread *b);
...
```
***threads/schdeduler.cc*** :
```C++
...
Scheduler::Scheduler(SchedulerType type)
{
schedulerType = type;
switch(type)
{
case RR:
readyList = new List<Thread *>;
break;
case PRIORITY:
readyList = new SortedList<Thread *>(PriorityCompare);
break;
case SJF:
readyList = new SortedList<Thread *>(SJFCompare);
break;
case FCFS:
readyList = new SortedList<Thread *>(FCFSCompare);
break;
}
toBeDestroyed = NULL;
}
...
//----------------------------------------------------------------------
// PriorityCompare
// Compare to threads based on their priority.
//----------------------------------------------------------------------
int
PriorityCompare(Thread *a, Thread *b)
{
if (a->getPriority() == b->getPriority()) { return 0; }
else if (a->getPriority() > b->getPriority()) { return 1; }
else { return -1; }
}
//----------------------------------------------------------------------
// SJFCompare
// Compare to threads based on their CPU burst time.
//----------------------------------------------------------------------
int
SJFCompare(Thread *a, Thread *b)
{
if (a->getBurstTime() == b->getBurstTime()) { return 0; }
else if (a->getBurstTime() > b->getBurstTime()) { return 1; }
else { return -1; }
}
//----------------------------------------------------------------------
// FCFSCompare
// Compare to threads based on their start time.
//----------------------------------------------------------------------
int
FCFSCompare(Thread *a, Thread *b)
{
if (a->startTime() == b->startTime()) { return 0; }
else if (a->startTime() > b->startTime()) { return 1; }
else { return -1; }
}
...
```
## Result
### System Call
#### Experiment result
寫了兩支程式分別有不同的睡眠時間，`sleeptest1`的睡眠時間是`sleeptest2`的10倍，所以預計在`sleeptest1`起床的間隔中，`sleeptest2`會起床9~10次。無法確定的原因是因為，如果是多核心執行時，兩支程式在同一個tick進入睡眠，那`sleeptest1`起床的時間理論上會和`sleeptest2`在同一個tick，這就造成了我無法確定兩者的輸出順序。
***test/sleeptest1.c*** :
```C
#include "syscall.h"
int main()
{
int i = 0;
for ( i = 0; i < 5; i += 1)
{
Sleep(100000);
PrintInt(1);
}
return 0;
}
```
***test/sleeptest2.c*** :
```C
#include "syscall.h"
int main()
{
int i = 0;
for ( i = 0; i < 20; i += 1)
{
Sleep(10000);
PrintInt(2);
}
return 0;
}
```
輸入`./userprog/nachos -e ./test/sleeptest1 -e ./test/sleeptest2`
```
Total threads number is 2
Thread ./test/sleeptest1 is executing.
Thread ./test/sleeptest2 is executing.
Sleep for 100000
A thread goes to sleep.
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:1
Sleep for 100000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:2
Sleep for 10000
A thread goes to sleep.
Thread wake up.
Print integer:1
Sleep for 100000
A thread goes to sleep.
Thread wake up.
Print integer:2
return value:0
Thread wake up.
Print integer:1
Sleep for 100000
A thread goes to sleep.
Thread wake up.
Print integer:1
Sleep for 100000
A thread goes to sleep.
Thread wake up.
Print integer:1
return value:0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
Ticks: total 500600, idle 499441, system 550, user 609
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
```
#### 觀察
在debug的時候發現在中放在`currentT->Sleep(false);`這行程式後面的區域好像不會被執行到。會發現這件事情是因為執行未修改的程式(見下方)時，發現結果是thread沉沉睡去，沒有要醒來的意思，而且也沒有輸出`A thread goes to sleep.`這行文字。在把輸出資訊的那行移至Sleep上方後，輸出的結果就跑出來了。雖然輸出正常了，但是thread還是沒有起床的意思，因此推測可能是在`CallBack()`出問題了，但是看了看`sleepflag`的邏輯好像找不出錯誤，那會讓nachos結束的可能就只有`sleepSer.IsEmpty()`了。於是加上一行DEBUG檢查裡面到底有沒有東西，結果是真的沒有東西，那問題很明顯就出在`WaitUntil(int x)`中的`sleepSer->Insert( st )`，顯然是這行程式並沒有起作用，有了之前輸出消失的經驗，把`sleepSer->Insert( st );`換到`currentT->Sleep(false);`的上方還真的有用，接著就一切正常了。
***threads/alarm.cc*** :
```C++
...
//----------------------------------------------------------------------
// Alarm::WatiUntil
// Suspend execution until time > now + x
// This function should not be interrupted.
//----------------------------------------------------------------------
void
Alarm::WaitUntil(int x)
{
// make sure interrupts were disabled
IntStatus oriStat = kernel->interrupt->SetLevel(IntOff);
// get the current thread & calculate wake up time
Thread *currentT = kernel->currentThread;
int wakeTick = kernel->stats->totalTicks + x;
SleepingThread *st = new SleepingThread(currentT, wakeTick);
// let the thread sleep, and put it to the sleeping series
currentT->Sleep(false);
cout << "A thread goes to sleep." << endl;
sleepSer->Insert( st );
// let the interrupt status as before
kernel->interrupt->SetLevel(oriStat);
}
...
```
### CPU Scheduling
#### Experiment result
`Thread::SelfTest()`內容
```C++
...
char *name[thread_num] = {"A", "B", "C"};
int priority[thread_num] = {7, 4, 6};
int burst[thread_num] = {5, 19, 3};
int start[thread_num] = {1, 2, 3};
...
```
執行`./threads/nachos -sch RR`，結果如下
```
Using Round Robin now.
*** thread A: remaining time 4
*** thread A: remaining time 3
*** thread A: remaining time 2
*** thread B: remaining time 18
*** thread B: remaining time 17
*** thread B: remaining time 16
*** thread B: remaining time 15
*** thread B: remaining time 14
*** thread B: remaining time 13
*** thread B: remaining time 12
*** thread B: remaining time 11
*** thread B: remaining time 10
*** thread C: remaining time 2
*** thread C: remaining time 1
*** thread C: remaining time 0
*** thread A: remaining time 1
*** thread A: remaining time 0
*** thread B: remaining time 9
*** thread B: remaining time 8
*** thread B: remaining time 7
*** thread B: remaining time 6
*** thread B: remaining time 5
*** thread B: remaining time 4
*** thread B: remaining time 3
*** thread B: remaining time 2
*** thread B: remaining time 1
*** thread B: remaining time 0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
...
```
執行`./threads/nachos -sche SJF`，結果如下
```
Using Shortest-Job-First now.
*** thread C: remaining time 2
*** thread C: remaining time 1
*** thread C: remaining time 0
*** thread A: remaining time 4
*** thread A: remaining time 3
*** thread A: remaining time 2
*** thread A: remaining time 1
*** thread A: remaining time 0
*** thread B: remaining time 18
*** thread B: remaining time 17
*** thread B: remaining time 16
*** thread B: remaining time 15
*** thread B: remaining time 14
*** thread B: remaining time 13
*** thread B: remaining time 12
*** thread B: remaining time 11
*** thread B: remaining time 10
*** thread B: remaining time 9
*** thread B: remaining time 8
*** thread B: remaining time 7
*** thread B: remaining time 6
*** thread B: remaining time 5
*** thread B: remaining time 4
*** thread B: remaining time 3
*** thread B: remaining time 2
*** thread B: remaining time 1
*** thread B: remaining time 0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
...
```
執行`./threads/nachos -sche FCFS`，結果如下
```
user@user-VirtualBox:~/Documents/nachos/nachos-4.0/code$ ./threads/nachos -sche FCFS
Using First-Come-First-Service now.
*** thread A: remaining time 4
*** thread A: remaining time 3
*** thread A: remaining time 2
*** thread A: remaining time 1
*** thread A: remaining time 0
*** thread B: remaining time 18
*** thread B: remaining time 17
*** thread B: remaining time 16
*** thread B: remaining time 15
*** thread B: remaining time 14
*** thread B: remaining time 13
*** thread B: remaining time 12
*** thread B: remaining time 11
*** thread B: remaining time 10
*** thread B: remaining time 9
*** thread B: remaining time 8
*** thread B: remaining time 7
*** thread B: remaining time 6
*** thread B: remaining time 5
*** thread B: remaining time 4
*** thread B: remaining time 3
*** thread B: remaining time 2
*** thread B: remaining time 1
*** thread B: remaining time 0
*** thread C: remaining time 2
*** thread C: remaining time 1
*** thread C: remaining time 0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
...
```
執行`./threads/nachos -sche Priority`，結果如下
```
Using Priority now.
*** thread B: remaining time 18
*** thread B: remaining time 17
*** thread B: remaining time 16
*** thread B: remaining time 15
*** thread B: remaining time 14
*** thread B: remaining time 13
*** thread B: remaining time 12
*** thread B: remaining time 11
*** thread B: remaining time 10
*** thread B: remaining time 9
*** thread B: remaining time 8
*** thread B: remaining time 7
*** thread B: remaining time 6
*** thread B: remaining time 5
*** thread B: remaining time 4
*** thread B: remaining time 3
*** thread B: remaining time 2
*** thread B: remaining time 1
*** thread B: remaining time 0
*** thread C: remaining time 2
*** thread C: remaining time 1
*** thread C: remaining time 0
*** thread A: remaining time 4
*** thread A: remaining time 3
*** thread A: remaining time 2
*** thread A: remaining time 1
*** thread A: remaining time 0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!
...
```
### 雜項
#### Makefile
增加`sleeptest1.c`以及`sleeptest2.c`的時候要如何一起編譯呢？修改`Makefile`中的`all`以及在最後加上該檔案的東東。老樣子，就是抄前人已經寫好的部分再稍微修改。
***test/Makefile*** :
```makefile
...
all: halt shell matmult sort test1 test2 test3 sleeptest1 sleeptest2
...
sleeptest1: sleeptest1.o start.o
$(LD) $(LDFLAGS) start.o sleeptest1.o -o sleeptest1.coff
../bin/coff2noff sleeptest1.coff sleeptest1
sleeptest2: sleeptest2.o start.o
$(LD) $(LDFLAGS) start.o sleeptest2.o -o sleeptest2.coff
../bin/coff2noff sleeptest2.coff sleeptest2
```
#### Constructor in constructor (C++)
在與那些`Kernel`們奮鬥時，常常會想為甚麼要把同樣的程式碼複製貼上呢？想起初學程式時老師的告誡，如果寫程式要用到複製貼上，那就不是好程式。明明default constructor就是那些帶參數的constructor的特例，是不是可以重複使用呢？
***sample.cpp*** :
```C++
#include <iostream>
using namespace std;
class A{
public:
A(int x) {a = x;}
A() { A(1000); }
int a;
};
int main() {
A *a1 = new A(5);
A *a2 = new A();
cout << a1->a << " " << a2->a;
return 0;
}
```
***output*** :
```
5 0
```
看起來是不行。[ISO CPP FAQ](https://isocpp.org/wiki/faq/ctors#init-methods) 看看這邊的FAQ，對於亂搞一通的我氣得跟甚麼一樣。
我相信人的惰性以及對程式的美的要求，一定有一個好的解法。而且記憶中依稀記得C++中constructor是可以呼叫另一個constructor的。於是找到了下面這個解。這是在C++11之後可以使用的解法。[stack overflow](https://stackoverflow.com/questions/308276/can-i-call-a-constructor-from-another-constructor-do-constructor-chaining-in-c)
***sample.cpp*** :
```C++
#include <iostream>
using namespace std;
class A{
public:
A(int x) {a = x;}
A() : A(1000) { }
int a;
};
int main() {
A *a1 = new A(5);
A *a2 = new A();
cout << a1->a << " " << a2->a;
return 0;
}
```
***output*** :
```
5 1000
```
## Reference
[助教投影片](https://hackmd.io/@2xu_sb9JT2KDaAH-UKS7PA/HkqwUPuOw)
[偉大的學長姐](http://blog.terrynini.tw/tw/OS-NachOS-HW1/)
[也是偉大的學長姐](https://morris821028.github.io/2014/05/24/lesson/hw-nachos4/)
[也是偉大的學長姐](https://morris821028.github.io/2014/05/30/lesson/hw-nachos4-2/)
[ISO CPP FAQ](https://isocpp.org/wiki/faq/ctors#init-methods)
[stack overflow constructor](https://stackoverflow.com/questions/308276/can-i-call-a-constructor-from-another-constructor-do-constructor-chaining-in-c)
Sign in with Wallet
Connect another wallet