Skip to main content

Shortest Job First Scheduling (SJF)

 

Shortest Job First Scheduling (SJF)

·         SJF ia also known as shortest-job-next(SJN) algorithm and is faster than FCFS.

·         In SJF, the process with the least estimated execution time is selected from the ready queue for  execution.

·         For this, SJF algorithm associates with each process, the length of its next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst.

·         If tow processes have the same length of next CPU burst ,FCFS scheduling algorithm is used to break the tie.

·         SJF algorithm can be preemptive or non-preemptive.

 

 

Non-preeptive SJF

·         In non-preemptive SJF, scheduling, CPU is always assigned to the process with least CPU burst time and the process keeps CPU with it until it terminates.

·         The main advantages of SJF scheduling is that it give minimum average waiting time for a given set of processes. By moving a short process before a long process, the waiting time of the short process decreases before a long process, the waiting time of the short process decreases more than it increases the waiting time of the long process.

·         The main disadvantages of SJF scheduling is that it requires precise knowledge of how long a job or process will run and this information is usually not available.

·         Another disadvantages of SJF scheduling is that the processeswith high estimated execution time may have to wait for a long time if there are a large number of processes with short estimated execution time .

 

Preemptive SJF

·         The preemptive of SJF scheduling is known as shortest remaining time (SRT)scheduling.

·         Srt scheduling id useful in timesharing  system

·         In SRT, the process with the smallest estimated run-time to completionis run next. This is applied even for new arrival processes.

·         Any time a new process enters the pool of processes to be scheduled, the scheduling compare the expected value for its remaining process’s time is less, then currently running process is preempted and CPU is allocated to new process.

 

The disadvantages of SRT scheduling ARE:

1.       The Execution Time Of Processes Must Be Known In Advance. Calculateing Execution Time Of A Process Without Executing It Is Difficult.

2.       SRT has higher overhead than SJF. It must keep the track of the elapsed service-time of the running job and must handle occasional preemptions

3.       As SRT fovours short jobs, the mean waiting time for longer processes or jobs is more longer and long jobs can be victim of starvation.


Shortest Job First (SJF): Preemptive, Non-Preemptive Example

Non-Preemptive SJF

In non-preemptive scheduling, once the CPU cycle is allocated to process, the process holds it till it reaches a waiting state or terminated.

Consider the following five processes each having its own unique burst time and arrival time.

Process QueueBurst timeArrival time
P162
P225
P381
P430
P544

Step 0) At time=0, P4 arrives and starts execution.

Step 1) At time= 1, Process P3 arrives. But, P4 still needs 2 execution units to complete. It will continue execution.

Step 2) At time =2, process P1 arrives and is added to the waiting queue. P4 will continue execution.

Step 3) At time = 3, process P4 will finish its execution. The burst time of P3 and P1 is compared. Process P1 is executed because its burst time is less compared to P3.

Step 4) At time = 4, process P5 arrives and is added to the waiting queue. P1 will continue execution.

Step 5) At time = 5, process P2 arrives and is added to the waiting queue. P1 will continue execution.

Step 6) At time = 9, process P1 will finish its execution. The burst time of P3, P5, and P2 is compared. Process P2 is executed because its burst time is the lowest.

Step 7) At time=10, P2 is executing and P3 and P5 are in the waiting queue.

Step 8) At time = 11, process P2 will finish its execution. The burst time of P3 and P5 is compared. Process P5 is executed because its burst time is lower.

Step 9) At time = 15, process P5 will finish its execution.

Step 10) At time = 23, process P3 will finish its execution.

Step 11) Let's calculate the average waiting time for above example.

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

Preemptive SJF

In Preemptive SJF Scheduling, jobs are put into the ready queue as they come. A process with shortest burst time begins execution. If a process with even a shorter burst time arrives, the current process is removed or preempted from execution, and the shorter job is allocated CPU cycle.

Consider the following five process:

Process QueueBurst timeArrival time
P162
P225
P381
P430
P544

Step 0) At time=0, P4 arrives and starts execution.

Process QueueBurst timeArrival time
P162
P225
P381
P430
P544

Step 1) At time= 1, Process P3 arrives. But, P4 has a shorter burst time. It will continue execution.

Step 2) At time = 2, process P1 arrives with burst time = 6. The burst time is more than that of P4. Hence, P4 will continue execution.

Step 3) At time = 3, process P4 will finish its execution. The burst time of P3 and P1 is compared. Process P1 is executed because its burst time is lower.

Step 4) At time = 4, process P5 will arrive. The burst time of P3, P5, and P1 is compared. Process P5 is executed because its burst time is lowest. Process P1 is preempted.

Process QueueBurst timeArrival time
P15 out of 6 is remaining2
P225
P381
P430
P544

Step 5) At time = 5, process P2 will arrive. The burst time of P1, P2, P3, and P5 is compared. Process P2 is executed because its burst time is least. Process P5 is preempted.

Process QueueBurst timeArrival time
P15 out of 6 is remaining2
P225
P381
P430
P53 out of 4 is remaining4

Step 6) At time =6, P2 is executing.

Step 7) At time =7, P2 finishes its execution. The burst time of P1, P3, and P5 is compared. Process P5 is executed because its burst time is lesser.

Process QueueBurst timeArrival time
P15 out of 6 is remaining2
P225
P381
P430
P53 out of 4 is remaining4

Step 8) At time =10, P5 will finish its execution. The burst time of P1 and P3 is compared. Process P1 is executed because its burst time is less.

Step 9) At time =15, P1 finishes its execution. P3 is the only process left. It will start execution.

Step 10) At time =23, P3 finishes its execution.

Step 11) Let's calculate the average waiting time for above example.

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Advantages of SJF

Here are the benefits/pros of using SJF method:

  • SJF is frequently used for long term scheduling.
  • It reduces the average waiting time over FIFO (First in First Out) algorithm.
  • SJF method gives the lowest average waiting time for a specific set of processes.
  • It is appropriate for the jobs running in batch, where run times are known in advance.
  • For the batch system of long-term scheduling, a burst time estimate can be obtained from the job description.
  • For Short-Term Scheduling, we need to predict the value of the next burst time.
  • Probably optimal with regard to average turnaround time.

Disadvantages/Cons of SJF

Here are some drawbacks/cons of SJF algorithm:

  • Job completion time must be known earlier, but it is hard to predict.
  • It is often used in a batch system for long term scheduling.
  • SJF can't be implemented for CPU scheduling for the short term. It is because there is no specific method to predict the length of the upcoming CPU burst.
  • This algorithm may cause very long turnaround times or starvation.
  • Requires knowledge of how long a process or job will run.
  • It leads to the starvation that does not reduce average turnaround time.
  • It is hard to know the length of the upcoming CPU request.
  • Elapsed time should be recorded, that results in more overhead on the processor.

Comments

Post a Comment

Popular posts from this blog

Monolithic Architecture

  Monolithic Architecture Monolith means composed all in one piece. The  Monolithic  application describes a single-tiered  software  application in which different components combined into a single program from a single platform. Components can be: Authorization — responsible for authorizing a user Presentation — responsible for handling HTTP requests and responding with either HTML or JSON/XML (for web services APIs). Business logic — the application’s business logic. Database layer — data access objects responsible for accessing the database. Application integration — integration with other services (e.g. via messaging or REST API). Or integration with any other Data sources. Notification module — responsible for sending email notifications whenever needed. Example for Monolithic Approach Consider an example of Ecommerce application, that authorizes customer, takes an order, check products inventory, authorize payment and ships ordered products. This applicat...
Post a Comment
Read more

Change the priority of a process

  Change the priority of a process You can tell the computer that certain processes should have a higher priority than others, and so should be given a bigger share of the available computing time. This can make them run faster, but only in certain cases. You can also give a process a  lower  priority if you think it is taking up too much processing power. Go to the  Processes  tab and click on the process you want to have a different priority. Right-click the process, and use the  Change Priority  menu to assign the process a higher or lower priority. There is typically little need to change process priorities manually. The computer will usually do a good job of managing them itself. (The system for managing the priority of processes is called  nice .) Does higher priority make a process run faster? The computer shares its processing time between all of the running processes. This is normally shared intelligently, so programs that are doing more ...
Post a Comment
Read more

Defination of OS(operating system) and its concepts

    What do you mean by operating system?     Definition :  An operating system is a program that act as an interface between the user of a computer and the                                      Computer hardware. Operating system is a first program that gets loaded into the memory through a process called booting. Concepts of operating system : ·                       The purpose of operating system is to provide an environment in which a user can execute program in a convenient and efficient manner. ·                       Operating system is an integrated set of program that ma...
3 comments
Read more

System structure operating architecture

  System structure operating  architecture An operating system is a construct that allows the user application programs to interact with the system hardware. Since the operating system is such a complex structure, it should be created with utmost care so it can be used and modified easily. An easy way to do this is to create the operating system in parts. Each of these parts should be well defined with clear inputs, outputs and functions. Simple Structure There are many operating systems that have a rather simple structure. These started as small systems and rapidly expanded much further than their scope. A common example of this is MS-DOS. It was designed simply for a niche amount for people. There was no indication that it would become so popular. An image to illustrate the structure of MS-DOS is as follows − It is better that operating systems have a modular structure, unlike MS-DOS. That would lead to greater control over the computer system and its various applications. T...
Post a Comment
Read more

Distributed system

  Distributed system ·           A distributed system is a collection of processor located in geographical dispersal physical location. ·           In this system, the workhold is distributed or divided between two or more computers that are linked together by communication network . that is the different processors communicate using communication links, such as telephone lines and buses3 ·           The various processors do not share memory, clock ,or peripheral devices instead each processors has its local memory. ·           The purpose of distributed system is to provide an efficient and convenient environment for sharing of resources. ·           Some example of distributed operating system are amoeba, angle, chorus, much, alpha kernel. ·   ...
Post a Comment
Read more