Message passing
Encyclopedia
Message passing in computer science
is a form of communication used in parallel computing
, object-oriented programming
, and interprocess communication. In this model, processes
or objects
can send and receive messages (comprising zero or more bytes, complex data structures, or even segments of code) to other processes. By waiting for messages, processes can also synchronize
.
invocation, signals, and data packets. When designing a message passing system several choices are made:
Prominent theoretical foundations of concurrent computation, such as the Actor model
and the process calculi are based on message passing. Implementations of concurrent systems that use message passing can either have message passing as an integral part of the language, or as a series of library calls from the language.
Examples of the former include many distributed object systems. Examples of the latter include Microkernel operating system
s pass messages between one kernel and one or more server blocks, and the Message Passing Interface
used in high-performance computing
.
, Java RMI, DCOM
, SOAP, .NET Remoting
, CTOS, QNX Neutrino RTOS
, OpenBinder
, D-Bus
and similar are message passing systems.
Message passing systems have been called "shared nothing" systems because the message passing abstraction hides underlying state changes that may be used in the implementation of sending messages.
Message passing model based programming languages typically define messaging as the (usually asynchronous) sending (usually by copy) of a data item to a communication endpoint (Actor, process, thread, socket, etc.). Such messaging is used in Web Services by SOAP. This concept is the higher-level version of a datagram
except that messages can be larger than a packet and can optionally be made reliable, durable
, secure
, and/or transacted
.
Messages are also commonly used in the same sense as a means of interprocess communication; the other common technique being streams or pipes, in which data are sent as a sequence of elementary data items instead (the higher-level version of a virtual circuit
).
Synchronous communication has two advantages. The first advantage is that reasoning about the program can be simplified in that there is a synchronisation point between sender and receiver on message transfer. The second advantage is that no buffering is required. The message can always be stored on the receiving side, because the sender will not continue until the receiver is ready.
Asynchronous message passing systems deliver a message from sender to receiver, without waiting for the receiver to be ready. The advantage of asynchronous communication is that the sender and receiver can overlap their computation because they do not wait for each other.
Synchronous communication can be built on top of asynchronous communication by ensuring that the sender always wait for an acknowledgement message from the receiver before continuing.
The buffer required in asynchronous communication can cause problems when it is full. A decision has to be made whether to block the sender or whether to discard future messages. If the sender is blocked, it may lead to an unexpected deadlock
. If messages are dropped, then communication is no longer reliable.
. In a traditional
containing the addresses of each of the arguments. This form of communication differs from message passing in at least three crucial areas:
In message passing, each of the arguments has to have sufficient available extra memory for copying the existing argument into a portion of the new message. This applies irrespective of the size of the original arguments – so if one of the arguments is (say) an HTML
string of 31,000 octet
s describing a web page (similar to the size of this article), it has to be copied in its entirety (and perhaps even transmitted) to the receiving program (if not a local program).
By contrast, for the call method, only an address of say 4 or 8 bytes needs to be passed for each argument and may even be passed in a general purpose register requiring zero additional storage and zero "transfer time". This of course is not possible for distributed systems since an (absolute) address – in the callers address space – is normally meaningless to the remote program (however, a relative address might in fact be usable if the callee had an exact copy of, at least some of, the callers memory in advance). Web browsers and web server
s are examples of processes that communicate by message passing. A URL is an example of a way
of referencing resources that does depend on exposing the internals of a process.
A subroutine
call or method
invocation will not exit until the invoked computation has terminated. Asynchronous message passing, by contrast, can result in a response arriving a significant time after the request message was sent.
A message handler will, in general, process messages from more than one sender. This means its state can change for reasons unrelated to the behaviour of a single sender or client process. This is in contrast to the typical behaviour of an object upon which methods are being invoked: the latter is expected to remain in the same state between method invocations. (in other words, the message handler behaves analogously to a volatile object
).
of the main alternatives is mutual exclusion
or locking. Examples of resources include shared memory, a disk file or region thereof, a database table or set of rows.
In locking, a resource is essentially shared, and processes wishing to access it (or a sector of it) must first obtain a lock. Once the lock is acquired, other processes are blocked out, ensuring that corruption from simultaneous writes does not occur. After the process with the lock is finished with the resource, the lock is then released.
With the message-passing solution, it is assumed that the resource is not exposed, and all changes to it are made by an associated process, so that the resource is encapsulated. Processes wishing to access the resource send a request message to the handler. If the resource (or subsection) is available, the handler makes the requested change as an atomic event, that is conflicting requests are not acted on until the first request has been completed.
If the resource is not available, the request is generally queued. The sending programme may or may not wait until the request has been completed.
and Pi calculus.
In the terminology of some object-oriented programming language
s, a message is the single means to pass control to an object. If the object "responds" to the message, it has a method
for that message. In pure object-oriented programming
, message passing is performed exclusively through a dynamic dispatch
strategy.
Objects can send messages to other objects from within their method bodies. Message passing enables extreme late binding
in systems. Sending the same message to an object twice will usually result in the object applying the method twice. Two messages are considered to be the same message type, if the name and the arguments
of the message are identical. Some languages support the forwarding or delegation of method invocations from one object to another if the former has no method to handle the message, but "knows" another object that may have one. See also Inversion of Control
.
Alan Kay
has argued that message passing is more important than objects in OOP, and that objects themselves are often over-emphasized. The live distributed object
s programming model builds upon this observation; it uses the concept of a distributed data flow
to characterize the behavior of a complex distributed system in terms of message patterns, using high-level, functional-style specifications.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
is a form of communication used in parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
, object-oriented programming
Object-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
, and interprocess communication. In this model, processes
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
or objects
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
can send and receive messages (comprising zero or more bytes, complex data structures, or even segments of code) to other processes. By waiting for messages, processes can also synchronize
Synchronization (computer science)
In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
.
Overview
Message passing is the paradigm of communication where messages are sent from a sender to one or more recipients. Forms of messages include (remote) methodMethod (computer programming)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
invocation, signals, and data packets. When designing a message passing system several choices are made:
- Whether messages are transferred reliablyReliability (computer networking)In computer networking, a reliable protocol is one that provides reliability properties with respect to the delivery of data to the intended recipient, as opposed to an unreliable protocol, which does not provide notifications to the sender as to the delivery of transmitted data.A reliable...
- Whether messages are guaranteed to be delivered in orderOut-of-order deliveryIn computer networking, out-of-order delivery is the delivery of data packets in a different order from which they were sent. Out-of-order delivery can be caused by packets following multiple paths through a network, or via parallel processing paths within network equipment that are not designed to...
- Whether messages are passed one-to-one, one-to-many (unicastUnicastright|200pxIn computer networking, unicast transmission is the sending of messages to a single network destination identified by a unique address.-Addressing methodologies:...
ing or multicastMulticastIn computer networking, multicast is the delivery of a message or information to a group of destination computers simultaneously in a single transmission from the source creating copies automatically in other network elements, such as routers, only when the topology of the network requires...
), or many-to-one (client–server). - Whether communication is synchronous or asynchronousSynchronization (computer science)In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
.
Prominent theoretical foundations of concurrent computation, such as the Actor model
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
and the process calculi are based on message passing. Implementations of concurrent systems that use message passing can either have message passing as an integral part of the language, or as a series of library calls from the language.
Examples of the former include many distributed object systems. Examples of the latter include Microkernel operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s pass messages between one kernel and one or more server blocks, and the Message Passing Interface
Message Passing Interface
Message Passing Interface is a standardized and portable message-passing system designed by a group of researchers from academia and industry to function on a wide variety of parallel computers...
used in high-performance computing
High-performance computing
High-performance computing uses supercomputers and computer clusters to solve advanced computation problems. Today, computer systems approaching the teraflops-region are counted as HPC-computers.-Overview:...
.
Message passing systems
Distributed object and remote method invocation systems like ONC RPC, CorbaÇorba
Chorba , ciorbă , shurpa , shorpo , or sorpa is one of various kinds of soup or stew found in national cuisines across Middle East...
, Java RMI, DCOM
Distributed component object model
Distributed Component Object Model is a proprietary Microsoft technology for communication among software components distributed across networked computers. DCOM, which originally was called "Network OLE", extends Microsoft's COM, and provides the communication substrate under Microsoft's COM+...
, SOAP, .NET Remoting
.NET Remoting
.NET Remoting is a Microsoft application programming interface for interprocess communication released in 2002 with the 1.0 version of .NET Framework. It is one in a series of Microsoft technologies that began in 1990 with the first version of Object Linking and Embedding for 16-bit Windows...
, CTOS, QNX Neutrino RTOS
QNX
QNX is a commercial Unix-like real-time operating system, aimed primarily at the embedded systems market. The product was originally developed by Canadian company, QNX Software Systems, which was later acquired by Canadian BlackBerry-producer Research In Motion.-Description:As a microkernel-based...
, OpenBinder
OpenBinder
OpenBinder is a system for Inter-process communication. It was developed at Be Inc. and then Palm, Inc. and has more recently been used in the Android operating system developed by Google....
, D-Bus
D-Bus
In computing, D-Bus is a simple inter-process communication open-source system for software applications to communicate with one another. Heavily influenced by KDE2–3's DCOP system, D-Bus has replaced DCOP in the KDE 4 release. An implementation of D-Bus supports most POSIX operating...
and similar are message passing systems.
Message passing systems have been called "shared nothing" systems because the message passing abstraction hides underlying state changes that may be used in the implementation of sending messages.
Message passing model based programming languages typically define messaging as the (usually asynchronous) sending (usually by copy) of a data item to a communication endpoint (Actor, process, thread, socket, etc.). Such messaging is used in Web Services by SOAP. This concept is the higher-level version of a datagram
Datagram
A datagram is a basic transfer unit associated with a packet-switched network in which the delivery, arrival time, and order are not guaranteed....
except that messages can be larger than a packet and can optionally be made reliable, durable
Durable
Durability is the ability to endure. It can refer to:*Durable goods, goods with a long usable life in economics.*Durability , one of the ACID properties.In safety and technology:*Dust resistant*Fire resistant*Rot-proof...
, secure
Secure
Secure may refer to:* Security, being protected against danger or loss** Securitate , the secret service of Communist Romania* Security , e.g. secured loans...
, and/or transacted
Database transaction
A transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
.
Messages are also commonly used in the same sense as a means of interprocess communication; the other common technique being streams or pipes, in which data are sent as a sequence of elementary data items instead (the higher-level version of a virtual circuit
Virtual circuit
In telecommunications and computer networks, a virtual circuit , synonymous with virtual connection and virtual channel, is a connection oriented communication service that is delivered by means of packet mode communication...
).
Synchronous versus asynchronous message passing
Synchronous message passing systems require the sender and receiver to wait for each other to transfer the message. That is, the sender will not continue until the receiver has received the message.Synchronous communication has two advantages. The first advantage is that reasoning about the program can be simplified in that there is a synchronisation point between sender and receiver on message transfer. The second advantage is that no buffering is required. The message can always be stored on the receiving side, because the sender will not continue until the receiver is ready.
Asynchronous message passing systems deliver a message from sender to receiver, without waiting for the receiver to be ready. The advantage of asynchronous communication is that the sender and receiver can overlap their computation because they do not wait for each other.
Synchronous communication can be built on top of asynchronous communication by ensuring that the sender always wait for an acknowledgement message from the receiver before continuing.
The buffer required in asynchronous communication can cause problems when it is full. A decision has to be made whether to block the sender or whether to discard future messages. If the sender is blocked, it may lead to an unexpected deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
. If messages are dropped, then communication is no longer reliable.
Message passing versus calling
Message passing should be contrasted with the alternative communication method for passing information between programs – the CallCalling convention
In computer science, a calling convention is a scheme for how subroutines receive parameters from their caller and how they return a result; calling conventions can differ in:...
. In a traditional
Call, arguments are passed to the "callee" (the receiver) typically by one or more general purpose registers or in a parameter listParameter (computer science)
In computer programming, a parameter is a special kind of variable, used in a subroutine to refer to one of the pieces of data provided as input to the subroutine. These pieces of data are called arguments...
containing the addresses of each of the arguments. This form of communication differs from message passing in at least three crucial areas:
- total memory usage
- transfer timeBit rateIn telecommunications and computing, bit rate is the number of bits that are conveyed or processed per unit of time....
- locality
In message passing, each of the arguments has to have sufficient available extra memory for copying the existing argument into a portion of the new message. This applies irrespective of the size of the original arguments – so if one of the arguments is (say) an HTML
HTML
HyperText Markup Language is the predominant markup language for web pages. HTML elements are the basic building-blocks of webpages....
string of 31,000 octet
Octet (computing)
An octet is a unit of digital information in computing and telecommunications that consists of eight bits. The term is often used when the term byte might be ambiguous, as there is no standard for the size of the byte.-Overview:...
s describing a web page (similar to the size of this article), it has to be copied in its entirety (and perhaps even transmitted) to the receiving program (if not a local program).
By contrast, for the call method, only an address of say 4 or 8 bytes needs to be passed for each argument and may even be passed in a general purpose register requiring zero additional storage and zero "transfer time". This of course is not possible for distributed systems since an (absolute) address – in the callers address space – is normally meaningless to the remote program (however, a relative address might in fact be usable if the callee had an exact copy of, at least some of, the callers memory in advance). Web browsers and web server
Web server
Web server can refer to either the hardware or the software that helps to deliver content that can be accessed through the Internet....
s are examples of processes that communicate by message passing. A URL is an example of a way
of referencing resources that does depend on exposing the internals of a process.
A subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
call or method
Method (computer programming)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
invocation will not exit until the invoked computation has terminated. Asynchronous message passing, by contrast, can result in a response arriving a significant time after the request message was sent.
A message handler will, in general, process messages from more than one sender. This means its state can change for reasons unrelated to the behaviour of a single sender or client process. This is in contrast to the typical behaviour of an object upon which methods are being invoked: the latter is expected to remain in the same state between method invocations. (in other words, the message handler behaves analogously to a volatile object
Volatile variable
In computer programming, particularly in the C, C++, C#, and Java programming languages, a variable or object declared with the volatile keyword usually has special properties related to optimization and/or threading...
).
Message passing and locks
Message passing can be used as a way of controlling access to resources in a concurrent or asynchronous system. Oneof the main alternatives is mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
or locking. Examples of resources include shared memory, a disk file or region thereof, a database table or set of rows.
In locking, a resource is essentially shared, and processes wishing to access it (or a sector of it) must first obtain a lock. Once the lock is acquired, other processes are blocked out, ensuring that corruption from simultaneous writes does not occur. After the process with the lock is finished with the resource, the lock is then released.
With the message-passing solution, it is assumed that the resource is not exposed, and all changes to it are made by an associated process, so that the resource is encapsulated. Processes wishing to access the resource send a request message to the handler. If the resource (or subsection) is available, the handler makes the requested change as an atomic event, that is conflicting requests are not acted on until the first request has been completed.
If the resource is not available, the request is generally queued. The sending programme may or may not wait until the request has been completed.
Mathematical models
The prominent mathematical models of message passing are the Actor modelActor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
and Pi calculus.
In the terminology of some object-oriented programming language
Object-oriented programming language
This is a list of object-oriented programming programming languages.-Languages with object-oriented features:*ABAP*Ada 95*AmigaE*BETA*Blue*Boo*C++*C#*COBOL*Cobra*ColdFusion*Common Lisp*COOL*CorbaScript*Clarion*CLU*Curl*D*Dylan*E*Eiffel...
s, a message is the single means to pass control to an object. If the object "responds" to the message, it has a method
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
for that message. In pure object-oriented programming
Object-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
, message passing is performed exclusively through a dynamic dispatch
Dynamic dispatch
In computer science, dynamic dispatch is the process of mapping a message to a specific sequence of code at runtime. This is done to support the cases where the appropriate method can't be determined at compile-time...
strategy.
Objects can send messages to other objects from within their method bodies. Message passing enables extreme late binding
Late binding
Late binding is a computer programming mechanism in which the method being called upon an object is looked up by name at runtime. This is informally known as duck typing or name binding....
in systems. Sending the same message to an object twice will usually result in the object applying the method twice. Two messages are considered to be the same message type, if the name and the arguments
Parameter (computer science)
In computer programming, a parameter is a special kind of variable, used in a subroutine to refer to one of the pieces of data provided as input to the subroutine. These pieces of data are called arguments...
of the message are identical. Some languages support the forwarding or delegation of method invocations from one object to another if the former has no method to handle the message, but "knows" another object that may have one. See also Inversion of Control
Inversion of Control
In software engineering, Inversion of Control is an abstract principle describing an aspect of some software architecture designs in which the flow of control of a system is inverted in comparison to procedural programming....
.
Alan Kay
Alan Kay
Alan Curtis Kay is an American computer scientist, known for his early pioneering work on object-oriented programming and windowing graphical user interface design, and for coining the phrase, "The best way to predict the future is to invent it."He is the president of the Viewpoints Research...
has argued that message passing is more important than objects in OOP, and that objects themselves are often over-emphasized. The live distributed object
Live distributed object
- Definitions :The term live distributed object refers to a running instance of a distributed multi-party protocol, viewed from the object-oriented perspective, as an entity that has a distinct identity, may encapsulate internal state and threads of execution, and that exhibits a well-defined...
s programming model builds upon this observation; it uses the concept of a distributed data flow
Distributed data flow
Distributed data flow refers to a set of events in a distributed application or protocol that satisfies the following informal properties:* Asynchronous, non-blocking, and one-way...
to characterize the behavior of a complex distributed system in terms of message patterns, using high-level, functional-style specifications.
Examples
- Actor model implementationActor model implementationIn computer science, Actor model implementation concerns implementation issues for the Actor model.-Cosmic Cube:The Cosmic Cube was developed by Chuck Seitz et al. at Caltech providing architectural support for Actor systems...
- Amorphous computingAmorphous computingAmorphous computing refers to computational systems that use very large numbers of identical, parallel processors each having limited computational ability and local interactions...
- Flow-based programmingFlow-based programmingIn computer science, flow-based programming is a programming paradigm that defines applications as networks of "black box" processes, which exchange data across predefined connections by message passing, where the connections are specified externally to the processes...
- SOAP (protocol)
See also
- Active messageActive messageAn Active message is a messaging object capable of performing processing on its own. This contrasts with traditional computer-based messaging systems in which messages are passive entities with no processing power....
- Database-centric architectureDatabase-centric architectureDatabase-centric architecture or data-centric architecture has several distinct meanings, generally relating to software architectures in which databases play a crucial role. Often this description is meant to contrast the design to an alternative approach...
- Distributed computingDistributed computingDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
- Dynamic dispatchDynamic dispatchIn computer science, dynamic dispatch is the process of mapping a message to a specific sequence of code at runtime. This is done to support the cases where the appropriate method can't be determined at compile-time...
- Event loopEvent loopIn computer science, the event loop, message dispatcher, message loop, message pump, or run loop is a programming construct that waits for and dispatches events or messages in a program...
- Inter-process communicationInter-process communicationIn computing, Inter-process communication is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared...
- Message loop in Microsoft WindowsMessage loop in Microsoft WindowsMicrosoft Windows programs are event-based. They act upon messages that the operating system posts to the main thread of the application. These messages are received from the message queue by the application by repeatedly calling the GetMessage function in a section of code called the "event...
- Message-oriented middlewareMessage-oriented middlewareMessage-oriented middleware is software or hardware infrastructure supporting sending and receiving messages between distributed systems. MOM allows application modules to be distributed over heterogeneous platforms and reduces the complexity of developing applications that span multiple...
- Messaging pattern