FCFS & SJF SchedulingAlgorithm
Dr. Shashi Kant Gupta
Professor, Department of CSA, SoET
Outlines
• Prerequisite of topic
• Problem Objective
• Basics
• Learning Outcomes
• References
1
Prerequisite of Topic
• Basic Concept of Operating System
• Services of operating System
• Process Concept
• Schedulers
• Process Scheduling Criteria
Problem Objective
• Understand about the Process Scheduling
• FCFSAlgorithm
• Examples of FCFSAlgorithm
FCFS
The first come first serve scheduling algorithm states that the process that
requests the CPU first is allocated the CPU first.
Characteristics of FCFS
• FCFS supports non-preemptive and preemptive CPU scheduling
algorithms.
• Tasks are always executed on a First-come, First-serve concept.
• FCFS is easy to implement and use.
• This algorithm is not very efficient in performance, and the wait time is
quite high.
• This is used in Batch System.
SELO: 5,8,9 Reference No.: R1, R2
Advantages
• It doesn't include any complex logic, it just puts the process requests
in a queue and executes it one by one.
• FCFS is pretty simple and easy to implement.
• Eventually, every process will get a chance to run, so starvation
doesn't occur.
SELO: 5,8,9 Reference No.: R1, R2
Disadvantages
• There is no option for pre-emption of a process. If a process is
started, then CPU executes the process until it ends.
• Because there is no pre-emption, if a process executes for a long
time, the processes in the back of the queue will have to wait for a
long time before they get a chance to be executed.
SELO: 5,8,9 Reference No.: R1, R2
Shortest Job First Scheduling
• Shortest Job First scheduling works on the process with the
shortest burst time or duration first.
• This is the best approach to minimize waiting time.
• This is used in Batch Systems.
• The burst time/duration time of the processes should be known to the
processor in advance, which is practically not feasible all the time.
• This scheduling algorithm is optimal if all the jobs/processes are
available at the same time.
SELO: 5,8,9 Reference No.: R1, R2
Types of SJF
– Non Pre-emptive
– Pre-emptive
SELO: 5,8,9 Reference No.: R1, R2
Problem with Non Pre-emptive SJF
• Starvation
• Aging
SELO: 5,8,9 Reference No.: R1, R2
Advantages
• Short processes are executed first and then followed by longer
processes.
• The throughput is increased because more processes can be executed
in less amount of time.
SELO: 5,8,9 Reference No.: R1, R2
Disadvantages
• The time taken by a process must be known by the CPU beforehand,
which is not possible.
• Longer processes will have more waiting time, eventually they'll
suffer starvation.
SELO: 5,8,9 Reference No.: R1, R2
Learning Outcomes
After this Lecture students are able to:
• Process Scheduling
• FCFSAlgorithm working
SELO: 5,8,9 Reference No.: R1, R2
assignment FCFS/SJF
• Given 4 Processes
Process Arrival Time (msec) Burst Time (msec)
P1 0 15
P2 1 7
P3 2 12
P4 3 5
• Apply FCFS algorithm and Find theAWT andATT
References
1. A. Silberschatz, P. B. Galvin, G. Gagne; Operating System
Concepts; Wiley Publishing.
2. A. S. Tanenbaum; Modern Operating System; PHI Publication.
SELO
5. Design Thinking ability
[Link] to understand subject related concepts clearly along
with contemporary issues.
[Link] of concepts of topic and its technological
applications
