CPU Scheduling Part-I.pdf

CPU scheduling is the basis of multi-programmed operating systems. By switching the CPU among processes, the operating system can make the computer more productive
- To introduce CPU scheduling, which is the basis for multi-programmed operating systems
- To describe various CPU-scheduling algorithms
- To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system
- To examine the scheduling algorithms of several operating systems

1. Amrita School of Engineering, Bangalore
Ms. Harika Pudugosula
Teaching Assistant
Department of Electronics & Communication Engineering

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

3. Objectives
CPUschedulingisthebasisofmultiprogrammedoperatingsystems.By
switchingtheCPUamongprocesses,theoperatingsystemcanmakethe
computermoreproductive
•TointroduceCPUscheduling,whichisthebasisformultiprogrammed
operatingsystems
•TodescribevariousCPU-schedulingalgorithms
•TodiscussevaluationcriteriaforselectingaCPU-schedulingalgorithmfor
aparticularsystem
•Toexaminetheschedulingalgorithmsofseveraloperatingsystems
3

4. Basic Concepts
•Inasingle-processorsystem,onlyoneprocesscanrunatatime
•OthersmustwaituntiltheCPUisfreeandcanberescheduled
•Theobjectiveofmultiprogrammingistohavesomeprocessrunningat
alltimes,tomaximizeCPUutilization
•Aprocessisexecuteduntilitmustwait,typicallyforthecompletionof
someI/Orequest
•Inasimplecomputersystem,theCPUthenjustsitsidle.Allthiswaiting
timeiswasted;nousefulworkisaccomplished
•Withmultiprogramming,wetrytousethistimeproductively,maximum
CPUutilization
4

5. Basic Concepts
•Withmultiprogramming,wetrytousethistimeproductively
•Severalprocessesarekeptinmemoryatonetime
•Whenoneprocesshastowait,theoperatingsystemtakestheCPU
awayfromthatprocessandgivestheCPUtoanotherprocess
•Thispatterncontinues...
5

6. Basic Concepts
•Processexecutionconsistsofa
cycleofCPUexecutionandI/O
wait-CPU-I/OBurstCycle
•CPUBurst-whentheprocessis
beingexecutedintheCPU
•I/OBurst-whentheCPUis
waitingforI/Oforfurtherexection
•CPUburstfollowedbyI/Oburst
•Eventually,thefinalCPUburst
endswithasystemrequestto
terminateexecution
6

7. Histogram of CPU-burst Times
7
•AnI/O-boundprogramtypicallyhasmanyshortCPUbursts
•ACPU-boundprogrammighthaveafewlongCPUbursts.

8. CPU Scheduler
•Short-term/CPUscheduler selects from among the processes inready
queue, and allocates the CPU to one of them
•Queue may be ordered in various ways
•CPU scheduling decisions may take place when a process:
1.Switches from running to waiting state
2.Switches from running to ready state
3.Switches from waiting to ready
4. Terminates
•For situations 1 and 4, there is no choice in terms of scheduling
A new process(if one exists in the ready queue) must be selected for
execution
•However, there is achoice for situations 2 and 3
8

9. CPU Scheduler
•Whenschedulingtakesplaceonlyundercircumstances1and4,wesay
thattheschedulingschemeisnonpreemptiveorcooperative
•Otherwise,itispreemptive
•Undernonpreemptivescheduling,oncetheCPUhasbeenallocatedto
aprocess,theprocesskeepstheCPUuntilitreleasestheCPUeitherby
terminatingorbyswitchingtothewaitingstate
•Underpreemptivescheduling,CPUhasbeentakenawayfroma
process,beforetheprocesshascompleteditsexecutionorbeforeitis
swictingtothewaitingstate
•Schedulingunder1and4isnonpreemptive
•Allotherschedulingispreemptive
•Consideraccesstoshareddata
•Considerpreemptionwhileinkernelmode
•ConsiderinterruptsoccurringduringcrucialOSactivities
9

10. Dispatcher
•DispatchermodulegivescontroloftheCPUtotheprocessselectedby
theshort-termscheduler;thisinvolves:
•switchingcontext
•switchingtousermode
•jumpingtotheproperlocationintheuserprogramtorestartthat
program
•Dispatchlatency–timeittakesforthedispatchertostoponeprocess
andstartanotherrunning
10

11. Scheduling Criteria
•CPUutilization–
•keeptheCPUasbusyaspossible
•Conceptually,CPUutilizationcanrangefrom0to100percent
•Inarealsystem,itshouldrangefrom40percent(foralightlyloaded
system)to90percent(foraheavilyloadedsystem).
•Throughput–
•Numberofprocessesthatcompletetheirexecutionpertimeunit
•Forlongprocesses,thisratemaybeoneprocessperhour
•Forshorttransactions,itmaybetenprocessespersecond
•Turnaroundtime–
•amountoftimetoexecuteaparticularprocess
•Theintervalfromthetimeofsubmissionofaprocesstothetimeof
completionistheturnaroundtime
11

12. Scheduling Criteria
•Turnaroundtime–
•Turnaroundtimeisthesumoftheperiodsspentwaitingtogetinto
memory,waitinginthereadyqueue,executingontheCPU,anddoing
I/O
•Waitingtime–
•TheCPU-schedulingalgorithmdoesnotaffecttheamountoftime
duringwhichaprocessexecutesordoesI/O
•Itaffectsonlytheamountoftimethataprocessspendswaitinginthe
readyqueue
•Waitingtimeisthesumoftheperiodsspentwaitingintheready
queue
•Responsetime–
•amountoftimeittakesfromwhenarequestwassubmitteduntilthe
firstresponseisproduced,notoutput(fortime-sharingenvironment)
12

13. Scheduling Algorithm Optimization Criteria
•Max CPU utilization
•Max throughput
•Min turnaround time
•Min waiting time
•Min response time
13

14. 14
References
1.SilberscatnzandGalvin,“OperatingSystemConcepts,”NinthEdition,John
WileyandSons,2012.

15. 15
Thank you