A few minor clarifications have been made to the handout. One place referred to "run queue" which is called the "ready queue" everywhere else.
If you're working in C or C++, be aware of getopt(3).
We already talked about FCFS, but here it is again, so it's all in one place.
First-Come, First-Served (FCFS) Scheduling
As its name suggests, the first process to arrive gets to go first. It is a non-preemptive FIFO system.
Example:
Consider 4 processes P1, P2, and P3 that have burst times of 24, 3, and 3, respectively.
If the processes arrive in the order P1, P2, P3, FCFS will service them in that order. We visualize this with a Gantt Chart:
|---------P1----------|-P2-|-P3-| 0 24 27 30
Waiting times: P1 = 0; P2 = 24; P3 = 27, Avg: (0+24+27)/(3)=17.
But what if the processes arrive P2, P3, P1?
|-P2-|-P3-|---------P1-----------| 0 3 6 30
Waiting times: P1 = 6; P2 = 0; P3 = 3, Avg: (6+0+3)/(3)=3.
FCFS characteristics:
Shortest-Job-First (SJF) Scheduling a.k.a. Shortest Process Next (SPN)
Choose the process with the smallest next CPU burst.
Non-premptive - process does not leave until its burst is complete
Preemptive - if a new process arrives with CPU burst length less than the remaining time of the currently executing process, we preempt. This is also known as Shortest Remaining Time First (SRTF).
Example:
Consider these processes
| Process | Arrival Time | Burst Time |
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
Non-preemptive:
|---P1---|P3|--P2--|--P4--| 0 7 8 12 16
Average waiting time: (0+6+3+7)/(4) = 4.
Preemptive (SRTF):
|-P1-|-P2-|P3|-P2-|--P4--|--P1---| 0 2 4 5 7 11 16
Average waiting time: (9+1+0+2)/(4) = 3.
SJF characteristics:
Priority Scheduling
Associate a priority with each process and always choose the one with the highest priority.
SJF/SRTF are examples of this, with the priority assigned as the burst times.
Biggest problem: starvation of low-priority jobs.
Can deal with this by aging - increasing the priority of processes that are not getting a chance.
Round Robin (RR) Scheduling
Each process gets a small unit of time on the CPU (the time quantum), typically 10-100 ms. After this time, the job is preempted and added to the end of the ready queue.
For n processes and quantum q, each process gets (1)/(n) of the CPU time. No process waits more than (n-1)q for its next turn on the CPU.
RR characteristics:
Example, q=20:
| Process | Burst Time |
| P1 | 53 |
| P2 | 17 |
| P3 | 68 |
| P4 | 24 |
|-P1-|-P2-|-P3-|-P4-|-P1-|-P3-|-P4-|-P1-|-P3-|-P3-| 0 20 37 57 77 97 117 121 134 154 162
What if we changed q to 5? Lots more context switching - more overhead. You will see this in Project 1.
Multilevel queues
We can partition the ready queue into a number of queues.
Perhaps with 2 queues, one can have an RR discipline for interactive jobs and the other can have a FCFS discipline for batch jobs.
Need to schedule among the queues as well, then.
Perhaps, a priority system - take jobs from high priority queues:
Multilevel Feedback Queues
This is a method used in real systems.
Processes may move among queues; aging may be implemented this way.
Parameters:
A simple example:
Three queues, Q0 has q=8 ms, Q1 has q=16 ms, Q2 is FCFS.
Processes enter at Q0, if not finished after 8 ms, move to Q1, if not finished after an additional 16 ms, move to Q2.
Q2 is served only when Q1 and Q0 are empty. Q1 is served only when Q0 is empty.
How does this benefit interactive jobs? How does this benefit CPU-bound jobs? I/O-bound jobs?
Fair-share scheduling
What if the goal is to divide the CPU fairly among a group of users, regardless of the number of processes they start?
Lottery scheduling and Fair-share scheduling are discussed in Tanenbaum and are the subject of a Homework 2 question.
This section has been moved to the notes for the next lecture.