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

操作系统目录第一章引论赵英1．1操作系统的作用与功能1．2操作系统基础概念1．3操作系统的特性1．4操作系统的性能第二章进程管理陈春超、张莹、王羽中、许静2．1 进程的基本概念2．2 进程的状态及表示2．3 进程通讯基础2．4 经典的进程通讯问题2．5 中断和陷入2．6 进程调度第三章存储管理刘家根、毛敏、李建强、何晓燕、常虹3．1 存储管理和概述3．2 存储管理的早期技术3．3 虚拟存储的的基本思想3．4 页式虚拟组织3．5 页式虚拟组织存储虚拟管理算法3．6 段式虚拟存储器3．7 段式虚拟存储器第四章输入和输出李明、刘娜、杨玲玲4．1 概述4．2 终端4．3 时钟第五章文件系统基础林碧华、王琳、程晓5．1 概述5．2 文件5．3 目录5．4 文件系统实现5．5 文件系统的可靠性及性能1操作系统第一章引论1.1 操作系统的作用和功能首先，让我们对操作系统的作用和功能有一个基本的了解，操作系统作为计算机系统中最重要的系统软件，它的作用可以从两个角度来观察，从用户的角度来说，操作系统是对用户所提供的使用计算机的界面 (Interface)，也就是我们将要讨论的虚拟机的概念。

而从机器的角度来说，操作系统又是对计算机各种系统资源的管理者，负责对各种硬件和软件资源进行分配。

所以，了解一下操作系统的基本作用和功能对于全面理解操作系是十分重要的。

1.1.1 从虚拟机角度观察 OS大家知道，用户直接使用裸机是非常不方便的，例如，用户对裸机进行输入、输出操作时，必须直接对硬件进行繁琐的程序设计，这对多数用户而言是难以胜任的。

而操作系统的主要任务就是将这些复杂的硬件操作与用户隔离开来，代替用户对计算机硬件进行控制，如磁盘读写、中断响应、内存管理等。

从用户的角度来看，他们所直接面对的不再是令人头疼的硬件，而是使用起来方便的多的操作系统了，这就是我们所说的虚拟机 (Virtual Machine)。

1.1.2 从资源管理者角度观察 OS购置计算机的用户最关心的莫过于系统性能与价格是否相称，能否高效地工作，能否给他们带来一定的经济效益，而在这时操作系统的任务就是合理而有效地管理好系统中所有的软、硬件资源，按照需要和一定规则对它们进行分配、控制和回收，以便经济而高效地向用户提供各种性能优良的服务。

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。