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.

To appear in Proc of the 25th IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems, Taipei, Taiwan, October 2005.

Postscript, PDF. © 2005, Springer Verlag.

© Henny Sipma /
Last modified: Thu Jan 12 14:40:50 PDT 2004