The single processor system, one process runs, and other processes wait until CPU is free. In a multiprocessor system, some process always runs and thus increases the CPU utilization.
If a process is waiting for the completion of some task, or I/O request, the CPU remains idle. To stop wasting CPU time, the CPU switch from the current process to another process. The CPU is one of the computer resources hence it must be scheduled in such a way that we get maximum performance.
CPU-I/O Burst Cycle
The process execution consists of CPU cycle and then followed by an I/O burst cycle, another CPU burst cycle, then followed by I/O burst cycle and so on. Finally, the CPU gets a request to terminate the execution.
IO bound process will have many long I/O bursts and short CPU bursts. A CPU bound process will have a few long CPU bursts and short I/O bursts. This affects the choice of the CPU scheduling algorithm.
CPU Scheduler
When CPU becomes idle the OS must select one of the processes from the ready queue with the help of a short-term scheduler or CPU scheduler.
The ready queue can be implemented using different data structures – a FIFO queue, a linked-list queue, or a tree and so on. The records in the queue are process control blocks (PCBs) of the processes.
Preemptive Scheduling
CPU-Scheduling decision may take place under 4 circumstances:
- Process switches from running to wait state. e.g IO request.
- Process switches from running to ready state. e.g interrupts.
- Process switches from wait to ready state. e.g IO for process completed.
- Process terminates.
We can ignore 1 and 4 because there is no chance of scheduling. It is called nonpreemptive or cooperating scheduling scheme. When 2 or 3 happens, it is called preemptive scheduling.
Non preemptive scheduling
Process keeps CPU until it is terminated or goes to waiting state.
Preemptive scheduling –
Process can be preempted any time. E.g two process access shared data, one process can be preempted to let others access the data. The preemption affects the design of the OS kernel because a process can be preempted in the middle of the system call, before a context switch. The kernel data structures will be an inconsistent state.
Dispatcher
The dispatcher is part of CPU-scheduling that gives control of CPU to the process selected by short-term scheduler.
This function involves the following:
– Switching context
– Switching to user mode
– Jumping to a proper location in the user program to restart the program.
The time taken to stop one process and start another process running is called dispatch latency.
Scheduling Criteria
We must compare CPU-Scheduling algorithms based on following criteria:
CPU utilization – It is to keep CPU busy that range from 40 to 90 percent.
Throughput – Number of processes completed per unit of time.
Turnaround time – It is the sum of time spent – waiting to get into memory, waiting in ready queue, executing in the CPU, and doing I/O.
Waiting Time – Scheduling gets affected by time spent waiting in ready queue. This whole time spent is called the waiting time.
Response time – Turnaround time depends on output device. But in some interactive systems, you get the first response after process submission although the process may still be working. This time is called response time.
Scheduling tries to maximize :
- Throughput
- CPU utilization
Scheduling tries to minimize:
- Response time
- Waiting time
- Turnaround time
The goal here is to reach an optimize level of performance, rather than maximizing or minimizing any thresholds. You will learn more about this in future articles.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
- Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.
