文献翻译格式例子.doc

文献翻译作业下属学院 专 业 班 级 学 号 姓 名 指导教师 骆挺 职称 讲师 -年-月-日DEADLOCKSSilberschatz, A. Galvin, P.B&G. Gagne. Operating System Concepts M. Beijing: Higher Education Press,2004:243-270In a multiprogramming environment, several processes may compete for a finite number of recourses process requests resources; if the resources are not available at the time, the process enters a wait state. Waiting processes may never again change state, because the resources they have requested are held by other waiting processes. This situation is called a deadlock.In a deadlock, processes never finish executing and system are tied up, preventing other jobs from starting. Before we discuss the various methods for dealing with the deadlock problem, we shall describe features that characterize deadlock. 1. The Necessary Conditions of DeadlocksA deadlock situation can raise if the following four conditions hold simultaneously in a system: Mutual exclusion: At least one resource must be held in a non-sharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.Hold and wait: A process must be holding at least one resources and waiting to acquire additional resources that are currently being held by other processes.No preemption: Resources cannot be preempted; that is ,a resource can be released only voluntarily by the process holding it, after that process has completed its task.Circular wait: A setP0,P1,.Pn of waiting processes must exist such that P0 is waiting for a resource that is held by P1,P1 is waiting for a resource that is held by P2,Pn-1 is waiting for a resource that is held by P0.We emphasize that all four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and-wait condition, so the four conditions are not completely independent.2. Methods for Handing DeadlocksPrincipally, we can deal with the deadlock problem in one of three ways:We can use a protocol it prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.We can allow the system to enter a deadlock system, detect it, and recover.We can ignore the problem altogether, and pretend that deadlock never occur in the systems. This solution is used by most operating systems, including UNIX.To ensure that deadlocks never occur, in the systems can use either a deadlock-prevention or deadlock-avoidance scheme. Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made. Possible side effects of preventing deadlocks by this method, however, are low device utilization and reduced system throughput. Deadlock avoidance,on the other hand ,requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime. With this additional knowledge, we can decide for each request whether or not the process should wait. To decide whether the current request can be satisfied or must be delayed, the system must consider the resources currently available, the resources currently allocated to each process, and the future request and releases of each process. For Deadlock avoidance usually used the Bankers Algorithm. The name was chosen because this algorithm could be used in a banking system to ensure that the bank never allocates its availed cash such that it can no longer satisfy the needs of all its customers. When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resource in the system in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state .If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources. Several data structures must be maintained to implement the bankers algorithm. These data structures encode the state of the resource-allocation system.3.Deadlock DetectionIf a system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm, then a deadlock situation may occur. In this environment, the system must provide:An algorithm that examines the state of the system to determine whether a deadlock has occurred.An algorithm to recover form the deadlock.In the following discussion, we elaborate on these two requirements as they pertain to systems with only a single instance of each resource type, as well as to systems with several instance of each resource type. At this point, however, let us note that a detection-and-recovery scheme requires overhead that includes not only the run-time cost of maintaining the necessary information and executing the detection algorithm, but also the potential losses inherent in recovering form a deadlock. 1 Single Instance of Each Resource TypeIf all resources have only a single instance, then we can define a deadlock-detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph. we obtain this graph form the resource-allocation graph by removing the nodes of type resource and collapsing the appropriate.As before, a deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect deadlocks, the system needs to maintain the wait-for graph and periodically to invoke an algorithm that searches for a cycle in the graph.2Several Instance of a Resource TypeThe wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type. The deadlock-detection algorithm that we describe next is applicable to such a system. The algorithm employs several time-varying data strikers are similar to those used in the bankers algorithm:Available: A vector of length m indicates the number of availed resources of each type.Allocation: An nm matrix define the number of resources of each type currently allocated to each process.Request: An nm matrix indicates the current request of each process. If Requesti,j=k, then process Pi is requesting k more instance of resource type Rj.Then relation between two vectors is defining as before. To simplify notation, we shall again treat the rows in the matrices Allocation and Request as vector, and shall refer to them as Allocation1and Requet1, possible allocation sequence for the processes that remain to be completed.3Detection-Algorithm UsageWhen should we invoke the detection algorithm? The answer depends on two factors:How often is a deadlock likely to occur?How many processes will be affected by deadlock when it happens?If deadlocks occur frequently, then the detection algorithm should be invoked frequently. Resource allocated to deadlocked processes will be idle until the deadlock can be broken. In addition, the number of processes involved in the deadlock cycle may grow.4. Recover form DeadlockWhen a detection algorithm determines that a deadlock exists, several alter-native exist. One possibility is to inform the operator that a deadlock has occurred, and to let the operator deal with his deadlock manually. The other possibility is to let the system recover form the deadlock automatically. There are two options for breaking a deadlock. One solution is simply to abort one or more processes to break the circular wait. The second option is to preempt some resources form one or more of the deadlocked processes.A deadlock state occurs when two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes. Principally, there are there methods for dealing with deadlocks: Use some protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.Allow the system to enter deadlock state, detect it, and then recover.Ignore the problem all together, and pretend that deadlocks never occur in the system. This solution is the one is the one used by most operating systems, including UNIX.A deadlock situation may occur if and only if four necessary conditions hold simultaneously in the system: mutual exclusions hold and wait, no preemptions, and circular wait. To prevent deadlocks, we ensure that at least one of the necessary conditions never holds.Another method for avoiding deadlocks that is less stringent than the perception algorithms is to have a priori information on how each process will be utilizing the resources. The bankers algorithms, for example, needs to know the maximum number of each resource class that maybe requested by each process. Using this information, we can define a deadlock-avoidance algorithm. 死锁在多道程序设计环境之下，多个进程可能竞争一定数量的资源。一个进程申请资源，如果资源不可用，那么进程进入等待状态。如果所申请的资源被其他等待进程占有，那么该等待进程有可能无法改变状态，这种情况就被称为死锁。当出现死锁时，进程不能完成执行任务而且系统资源被占用，阻止了其他作业开始执行。在讨论了各种方法处理死锁问题之前，先讨论一下死锁的特征。一、死锁的必要条件如果在一个系统中下面的四个条件同时满足，那么会引起死锁。互斥：至少有一个资源必须处于非共享模式；即一次只有一个进程使用。如果另一个资源申请该资源，那么申请进程必须延迟直到该资源释放为止。占有并等待：一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。非抢占：资源不能被抢占；即，只在进程完成其任务之后，才会释放其资源。循环等待：有一组进程P0,P1Pn，P0等待的资源为P1所占有，P1等待的资源为P2所占有的，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。强调所有四个条件必须同时满足才会出现死锁。循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。二、死锁的处理方法从原理上来说，有三种方式可以处理死锁问题：可使用协议来预防或避免死锁，确保系统绝不会进入死锁状态。可允许系统进入死锁状态，然后检测它，并加以恢复。可忽视这个问题，认为死锁不可能在系统内发生。这种方法为绝大多数操作系统如UNIX所使用。为了确保死锁不会发生，系统可以采取死锁预防或死锁避免方法。死锁预防是一组方法，以确保至少一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。然而，通过这种方法预防死锁的副作用会造成设备使用率和系统吞吐率降低。另一方面，死锁避免要求操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息，可确定：对于一个申请，进程是否应该等待。为了确定当前申请是满足还是延迟，系统必须考虑现有可用资源、已分配给每个进程的资源、每个进程将来申请和释放的资源。对于死锁的避免通常会使用银行家算法。该算法如此命名是因为这个算法可用于银行系统，以确保银行界不会分配其现金一直使它不能满足其所有客户的需求。当新进程进入系统时。它必须说明其可能需要的每种资源类型的实例的最大数量。这一数量不可能超多系统资源的总量。当用户申请一组资源时，系统必须确定这些资源的分配是否仍然会使系统处于安全状态。如果会，就可分配资源；否则，进程必须等待直到某个其他进程释放足够资源为止。三、死锁的检测如果一个系统即不采用死锁预防算法也不采用死锁避免算法，那么可能会出现死锁。在这种环境下，系统应该提供：一个用来检查系统死锁状态从而确定是否出现了死锁的算法。一个用来从死锁状态中恢复的算法。在以下讨论中，将针对每种资源类型只有单个实例和每种资源类型可有多个实例这两种情况分别研究这两个算法。不过，现在需要注意到检测恢复