Real-Time Concepts for Embedded Systems

N3

…

Nk

where N_i is the number of units of resource type R_i for all i where {1 ? i ? k }.

A = Available System Resources Table

A1

A2

A3

…

Ak

where A_i the number of units remaining for resource type R_i available for allocation.

C = Tasks Resources Assigned Table	C11	C12	C13	…	C1k
	C21	C22		…	C2k
	…			…
Cm1			…	Cmk
D = Tasks Resources Demand Table	D11	D12	D13	…	D1k
	D21	D22		…	D2k
	…			…
Dm1			…	Dmk

For example in table C, there are C₁₁ units of resource R1, C₁₂ units of resource R2, and so on, which are allocated to task T1. Similarly, there are C₂₁ units of resource R1, C₂₂ units of resource R2, and so on, which are allocated to task T2. For example in table D, task T1 demands additional D₁₁ units of resource R1, additional D₁₂ units of resource R2, and so on, in order to complete execution.

The deadlock detection algorithm is as follows:

1. Find a row i in table D, where D_ij ‹ A_j for all 1 ? j ? k. If no such row exists, the system is deadlocked, and the algorithm terminates.

2. Mark the row i as complete and assign A_j = A_j + D_ij for all 1 ? j ? k.

3. If an incomplete row is present, return to step 1. Otherwise, no deadlock is in the system, and the algorithm terminates.

Step 1 of the algorithm looks for a task whose resource requirements can be satisfied. If such a task exists, the task can run to completion. Resources from the completed task are freed back into the resource pool, which step 2 does. The newly available resources can be used to meet the requirements of other tasks, which allow them to resume execution and run to completion.

When the algorithm terminates, the system is deadlocked if table T has incomplete rows. The incomplete