© 1988 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Concurrent Maintenance of Data Structures in a Distributed Environment
1 Department of Computer Science, University of Houston, University Park, Houston, Texas 77004, USA, 2 Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana 70803, USA, 3 Valid Logic, Inc., 2820 Orchard Parkway, San Jose, CA 95134, USA
We consider a distributed system consisting of a collection of clients and servers in which each server runs on a processor dedicated to it. Each server can be viewed as an instance of an abstract data-type module that provides a set of facilities for its clients. In such systems it may be possible to improve the performance of a server by scheduling its housekeeping activities to occur during periods when the server is waiting for requests from clients or is transmitting a response to a client. We consider the case where the client requests are handled by a foreground process while the maintenance tasks are performed by one or more background processes. We illustrate how the code for these processes can be developed in a stepwise manner, proceeding from coarse-grained concurrency to fine-grained concurrency. This approach is augmented with the use of rely/guarantee conditions which serve to simplify the proof of non-interference. The method is illustrated using a search-table abstraction.
Received November 1986. revised July 1987.
* Department of Computer Science, University of Houston, University Park, Houston, Texas 77004, USA
Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana 70803, USA
¶ Valid Logic, Inc., 2820 Orchard Parkway, San Jose, CA 95134, USA