Process Scheduling Algorithms.pdf

Process Scheduling Algorithms

1. Operating System
Lecture 05
Mohammad Ashraful Islam
Lecturer
Department of Computer Science and Engineering,
Jahangirnagar University

2. Scheduling Criteria
CPU utilization –keep the CPU as busy as possible
Throughput–# of processes that complete their execution per time
unit
Turnaround time –amount of time to execute a particular process
TAT = CT -AT
Waiting time –amount of time a process has been waiting in the ready
queue
TAT -BT
Response time –amount of time it takes from when a request was
submitted until the first response is produced, not output (for time-
sharing environment)

3. Scheduling Algorithm Optimization Criteria
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time

4. OS Scheduling Algorithms
First-Come, First-Served (FCFS) Scheduling
Shortest-Job-Next (SJN) Scheduling
Priority Scheduling
Shortest Remaining Time
Round Robin(RR) Scheduling
Multiple-Level Queues Scheduling

5. First-Come, First-Served (FCFS) Scheduling
Jobs are executed on first come, first serve basis.
It is a non-preemptive, pre-emptive scheduling algorithm.
Easy to understand and implement.
Its implementation is based on FIFO queue.
Poor in performance as average wait time is high.
Implemented in early batch systems.

6. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P
1 24
P
2 3
P
3 3
Suppose that the processes arrive in the order: P
1, P
2, P
3
The Gantt Chart for the schedule is:
Waiting time for P
1= 0; P
2= 24; P
3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17P P P
1 2 3
0 24 3027

7. First-Come, First-Served (FCFS) Scheduling
EXAMPLEDATA:
Process Arrival Burst
Time Time
1 0 8
2 1 4
3 2 9
4 3 5
Waiting time for P
1= ?; P
2= ?; P
3 = ?; P
4 = ?
Average waiting time = ?
Calculate TAT for each process.
Average TAT = ?

8. Shortest-Job-First (SJF) Scheduling
AssociatewitheachprocessthelengthofitsnextCPUburst
Usetheselengthstoscheduletheprocesswiththeshortesttime
SJFisoptimal–givesminimumaveragewaitingtimeforagivensetof
processes
ThedifficultyisknowingthelengthofthenextCPUrequest
Couldasktheuser

9. Shortest-Job-First (SJF) Scheduling

Process Arrival TimeBurst Time
P
1 0 6
P
2 0 8
P
3 0 7
P
4 0 3
Consider the below processes available in the ready queue for execution, with arrival
time as 0 for all and given burst times.
SJF scheduling chart
Average waiting time = (3 + 16 + 9 + 0) / 4 = 7P
3
0 3 24
P
4
P
1
169
P
2

10. Shortest-Job-First (SJF) Scheduling

Process Arrival TimeBurst Time
P
1 0.0 6
P
2 2.0 8
P
3 4.0 7
P
4 5.0 3
Determine SJF scheduling chart
Determine AWT, ATAT

11. Preemptive Shortest-Job-First (SJF) Scheduling
EXAMPLEDATA:
Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9
4 3 5
1.DetermineWaitTimeforeachprocess,
2.AverageWaitingTime,
3.TATforeachprocess,
4.AverageTAT.

12. Preemptive Shortest-Job-First (SJF) Scheduling
EXAMPLEDATA:
Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9
4 3 5
DetermineWaitTime,AverageWaitingTime,TAT,
AverageTAT.

13. Shortest Running Time Scheduling
EXAMPLEDATA:
Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9
4 3 5
DetermineWaitTime,AverageWaitingTime,TAT,
AverageTAT.

14. Round Robin Scheduling
RoundRobin(RR)schedulingalgorithmismainlydesignedfortime-sharing
systems.ThisalgorithmissimilartoFCFSscheduling,butinRound
Robin(RR)scheduling,preemptionisaddedwhichenablesthesystemto
switchbetweenprocesses.
➢A fixed time is allotted to each process, called aquantum, for execution.
➢Once a process is executed for the given time period that process is
preempted and another process executes for the given time period.
➢Context switching is used to save states of preempted processes.

15. Round Robin Scheduling
EXAMPLEDATA:Quantum=3
Process Arrival Service
Time Time
1 0 8
2 0 4
3 0 9
4 0 5
DetermineWaitTime,AverageWaitingTime,TAT,
AverageTAT.

16. Round Robin Scheduling
EXAMPLEDATA:
Process Arrival Service
Time Time
1 0 8
2 1 4
3 2 9
4 3 5
DetermineWaitTime,AverageWaitingTime,TAT,
AverageTAT.

17. Time Sharing vs Parallel System
ParallelProcessingSystemsaredesignedtospeeduptheexecutionof
programsbydividingtheprogramintomultiplefragmentsandprocessing
thesefragmentssimultaneously.Suchsystemsaremultiprocessorsystems
alsoknownastightlycoupledsystems.Parallelsystemsdealwiththe
simultaneoususeofmultiplecomputerresourcesthatcanincludeasingle
computerwithmultipleprocessors,severalcomputersconnectedbya
networktoformaparallelprocessingclusteroracombinationofboth.
Parallelcomputingisanevolutionofserialcomputingwherethejobsare
brokenintodiscretepartsthatcanbeexecutedconcurrently.Eachpartis
furtherbrokendownintoaseriesofinstructions.Instructionsfromeachpart
executesimultaneouslyondifferentCPUs.

18. Time Sharing vs Parallel System
Time-sharingisatechniquethatenablesmanypeople,locatedatvarious
terminals,touseaparticularcomputersystematthesametime.Time-
sharingormultitaskingisalogicalextensionofmulti-programming.
Processor'stimewhichissharedamongmultipleuserssimultaneouslyis
termedtime-sharing.
MultiplejobsareexecutedbytheCPUbyswitchingbetweenthem,butthe
switchesoccursofrequently.Thus,theusercanreceiveanimmediate
response.Forexample,intransactionprocessing,theprocessorexecutes
eachuserprograminashortburstorquantumofcomputation.Thatis,
ifnusersarepresent,theneachusercangetatimequantum.Whentheuser
submitsthecommand,theresponsetimeisinfewsecondsatmost.

19. Thank You