New approach eliminates software deadlocks using discrete control theory

December 02, 2008

ANN ARBOR, Mich.--- Software deadlocks are the Catch-22s of the computer world. These common bugs can freeze the machine when different parts of a program end up in an endless cycle of waiting for one another as they access shared data.

University of Michigan researchers developed a new way around this problem with a controller that can anticipate and prevent situations that might cause deadlock.

Their controller is called Gadara. It's a plug-in that operates using feedback techniques similar to those that give us cruise control in cars and thermostats in heating systems.

"This is a totally different approach to what people had done before for deadlock. Previously, engineers would try to identify potential deadlocks through testing or program analysis and then go back and rewrite the program. The bug fixes were manual, and not automatic. Gadara automates the process," said Stéphane Lafortune, a professor in the Department of Electrical Engineering and Computer Science and a Gadara developer.

Yin Wang, a doctoral student who works with Lafortune in the same department, will present a paper on Gadara Dec. 9 at the USENIX Symposium on Operating Systems Design and Implementation in San Diego.

"Every time you find a problem today you need the original programmer to solve it. The goal of Gadara is to allow anyone with our tool to solve the problem," Wang said.

Deadlock is becoming a more pressing concern as multicore chips grow in complexity and software performs an increasing number of tasks simultaneously. The bug shows up often in parallel programs that use shared data.

Gadara works by analyzing a program to find potential deadlocks, and then inserting control logic into the program. The control logic ensures that the program cannot deadlock.

Gadara uses a unique combination of discrete control theory and compiler technology, said Lafortune, whose primary work focuses on discrete control theory. The control theory provides the logic that allows Gadara to use feedback to prevent software deadlocks.

The compiler technology, which was developed by Scott Mahlke, a professor in the Department of Electrical Engineering and Computer Science, enables Gadara to operate on real-world applications. Compilers translate programs written in high-level programming languages in executable code.
-end-
The paper is titled "Gadara: Dynamic Deadlock Avoidance for Multithreaded Programs." Other co-developers of Gadara are Terence Kelly, who received his doctoral degree from U-M and is currently at Hewlett-Packard Laboratories, and Manjunath Kudlur, a recent doctoral graduate from U-M who is now working at NVidia.

Current research on Gadara is funded by the National Science Foundation and by an HP Labs Open Innovation award.

For more information on Lafortune, visit: http://www.eecs.umich.edu/~stephane/
Yin Wang: http://www.eecs.umich.edu/~yinw/
Scott Mahlke: http://www.eecs.umich.edu/~mahlke/
USENIX Symposium on Operating Systems Design and Implementation: http://www.usenix.org/events/osdi08/

Michigan Engineering:

The University of Michigan College of Engineering is ranked among the top engineering schools in the country. At more than $130 million annually, its engineering research budget is one of largest of any public university. Michigan Engineering is home to 11 academic departments and a National Science Foundation Engineering Research Center. The college plays a leading role in the Michigan Memorial Phoenix Energy Institute and hosts the world class Lurie Nanofabrication Facility. Michigan Engineering's premier scholarship, international scale and multidisciplinary scope combine to create The Michigan Difference. Find out more at http://www.engin.umich.edu/.

University of Michigan

Related Electrical Engineering Articles from Brightsurf:

Knotting semimetals in topological electrical circuits
Scientists created exotic states of matter using electrical circuit enhanced by machine-learning algorithm

Physicists make electrical nanolasers even smaller
Researchers cleared the obstacle that had prevented the creation of electrically driven nanolasers for integrated circuits.

Making plastic more transparent while also adding electrical conductivity
In an effort to improve large touchscreens, LED light panels and window-mounted infrared solar cells, researchers at the University of Michigan have made plastic conductive while also making it more transparent.

Using electrical stimulus to regulate genes
A team of researchers led by ETH professor Martin Fussenegger has succeeded in using an electric current to directly control gene expression for the first time.

2D oxide flakes pick up surprise electrical properties
Rice University researchers find evidence of piezoelectricity in lab-grown, two-dimensional flakes of molybdenum dioxide.

Electrical activity in living organisms mirrors electrical fields in atmosphere
A new Tel Aviv University study provides evidence for a direct link between electrical fields in the atmosphere and those found in living organisms, including humans.

3D-printed plastics with high performance electrical circuits
Rutgers engineers have embedded high performance electrical circuits inside 3D-printed plastics, which could lead to smaller and versatile drones and better-performing small satellites, biomedical implants and smart structures.

In and out with 10-minute electrical vehicle recharge
Electric vehicle owners may soon be able to pull into a fueling station, plug their car in, go to the restroom, get a cup of coffee and in 10 minutes, drive out with a fully charged battery, according to a team of engineers.

Electrical stimulation aids in spinal fusion
Spine surgeons in the U.S. perform more than 400,000 spinal fusions each year as a way to ease back pain and prevent vertebrae in the spine from wiggling around and doing more damage.

Fat pumps generate electrical power
A previously unknown electrical current develops in the body's cells when the vital fat pump function of the flippases transfers ('flips') lipids from the outer to the inner layer of the body's cell membranes.

Read More: Electrical Engineering News and Electrical Engineering Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.