Term
|
Definition
| An attribute of a system that occurs when a process, or multiple processes can not make progress due to requiring more resources that the system can not grant to it. There are four criteria that must hold for deadlocks to be possible. No preemption, meaning a process can not be interrupted and have a resource taken from it. Hold and Wait, where a process can have resources and still ask for more. Mutual exclusion, where only one process may use a resource at a time. And circular wait, where a cycle exists where processes are waiting on other processes to give up resources that in turn are waiting on this first process to give up a resource it holds. |
|
|
Term
|
Definition
| A process must make a system call to the operating system to obtain a resource. A request is this system call. |
|
|
Term
|
Definition
| A process has a resource and is using it. |
|
|
Term
|
Definition
| A process gives up a resource and lets the operating system know this. |
|
|
Term
| Mutual Exclusion (as a necessary condition for a deadlock) |
|
Definition
| A resource can only be used by one process at a time. |
|
|
Term
| Hold And Wait (as a necessary condition for a deadlock) |
|
Definition
| A process may hold resources and request more. |
|
|
Term
| No Preemption (as a necessary condition for a deadlock) |
|
Definition
| A process can not be interrupted by the operating system and have a resource taken away from it. |
|
|
Term
| Circular Wait (as a necessary condition for a deadlock) |
|
Definition
| A cycle exists for some processes such that these processes are waiting on each other to give up resources that will not be given up until the process gets a resource that it will not get, due to another process holding it. |
|
|
Term
| Resource Allocation Graph |
|
Definition
| A graph that shows which processes hold or request the resources in a system. Can be enhanced by showing claim edges that say a process may request a resource in the future. |
|
|
Term
|
Definition
| An edge in the resource allocation graph that signifies a process wants to have a resource and will not continue until it has this resource. Goes from the process to the resource box. |
|
|
Term
|
Definition
| An edge in the resource allocation graph that signifies a process controls an instance of a resource. Goes from the instance of the resource to the process. |
|
|
Term
|
Definition
| Exactly what it sounds like. Avoids deadlocks from occurring. Usually done by ensuring the system always stays in a safe state, meaning that no process can make a request at this time that would result in deadlock. This differs from an unsafe state by the fact that an unsafe state could go into deadlock if a process makes a request that causes a deadlock. An system in an unsafe state is not necessarily going to go into deadlock, it just means that the potential is there, and the operating system can not do anything to stop it. Deadlock avoidance can be done through banker's algorithm to prevent the system from going into an unsafe state. |
|
|
Term
|
Definition
| Prevents deadlocks from occurring by making them impossible to happen. This is achieved by making one of four important conditions not hold up. This unfortunately generally makes a system much harder to use correctly and some of the conditions can not be broken without significant draw-backs. No mutual exclusion means all resources must be virtualized. No no preemption makes resources like printers unreliable since the print job may be interrupted by some other process and the print out would be useless. No hold and wait would make some programs very limited, such as video-players since no sound could be done by the same process at the same time as video. No circular wait is the only one of these that can be reasonably used. Done by imposing a total ordering on all resources. |
|
|
Term
|
Definition
| The operating system checks to see if a deadlock has occurred. If there is no circular wait then there is no deadlock. If there is a circular wait however, there may not necessarily be a deadlock. For a deadlock to exist the circular wait must not be able to be resolved. An algorithm for this is to remove any processes and the associated edges from the resource allocation graph that have no outstanding requests. Keep doing this until either no processes remain, or no processes can be removed because they still have requests that can not be satisfied. If processes remain then a deadlock exists. |
|
|
Term
|
Definition
| A type of edge in a resource allocation graph that signifies that a process may request a resource in the future. Used in deadlock avoidance. |
|
|
Term
| Safe State (in deadlock avoidance) |
|
Definition
| A state where a deadlock can not occur because any request a process can make, can be currently satisfied. |
|
|
Term
| Unsafe State (in deadlock avoidance) |
|
Definition
| A state where a deadlock may occur that the operating system is powerless to stop because it can not prevent processes from making a request that causes deadlock. |
|
|
Term
|
Definition
| An algorithm that can be run before the operating system grants a resource to a process to ensure the system does not enter an unsafe state after the process gets the resource. Needs to know how many of each type of resource each process could need at most, how many it currently holds, and how many the system currently has available. A resource will only be allocated if the number of resources that the process needs is both less than or equal to the max it will ever need and is less than or equal to the currently available amount. This algorithm goes through and tries to complete processes by giving it all the resources it could need and letting it complete, then reclaiming the resources and doing this to another process until all processes are done. |
|
|
Term
| Deadlock Recovery (from deadlock) |
|
Definition
| Once a deadlock has been detected the most common way to deal with it is to kill a process involved in the deadlock to free up its resources, although this has significant overhead because killing one process involved does not guarantee the deadlock ends, and so the algorithm must be run after each process dies to check if the deadlock is broken. Another approach is to kill all processes involved, but this can cause a great drop in efficiency since a lot of computer time may have been wasted. |
|
|
Term
| Victim Selection (in deadlock recovery) |
|
Definition
| The general idea is to select a process that will be missed the least. The main factors for this are priority, how long the process has been computing and how much longer it needs to complete its task, how many and the kinds of resources it has used, how many resources it needs in order to complete, how many process will need to be killed if this process is killed, and if the process is interactive or batch. |
|
|
