Scheduling is very important part of Operating System. Generally 1-2 questions is expected from this topic. Gate-PrepLadder have compiled 8 tips to solve questions on subnetting and how to implement them in GATE.

Subscribe for latest news, tips and free tutorials at your personal email id.

 

Expert Tips and Tutorials to crack GATE 2018 Exam.

Subscribe Here     

 

CPU scheduling is the basis of multiprogrammed operating system. By switching the CPU among processes, the operating system can make the computer more productive.

We need to learn some terms that can be asked in GATE 2017 from scheduling.

Terms To remember :

CPU utilization :  We want to keep the CPU as busy as possible.

Throughput : Number of processes completed per time unit

Turn Around Time : Process complete Time – process Arrival time

Waiting Time : The sum of periods spent waiting in ready queue

Response Time : The time from the submission of a request until the first response is produced.

 

Also read : Solve Subnetting Questions in GATE in less than a Minute

Scheduling Algorithm :

We need to know scheduling algorithm that are important for GATE 2017 from scheduling

First Come First Served Scheduling :

The processes are served in order. The first process will be served first.

 

Shortest Job First Scheduling :

When CPU is available , it is assigned to process that has the smallest next CPU burst. SJF scheduling is used frequently in long-term scheduling. SJF cannot be implemented at the level of short term CPU scheduling.

 

 

Free All India Test Equipped with Artificial Intelligence

Start Test  

Priority Scheduling :

A priority is associated with each process and the CPU is allocated to the process with highest priority. Equal priority processes are scheduled in FCFS order.

 

Round Robin Scheduling:

The round robin scheduling is designed especially for time sharing systems . A small unit of time is defined. At the end of quantum , a context switch is expected . The process may have CPU burst of less than 1 time quantum ,in this case the process itself will release the CPU voluntarily. If the CPU burst is longer than 1 quantum the timer will go off and will cause interrupt to the operating system.

 

Multilevel Queue Scheduling :

 This algorithm partitions the ready queue into several separate queues. Each queue has its own scheduling algorithm

Foreground RR

Background FCFS

Multilevel Feedback Queue Scheduling :

The purpose is to separate processes with different CPU burst characteristics. If process uses too much CPU time , it will be moved to lower priority queue.

3 queues :      1st   RR with time quantum 8 ms

                    2nd  RR with time quantum 16 ms

                    3rd    FCFS

Also read :Best Books for GATE-CSE by Toppers

 8 Tips To Remember For GATE 2017

You need to remember certain tips to solve questions from scheduling for GATE 2017.

#Tip 1

Turnaround Time = Completion Time - Arrival Time

#Tip 2

Waiting Time = Completion Time - Arrival Time - Execution Time

#Tip 3

FCFS is non-premptive

#Tip 4

Shortest job First may be either preemptive or non-preemptive. The choice arises when new process arrives at ready queue while previous process is executing

 

Free All India Test Equipped with Artificial Intelligence

Start Test  

 

#Tip 5

The major problem with priority scheduling is indefinite blocking or starvation. A solution to the problem of indefinite blockage of low priority process is aging.

#Tip 6

In Round Robin Scheduling ,each process must wait no longer than (n-1) *q time units until its next time quantum. The performance of Round Robin Scheduling depends heavily on size of time quantum.

#Tip 7

In multilevel scheduling, each queue gets a certain amount of CPU time i.e 80 % to foreground in RR and 20% to background in FCFS.

#Tip 8

In multilevel feedback scheduling , process in queue 2 will only be executed if queues 0 and 1 are empty.

Also read : Tips to Solve Asymptotic Notation Questions in GATE - CS

Questions From GATE :

Question 1 : Consider the 3 processes, P1, P2 and P3 shown in the table
----------------------------------------------
Process     Arrival time    Time unit required
----------------------------------------------
  P1              0                    5
  P2              1                    7
  P3              3                    4
----------------------------------------------
The completion order of the 3 processes under the policies FCFS and RRS (round robin scheduling with CPU quantum of 2 time units) are
(a) FCFS: P1, P2, P3 RR2: P1, P2, P3
(b) FCFS: P1, P3, P2 RR2: P1, P3, P2
(c) FCFS: P1, P2, P3 RR2: P1, P3, P2
(d) FCFS: P1, P3, P2 RR2: P1, P2, P3

Answer : C

Explanation :

For FCFS, the process arrived first will be first served  So the sequence is P1, P2, P3.For RRS, the chart is shown below.The execution chart and ready queue sequence at each time unit is given below. The orange box  denotes the Ready Queue Sequence and blue box denoted the Execution Sequence. Hence we get the completion order P1,P3,P2.

Question 2

Consider the following table of arrival time and burst time for three processes P0, P1 and P2.
-----------------------------------
Process   Arrival time   Burst Time
-----------------------------------
 P0            0 ms          9 ms
 P1            1 ms          4 ms
 P2            2 ms          9 ms
-----------------------------------
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
(a) 5.0 ms  (b) 4.33 ms  (c) 6.33 ms  (d) 7.33 ms

Answer (a)

Explanation :
Execution chart is shown below:

P0

P1

P0

P2

1

5

13

22

Waiting Time = Completion Time - Arrival Time - Execution Time
----------------------------------------------------------------------------------------
Pro   ArrivalTime   BurstTime   Completion Time     WaitingTime
---------------------------------------------------------------------------------------
 P0    0                  9                 13                      4
 P1    1                  4                  5                       0
 P2    2                  9                  22                     11
----------------------------------------------------------------------------------------
Average time(Waiting) = (4+0+11)/3 = 5ms .

 Best Wishes !!

 

Enroll in Mentor Program and Avail your Personalized Mentor for GATE 2017 Preparation and Doubts Clarification!

What aspirants need is the right approach along with concrete strategies to reach their goals. GATE GUARANTEE PACK has been the choice of successful GATE toppers all over India.

It is the perfect online tool to check your level of preparedness among st students preparing all over the country where you study under guidance of mentors.

Free All India Test Equipped with Artificial Intelligence

Start Test  

Search on PrepLadder