Synchronization in actor systems

ABSTRACT

This paper presents a mechanism for the arbitration of parallel requests to shared resources. This mechanism is the serialize, which may be described as a kind of protection mechanism, in that it prevents improper orders of access to a protected resource. The mechanism is a generalization and improvement of the monitor mechanism of Brinch-Hansen and Hoare.Serializers attempt to systematize and abstract desirable structural features of synchronization control structure into a coherent language construct. They represent an improvement in the modularity of synchronization over monitors in several respects. Monitors synchronize requests by providing a pair of operations for each request type [examples are STARTREAD/ENDREAD and STARTWRITE/ENDWRITE for the readers-writers problems]. Such a pair of operations must be used in a certain order for the synchronization to work properly, yet nothing in the monitors construct enforces this use. Serializers incorporate this structural aspect of synchronization in a unified mechanism to guarantee proper check-in and check-out. In scheduling access to a protected resource, it is often desired to wait in a queue for a certain condition before it continues execution. Monitors require that a process waiting in a queue will remain dormant forever, unless another process explicitly signals to the dormant process that it should continue. Serializers improve the modularity of synchronization by providing that the condition for resuming execution must be explicitly stated when a process enters a queue making it it unnecessary for processes to signal other processes. Each process determines for itself the conditions required for its further execution.The behavior of a serializer is defined using the actor message-passing model of computation. Different versions of the "readers-writers" problems are used to illustrate how the structure of a serializer corresponds in a natural way to the structure of the arbitration problem to be solved. The correspondence makes it easier to synthesize a scheduler from behavioral specifications and to verify that an implementation satisfies its specifications.No claim is made for the "completeness" of the serializer mechanism, beyond showing that semaphores can be implemented using serializers. Further, no "complete" solution is proposed to the "no-starvation" specification which requires that a resource reply to each request which it receives. Rather, it is shown for some simple examples that serializers represent a step toward better structuring of parallel access to shared resources, and that proofs that starvation is impossible for these examples are easier with serializers than with some of the currently existing mechanisms for controlling parallel access to resources.

REFERENCES

• 1: Dijkstra, E. W. "Hierarchical Ordering of Sequential Processes" Acta Informatica. 1971.
• 2: I. Grief , Irene Greif, SEMANTICS OF COMMUNICATING PARALLEL PROCESSES, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 3: Irene Greif , Carl Hewitt, Actor semantics of PLANNER-73, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.67-77, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512984]
• 4: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 5: Hewitt, C., Bishop P., and Steiger, R. "A Universal Modular Actor Formalism for Artificial Intelligence" IJCAI-73. Stanford, Calif. Aug, 1973. pp. 235-245.
• 6: Hewitt, C. and Smith, B. "Towards a Programming Apprentice" IEEE Transactions on Software Engineering. SE-1, 1. March 1975. pp. 26-45.
• 7: Hewitt, C. "Protection and Synchronization in Actor Systems" ACM SIGCOMM-SIGOPS Interface Workshop on Interprocess Communication. March 24-25, 1975. Santa Monica, Calif.
• 8: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 9: John H. Howard, Proving monitors, Communications of the ACM, v.19 n.5, p.273-279, May 1976 [doi>10.1145/360051.360079]