Talk by Sanchez on Deadlock Avoidance for Distributed Real-Time and Embedded Systems
Luca de Alfaro
Systems
SPEAKER: Cesar Sanchez
Graduating from Department of Computer Science, Stanford University
and starting a postdoc at UCSC
ABSTRACT:
This talk is about deadlock avoidance for distributed real-time and
embedded systems (DREs).
Deadlocks are undesirable states of concurrent systems, characterized
by a set of processes in a circular wait state, in which each process
is blocked trying to gain access to a resource held by the next one in
the chain. Solutions can be classified into three categories:
- Deadlock detection is an optimistic approach. It assumes that
deadlocks are infrequent and detects and corrects them at
run-time. This technique is not applicable to real-time systems
since the worst case running time is long. Moreover, in embedded
systems actions cannot be undone.
- Deadlock prevention is a pessimistic approach. The possibility of a
deadlock is broken statically at the price of restricting
concurrency.
- Deadlock avoidance takes a middle route. At runtime each allocation
request is examined to ensure that it cannot lead to a deadlock.
Deadlock prevention is commonly used in DREs but, since concurrency is
severely limited, an efficient distributed deadlock avoidance schema
can have a big practical impact. However, it is known since the mid
90s that the general solution for distributed deadlock avoidance is
impractical, because it requires maintaining global states and global
atomicity of actions. The communication costs involved simply outweigh
the benefits gained from avoidance over prevention.
I will present an efficient distributed deadlock avoidance schema that
requires no inter-site communication, based on a combination of static
analysis and runtime protocols. This solution assumes that the
possible sequences of calls are available for analysis at design
time. I will also present extensions of the basic schema that
guarantee liveness, and an efficient distributed priority inheritance
protocol. Finally, I will discuss the trade-offs to implement these
protocols and the importance of accurate static analysis.
------------------------------------------------------------
Luca de Alfaro
TITLE: Deadlock Avoidance for Distributed Real-Time and Embedded
Systems
SPEAKER: Cesar Sanchez
Graduating from Department of Computer Science, Stanford University
and starting a postdoc in the Department of Computer Engineering,
SOE, UCSC
Tuesday, May 22, 2007
2:15pm, E2 Rm. 399