CSI3101 Operating Systems - Project 2: CPU Scheduling
Project 2: CPU Scheduling |
Project plan • Total 6 projects
|
|
Background: xv6 Process State
|
|
Background: xv6 CPU Scheduler |
|
Background: xv6 Scheduling Points
Exiting process (exit() in proc.c)
Blocked process (sleep() in proc.c)
Yielding CPU
– trap() in trap.cDo it by yourself using cscope
– In command mode of VIM, “:cs find c sched”
• This command will list up codes that invokes sched()
5
Background: xv6 Scheduling Examples
Every timer IRQ enforces an yield of a CPU
Process to be scheduled to RUNNING will be chosen in round-robin manner
tick tick tick tick
sleep()
tick
P1 P2 P3
exit()
RUNNING |
RUNNABLE |
SLEEP |
This slide is about the master branch (Project 0), NOT project1 branch
6
Objective 1: Priority Scheduler • Implement a priority scheduler in xv6 • Requirements – Schedule a process with the highest priority to run – Scheduling points
|
|
Objective 1: Priority Scheduler • Hints – Timer tick is left to occur but should not incur CPU scheduling – When you call sched(), you need to refer to the comments of the sched() function – When there is no runnable process, the scheduler context is running • In this case, invoking sched() may lead to unexpected behavior |
|
Objective 2: MLFQ Scheduler • Implement a MLFQ scheduler in xv6 • Requirements – 3 priority classes (high, medium, low) – Rule 4: If a job uses up an entire time slice while running, its priority is reduced (i.e. moves down one queue). If a job gives up the CPU before the time slice is up, it stays at the same priority level. – RR time slice is 4 ticks • A process’s time slice is reduced every time a timer tick happens, even if the process has not fully utilized the time provided by that timer tick. |
|
Objective 2: MLFQ Scheduler • Requirements (cont’d) – Scheduling points • Hints scheduling |
|
Hand-out Instruction
|
|
Hand-in Instruction
|
|
Hints (1/5) • Use gdb to debug your xv6 – You need to create a gdbinit file • $ mkdir -p ~/.config/gdb • $ echo “add-auto-load-safe-path /path/to/xv6/” > ~/.config/gdb/gdbinit – Then, run “make qemu-nox-gdb” – Open another terminal and run “gdb” |
|
Hints (2/5) • Identifying callsites – addr2line • Convert addresses into file names and line numbers • Example: $ addr2line -e kernel 80103eb1 8010427b 80105ded 80105afc 8010313f 8010328c |
|
Hints (3/5)
|
|
Hints (4/5) • xv6 has no dynamic memory allocator like malloc() in C memory – Before using kalloc(), please consider whether your required memory can be allocated statically – Memory leak should NOT occur. Hence, you need to free memory whenever the memory is no longer necessary |
|
