Deadlock

Вызов последовательности для блокировки функций заставляет две задачи блокировать друг друга

Описание

Этот дефект возникает, когда несколько задач застревают в их критических разделах (CS), потому что:

Каждая CS ожидает окончания работы другой CS.
Критические участки (CS) образуют замкнутый цикл. Для примера:
- CS # 1 ожидает окончания CS # 2, а CS # 2 - окончания CS # 1.
- CS # 1 ожидает окончания CS # 2, CS # 2 ожидает окончания CS # 3, и CS # 3 ожидает окончания CS # 1.

Polyspace^® ожидает, что критические разделы кода будут соответствовать определенному формату. Критический раздел находится между вызовом функции блокировки и вызовом функции разблокировки. Когда задача my_task вызывает функцию блокировки my_lock, другие задачи, вызывающие my_lock необходимо подождать до my_task вызывает соответствующую функцию разблокировки. Функции блокировки и разблокировки должны иметь форму void func(void).

Чтобы найти этот дефект, перед анализом необходимо задать опции многозадачности. Чтобы задать эти опции, на панели Configuration выберите Multitasking.

Риск

Каждая задача ожидает завершения критического раздела в другой задаче и не может продолжить. Программа может замерзнуть на неопределенный срок.

Зафиксировать

Исправление зависит от первопричины дефекта. Можно попытаться разбить циклический порядок между задачами одним из следующих способов:

Запишите все критические разделы, вовлеченные в тупик, в определенной последовательности. Всякий раз, когда вы вызываете функции блокировки критических разделов в задаче, уважайте порядок в этой последовательности. См. пример ниже.
Если одна из критических секций, участвующих в взаимоблокировке, происходит в прерывании, попробуйте отключить все прерывания во время критических секций во всех задачах. См. Disabling all interrupts (-routine-disable-interrupts -routine-enable-interrupts).

Просмотр этого дефекта является возможностью проверить, все ли операции в вашем критическом разделе действительно предназначены для выполнения в качестве атомарного блока. Рекомендуется держать критические сечения на минимальном уровне.

Если вы не хотите устранять проблему, добавьте комментарии к своему результату или коду, чтобы избежать другой проверки. Смотрите Адрес Результаты Polyspace через исправления ошибок или обоснования.

Примеры

расширить все

Тупик с двумя задачами



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

В этом примере, чтобы эмулировать поведение в многозадачном режиме, вы должны задать следующие опции:

Опция	Спецификация
`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`

Deadlock происходит, потому что инструкции могут выполняться в следующей последовательности:

task1 вызывает begin_critical_section_1.
task2 вызывает begin_critical_section_2.
task1 достигает команды begin_critical_section_2();. Начиная с task2 уже звонил begin_critical_section_2, task1 ждет task2 для вызова end_critical_section_2.
task2 достигает команды begin_critical_section_1();. Начиная с task1 уже звонил begin_critical_section_1, task2 ждет task1 для вызова end_critical_section_1.

Коррекция - следуйте той же последовательности блокировки в обеих задачах

Одной из возможных коррекций является следование одной и той же последовательности вызовов для блокировки и разблокировки функций в обоих task1 и 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();
 } 
}

Тупик с более чем двумя задачами



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

В этом примере, чтобы эмулировать поведение в многозадачном режиме, вы должны задать следующие опции:

Опция	Спецификация
Configure multitasking manually
Entry points	`task1` `task2` `task3`
Critical section details	Starting routine	Ending routine
	`lock1`	`unlock1`
	`lock2`	`unlock2`
	`lock3`	`unlock3`

Deadlock происходит, потому что инструкции могут выполняться в следующей последовательности:

task1 вызывает lock1.
task2 вызывает lock2.
task3 вызывает lock3.
task1 достигает команды lock2();. Начиная с task2 уже звонил lock2, task1 ждет вызова, чтобы unlock2.
task2 достигает команды lock3();. Начиная с task3 уже звонил lock3, task2 ждет вызова, чтобы unlock3.
task3 достигает команды lock1();. Начиная с task1 уже звонил lock1, task3 ждет вызова, чтобы unlock1.

Коррекция - разрыв циклического порядка

Чтобы разбить циклический порядок между критическими разделами, обратите внимание на каждую функцию блокировки в вашем коде в определенной последовательности, например:

lock1
lock2
lock3

Если вы используете в задаче несколько функций блокировки, используйте их в том порядке, в котором они появляются в последовательности. Для примера можно использовать lock1 далее следуют lock2 но не lock2 далее следуют 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();
 } 
}

Информация о результатах

Группа: Параллелизм

Язык: C | C++

По умолчанию: On

Синтаксис командной строки: DEADLOCK

Влияние: Высокий

ИДЕНТИФИКАТОР CWE: 833

См. также

Темы

Введенный в R2014b

Документация