Main Content

CERT C: Rule POS51-C

Avoid deadlock with POSIX threads by locking in predefined order

expand all in page

Description

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

Rule Definition

Avoid deadlock with POSIX threads by locking in predefined order.1

Polyspace Implementation

The rule checker checks for Deadlock.

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

Issue

Deadlock 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. Both lock and unlock functions must have the form void func(void).

To find this defect, you must specify the multitasking options before analysis. To specify these options, on the Configuration pane, select Multitasking.

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:

Example - 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(); //Noncompliant
    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:

OptionSpecification
Configure multitasking manually
Entry points

task1

task2

Critical section detailsStarting routineEnding routine
begin_critical_section_1end_critical_section_1
begin_critical_section_2end_critical_section_2

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

  1. task1 calls begin_critical_section_1.

  2. task2 calls begin_critical_section_2.

  3. 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.

  4. 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();
 } 
}
Example - 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(); //Noncompliant
    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:

OptionSpecification
Configure multitasking manually
Entry points

task1

task2

task3

Critical section detailsStarting routineEnding routine
lock1unlock1
lock2unlock2
lock3unlock3

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

  1. task1 calls lock1.

  2. task2 calls lock2.

  3. task3 calls lock3.

  4. task1 reaches the instruction lock2();. Since task2 has already called lock2, task1 waits for call to unlock2.

  5. task2 reaches the instruction lock3();. Since task3 has already called lock3, task2 waits for call to unlock3.

  6. 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:

  1. lock1

  2. lock2

  3. 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();
 } 
}

Check Information

Group: Rule 50. POSIX (POS)

Version History

Introduced in R2019a

See Also

Topics

External Websites

1 This software has been created by MathWorks incorporating portions of: the “SEI CERT-C Website,” © 2017 Carnegie Mellon University, the SEI CERT-C++ Web site © 2017 Carnegie Mellon University, ”SEI CERT C Coding Standard – Rules for Developing safe, Reliable and Secure systems – 2016 Edition,” © 2016 Carnegie Mellon University, and “SEI CERT C++ Coding Standard – Rules for Developing safe, Reliable and Secure systems in C++ – 2016 Edition” © 2016 Carnegie Mellon University, with special permission from its Software Engineering Institute.

ANY MATERIAL OF CARNEGIE MELLON UNIVERSITY AND/OR ITS SOFTWARE ENGINEERING INSTITUTE CONTAINED HEREIN IS FURNISHED ON AN "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.

This software and associated documentation has not been reviewed nor is it endorsed by Carnegie Mellon University or its Software Engineering Institute.