Transcript Stacey Levine

Stacey Levine
Chapter 4.1
Message Passing Communication
Introduction

Basic Message passing
Communication Models
Support for processes to communicate
among themselves.
 Traditional (centralized) OS’s:

– Provide local (within single machine)
communication support.
– Distributed OS’s: must provide support for
communication across machine boundaries.

Over LAN or WAN.
Message Passing

Basic communication primitives:
– Send message.
Send
– Receive message.

Modes of communication:
– Synchronous versus asynchronous.
Sending Q
...
Receiving Q
...
Synchronization Stages
Sender
source
network
destination
receiver
kernel
Message
ack
Non blocking send is 1st step. Everything else is blocking
Communication Models

Communication may take place using
either message passing or shared
memory.
Synchronous Communication

Blocking send
– Blocks until message is transmitted
– Blocks until message acknowledged

Blocking receive
– Waits for message to be received

Process synchronization.
Asynchronous Communication


Non-blocking send: sending process continues as
soon as message is queued.
Blocking or non-blocking receive:
– Blocking:


Timeout.
Threads.
– Non-blocking: proceeds while waiting for message.


Message is queued upon arrival.
Process needs to poll or be interrupted.
Direct Communication
Indirect Communication

Indirect communications :
– messages sent to and received from mailboxes (or ports)
 mailboxes can be viewed as objects into which messages placed by
processes and from which messages can be removed by other
processes
– each mailbox has a unique ID
– two processes can communicate only if they have a shared mailbox
The Producer Consumer
Problem

The producer-consumer problem illustrates the
need for synchronization in systems where many
processes share a resource. In the problem, two
processes share a fixed-size buffer. One process
produces information and puts it in the buffer,
while the other process consumes information
from the buffer. These processes do not take
turns accessing the buffer, they both work
concurrently. Herein lies the problem. What
happens if the producer tries to put an item into a
full buffer? What happens if the consumer tries
to take an item from an empty buffer?
Producer
Consumer
Sleep and Wakeup


Waiting is wasteful
Processes waiting to enter their critical sections
waste processor time checking to see if they can
proceed
– when a process is not permitted to access its critical
section, it uses a system call known as Sleep, which
causes that process to block
– . The process will not be scheduled to run again, until
another process uses the Wakeup system call
Semaphores
In the Producer-Consumer problem,
semaphores are used for two purposes:
 mutual exclusion and
 synchronization.
Sleep and Wakeup using Monitors
Message Passing
Sempahores and Monitors use shared
memory.
 Not effective on Distributed systems

Sleep and Wakeup using Message Passing
Two primitives, SEND and RECEIVE are used in the message passing scheme.
• SEND primitive sends a message to a destination process
• RECEIVE primitive receives a message from a specified source process.
•Message Passing works on distributed systems because these messages can be sent from machine
to machine through a network. Typically, each process has a mailbox; a buffer which receives all
the messages which are sent to that process. The destination of the SEND and RECEIVE system
calls is a process' mailbox, not the process itself.
Message Passing Interface
http://www.mpi-forum.org/
 MPI is a message-passing standard
 Process = A regular sequential
language + calls to MPI functions for
sending and receiving messages
 MPI has many implementations, MPI
contains > 130 functions
 MPI 2.1 is the current version

How is Mutual Exclusion implemented with Message Passing
This pictures shows an interaction between a process that wants to access a shared resource, and a
resource control process. Three messages are sent here. Message (1) is a request for access to the
resource. Process P1 then blocks, waiting for a reply from the resource control process. Message (2)
is the reply sent by the control process. This message wakes up P1, and P1 now uses the resource.
Message (3) informs the resource control process that P1 is done using the resource.
Examples ….
SSL
 Local system events (mouse movements..)
 HTTP
 RPC …

References







Operating System Concepts, Silberschatz,Galvin and Gange 2002
Message passing information from The University of Edinburgh
MPI-2: standards beyond the message-passing model
Lusk, E.;
Massively Parallel Programming Models, 1997. Proceedings. Third Working Conference on
12-14 Nov. 1997 Page(s):43 - 49
Digital Object Identifier 10.1109/MPPM.1997.715960
A multithreaded message-passing system for high performance distributed computing applications
Park, S.-Y.; Lee, J.; Hariri, S.;
Distributed Computing Systems, 1998. Proceedings. 18th International Conference on
26-29 May 1998 Page(s):258 - 265
Digital Object Identifier 10.1109/ICDCS.1998.679521
Lessons for massively parallel applications on message passing computers
Fox, G.C.;
Compcon Spring '92. Thirty-Seventh IEEE Computer Society International Conference, Digest of Papers.
24-28 Feb. 1992 Page(s):103 - 114
Digital Object Identifier 10.1109/CMPCON.1992.186695
An analysis of message passing systems for distributed memory computers
Clematis, A.; Tavani, O.;
Parallel and Distributed Processing, 1993. Proceedings. Euromicro Workshop on
27-29 Jan. 1993 Page(s):299 - 306
Digital Object Identifier 10.1109/EMPDP.1993.336388
Chandras, R. G. 1990. Distributed message passing operating systems. SIGOPS Oper. Syst. Rev. 24, 1 (Jan.
1990), 7-17. DOI= http://doi.acm.org/10.1145/90994.90999