Intel® Advisor User Guide

ID 766448
Date 7/13/2023
Public

A newer version of this document is available. Customers should click here to go to the newest version.

Document Table of Contents

Lock Hierarchy Violation

Occurs when two or more locks are acquired in a different order in two task executions, potentially leading to a deadlock when the program's tasks execute in parallel.

A Lock hierarchy violation problem indicates the following timeline:

Task 1

  1. Acquire lock A.

  2. Acquire lock B.

  3. Release lock B.

  4. Release lock A.

Task 2

  1. Acquire lock B.

  2. Acquire lock A.

  3. Release lock A.

  4. Release lock B.

If these time lines are interleaved when the two tasks execute in parallel, a Deadlock occurs:

  1. Task 1: Acquire lock A.

  2. Task 2: Acquire lock B.

  3. Task 1: Try to acquire lock B; wait until task 2 releases it.

  4. Task 2: Try to acquire lock A; wait until task 1 releases it.

The Dependencies tool reports a Lock hierarchy violation as multiple problems in a problem set. Each problem shows a portion of the Lock hierarchy violation from the perspective of a single thread.

Lock hierarchy violation problems are the most common cause of Deadlock problems, and a report of a Lock hierarchy violation problem indicates a Deadlock problem might occur when the target executes in parallel.

Syntax

Problem type: Lock hierarchy violation

ID

Code Location

Description

1

Allocation site

If present, represents the location and its associated call stack where the synchronization object acquired by a thread (usually the object acquired first) was created.

2

Parallel site

If present, represents the location and associated call stack of the parallel site containing the Lock Hierarchy Violation problem.

3

Lock owned

Represents the location and associated call stack where a task acquired a lock.

4

Lock owned

Represents the location and associated call stack where a task acquired a second lock while the task still held the first lock.

Example

// in task 1

ANNOTATE_LOCK_ACQUIRE(&lahv_lock1);
ANNOTATE_LOCK_ACQUIRE(&lahv_lock2); /* lock hierarchy violation */
ANNOTATE_LOCK_RELEASE(&lahv_lock2);
ANNOTATE_LOCK_RELEASE(&lahv_lock1);

// in task 2

ANNOTATE_LOCK_ACQUIRE(&lahv_lock2);
ANNOTATE_LOCK_ACQUIRE(&lahv_lock1); /* lock hierarchy violation */
ANNOTATE_LOCK_RELEASE(&lahv_lock1);
ANNOTATE_LOCK_RELEASE(&lahv_lock2);

Possible Correction Strategies

Determine if interleaving is possible, or whether some other synchronization exists that might prevent interleaving. If interleaving is possible, consider the following options.

Use a single lock instead of multiple locks:

// in task 1

ANNOTATE_LOCK_ACQUIRE(&lahv_lock1);
a++;
b += a;
ANNOTATE_LOCK_RELEASE(&lahv_lock1);

// in task 2

ANNOTATE_LOCK_ACQUIRE(&lahv_lock2); 
b += x[i];
a -= b;
ANNOTATE_LOCK_RELEASE(&lahv_lock2); 

Try to define a consistent order for your locks, so that any task that acquires the same set of locks, will acquire them in the same order:

// in task 1

ANNOTATE_LOCK_ACQUIRE(&lahv_lock1);
a++;
b += a;
ANNOTATE_LOCK_RELEASE(&lahv_lock1);

// in task 2

ANNOTATE_LOCK_ACQUIRE(&lahv_lock2); 
b += x[i];
a -= b;
ANNOTATE_LOCK_RELEASE(&lahv_lock2);

When a task acquires multiple locks, make sure that it always releases them in the opposite order that it acquired them.