William stallings computer organization and architecture 6th edition - Chapter 8: Operating system support

William Stallings Computer Organization and Architecture6th EditionChapter 8Operating System SupportObjectives and FunctionsConvenienceMaking the computer easier to useEfficiencyAllowing better use of computer resourcesLayers and Views of a Computer SystemOperating System ServicesProgram creationProgram executionAccess to I/O devicesControlled access to filesSystem accessError detection and responseAccountingO/S as a Resource ManagerTypes of Operating SystemInteractiveBatchSingle program (Uni-programming)Multi-programming (Multi-tasking)Early SystemsLate 1940s to mid 1950sNo Operating SystemPrograms interact directly with hardwareTwo main problems:SchedulingSetup timeSimple Batch SystemsResident Monitor programUsers submit jobs to operatorOperator batches jobsMonitor controls sequence of events to process batchWhen one job is finished, control returns to Monitor which reads next jobMonitor handles schedulingMemory Layout for Resident MonitorJob Control LanguageInstructions to MonitorUsually denoted by $e.g.$JOB$FTN... Some Fortran instructions$LOAD$RUN... Some data$ENDDesirable Hardware FeaturesMemory protectionTo protect the MonitorTimerTo prevent a job monopolizing the systemPrivileged instructionsOnly executed by Monitore.g. I/OInterruptsAllows for relinquishing and regaining controlMulti-programmed Batch SystemsI/O devices very slowWhen one program is waiting for I/O, another can use the CPUSingle ProgramMulti-Programming with Two ProgramsMulti-Programming with Three ProgramsUtilizationTime Sharing SystemsAllow users to interact directly with the computeri.e. InteractiveMulti-programming allows a number of users to interact with the computerSchedulingKey to multi-programmingLong termMedium termShort termI/OLong Term SchedulingDetermines which programs are submitted for processingi.e. controls the degree of multi-programmingOnce submitted, a job becomes a process for the short term scheduler(or it becomes a swapped out job for the medium term scheduler)Medium Term SchedulingPart of the swapping function (later)Usually based on the need to manage multi-programmingIf no virtual memory, memory management is also an issueShort Term SchedulerDispatcherFine grained decisions of which job to execute nexti.e. which job actually gets to use the processor in the next time slotProcess StatesProcess Control BlockIdentifierStatePriorityProgram counterMemory pointersContext dataI/O statusAccounting informationPCB DiagramKey Elements of O/SProcess SchedulingMemory ManagementUni-programMemory split into twoOne for Operating System (monitor)One for currently executing programMulti-program“User” part is sub-divided and shared among active processesSwappingProblem: I/O is so slow compared with CPU that even in multi-programming system, CPU can be idle most of the timeSolutions:Increase main memory ExpensiveLeads to larger programsSwappingWhat is Swapping?Long term queue of processes stored on diskProcesses “swapped” in as space becomes availableAs a process completes it is moved out of main memoryIf none of the processes in memory are ready (i.e. all I/O blocked)Swap out a blocked process to intermediate queueSwap in a ready process or a new processBut swapping is an I/O process...PartitioningSplitting memory into sections to allocate to processes (including Operating System)Fixed-sized partitionsMay not be equal sizeProcess is fitted into smallest hole that will take it (best fit)Some wasted memoryLeads to variable sized partitionsFixedPartitioningVariable Sized Partitions (1)Allocate exactly the required memory to a processThis leads to a hole at the end of memory, too small to useOnly one small hole - less wasteWhen all processes are blocked, swap out a process and bring in anotherNew process may be smaller than swapped out processAnother holeVariable Sized Partitions (2)Eventually have lots of holes (fragmentation)Solutions:Coalesce - Join adjacent holes into one large holeCompaction - From time to time go through memory and move all hole into one free block (c.f. disk de-fragmentation)Effect of Dynamic PartitioningRelocationNo guarantee that process will load into the same place in memoryInstructions contain addressesLocations of dataAddresses for instructions (branching)Logical address - relative to beginning of programPhysical address - actual location in memory (this time)Automatic conversion using base addressPagingSplit memory into equal sized, small chunks -page framesSplit programs (processes) into equal sized small chunks - pagesAllocate the required number page frames to a processOperating System maintains list of free framesA process does not require contiguous page framesUse page table to keep trackLogical and Physical Addresses - PagingVirtual MemoryDemand pagingDo not require all pages of a process in memoryBring in pages as requiredPage faultRequired page is not in memoryOperating System must swap in required pageMay need to swap out a page to make spaceSelect page to throw out based on recent historyThrashingToo many processes in too little memoryOperating System spends all its time swappingLittle or no real work is doneDisk light is on all the timeSolutionsGood page replacement algorithmsReduce number of processes runningFit more memoryBonusWe do not need all of a process in memory for it to runWe can swap in pages as requiredSo - we can now run processes that are bigger than total memory available!Main memory is called real memoryUser/programmer sees much bigger memory - virtual memoryPage Table StructureTranslation Lookaside BufferEvery virtual memory reference causes two physical memory accessFetch page table entryFetch dataUse special cache for page tableTLBTLB OperationTLB and Cache OperationSegmentationPaging is not (usually) visible to the programmerSegmentation is visible to the programmerUsually different segments allocated to program and dataMay be a number of program and data segmentsAdvantages of SegmentationSimplifies handling of growing data structuresAllows programs to be altered and recompiled independently, without re-linking and re-loadingLends itself to sharing among processesLends itself to protectionSome systems combine segmentation with pagingPentium IIHardware for segmentation and pagingUnsegmented unpagedvirtual address = physical addressLow complexityHigh performanceUnsegmented pagedMemory viewed as paged linear address spaceProtection and management via pagingBerkeley UNIXSegmented unpagedCollection of local address spacesProtection to single byte levelTranslation table needed is on chip when segment is in memorySegmented pagedSegmentation used to define logical memory partitions subject to access controlPaging manages allocation of memory within partitionsUnix System VPentium II Address Translation MechanismPentium II SegmentationEach virtual address is 16-bit segment and 32-bit offset2 bits of segment are protection mechanism14 bits specify segmentUnsegmented virtual memory 232 = 4GbytesSegmented 246=64 terabytesCan be larger – depends on which process is activeHalf (8K segments of 4Gbytes) is globalHalf is local and distinct for each processPentium II ProtectionProtection bits give 4 levels of privilege0 most protected, 3 leastUse of levels software dependentUsually level 3 for applications, level 1 for O/S and level 0 for kernel (level 2 not used)Level 2 may be used for apps that have internal security e.g. databaseSome instructions only work in level 0Pentium II PagingSegmentation may be disabledIn which case linear address space is usedTwo level page table lookupFirst, page directory1024 entries maxSplits 4G linear memory into 1024 page groups of 4MbyteEach page table has 1024 entries corresponding to 4Kbyte pagesCan use one page directory for all processes, one per process or mixturePage directory for current process always in memoryUse TLB holding 32 page table entriesTwo page sizes available 4k or 4MPowerPC Memory Management Hardware32 bit – paging with simple segmentation64 bit paging with more powerful segmentationOr, both do block address translationMap 4 large blocks of instructions & 4 of memory to bypass paginge.g. OS tables or graphics frame buffers32 bit effective address12 bit byte selector =4kbyte pages16 bit page id64k pages per segment4 bits indicate one of 16 segment registersSegment registers under OS controlPowerPC 32-bit Memory Management FormatsPowerPC 32-bit Address TranslationRequired ReadingStallings chapter 8Stallings, W. Operating Systems, Internals and Design Principles, Prentice Hall 1998Loads of Web sites on Operating Systems