# NachOS MP3 109000109 謝秉軒

## Trace code

**New→Ready**
Kernel::ExecAll(): This function serves as the starting point for all applications in NachOS. It starts a new thread to run the program and then calls the main function of that program. When the main function is finished, control is returned to the thread pool, allowing other applications to operate.

Kernel::Exec(char*): This method generates a new thread to execute the provided program. It loads the code and data from the program file into memory before launching a new thread with the program's entry point set to the thread's initial program counter (PC). Finally, the function adds the thread to the thread pool, allowing the application to be executed.

Thread::Fork(VoidFunctionPtr, void*): This method launches a new NachOS thread and initializes its program counter and stack. It defines the function to be executed by referencing the function with a VoidFunctionPtr pointer and passing the parameters to the function with a void pointer. Finally, it adds the newly formed thread to the ready queue, allowing the function to be executed.

Thread::StackAllocate(VoidFunctionPtr, void*): This function is used to allocate stack space for a NachOS thread. It defines the function to be run by using a VoidFunctionPtr pointer that references the function and a void pointer that passes the arguments to the function. Finally, it returns a new stack pointer that points to the stack space allocated for the thread.

Scheduler::ReadyToRun(Thread*): This function allocates stack space to a NachOS thread. It defines the function to be executed by referencing the function with a VoidFunctionPtr pointer and passing the parameters to the function with a void pointer. Finally, it returns a new stack pointer pointing to the thread's stack area.

**Running→Ready**
Machine::Run(): This function is in charge of running NachOS applications on the emulated computer. This is accomplished by continually invoking Interrupt::OneTick() to mimic the passage of time and Scheduler::Run() to execute the next thread in the ready queue.

Interrupt::OneTick(): This function is called by Machine::Run() to simulate the passage of time. It advances the internal clock of the simulated machine by one tick, and checks whether any interrupts should be triggered based on the current state of the machine.

Thread::Yield(): Machine::Run() uses this method to mimic the passage of time. It advances the simulated machine's internal clock by one tick and checks to see whether any interrupts should be triggered depending on the machine's present state.

Scheduler::FindNextToRun(): This function is in charge of determining the next thread to execute from the ready queue. It searches the ready queue for the thread with the highest priority that is ready to run and provides a reference to that thread.

Scheduler::ReadyToRun(Thread*): This method adds a thread to the ready queue so that it may be scheduled for execution. It adds the given thread to the ready queue, changes its status to ready, and, if required, modifies its priority.

Scheduler::Run(Thread*, bool): This function is in charge of keeping a thread running on the CPU. It switches to the new thread's context by setting the current thread to the given thread, setting its status to running, and using Thread::Switch(). If the thread is already operating, the method returns with no action. The second option specifies whether the current thread should be returned to the ready queue when it has completed its execution.

**Running→Waiting**
SynchConsoleOutput::PutChar(char): This function sends a single character to the console. It guarantees that the output is synchronized, preventing characters from various threads from interleaving.

Semaphore::P(): This method is called to obtain a semaphore. If the value of the semaphore is 0, the calling thread is stopped until the semaphore is accessible.

List<T>::Append(T): This method adds a new entry to a linked list. It moves the item to the bottom of the list.

Thread::Sleep(bool): This function is used to sleep a thread for a defined amount of time. If the boolean option is set to true, the thread will be put to sleep until it is woken up by another thread.

Scheduler::FindNextToRun(): This function is responsible for finding the next thread to run from the ready queue. It searches the ready queue for the highest priority thread that is ready to run, and returns a pointer to that thread.

Scheduler::Run(Thread*, bool): This function is responsible for running a thread on the CPU. It sets the current thread to the specified thread, sets its state to running, and calls Thread::Switch() to switch to the new thread's context. If the thread is already running, the function simply returns without doing anything. The second parameter indicates whether the current thread should be added back to the ready queue after it has finished running.

**Waiting→Ready**
Semaphore::V(): This function is used to release a semaphore. It increments the semaphore value, and wakes up one thread that is waiting for the semaphore, if any.

Scheduler::ReadyToRun(Thread*): This function is used to add a thread to the ready queue so that it can be scheduled to run. It adds the specified thread to the ready queue, sets its state to ready, and updates its priority if necessary. This function is typically used to wake up a thread that was waiting for a resource or semaphore, after that resource or semaphore has become available.

**Running→Terminated**
Thread::Finish(): This function is used to terminate the current thread. It sets the thread's state to finished, removes the thread from the ready queue, and calls Thread::Switch() to switch to the next thread in the ready queue. It also deallocates the thread's stack and any other resources that the thread was using.

Thread::Sleep(bool): This function is used to put a thread to sleep for a specified period of time. If the boolean parameter is set to true, the thread is put to sleep indefinitely until it is woken up by another thread.

Scheduler::FindNextToRun(): This function is responsible for finding the next thread to run from the ready queue. It searches the ready queue for the highest priority thread that is ready to run, and returns a pointer to that thread.

Scheduler::Run(Thread*, bool): This function is responsible for running a thread on the CPU. It sets the current thread to the specified thread, sets its state to running, and calls Thread::Switch() to switch to the new thread's context. If the thread is already running, the function simply returns without doing anything. The second parameter indicates whether the current thread should be added back to the ready queue after it has finished running.

**Ready→Running**

## Implementation
To turn your scheduler into a preemptive SJF (Shortest Remaining Time First) scheduler, you need to perform a check every time a new thread becomes ready to run. If the new thread has a shorter remaining burst time than the currently executing thread, you should preempt the current thread and schedule the new thread for execution.

**Function added to the thread.cc**

    int Thread::GetExecTick()
{
    if (burstTime <= 0)
    return lastExecTime; // means it has terminate (in waiting state), we grab the last execute result.
    else
    return burstTime; // means it just stop (in ready state), we grab the current burst time.
}

// When Thread::Sleep(), running -> waiting
void Thread::TerminateBurstTimeCounting()
{
    // Confirm burst time (execution time) first.
    RecalculateBurstTime();
    if (preemtion == 1)
    {
    predictTime = predictTime - burstTime;
    burstTime = 0.0;
    }
    else
    {
    double newPredictTime = (double)(predictTime / 2) + (double)(burstTime / 2);
    DEBUG(dbgExpr, "[C] Tick [" << kernel->stats->totalTicks << "]: Thread [" << ID << "] update approximate burst time, from: [" << predictTime << "], add [" << burstTime << "], to [" << newPredictTime << "]");
    predictTime = newPredictTime;
    lastExecTime = burstTime;
    burstTime = 0.0;
    }
}

// When Thread::Yield(), running -> ready OR When Thread::Sleep(), running -> waiting
int Thread::RecalculateBurstTime()
{
    burstTime += (double)(kernel->stats->totalTicks - initialTick);
    return burstTime;
}

double Thread::GetApproximateBurstTime()
{
    return predictTime; // According to Discuss Room, we don't need to check for "remaining approximate burst time", "approximate burst time" is good enough
}

**Function added to the scheduler.cc**

    Thread *Scheduler::PutIntoQueue(Thread *newThread)
{
    readyList->Insert(newThread);
    DEBUG(dbgExpr, "[A] Tick [" << kernel->stats->totalTicks << "]: Thread [" << newThread->getID() << "] is inserted into queue");
    return newThread;
}

Thread *Scheduler::RemoveFromQueue(Thread *newThread)
{
    readyList->Remove(newThread);
    DEBUG(dbgExpr, "[B] Tick [" << kernel->stats->totalTicks << "]: Thread [" << newThread->getID() << "] is removed from queue");
    newThread->SetAgeInitialTick(kernel->stats->totalTicks); // Keep current tick data to thread struct, it's useful when this thread is transfered in aging rather than go to execute.
    return newThread;
}

void Scheduler::PreemptiveCheck(Thread *newThread)
{
    if (kernel->currentThread->getStatus() == RUNNING &&
        newThread->GetApproximateBurstTime() < kernel->currentThread->GetApproximateBurstTime())
    {
        DEBUG(dbgExpr, "[E] Tick [" << kernel->stats->totalTicks << "]: Thread [" << kernel->currentThread->getID() << "] is now selected for execution, thread [" << newThread->getID() << "] is preempted, and it has executed [" << newThread->GetExecTick() << "] ticks");
        // kernel->interrupt->YieldOnReturn();
        kernel->interrupt->OneTick(); // To simulate the time taken by the context switch
        kernel->currentThread->setStatus(READY);
        kernel->currentThread->preemtion = 1;
        PutIntoQueue(kernel->currentThread);
        Run(newThread, FALSE);
    }
}