Reliable, Fair and Efficient Concurrent Software withDynamic Allocation of Identical Resources

Dynamic allocation of a class of identical resources, such as memory slots, is considered for concurrent software. Resources are allocated at run time to processes in a context prone to deadlock [Coffman 71] : the resources are allocated to one process at a time, a process may hold allocated resources while awaiting assignment of others, no resource can be forcibly removed from a process holding it. Safety of concurrent software, i.e. absence of deadlock, can be obtained by avoidance policies, called in this paper beforehand precaution and dynamic prevention. Both rely on the banker's algorithm [Habermann 69] based on a priori process claims and on service postponement when a request can lead to deadlock once processes proceed requesting resources up to their claims. Fairness of concurrent software, i.e. starvation avoidance cannot always be based on a pure FIFO service of requests since it may block all the processes and therefore introduce another source of deadlock. We present a safe and fair implementation which rely on the concurrent semantic of protected objects in Ada and which has been proven with the model of colored Petri nets