现代操作系统复习Review2015

1、Modern Operating Systems ReviewZhang YangSpring 2014Chapter 1 Introduction nWhat is an OS?It is an extended machineIt is a resource managernHistory of OSFirst generation, no OSSecond generation, early batch systemThird generation, multiprogramming, spooling and timesharingFourth generationnOperating

2、 System StructureMonolithic SystemLayered SystemMicrokernelClient-Server Model Virtual MachineExokernelChapter 2 Process (1) nProcess ModelMultiprogramming, concurrencynProcessDefinition: an executing programProcess vs. programProgramp The collection of instruction, static conceptpA program can be t

3、he execution program of multiple processProcesspDescribe concurrency, dynamic conceptpA process include program ,data ,and PCBpTemporarypA process can call multiple programChapter 2 Process (2) nProcess StatesThree states: running, ready, blockTransition between StatesnProcess Control BlockA data st

4、ructure in the operating system kernel containing the information needed to manage a particular process. OS maintains a PCB for each process.Chapter 2 Process (3) Chapter 2 Process (4) nProcess Context SwitchSwitch CPU from one process to another, performed by scheduler Expensive (1-1000ms), no usef

5、ul work is done (pure overhead)Chapter 2 Process (5) nProcess Creation EventsSystem InitializationExecution of a process creation system callUser request to create a new processInitiation of a batch jobnLinux Process Creation: fork( )nProcess Termination EventsNormal exit (voluntary)Error exit (volu

6、ntary)Fatal error (involuntary)Killed by another process (involuntary)Chapter 2 Process (6) nThreadDefinition: A sequential execution stream within a process (also called lightweight process)Advantages nCreating a thread is (much) cheaper than a process (10-20 times)nSwitching to a different thread

7、in same process is (much) cheaper (5-50 times)nThreads within same process can share data and other resources more conveniently and efficiently (without copying or messages)nThreads within a process are not protected from each otherChapter 2 Process (7) nThreadThe Thread ModelImplementation: user sp

8、ace, kernel space, hybridChapter 2 Process (8) nProcess vs.ThreadProcessnUnit of resource ownership with respect to the execution of a single programnCan encompass more than one thread of executionnProcesses are largely independentnExpensive creationnExpensive context switchingThreadnUnit of executi

9、onnBelongs to a processnThreads are part of the same “job” and are actively and closely cooperatingnInexpensive creationnInexpensive context switchingChapter 2 Process (9)User-LevelnManaged by applicationnKernel not aware of threadnContext switching cheapnCreate as many as needednMust be used with c

10、areKernel-LevelnManaged by kernelnConsumes kernel resourcesnContext switching expensive nNumber limited by kernel resourcesnSimpler to useKey issue: kernel threads provide virtual processors to user-level threads, but if all of kthreads block, then all user-level threads will block even if the progr

11、am logic allows them to proceedUser-LevelnManaged by applicationnKernel not aware of threadnContext switching cheapnCreate as many as needednMust be used with careKernel-LevelnManaged by kernelnConsumes kernel resourcesnContext switching expensive nNumber limited by kernel resourcesnSimpler to usen

12、User-Level vs. Kernel ThreadsChapter 2 Process (10) nIPCRace conditionnThe situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last.Critical region or sectionnPart of the process code that affects th

13、e shared resource.nFour requirementsSemaphore and PV operationsClassical IPC problemsnUsing semaphore to solveProducer-Consumer ProblemReaders and Writers ProblemDining Philosophers ProblemSemaphore as Synchronization Tool nExecute B in Pj only after A executed in PinUse semaphore S initialized to 0

14、nCode:Pi PjA P(S)V(S) BChapter 2 Process (11) nProcess ScheduleWhen to schedulenA new process startsnThe running process exitsnThe running process is blocked nI/O interrupt (some processes will be ready)nClock interrupt (e.g. every 10 milliseconds)Schedule algorithmnBatch systemsFirst-Come First-Ser

15、ved (FCFS)Short Job FirstnInteractive systemRound RobinPriority SchedulingMulti Queue & Multi-level FeedbackChapter 3 Memory Management (1) nBasic Memory ManagementStatic RelocationnAt load time, OS adjusts addresses in process to reflect position in memorynOS cannot move process after relocatio

16、n Dynamic RelocationnRun-time mapping of virtual address into physical address with the support of some hardware mechanism nHardware adds relocation register (base) to virtual address to get physical addressFree Space ManagementnBit mapnLinked listChapter 3 Memory Management (2) nBasic Memory Manage

17、ment (ctd.)Storage Placement StrategynFirst fitnNext fitnBest fitnWorst fitnPagingAddress translation schemePage tables, TLB, multi-level page tables, inverted page tablesPage faultChapter 3 Memory Management (3) nPage Replacement AlgorithmOptimalFIFO: Beladys anomalySecond chanceNRUClockLRUNFUAging

18、Working setnA processs working set is the set of pages that it currently “needs”.Working set clockChapter 3 Memory Management (4) nDesign Issues for PagingResident Set ManagementnSet of a process pages which are in main memorynReplacement ScopeLocal ReplacementGlobal ReplacementnResident Set SizeFix

19、ed AllocationVariable AllocationnSegmentationAddress translationChapter 4 File System (1)nFile A named collection of related information that is recorded on secondary storage.nFile System A method for storing and organizing files and the data they contain to make it easy to find and access them.nBas

20、ic Functions of File SystemPresent logical (abstract) view of files and directoriesFacilitate efficient use of storage devicesSupport sharingnFile TypesRegular file: ASCII, BinaryDirectoryCharacter special fileBlock special fileChapter 4 File System (2) nDirectoryOne-level directory systemTwo-level

21、directory systemHierarchical directory systemnFile Storage ImplementationContiguous allocationLinked list allocation: FATIndexed allocation: i nodeChapter 4 File System (3) nShared Files Hard linkSymbolic linknBlock SizenDisk Space ManagementLinked listBit mapnFile System BackupLogical dump algorith

22、mnFile System ConsistencyChecking blockChecking directorynUnix V7 file systemChapter 5 Input/Output (1) nGoals of I/O softwareDevice IndependenceUniform NamingError HandlingSynchronous vs. Asynchronous TransferBufferingSharable vs. Dedicated Devices File access nPrincipals of I/O SoftwareProgrammed

23、I/OInterrupt-driven I/OI/O using DMAChapter 5 Input/Output (2) nI/O Software LayersInterrupt handlersDevice driversnAccept abstract read/write requests from the device-independent software above and translate them into concrete I/O-module-specific commandsnSchedule requests: optimize queued request

24、order for best device utilization (eg: disk arm)nInitialize the device, if needednManage power requirements and log device eventsDevice independent OS SoftwarenUniform interfacing to device deriversnBufferingnError reportingnAllocating and releasing dedicated devicesnProviding a device-independent block sizeUser-level I/O SoftwareChapter 5 Input/Output (3) nCylinder skewnDis