$39
The default CPU scheduling algorithm of Nachos is a simple round-robin scheduler with 100 ticks time quantum. The goal of this MP is to replace it with a multilevel feedback queue, and understand the implementation of process lifecycle management and context switch mechanism.
1-1. New→Ready
Kernel::ExecAll()
↓
Kernel::Exec(char*)
↓
Thread::Fork(VoidFunctionPtr, void*)
↓
Thread::StackAllocate(VoidFunctionPtr, void*)
↓
Scheduler::ReadyToRun(Thread*)
1-2. Running→Ready
Machine::Run()
↓
Interrupt::OneTick()
↓
Thread::Yield()
↓
Scheduler::FindNextToRun()
↓
Scheduler::ReadyToRun(Thread*)
↓
Scheduler::Run(Thread*, bool)
1-3. Running→Waiting (Note: only need to consider console output as an example)
SynchConsoleOutput::PutChar(char)
↓
Semaphore::P()
↓
List<T>::Append(T)
↓
Thread::Sleep(bool)
↓
Scheduler::FindNextToRun()
↓
Scheduler::Run(Thread*, bool)
1-4. Waiting→Ready (Note: only need to consider console output as an example)
Semaphore::V()
↓
Scheduler::ReadyToRun(Thread*)
1-5. Running→Terminated (Note: start from the Exit system call is called)
ExceptionHandler(ExceptionType) case SC_Exit
↓
Thread::Finish()
↓
Thread::Sleep(bool)
↓
Scheduler::FindNextToRun()
↓
Scheduler::Run(Thread*, bool)
1-6. Ready→Running
Scheduler::FindNextToRun()
↓
Scheduler::Run(Thread*, bool)
2.5↓
SWITCH(Thread*, Thread*)
↓
(depends on the previous process state, e.g.,
[New,Running,Waiting]→Ready)
↓
for loop in Machine::Run()
Note: switch.S contains the instructions to perform context switch. You must understand and describe the purpose of these instructions in your report. (You can try to understand the x86 instructions first. Appendix C and the MIPS version equivalent to x86 can get a lot of help.)
2-1. Implement a multilevel feedback queue scheduler with aging mechanism as described below:
(a) There are 3 levels of queues: L1, L2 and L3. L1 is the highest level queue, and L3
is the lowest level queue.
ti = 0.5 * T + 0.5 * ti-1 (type double) , i > 0 , t0 = 0
Where T is the total running ticks within a CPU burst and the NachOS kernel statistic can be used to calculate the ticks. Update the approximated burst time when the thread becomes waiting state, stop accumulating T when the thread becomes ready state, and resume accumulating T when the thread moves back to the running state. If there is any ready thread with the approximated remaining burst time lower than the current thread, the current thread should be preempted. The approximated remaining burst time can be calculated by the approximated burst time minus its running burst time T.
2-2. Add a command line argument -ep for nachos to initialize priority of process. E.g., the command below will launch 2 processes: test1 with initial priority 40, and test2 with initial priority 80.
$ ../build.linux/nachos -ep test1 40 -ep test2 80
2-3. Add a debugging flag z and use the DEBUG('z', expr) macro (defined in debug.h) to print
following messages. Replace {...} to the corresponding value.
(a) Whenever a process is inserted into a queue:
$ cp -r NachOS-4.0_MP2 NachOS-4.0_MP3
const int ConsoleTime = 1;
$ cd NachOS-4.0_MP3/code/test
$ cp /home/os2023/share/hw3t{1,2,3}.c ./
Appendix A
Note that the sample test case may have too little loop to trigger the aging mechanism. You can change the test case code by yourself.
$ |
../build.linux/nachos -ep hw3t1 0 -ep hw3t2 0 |
|
#L3 |
|
|
|
|
|
|
|
|
|
|
$ |
../build.linux/nachos -ep hw3t1 50 -ep hw3t2 |
50 |
#L2 |
|||
|
|
|
|
|
|
|
$ |
../build.linux/nachos -ep hw3t1 50 -ep hw3t2 |
90 |
#L2 |
|||
|
|
|
|
|
||
$ |
../build.linux/nachos -ep hw3t1 100 -ep hw3t2 100 |
#L1 |
||||
|
|
|
|
|
|
|
$ |
../build.linux/nachos -ep hw3t1 40 |
-ep hw3t2 |
55 |
#L3 → L2 |
||
|
|
|
|
|
|
|
$ |
../build.linux/nachos -ep hw3t1 40 |
-ep hw3t2 |
90 |
#L3 → L2 |
||
|
|
|
|
|
|
|
$ |
../build.linux/nachos -ep hw3t1 90 |
-ep hw3t2 |
100 |
#L2 → L1 |
||
|
|
|
|
|
|
|
$ |
../build.linux/nachos -ep hw3t1 60 |
-ep hw3t3 |
50 |
#L2 |
Appendix C
x86 registers (32bit)
Register |
Description |
|
|
eax, ebx, ecx, edx, esi, edi |
general purpose registers |
|
|
esp |
stack pointer |
|
|
ebp |
base pointer |
|
|
x86 instructions (32bit, AT&T)
Instruction |
|
Description |
|
|
|
movl %eax, %ebx |
move 32bit value from register eax to register ebx |
|
|
|
|
movl 4(%eax), %ebx |
move 32bit value at memory address pointed by (the value of register eax |
|
plus 4), to register ebx |
||
|
||
|
|
|
ret |
set CPU program counter to the memory address pointed by the value of |
|
register esp |
||
|
||
|
|
|
pushl %eax |
subtract register esp by 4 (%esp = %esp - 4), then move 32bit value of |
|
register eax to the memory address pointed by register esp |
||
|
||
|
|
|
popl %eax |
move 32bit value at the memory address pointed by register esp to register |
|
eax, then add register esp by 4 (%esp = %esp + 4) |
||
|
||
|
|
|
call *%eax |
push CPU program counter + 4 (return address) to stack, then set CPU |
|
program counter to memory address pointed by the value of register eax |
||
|
||
|
|
|
x86 calling convention (cdecl) |
|
|
Item |
|
Description |
|
|
|
Caller passes function parameters |
Caller pushes the arguments to stack in the descending order. |
|
|
|
|
|
|
Callee reads the arguments from the memory address pointed by |
Callee catches function parameters |
(register esp + 4) in the ascending order. By the way, the value |
|
of memory address pointed by register esp is the return address |
||
|
|
|
|
|
described above (call instruction). |
|
|
|
Function parameters cleaning up |
Caller is responsible for cleaning up the arguments (pop). |
|
|
|
|