Operating System | Process Management | CPU Scheduling

Scheduling of processes/work is done to finish the work on time.

Scheduling Criteria

There are many different criteria to check when considering the "best" scheduling algorithm :

• CPU utilization
  To make out the best use of CPU and not to waste any CPU cycle, CPU would be working most of the time(Ideally 100% of the time). Considering a real system, CPU usage should range from 40% (lightly loaded) to 90% (heavily loaded.)[ make CPU as busy as possible.]
• Throughput
  It is the total number of processes completed per unit time or rather say total amount of work done in a unit of time. This may range from 10/second to 1/hour depending on the specific processes. 
• Turnaround time
  It is the amount of time taken to execute a particular process, i.e. The interval from time of submission of the process to the time of completion of the process.
• Waiting time [The amount of time that is taken by a process in ready queue. ]
  Amount of time a process has been waiting in the ready queue to acquire get control on the CPU.
• Load average
  It is the average number of processes residing in the ready queue waiting for their turn to get into the CPU.
• Response time [time difference b/w the first response and arrival time]
  (The time from the submission of a request to the time of first response by the CPU.) Amount of time it takes from when a request was submitted until the first response is produced. Remember, it is the time till the first response and not the completion of process execution(final response).

In general CPU utilization and Throughput are maximized and other factors are reduced for proper optimization.

Arrival Time:       Time at which the process arrives in the ready queue.
Completion Time:    Time at which process completes its execution.
Burst Time:         Time required by a process for CPU execution.
Turn Around Time:   Time Difference between completion time and arrival time.          
     Turn Around Time = Completion Time - Arrival Time

Waiting Time(W.T): Time Difference between turn around time and burst time.
     Waiting Time = Turn Around Time - Burst Time

Objectives of Process Scheduling Algorithm

Max CPU utilization [Keep CPU as busy as possible]
Fair allocation of CPU.
Max throughput [Number of processes that complete their execution per time unit]
Min turnaround time [Time taken by a process to finish execution]
Min waiting time [Time a process waits in ready queue]
Min response time [Time when a process produces first response]

Scheduling Algorithms

We'll discuss four major scheduling algorithms here which are following :

1. First Come First Serve(FCFS) Scheduling
2. Shortest-Job-First(SJF) Scheduling
3. Priority Scheduling
4. Round Robin(RR) Scheduling
5. Multilevel Queue Scheduling
6. Multilevel Feedback Queue Scheduling