When the scheduler thinks that the currently running thread has been long enough on the CPU, it selects a new thread to run. For BFS and time-sharing threads, the decision which thread should run next is based on a special number that is associated with every thread. BFS refers to this number as a virtual deadline. An O(n) lookup is performed to find a thread with the earliest virtual deadline.
Computing the virtual deadline for a thread
The BFS computes a new virtual deadline for a thread only when the thread runs out of its time slice. If we have a thread with nice value -20, then the new deadline is computed as follows:
new_deadline := now + rr_interval
Where the rr_interval is the time quantum the thread is allowed to run on CPU until it is preempted and now is the current time. If a virtual deadline for a task with nice value different than -20 is calculated, the rr_interval in the formula above is increased by 10% for every nice level. So if we have a thread with a default nice value 0, its virtual deadline is computed as follows:
new_deadline := now + rr_interval * 1.120
and that is effectively:
new_deadline := now + rr_interval * 6.727
An important thing to note about the virtual deadline calculations is that it does not consider the number of threads in the time-sharing queue. So it can sometimes calculate deadlines for threads and it will be impossible to meet all the deadlines if the threads use up their whole time quantums. The BFS does not give any guarantee that a given task will be scheduled by the time its virtual deadline passes. It uses the virtual deadline merely in the selection process to choose the next thread to run.
BFS and interactivity
What I personally like most about the BFS design is how it handles and favors interactive processes. When you look at the way how the original 4BSD scheduler calculates the CPU usage estimates and updates the thread priority based on these computations, I think you will also like the way how the BFS handles it:-)
The BFS simply needs nothing to do. By interactive threads, I mean the threads that sleep a lot. And if a thread sleeps long enough, its virtual deadline will be already over by the time the thread wakes up. Its deadline will be low in comparison to other (non-interactive) threads and therefore the BFS will choose it to run sooner.
What I still need to implement
In the previous paragraphs I described how I understand the BFS virtual deadline mechanism. I have all this already implemented in the current version of the FBFS scheduler. There are, however, some other important points that are relevant to the virtual deadline mechanism and that still need to be implemented.
- When the BFS chooses the next thread to run and looks for the thread with the lowest virtual deadline, it stops the O(n) lookup if it finds a thread whose deadline has already passed.
- When a thread in BFS does not use up its whole time quantum, it runs only with the remaining time quantum the next time it is scheduled. My FBFS implementation, that is based on the 4BSD scheduler, assigns a thread full time quantum every time the process is scheduled.
- The virtual deadline mechanism does not apply only to the time-sharing threads, but also to the idle threads.
I will try to address these points next week.