Scheduling Algorithm

Scheduling Algorithm

Every scheduling algorithm has its own criteria to choose next job that will run on CPU.

Timelines

Scheduling is based on information that is available at given time.

Gantt Chart

Gantt charts are used to represent the state of the system and any process in it  and how it changes over time. Gantt chart is a timeline that are used to depict the order of process execution graphically.

First Come First Served Scheduling

FCFS is simplest CPU scheduling algorithm. FCFS scheduling says that the process that enters first should get. It is easy to understand. FCFS method can be managed with FIFO queue.

Example

Banks, Shops queue

Example (1) 

Suppose that there are three processes that arrive in the order shown below. All processes arrive at time 0 but system has decided to serve them in this order.

Process Name 

Arrival Time 

Burst Time 

Process 1 

0 

20 

Process 2 

0 

4 

Process 3 

0 

4 

Process 4 

0 

4 

Gantt Chart

Process 1 

Process 2 

Process 3 

Process 4 

                                                                             0                     20 

                                                               24 

                                                                  28 

                                                          32 

Process 1 is dispatched and runs for 20 units. When process 1 has finished , process 2 is dispatched and runs for 4 time units. Now process 2 starts at time 20. When process 2 has finished at time 24, process 3 is dispatched and runs for 4 time units. Now process 3 starts at time 24 and finished at time 28. Now process 4 runs for 4 time units.  There have been 32 time units used (20+4+4+4) when process 4 has finished.

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 

20 

20 

0 

Process 2 

0 

4 

24 

20 

Process 3 

0 

4 

28 

24 

Process 4 

0 

4 

32 

28 

Waiting time for process

Process 1

Waiting time = 20-20-0

Waiting time=0

Process 2

Waiting Time= 24-4-0

Waiting Time=20

process3

Waiting Time=28-4-0

Waiting Time=24

Process4

Waiting Time=32-4-0

Waiting Time=28

Average Waiting Time

Average waiting time for whole set of processes can be calculated by adding all processes waiting times and dividing by the number of processes.

Average Waiting Time = (0+20+24+28)/4

  Average Waiting Time =  72/4

Average Waiting Time = 18

Example(2) 

Process Name 

Arrival Time 

Burst Time 

Process 1 

0 

4 

Process 2 

0 

4 

Process 3 

0 

4 

Process 4 

0 

20 


Gantt Chart


Process 1 

Process 2 

Process 3 

Process 4 

0               4 

               8                                                          

                12                                                     

                     32                            


Process I is dispatched  and runs for 4 time units. When process i has finished , process 2 is dispatched and run for 4 time units. Now process 2 starts at time 4. When process 2 has finished at time 8, process 3 is dispatched and runs for 4 time units. Now process 3 starts at time 8 and finished at time 12. Now process 4 runs for 20 time units. There have been 32 time units use (4+4+4+20) when process 4 has finished.


Process Name 

Arrival Time 

Burst Time 

Finish Time 

Waiting Time 

Process 1 

0 

4 

4 

0 

Process 2 

0 

4 

8 

4 

Process 3 

0 

4 

12 

8 

Process 4 

0 

20 

32 

12 


Waiting time for process

Process 1

Waiting time = 20--0

Waiting time=0

Process 2

Waiting Time= 8-4-0

Waiting Time=4

process3

Waiting Time=12-4-0

Waiting Time=8

Process4

Waiting Time=32-20-0

Waiting Time=12

Average Waiting Time

Average Waiting Time = (0+4+8+12)/4

  Average Waiting Time =  24/4

Average Waiting Time = 6

There is a huge difference between example 1 and example 2. Average waiting time in example 1 is 24 and in example 2 is 6. So FCFS scheduling is not preemptive. FCFS is not good scheduling algorithm.

Shortest Job First Scheduling


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