Deadlock

Information Systems; Operating Systems; System Analysis

In computing, a deadlock is when two or more processes are running simultaneously and each one needs access to a resource that the other is using. Neither process can terminate until the other one does, so they become stuck, or “locked.” Deadlock can occur in several different areas of computer systems, including operating systems, database transaction processing, and software execution.

In order to understand how a deadlock can arise in a computer system, one must first understand how resources are used in a computer system. One way is to think of the system as a bank account. A database keeps records of debits and credits to the account, and each new transaction is recorded in the database. If money is transferred from one account to another—for example, from a customer's savings account to their checking account—the transfer must be recorded twice, as both a debit from the savings account and a credit to the checking account. Recording the debit and recording the credit are two separate actions. However, in a transactional database, they represent a single transaction, because together they form a logical unit: money cannot be added to one account without being subtracted from another. In this case, the balances of both accounts represent system resources. In order to prevent another process, such as a withdrawal from the checking account, from interrupting the transaction before both the debit and the credit are recorded, the system enforces a rule known as mutual exclusion. This rule means that no two processes can access the same resources at once. Instead, the transfer process places a hold on the account balances until the transaction is complete. This practice is called resource holding, or sometimes “hold and wait.” Only after the transfer is recorded as both a debit and a credit will the transfer process release its hold on the account balance resources. At this point, the withdrawal process is free to access the checking account balance.

Deadlock can be understood as an unintended consequence of resource holding. While resource holding serves a legitimate purpose, inevitably situations arise in which two processes each hold a resource that the other needs in order to finish its work. Process A needs a resource locked by process B in order to finish, while process B needs a resource locked by process A to finish, and neither can relinquish its resources until it is completed. This situation is called a circular wait.

In 1971, computer scientist Edward G. Coffman described the four conditions, now known as the Coffman conditions, necessary for deadlock to occur:

Mutual exclusion, resource holding, and circular wait are described above. Preemption is when one process takes control of a resource being used by another process. Some designated processes have priority over other operations. As such, they can force other processes to stop and let them finish first. Preemption is typically reserved for processes that are fundamental to the operation of the system. If one of the conflicting processes can preempt another, deadlock will not occur. In fact, if any one of the Coffman conditions is not true, deadlock will not occur.

System designers have several options for dealing with deadlocks. One is to simply ignore the issue altogether, though this is not practical in most circumstances. A second approach is to focus on detecting deadlocks and then have a variety of options available for resolving them. A third approach is to try to avoid deadlocks by understanding which system operations tend to cause them. Finally, system designers may adopt a preventive approach in which they make changes to the system architecture specifically to avoid potential deadlocks.

—Scott Zimmer, JD