# Operating System Final Project
[github好讀版](https://hackmd.io/@peiyeeee/OSFinal_2024)
## 組員
1. 黃苡溱 112065534
2. 王斾頤 112065522
3. 李維文 110060033
---
## Table of Contents
[Part 1 - Trace Code](#Part-1---Trace-Code)
: [1-1. New -> Ready ](#1-2-Running--gt-Ready)
[1-2. Running -> Ready ](#1-2-Running--gt-Ready)
[1-3. Running -> Waiting ](#1-3-Running--gt-Waiting)
[1-4. Waiting -> Ready](#1-4-Waiting--gt-Ready)
[1-5. Running -> Terminated](#1-5-Running--gt-Terminated)
[1-6. Ready -> Running](#1-6-Ready--gt-Running)

[Part 2 - Implementation](##Part-2---Implementation)
: [2-1. Initialization-of-threads](#2-1-Initialization-of-threads)
[2-2. Preemption-and-scheduling](#2-2-Preemption-and-scheduling)
[2-3. Termination-of-threads](#2-3-Termination-of-threads)

---
## Part 1 - Trace Code
### Data Structure (listing some important variables)
* UserProgKernel: A subclass inherit from ThreadKernel, containing the following variables:

	bool debugUserProg;
	Thread* t[30];
	char* execfile[30];
	int threadPriority[30];
	int threadRemainingBurstTime[30];
	int threadNum;
	int execfileNum;
	char *consoleIn;
	char *consoleOut;

* ThreadKernel

	Thread *currentThread;		// the thread holding the CPU
	Scheduler *scheduler;		// the ready list
	Interrupt *interrupt;		// interrupt status
	Statistics *stats;		// performance metrics
	Alarm *alarm;

* Thread: Data structure for managing thread, containing the following variables and functions

	 int *stackTop;
	 void *machineState[MachineStateSize];	//​​ MachineStateSize is defined to 75
	 int *stack; 
	 ThreadStatus status;
	 char* name;
	 int ID;
	 int Priority;
	 int WaitTime;
	 int RemainingBurstTime;
	 int RunTime;
	 int RRTime;
	 void StackAllocate(VoidFunctionPtr func, void *arg);
	 AddrSpace *space;

---

### 1-1. New -> Ready

#### UserProgKernel::InitializeAllThreads() (userprog/userkernel.cc)
loop over every execute file, and then call `InitializeOneThread()`. After initializing all threads, we terminate the currentThread (See `ThreadKernel`).


#### UserProgKernel::InitializeOneThreads(char*, int, int) (userprog/userkernel.cc)
Called by `InitializeOneThread()`, we initialize the thread by requiring new `AddrSpace()` (see `Thread`), and then fork it by calling `Fork()`. Lastly, the function increases the `threadNum` (a variable keeps track of the number of threads).
>

#### ThreadFork::Fork(VoidFunctionPtr, void*) (threads/thread.cc)
When `Fork()` is called, we allocate the function (the procedure to run) and the arguments to a stack. Then, since we want `ReadyToRun()` to be an atomic function, we disable the interrupt status by `SetLevel(IntOff)` and store the old Status to oldLevel (`SetLevel()` Returns the previous state).


There are two interrupt status : IntOn / IntOff defined in `interrupt.h`


And now we ask the scheduler to transfer the thread to Ready state. Finally, we restore the interrupt `SetLevel()` with the value stored in oldLevel.


#### Thread::StackAllocate(VoidFunctionPtr, void*) (threads/thread.cc)
The following objects and variables are defined in Thread: `stack`, `stackTop`, `StackSize`, `machineState`. We first allocate an array to the stack defined in the Thread data structure.


Since we’re using x86 architecture to test the code, we only trace this part. Due to the size of the newly allocated function is 4, the stackTop is set to `stack + StackSize - 4` . After setting up the stack, we switch to the `ThreadRoot`. To avoid overflow, the stack has a fencepost.

`STACK_FENCEPOST`

Finally we set the machineStates, they are defined in `switch.h`

The Stack is implemented as follows

image source: https://hackmd.io/@LJP/Sy6IzZ95B#Trace6_StackAllocate

#### Scheduler::ReadyToRun(Thread*) (threads/scheduler.cc)
The TODO part. According to the priority, put them in the corresponding ReadyQueue.


---
### 1-2. Running -> Ready

#### Machine::Run() (machine/mipssim.cc)
Enters an infinite loop, continuously executing instructions and handling clock interrupts. `OneTick()` is called when an interrupt is re-enabled or when a user instruction ends.


#### Interrupt::OneTick() (machine/interrupt.cc)
Saves the current machine status to `oldStatus` and advances the simulated time based on the current status (system mode or user mode). If in system mode, increments `totalTicks` and `systemTicks` by `SystemTick`. If in user mode, increments `totalTicks` and `userTicks` by `UserTick`. Checks whether there are pending interrupts and handles context switches if requested.


#### Thread::Yield() (threads/thread.cc)
Allows the currently executing thread to yield the CPU and perform a context switch. It first disables interrupts and saves the current interrupt status then ensures that the current thread is the one running. In the TODO part, we need to put the current thread into the ready state, find the next thread to run. After that we can restore the previous interrupt status.


#### Scheduler::FindNextToRun() (threads/scheduler.cc)
Finds the next thread to run from the ready list.


#### Scheduler::ReadyToRun(Thread*) (threads/scheduler.cc )
Finds the next thread to run from the ready list. If the ready list is empty, it returns `NULL`. Otherwise, it removes and returns the first thread from the ready list (ready list is a simple FIFO queue).


#### Scheduler::Run(Thread*, bool) (threads/scheduler.cc )
Implements the context switch between the current running thread and the next thread to be run. It first saves the current thread, disables interrupts, and marks the current thread for deletion if it is finished. It then saves the user program state if applicable, checks for stack overflow, switches to the next thread, performs the context switch, and finally checks if the previous thread needs to be cleaned up and restores the user program state if applicable.


---
### 1-3. Running -> Waiting

#### ExceptionHandler(ExceptionType) case SC_PrintInt (userprog/exception.cc)
When the user program makes this system call, it is requesting to read the integer value from register 4, print the integer to the console using `PutInt()` and log a debug message if the corresponding debug flag is enabled. It allows the user program to output integers to the console via system calls, with debugging support to help developers trace the behavior of their program.


#### SynchConsoleOutput::PutInt() (userprog/synchconsole.cc)
This function converts an integer to a string and outputs it character by character to the console. Meanwhile, it uses a `lock->Acquire()` and `lock-Release()` to ensure thread-safe access to the console and a semaphore to wait for each character to be processed before continuing.


#### ConsoleOutput::PutChar(char) (machine/console.cc)
Write a character to the output file and set a flag `putBusy` to prevent concurrent writes. It schedules an interrupt to clear the flag after a specified time for ensuring orderly character output.


#### Semaphore::P() (threads/synch.cc)
The line `IntStatus oldLevel = interrupt-SetLevel(IntOff);` disables interrupts and saves the previous state to ensure that the following operations are not interrupted. If the semaphore value is`0`meaning that the resource is not available, the current thread is appended to the waiting queue. When the semaphore value is bigger than`0`, it implements `value--` and re-enables interrupts to allow the thread to proceed.


#### SynchList<T>::Append(T) (threads/synchlist.cc)
Add an item to the list by first acquiring a lock to ensure exclusive access, and then signal any waiting threads that the list is no longer empty. Lastly, it releases the lock and allows other threads to access the list.


#### Thread::Sleep(bool) (threads/thread.cc)
The two assertions are for ensuring that the current thread is indeed the one calling this function and that interrupts are turned off. Put the current thread to sleep through marking the status as `BLOCKED` and loop search for the next thread to run. If no thread is found, it calls `idles()` until an interrupt occurs. If the next thread is found, it updates `RemainingBurstTime`, reset some value of `current_thread` and performs the context switch to it within the `Run(nextThread, finishing);` function.


#### Scheduler::FindNextToRun() (threads/scheduler.cc)
Check the ready list for the next thread to run and ensure interrupts are turned off. If the ready list is empty, returns `NULL`; otherwise, it returns the next thread by removing it from the front of the ready list.


#### Scheduler::Run(Thread*, bool) (threads/scheduler.cc)
The function switches the CPU from the current thread to the next thread and ensures interrupts are turned off. It handles finishing threads, saves and restores user program state, and checks if the old thread has an undetected stack overflow before performing the context switch.


---
### 1-4. Waiting -> Ready

#### Semaphore::V() (threads/synch.cc)
Disables interrupts and saves the current interrupt status to oldLevel. Disabling interrupts prevents race conditions during the critical section. Checks if the waiting queue is empty. If the queue is not empty, it removes the first thread from the queue and makes it ready to run. Increases the `semaphore` value and re-enable the interrupts.


#### Scheduler::ReadyToRun(Thread*) (threads/scheduler.cc)
Finds the next thread to run from the ready list. If the ready list is empty, it returns `NULL`. Otherwise, it removes and returns the first thread from the ready list (ready list is a simple FIFO queue).


---
### 1-5. Running -> Terminated

#### ExceptionHandler(ExceptionType) case SC_Exit (userprog/exception.cc)
Handles many types of exceptions. The parameter which specifies the type of exception.


Under the `SC_Exit` case, it reads the value from register 4, prints the information in the console, and terminates the current thread.


#### Thread::Finish() (threads/thread.cc)
Called when a thread is done. It disables interrupts, ensures the current thread is the running thread, and then puts the thread to sleep.


#### Thread::Sleep(bool) (threads/thread.cc)
Disables interrupts, ensures the current thread is the running thread, outputs debug information, sets the thread status to blocked, and then looks for the next thread to run. If no runnable thread is found, it waits for an interrupt. Finally, it updates the `remainingBurstTime` and performs a context switch to the next thread.


#### Scheduler::FindNextToRun() (threads/scheduler.cc)
Finds the next thread to run from the ready list.


#### Scheduler::Run(Thread*, bool) (threads/scheduler.cc)
Implements the context switch between the current running thread and the next thread to be run. It first saves the current thread, disables interrupts, and marks the current thread for deletion if it is finished. It then saves the user program state if applicable, checks for stack overflow, switches to the next thread, performs the context switch, and finally checks if the previous thread needs to be cleaned up and restores the user program state if applicable.


---
### 1-6. Ready -> Running
#### Scheduler::FindNextToRun() (threads/scheduler.cc)
Find the next thread in the `ReadyQueue`.


#### Scheduler::Run(Thread*, bool) (threads/scheduler.cc)
Function that switches the current thread to the next thread. The interrupt is turned off first. Then if the current thread has finished, the current thread will be set to `toBeDestroyed`. If the current thread is a user program, we save its state. Finally, after checking for overflow, the next thread is switched to the current thread, and the next thread is set to running state. Then we may call the `SWITCH()` function to switch the context of current and next thread.


#### SWITCH(Thread*, Thread*) (threads/switch.s)
Initially, we have the following main stack that stores pointers to the threads.
The return address is at esp, `thread *t1` is at 4(esp), `thread *t2` is at 8(esp).


1. Store the contexts of `t1` from the registers to its own stack.

We save whatever is in eax to a temporary `storage _eax_save`. Then, the pointer to `t1` is moved to eax. And by referencing the location of `t1`, we can store the registers’ value to `t1`’s memory(`t1`’s own stack) with

movl %ebx, _EBX(%eax)
movl %ecx, _ECX(%ecx)
and so on….

The value of _EBX is defined in switch.h with the following values:
These value are associated with the threads’ stack, which is defined in the thread class:

_ESP(%eax) is interpreted as 0(%eax), which stores int *stackTop.
_EAX(%eax) stores machineState[0]
_EBX(%ebx) stores machineState[1]
and so on…

Then we restore the value of `%eax` back from `_eax_save`, and store the return value of the main stack to `_PC(%eax)`. (possibly `machineState[7]`)

2. Move the contexts of `t2` from its stack to the registers

We first load the pointer of `t2` to `%eax`. Then the following code load the context of `t2` back to the registers:

movl _EAX(%eax), %ebx
movl %ebx _eax_save
movl _EBX(%ebx), %ebx
and so on and so forth….
Note that the esp of the machine is switched to pointing to the stacktop of `t2`.
Finally, the ret instruction pop the value of `%esp` and let `%esp = %esp + 4`. Therefore, now the `%esp` is at `ThreadRoot + 4`. (or `stackTop + 4`)
The following Assembly code is written in `AT&T` syntax, which implies that it is written in the following style:

instruction [source] [destination]

Note that this is different from Intel Syntax, which reverses the source and destination.

---

## Part 2 - Implementation
### General Consideration
The main goal of Part-2 is to implement the scheduler. We separate the implementation into three main segments: 1. the **initialization of threads**,2. the **preemption and scheduling of threads**, and 3. the **termination of threads**. Please refer to the following sections for further discussion.

### 2-1. Initialization of threads

#### UserProgKernel::UserProgKernel()
When detecting the flag `-epb`, we may set the file name, the priority and the remaining burst time to the input value.


#### New → Ready
:::spoiler Trace
UserProgKernel::InitializeAllThreads()
↓
UserProgKernel::InitializeOneThreads(char*, int, int)
↓
ThreadFork::Fork(VoidFunctionPtr, void*)
↓
UserProgKernel::ForkExecute()
↓
Thread::StackAllocate(VoidFunctionPtr, void*)
↓
Scheduler::ReadyToRun(Thread*)
:::
#### UserProgKernel::IntializeOneThread()
Add a new thread, then set the priority, burst time according to the input value. Since they have not been executed, the waiting time, run time and RR time are set to 0.


#### UserProgKernel::ForkExecute()
Execute the thread using `t->space->Execute`.

#### Scheduler::ReadyToRun()
We will mention it in [2-2.](#2-2-Preemption-and-scheduling)

---
### 2-2. Preemption and scheduling

#### Ready → Running
:::spoiler Trace
Scheduler::FindNextToRun()
↓
Scheduler::Run(Thread*, bool)
↓
SWITCH(Thread*, Thread*)
:::
#### Scheduler::FindNextToRun()

#### Scheduler::Run()
The `Run` function manages thread context switching. It saves the current thread `oldThread`, verifies interrupt disablement, and marks threads for deletion if `finishing`. After ensuring stack overflow detection for `oldThread`, it switches execution to `nextThread`, updates statuses, logs the switch, and asserts interrupt state upon return. It also cleans up any finished threads and restores user states if applicable.

---
#### Running → Ready
:::spoiler Trace
Machine::Run()
`kernel->interrupt->OneTick();`
↓
Interrupt::OneTick()
`kernel->currentThread->Yield();`
↓
Thread::Yield()
`kernel->scheduler->ReadyToRun(this);`
`nextThread = kernel->scheduler->FindNextToRun();`
↓
Scheduler::ReadyToRun(Thread*)
↓
Scheduler::FindNextToRun()
:::

Current thread will yield its exection while interrupt happend.

#### Thread::Yield()
The preempted thread need to Update RemainingBurstTime and RunTime while it return to ready state. `int old` stores the remaining burst time of the current thread. Then we updates the remaining burst time by subtracting the runtime. After context switch, we reset the runtime of the current thread by `setRunTime(0)`.

#### Scheduler::FindNextToRun()

**Scheduling** is the process of determining which thread should run next. The scheduler in this project uses multiple queues with different priorities:
* L1 : Uses SRTN.
* L2 : Uses FCFS.
* L3 : Uses RR with time quantum 200 tick.

The `FindNextToRun` function checks each queue in order of priority (L1, L2, then L3) and selects the first non-empty queue to return a thread from. This ensures that higher priority queues are given preference during the scheduling process.


#### Scheduler::ReadyToRun()
Place a thread into the appropriate ready queue based on its priority. The Function also handles the potential preemption of the currently running thread if a higher priority thread is added. Consider a thread that has just completed I/O operations and is now ready to run again. When this thread is added back to the ready queue, we reset its wait time to zero by `setWaitTime(0)`


#### Alarm::CallBack()
The `CallBack()` function **executes every 100 ticks**.
It starts by retreiving the kernel's interrupt handler and checking if the current system status is IdleMode.
If the system idle and no pending interrupts remain, the timer is disabled. Otherwise, it increases thread's runtime by 100 ticks, calls `UpdatePrioirty()`and triggers a context switch with `YieldOnReturn`to preempt the current thread and allow others to run.

#### Scheduler::UpdatePriority()
`UpdatePriority()` can be separated into three section:
1. Update WaitTime
2. Update Priority
3. Check for Preemption

When the function is called, we add 100 to all the threads in the ReadyQueue with the help of ListIterators. Then, we check whether the threads have their `waitTime` larger than 400. If so, we update their priority by 10 and reset the `waitTime` to 0. Since updating priority may lead to the change of queue level, we check for it. If the thread requires so, we remove it from the current queue and call `ReadyToRun()` in order to insert it to the target queue.

Finally, when all dust is settled, we should check for preemption.
According to the priority of the `currentThread`, the rules are stated as follows:

If currentThread is in L1, it could possibly be preempted by a thread in L1. Therefore, we first check whether L1 is empty, and then compare the `Front()` of L1(which is the thread with the shortest `RemainingBurstTime`) with currentThread. If Front() has the shorter `RemainingBurstTime`, we set `YieldOnReturn()`.

If `currentThread` is in L2, it may be preempted by L1, but not by L2, since L2 is not preempive. Therefore, the only task here is to check whether L1 is empty. If not, we call `YieldOnReturn()`.

If the former two criterion does not met, we know `currentThread` should be in L3. There are two possible cause of `currentThread` being preempted here. 1. There are threads in L1 or L2. 2. There are threads in L3 and that the `currentThread` has run for more than 200 ticks.(`RunTime > 200`) If either of the requirement are met, we call `YieldOnReturn()`.


---
#### Running → Waiting

:::spoiler Trace
SynchConsoleOutput::PutInt()
`lock->Acquire()`
↓
Lock::Acquire() in *threads/synch.cc*
`semaphore->P()`
↓
Semaphore::P()
`queue->Append(currentThread);` to *SynchList<T>::Append(T)*
`currentThread->Sleep(FALSE);`
↓
Thread::Sleep()
`while ((nextThread = kernel->scheduler->FindNextToRun()) == NULL)`
`kernel->scheduler->Run(nextThread, finishing)`
↓
Scheduler::FindNextToRun()
↓
Scheduler::Run(Thread*, bool)
:::

#### Thread::Sleep()
Need to recalculate `RemainingBurstTime` and `RunTime` when the thread switch to waiting state.

#### Scheduler::FindNextToRun()

#### Waiting → Ready
:::spoiler Trace
Semaphore::V()
`kernel->scheduler->ReadyToRun(queue->RemoveFront())`
↓
Scheduler::ReadyToRun(Thread*)
:::

#### Scheduler::ReadyToRun()

---
### 2-3. Termination of threads
#### Running → Terminated
Similar to Running → Waiting
:::spoiler Trace
ExceptionHandler(ExceptionType) case SC_Exit
`kernel->currentThread->Finish();`
↓
Thread::Finish()
`Sleep(TRUE)`
↓
Thread::Sleep()
`while ((nextThread = kernel->scheduler->FindNextToRun()) == NULL)`
`kernel->scheduler->Run(nextThread, finishing)`
↓
Scheduler::FindNextToRun()
↓
Scheduler::Run(Thread*, bool)
:::

#### Thread::Sleep()
#### Scheduler::FindNextToRun()
#### Scheduler::Run()

---
## ScreenShot