OS161 provides a simple round-robin scheduler by default. It works like this:
$OS161_SRC/kern/thread/clock.cwill be periodically called (from hardware clock interrupt handler)
Two functions may be called there after:
scheduleto change the order the threads in ready queue, which currently does nothing
thread_consider_migratonto enable thread migration among CPU cores
Then it will call
thread_yieldto cause the current thread yield to another thread
We need to play with the
schedule function to give interactive threads higher
Why give priority to interactive threads?
There are two reasons about this (at least the two in my mind) :
Your time is more valuable than computer's. So in general, we should first serve those threads that interact with you. For example, you don't want to wait the computer in a shell while it's busy doing backup, right?
Interactive threads tend to be I/O bound, which means they often get stuck waiting for input or output. So they normally fail to consume their granted time slice. Thus we can switch to computation bound threads when they stuck and boost computer utilization.
How can we know whether a thread is interactive or not?
As said above, interactive threads are normally I/O bound. So they often need to sleep a lot.
$OS161_SRC/kern/thread/thread.c, we can see that
thread_switch is used to actually
switch between threads. The first argument is
newstate, which give some hints
about the current thread.
S_READY, it means that current thread has consumed all
its time slice and is forced to yield to another thread (by hardware clock).
So we can guess that it's not interactive, or, it's computation intensive.
S_SLEEP, then it means current thread offers to
yield to another thread, maybe waiting for I/O or a mutex. Thus we can guess
that this thread is more interactive, or, it's I/O intensive.
So by the
newstate, we can make a good guess of current thread.
How to implement it?
Multi-Level Feedback Queue seems to be a good enough algorithm in this case.
We can add a priority field in
struct thread and initiate it as medium
thread_create. Then in
thread_swith, we can adjust current
thread's priority by the
- If it's
S_SLEEPthen we increase current thread's priority.
- Otherwise, if it's
S_READYthen we decrease current thread's priority.
Of course, we can only support a finite priority level here, so be careful
with boundary case. For example, if current thread is
already the highest priority and still request
S_SLEEP, then we just leave it
in that priority.
schedule, we need to find the thread with highest priority
among all the threads in
curcpu->c_runqueue, and bring it to head.
Current CPU's run queue is organized as a double linked list with head
$OS161_SRC/kern/include/threadlist.h provides several useful interface to
let us manipulate the list. Find a maximum/minimum number among a list
is so simple that I won't provide any details here. But note that the
head element is just a place holder. So you may want to start from
curcpu->c_runqueue.tl_head.tln_Next and stop when
elem->tln_next == NULL.
Once find the thread, we need to bring it to list head so we can
thread_switch unchanged. A
threadlist_remove followed by
threadlist_addhead will be sufficient here.
One problem of MLFQ is starvation. So you may want to periodically reset all threads' priority to medium level for fairness.
That's all. Here's just a work solution. Much work has be done if you want better scheduling for performance.