Deadlock

Call sequence to lock functions cause two tasks to block each other

Description

This checker is deactivated in a default Polyspace^® as You Code analysis. See Checkers Deactivated in Polyspace as You Code Analysis (Polyspace Access).

This defect occurs when multiple tasks are stuck in their critical sections (CS) because:

Each CS waits for another CS to end.
The critical sections (CS) form a closed cycle. For example:
- CS #1 waits for CS #2 to end, and CS #2 waits for CS #1 to end.
- CS #1 waits for CS #2 to end, CS #2 waits for CS #3 to end and CS #3 waits for CS #1 to end.

Polyspace expects critical sections of code to follow a specific format. A critical section lies between a call to a lock function and a call to an unlock function. When a task my_task calls a lock function my_lock, other tasks calling my_lock must wait until my_task calls the corresponding unlock function.

To find this defect, specify your lock and unlock functions using one of these methods:

Invoke one of the concurrency primitives that Polyspace Bug Finder™ can detect automatically. See Auto-Detection of Thread Creation and Critical Section in Polyspace.
Specify lock and unlock functions explicitly before analysis as configuration options. Polyspace requires that both lock and unlock functions must have the form void func(void). See Critical section details (-critical-section-begin -critical-section-end).

Risk

Each task waits for a critical section in another task to end and is unable to proceed. The program can freeze indefinitely.

Fix

The fix depends on the root cause of the defect. You can try to break the cyclic order between the tasks in one of these ways:

Write down all critical sections involved in the deadlock in a certain sequence. Whenever you call the lock functions of the critical sections within a task, respect the order in that sequence. See an example below.
If one of the critical sections involved in a deadlock occurs in an interrupt, try to disable all interrupts during critical sections in all tasks. See Disabling all interrupts (-routine-disable-interrupts -routine-enable-interrupts).

Reviewing this defect is an opportunity to check if all operations in your critical section are really meant to be executed as an atomic block. It is a good practice to keep critical sections at a bare minimum.

If you do not want to fix the issue, add comments to your result or code to avoid another review. See:

Address Results in Polyspace User Interface Through Bug Fixes or Justifications if you review results in the Polyspace user interface.
Address Results in Polyspace Access Through Bug Fixes or Justifications (Polyspace Access) if you review results in a web browser.
Annotate Code and Hide Known or Acceptable Results if you review results in an IDE.

Extend Checker

You might be using multithreading functions that are not supported by Polyspace. Extend this checker by mapping the functions of your multithreading functions to their known POSIX^® equivalent. See Extend Concurrency Defect Checkers to Unsupported Multithreading Environments.

Examples

expand all

Deadlock with Two Tasks



void task1(void);
void task2(void);

int var;
void perform_task_cycle(void) {
 var++;
}

void begin_critical_section_1(void);
void end_critical_section_1(void);

void begin_critical_section_2(void);
void end_critical_section_2(void);

void task1() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

void task2() {
 while(1) {
    begin_critical_section_2();
    begin_critical_section_1();
    perform_task_cycle();
    end_critical_section_1();
    end_critical_section_2();
 } 
}

In this example, to emulate multitasking behavior, you must specify the following options:

Option	Specification
`Configure multitasking manually`
`Tasks (-entry-points)`	`task1` `task2`
`Critical section details (-critical-section-begin -critical-section-end)`	Starting routine	Ending routine
	`begin_critical_section_1`	`end_critical_section_1`
	`begin_critical_section_2`	`end_critical_section_2`

A Deadlock occurs because the instructions can execute in the following sequence:

task1 calls begin_critical_section_1.
task2 calls begin_critical_section_2.
task1 reaches the instruction begin_critical_section_2();. Since task2 has already called begin_critical_section_2, task1 waits for task2 to call end_critical_section_2.
task2 reaches the instruction begin_critical_section_1();. Since task1 has already called begin_critical_section_1, task2 waits for task1 to call end_critical_section_1.

Correction-Follow Same Locking Sequence in Both Tasks

One possible correction is to follow the same sequence of calls to lock and unlock functions in both task1 and task2.



void task1(void);
void task2(void);
void perform_task_cycle(void);

void begin_critical_section_1(void);
void end_critical_section_1(void);

void begin_critical_section_2(void);
void end_critical_section_2(void);

void task1() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

void task2() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

Deadlock with More Than Two Tasks



int var;
void performTaskCycle() {
 var++;
}

void lock1(void);
void lock2(void);
void lock3(void);


void unlock1(void);
void unlock2(void);
void unlock3(void);

void task1() {
 while(1) {
    lock1();
    lock2();
    performTaskCycle();
    unlock2();
    unlock1();
 } 
}

void task2() {
 while(1) {
    lock2();
    lock3();
    performTaskCycle();
    unlock3();
    unlock2();
 } 
}

void task3() {
 while(1) {
    lock3();
    lock1();
    performTaskCycle();
    unlock1();
    unlock3();
 } 
}

In this example, to emulate multitasking behavior, you must specify the following options:

Option	Specification
Configure multitasking manually
Entry points	`task1` `task2` `task3`
Critical section details	Starting routine	Ending routine
	`lock1`	`unlock1`
	`lock2`	`unlock2`
	`lock3`	`unlock3`

A Deadlock occurs because the instructions can execute in the following sequence:

task1 calls lock1.
task2 calls lock2.
task3 calls lock3.
task1 reaches the instruction lock2();. Since task2 has already called lock2, task1 waits for call to unlock2.
task2 reaches the instruction lock3();. Since task3 has already called lock3, task2 waits for call to unlock3.
task3 reaches the instruction lock1();. Since task1 has already called lock1, task3 waits for call to unlock1.

Correction — Break Cyclic Order

To break the cyclic order between critical sections, note every lock function in your code in a certain sequence, for example:

lock1
lock2
lock3

If you use more than one lock function in a task, use them in the order in which they appear in the sequence. For example, you can use lock1 followed by lock2 but not lock2 followed by lock1.



int var;
void performTaskCycle() {
 var++;
}

void lock1(void);
void lock2(void);
void lock3(void);

void unlock1(void);
void unlock2(void);
void unlock3(void);

void task1() {
 while(1) {
    lock1();
    lock2();
    performTaskCycle();
    unlock2();
    unlock1();
 } 
}

void task2() {
 while(1) {
    lock2();
    lock3();
    performTaskCycle();
    unlock3();
    unlock2();
 } 
}

void task3() {
 while(1) {
    lock1();
    lock3();
    performTaskCycle();
    unlock3();
    unlock1();
 } 
}

Result Information

Group: Concurrency

Language: C | C++

Default: On

Command-Line Syntax: DEADLOCK

Impact: High

Version History

Introduced in R2014b