Message passing in
computer scienceComputer 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 computingParallel 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 programmingObject-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,
processesIn 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
objectsIn 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
synchronizeIn 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)
methodIn 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 reliably
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 order
In 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 (unicast
right|200pxIn computer networking, unicast transmission is the sending of messages to a single network destination identified by a unique address.-Addressing methodologies:...
ing or multicastIn 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 asynchronous
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 modelIn 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 systemAn 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 InterfaceMessage 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 computingHigh-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,
CorbaChorba , ciorbă , shurpa , shorpo , or sorpa is one of various kinds of soup or stew found in national cuisines across Middle East...
, Java RMI,
DCOMDistributed 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 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 RTOSQNX 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...
,
OpenBinderOpenBinder 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-BusIn 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
datagramA 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,
durableDurability 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...
,
secureSecure may refer to:* Security, being protected against danger or loss** Securitate , the secret service of Communist Romania* Security , e.g. secured loans...
, and/or
transactedA 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 circuitIn 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
deadlockA 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
CallIn 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 listIn 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 time
In 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
HTMLHyperText Markup Language is the predominant markup language for web pages. HTML elements are the basic building-blocks of webpages....
string of 31,000
octetAn 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 serverWeb 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
subroutineIn 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
methodIn 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 objectIn 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. One
of the main alternatives is
mutual exclusionMutual 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 modelIn 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 languageThis 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
methodIn 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 programmingObject-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 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...
strategy.
Objects can send messages to other objects from within their method bodies. Message passing enables extreme
late bindingLate 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
argumentsIn 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 ControlIn 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 KayAlan 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- 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 flowDistributed 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 implementation
In 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 computing
Amorphous computing refers to computational systems that use very large numbers of identical, parallel processors each having limited computational ability and local interactions...
- Flow-based programming
In 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 message
An 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 architecture
Database-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 computing
Distributed 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 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...
- Event loop
In 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 communication
In 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 Windows
Microsoft 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 middleware
Message-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
External links