operating system MP3

12月 12, 2018

operating system MP3

這次要做的是scheduler
原本NachOS是用一個queue來做而且algorithm是用round robin
這次的machine problem 是要把原本NachOS的scheduling方式改成
Multi Level Feedback Queue
L1是用shortest job first
L2是用priority queue
L3是用round robin

Trace Code
interrupt.h/interrupt.cc
在NachOS中 interrupt這個資料結構用來模擬真實電腦上硬體如何發出hardware interrupt
在這個資料結構中用Setlevel這個routine來enable跟disable interrupts
(結合先前知識:如果我們在kernel mode處理interrupt(interrupt handler) 我們不希望自己被下一個進來的interrupt 所打斷故要disable interrupts 如果處理完之後再去enable interrupts)
interrupt這個資料結構也會追蹤我們在NachOS上的模擬時間當我們在做以下事情的時候 time才會advance

1.interrupt are re-enabled
(理解:當我們在kernel mode處理interrupt之前會先 disable 其他 interrupt也就是我們在kernel mode 做 interrupt handler的時候時間是暫停的因為在我們的模擬之下 interrupts 會被放入一個pending queue之中只有當pending queue裡的interrupts有人時間到要發出來時 interrupt才算真正發出故如果我們(kernel)在處理一個interrupt的時候我們不能讓時間繼續增加否則又會有interrupt 從queue裡面跑出來)

2.a user instruction is executed

3. there is nothing in the ready queue

綜合以上我們有此結果:
// As a result, unlike real hardware, interrupts (and thus time-slice
// context switches) cannot occur anywhere in the code where interrupts
// are enabled, but rather only at those places in the code where
// simulated time advances (so that it becomes time to invoke an
// interrupt in the hardware simulation).

alarm.h/alarm.cc

alarm is a data structure for a software alarm clock.
他使用一個timer(hardware device)每當這個timer經過一定的時間就會發起interrupt
因此我們可以透過這個資料結構來讓thread 醒來;並規定在一定的time slice之後才會醒來

alarm 這個類別繼承 Callback Object

class Alarm : public CallBackObj {
public:
Alarm(bool doRandomYield); // Initialize the timer, and callback
// to "toCall" every time slice.
~Alarm() { delete timer; }

void WaitUntil(int x); // suspend execution until time > now + x
// this method is not yet implemented

private:
Timer *timer; // the hardware timer device

void CallBack(); // called when the hardware
// timer generates an interrupt
};

alarm這個類別的建構函式:

Alarm::Alarm(bool doRandom)
{
timer = new Timer(doRandom, this);
}

new出一個timer 並將是不是要doRandom 跟自己傳入 timer的建構函式之中
(doRandom如果是TRUE 表示timer將在經過任一時間後發出interrupt)

timer的建構函式:
//----------------------------------------------------------------------
// Timer::Timer
// Initialize a hardware timer device. Save the place to call
// on each interrupt, and then arrange for the timer to start
// generating interrupts.
//
// "doRandom" -- if true, arrange for the interrupts to occur
// at random, instead of fixed, intervals.
// "toCall" is the interrupt handler to call when the timer expires.
//----------------------------------------------------------------------

Timer::Timer(bool doRandom, CallBackObj *toCall)
{
randomize = doRandom;
callPeriodically = toCall;
disable = FALSE;
SetInterrupt();
}

timer的SetInterrupt函式
//----------------------------------------------------------------------
// Timer::SetInterrupt
// Cause a timer interrupt to occur in the future, unless
// future interrupts have been disabled. The delay is either
// fixed or random.
//----------------------------------------------------------------------

void
Timer::SetInterrupt()
{
if (!disable) {
int delay = TimerTicks;

if (randomize) {
delay = 1 + (RandomNumber() % (TimerTicks * 2));
}
// schedule the next timer device interrupt
kernel->interrupt->Schedule(this, delay, TimerInt);
}
}

(其中TimerTicks定義在stats.h中)

interrupt.cc中的schedule function:

//----------------------------------------------------------------------

// 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);

}

timer的SetInterrupt()呼叫interrupt類別中的Schedule這個函式

Schedule這個函式將從timer那裏拿來的(this, delay, TimerInt)打包入一個叫做toOccur的物件之中

(其中this為呼叫SetInterrupt的自己這個timer

delay為經過多久要發出interrupt

TimerInt為標示interrupt的type)

之後Schedule在將這個toOccur物件丟入pending 這個 priority queue之中

interrupt類別中的CheckIfDue

//----------------------------------------------------------------------

// Interrupt::CheckIfDue

// Check if any interrupts are scheduled to occur, and if so,

// fire them off.

// Returns:

// TRUE, if we fired off any interrupt handlers

// Params:

// "advanceClock" -- if TRUE, there is nothing in the ready queue,

// so we should simply advance the clock to when the next

// pending interrupt would occur (if any).

//----------------------------------------------------------------------

bool

Interrupt::CheckIfDue(bool advanceClock)

{

PendingInterrupt *next;

Statistics *stats = kernel->stats;

ASSERT(level == IntOff); // interrupts need to be disabled,

// to invoke an interrupt handler

if (debug->IsEnabled(dbgInt)) {

DumpState();

}

if (pending->IsEmpty()) { // no pending interrupts

return FALSE;

}

next = pending->Front();

if (next->when > stats->totalTicks) {

if (!advanceClock) { // not time yet

return FALSE;

}

else { // advance the clock to next interrupt

stats->idleTicks += (next->when - stats->totalTicks);

stats->totalTicks = next->when;

// UDelay(1000L); // rcgood - to stop nachos from spinning.

}

DEBUG(dbgInt, "Invoking interrupt handler for the ");

DEBUG(dbgInt, intTypeNames[next->type] << " at time " << next->when);

if (kernel->machine != NULL) {

kernel->machine->DelayedLoad(0, 0);

}

inHandler = TRUE;

do {

next = pending->RemoveFront(); // pull interrupt off list

DEBUG(dbgTraCode, "In Interrupt::CheckIfDue, into callOnInterrupt->CallBack, " << stats->totalTicks);

next->callOnInterrupt->CallBack();// call the interrupt handler

DEBUG(dbgTraCode, "In Interrupt::CheckIfDue, return from callOnInterrupt->CallBack, " << stats->totalTicks);

delete next;

} while (!pending->IsEmpty()

&& (pending->Front()->when <= stats->totalTicks));

inHandler = FALSE;

return TRUE;

}

當ChechIfDue這個函式被呼叫到後我們將取pending queue中最前面的東西(也就是interrupt)

把這個東西的when這個field拿出來看

看看目前kernel的totaltick是不是超過了when

如果超過了表示這個東西(也就是interrupt)可以被發起

那我們就把inHandler這個屬於Interrupt類別的flag設成1 表示我們進入interrupt handler

然後就把pending queue裡面的東西一個一個拉出來(如果totaltick超過這個東西的when)

並去呼叫這些東西的CallBack()

在TimerInt中我們是先去呼叫timer的Callback()

//----------------------------------------------------------------------

// Timer::CallBack

// Routine called when interrupt is generated by the hardware

// timer device. Schedule the next interrupt, and invoke the

// interrupt handler.

//----------------------------------------------------------------------

void

Timer::CallBack()

{

// invoke the Nachos interrupt handler for this device

callPeriodically->CallBack();

SetInterrupt(); // do last, to let software interrupt handler

// decide if it wants to disable future interrupts

}

然後timer的Callback()會再去呼叫callPeriodically的Callback()

如果這個timer是屬於alarm的話

我們會去叫到alarm的Callback()

//----------------------------------------------------------------------

// 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).

//----------------------------------------------------------------------

void

Alarm::CallBack()

{

Interrupt *interrupt = kernel->interrupt;

MachineStatus status = interrupt->getStatus();

if (status != IdleMode) {

interrupt->YieldOnReturn();

}

這裡會去call到Interrupt的YieldOnReturn()

(如果MachineStatus不是IdleMode的話)

//----------------------------------------------------------------------

// Interrupt::YieldOnReturn

// Called from within an interrupt handler, to cause a context switch

// (for example, on a time slice) in the interrupted thread,

// when the handler returns.

// We can't do the context switch here, because that would switch

// out the interrupt handler, and we want to switch out the

// interrupted thread.

//----------------------------------------------------------------------

void

Interrupt::YieldOnReturn()

{

ASSERT(inHandler == TRUE);

yieldOnReturn = TRUE;

}

(關於這句話:We can't do the context switch here, because that would switch out the interrupt handler, and we want to switch out the interrupted thread.

我的理解是因為現在我們在interrupt handler之中(kernel mode) 但我們要去switch的是user mode正在使用CPU的thread 所以在這裡我們只能將yieldOnReturn這個flag拉成TRUE

等跳出interrupt handler之後我們再憑藉著這個flag去做kernel->currentthread->Yield())

做完YieldOnReturn之後回到Alarm的Callback() 再回到Timer的Callback() 然後在Timer的Callback()中會去call 一次SetInterrupt()

(這個我覺得之後要將它改成disable 因為user mode的thread準備要context switch了不用再放一個TimerInt進入pending queue裡面)

之後再回到CheckIfDue的while loop裡面然後跳出while loop 將InHandler設成0 表示離開interrupt handler

由於進入CheckIfDue的點很有可能為OneTick所以做完CheckIfDue我們會回到OneTick裡面

//----------------------------------------------------------------------

// Interrupt::OneTick

// Advance simulated time and check if there are any pending

// interrupts to be called.

// Two things can cause OneTick to be called:

// interrupts are re-enabled

// a user instruction is executed

//----------------------------------------------------------------------

void

Interrupt::OneTick()

{

MachineStatus oldStatus = status;

Statistics *stats = kernel->stats;

// advance simulated time

if (status == SystemMode) {

stats->totalTicks += SystemTick;

stats->systemTicks += SystemTick;

} else {

stats->totalTicks += UserTick;

stats->userTicks += UserTick;

}

DEBUG(dbgInt, "== Tick " << stats->totalTicks << " ==");

// check any pending interrupts are now ready to fire

ChangeLevel(IntOn, IntOff); // first, turn off interrupts

// (interrupt handlers run with

// interrupts disabled)

CheckIfDue(FALSE); // check for pending interrupts

ChangeLevel(IntOff, IntOn); // re-enable interrupts

if (yieldOnReturn) { // if the timer device handler asked

// for a context switch, ok to do it now

yieldOnReturn = FALSE;

status = SystemMode; // yield is a kernel routine

kernel->currentThread->Yield();

status = oldStatus;

}

在這裡我們由於剛剛有將yieldOnReturn設成TRUE所以會進入判斷式之中然後執行

kernel->currentThread->Yield()

(這裡有個問題就是為什麼不在進入CheckIfDue的時候就將status設成SystemMode呢感覺CheckIfDue會進入到interrupt handler 應該也是在SystemMode)

Implement:

在Thread類別中新增這些field

priority為thread的priority
burstTime為此thread進入到Sleep()時去算這次執行完整個CPU burst所需的時間
start為每次這個thread要進入到Running State的時候,去存當下的totalTick(整個系統的時間)
當這個thread被Yield的時候用當下的totalTick減掉存起來的start就是這次執行的時間但此時是Yield表示 CPU burst還沒做完要做的是累加(當下的totalTick減掉存起來的start)到burstTime之中
在進入Sleep()的時候去算 historyBurstTime = historyBurstTime*0.5 + busrtTime*0.5

Kernel::Kernel(int argc, char **argv)

這裡去讀輸入的指令
ex:$ ../build.linux/nachos -ep test1 40 -ep test2 80
其中execfilePriority為我們自己新加的array

在Kernel::Initialize()中

我們會去new 一個main thread並將(Thread)*currentThread指向這個thread(name為main threadID為0)

threadNum在這裡會去++ 變成1

然後這裡還會去new 一個PostOfficeInput的物件
主要是去做MSG的傳送裡面會去new一個thread名為postal worker

由於這個thread是在做PostOfficeInput的建構函式時去new的跟kernel裡面的Thread*t[10]無關
我們在這裡set這個thread的priority為149使其進入到L1
並且將其historyBurstTime設為0
然後去做Fork 並在Fork裡面去呼叫 scheduler->ReadyToRun(this);使其進入ready queue之中
這裡這樣做是要讓其先被執行掉(我理解為在main thread 去 call Finish()的時候會去先把postal worker叫起來做)

void Kernel::ExecAll()

根據有幾個要執行的程式去new出這些thread 由於在Kernel::Initialize()的時候去讓
threadNum++故現在threadNum為1
故void Kernel::ExecAll()中的for loop不會錯

在main thread去 call currentThread->Finish()之前將SetIsPreemptable設成TRUE
表示之後有人進入到ready queue且符合條件scheduler就必須重新scheduling

class Scheduler