operating systems hybrid notes for computerscience.pdf

Operating systems notes for Computer Science

1. 2010-2011
Lecture Notes on Operating Systems

2. Lecture 1: Introduction to Operating Systems
•Anoperatingsystemisaprogramthatactsasan
intermediarybetweenauserofacomputerandthe
computerhardware.
•Thepurposeofanoperatingsystemistoprovidean
environmentinwhichausercanexecuteprograms.
Theprimarygoalofanoperatingsystemisthusto
makethecomputersystemconvenienttouse.
•Asecondarygoalistousethecomputerhardwarein
anefficientmanner.

3. Lecture 1: Introduction to Operating Systems
•Inbrief,anoperatingsystemisthesetofprograms
thatcontrolsacomputer.Someexamplesof
operatingsystemsareUNIX,Mach,MS-DOS,MS-
Windows,Windows/NT,OS/2andMacOS.
•Anoperatingsystemisanimportantpartofalmost
everycomputersystem.
•Acomputersystemcanbedividedroughlyintofour
components:thehardware,theoperatingsystem,
theapplicationprogramsandtheusers(Figure1.1).

5. Objectives of Operating Systems
•Tohidedetailsofhardwarebycreatingabstraction.
•Toallocateresourcestoprocesses(Manage
resources).
•Provideapleasantandeffectiveuserinterface.

6. History of Operating Systems
•The1940's-FirstGenerations
Theearliestelectronicdigitalcomputershadnooperatingsystems.
Machinesofthetimeweresoprimitivethatprogramswereoftenentered
onebitattimeonrowsofmechanicalswitches(plugboards).
Programminglanguageswereunknown(notevenassemblylanguages).
Operatingsystemswereunheardof.
•The1950's-SecondGeneration
Bytheearly1950's,theroutinehadimprovedsomewhatwiththe
introductionofpunchcards.TheGeneralMotorsResearchLaboratories
implementedthefirstoperatingsystemsinearly1950'sfortheirIBM701.
Thesystemofthe50'sgenerallyranonejobatatime.

7. •The1960's-ThirdGeneration
Thesystemsofthe1960'swerealsobatchprocessingsystems,butthey
wereabletotakebetteradvantageofthecomputer'sresourcesbyrunning
severaljobsatonce.
•FourthGeneration
WiththedevelopmentofLSI(LargeScaleIntegration)circuits,chips,
operatingsystementeredinthepersonalcomputerandtheworkstation
age.Microprocessortechnologyevolvedtothepointthatitbecomes
possibletobuilddesktopcomputersaspowerfulasthemainframesofthe
1970s.
History of Operating Systems

8. Lecture 2: Operating Systems Structure
•SystemComponents
•OperatingSystemsServices
•SystemCallsandSystemPrograms

9. System Components
•ProcessManagement
AprocessisonlyONEinstantofaprograminexecution.
Therearemanyprocessescanberunningthesameprogram.
Thefivemajoractivitiesofanoperatingsysteminregardtoprocess
managementare:
•Creationanddeletionofuserandsystemprocesses.
•Suspensionandresumptionofprocesses.
•Amechanismforprocesssynchronization.
•Amechanismforprocesscommunication.
•Amechanismfordeadlockhandling.

10. System Components
•Main-MemoryManagement
Main-Memoryisalargearrayofwordsorbytes.Eachwordorbyte
hasitsownaddress.Mainmemoryisarepositoryofquicklyaccessible
datasharedbytheCPUandI/Odevices.
Themajoractivitiesofanoperatingsysteminregardtomemory-management
are:
•Keeptrackofwhichpartofmemoryarecurrentlybeingusedandbywhom.
•Decidewhichprocessesareloadedintomemorywhenmemoryspace
becomesavailable.
•Allocateanddeallocatememoryspaceasneeded.

11. System Components
•File Management
Afileisacollectedofrelatedinformationdefinedbyits
creator.Computercanstorefilesonthedisk(secondary
storage),whichprovidelongtermstorage.
•The creation and deletion of files.
•The creation and deletion of directions.
•The support of primitives for manipulating files and directions.
•The mapping of files onto secondary storage.
•The backup of files on stable storage media.

12. System Components
•I/OSystemManagement
Oneofthepurposesofanoperatingsystemistohidethe
peculiaritiesofspecifichardwaredevicesfromtheuser.
•Secondary-StorageManagement
Generallyspeaking,systemshaveseverallevelsof
storage,includingprimarystorage,secondarystorageand
cachestorage.Instructionsanddatamustbeplacedinprimary
storageorcachetobereferencedbyarunningprogram.

13. System Components
•Networking
Adistributedsystemisacollectionofprocessorsthatdonotshare
memory,peripheraldevices,oraclock.Theprocessorscommunicatewith
oneanotherthroughcommunicationlinescallednetwork.
•ProtectionSystem
Protectionreferstomechanismforcontrollingtheaccessof
programs,processes,oruserstotheresourcesdefinedbyacomputer
system.
•CommandInterpreterSystem
Acommandinterpreterisaninterfaceoftheoperatingsystemwith
theuser.Theusergivescommandswithareexecutedbyoperatingsystem
(usuallybyturningthemintosystemcalls).

14. Operating Systems Services
•ProgramExecution
Thesystemmustbeabletoloadaprogramintomemoryandtorun
it.Theprogrammustbeabletoenditsexecution,eithernormallyor
abnormally(indicatingerror).
•I/OOperations
ArunningprogrammayrequireI/O.ThisI/Omayinvolveafileoran
I/Odevice.
•FileSystemManipulation
Theoutputofaprogrammayneedtobewrittenintonewfilesor
inputtakenfromsomefiles.Theoperatingsystemprovidesthisservice.
•ErrorDetection
Anerrorisonepartofthesystemmaycausemalfunctioningofthe
completesystem.Toavoidsuchasituationtheoperatingsystemconstantly
monitorsthesystemfordetectingtheerrors.

15. System Calls and System Programs
•Systemcallsprovidetheinterfacebetweenaprocessandthe
operatingsystem.Thesecallsaregenerallyavailableas
assembly-languageinstructions,andareusuallylistedinthe
manualsusedbyassembly-languageprogrammers.

16. Lecture 3:Process Management
•Theoperatingsystemisresponsibleforthefollowingactivitiesin
connectionwithprocessmanagement:thecreationanddeletionofboth
userandsystemprocesses;theschedulingofprocesses;andtheprovision
ofmechanismsforsynchronization,communication,anddeadlock
handlingforprocesses.
Process,ontheotherhand,includes:
•CurrentvalueofProgramCounter(PC)
•Contentsoftheprocessorsregisters
•Valueofthevariables
•Theprocessesstack(SP)whichtypicallycontainstemporarydatasuchas
subroutineparameter,returnaddress,andtemporaryvariables.
•Adatasectionthatcontainsglobalvariables.

17. ••ProcessProcessStateState
Asaprocessexecutes,itchangesstate.Thestateofa
processisdefinedinpartbythecurrentactivityofthat
process.Eachprocessmaybeinoneofthefollowingstates:
•NewState:Theprocessbeingcreated.
•RunningState:AprocessissaidtoberunningifithastheCPU,thatis,
processactuallyusingtheCPUatthatparticularinstant.
•Blocked(orwaiting)State:Aprocessissaidtobeblockedifitiswaitingfor
someeventtohappensuchthatasanI/Ocompletionbeforeitcan
proceed.Notethataprocessisunabletorununtilsomeexternalevent
happens.
•ReadyState:Aprocessissaidtobereadyifitiswaitingtobeassignedtoa
processor.
•Terminatedstate:Theprocesshasfinishedexecution.

18. Figure : Diagram of process states.

19. •ProcessControlBlock
•Eachprocessisrepresentedintheoperatingsystembya
processcontrolblockPCS)—alsocalledataskcontrolblock.
Process state
process number
program counter
Registers
memory limits
list of open files
.
.
Figure : Process control block.

20. Lecture 4: CPU Scheduling
•CPUschedulingisthebasisofmultiprogrammedoperating
systems.ByswitchingtheCPUamongprocesses,theoperating
systemcanmakethecomputermoreproductive.
•BasicConcepts
Theideaofmultiprogrammingisrelativelysimple.A
processisexecuteduntilitmustwait,typicallyforthe
completionofsomeI/Orequest.Inasimplecomputersystem,
theCPUwouldthenjustsitidle.
Schedulingisafundamentaloperating-systemfunction.
Almostallcomputerresourcesarescheduledbeforeuse.

21. •CPU-I/OBurstCycle
ThesuccessofCPUschedulingdependsonthefollowing
observedpropertyofprocesses:Processexecutionconsistsof
acycleofCPUexecutionandI/Owait.Processesalternate
backandforthbetweenthesetwostates.
•ContextSwitch
Togiveeachprocessonamultiprogrammedmachinea
fairshareoftheCPU,ahardwareclockgeneratesinterrupts
periodically.
Thisallowstheoperatingsystemtoscheduleallprocesses
inmainmemory(usingschedulingalgorithm)torunonthe
CPUatequalintervals.EachswitchoftheCPUfromone
processtoanotheriscalledacontextswitch.

22. •PreemptiveScheduling
CPUschedulingdecisionsmaytakeplaceunderthe
followingfourcircumstances:
1.Whenaprocessswitchesfromtherunningstatetothewaitingstate(for.
example,I/Orequest,orinvocationofwaitfortheterminationofoneof
thechildprocesses).
2.Whenaprocessswitchesfromtherunningstatetothereadystate(for
example,whenaninterruptoccurs).
3.Whenaprocessswitchesfromthewaitingstatetothereadystate(for
example,completionofI/O).
4.Whenaprocessterminates.

23. •Dispatcher
•Switchingcontext.
•Switchingtousermode.
•Jumpingtotheproperlocationintheuserprogramtorestartthatprogram
•SchedulingCriteria
•DifferentCPUschedulingalgorithmshavedifferentpropertiesandmay
favoroneclassofprocessesoveranother.Inchoosingwhichalgorithmto
useinaparticularsituation,wemustconsiderthepropertiesofthe
variousalgorithms.

24. •ManycriteriahavebeensuggestedforcomparingCPU
schedulingalgorithms.
•Criteriathatareusedincludethefollowing:
•CPUutilization.
•Throughput.
•Turnaroundtime.
•Waitingtime.
•Responsetime.

25. Lecture 5: Scheduling Algorithms
1.First-Come,First-ServedScheduling
2.Shortest-Job-FirstScheduling
3.PriorityScheduling
4.Round-RobinScheduling
5.MultilevelQueueScheduling
6.MultilevelFeedbackQueueScheduling

26. First-Come, First-Served Scheduling
ProcessBurst Time
P1 24
P2 3
P3 3
P1 P2P3
0 242730

27. Shortest-Job-First Scheduling
ProcessBurst Time
P1 6
P2 8
P3 7
P4 3
P4 P1 P3 P2
0 3 9 16 24

28. Priority Scheduling
ProcessBurst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
P2 P5 P1 P3 P4

29. Round-Robin Scheduling
ProcessBurst Time
P1 24
P2 3
P3 3

30. Multilevel Queue Scheduling

31. •Inamultilevelqueueschedulingprocessesarepermanently
assignedtoonequeues.
•Theprocessesarepermanentlyassignedtooneanother,
basedonsomepropertyoftheprocess,suchas
•Memorysize
•Processpriority
•Processtype
•Algorithmchoosestheprocessfromtheoccupiedqueuethat
hasthehighestpriority,andrunthatprocesseither
•Preemptiveor
•Non-preemptively

32. 6. Process Synchronization
•Acooperatingprocessisonethatcanaffectorbe
affectedbytheotherprocessesexecutinginthe
system.
•Cooperatingprocessesmayeitherdirectlysharea
logicaladdressspace(thatis,bothcodeanddata),or
beallowedtosharedataonlythroughfiles.The
formercaseisachievedthroughtheuseof
lightweightprocessesorthreads.Concurrentaccess
toshareddatamayresultindatainconsistency.
•Inthislecture,wediscussvariousmechanismsto
ensuretheorderlyexecutionofcooperating
processesthatsharealogicaladdressspace,sothat
dataconsistencyismaintained.

33. CooperatingProcesses
•Theconcurrentprocessesexecutingintheoperating
systemmaybeeitherindependentprocessesor
cooperatingprocesses.
•Aprocessisindependentifitcannotaffectorbe
affectedbytheotherprocessesexecutinginthe
system.
•Ontheotherhand,aprocessiscooperatingifitcan
affectorbeaffectedbytheotherprocessesexecuting
inthesystem.

34. •Thereareseveralreasonsforprovidinganenvironmentthat
allowsprocesscooperation:
Information sharing
Computationspeedup
Modularity
Convenience

35. Race condition
•Whenseveralprocessesaccessand
manipulatethesamedataconcurrentlyand
theoutcomeoftheexecutiondependsonthe
particularorderinwhichtheaccesstakes
place,iscalledaracecondition.

36. The Critical-Section Problem
•Theimportantfeatureofthesystemisthat,whenoneprocess
isexecutinginitscriticalsection,nootherprocessistobe
allowedtoexecuteinitscriticalsection.
•Thus,theexecutionofcriticalsectionsbytheprocessesis
mutuallyexclusiveintime.
•Thecritical-sectionproblemistodesignaprotocolthatthe
processescanusetocooperate.
•Eachprocessmustrequestpermissiontoenteritscritical
section.

37. •Asolutiontothecritical-sectionproblemmustsatisfy
thefollowingthreerequirements:
1.MutualExclusion:IfprocessPiisexecutinginitscritical
section,thennootherprocessescanbeexecutingintheir
criticalsections.
2.Progress:Ifnoprocessisexecutinginitscriticalsectionand
thereexistsomeprocessesthatwishtoentertheircritical
sections,thenonlythoseprocessesthatarenotexecutingin
theirremaindersectioncanparticipateinthedecisionof
whichwillenteritscriticalsectionnext,andthisselection
cannotbepostponedindefinitely.
3.BoundedWaiting:Thereexistaboundonthenumberoftimes
thatotherprocessesareallowedtoentertheircriticalsections
afteraprocesshasmadearequesttoenteritscriticalsection
andbeforethatrequestisgranted.

38. DEADLOCKS
•Aprocessrequestsresources;iftheresourcesarenot
availableatthattime,theprocessentersawaitstate.Itmay
happenthatwaitingprocesseswillneveragainchangestate,
•becausetheresourcestheyhaverequestedareheldbyother
waitingprocesses.Thissituationiscalledadeadlock.
•Inthislecture,wedescribemethodsthatanoperatingsystem
canusetodealwiththedeadlockproblem.

39. Resources
•A process must request a resource before using it, and must
release the resource after using it.
•A process may request as many resources as it requires to
carry out its designated task.
•a process may utilize a resource in only the following
sequence:
Use
Release
Request

40. DeadlockCharacterization
•Inadeadlock,processesneverfinishexecutingand
systemresourcesaretiedup,preventingotherjobs
fromeverstarting.
•Beforewediscussthevariousmethodsfordealing
withthedeadlockproblem,weshalldescribe
featuresthatcharacterizedeadlocks.

41. Necessary Conditions
•Adeadlocksituationcanariseifthefollowingfour
conditionsholdsimultaneouslyinasystem:
•Mutual exclusion
•Hold and wait
•No preemption
•Circular wait

42. Methods for Handling Deadlocks
•Principally,therearethreedifferentmethodsfor
dealingwiththedeadlockproblem:
•Wecanuseaprotocoltoensurethatthesystemwillnever
enteradeadlockstate.
•Wecanallowthesystemtoenteradeadlockstateandthen
recover.
•Ignoretheproblemandpretendthatdeadlocksneveroccurin
thesystem;usedbymostoperatingsystems,includingUNIX.

43. DeadlockPrevention
•Byensuringthatatleastoneoftheseconditionscannothold,
wecanpreventtheoccurrenceofadeadlock
MutualExclusion–notrequiredforsharableresources;mustholdfor
nonsharableresources.
HoldandWait–mustguaranteethatwheneveraprocessrequestsa
resource,itdoesnotholdanyotherresources.
NoPreemption–oIfaprocessthatisholdingsomeresourcesrequests
anotherresourcethatcannotbeimmediatelyallocatedtoit,thenall
resourcescurrentlybeingheldarereleased.
•CircularWait–imposeatotalorderingofallresourcetypes,andrequire
thateachprocessrequestsresourcesinanincreasingorderof
enumeration.

44. Deadlock Avoidance
•Requires that the system has some additional a priori
information available.
Simplestandmostusefulmodelrequiresthateachprocessdeclare
themaximumnumberofresourcesofeachtypethatitmayneed.
Thedeadlock-avoidancealgorithmdynamicallyexaminesthe
resource-allocationstatetoensurethattherecanneverbea
circular-waitcondition.
Resource-allocationstateisdefinedbythenumberofavailableand
allocatedresources,andthemaximumdemandsoftheprocesses.

45. Deadlock Detection
•Ifasystemdoesnotemployeitheradeadlock-preventionora
deadlockavoidancealgorithm,thenadeadlocksituationmay
occur.Inthisenvironment,thesystemmustprovide:
Analgorithmthatexaminesthestateofthesystemto
determinewhetheradeadlockhasOccurred.
Analgorithmtorecoverfromthedeadlock

46. Memory ManagementMemory Management

47. Programmustbebrought(fromdisk)intomemory
andplacedwithinaprocessforittoberun.
MainmemoryandregistersareonlystorageCPUcan
accessdirectly.RegisteraccessinoneCPUclock(or
less).
Mainmemorycantakemanycycles.
CachesitsbetweenmainmemoryandCPUregisters.
Protectionofmemoryrequiredtoensurecorrect
operation.

60. Virtual Memory

95. Protection
Domain of Protection
Security
cryPtograPhy
authentication