HackMD
OS 2020 HW2 Nachos Report
Motivation
System Call
先按照作業的說明操作，在製作sleep list的時候若能依照起床時間排序將會省事不少。
CPU Scheduling
根據指示，若有實作多個scheduling，則應該要在threads/main.cc中設計可以提供選擇的功能。
threads/main.cc :
...
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 :
...
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 :
...
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()加上自己要測試的程式。
...
//----------------------------------------------------------------------
// 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 :
...
#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 :
...
.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 :
...
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 :
...
#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 :
...
//----------------------------------------------------------------------
// 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 :
...
SortedList<PendingInterrupt *> *pending;
...
machine/interrupt.cc :
...
//----------------------------------------------------------------------
// 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 :
...
//----------------------------------------------------------------------
// 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 :
...
//----------------------------------------------------------------------
// 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 :
...
//----------------------------------------------------------------------
// 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 :
...
#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 :
...
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 :
...
//----------------------------------------------------------------------
// 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 :
...
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 :
...
//----------------------------------------------------------------------
// 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 :
...
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 :
...
//----------------------------------------------------------------------
// 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 :
...
int PriorityCompare (Thread *a, Thread *b);
int SJFCompare (Thread *a, Thread *b);
int FCFSCompare (Thread *a, Thread *b);
...
threads/schdeduler.cc :
...
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 :
#include "syscall.h"
int main()
{
int i = 0;
for ( i = 0; i < 5; i += 1)
{
Sleep(100000);
PrintInt(1);
}
return 0;
}
test/sleeptest2.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 :
...
//----------------------------------------------------------------------
// 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()內容
...
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 :
...
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 :
#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 看看這邊的FAQ，對於亂搞一通的我氣得跟甚麼一樣。
我相信人的惰性以及對程式的美的要求，一定有一個好的解法。而且記憶中依稀記得C中constructor是可以呼叫另一個constructor的。於是找到了下面這個解。這是在C11之後可以使用的解法。stack overflow
sample.cpp :
#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
