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 Smarter robot vacuum cleaners for automated office cleaning
15.08.2017 | Fraunhofer-Institut für Arbeitswirtschaft und Organisation IAO

nachricht Researchers 3-D print first truly microfluidic 'lab on a chipl devices
15.08.2017 | Brigham Young 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: Exotic quantum states made from light: Physicists create optical “wells” for a super-photon

Physicists at the University of Bonn have managed to create optical hollows and more complex patterns into which the light of a Bose-Einstein condensate flows. The creation of such highly low-loss structures for light is a prerequisite for complex light circuits, such as for quantum information processing for a new generation of computers. The researchers are now presenting their results in the journal Nature Photonics.

Light particles (photons) occur as tiny, indivisible portions. Many thousands of these light portions can be merged to form a single super-photon if they are...

Im Focus: Circular RNA linked to brain function

For the first time, scientists have shown that circular RNA is linked to brain function. When a RNA molecule called Cdr1as was deleted from the genome of mice, the animals had problems filtering out unnecessary information – like patients suffering from neuropsychiatric disorders.

While hundreds of circular RNAs (circRNAs) are abundant in mammalian brains, one big question has remained unanswered: What are they actually good for? In the...

Im Focus: RAVAN CubeSat measures Earth's outgoing energy

An experimental small satellite has successfully collected and delivered data on a key measurement for predicting changes in Earth's climate.

The Radiometer Assessment using Vertically Aligned Nanotubes (RAVAN) CubeSat was launched into low-Earth orbit on Nov. 11, 2016, in order to test new...

Im Focus: Scientists shine new light on the “other high temperature superconductor”

A study led by scientists of the Max Planck Institute for the Structure and Dynamics of Matter (MPSD) at the Center for Free-Electron Laser Science in Hamburg presents evidence of the coexistence of superconductivity and “charge-density-waves” in compounds of the poorly-studied family of bismuthates. This observation opens up new perspectives for a deeper understanding of the phenomenon of high-temperature superconductivity, a topic which is at the core of condensed matter research since more than 30 years. The paper by Nicoletti et al has been published in the PNAS.

Since the beginning of the 20th century, superconductivity had been observed in some metals at temperatures only a few degrees above the absolute zero (minus...

Im Focus: Scientists improve forecast of increasing hazard on Ecuadorian volcano

Researchers from the University of Miami (UM) Rosenstiel School of Marine and Atmospheric Science, the Italian Space Agency (ASI), and the Instituto Geofisico--Escuela Politecnica Nacional (IGEPN) of Ecuador, showed an increasing volcanic danger on Cotopaxi in Ecuador using a powerful technique known as Interferometric Synthetic Aperture Radar (InSAR).

The Andes region in which Cotopaxi volcano is located is known to contain some of the world's most serious volcanic hazard. A mid- to large-size eruption has...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

Event News

Call for Papers – ICNFT 2018, 5th International Conference on New Forming Technology

16.08.2017 | Event News

Sustainability is the business model of tomorrow

04.08.2017 | Event News

Clash of Realities 2017: Registration now open. International Conference at TH Köln

26.07.2017 | Event News

 
Latest News

New thruster design increases efficiency for future spaceflight

16.08.2017 | Physics and Astronomy

Transporting spin: A graphene and boron nitride heterostructure creates large spin signals

16.08.2017 | Materials Sciences

A new method for the 3-D printing of living tissues

16.08.2017 | Interdisciplinary Research

VideoLinks
B2B-VideoLinks
More VideoLinks >>>