Shortest Job First Scheduling


Shortest job first scheduling means pick the job that will take the less time to complete. Shortest job first scheduling picks the shortest job in terms of burst time and places it on the CPU. Shortest job first having minimum average waiting time among all the scheduling algorithms. SJF scheduling is simple to implement in the batch operating system because in this CPU time is known in advance.

Shortest job first scheduling can be used in both non preemptive and preemptive mode.

Shape 

(1) Non Preemptive

Once the CPU cycle is allocated to a process, it cannot be preempted until the current process reaches a waiting state or terminated.

(2) Preemptive

Jobs are moved into ready queue. Processes which have shortest burst time begins its execution first. When process with shorter burst time arrives, then the current process stops and other process which having shorter burst time is allocated with the CPU first.

 Example (1)

Non Preemptive SJF

Suppose there are four processes are as below.

Process Name 

Arrival Time 

Burst Time 

Process 1 

0 

8

Process 2 

2 

3 

Process 3 

4 

2

Process 4 

5 

4 


Step (1)

Arrival time are important, since there is 1 process available at time 0, So process 1 is by default shortest process.

 Step (2)

At time 2, process 2 arrives but process 1 is already running. So process 2 has to wait until process 1 finishes.

 Step (3)

At time 3, Process 3 arrives that is shortest but process 1 has still not finished.

Step (4)

At  time 4, Process 4 arrives but process 3 is the shortest. When process 1 finishes, then process 3 will run.

Step (5)

At time 5, When process 3 finishes, process 2 will run .

 Step (6)

After process 2 finishes, process 4 will run.


Gantt Chart

Process 1 

Process 3 

Process 2 

Process 4 

0            8       

                     10            

                          13 

                                   17 


Waiting Time

Waiting time for a process can be measured by taking its finish time and subtracting burst time and arrival time. 

Waiting Time = Finish time - Burst time - Arrival time


Process Name 

Arrival Time 

Burst Time 

Finish Time 

Waiting Time 

Process 1 

0 

8 

8 

0 

Process 2 

2 

3 

13 

8 

Process 3 

4 

2 

10 

4 

Process 4 

5 

4 

17 

8 


Waiting time for process

Process 1

Waiting time = 8-8-0

Waiting time=0

Process 2

Waiting Time= 13-3-2

Waiting Time=8

process3

Waiting Time=10-2-4

Waiting Time=4

Process4

Waiting Time=17-4-5

Waiting Time=8

Average Waiting Time

Average waiting time = (0+8+4+8)/4
Average waiting time= 20/4
Average waiting time= 5

(2) Preemptive SJF

There are four processes as below.

Process Name 

Arrival Time 

Burst Time 

Process 1 

0 

6 

Process 2 

2 

4 

Process 3 

4 

2 

Process 4 

5 

4 


 Step (1)

Arrival time are important , since there is only one process available at time 0, that is process 1. Process i is by default the shortest process.

 Step (2)

At time 2 ,process 2 arrives but process 1 is already running. There is a preemption, so process 1 is removed from the CPU and replaced with process 2.

Step (3)

At time 4, Process 3 arrives that is the shortest process, so it replace process 2 on CPU.

 Step (4)

At time 6, process 3 finishes and process 4 arrives. Now process 2 is again shortest and it execute until the finish.

 Step (5)

At time 8, process 4 is shortest and run until time 11. Process 1 which is the only process left is the shortest process and execute until the finishes.

Gantt Chart

Process 1 

Process 2 

Process3 

Process 2 

Process4 

Process 1 

0          2           

                 4                   

               6                            

                  8 

              12 

              17 



Waiting Time 

Waiting Time = Finish time - Burst time - Arrival time

Process Name 

Arrival Time 

Burst Time 

Finish Time 

Waiting Time 

Process 1 

0 

6 

17 

11 

Process 2 

2 

4 

8 

2 

Process 3 

4 

2 

6 

0 

Process 4 

5 

4 

12 

3 


Waiting time for process

Process 1

Waiting time = 17-6-0

Waiting time=11

Process 2

Waiting Time= 8-4-2

Waiting Time=2

process3

Waiting Time=6-2-4

Waiting Time=0

Process4

Waiting Time=12-4-5

Waiting Time=3

Average Waiting Time

Average waiting time = (11+2+0+3)/4
Average waiting time= 16/4
Average waiting time= 4

Scheduling Algorithm

Comments

Post a Comment

If you have any doubts, please let me know

Popular Posts

Computer Abbreviation

Topic Outline Introduction to computer abbreviation Abbreviation of system unit component  Abbreviation of storage devices  Abbreviation of input and output devices  Abbreviation of data communication and computer network Abbreviation of Programming Languages Abbreviation of Operating System and Networks  In this lecture, we will discuss the different Computer Abbreviations. Introduction to Computer & Information technology   Abbreviation   Full-Form   1   Computer     Common Operating Machine Particularly Used for Technological and Education Research   2   IPC   Information Processing Cycle   3   IT   Information Technology   4   PC   Personal Computer   5   CPU   Central Processing Unit   6   USB   Universal Serial Bus   7   ENIAC   Electronical Numerical Integrator and Calculator   8   EDVAC   Electronic Discrete Variable Autom...
Read more

Transport Layer

Image
  Topic Outline Transport Layer TCP Function of TCP UDP Difference between TCP and UDP Transport Layer The Transport layer is essentially responsible for delivering data to the appropriate application on the host computer. It receives requests from the application layer protocols and passes them down to the internet network layer. Two most commonly used transport layer protocols are the connection TCP and connection UDP. TCP  Transmission Control Protocol End to End communication for user processes. Processes can communicate in a simple stream of binary data. Each byte of data will arrive in the order it was sent. If some part of the data cannot be received this will be made explicit by an error being passed to the user code. Functions of TCP   (1) Data Transfer TCP transfer a continuous stream of bytes. TCP itself decides how to segment the data and it may forward the data at its own convenience. (2) Reliability TCP assigns a sequence number to each byte transmitted and ...
Read more

Introduction to Database

 Topic Outline Introduction to Database  Types of Data Metadata Components of Database Environment Application Program Range of Database applications Types of Users Types of Data Different types of data are as follow: Numeric Data It consists of numeric digits from 0 to 9 like 22, 58, 1123, or -123. The numeric data may be, either positive or negative. Alphabetic Data It consists of alphabetic letters from A to Z, a to z, and blank spaces. For example, "Computer", "Software", "IT", and "Automata" etc. Image Data Image data includes graphs, pictures, drawings,, and charts. Image data is more comprehensive.  Alphanumeric Data It consists of numeric digits (0 to 9) , letters (A- to Z) and all special characters (+, -, @, $, #) etc. Audio Data This data includes music, speech, and any type of sound. Video Data This data is a set of full-motion images played at a high speed. It is used to display actions and movement. Metadata The metadata can be defi...
Read more

Types of database

Topic Outline Types of Database Object-Oriented Database Centralized Database Decentralized Database Distributed Database Hierarchical Database Personal Database Cloud Database Multi-Dimensional Database Operational Database Relational Database  1:Object-Oriented Database Object-oriented database stores data in the form of objects. An object is an item that can contain data and functions. For example, an object employee may contain data about an employee such as Employee ID, Name, Address, Phone Number, etc. It may also contain functions to process the data such as printing the record of an employee, calculating salary, etc. Characteristics The object-oriented data model must be able to provide complex object representation. The object-oriented data model must be extensible. It means it provides support for defining new data types and methods. The object-oriented data model must support encapsulation or information hiding. The object-oriented data model must exhibit inheritance. In...
Read more

Threads in operating system

Image
  Topic Outline Threads Difference between thread and process Types of Threads Kernel Level Thread User Level Thread Multithreading Advantages Resource Sharing Responsiveness Utilization of Multiprocessor Architecture Multithreading Models Many to One Model One to One Model Many to Many Model Threads Thread is a basic unit of CPU utilization. Thread is also called a lightweight process. Thread is a process within a process but it does not have its own process control block. In a process, multiple threads are created. In a process, multiple threads allow multiple executions.   The thread consists of the following things. Thread ID Register Program counter Stack Difference between threads and process. Threads   Process   In threads no system  call  is  involved .   In a process system call is  involved .   Thread  is  a  lightweight  process.   The Process is  heavyweight .  If  the th...
Read more

Display devices

Image
  Topic Outline Display devices Types Cathode Ray Tube Flat Panel Display Emissive Display LED OLED Gas Plasma Non-Emissive Display LCD A display device is an output device. It is used to represent information in the form of text, graphics, images, and video. The display for a desktop computer is a monitor. Mobile computers and devices integrate the display in the same physical case. Some displays have touch screens such as mobile phones and laptops etc. The output displayed by a display device is called soft copy. Display devices are available in different sizes. For example When we write any document on the computer, it is a soft copy of the document. When we get a print of this document, it is a hard copy of the document. Types Types of display devices are as follows. (1) Cathode Ray Tube A cathode-ray tube creates an image on the screen by using a beam of electrons. Cathode ray tube consists of one or more guns. These guns fire a beam of electrons inside the screen. The monitor...
Read more

Shortcut keys of computer

Important Shortcut keys of Computer Shortcut keys are an easier and quicker method of executing the commands in the computer system. When we work on the computer, different shortcut keys are used. Some important shortcut keys are as follow: Short cut keys   Working   Ctrl+ C   Copy the select item   Ctrl+ V   Paste the item   Ctrl+ X   Cut the select item   Ctrl+ Del   Cut the select item   Ctrl+ A   Select all text   Ctrl+ Home   Go to beginning of the document   Ctrl+ End   Go to end of the document   Ctrl +( left arrow)   Move one word to the left at a time   Ctrl +( right arrow)   Move one word to the right at a time   Ctrl +( Plus key)   Adjusts width in window explorer   Ctrl +( Minus key)   Adjust width in window explorer   Ctrl+ Alt+ Del   Windows task manager   Ctrl+ Ecs   Bring up the start menu   Ctrl+F4   Close window in progra...
Read more

History of Computer

Image
  Topic Outline History of computer Abacus John Napier's Bone Blaise Pascal Von Leibnitz Charles Xavier Joseph Charles Babbage Herman Hollerith Atanasoff George Boole Mark 1 Computer ENIAC  EDVAC UNIVAC Commercial Computer History of computer Today those computers that we are used behind this many efforts of different peoples. An Abacus computing device was used for addition and subtraction. John Napier Bones created the slide rule to perform mathematical calculations. Blaise Pascal invented the mechanical machine for adding and subtracting. Von Leibnitz also invented the calculating machine that was used for division and multiplication. Charles Xavier invented the machine that could perform addition, subtraction, multiplication, and division.  Charles Babbage invented a difference engine and an analytical engine. A brief history is available below👇. The computer was invented because 'necessity is the mother of invention'. A brief history behind the invention of the comp...
Read more