Scheduling: Non-Preemptive Scheduling

Scheduling:

In multi-programmed computer, multiple processes competing for the CPU at the same time. This situation occurs whenever two or more processes are simultaneously in the ready state. If only one CPU is available. Then we need a system that decide which process run first and then next and this will be done by the scheduler.

Scheduler:

scheduler is an operating system module that she loves an axe top to be admitted into the system and then the next process to run.

Scheduling is of two type:

1) Pre-emptive

2) Non pre-emptive

Non Pre-emptive Scheduling:

In batch non Pre-emptive scheduling implies that, once scheduled, selected job runs to completion.

In other words, the running process not forced to relinquish ownership of the processor when a higher priority process becomes ready for execution.

The scheduling techniques which use non preemptive scheduling are:

1) first come first serve (FCFS) scheduling

2) shortest job next (SJN) scheduling

3) deadline scheduling

 a) First Come First Serve ( FCFS): FCFS schedules the process in such a way, such that the process which requires the right of CPU is located first. There is a simple queue of ready process.

• It's very simple to implement
• It's non-discriminatory 

 Disadvantages:

• The waiting time is often long
• The system throughput and CPU utilisation is very low
• No preemption means it does not taken into consideration of process priority and the execution time
•  It cannot be using time sharing system

Example:

PROCESS	BURST TIME
P1	20
P2	07
P3	08

 

The processes P1 P2 P3 aimed in the order P1,P2 and P3. When they served according to FCFS policy, we get the result as shown in Gantt chart:

0                                              20                                           7                                              5

P1

P2

P3

0                                                          20              

Waiting for process p1 = 0

Waiting for process P2= 20

Waiting for process P3 = 27

Average waiting time = (0+20+27)/3 = 15.67

b) Shortest Job Next: SJN scheduling, whenever a new job is to be admitted the shortest of the arrived jobs is selected and given the CPU time . Throughput remains the same as in FCFS scheduling but waiting time improves.

Example:

                                                                      

JOB	CPU BURST TIME
J1	4
J2	6
J3	3
J4	2
J5	7
J6	3

 

Here, note that if two job have same burst time than give priority to job which comes first

Using SJN, scheduling order of this jobs would be:

Job 4, job 3, job 6, job 1, job 2, job 5

 Waiting time for job 1= 8

Waiting time for job 2= 12

Waiting time for job 3= 2

Waiting time for job 4= 0

Waiting time for job 5= 18

Waiting time for job 6= 5

Average waiting time = (45)/6 = 7.5 

Hence it's clearly seen that waiting time for SJN is better than FCFS.

Deadline scheduling:

In deadline scheduling, the job at the earliest deadline is selected for schedule. Deadline of a job is the time limit within which a job must be over.if a job overshoots its deadline, it is said to be deadline over  Deadline over run is calculated as

                                  K=C - D

where K is deadline overrun, C is job completion time and D is deadline for a job.