A CPU Scheduler is a core component of any multiprogramming operating system kernel. It is important to understand the details about the CPU scheduler to know dynamic behaviors of the operating system.
In this project, C programs were written to simulate the following CPU scheduling algorithms for a single CPU machine:
CPU scheduling algorithm not included in this project:
Based on a given static CPU workload, the programs calculate the following:
CPU scheduling is the basis of multiprogramming. By switching the CPU among processes, the operating system can make the computer more productive. The idea is relatively simple, the objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.
CPU scheduling consists of two components:
Process execution consists of a cycle of CPU execution and I/0 wait. Processes alternate between these two states until the final CPU burst that ends with a system request to terminate execution.
The durations of CPU bursts have been measured extensively and they vary greatly from process to process and from computer to computer. However, they tend to have a frequency curve similar to that shown below:
CPU scheduling decisions may take place when a process:
Preemptive scheduling takes place in 1, 2, 3, 4.
Non-preemptive scheduling takes place under 1 and 4.
CPU utilization | keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system). |
Throughput | Number of processes that complete their execution per time unit. |
Turnaround time | amount of time to execute a particular process. The interval from the time of submission of a process to the time of its completion. |
Waiting time | amount of time a process has been waiting in the ready queue. |
Response time | amount of time it takes from when a request was submitted until the first response is produced, not the final output (for time-sharing environment). |
The First-Come, First-Served (FCFS) scheduling algorithm is the simplest CPU-scheduling algorithm. The process that requests the CPU first is allocated the CPU first. FCFS is easy to implement (as a FIFO queue) but it results in long waits in most cases and suffers convoy effect.
This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.
Example of FCFS
Process | Burst Time (ms) |
---|---|
P1 | 24 |
P2 | 3 |
P3 | 3 |
Suppose that the processes arrive at time 0 in the order: P1, P2, P3. The Gantt Chart for the scheduling is:
Waiting time:
Process | Burst Time (ms) | Wait Time (ms) |
---|---|---|
P1 | 24 | 0 |
P2 | 3 | 24 |
P3 | 3 | 27 |
Average waiting time: (0 + 24 + 27) / 3 = 17 ms
Now suppose that the processes arrive at time 0 in the order: P2, P3, P1. The Gantt Chart for the scheduling is:
Waiting time:
Process | Burst Time (ms) | Wait Time (ms) |
---|---|---|
P1 | 24 | 6 |
P2 | 3 | 0 |
P3 | 3 | 3 |
Average waiting time: (6 + 0 + 3) / 3 = 3 ms
As you can see, the average waiting time reduction is substantial.
The FCFS scheduling algorithm is nonpreemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/0.
The Round-Robin (RR) scheduling algorithm is designed especially for timesharing 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 defined. 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.
Fairness: If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.
Time Quantum and Context Switch Time
Example of RR with Time Quantum q = 20
Process | Burst Time (ms) |
---|---|
P1 | 53 |
P2 | 17 |
P3 | 68 |
P4 | 24 |
Suppose that the processes arrive at time 0 in the order: P1, P2, P3, P4. The Gantt Chart for the scheduling is:
Waiting time:
Process | Burst Time (ms) | Wait Time (ms) |
---|---|---|
P1 | 53 | 81 |
P2 | 17 | 20 |
P3 | 68 | 94 |
P4 | 24 | 97 |
Average waiting time: (81 + 20 + 94 + 97) / 4 = 73 ms
RR Performance:
If q large, then RR resembles FCFS.
If q small, then there are too many context switches, so overhead is high.
A multilevel queue scheduling algorithm partitions the ready queue into several separate queues.
In a multilevel feedback queue scheduling algorithm a process can move between the various queues; aging can be implemented this way.
This form of aging prevents starvation or indefinite blocking, one the major problems with priority scheduling algorithms.
Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.
Multilevel-feedback-queue scheduler defined by the following parameters:
The multilevel feedback queue scheduling algorithm is the most general CPU scheduling algorithm. It can be configured to match a specific system under design.
Example of Multilevel Feedback Queue
Three queues are implemented as follows:
Each line in the CPU workload data files represent one process with the following format: (all numbers are in unit of millisecond)
pid arrival_time 1st_CPU_burst (1st_IO_burst) 2nd_CPU_burst (2nd_IO_burst) ...
e.g.
0 0 4 (100) 12 (67) 2 ... 1 13 7 (210) 20 (23) 67 ...
where each I/O burst includes both the time waiting in the device queue and the time spent in actual I/O operations.
If two or more processes are identical in terms of scheduling criterion, priority is given to the process which has lowest pid number.