Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

New Approach Eliminates Software Deadlocks Using Discrete Control Theory

04.12.2008
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.

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.

Nicole Casal Moore | Newswise Science News
Further information:
http://www.umich.edu
http://www.engin.umich.edu

More articles from Information Technology:

nachricht NIST's antenna evaluation method could help boost 5G network capacity and cut costs
11.12.2018 | National Institute of Standards and Technology (NIST)

nachricht ETRI exchanged quantum information on daylight in a free-space quantum key distribution
10.12.2018 | National Research Council of Science & Technology

All articles from Information Technology >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Topological material switched off and on for the first time

Key advance for future topological transistors

Over the last decade, there has been much excitement about the discovery, recognised by the Nobel Prize in Physics only two years ago, that there are two types...

Im Focus: Researchers develop method to transfer entire 2D circuits to any smooth surface

What if a sensor sensing a thing could be part of the thing itself? Rice University engineers believe they have a two-dimensional solution to do just that.

Rice engineers led by materials scientists Pulickel Ajayan and Jun Lou have developed a method to make atom-flat sensors that seamlessly integrate with devices...

Im Focus: Three components on one chip

Scientists at the University of Stuttgart and the Karlsruhe Institute of Technology (KIT) succeed in important further development on the way to quantum Computers.

Quantum computers one day should be able to solve certain computing problems much faster than a classical computer. One of the most promising approaches is...

Im Focus: Substitute for rare earth metal oxides

New Project SNAPSTER: Novel luminescent materials by encapsulating phosphorescent metal clusters with organic liquid crystals

Nowadays energy conversion in lighting and optoelectronic devices requires the use of rare earth oxides.

Im Focus: A bit of a stretch... material that thickens as it's pulled

Scientists have discovered the first synthetic material that becomes thicker - at the molecular level - as it is stretched.

Researchers led by Dr Devesh Mistry from the University of Leeds discovered a new non-porous material that has unique and inherent "auxetic" stretching...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

New Plastics Economy Investor Forum - Meeting Point for Innovations

10.12.2018 | Event News

EGU 2019 meeting: Media registration now open

06.12.2018 | Event News

Expert Panel on the Future of HPC in Engineering

03.12.2018 | Event News

 
Latest News

Electronic evidence of non-Fermi liquid behaviors in an iron-based superconductor

11.12.2018 | Physics and Astronomy

Topological material switched off and on for the first time

11.12.2018 | Materials Sciences

NIST's antenna evaluation method could help boost 5G network capacity and cut costs

11.12.2018 | Information Technology

VideoLinks
Science & Research
Overview of more VideoLinks >>>