Browse Prior Art Database

A probablistic system for launching deadlock detection

IP.com Disclosure Number: IPCOM000223676D
Publication Date: 2012-Nov-22
Document File: 1 page(s) / 36K

Publishing Venue

The IP.com Prior Art Database

Abstract

Programs use locks to control and serialize access to certain resources. If two threads of execution each require two locks, but take them in a different order, they can deadlock; each thread holds one lock and is trying to get the other which is held by the other thread. In this situation, neither thread can make any progress. Deadlock detection is typically carried out using the construction of a graph of locks where the direction of the links corresponds to the order in which locks are acquired. A loop in the graph indicates where locks are taken in a different order at different points in a computer program which could potentially lead to a deadlock. This is well understood, but has the side effect of impacting the system: being able to traverse the locks and threads to build the graph is a "stop the world", time consuming event. As a result, most programs that offer some form of deadlock detection do so only on request, or on an interval basis. Disclosed is a system for determining when there is a high probability that a deadlock has occurred and using this to launch the costly deadlock detection mechanism.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 87% of the total text.

Page 01 of 1

A probablistic system for launching deadlock detection

A system is disclosed that determines a high probability that a deadlock has occurred, and uses that determination to launch an accurate deadlock detection mechanism. This minimises the disruption to the application and maximises the speed of detection by running the deadlock detection only when we have strong statistical indicators that a deadlock has occurred. This has the benefit of providing automatic runtime deadlock detection whilst minimizing the ongoing overhead of continuous interruptive checks being made.

    The disclosed deadlock detection system measures the contended wait time for individual locks. As deadlocks must involve at least two locks, the measured contended wait time from two or more locks occurring at the same are combined into parings and groupings. The parings and groupings are then used to create a statistical model of contended wait time durations that are "normal": have occurred before and not been the cause of a deadlock, or "outliers" compared to the existing statistical model. Where a long contended wait time occurs for two or more locks that is additionally classed as an outlier according to the statistical model of parings and groupings, an accurate deadlock detection mechanism can be launched.

    This mechanism allows for common "phase change" or interruptive events such as garbage collection to occur without triggering deadlock detection for all currently held locks as any pairin...