Cpu scheduling

Understanding the concept of CPU scheduling

1. CPU Scheduling
BY
Dr. V. S. PRAKASH
Assistant Professor
Department of Computer Science (UG)
KristuJayantiCollege

2. Operating System Concepts
CPU Scheduling
•Basic Concepts
•Scheduling Criteria
•Scheduling Algorithms
•Multiple-Processor Scheduling
•Real-Time Scheduling
•Algorithm Evaluation

3. Operating System Concepts
Basic Concepts
•Maximum CPU utilization obtained with multiprogramming
•I/O Burst phase: –when the process waits for some IO
operation
–Process execution consists of a cycleof CPU execution and I/O
wait.
•CPU burst phase :distributionor when the process is allocated
CPU and other resource is executing

4. Operating System Concepts
Alternating Sequence of CPU And I/O Bursts

5. Operating System Concepts
Histogram of CPU-burst Times

6. CPU Scheduler
•Selects from among the processes in memory that are ready to
execute, and allocates the CPU to one of them.
•CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state.( I/O wait)
2.Switches from running to ready state.( Interrupt)
3.Switches from waiting to ready.(IO complete)
4.Process terminates.
Scheduling under 1 and 4 is nonpreemptive.
•Nonpreemptive: there is no choice for CPU scheduling ( Stop)
–Terminate or waiting state
–new process present in queue.
•All other scheduling is preemptive(2 and 3):
–Process has choice CPU scheduling and CPU is execute
based on the priority.

7. Dispatcher
•Dispatcher module gives control of the CPU to the process
selected by the short-term scheduler; this functionality involves:
–switching context: switching from one process to another
process
–switching to user mode: switching to kernel mode to user
mode
–jumping to the proper location in the user program to
restart that program
•Dispatch latency–time it takes to stop one process and start
another running process.

8. 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
•Waiting time –amount of time a process has been waiting in the
ready queue
•Response time –amount of time it takes from when a request
was submitted until the first response is produced, notoutput
(for time-sharing environment)

9. Optimization Criteria
•Max CPU utilization
•Max throughput
•Min turnaround time
•Min waiting time
•Min response time

10. FCFS: First Come First Serve
•FirstComeFirstServe,isjustlikeFIFO(FirstinFirstout)Queue
datastructure,wherethedataelementwhichisaddedtothe
queuefirst,istheonewholeavesthequeuefirst.
•ThisisusedinBatchSystems.
•It'seasytounderstandandimplementprogrammatically,using
aQueuedatastructure,whereanewprocessentersthrough
thetailofthequeue,andtheschedulerselectsprocessfrom
theheadofthequeue.
•AperfectreallifeexampleofFCFSschedulingisbuyingtickets
atticketcounter.
•Bursttime:thetimeCPUtakingcontrolofprocess

11. First-Come, First-Served (FCFS) Scheduling
•Example: 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 = 17
P
1 P
2 P
3
24 27 300

12. FCFS Scheduling (Cont.)
Suppose that the processes will arrive in the order
P
2, P
3, P
1.
•The Gantt chart for the schedule is:
•Waiting time for P
1 =6;P
2= 0
; P
3 = 3
•Average waiting time: (6 + 0 + 3)/3 = 3
•Much better than previous case.
•Convoy effectshort process behind long process
P
1P
3P
2
63 300

13. FCFS
•Problems:
1.It is non-preemptive
2.Improper process Scheduling
3.Resource unitization in parallel is not possible, which
leads to convey effect and hence poor resource
utilization
–convey effect: in which whole osslows down due to few slow
process.

14. Shortest-Job-First (SJF) Scheduling
•It is the best approach to minimize waiting time.
•It select the waiting process with the smallest
execution time to execute next.

15. Shortest-Job-First (SJF) Scheduling
•AssociatewitheachprocessthelengthofitsnextCPUburst.
Usetheselengthstoscheduletheprocesswiththeshortesttime.
•Twoschemes:
–nonpreemptive–onceCPUgiventotheprocessitcannot
bepreempteduntilcompletesitsCPUburst.
–Preemptive–ifanewprocessarriveswithCPUburstlength
lessthanremainingtimeofcurrentexecutingprocess,
preempt. Thisscheme isknow asthe
Shortest-Remaining-Time-First(SRTF).
•SJFisoptimal–givesminimumaveragewaitingtimeforagiven
setofprocesses.

17. Disadvantage:
Thetotalexecutiontimeofjobmustbeknownbefore
executionwhileitisnotpossibletoperfectlypredict
execution

19. Shortest-Remaining-Time-First (SRTF).
•AsyoucanseeintheGANTTchartabove,asP1arrivesfirst,
henceit'sexecutionstartsimmediately,butjustafter1ms,
processP2arriveswithabursttimeof3mswhichislessthan
thebursttimeofP1,hencetheprocessP1(1msdone,20ms
left)ispreemptiedandprocessP2isexecuted.
•AsP2isgettingexecuted,after1ms,P3arrives,butithasa
bursttimegreaterthanthatofP2,henceexecutionofP2
continues.Butafteranothermillisecond,P4arriveswithaburst
timeof2ms,asaresultP2(2msdone,1msleft)ispreemptied
andP4isexecuted.
•AfterthecompletionofP4,processP2ispickedupandfinishes,
thenP2willgetexecutedandatlastP1.
•ThePre-emptiveSJFisalsoknownasShortestRemaining
TimeFirst,becauseatanygivenpointoftime,thejobwiththe
shortestremainingtimeisexecutedfirst.

20. Process Arrival Time Burst Time
P
1 0.0 7
P
2 2.0 4
P
3 4.0 1
P
4 5.0 4
•SJF (non-preemptive)
•Average waiting time = (0 + 6 + 3 + 7)/4 -4
Example of Non-Preemptive SJF
P
1 P
3 P
2
73 160
P
4
8 12

21. Example of Preemptive SJF
Process Arrival Time Burst Time
P
1 0.0 7
P
2 2.0 4
P
3 4.0 1
P
4 5.0 4
•SJF (preemptive)
•Average waiting time = (9 + 1 + 0 +2)/4 -3
P
1 P
3P
2
42
110
P
4
5 7
P
2 P
1
16

22. Priority Scheduling
•A priority number (integer) is associated with each process
•The CPU is allocated to the process with the highest priority
(smallest integer highest priority).
–Preemptive
–nonpreemptive
•SJF is a priority scheduling where priority is the predicted next
CPU burst time.
•Problem Starvation –low priority processes may never
execute.
•Solution Aging –as time progresses increase the priority of the
process.

23. Priority Scheduling
•Priorityschedulingcanbeoftwotypes:
–PreemptivePriorityScheduling:Ifthenewprocess
arrivedatthereadyqueuehasahigherprioritythanthe
currentlyrunningprocess,theCPUispreempted,which
meanstheprocessingofthecurrentprocessisstoped
andtheincomingnewprocesswithhigherprioritygets
theCPUforitsexecution.
–Non-PreemptivePriorityScheduling:Incaseofnon-
preemptivepriorityschedulingalgorithmifanew
processarriveswithahigherprioritythanthecurrent
runningprocess,theincomingprocessisputatthe
headofthereadyqueue,whichmeansafterthe
executionofthecurrentprocessitwillbeprocessed.

24. Characteristics of Priority Scheduling
•ACPUalgorithmthatschedulesprocessesbasedonpriority.
•ItusedinOperatingsystemsforperformingbatchprocesses.
•IftwojobshavingthesamepriorityareREADY,itworksona
FIRSTCOME,FIRSTSERVEDbasis.
•Inpriorityscheduling,anumberisassignedtoeachprocess
thatindicatesitsprioritylevel.
•Lowerthenumber,higheristhepriority.
•Inthistypeofschedulingalgorithm,ifanewerprocessarrives,
thatishavingahigherprioritythanthecurrentlyrunning
process,thenthecurrentlyrunningprocessispreempted.

25. Example of Priority Scheduling Algorithm
•Considertheabovetableofprocesseswiththeir
respectiveCPUbursttimesandthepriorities.

26. Problem with Priority Scheduling
Algorithm
•Inpriorityschedulingalgorithm,thechancesofindefinite
blockingorstarvation.
•Aprocessisconsideredblockedwhenitisreadytorunbut
hastowaitfortheCPUassomeotherprocessisrunning
currently.
•Butincaseofpriorityschedulingifnewhigherpriority
processeskeepscominginthereadyqueuethenthe
processeswaitinginthereadyqueuewithlowerpriority
mayhavetowaitforlongdurationsbeforegettingtheCPU
forexecution.

27. Using Aging Technique with Priority
Scheduling
•Topreventstarvationofanyprocess,wecanusethe
conceptofagingwherewekeeponincreasingthe
priorityoflow-priorityprocessbasedontheitswaiting
time.
•Forexample,ifwedecidetheagingfactortobe0.5for
eachdayofwaiting,thenifaprocesswith
priority20(whichiscomparitivelylowpriority)comesin
thereadyqueue.Afteronedayofwaiting,itspriorityis
increasedto19.5andsoon.
•Doingso,wecanensurethatnoprocesswillhaveto
waitforindefinitetimeforgettingCPUtimefor
processing.

28. Round Robin Scheduling
•CPUisassignedtotheprocessonthebasisof
FCFSforafixedamountoftime.
•Thisfixedamountoftimeiscalledastime
quantumortimeslice.
•Afterthetimequantumexpires,therunning
processispreemptedandsenttotheready
queue.
•Then,theprocessorisassignedtothenext
arrivedprocess.
•Itisalwayspreemptiveinnature.
•RoundRobinSchedulingisFCFSScheduling
withpreemptivemode.

30. Advantages-
•Itgivesthebestperformanceintermsofaverageresponsetime.
•Itisbestsuitedfortimesharingsystem,clientserverarchitecture
andinteractivesystem.
Disadvantages-
•Itleadstostarvationforprocesseswithlargerbursttimeasthey
havetorepeatthecyclemanytimes.
•Itsperformanceheavilydependsontimequantum.
•Prioritiescannotbesetfortheprocesses.

31. Note(RRS)
Withdecreasingvalue
oftimequantum,
•Numberofcontext
switchincreases
•Response time
decreases
•Chancesofstarvation
decreases
Withincreasingvalue
oftimequantum,
•Numberofcontext
switchdecreases
•Response time
increases
•Chancesofstarvation
increases
•

32. Problem-01:
Process Id Arrival time Burst time
P1 0 5
P2 1 3
P3 2 1
P4 3 2
P5 4 3
Consider the set of 5 processes whose arrival time and burst time are given below-
If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate the average waiting time and average turn around time.

33. Now, we know-
Turn Around time = Exit time –Arrival time
Waiting time = Turn Around time –Burst time
Process
Id
Exit time
Turn Around
time
Waiting time
P1 13
13 –0 =
13
13 –5 = 8
P2 12
12 –1 =
11
11 –3 = 8
P3 5 5 –2 = 3 3 –1 = 2
P4 9 9 –3 = 6 6 –2 = 4
P5 14
14 –4 =
10
10 –3 = 7
Average Turn Around time =
(13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6
unit
Average waiting time =
(8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit

34. Process Id Arrival time Burst time
P1 0 4
P2 1 5
P3 2 2
P4 3 1
P5 4 6
P6 6 3
Consider the set of 6 processes whose arrival time and burst time are given below-

35. P5, P6, P2, P5, P6, P2, P5, P4, P1, P3, P2, P1

36. Process Id Arrival time Burst time
P1 0 4
P2 1 5
P3 2 2
P4 3 1
P5 4 6
P6 6 3
Consider the set of 5 proceses whose arrival time and burst time are given below-
If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate the average waiting time and average turn around time.

37. Problem-01:
Process Id Arrival time Burst time
P1 0 5
P2 1 3
P3 2 1
P4 3 2
P5 4 3
Consider the set of 5 processes whose arrival time and burst time are given below-
If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate the average waiting time and average turn around time.

38. Example: RR with Time Quantum = 20
Process Burst Time
P
1 53
P
2 17
P
3 68
P
4 24
•The Gantt chart is:
•Typically, higher average turnaround than SJF, but better
response.
P
1P
2P
3P
4P
1P
3P
4P
1P
3P
3
02037577797117121134154162

39. P1=6, p2=5, p3=2, p4=3,p5=7

40. Multilevel Queue
•Ready queue is partitioned into separate queues:
foreground (interactive)
background (batch)
•Each queue has its own scheduling algorithm,
foreground –RR
background –FCFS
•Scheduling must be done between the queues.
–Fixed priority scheduling; i.e., serve all from foreground then
from background. Possibility of starvation.
–Time slice –each queue gets a certain amount of CPU time
which it can schedule amongst its processes; i.e.,
-80% to foreground in RR
-20% to background in FCFS

41. Multilevel Queue Scheduling

42. Multilevel Feedback Queue
•A process can move between the various queues; aging can be
implemented this way.
•Multilevel-feedback-queue scheduler defined by the following
parameters:
–number of queues
–scheduling algorithms for each queue
–method used to determine when to upgrade a process
–method used to determine when to demote a process
–method used to determine which queue a process will enter
when that process needs service

43. Multilevel Feedback Queues

44. Example of Multilevel Feedback Queue
•Three queues:
–Q
0–time quantum 8 milliseconds
–Q
1–time quantum 16 milliseconds
–Q
2–FCFS
•Scheduling
–A new job enters queue Q
0which is servedFCFS. When it
gains CPU, job receives 8 milliseconds. If it does not finish
in 8 milliseconds, job is moved to queue Q
1.
–At Q
1job is again served FCFS and receives 16 additional
milliseconds. If it still does not complete, it is preempted
and moved to queue Q
2.