COSC038@canterbury.ac.nz (Paul Ashton) (07/17/90)
A couple of weeks ago I posted the following question: |> I am trying to track down references which discuss the equivalence of |> shared memory and message passing as inter-process communication |> methods. A summary of the replies, and where they came from follows. My reason for asking the question is that I am trying to develop a way of describing the processing performed for individual user interactions in a distributed environment. I thought that if it had been shown reasonably formally that the shared memory and message passing forms of IPC are duals, and it had also been shown that there exists a simple mapping between them, then I could just develop ways of representing one form (say message passing), and declare the other form (say shared memory) to be easily mapped onto the representation of the first. The paper by Lauer and Needham showed empirically that operating systems that are "procedure oriented" (single kernel address space shared by many threads which communicate using the shared kernel address space), and operating systems that are "message oriented: (multiple kernel processes each with their own address space, and processes comunicate by message passing) are duals in the sense that "a program or subsystem constructed strictly according to the primitives defined by one model can be mapped into a dual program or subsystem which fits the other model." This paper is a bit too high in level (i.e. at the subsystem or program level) and a somewhat different emaphsis to show what I had hoped to be shown. The paper by Young et al, describes an efficient way of implementing passing large messages (where shared memory is available), where a large message is put into an area of memory which is subsequently mapped (rather than copied) into the receiver's address space. They also describe a virtual memory implementation (which can support shared virtual memory) which is implemented by providing for pagers implemented outside the kernel, with a message passing interface specified for interactions between an application, the kernel, and a pager. They say that where both IPC mechanisms are available, one can be used to provide the services of the other, but in an empirical rather than formal way. The paper by Andrews and Schneider contains a survey of synchronisation and message passing mechanisms, and how they are supported by programming language constucts. They describe three models of concurrent programming languages: - procedure oriented - process interaction based on shared variables. Mechanisms for synchronising access to the shared variables are required. - message oriented - process interaction based on send and receive primitives. - operatrion oriented - process interaction based on RPC. They state that "At an abstract level the three types of languages are interchangeable." Again a fairly high level viewpoint. The paper by Scott is more on remote procedure calls Vs message passing. I have not got hold of the papers by Dally, by Valiant or by Cashin, so if they seem to contain something relevant to the problem I outlined above I would appreciate hearing about it (or hearing about any other references I might have missed). Thanks to all who responded Paul Ashton. Reference list: From: bsy+@cs.cmu.edu (Bennet S. Yee) @Inproceedings(MachSOSP11, Author="Michael Wayne Young and Avadis {Tevanian, Jr.} and Richard F. Rashid and David B. Golub and Jeffrey Eppinger and Jonathan Chew and William Bolosky and David L. Black and Robert V. Baron", Key="Young et al.", Booktitle="Proceedings of the 11th Symposium on Operating System Principles", Organization="ACM", Title="The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System", Year=1987, Month="November", Pages="63-76") ---------------------------------------------------------------- From: jamesp@bison.cs.uwa.OZ.AU %T On the Duality of Operating System Structures %A Hugh C. Lauer %A Roger M. Needham %J Operating Systems Review %V 13 %N 2 %D April 1979 %P 3-19 %O Originally from Proceeding of the Second International Symposium on Operating Systems, IRIA, October 1978 --------------------------------------------------------------- From: Terrence W. Holm (holm@mprgate.mpr.ca) Thesis: Terrence W. Holm The Execution Capability Model MMath Thesis 1985 University of Waterloo Waterloo, Ontario, Canada Overview: Andrews, G.R. and Schneider, F.B. ``Concepts and Notations for Concurrent Programming'' ACM Computing Surveys 15,1. March 1983. pp. 3-43 Duality: Lauer H.C. and Needham R.M. ``On the Duality of Operating System Structures'' Operating Systems Review. 13,2. April 1979. pp3-19 Cashin, P. ``Inter Process Communication'' Bell-Northern Research Ref 8005014. June 1980. -------------------------------------------------------------- From: pardo@cs.washington.edu Not really what you asked, see also %A Michael Lee Scott %T Messages vs. Remote Procedures is a False Dichotomy %J SIGPLAN Notices %V 18 %N 5 %D May 1983 Also, famous quote (but I don't know who said it): ``RPC is poor man's shared memory.'' ----------------------------------------------------------------------- From: ecsv38@castle.edinburgh.ac.UK (S Manoharan) Universal communication mechanisms are discussed in: @inproceedings{dally, author = {W.J. Dally}, title = {Universal Mechanisms for Concurrency}, booktitle = {PARLE '89, Parallel Architectures and Languages Europe}, publisher = {Springer-Verlag Lecture Notes in Computer Science 365}, month = {June}, year = {1989}, pages = {19-33}, } Another related paper is: @article{valiant:royal, author = {L.G. Valiant}, title = {Optimally Universal Parallel Computers}, journal = {Proceedings of the Royal Society}, year = {1987}, } --------------------------------------------------------------- -- Paul Ashton Email(internet): paul@cosc.canterbury.ac.nz NZ Telecom: Office: +64 3 667 001 x6350 NZ Post: Dept of Computer Science University of Canterbury, Christchurch, New Zealand