Scheduling: FCFS, SJF, Round Robin etc.

Content: 

 

Throughput - Number of processes completed per unit time. May range from 10 / second to 1 / hour depending on the specific processes.
Turnaround time - Time required for a particular process to complete, from submission time to completion. ( Wall clock time. )
Waiting time - How much time processes spend in the ready queue waiting their turn to get on the CPU.
Load average - The average number of processes sitting in the ready queue waiting their turn to get into the CPU. 
Response time - Amount of time it takes from when a request was submitted until the first response is produced. 
For a particular process :
Completion time - Arrival time = Burst time + Waiting time = Turn around time

 


Content covered: 

This Video Contains:

1. Process State Transition Digram
2. Various Schedulers

 

FCFS :

Process Burst Time
  P1 24
  P2 3
  P3   3

Suppose that the processes arrive in the order: P1 P2 P3
The Gantt Chart for the schedule is:

P1

P2

P3

0 ............................................  24 .............................. 27........................................................ 30

  Waiting time for P1 = 0; P2 = 24; P3 = 27

  Average waiting time: (0 + 24 + 27)/3 = 17

Suppose that the processes arrive in the order: P2 P3 P1 .

The Gantt chart for the schedule is:

P2

P3

P1

0 ..................................................3............................. .........6....................................................30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case.

Convoy effect short process behind long process

Shortest-Job-First (SJR) Scheduling :
Associate with each process the length of its next CPU 
burst. Use these lengths to schedule the process with the shortest time.
Two schemes:
1.  non pre- emptive – once CPU given to the process it cannot 
be preempted until completes its CPU burst.
2. preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF).

SJF is optimal – gives minimum average waiting time for a given set of processes.
 

 Process   Arrival Time Burst Time
P1  0.0     7
P2    2.0      4
P3  4.0   1
P4 5.0      4

SJF (non-preemptive):

P1

P3

P2

P4

0.................................. 7................................. 8 ........................12.........................................16

Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4

SJF (preemptive)

P1

P2

P3

P2

P4

P1

0 ................... 2......................4........................5..................... 7..................... 11...................16

Average waiting time = (9 + 1 + 0 +2)/4 =3
Determining Length of Next CPU Burst Can only estimate the length. Can be done by using the length of previous CPU bursts, using exponential averaging.

Round Robin (RR):
Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time  has elapsed, the process is preempted and added to the end of the ready queue.

If there are processes in the ready queue and the time quantum is q, then each process gets 1/of the CPU time in chunks of at most time units at once. No process waits more than (n-1)time units.

Performance:

1. large _ FIFO

2. small _ must be large with respect to context switch, otherwise overhead is too high.

Example of RR with Time Quantum = 4

Process Burst Time
  P1 24
  P2 3
  P3   3

The Gantt chart is:

P1

P2

P3

P1

P1

P1

P1

P1

0.............4...............7.............10............14............18 ............22.............26............ 30

Average waiting time =    [(30-24)+4+7]/3  = 17/3 =5.66


Content covered: 

This Video from YouTube contains about FCFS Scheduling Algorithm.


Content covered: 

This Video from YouTube gives an idea of Non-Preemptive Version of SJF.


Content covered: 

This Video from YouTube describes the Preemptive Version of SJF also called SRTF i.e. Shortest Remaining Time First.


Content covered: 

Round Robin Example

  • This quiz contains 5 questions on the topic Scheduling.
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  basic
No. of Questions:  5

Awesome, you did good to complete todays course.

To continue your preparation while we publish tomorrow’s topic,

please subscribe to our youtube channel.

 

Responses

where are the next videos?

amit17's picture

sir videos are not being uploaded on time .

sumitverma's picture

We will try our level Best to provide the contents according to the schedule.
Thank you very much for bearing with us.

please stick to the schedule sir.

hradeshpatel's picture

plz explain how can u say that it is true in non-premitive scheduling  waiting time = responce time and how it is false in premitive scheduling   waiting time > responce time ..........plz check??

roshanchettr's picture

Response time is the time the job has to wait till it is allocated the CPU for the very first time. And in Non- Preemptive Scheduling once the job is allocated the CPU, it is run till completion. Therefore,, in non-preemptive scheduling response time is always equal to the Waiting time of the job.

But in Preemptive Scheduling, once the job is allocated the CPU, it might be again preempted which Adds the waiting time of the job until its scheduled next, but this second ( or subsequent) waiting time, resulting from preemption does not adds the response time. Therefore in Preemptive scheduling Waiting Time is always greater than or equal to response time. 

may47's picture

When a process switches from waiting state to ready state or When a process switches from running state to waiting state both comes in i/o scheduling & only sort term scheduler is called CPU scheduler,

plz comment 

S2 :waiting time > response time should be true. 

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.