New approach eliminates software deadlocks using discrete control theory

Dec 02, 2008

(PhysOrg.com) -- 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.

Provided by University of Michigan

Explore further: Artificial intelligence that imitates children's learning

add to favorites email to friend print save as pdf

Related Stories

Recommended for you

Artificial intelligence that imitates children's learning

3 hours ago

The computer programmes used in the field of artificial intelligence (AI) are highly specialised. They can for example fly airplanes, play chess or assemble cars in controlled industrial environments. However, a research ...

Oculus unveils new prototype VR headset

Sep 20, 2014

Oculus has unveiled a new prototype of its virtual reality headset. However, the VR company still isn't ready to release a consumer edition.

Who drives Alibaba's Taobao traffic—buyers or sellers?

Sep 18, 2014

As Chinese e-commerce firm Alibaba prepares for what could be the biggest IPO in history, University of Michigan professor Puneet Manchanda dug into its Taobao website data to help solve a lingering chicken-and-egg question.

Computerized emotion detector

Sep 16, 2014

Face recognition software measures various parameters in a mug shot, such as the distance between the person's eyes, the height from lip to top of their nose and various other metrics and then compares it with photos of people ...

User comments : 3

Adjust slider to filter visible comments by rank

Display comments: newest first

GrayMouser
4 / 5 (1) Dec 02, 2008
This is the press release, verbatim even:
http://www.eureka...0208.php
raron
not rated yet Dec 03, 2008
So it injects "control logic" into other programs... hm....
concerned
5 / 5 (1) Dec 03, 2008
I'd have to see this. The logic that leads up to deadlocks can often be very complex and I have serious doubts that anything today (even this new method) can "see" the entire logic that leads up to a deadlock. I don't doubt that it can find SOME logic that leads to deadlocks, but not everything and not anything remotely complex.