A quick course in operating systemsRaphael FinkelComputer Science DepartmentUniversity of KentuckyLexington, [email protected] Systems 1What is an operating system?____________________________________Resource Principle____________________________________An operating system is a setof algorithms that allocateresources to processes.________________________________________________________________________Beautification Principle____________________________________An operating system is a setof algorithms thathide the detailsof the hardwareand provide a morepleasant environment.____________________________________Operating Systems 2What an operating system looks likenetworksterminalsdevice interfaceprocess interfacecards clockprocessesresponsestapesprintersdisksinterrupts device controlkerneluser interfaceother computersservice callsOperating Systems 3How the kernel is structureddevicesprocesseskernelservice callfaultinterruptinterruptpagediskclockstorage managerschedulerdisk driverenvelopeOperating Systems 4Dispatching processesservice callsEDCBAafterbeforekerneldevicesprocessesresponsesservice callsEDCBAkerneldevicesprocessesresponsesOperating Systems 5Virtualizing operating systeminteractive operating systembatch operating system21PPVphysical devicesvirtualizing kernelkernelvirtual devices virtual deviceskernelOperating Systems 6The resource of timelong termreadymedium termreadyruntransput waitreadyshort termmain-store waitOperating Systems 7Comparing short-term scheduling0 10 20 30 40 50 60 70 80 90 100Penalty ratioPercentile of time requiredPSPNPSPNFBFBRRRRSPNSPNHPRNHPRNFCFSFCFS100101Operating Systems 8Percentile of time requiredMissed timeRRRRFBFBHPRNHPRNPSPNSPNSPNFCFSFCFS1098765432101009080706050403020100Operating Systems 9Round robin scheduling191092020181186129313012931300 5 10 15 20ABDEA A AB B B B BD D D D DE E E E EC C0 5 10 15 20ABDEA B B D E D Eq = 1q = 4CCCOperating Systems 10The resource of space_______________________________Cache Principle_______________________________The more frequently dataare accessed,the faster the accessshould be._______________________________Operations that must beperformed oftenshould beperformed rapidly._______________________________archivecachehardware cacheSize: 1012bytesSize: 109bytesSize: 106bytesSize: 10 bytesAccess time: 50 mslong-term store: magnetic tapebacking store: diskmain storeAccess time: 50 nsAccess time: 500 nsAccess time: 50 sOperating Systems 11Address translation hardwarecputables translatormain storebusdatav addrp addrp addr datadataOperating Systems 12Pagingframepage offsetpresentframesionspermis-virtual addressphysical addressaddress-translation tableOperating Systems 13Paging on the VAXfedcba512 bytes512 bytesOffsetPage FramePage[14..22]Page in process page tablePresentPermitPageFramePage[2..13]Kernel Base RegisterKernel Page TablePresentPermitPageFrameS OffsetPage2320Virtual addressProcess Base RegisterOperating Systems 14Page-replacement strategiespage frames availableAreaMethod0 10 20 30 40 50 60 70 800100020003000400050006000700080009000100001146941047399415960360RandomFIFOLRUMincoldfaultsOperating Systems 15Serially reusable resourcesABtape 2tape 1tapeprinterprintertapeprocess Aprocess B123456 7 8Operating Systems 16What can be done to avoid the problem?foreknowledgewithconservativeavoid deadlockprevent deadlockwithout foreknowledgepossibledeadlockveryexpensive serializationliberalgrant if available one-shothierarchicalnever grantadvance-claim• One-shot allocation: A process may requestresources only when it has none at all.• Hierarchical allocation: A process may requestonly resources at a higher level than those itholds.• Advance claim: Each process registers a max-imum claim. It may never request more thanthe claim. The kernel blocks any request thatcan lead to an unsafe state.Operating Systems 17Safe stateThere is a sequence of processes that• can be finished in order,• even if they need their full claim• by blocking all other processes if necessary.________________________________Process Holding Claims________________________________A 4 6B 2 9C 4 11________________________________Unallocated 2________________________________Operating Systems 18Beautification: controlling devicesHardware organizationdevice driverinstructionsinterruptsdevicedatastatusdevice interfaceprocesseskerneldevice driverstatuscontrollerordersdevice device devicemainstoreinterruptsDMAprocesseskernelOperating Systems 19Software controlkernel task open close read writework queueinsertreorderremoveinterrupt controlupper driverlower driverawakenprocesseskerneldeviceskernel is emptyingprocess is readingkernel is fillingprocess is writinginput outputOperating Systems 20Disk-head schedulingarrival rateFCFSPickupSSFLookC-Look0 10203040506070809010048163264128Throughputarrival rateFCFSPickupSSFLookC-Look0 1020304050607080901000.030.060.120.250.501.002.004.008.0016.00Mean time to completeOperating Systems 21File structuresroot/users/smith/thesis/chapter1.textsmith.textsoftwaresimulate.forsimulate.runchapter1.textslide1.textJIR.textusersutilities fortran.runsmithtroymailthesiscoursespapersOperating Systems 22File access• (Access control) A file may be accessed undera given name by a process only if the processhas the appropriate access rights for all thedirectories in the given name of the file.• (Sequential access) File is opened, read orwritten from beginning to end, then closed.• (Direct access) File is opened, repeatedly posi-tioned and read/written, then closed.• (Mapped access) File is mapped into virtualspace of the process, accessed by ordinarymemory operations, then unmapped.• (Structured file) File is opened, repeatedlyindexed and read/written, then closed. A data-base is a collection of related structured files.Operating Systems 23Physical representation of files• Disk: collection of blocks.• Disk descriptor: Which blocks are free, whichhold file descriptors, which hold data blocks.• File descriptor: Which data blocks belong tothis file, and in which order.It is good to:• cluster blocks within a file• cluster file descriptors within a directory• provide enough redundancy to survive crashes• allow the end of a file to sit in a sub-block(fragment)Operating Systems 24Unix layout for huge filesOperating Systems 25Networked file systemsmachine 3machine 2machine 14 (13)3 (9)2 (5)1615141211108761161514131211109disk Fdisk Edisk Ddisk C12 3 4432187654321disk Bdisk AOperating Systems