Operating System Final Project

github好讀版

組員

1. 黃苡溱 112065534
2. 王斾頤 112065522
3. 李維文 110060033

---

Table of Contents

Part 1 - Trace Code

1-1. New -> Ready
1-2. Running -> Ready
1-3. Running -> Waiting
1-4. Waiting -> Ready
1-5. Running -> Terminated
1-6. Ready -> Running

Part 2 - Implementation

2-1. Initialization-of-threads
2-2. Preemption-and-scheduling
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 is0meaning that the resource is not available, the current thread is appended to the waiting queue. When the semaphore value is bigger than0, 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

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

Ready → Running

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

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 YieldOnReturnto 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

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

Trace

Semaphore::V()
kernel->scheduler->ReadyToRun(queue->RemoveFront())
↓
Scheduler::ReadyToRun(Thread*)

Scheduler::ReadyToRun()

---

2-3. Termination of threads

Running → Terminated

Similar to Running → Waiting

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