Deadlock (computer science)

Deadlock or jamming referred to in the computer science a state in which a cyclic waiting situation between several processes occurs, each process involved the release of resources waiting that has been exclusively assigned another party process. Another form of blocking of processes is the livelock .

The state of a deadlock can be defined as a set of processes in which a deadlock is, provided that each of these processes is waiting for an event that only another process from this set can cause.

Four processes (blue lines) compete for one resource (gray circle). The right-before-left rule applies. A deadlock occurs when all four processes occupy or block the resource at the same time (black lines). The deadlock can be resolved by breaking the symmetry.

General

For example, the screen may have been assigned to a process p ₁ . At the same time, however , p ₁ needs the printer. On the other hand, the printer is assigned to process p ₂ , which in turn requests the screen. An example of a deadlock from real life is a street crossing where cars have come from all four sides and are now ( assuming the rule right before left ) waiting for the car waiting on the right to drive first. Another example is the philosopher problem .

According to Coffman et al. the following four conditions are sufficient for a deadlock; if these are present, there is also a deadlock:

The resources are only released by the processes ( because resource access of a process cannot be interrupted. No preemption ).
The processes request resources, but at the same time retain access to others ( hold and wait ).
Access to the resources is exclusive ( mutual exclusion ).
At least two processes have a circular dependency with regard to the resources ( circular wait ).

Deadlocks can occur in systems that are able to run several processes in parallel (multitask systems) and for which the order of resource allocation is not defined. If you want to go beyond the ostrich algorithm and allow the possibility of a deadlock, you have to prevent or avoid it, if necessary eliminate it.

The definitions of deadlock prevention and deadlock avoidance are often found interchanged in the literature.

Verklemmungsprävention (deadlock prevention)

Basically, if there is only one process in a closed system, it can never get stuck. Likewise, a process that only requires one piece of equipment cannot jam.

If deadlocks occur, they can usually not be eliminated normally. Instead, resource management should try to apply preventive measures in order to achieve suitable sequencing . One speaks of a prevention if at least one of the four conditions are not met for a jam.

Perform preemption: Resources are withdrawn from a process in order to reallocate them to another.
Prevent hold and wait: At the beginning of each process, it indicates which resources it needs. If all required resources are free at the same time, they are assigned a process at once.
Eliminate mutual exclusion: To make the required resources available for all processes by canceling the exclusive access. Alternatively spooling (example: printer) or virtualization of resources (example: CPU).
Exclude circular wait: Equipment is arranged linearly and allocated in a fixed order.

Deadlock (deadlock avoidance)

In addition, you can try to avoid deadlock (sometimes also called deadlock prevention ). This means that deadlocks are theoretically possible; however, the system tries to monitor the processes so that they do not get stuck. This procedure is based on the safe state method . A state is considered safe if there is at least one scheduling order in which all existing processes can be terminated, even if they should still make their maximum resource requirements.

In a prevention must all possible following operations be known. The banking algorithm is often used here, in which the resources are only allocated to a process if they have been returned in full. For example, a process π _{1 has} a total of five resources and it requires three more resources to be fully executed. The operating system provides three additional resources. A process π ₂ has two resources and requires eight resources. As a result, process π ₁ receives the three resources. It thus has all the resources to be completely processed, whereupon the operating system has eight resources freely available after processing, which can now be allocated to process π ₂ . Avoidance is often very difficult because it is difficult to estimate which process will release enough resources.

Two simple methods of avoidance are wait / die and wound / wait . Here, cyclical dependencies are avoided in that there are fixed rules as to who is allowed to keep a remedy and which it can be withdrawn. This procedure is mainly used in database systems with regard to write and read locks, which is why the term transactions and not processes will be used in the following:
With both procedures, each transaction is assigned a time stamp when it is instantiated.

wait / die :

If a transaction requests a lock that is held by a younger one, the older one waits until the lock is released by the younger one.
If a transaction requests a lock that is held by an older one, it aborts itself (more precisely: it restarts, but it retains its old time stamp in order to appear "older" and increase its chances, this time completely to go through)

wound / wait :

If a transaction requests a lock that is held by a younger one, the younger one is aborted (more precisely: restarted) and the older one is assigned the lock.
If a transaction requests a lock that is held by an older one, it waits until the older one releases the lock.

The terminology should be understood as follows. wait / die or wound / wait indicate how the requesting transaction will behave if a lock conflict occurs. The first term indicates what happens if the requesting transaction is the older, the second term indicates what happens if the requesting transaction is the more recent. "Wait" means: the requesting transaction is waiting for the lock to be released; English the dies' means the requesting transaction is reset; "Wound" means the requesting transaction "wounds" the lock owner; H. the requesting transaction tries to reset the lock owner. In order to avoid unnecessary resets, resetting can be dispensed with in the case of "wound" if the lock owner is already in the release. In this case, contrary to the rule, the requesting transaction waits because it is ensured that the lock owner is not involved in a deadlock.

Verklemmungsbeseitigung (recovery from deadlocks)

Elimination through process termination: The simplest way of eliminating deadlocks is to specifically abort processes. If possible, a process should be selected that reliably resolves the deadlock. Otherwise the procedure must be repeated until all conflicts have been resolved. The mostly unavoidable loss of data can be minimized with a skilful process selection, which makes it very difficult to automate this process.
Elimination through preemption: A more elegant solution to deadlocks is to suspend a process that is occupying a resource and only resume execution at a later point in time. In the meantime, the blocked processes can complete their task, which clears the deadlock. For this procedure, however, it is crucial to know exactly what the process to be interrupted is doing in order to rule out errors. In most cases, it is practically impossible to automatically eliminate deadlocks using this method.
Elimination through rollback: Another option is to roll back a selected process that can be blamed for the deadlock. For this purpose, backups are created for each process at predefined time intervals, to which you can jump back if necessary. If a deadlock occurs, a process is selected, reset to the last saved state and suspended in order to clear the deadlock. Not all types of processes can be reset easily this way. For example, a hard disk write process is more suitable than a CD / DVD burn process in most cases . The interrupted process will only continue its execution when the required resources are available, which can starve it in unfavorable cases .

Livelock

Another form of blocking of processes which, like a deadlock, prevents the further execution of the program is the livelock. It denotes a form of blocking two or more processes that, unlike deadlock, do not remain in one state, but constantly switch between several states from which they can no longer escape. Each individual process does not remain in the waiting state forever, but is still active, but cannot complete its task either.

One can clearly imagine two people at the Livelock who come towards each other in a corridor and continually try to avoid each other in the same (absolute) direction, thereby always blocking each other. In the deadlock - sticking to this illustration - the two people would only face each other and each wait for the other to move aside, which does not happen.

Rail operations

In rail operations , deadlock describes an operating situation in which two or more trains block each other so that the safety technology no longer allows regular train journeys . There is an analogy here with IT: Each train blocks a section of the train heading and waits to be able to enter the next section. A deadlock can be recognized in algorithms for controlling interlockings by the fact that a circular reference occurs when a route is set.

Web links

Wiktionary: Deadlock - explanations of meanings, word origins, synonyms, translations

Deadlock detection

Individual evidence

^ Andrew S. Tanenbaum : Modern Operating Systems . Prentice Hall International, 2008, ISBN 978-0-13-813459-4 .
^ EC Coffman, Michael John Elphick , A. Shoshani: System Deadlocks . In: Computing Surveys . tape 3 , no. 2 , 1971, p. 67–78 ( cs.umass.edu [PDF; 896 kB ]).
↑ Andrew S. Tanenbaum: Modern Operating Systems . Pearson Studium, 2009, ISBN 3-8273-7342-5 , pp. 539 ( limited preview in Google Book search).
↑ Section block on a single-track route. Stellwerke.de; Retrieved July 25, 2013.
↑ Jacob carbon Russ: investigation of methods to avoid deadlocks in synchronous railway simulation programs . Diploma thesis, Institute for Traffic Management, Braunschweig / Wolfenbüttel University of Applied Sciences, 2007.
^ Yong Cui: Simulation-Based Hybrid Model for a Partially-Automatic Dispatching of Railway Operation . Dissertation, University of Stuttgart, 2009, p. 55ff.

[1] Andrew S. Tanenbaum : Modern Operating Systems . Prentice Hall International, 2008, ISBN 978-0-13-813459-4 .

[2] EC Coffman, Michael John Elphick , A. Shoshani: System Deadlocks . In: Computing Surveys . tape 3 , no. 2 , 1971, p. 67–78 ( cs.umass.edu [PDF; 896 kB ]).

[3] Andrew S. Tanenbaum: Modern Operating Systems . Pearson Studium, 2009, ISBN 3-8273-7342-5 , pp. 539 ( limited preview in Google Book search).

[4] Section block on a single-track route. Stellwerke.de; Retrieved July 25, 2013.

[5] Jacob carbon Russ: investigation of methods to avoid deadlocks in synchronous railway simulation programs . Diploma thesis, Institute for Traffic Management, Braunschweig / Wolfenbüttel University of Applied Sciences, 2007.

[cui-6] Yong Cui: Simulation-Based Hybrid Model for a Partially-Automatic Dispatching of Railway Operation . Dissertation, University of Stuttgart, 2009, p. 55ff.