MISRA C:2023 Dir 5.2

There shall be no deadlocks between threads

Since R2024b

Description

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

Directive Definition

There shall be no deadlocks between threads¹ .

Rationale

A deadlock can occur when the threads sharing synchronization resources create a circular chain, with each thread waiting for another thread. Consider this code:

mtx_t mtx1, mtx2;

void worker1() { /*In thread T1*/
	mtx_lock(&mtx1);
	//...
	mtx_lock(&mtx2); // potential deadlock

}

void worker2() { /*In thread T2*/
	mtx_lock(&mtx2);
	//...
	mtx_lock(&mtx1); // potential deadlock
}

The functions worker1() and worker2() run concurrently in two threads. The function worker1() locks mtx1 and then tries to lock mtx2, while worker2() locks mtx2 and then tries to lock mtx1. If both threads lock their first mutex before either tries to lock their second, then each thread remains waiting for the other to release its mutex, leading to a deadlock.

To avoid deadlocks, use mutexes in a fixed global noncyclic order.

Polyspace Implementation

Polyspace reports violations of this directive when multiple threads wait on their mutex objects cyclically:

• Each thread waits for another thread to unlock a mutex.

• The threads form a closed cycle.

Polyspace recognizes the threads and mutex objects from the C11 library. See Auto-Detection of Thread Creation and Critical Section in Polyspace. You can also manually specify your threads by using the option Tasks (-entry-points), and your mutex objects by using Critical section details (-critical-section-begin -critical-section-end).

Troubleshooting

If you expect a rule violation but do not see it, refer to Diagnose Why Coding Standard Violations Do Not Appear as Expected.

Examples

Deadlock with Two Tasks

In this example, the function worker1() and worker2() run concurrently in threads t1 and t2. A deadlock occurs because t1 locks the mutex mutex1 and then, before unlocking mutex1, attempts to lock mutex2, which is already locked by another thread. Polyspace reports a violation.

#include <stdio.h>
#include <threads.h>
void doWork(void);
mtx_t mutex1, mutex2;

// Worker function 1 locks mutex1 then mutex2
int worker1(void* arg) {
    mtx_lock(&mutex1); // Locks mutex1
     
    doWork();
    mtx_lock(&mutex2); // Noncompliant - attempts to lock mutex2, but may be locked by worker2()

    mtx_unlock(&mutex2);
    mtx_unlock(&mutex1);
    return 0;
}

// Worker function 2 locks mutex2 then mutex1
int worker2(void* arg) {
    mtx_lock(&mutex2); // Locks mutex2
 
    doWork();
    mtx_lock(&mutex1); // Attempts to lock mutex1, but may be locked by worker1()
     
    mtx_unlock(&mutex1);
    mtx_unlock(&mutex2);
    return 0;
}

int main() {
    thrd_t t1, t2;

    // Initialize mutexes
    mtx_init(&mutex1, mtx_plain);
    mtx_init(&mutex2, mtx_plain);

    // Create worker threads
    if (thrd_create(&t1, worker1, NULL) != thrd_success) {
        printf("Failed to create thread 1\n");
        return 1;
    }
    if (thrd_create(&t2, worker2, NULL) != thrd_success) {
        printf("Failed to create thread 2\n");
        return 1;
    }

    // Wait for threads to finish (they won't, due to deadlock)
    thrd_join(t1, NULL);
    thrd_join(t2, NULL);

    // Clean up
    mtx_destroy(&mutex1);
    mtx_destroy(&mutex2);

    return 0;
}

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

Option	Specification
Configure multitasking manually	On
Tasks (-entry-points)	worker1 worker2

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 t1 and t2.

#include <stdio.h>
#include <threads.h>
void doWork(void);
mtx_t mutex1, mutex2;

// Worker function 1 locks mutex1 then mutex2
int worker1(void* arg) {
    mtx_lock(&mutex1); // Locks mutex1

    doWork();
    mtx_lock(&mutex2); // Compliant

    mtx_unlock(&mutex2);
    mtx_unlock(&mutex1);
    return 0;
}

// Worker function 2 locks mutex1 then mutex2
int worker2(void* arg) {
    mtx_lock(&mutex1); // Locks mutex1

    doWork();
    mtx_lock(&mutex2); 

    mtx_unlock(&mutex1);
    mtx_unlock(&mutex2);
    return 0;
}

int main() {
    thrd_t t1, t2;

    // Initialize mutexes
    mtx_init(&mutex1, mtx_plain);
    mtx_init(&mutex2, mtx_plain);

    // Create worker threads
    if (thrd_create(&t1, worker1, NULL) != thrd_success) {
        printf("Failed to create thread 1\n");
        return 1;
    }
    if (thrd_create(&t2, worker2, NULL) != thrd_success) {
        printf("Failed to create thread 2\n");
        return 1;
    }

    // Wait for threads to finish 
    thrd_join(t1, NULL);
    thrd_join(t2, NULL);

    // Clean up
    mtx_destroy(&mutex1);
    mtx_destroy(&mutex2);

    return 0;
}

Deadlock with More Than Two Tasks

In this example, three threads create a circular dependency chain that results in a deadlock, with each thread waiting for a mutex held by another thread in the cycle.

#include <stdio.h>
#include <threads.h>
#include <stdlib.h>
void doWork(void);
mtx_t mutex1, mutex2, mutex3;

int thread1(void *arg) {
    mtx_lock(&mutex1); // Thread 1 locks mutex1
    doWork();
    mtx_lock(&mutex2); // Noncompliant
    // Critical section (not reached)
    mtx_unlock(&mutex2);
    mtx_unlock(&mutex1);
    return 0;
}

int thread2(void *arg) {
    mtx_lock(&mutex2); // Thread 2 locks mutex2
    doWork();
    mtx_lock(&mutex3); // Waits for Thread 3 to release mutex3
    // Critical section (not reached)
    mtx_unlock(&mutex3);
    mtx_unlock(&mutex2);
    return 0;
}

int thread3(void *arg) {
    mtx_lock(&mutex3); // Thread 3 locks mutex3
    doWork();
    mtx_lock(&mutex1); // Waits for Thread 1 to release mutex1
    // Critical section (not reached)
    mtx_unlock(&mutex1);
    mtx_unlock(&mutex3);
    return 0;
}

int main() {
    thrd_t t1, t2, t3;

    mtx_init(&mutex1, mtx_plain);
    mtx_init(&mutex2, mtx_plain);
    mtx_init(&mutex3, mtx_plain);

    thrd_create(&t1, thread1, NULL);
    thrd_create(&t2, thread2, NULL);
    thrd_create(&t3, thread3, NULL);

    thrd_join(t1, NULL);
    thrd_join(t2, NULL);
    thrd_join(t3, NULL);

    mtx_destroy(&mutex1);
    mtx_destroy(&mutex2);
    mtx_destroy(&mutex3);

    return 0;
}

In this example, to emulate multitasking behavior, specify these options:

Option	Specification
Configure multitasking manually	On
Tasks (-entry-points)	thread1 thread2 thread3

Correction — Use Consistent Global Order to Break Cycle

To break the cyclic order between critical sections, use the same global order (mutex1, mutex2, mutex3) in all the threads.

#include <stdio.h>
#include <threads.h>
#include <stdlib.h>
void doWork(void);
mtx_t mutex1, mutex2, mutex3;

int thread1(void *arg) {
	mtx_lock(&mutex1); // Thread 1 locks mutex1 first
	void doWork(void);
	mtx_lock(&mutex2); // Then locks mutex2
	mtx_lock(&mutex3); // Finally locks mutex3
	// Critical section
	mtx_unlock(&mutex3);
	mtx_unlock(&mutex2);
	mtx_unlock(&mutex1);
	return 0;
}

int thread2(void *arg) {
	mtx_lock(&mutex1); // Thread 2 also starts by locking mutex1 first
	void doWork(void);
	mtx_lock(&mutex2); // Then locks mutex2
	mtx_lock(&mutex3); // Finally locks mutex3
	// Critical section
	mtx_unlock(&mutex3);
	mtx_unlock(&mutex2);
	mtx_unlock(&mutex1);
	return 0;
}

int thread3(void *arg) {
	mtx_lock(&mutex1); // Thread 3 also starts by locking mutex1 first
	void doWork(void);
	mtx_lock(&mutex2); // Then locks mutex2
	mtx_lock(&mutex3); // Finally locks mutex3
	// Critical section
	mtx_unlock(&mutex3);
	mtx_unlock(&mutex2);
	mtx_unlock(&mutex1);
	return 0;
}

int main() {
	thrd_t t1, t2, t3;

	mtx_init(&mutex1, mtx_plain);
	mtx_init(&mutex2, mtx_plain);
	mtx_init(&mutex3, mtx_plain);

	thrd_create(&t1, thread1, NULL);
	thrd_create(&t2, thread2, NULL);
	thrd_create(&t3, thread3, NULL);

	thrd_join(t1, NULL);
	thrd_join(t2, NULL);
	thrd_join(t3, NULL);

	mtx_destroy(&mutex1);
	mtx_destroy(&mutex2);
	mtx_destroy(&mutex3);

	return 0;
}

Check Information

Group: Concurrency Considerations

Category: Required

AGC Category: Required

Version History

Introduced in R2024b