Your browser does not support JavaScript! Skip to main content
Free 30-day trial DO-178C Handbook RapiCoupling Preview DO-178C Multicore Training Multicore Resources
Rapita Systems
 

Industry leading verification tools & services

Rapita Verification Suite (RVS)

  RapiTest - Unit/system testing  RapiCover - Structural coverage analysis  RapiTime - Timing analysis (inc. WCET)  RapiTask - Scheduling visualization  RapiCoverZero - Zero footprint coverage analysis  RapiTimeZero - Zero footprint timing analysis  RapiTaskZero - Zero footprint scheduling analysis  RapiCouplingPreview - DCCC analysis

Multicore Verification

  MACH178  MACH178 Foundations  Multicore Timing Solution  RapiDaemons

Engineering Services

  V&V Services  Data Coupling & Control Coupling  Object code verification  Qualification  Training  Consultancy  Tool Integration  Support

Industries

  Civil Aviation (DO-178C)   Automotive (ISO 26262)   Military & Defense   Space

Other

RTBx Mx-Suite Software licensing Product life cycle policy RVS Assurance issue policy RVS development roadmap

Latest from Rapita HQ

Latest news

SAIF Autonomy to use RVS to verify their groundbreaking AI platform
RVS 3.22 Launched
Hybrid electric pioneers, Ascendance, join Rapita Systems Trailblazer Partnership Program
Magline joins Rapita Trailblazer Partnership Program to support DO-178 Certification
View News

Latest from the Rapita blog

How to certify multicore processors - what is everyone asking?
Data Coupling Basics in DO-178C
Control Coupling Basics in DO-178C
Components in Data Coupling and Control Coupling
View Blog

Latest discovery pages

control_tower DO-278A Guidance: Introduction to RTCA DO-278 approval
Picture of a car ISO 26262
DCCC Image Data Coupling & Control Coupling
Additional Coe verification thumb Verifying additional code for DO-178C
View Discovery pages

Upcoming events

Avionics and Testing Innovations 2025
2025-05-20
DASC 2025
2025-09-14
DO-178C Multicore In-person Training (Fort Worth, TX)
2025-10-01
DO-178C Multicore In-person Training (Toulouse)
2025-11-04
View Events

Technical resources for industry professionals

Latest White papers

Mitigation of interference in multicore processors for A(M)C 20-193
Sysgo WP
Developing DO-178C and ED-12C-certifiable multicore software
DO178C Handbook
Efficient Verification Through the DO-178C Life Cycle
View White papers

Latest Videos

Rapita Systems - Safety Through Quality
Simulation for the Motorola 68020 microprocessor with Sim68020
AI-driven Requirements Traceability for Faster Testing and Certification
Multicore software verification with RVS 3.22
View Videos

Latest Case studies

GMV case study front cover
GMV verify ISO26262 automotive software with RVS
Kappa: Verifying Airborne Video Systems for Air-to-Air Refueling using RVS
Supporting DanLaw with unit testing and code coverage analysis for automotive software
View Case studies

Other Resources

 Webinars

 Brochures

 Product briefs

 Technical notes

 Research projects

 Multicore resources

Discover Rapita

Who we are

The company menu

  • About us
  • Customers
  • Distributors
  • Locations
  • Partners
  • Research projects
  • Contact us

US office

+1 248-957-9801
info@rapitasystems.com
Rapita Systems, Inc.
41131 Vincenti Ct.
Novi
MI 48375
USA

UK office

+44 (0)1904 413945
info@rapitasystems.com
Rapita Systems Ltd.
Atlas House
Osbaldwick Link Road
York, YO10 3JB
UK

Spain office

+34 93 351 02 05
info@rapitasystems.com
Rapita Systems S.L.
Parc UPC, Edificio K2M
c/ Jordi Girona, 1-3
Barcelona 08034
Spain

Working at Rapita

Careers

Careers menu

  • Current opportunities & application process
  • Working at Rapita
Back to Top Contact Us

How to trace the source of deadlocks

Breadcrumb

  1. Home
2014-08-28

In this article I explain how you can use the principles of tracing tools to find the sequence of events that lead to a deadlock. A deadlock is a cyclic dependency, for example where action A cannot continue because it is waiting for a resource to be unlocked by action B, however action B is waiting on A before continuing.

Deadlocks are one of the many banes of multithreaded development for dynamically scheduled systems. Even though the locations of the deadlock itself are easy enough to find, establishing how we got to that point is often a harder task.

Access to resources is managed by access control locks, such as semaphores or mutexes. In figure 1 (below) this is represented by a chain of tasks claiming locks and locks claimed by tasks. Task and lock can only be in one of three dependency states:

  • Task is waiting to claim a lock (task depends on lock)
  • Lock is claimed by a task (lock depends on task)
  • Task is not waiting and lock is not claimed (no dependencies)
A chain of tasks claiming locks and locks claimed by tasks

Figure 1: A chain of tasks claiming locks and locks claimed by tasks

Knowing the state of each task and lock combination in the system is enough to confirm a deadlock and show the sequence of locks that lead up to this.

Note that, when dealing with binary semaphores and mutexes, these dependency relationships are a many-to-one relationship. This makes the state-machine of the relationships deterministic. So, at any point in a system, taking a snapshot of this state machine leaves us with the job of traversing this state machine to establish if there are any loops. Such a loop indicates a cyclic dependency and therefore a deadlock.

A cyclic dependency

Figure 2: A cyclic dependency

Implementing tracing functions

The first task in establishing a deadlock is to be able to record the state of the system. We can do this by wrapping any instance of lock_claim and lock_release functions with wrappers. The wrappers store key trace data at several key stages for both an attempt to lock and release. This data includes the state of the last lock attempt, the task ID and the lock ID

  • Prior to a lock attempt as WAITING
  • After the lock attempt, logging the outcome as either CLAIMED or RELEASED

One implementation option is to maintain the state machine of dependencies in memory. However, this can be costly in terms of time for something that should ideally operate at high-speed. Also, only recording the last dependency link for each object can mean that the history of execution can be lost.

In this situation, a better option could be to produce a trace. Every semaphore operation is logged so all the state machine history is preserved. A deadlock can be detected by using the trace to reconstruct the state machine of the resource locks and to detect the cyclic dependency indicating the deadlock.

Although we haven't considered the case of timeouts here, this could be handled by timestamping the trace entries. Without special handling, a deadlock that occurs due to a timed lock request (i.e. one which will time out) will still be detected. This is not necessarily a problem, even though this may be considered a false-positive, as requests that are timing out due to deadlocks in the system are not typically thought of as healthy.

There are many ways to implement the trace recording and collection, for example: logging to a memory buffer, writing to an I/O port or using a tracing debugger.

It's worth noting at this point that RapiTask, provides a framework for this type of instrumentation and data collection, which can make it easier to collect the information necessary to perform this type of analysis.

DO-178C webinars

DO178C webinars

White papers

Mitigation of interference in multicore processors for A(M)C 20-193
Sysgo WP Developing DO-178C and ED-12C-certifiable multicore software
DO178C Handbook Efficient Verification Through the DO-178C Life Cycle
A Commercial Solution for Safety-Critical Multicore Timing Analysis

Related blog posts

Software verification on the Solar Orbiter

.
2021-03-01

Out of the box RVS integration for DDC-I's Deos RTOS

.
2020-02-23

Lightweight instrumentation with RapiTask

.
2018-06-05

What's next for Ada?

.
2014-07-04

Pagination

  • Current page 1
  • Page 2
  • Next page Next ›
  • Last page Last »
  • Solutions
    • Rapita Verification Suite
    • RapiTest
    • RapiCover
    • RapiTime
    • RapiTask
    • MACH178

    • Verification and Validation Services
    • Qualification
    • Training
    • Integration
  • Latest
  • Latest menu

    • News
    • Blog
    • Events
    • Videos
  • Downloads
  • Downloads menu

    • Brochures
    • Webinars
    • White Papers
    • Case Studies
    • Product briefs
    • Technical notes
    • Software licensing
  • Company
  • Company menu

    • About Rapita
    • Careers
    • Customers
    • Distributors
    • Industries
    • Locations
    • Partners
    • Research projects
    • Contact
  • Discover
    • Multicore Timing Analysis
    • Embedded Software Testing Tools
    • Worst Case Execution Time
    • WCET Tools
    • Code coverage for Ada, C & C++
    • MC/DC Coverage
    • Verifying additional code for DO-178C
    • Timing analysis (WCET) & Code coverage for MATLAB® Simulink®
    • Data Coupling & Control Coupling
    • Aerospace Software Testing
    • Automotive Software Testing
    • Certifying eVTOL
    • DO-178C
    • AC 20-193 and AMC 20-193
    • ISO 26262
    • What is CAST-32A?

All materials © Rapita Systems Ltd. 2025 - All rights reserved | Privacy information | Trademark notice Subscribe to our newsletter