# MP3_report_29
## Team Member
### (1) 107000205 李柏漢
Contribution
* Trace Code
* All
* Implementation
* All
* Report
* Trace Code, Implementation 3
***
### (2) 107000115 林珈卉
Contribution
* Trace Code
* All
* Implementation
* All
* Report
* Implementation 1, 2, 3

<div style="page-break-after: always;"></div>

## Trace Code
#### 1. New→Ready
##### Kernel::ExecAll()
* It uses a for loop to run through all the files in "execfile", and execute them in "exec()" function.

void Kernel::ExecAll()
{
    for (int i = 1; i <= execfileNum; i++)
    {
        int a = Exec(execfile[i]);
    }
    currentThread->Finish();

##### Kernel::Exec(char*)
* We will throw fileName before entering this function.
* Then create a new thread and allocate a space for the file we want to execute.
* Use Fork function to execute the file.
* Since we are have create a new thread and it's all set, so the threadNum will be update to threadNum+1.

int Kernel::Exec(char *name)
{
    t[threadNum] = new Thread(name, threadNum);
    t[threadNum]->space = new AddrSpace(PhyMem);
    t[threadNum]->Fork((VoidFunctionPtr)&ForkExecute, (void *)t[threadNum]);
    threadNum++;

    return threadNum - 1;
}    

##### Thread::Fork(VoidFunctionPtr, void*)

* In fork function, we will first allocate a stack for the function.
* Set the interrupt off.
* And put it on the ready queue with ReadyToRun() function.
* And we will then set the level back to its old one according to the oldLevel variable we store before.

Thread::Fork(VoidFunctionPtr func, void *arg)
{
    Interrupt *interrupt = kernel->interrupt;
    Scheduler *scheduler = kernel->scheduler;
    IntStatus oldLevel;
    
    StackAllocate(func, arg);

    oldLevel = interrupt->SetLevel(IntOff);
    scheduler->ReadyToRun(this);
    (void) interrupt->SetLevel(oldLevel);
}    

##### Thread::StackAllocate(VoidFunctionPtr, void*)
* In StackAllocate we will create a stack space and initialize it according to different ISA.

Thread::StackAllocate (VoidFunctionPtr func, void *arg)
{
    stack = (int *) AllocBoundedArray(StackSize * sizeof(int));

#ifdef PARISC
    stackTop = stack + 16;	// HP requires 64-byte frame marker
    stack[StackSize - 1] = STACK_FENCEPOST;
#endif

#ifdef SPARC
    stackTop = stack + StackSize - 96; 	
    *stack = STACK_FENCEPOST;
#endif 

#ifdef PowerPC // RS6000
    stackTop = stack + StackSize - 16; 	// RS6000 requires 64-byte frame marker
    *stack = STACK_FENCEPOST;
#endif 

#ifdef DECMIPS
    stackTop = stack + StackSize - 4;	// -4 to be on the safe side!
    *stack = STACK_FENCEPOST;
#endif

#ifdef ALPHA
    stackTop = stack + StackSize - 8;	// -8 to be on the safe side!
    *stack = STACK_FENCEPOST;
#endif

#ifdef x86
    
    stackTop = stack + StackSize - 4;	// -4 to be on the safe side!
    *(--stackTop) = (int) ThreadRoot;
    *stack = STACK_FENCEPOST;
#endif
    
#ifdef PARISC
    machineState[PCState] = PLabelToAddr(ThreadRoot);
    machineState[StartupPCState] = PLabelToAddr(ThreadBegin);
    machineState[InitialPCState] = PLabelToAddr(func);
    machineState[InitialArgState] = arg;
    machineState[WhenDonePCState] = PLabelToAddr(ThreadFinish);
#else
    machineState[PCState] = (void*)ThreadRoot;
    machineState[StartupPCState] = (void*)ThreadBegin;
    machineState[InitialPCState] = (void*)func;
    machineState[InitialArgState] = (void*)arg;
    machineState[WhenDonePCState] = (void*)ThreadFinish;
#endif
}

##### Scheduler::ReadyToRun(Thread*)
* Use setStatus function to set status to READY and use append function to put current thread into readyList.

void
Scheduler::ReadyToRun (Thread *thread)
{
    thread->setStatus(READY);
    readyList->Append(thread);
}

#### 2. Running→Ready
##### Machine::Run()
* In this function, we Simulate the execution of a user-level program on Nachos.
* First, we have to create a storage for decoded instruction.
* Then switch the status to UserMode.
* Enter a for loop which never return.
* Put instr into oneInstruction() to execute it from a user-level program.
* Use oneTick() to advance simulated time and check if there are any pending interrupts to be called.

void Machine::Run()
{
    Instruction *instr = new Instruction;
    kernel->interrupt->setStatus(UserMode);
    for (;;)
    {
        OneInstruction(instr);
        kernel->interrupt->OneTick();
    }
}

##### Interrupt::OneTick()
* In this function we first save the old status in advance.
* First, we turn off interrupts with ChangeLevel(IntOn, IntOff);
* Second, go check if there is any pending interrupts are now ready to be fire,and if so, fire them off.
* After finishing dealing with interrupts, we have to turn the interrupt on again.
* Use yieldOnReturn to check if we are to context switch, if so, go deal with it!
* When we are going to deal with context switch, we will first turn the yieldOnReturn to FALSE and change the status to SystemMode, and call Yield() to do the thing, and finally, change the oldstutus back.

Interrupt::OneTick()
{
    MachineStatus oldStatus = status;
    Statistics *stats = kernel->stats;

    // stats->___Ticks += ...
    
    ChangeLevel(IntOn, IntOff);
    CheckIfDue(FALSE);		
    ChangeLevel(IntOff, IntOn);	
    
    if (yieldOnReturn) {	
        yieldOnReturn = FALSE;
        status = SystemMode;
        kernel->currentThread->Yield();
        status = oldStatus;
    }
}

##### Thread::Yield()
* When we call this function, it means we want to relinquish the current thread if any other thread is ready to run.
* First, we save current level into oldLevel var, and go to scheduler to find which is next to run.
* And if there is a thread we are going to run now, we put current thread to ready list, and use Run() to run the thread we just found on the scheduler.
* In the end, we set the interrupt level to the old one.

Thread::Yield ()
{
    Thread *nextThread;
    IntStatus oldLevel = kernel->interrupt->SetLevel(IntOff);
    nextThread = kernel->scheduler->FindNextToRun();
    
    if (nextThread != NULL) {
        kernel->scheduler->ReadyToRun(this);
        kernel->scheduler->Run(nextThread, FALSE);
    }
    (void) kernel->interrupt->SetLevel(oldLevel);
}

##### Scheduler::FindNextToRun()
* In this function, we're going to find out how we find next thread to be run.
* We first check if the readylist is empty, if it's true, then return, else, remove the first thread in the list and return it.

Scheduler::FindNextToRun ()
{
    if (readyList->IsEmpty())
        return NULL;
    else
    	return readyList->RemoveFront();
}

##### Scheduler::ReadyToRun(Thread*)
* This function is to put the thread to ready list.
* First we set the thread's status to READY.
* Then we add the thread to readyList.

Scheduler::ReadyToRun (Thread *thread)
{
    thread->setStatus(READY);
    readyList->Append(thread);
}

##### Scheduler::Run(Thread*, bool)
* In this function, we have to save the current thread first, then check if current thread is Finish, if so, then destroy it.
* then check if this thread is a user program, if so, save the user's CPU registers.
* Use oldThread->CheckOverflow(); to check if the old thread has overthread problem.
* Then use kernel->currentThread = nextThread nextThread->setStatus(RUNNING); to change the current thread to nextThraed and set it to RUNNING state.
* Use SWITCH() to stop running oldThread and start running newThread
* Use CheckToBeDestroyed() to detroy the threads before which are finished or need to be clean up.
* And finally, check if there is an address space, if so, do it!

Scheduler::Run (Thread *nextThread, bool finishing)
{
    Thread *oldThread = kernel->currentThread;
    
    if (finishing) {
	 toBeDestroyed = oldThread;
    }
    if (oldThread->space != NULL) {
        oldThread->SaveUserState();
        oldThread->space->SaveState();
    }
    oldThread->CheckOverflow();
    kernel->currentThread = nextThread;
    nextThread->setStatus(RUNNING);
    
    SWITCH(oldThread, nextThread);
    
    // we're back, running oldThread
    CheckToBeDestroyed();
    if (oldThread->space != NULL) {
        oldThread->RestoreUserState();
        oldThread->space->RestoreState();
    }
}

#### 3. Running→Waiting
##### SynchConsoleOutput::PutChar(char)
* In this function, our goal is to write a character to the console display, waiting if necessary.
* First, we go to Acquire() to check if it's lock, if so, wait until it's free, so we can get the lock.
* Then we can use PutChar() to put our ch to console.
* Use waitFor->P() to wait until semaphore value > 0, then decrement.
* Return the lock.

SynchConsoleOutput::PutChar(char ch)
{
    lock->Acquire();
    consoleOutput->PutChar(ch);
    waitFor->P();
    lock->Release();
}

##### Semaphore::P()
* We first save current level to oldLevel. and set interrupt off.
* Then enter a while loop, if value is equal to 0 then it means it's not available right now, so we put currentThread to queue and set it to Sleep until value>0.
* When it's available, we minus the value and set the interrupt to old level.

Semaphore::P()
{
    Interrupt *interrupt = kernel->interrupt;
    Thread *currentThread = kernel->currentThread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	
    
    while (value == 0) {
        queue->Append(currentThread);
        currentThread->Sleep(FALSE);
    } 
    value--;
    
    (void) interrupt->SetLevel(oldLevel);	
}

##### Thread::Sleep(bool)
* The goal of this function is to relinquish the CPU, because the current thread has either finished or is blocked waiting on a synchronization variable.
* If a thread call this function, we'll first set its status to BLOCKED, then enter a while loop and use FindNextToRun() to find the next thread to run, if not found, then stay in the while loop, and set interrupt to Idle.
* If found, take it and finishing as argument and throw it into Run().

Thread::Sleep (bool finishing)
{
    Thread *nextThread;
    status = BLOCKED;
    while ((nextThread = kernel->scheduler->FindNextToRun()) == NULL) {
        kernel->interrupt->Idle();
    }
    kernel->scheduler->Run(nextThread, finishing); 
}

##### Scheduler::FindNextToRun()
##### Scheduler::Run(Thread*, bool)

#### 4. Waiting→Ready
##### Semaphore::V()
* In this function, we increment semaphore value, waking up a waiter if necessary.
* We first save current level into oldLevel, and set the interrupt off.
* Check if there is something on the queue, if so, use ReadyToRun and go to readyList to find something to run.
* Increment value and turn set the interrupt level back.

Semaphore::V()
{
    Interrupt *interrupt = kernel->interrupt;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	
    
    if (!queue->IsEmpty()) {
	kernel->scheduler->ReadyToRun(queue->RemoveFront());
    }
    value++;
    
    (void) interrupt->SetLevel(oldLevel);
}

##### Scheduler::ReadyToRun(Thread*)

#### 5. Running→Terminated
##### ExceptionHandler(ExceptionType) case SC_Exit
* When we enter this case, we'll first go to Register 4 to find value and store it into val.
* Then we use Finish() to stop this Thread.
* When finish, break.

case SC_Exit:
    val = kernel->machine->ReadRegister(4);
    kernel->currentThread->Finish();
    break;

##### Thread::Finish()
* First, set the interrupt off.
* And use Sleep() to make this thread to sleep with argument "finsihing"==true.

void
Thread::Finish ()
{
    (void) kernel->interrupt->SetLevel(IntOff);
    Sleep(TRUE);
}

##### Thread::Sleep(bool)
##### Scheduler::FindNextToRun()
##### Scheduler::Run(Thread*, bool)

#### 6. Ready→Running
##### Scheduler::FindNextToRun
##### Scheduler::Run(Thread*, bool)
##### SWITCH(Thread*, Thread*)
* In this assembly code, we want to do context switch for purpose.
* At first we'll use .globl and. ent. ".globl" is an assembler directive that tells the assembler that the SWITCH symbol will be accessible from outside the current file, and .ent is a debugger operation that marks the entry of SWITCH.
* When context switching, we use sw to store the data from current register sp, s0, s1....s7, fp, ra to the old Thread"s register SP(a0), S0(a0), S1(a0).....S7(a0), FP(a0), PC(a0).
* After done with sw, the register sp, s0, s1......s7, fp, ra is available now. Then we start load data from a1's register, use lw to load SP(a1) S0(a1), S1(a1).....,S7(a1), fp(a1), ra(a1) to SP(a1), S0(a1), S1(a1)......S7(a1), FP(a1),PC(a1).
* After finishing sw and lw, we use j to jump to ra(return address), and end SWITCH.

# a0 -- pointer to old Thread
# a1 -- pointer to new Thread
	.globl SWITCH
	.ent	SWITCH,0
SWITCH:
	sw	sp, SP(a0)		# save new stack pointer
	sw	s0, S0(a0)		# save all the callee-save registers
	sw	s1, S1(a0)
	sw	s2, S2(a0)
	sw	s3, S3(a0)
	sw	s4, S4(a0)
	sw	s5, S5(a0)
	sw	s6, S6(a0)
	sw	s7, S7(a0)
	sw	fp, FP(a0)		# save frame pointer
	sw	ra, PC(a0)		# save return address
	
	lw	sp, SP(a1)		# load the new stack pointer
	lw	s0, S0(a1)		# load the callee-save registers
	lw	s1, S1(a1)
	lw	s2, S2(a1)
	lw	s3, S3(a1)
	lw	s4, S4(a1)
	lw	s5, S5(a1)
	lw	s6, S6(a1)
	lw	s7, S7(a1)
	lw	fp, FP(a1)
	lw	ra, PC(a1)		# load the return address	

	j	ra
	.end SWITCH

#endif // DECMIPS

##### (depends on the previous process state, e.g., [New,Running,Waiting]→Ready)
##### for loop in Machine::Run()

***

<div style="page-break-after: always;"></div>

## Implementation
### 1. Multilevel feedback queue scheduler
#### Thread
- In ExecAll(), send the strings of filename and priority to Exec().

int a = Exec(execfile[i], priority[i]);

- In Exec(), after construct a Thread, store the priority of it.

t[threadNum] = new Thread(name, threadNum);
t[threadNum]->SetPriority(pr);

- We need to store some arguments for thread.

int priority;
int initialTick;
double burstTime;
double predictTime;
double lastExecTime;
int initialAgeTick;
int totalAgeTick;

- We also need some function in Thread to implement scheduler.

void AddPriority();         // Aging
int GetLayer();             // it's L1, L2 or L3 layer
bool IsExceedAgeTick();     // check if totalAgeTick is more than 1500
void UpdateTotalAgeTick();  // update how long it wait every timer tick (100)
void DecreaseTotalAge();    // when age tick >= 1500, decrease it by 1500
void RecalculateBurstTime(); // recalculate when Yield() or Sleep()
void TerminateBurstTimeCounting(); // below

- When Sleep(), the thread is running->waiting or running->finish.
- If it goes to waiting queue, we still need its burst time data.
- Use the equation $$t_i = 0.5 * T + 0.5 * t_{i-1}$$ to calculate the predict time.

Thread::TerminateBurstTime() {
    RecalculateBurstTime();

    double newpredictTime = (burstTime/2) + (predictTime/2);

    DEBUG(dbgExpr, "[D]...");

    predictTime = newpredictTime;
    lastExecTime = burstTime;
    burstTime = 0.0;
}

#### Scheduler
- In scheduler, we replace a single "readylist" with 3 lists, L1, L2 and L3.
- And we need some functions.

List<Thread *> *L1;
List<Thread *> *L2;
List<Thread *> *L3;
// List<Thread *> *readyList;

bool hasThreadInL1() { return !(L1->IsEmpty()); }
void AgingProcess(); // All
void LayerAgingProcess(List<Thread *> *list, int lr);
void AddToQueue(int lr, List<Thread *> *list, Thread *newThread);
Thread* RemoveFromQueue(int lr, List<Thread *> *list, Thread *thr);

#### To Ready Queue
- When a thread is ready to run, we put it into one of the three queues according to its priority.
- We cannot simply store its layer as an argument, since it might change its layer after ==aging==.
- Meanwhile, set its initial age tick.

Scheduler::ReadyToRun (Thread *thread) {
    int pr = thread->GetPriority();
    if (pr >= 100){
        AddToQueue(1, L1, thread);
    } else if (pr >= 50 && pr <= 99){
        AddToQueue(2, L2, thread);
    } else {
        AddToQueue(3, L3, thread);
    }
    thread->SetAgeInitialTick(kernel->stats->totalTicks);
}

#### From Ready to Running
- We connot simply readylist->removeFront() same as before, because there should be different implementations to 3 queues.
- L1 has the highest priority, so check L1 first.

Scheduler::FindNextToRun (){
    if(!L1->IsEmpty()){...}
    else if(!L2->IsEmpty()){...}
    else if(!L3->IsEmpty()){...}
    else {return NULL;}
}

- If there is any thread in L1, use preemptive SJF method.
- Find the thread with the least predict time.
- Remove it from L1, and return it to Yield() (or Sleep()).

if (!L1->IsEmpty()) { // Preemptive SJF
    while (!iter->IsDone()) {
        thr = iter->Item();
        if (thr->GetApproximateBurstTime() < approximateThread->GetApproximateBurstTime()) {
            approximateThread = thr;
        }
        iter->Next();
    }
    return RemoveFromQueue(1, L1, approximateThread);
}

- L2 uses Non-preemptive priority method.
- Find the thread with the highest priority in L2.

else if (!L2->IsEmpty()) { // Non-preemptive priority
    while (!iter->IsDone()) {
        thr = iter->Item();
        if (thr->GetPriority() > highestPrThread->GetPriority()) {
            highestPrThread = thr;
        }
        iter->Next();
    }
    return RemoveFromQueue(2, L2, highestPrThread);
}

- L3 uses Round-robin, so find the front thread of L3.

else if(!L3->IsEmpty())
    return RemoveFromQueue(3, L3, L3->Front());

#### RemoveFromQueue
- The thread is from ready queue to running queue
- up

Scheduler::RemoveFromQueue(int lr, List<Thread *> *list, Thread *thr) {
    list->Remove(thr);
    DEBUG(dbgExpr, "[B]...");

    thr->UpdateTotalAgeTick(); 
    thr->SetAgeInitialTick(kernel->stats->totalTicks); 
    return thr;  
}

#### Aging Process
- Do the aging process every 1500.
- Alarm does callback every 100 ticks, so we call aging process when call back.
- YieldOnReturn
- If current thread is L1, we check for preemption.
- If it is L2, check if there is any thread in L1, since it could be preempted by the thread in L1.
- If it is L3, do round-robin.

Alarm::CallBack() 
{
    kernel->scheduler->AgingProcess();
    
    if (status != IdleMode) {
        int lr = kernel->currentThread->GetLayer();
        if (lr == 1 || kernel->scheduler->hasThreadInL1() || lr == 3) 
            interrupt->YieldOnReturn();
    }
}

- Do aging process to threads in three layers.

Scheduler::AgingProcess() {
    LayerAgingProcess(L1, 1);
    LayerAgingProcess(L2, 2);
    LayerAgingProcess(L3, 3);
}

- For each layer, run the while loop to access all threads in the queue.
- For each thread,
- If current thread is L1, we check for preemption.
- If it is L2, check if there is any thread in L1, since it could be preempted by the thread in L1.
- If it is L3, do round-robin.
- Deal with the threads crossing layers due to adding priorities.

while (!iter->IsDone()) {
    thr = iter->Item();
    thr->UpdateTotalAgeTick();
    thr->SetAgeInitialTick(kernel->stats->totalTicks); 
    
    if (thr->IsExceedAgeTime()) { //check if it waits over 1500 ticks
        // if so, decrease 1500 ticks and add priority by 10
        thr->DecreaseTotalAge(1500); 
        thr->AddPriority(10);

        DEBUG(dbgExpr, "[C]...");

        // For the threads crossing layers
        if (lr == 3 && thr->GetPriority() >= 50) {
            RemoveFromQueue(3, L3, thr);
            AddToQueue(2, L2, thr);
        } else if (lr == 2 && thr->GetPriority() >= 100) {
            RemoveFromQueue(2, L2, thr);
            AddToQueue(1, L1, thr);
        }
    }
    iter->Next();
}

#### Context Switch
- In Yield(), put current thread back to ready queue, and find next thread to run.
- It might be the same thread, so current thread needs to be put back before find the next thread.
- Before running new thread, we should reculculate the burst time of current thread.

Thread::Yield () {
    kernel->scheduler->ReadyToRun(this);
    nextThread = kernel->scheduler->FindNextToRun();
    if (nextThread != NULL) {
        RecalculateBurstTime();
        kernel->scheduler->Run(nextThread, FALSE);
    }
}

- When Run(), we should set initial tick to both threads.
- Set the new thread, call SWITCH(), then set the old thread.

DEBUG(dbgExpr, "[E]...");
nextThread->SetInitialTick(kernel->stats->totalTicks);

SWITCH(oldThread, nextThread);

oldThread->SetInitialTick(kernel->stats->totalTicks);

### 2. Command line argument ==-ep==
- There are 2 arguements after "-ep", so check i+2.

ASSERT(i + 2 < argc);

- Store the string of priority number, and check if the string is number.
- Then, convert the string into int, and store it into the list of priorities.

char *numStr = argv[++i];
int j = 0;
while (numStr[j] != '\0')
{
    ASSERT(numStr[j] >= '0' && numStr[j] <= '9');
    j++;
}
int priority = atoi(numStr);
ASSERT(priority >= 0 && priority <= 149); // check valid
priorities[execfileNum] = priority;

### 3. Debugging flag ==z==
- We first predefined a debugging flag z in debug.h

const char dbgExpr = 'z';

#### ==[A]== when Put Into Queue
- In Scheduler::AppendToQueue() we will use Append() to insert a thread to queue, so we add a DEBUG() with flag dbgExpr.

list->Append(newThread);
DEBUG(dbgExpr, "[A] Tick [" << kernel->stats->totalTicks 
        << "]: Thread [" << newThread->getID() 
        << "] is inserted into queue L["<< layerIdx <<"]");

#### ==[B]== when Remove From Queue
- In Scheduler::RemoveFromQueue, we will use Remove() to remove a Thread from a queue, so we add a DEBUG() with flag dbgExpr.

list->Remove(newThread);
DEBUG(dbgExpr, "[B] Tick ["<< kernel->stats->totalTicks 
        << "]: Thread [" << newThread->getID() 
        << "] is removed from queue L[" << layerIdx <<"]");

#### ==[C]== when changing its scheduling priority
- In Scheduler::LayerAgingProcess() we are going to do aging, which means its priority is going to be change in this function.
- We can found that it's going to change its priority in "iterThread->AddPriority(10)", so we add a DEBUG() with flagExpr behind.

iterThread->AddPriority(10);
DEBUG(dbgExpr, "[C] Tick ["<< kernel->stats->totalTicks 
        << "]: Thread [" << iterThread->getID() 
        << "] changes its priority from ["<< foundPriority 
        << "] to ["<< iterThread->GetPriority() <<"]");

#### ==[D]== when thread is from running -> waiting, updating its approximate burst time
- The thread update its approximate burst time in Thread::TerminateBurstTimeCounting() so after calculating the newPredictTime, we add a DEBUG() with flag dbgExpr.

RecalculateBurstTime();

double newPredictTime = (double)(predictTime/2) + (double)(burstTime/2);
DEBUG(dbgExpr, "[D] Tick ["<< kernel->stats->totalTicks 
        << "]: Thread [" << ID << "] update approximate burst time, from: ["
        << predictTime <<"], add ["<< burstTime 
        << "], to ["<< newPredictTime <<"]");

#### ==[E]== when context switch occurs
- In Scheduler::Run, we do context switching, so after kernel->currentThread is update to new thread and be set up to RUNNING state, then we call DEBUG() with dbgExpr.

DEBUG(dbgExpr, "[E] Tick ["<< kernel->stats->totalTicks 
        << "]: Thread ["<< nextThread->getID() 
        << "] is now selected for execution, thread ["
        << oldThread->getID() <<"] is replaced, and it has executed ["
        << oldThread->GetExecTick() << "] ticks");

###### tags: `OS`