ated by some ï¬xed range of numbers, such as 0 to 7 or 0 to 4,095. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. This difference can lead to confusion. In this text, we assume that low numbers represent high priority.
As an example, consider the following set of processes, assumed to have arrived at time 0 in the order P1, P2, ···, P5, with the length of the CPU time given in milliseconds:
| Process | CPU Time | Priority |
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
Using priority scheduling, we would schedule these processes according to the following Gantt chart:
The waiting time is 6 milliseconds for process P1, 0 milliseconds for process P2, 16 milliseconds for process P3, 18 milliseconds for process P4, and 1 millisecond for process P5. Thus, the average waiting time is (6+0+16+18+1)/5 = 8.2 milliseconds. The average waiting time is 8.2 milliseconds.
4. Round-Robin Scheduling
The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but preemption is added to enable the system to switch between processes. A small unit of time, called a time quantum or time slice, is deï¬ned. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is treated as a circular queue.
The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum. To implement RR scheduling, we again treat the ready queue as a FIFO queue of processes. New processes are added to the tail of the ready queue.
The CPU scheduler picks the ï¬rst process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process. One of two things will then happen. The process may have a CPU burst of less than 1 time quantum. In this case, the process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. If the CPU burst of the currently running process is longer than 1 time quantum, the timer will go off and will cause an interrupt to the operating system. A context switch will be executed, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue.
The average waiting time under the RR policy is often long. Consider the following set of processes that arrive at time 0, with the length of the CPU time given in milliseconds:
| Process | CPU Time |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
If we use a time quantum of 4 milliseconds, then process P1 gets the ï¬rst 4 milliseconds. Since it requires another 20 milliseconds, it is preempted after the ï¬rst time quantum, and the CPU is given to the next process in the queue, process P2. Process P2 does not need 4 milliseconds, so it quits before its time quantum expires. The CPU is then given to the next process, process P3. Once each process has received 1 time quantum, the CPU is returned to process P1 for an additional time quantum. The resulting RR schedule is as follows:
Let’s calculate the average waiting time for this schedule. P1 waits for 6 milliseconds (10-4), P2 waits for 4 milliseconds, and P3 waits for 7 milliseconds. Thus, the average waiting time is 17/3 = 5.66 milliseconds.
To learn more about CPU Scheduling, check the following sites:
CPU Scheduling at http://www.eee.metu.edu.tr/~halici/courses/442/Ch2%20Process%20Scheduling.pdf
CPU Scheduling at http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/PDF-dir/ch5.pdf
Operating Systems Scheduling at http://web.cs.wpi.edu/~cs3013/c07/lectures/Section05-Scheduling.pdf
CPU Scheduling at https://www.youtube.com/watch?v=8Mi_xwdqYcg
First Come First Served – CPU Scheduling Algorithm at https://www.youtube.com/watch?v=KtuQpQwlmYM
Priority Scheduling – CPU Scheduling at https://www.youtube.com/watch?v=cNdEQKw4apM
Round Robin CPU Scheduling Tutorial at https://www.youtube.com/watch?v=aWlQYllBZDs
Learn CPU Scheduling – Shortest Job First at https://www.youtube.com/watch?v=wk8dhWE_kSc
CPU Scheduling at http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_CPU_Scheduling.html
Scheduling algorithms at http://www.it.uu.se/edu/course/homepage/oskomp/vt07/lectures/scheduling_algorithms/handout.pdf
