Книга: Real-Time Concepts for Embedded Systems
16.3 Deadlocks
Deadlock is the situation in which multiple concurrent threads of execution in a system are blocked permanently because of resource requirements that can never be satisfied.
A typical real-time system has multiple types of resources and multiple concurrent threads of execution contending for these resources. Each thread of execution can acquire multiple resources of various types throughout its lifetime. Potential for deadlocks exist in a system in which the underlying RTOS permits resource sharing among multiple threads of execution. Deadlock occurs when the following four conditions are present:
Mutual exclusion - A resource can be accessed by only one task at a time, i.e., exclusive access mode.
No preemption - A non-preemptible resource cannot be forcibly removed from its holding task. A resource becomes available only when its holder voluntarily relinquishes claim to the resource.
Hold and wait - A task holds already-acquired resources, while waiting for additional resources to become available.
Circular wait - A circular chain of two or more tasks exists, in which each task holds one or more resources being requested by a task next in the chain.
Given that each resource is nonpreemptible and supports only exclusive access mode, Figure 16.1 depicts a deadlock situation between two tasks.
Figure 16.1: Deadlock situation between two tasks.
Figure 16.1 is a resource graph. An arrow labeled holds going from a resource to a task indicates that the task currently holds (or owns) the resource. An arrow labeled wants going from a task to a resource indicates that the task currently needs this resource to resume execution.
In this example, task #1 wants the scanner while holding the printer. Task #1 cannot proceed until both the printer and the scanner are in its possession. Task #2 wants the printer while holding the scanner. Task #2 cannot continue until it has the printer and the scanner. Because neither task #1 nor task #2 is willing to give up what it already has, the two tasks are now deadlocked because neither can continue execution.
Deadlocks can involve more than two tasks.
As shown in Figure 16.2, task T1 currently holds resource R1 (a printer), and T1 wants resource R2 (a scanner). Task T2 holds resource R2 and wants resource R3 (a memory buffer). Similarly, task T3 holds resource R3 and wants resource R1. It is easy to see the cycle, i.e., the circular-wait condition in this system. Tasks T1, T2, and T3, and resources R1, R2, and R3 comprise the deadlocked set. Note that in the system in Figure 16.2, one instance per resource type exists, i.e., there is one instance of R1, one instance of R2, and one instance of R3. A later section, 'Multi-Instance Resource Deadlock Detection' on page 266, discusses deadlock situations that involve multiple instances of a resource type.
Figure 16.2: Deadlock situation among three tasks.
In this example, each task requires a single instance of a single resource type at any given time. Many situations exist in which a task might require multiple instances of multiple types of resources. The formation of deadlocks depends on how a task requests resources (formally known as a resource request model). The deadlock detection algorithms are constructed according to the resource request models.
Оглавление книги
