Thread Allocation Protocols for Distributed Real-Time and Embedded Systems

Cesar Sanchez, Henny B. Sipma, Venkita Subramonian, Christopher Gill, Zohar Manna

We study the problem of thread allocation in asynchronous distributed real-time and embedded systems. Each distributed node handles a limited set of resources, in particular a limited thread pool. Different methods can be invoked concurrently in each node, either by external agents or as a remote call during the execution of a method. In this paper we study thread allocation under a WaitOnConnection strategy, in which each nested upcall made while a thread is waiting must be made in a different thread.

We study protocols that control the allocation of threads to guarantee the absence of deadlocks. First, we introduce a computational model in which we formally describe the different protocols and their desired properties. Then, we study two scenarios: a single agent performing sequential calls, and multiple agents with unrestricted concurrency. For each scenario we present (1) algorithms to compute the minimum amount of resources to avoid deadlocks, and (2) run-time protocols that control the allocation of these resources.

In Formal Techniques for Networked and Distributed Systems (FORTE 2005): 25th IFIP WG 6.1 International Conference, October 2005, Lecture Notes in Computer Science, Volume 3731, Springer Verlag, pp 159-173.

Postscript, PDF. © 2005, Springer Verlag.


© Henny Sipma / sipma@cs.stanford.edu
Last modified: Thu Jan 12 14:40:50 PDT 2004