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 Gecko adhesion technology moves closer to industrial uses
13.12.2017 | Georgia Institute of Technology

nachricht New silicon structure opens the gate to quantum computers
12.12.2017 | Princeton University

All articles from Information Technology >>>

The most recent press releases about innovation >>>

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

Im Focus: Long-lived storage of a photonic qubit for worldwide teleportation

MPQ scientists achieve long storage times for photonic quantum bits which break the lower bound for direct teleportation in a global quantum network.

Concerning the development of quantum memories for the realization of global quantum networks, scientists of the Quantum Dynamics Division led by Professor...

Im Focus: Electromagnetic water cloak eliminates drag and wake

Detailed calculations show water cloaks are feasible with today's technology

Researchers have developed a water cloaking concept based on electromagnetic forces that could eliminate an object's wake, greatly reducing its drag while...

Im Focus: Scientists channel graphene to understand filtration and ion transport into cells

Tiny pores at a cell's entryway act as miniature bouncers, letting in some electrically charged atoms--ions--but blocking others. Operating as exquisitely sensitive filters, these "ion channels" play a critical role in biological functions such as muscle contraction and the firing of brain cells.

To rapidly transport the right ions through the cell membrane, the tiny channels rely on a complex interplay between the ions and surrounding molecules,...

Im Focus: Towards data storage at the single molecule level

The miniaturization of the current technology of storage media is hindered by fundamental limits of quantum mechanics. A new approach consists in using so-called spin-crossover molecules as the smallest possible storage unit. Similar to normal hard drives, these special molecules can save information via their magnetic state. A research team from Kiel University has now managed to successfully place a new class of spin-crossover molecules onto a surface and to improve the molecule’s storage capacity. The storage density of conventional hard drives could therefore theoretically be increased by more than one hundred fold. The study has been published in the scientific journal Nano Letters.

Over the past few years, the building blocks of storage media have gotten ever smaller. But further miniaturization of the current technology is hindered by...

Im Focus: Successful Mechanical Testing of Nanowires

With innovative experiments, researchers at the Helmholtz-Zentrums Geesthacht and the Technical University Hamburg unravel why tiny metallic structures are extremely strong

Light-weight and simultaneously strong – porous metallic nanomaterials promise interesting applications as, for instance, for future aeroplanes with enhanced...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

See, understand and experience the work of the future

11.12.2017 | Event News

Innovative strategies to tackle parasitic worms

08.12.2017 | Event News

AKL’18: The opportunities and challenges of digitalization in the laser industry

07.12.2017 | Event News

 
Latest News

Plasmonic biosensors enable development of new easy-to-use health tests

14.12.2017 | Health and Medicine

New type of smart windows use liquid to switch from clear to reflective

14.12.2017 | Physics and Astronomy

BigH1 -- The key histone for male fertility

14.12.2017 | Life Sciences

VideoLinks
B2B-VideoLinks
More VideoLinks >>>