东南大学操作系统课件(汪芸老师版)

Chapter 7: DeadlocksgAgenda•The Deadlock ProblemSystem Model•System Model•Deadlock Characterization •Methods for Handling Deadlocks( Prevention, Avoidance, Detection and (Prevention Avoidance Detection and Recovery )The Deadlock Problem•A set of blocked processes each holding a resource and waiting to acquire a resourceg qheld by another process in the set. Example•Example–System has 2 disk drives.–P1and P2each hold one disk drive and eachneeds another one.Bridge Crossing Exampleg g pThe Deadlock Problem •Examplep,–semaphores A and B, initialized to 1P0P1wait (A);wait(A);wait(B)wait (B);wait(A)gAgenda•The Deadlock ProblemSystem Model•System Model•Deadlock Characterization •Methods for Handling Deadlocks( Prevention, Avoidance, Detection and (Prevention Avoidance Detection and Recovery )ySystem Model•Resource types R 1, R2, . . ., R mCPU cycles, memory space, I/O devices •Each resource type R i has W i instances.•Each process utilizes a resource asEach process utilizes a resource asfollows:–request–use–releaseDeadlock CharacterizationDeadlock can arise if four conditions holdsimultaneously.•Mutual exclusion:only one process at a time can use a resource.•Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.h ld b hDeadlock CharacterizationNo preemption:a resource can be released •No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task that process has completed its task.•Circular wait:there exists a set {P 0, P 1, …, P 0} of waiting processes such that 0is waiting for a of waiting processes such that P 0 is waiting for a resource that is held by P 1, P 1is waiting for a resource that is held by P , …, P is waiting for y 2,,n –1g a resource that is held by P n , and P 0is waiting for a resource that is held by P 0.Resource-Allocation Graph pA set of vertices V and a set of edges E .•V is partitioned into two types:={}the set consisting of all –P = {P 1, P 2, …, P n }, the set consisting of all the processes in the system.–R = {R 1, R 2, …, R m }, the set consisting of all resource types in the system resource types in the system.Resource-Allocation Graphp•request edge –directed edge P1 →R j •assignment edge –directed edge R j→P iResource-Allocation Graph(Cont.)(Cont)•ProcessResource Type with 4 instances•P requests instance of R P i R ji j•P i is holding an instance of R j P i R j is holding an instance ofExamplepResource Allocation Graph With A DeadlockA DeadlockGraph With A Cycle But No DeadlockN D dl kComments•If graph contains no cycles ⇒nodeadlock.g p y•If graph contains a cycle ⇒if only one instance per resource type,then deadlock.then deadlockif several instances per resource type,possibility of deadlockpossibility of deadlock.gAgenda•The Deadlock ProblemSystem Model•System Model•Deadlock Characterization •Methods for Handling Deadlocks( Prevention, Avoidance, Detection and (Prevention Avoidance Detection and Recovery )Methods for HandlingDeadlocks•Ensure that the system will never enter a E th t th t ill t deadlock state.•Allow the system to enter a deadlock state and then recover.state and then recover•Ignore the problem and pretend that deadlocks never occur in the system;y p g y,used by most operating systems, including UNIX.Tolerance & RecoveryDetectionPrevention & AvoidanceDeadlock Prevention•Mutual Exclusion–not required for sharable resources; must hold forh bl t h ld f nonsharable resources.Deadlock Prevention•Hold and Wait–must guarantee that whenever a process requests a resource, whenever a process requests a resource it does not hold any other resources.–Low resource utilization; starvation possible.Deadlock Prevention•No Preemption–y–Process will be restarted only when it canregain its old resources, as well as the new ones that it is requesting.q gDeadlock Prevention•Circular Wait–impose a total ordering of all resource types, and require that eachll t d i th t h process requests resources in an increasing order of enumeration.Deadlock AvoidanceRequires that the system has some additionala priori information available.•Each process declare the maximum number ofresources of each type that it may need. resources of each type that it may need •Dynamically examines the resource-allocationstate to ensure that there can never be a state to ens re that there can ne er be a circular-wait condition.Deadlock Avoidance•Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of resources,and the maximum demands of the processes.Safe State•System is in safe state if there exists a q1,2,,nsequence <P, P, …, P> of ALL the processes is the systems such that for each P i, the resources that P i requests each P the resources that P i requests can be satisfied by currently available resources + resources held by all the P j, resources+resources held by all the with j < i.Safe State Safe State–If Pi resource needs are not immediatelyavailable, then Pi can wait until all Pjhavef inished.–When P is finished, Pi can obtain neededjresources, execute, return allocated resources, and terminate.–When Pi terminates, Pi +1can obtain itsneeded resources, and so on.,Comments•If a system is in safe state ⇒noIf t i i f t tdeadlocks.•If a system is in unsafe state ⇒possibility of deadlock.•Avoidance ⇒ensure that a system will A id th t t ill never enter an unsafe state.Safe, Unsafe , Deadlock State Deadlock StateAvoidance algorithmsg•Single instance of a resource type. Use a resource-allocation graphUse a resource allocation graph•Multiple instances of a resource type. Use the banker’s algorithmResource-Allocation GraphpUnsafe State Unsafe StateResource-Allocation GraphAlgorithm•Suppose that process P i requests a resource R jThe request can be granted only if •The request can be granted only if converting the request edge to an assignment edge does not result in the assignment edge does not result in the formation of a cycle in the resourcell ti hallocation graphgBanker’s Algorithm•Multiple instances.M ltiple instancesp p•Each process must a priori claimmaximum use.•When a process requests a resource it When a process requests a resource itmay have to wait.•When a process gets all its resources itmust return them in a finite amount of must return them in a finite amount oftime.Data StructuresData StructuresLet n= number of processes, and m = number of resources types. •Available:Vector of length m. If available [j]yp j = k, there are k instances of resource type Ravailable.•Max: n x m matrix. If Max [i,j] = k, then:n x m matrix If Max i j]=then process P i may request at most k instancesf tof resource type R j.Data Structures•Allocation: n x m matrix. If Allocation[i,j] = k then P i is currently allocated kth i tl ll t d instances of R j.j•Need: n x m matrix. If Need[i,j] =k, then P i may need k more instances of R j tomay need more instances of to complete its task.i j]i j]i j]Need[i,j]= Max[i,j] –Allocation[i,j].Safety Algorithmy g1.Let Work and Finish be vectors ofg,p ylength m and n, respectively. Initialize: Work = AvailableFinish [i] =false for i= 0, 1, …, n-1.2.Find any i such that both:(a) Finish i] = false()[]≤Work(b) NeediIf no such i exists,go to step4.If no such i exists, go to step 4.y gSafety Algorithm3.Work= Work + Allocation iFinish[i] =true]=go to step 2.4.If Finish[i] == true for all i, then the 4If Fi i h]t f ll th th system is in a safe state.for Process Pfor Processi1.If Request i≤Need i go to step2.,, Otherwise, raise error condition, since process has exceeded its maximumclaim.2.If Request i≤Available, go to step3.Otherwise P i must wait, sinceOtherwise must wait sinceresources are not available.for Processfor Process Pi3.Pretend to allocate requested resources to Pi by modifying the state as follows:Available= Available –Request;Allocation= Allocation+ Request;i i iNeedi =Needi–Requesti;z If safe the resources are allocated to Pi.⇒z If unsafe ⇒Pi must wait, and the old resource-allocation state is restoredExamplep• 5 processes P0 through P4;3resource types:3 resource types:A(10 instances),B(5instances),C(7 instances).Examplep:S h t t ti•Snapshot at time TAllocation Max AvailableA B C A B C A B C0 1 07 5 3 3 3 2P0107533322 0 03 2 2P13 0 2 9 0 2P30290222 1 1 2 2 2P3P0 0 2 4 3 34Examplep•The content of the matrix Need is defined to be Th t t f th t i N d i d fi d t b Max–Allocation.NeedA B CP7 4 31 2 2122P16 0 0P2P0 1 13P 4 3 14ExampleThe system is in a safe state since the •The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria.safety criteriaExample: P Request (1,0,2)p1q()•Check that Request ≤Available (that is, (1,0,2) Check that Request Available(that is(102)≤(3,3,2) ⇒true.Allocation Need AvailableAll ti N d A il blA B C A B C A B CP0 1 0 7 4 3 2 3 03 0 20 2 0P30202013 0 1 6 0 0P22 1 1 0 1 1211011P30 0 2 4 3 1P4Example: P Request (1,0,2)p1q()•Executing safety algorithm shows thatE ti f t l ith h th tsequence < P, P, P, P, P> satisfies13402safety requirement.•Can request for (3,3,0) by P4be granted?Can request for(330)by be granted?•Can request for (0,2,0) by P0be granted?Deadlock Detection•Allow system to enter deadlock state •Detection algorithm•Recovery schemeSingle Instance ofEach Resource TypeEach Resource Type•Maintain wait-for graphNodes are processes–Nodes are processes.–P→P j if P i is waiting for P j.iy g •Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle there exists a deadlockis a cycle, there exists a deadlock.Single Instance ofEach Resource TypeE h R T•An algorithm to detect a cycle in a graph requires an order of n2operations,e e s t e u be o e t ces t e where n is the number of vertices in the graph.Resource-Allocation Graphand Wait-for Graphd W it f G hResource-Allocation Graph Corresponding wait-for graph。

Chapter 8: Main MemoryAgendag•AddressSwapping•Swapping•Contiguous Memory Allocation •Paging•SegmentationgBackground•Program must be brought (from disk) into P t b b ht(f di k)i t memory and placed within a process for it to be run•Main memory and registers are only Main memory and registers are only storage CPU can access directly •Register, main memory and cache Protection of memory•Protection of memoryBase and Limit Registersp g•A pair of base and limit registers define the logical address spaceMultistep Processing of a User ProgramBinding of Instructions andData to MemoryData to Memoryz Compile time: absolute code can be generated; must recompile code if starting location changes z Load time: relocatable codez Execution time: Need hardware support for address mapsLogical vs. Physical AddressSpace–Logical address–generated by the CPU;Logical address generated by the CPU;also referred to as virtual address–Physical address–address seen by thePh i l dd dd b thmemory unit•in compile-time and load-time address-binding schemesbinding schemes•in execution-time address-binding hschemeMemory-Management Unit(MMU)•Map virtual to physical address •Physical address = the value in therelocation register + every address relocation register+every addressgenerated by a user processDynamic relocation using a relocation register using a relocation registery gDynamic LoadingRoutine is not loaded until it is called •Routine is not loaded until it is called •Better memory-space utilization; unused routine is never loadedUseful when large amounts of code are •Useful when large amounts of code are needed to handle infrequently occurring cases•No special support from the operating system is requiredLinking g•Static linking•Dynamic linking in load timeD i li ki i l d tiy g•Dynamic linking in execution timeDynamic Linking in execution timey g•Linking postponed until execution timeLi ki t d til ti tip,,•Small piece of code, stub, used to locate the appropriate memory-resident libraryroutine•Stub replaces itself with the address of the routine, and executes the routineti d t th tiSystem also known as shared libraries •System also known as shared librariesgAgenda•AddressS i•Swappingg y •Contiguous Memory Allocation •Paging•SegmentationS t tiSwappingpp g• A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued executionb k i t f ti d ti •Backing store–fast disk; must provide direct Backing store fast disk m st pro ide direct access to these memory imagesSwappingpp g•Swapping space management•Roll out, roll in–swapping variant used for priority-based scheduling algorithms•I/O problemppp g Schematic View of SwappingAgendag•AddressSwapping•Swapping•Contiguous Memory Allocation •Paging•SegmentationgContiguous Allocation•Main memory usually into twoppartitions:–Resident operating system, usually heldin low memory with interrupt vectorin low memory with interrupt vector–User processes then held in highmemoryContiguous Allocationg•Relocation registers used to protect R l ti i t d t t t user processes from each other, and from changing operating-system code and data–Base register–Limit registerLimit register–MMU maps logical address dynamicallyHW address protection with base and limit registers base and limit registersg()Contiguous Allocation (Cont.)•Multiple-partition allocationM lti l titi ll tiy–Hole –block of available memory; holes ofvarious size are scattered throughout memoryWhen a process arrives, it is allocated memory –When a process arrives,it is allocated memoryfrom a hole large enough to accommodate it–Operating system maintains information about:Operating system maintains information about:a) allocated partitions b) free partitions (hole)g() Contiguous Allocation (Cont.)OS OS OS OS process 5process 5process 5process 5process 9process 9 process 8process 10 process 2process 2process 2process 2ProblemP bl t t t H t ti fz Problem statement:How to satisfy a request of size n from a list of free holes z Solutions:•First-fit: Allocate the first hole that is big enoughProblem•Best-fit: Allocate the smallest hole that is B t fit All t th ll t h l th t i big enough; must search entire list, unless ordered by size–Produces the smallest leftover hole•Worst-fit: Allocate the largest hole; must also search entire listalso search entire list–Produces the largest leftover holeFirst-fit and best-fit better than worst-fit in terms ofFi t fit d b t fit b tt th t fit i t fspeed and storage utilizationFragmentationg•External Fragmentation–total External Fragmentation total memory space exists to satisfy a request, but it is not contiguous Internal Fragmentation allocated •Internal Fragmentation–allocated memory may be slightly larger than requested memory; this size difference requested memory;this size difference is memory internal to a partition, but not being usedb i dFragmentationg•Reduce external fragmentation bypcompaction–Shuffle memory contents to place all freememory together in one large blockmemory together in one large block–Compaction is possible only if relocation is dynamic, and is done at execution timedynamic and is done at execution timeAgendag•AddressSwapping•Swapping•Contiguous Memory Allocation •Paging•Segmentationg gPaging•Logical address space of a process can L i l dd fbe noncontiguous•Divide physical memory into fixed-sizedblocks called frames(size is power of 2, blocks called(size is power of2between 512 bytes and 8,192 bytes)•Divide logical memory into blocks ofp gsame size called pagesAddress Translation Scheme•Page table•Address generated by CPU is divided into: Add t d b CPU i di id d i t ---Page number (p)---Page offset (d)g gPaging HardwarePaging Model of Logical and Physical MemoryPhysical MemoryPaging Example32-byte memory and 4-byte pagesFree FramesBefore allocation After allocationp g Implementation of Page Table•Page table is kept in main memory •Page-table base register (PTBR)Page-table base register(PTBR)points to the page table•Page-table length register (PRLR)p gindicates size of the page table •Two memory accessesp gImplementation of Page Table•Associative memory or translationlook aside buffers (TLBs): a special look-aside buffers(TLBs):a special fast-lookup hardware cache•Store address-space identifiers (ASIDs) St dd id tifi(ASID) in each TLB entryPage#Frame#Associative Memory y•Associative memory –parallel search •Address translation (p, d)Address translation(p d)–If p is in associative register, get frame # outo t–Otherwise get frame # from page table in memoryg gPaging Hardware With TLBEffective Access Time •Associative Lookup = εtime unit A i ti L k ti it Assume memory cycle time is 1 •Assume memory cycle time is1 microsecond•Hit ratio = αHit ti()•Effective Access Time(EAT) EAT = (1 + ε) α+ (2 + ε)(1 –α)2= 2 + ε-αyMemory Protection•Memory protection implemented by assoc a g p o ec o b eac a e associating protection bit with each frame•Read/write bit•Valid-invalid bit attached to each entry in p gthe page tableStructure of the Page Tableg •Hierarchical Pagingg•Hashed Page Tables •Inverted Page TablesgHierarchical Page Tables•Break up the logical address spacep p ginto multiple page tables•A simple technique is a two-level A i l t h i i t l l page tablegTwo-Level Page-Table SchemeAddress-Translation Schemepage number page offsetpage number page offsetp i p2d121010Three-level Paging Schemeg gHashed Page TablesgCommon in address spaces > 32 bits •Common in address spaces>32bits •The virtual page number is hashed into a page table.•Virtual page numbers are compared in this chain searching for a match. If i thi h i hi f t h Ifa match is found, the corresponding physical frame is extracted.g Hashed Page TablegInverted Page Table•One entry for each real page of memory •Entry consists of the virtual address of E t i t f th i t l dd f the page stored in that real memory location, with information about the process that owns that pageprocess that owns that pageInverted Page Table ArchitectureAgendag•AddressSwapping•Swapping•Contiguous Memory Allocation •Paging•SegmentationSegmentationg•Memory-management scheme that supports user view of memory supports user view of memory•A program is a collection of segments.。

师范学院2014~2015学年第二学期期末考试一、单项选择（30分）1、设计多道批处理系统时，首先要考虑的是（ B ）A、灵活性和可适应性B、交互性和响应时间C、系统效率和吞吐量D、实时性和可靠性2、下列选项中不会会产生新进程的是（C ）A、用户登录B、应用请求C、设备分配D、作业调度3、某计算机系统中若同时存在五个进程，则处于阻塞状态的最多和就绪状态最多分别有（C）A、1个，5个B、4个，5个C、5个,4个D、0个，1个4、设某类资源有5个，由3个进程共享，每个进程最多可申请多少资源而使系统不会死锁。

（ B ）A、1 个B、2 个C、3 个D、4个5、设某计算机的逻辑地址空间为64KB，按字节编址。

若某进程最多需要6页数据存储空间，页的大小为1KB，当进程要访问逻辑地址为17CAH的数据，请问该逻辑地址对应的页号是（C）A、2B、3C、5D、06、在一个请求页式存储管理系统中，进程P共有5页。

访问串为3、2、1、0、3、2、4、3、2、1、0、4时，下列叙述不正确的是（D）A、采用FIFO置换算法，物理块为3时，缺页率f=75%B、采用LRU置换算法，物理块为4时，缺页次数为8次C、采用FIFO置换算法，物理块越多，缺页率越高，这是FIFO 特有的。

D、采用LRU置换算法，物理块为3时，缺页率f=78%7、设置通道后，CPU向通道发送一条I/O指令，通道接受指令执行通道程序，完成后向CPU发送中断信号。

此过程中，通道程序是（A）A、在内存中B、在CPU中C、在通道中D、在外部设备中8、下列关于中断I/O方式和DMA方式比较的叙述中，错误的是( D ) A.中断I/O方式请求的是CPU处理时间，DMA方式请求的是总线使用权B.中断响应发生在一条指令执行结束后，DMA响应发生在一个总线事务完成后C.中断I/O方式下数据传送通过软件完成，DMA方式下数据传送由硬件完成D.中断I/O方式适用于所有外部设备，DMA方式仅适用于快速外部设备9、设系统缓冲区和用户工作区均采用单缓冲，从外设读入1个数据块到系统缓冲区的时间为100，从系统缓冲区读入1个数据块到用户工作区的时间为5，对用户工作区中的1个数据块进行分析的时间为90，进程从外设读入并分析2个数据块的最短时间为：（C）A、195B、290C、300D、39010、设文件F1的当前引用计数值为2，先建立F1的符号链接（软链接）文件F2，再建立F1的索引结点链接（硬链接）文件F3，然后删除F1。