techtud's picture

Scheduling: FCFS, SJF, Round Robin etc.

Scheduling | Important terms

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

 

0Comment
PCB & Various Schedulers
Content covered: 

This Video Contains:

1. Process State Transition Digram
2. Various Schedulers

 

More Less
0Comment
Various Scheduling Examples

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 the 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-preemptive – once CPU has 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 the currently executing process, preempt. This scheme is known 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 for 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

0Comment
FCFS Description
Content covered: 

This Video from YouTube contains about FCFS Scheduling Algorithm.

More Less
0Comment
Non-Preemptive SJF
Content covered: 

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

More Less
0Comment
Preemptive SJF
Content covered: 

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

More Less
0Comment
RR Example
Content covered: 

Round Robin Example

More Less
0Comment

  • 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
shashank shashankbhat 8 Jan 2017 06:52 pm

where are the next videos?

AMIT CHAUDHARY amit17 8 Jan 2017 10:30 pm

sir videos are not being uploaded on time .

Sumit Verma sumitverma 9 Jan 2017 11:47 am

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

shashank shashankbhat 9 Jan 2017 09:16 pm

please stick to the schedule sir.

Hradesh hradeshpatel 10 Jan 2017 10:57 pm

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??

Roshan Chettri roshanchettr 10 Jan 2017 11:09 pm

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. 

Mayank kumar may47 21 Jan 2017 01:56 pm

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 

Harshita Sharma harshitasharma 8 Feb 2017 03:05 pm

S2 :waiting time > response time should be true. 

Pages