Operating System (CPU Scheduling) - Part 5

Hi Folks,

We'll continue with CPU Scheduling in Operating systems. Previous article on "process synchronization" can be found at Operating systems - Part 4.

Raise your doubts in comments section!

Scheduling Criteria for Processes

As we know that CPU scheduler selects from among the processes in ready queue and assigns CPU to one of them. This scheduling is done on basis on certain parameters called scheduling criteria which are as follows:

• CPU utilization - aim is to keep CPU as busy as possible.
• Throughput - It is viewed in terms of number of processes that complete their execution per time unit. 
• Turnaround Time - amount of time a process takes to execute.
• Waiting Time - amount of time a process has been waiting in the ready queue. 
• Response Time - amount of time it takes for first response after a request has been submitted. 

Scheduling Algorithms  

The algorithms used mostly in practice are discussed as follows:

1. First Come First Served Scheduling (FCFS)

Major attributes of FCFS are as follows :

• It queues processes in the order that they arrive in ready queue. 
• Performance is usually poor as average response time is high.

Consider the process below & their burst times and lets see how their scheduling charts looks like. (Burst time - amount of CPU time a process requires).

2. Shortest Job First Scheduling (SJF)

Major attributes of SJF are as follows:

• Scheduler picks processes according to their burst times. Shortest one is picked first followed by next shortest one. 
• It gives minimum average waiting time for a given set of processes. 

3. Priority Scheduling

Major attributes are as follows: 

• A priority number is associated with each process (an integer value)
• CPU is allocated to the process with highest priority. 
• Problem - low priority process may never execute. Solution to that would be to increase the priority as time progresses for a ready process. 

4. Round Robin Scheduling

Major attributes are as follows:

• Each process gets a small unit of CPU time called quantum. 
• After that time, current process is preempted and added to end of ready queue. Next process gets CPU for next quantum. 
• It has higher avg waiting time than SJF but better response. 

Example of Round Robin Scheduling with time quantum = 4 is as below:

5. Multi Level Queue Scheduling

Major attributes are as follows:

• In this, ready queue is partitioned into separate queues e.g queue 1 and queue 2. 
• One process remains permanently in one queue and can not shift queues. 
• Each queue can have its own scheduling algorithms. 
• Scheduling must be done between two queues and once CPU assigned to a queue, process in that will be executed before moving to another queue. 

6. Thread Scheduling

Major attributes are as follows:

• Scheduler assigns CPU based on a distinction between user level threads and kernel threads. 
• Competition is between threads inside a process for allocation of CPU.

Practice MCQs 

1. Four jobs to be executed on a single processor system arrive at time 0 in the prder A, B, C, D. Their CPU burst time requirements are 4,1,8,1 units respectively. The completion time of A under RR scheduling with time quantum =1 would be?

a) 10   b) 4  c) 8   d) 9

2. Which of the follwing scheduling algorithms is non preemptive?

a) FCFS   b) RR  c) Priority Scheduling  d) Multilevel queue

OS fact of the day 

You can not create a folder named 'con' anywhere in your windows operating system. It was reserved for old DOS to be used.