Messages
°
c Department of Computing, Imperial College London Operating Systems II 119/396
Message Passing
Messages are mechanism for Inter-Process Communication
(IPC), transferring information between processes. Suitable for
networked or distributed systems. Three main issues:
How can one process pass information to another.
Make sure that process do not get in each other’s way.
Proper sequencing when dependencies are present.
°
c Department of Computing, Imperial College London Operating Systems II 120/396
Simple Message Primitives
send(P,msg) : Send message msg to process P. If process P
is busy, i.e. has not reached receive yet, the message is
queued. The send operation does not block (suspend) the
sending process, i.e. it continues after sending. This is called
an Asynchronous Send.
receive(P,msg) : Receive message from process P into
variable msg. If no message has arrived from P, i.e. there is
no message in the queue, the receiving process is blocked
Process A Process B
.....
send(B,msg) ... receive (A,msg)
°
c Department of Computing, Imperial College London Operating Systems II 121/396
Servers
Deal with the possibility of potentially multiple senders. Since it is
in general not clear what the source of a message is, this asks for
a different receive primitive
source = receive_any(msg) : Receives a message from
any process into variable msg. The name of the sending
process is returned in source.
Client Processes
Server Process
Process A Q Message Queue
Q .
.......
Q
.....
Process B .. P = receive_any(msg)
......
´
´
´
Process C
°
c Department of Computing, Imperial College London Operating Systems II 122/396
Producer - Consumer Example
.....
Producer .. Consumer
void Producer (void) {
for (;;) {
produce(item); /* generate something to put in buffer */
build_message(m,item); /* construct message to send */
send(Consumer,m); /* send item to Consumer */
} }
void Consumer (void) {
for (;;) {
receive(Prod,m); /* get message containing item */
extract_item(m,item); /* extract item from message */
consume(item); /* Do something with the item */
} }
°
c Department of Computing, Imperial College London Operating Systems II 123/396
Problems with Asynchronous Sends
An Asynchronous Send increases possible parallelism between
sender and receiver, but has some hazards:
Sender continues so can access message variable after
sending, but before it is received.
If message variable was declared within high level language
procedure, it can exit before message received, destroying the
data.
So the OS must provide buffer space.
°
c Department of Computing, Imperial College London Operating Systems II 124/396
Problems with Asynchronous Sends (2)
In fact, the OS copies message from sender’s variable into OS
buffer as part of the implementation of send. This message is
then queued from the OS buffer to the receiver. When receiving
process executes receive, the OS copies the message out of
the buffer into the receiver’s variable and releases the OS buffer
Process A Process B
.. ..
. .
send(B,M1) ..... receive(A,M2)
.. .. .. . .
. . ....
..
.........
. ..
.
...
. .
.
...
...... ......
M1 .. OS Buffer .. M2
°
c Department of Computing, Imperial College London Operating Systems II 125/396
Problems with Asynchronous Sends (3)
If the producer runs faster than the consumer, the OS may run
out of buffers. What to do then?
Block Producer?
Abort Producer?
Crash System?
Messages may be of any length, but the management of
variable sized buffers in OS increases complexity
Fixed Length Messages: Implemented in some OS to reduce
OS buffer management complexity. If sender has a long
message to send, it passes a pointer to variable in sender’s
space rather than the message itself
°
c Department of Computing, Imperial College London Operating Systems II 126/396
Asynchronous Receive
Queue of Messages waiting to be
Destination PCB received: each contains [Link]
® ......
. ¾
......
. ¾
......
.
Mess_Q ª Proc A Proc B
next
next ¼next ¼
void receive(source,mess)
{
if (mess from source in [Link]-Q) {
remove mess from receiver.Mess_Q
return buffer to kernel;
}
else state = waiting; /* for a message from source */
}
°
c Department of Computing, Imperial College London Operating Systems II 127/396
Asynchronous Send
void send(destination,mess)
{
if (destination waiting for message from current) {
copy mess from sender space to destination space;
ready(destination);
}
else if (getbuff(buffer) == FAIL) {
/* get buffer from kernel buffer pool */
error(nobuffers);
}
else {
buffer = mess; /* Save message in buffer */
insert buffer at end of receiver.Mess_Q;
}
/* sender continues */
}
°
c Department of Computing, Imperial College London Operating Systems II 128/396
Producer - Consumer with Flow Control
Empty Buffers
Producer
....... Consumer
.....
...
Message Queue
void Prod (void) {
for (;;) {produce(item); receive(Cons,mess);
build(mess,item); send(Consumer,mess); } }
void Cons (void) {
#define N 100; mess messages[N];
for (i=0;i<N;i++) send(Prod,messages[i]);
for (;;) {receive(Prod,mess); extract(mess,item);
send(Prod,mess); consume(item);
} }
°
c Department of Computing, Imperial College London Operating Systems II 129/396
Server Paradigm
Process A Process B
...... ......
Access resource Server Access resource
via request via request
......J .
.....
.
J J Access code
JJ Synchr. code
JJ
J .J
.
....
. Shared Data .
......
J
Data access and synchronisation code within manager. This is
a sequential program that receives requests, and sends
replies.
Manager is a separate compilation unit and syntactic unit, c.f.
abstract data type or monitor.
°
c Department of Computing, Imperial College London Operating Systems II 130/396
Example: Shared Access to Database
Database under control of one process, the database manager.
Permit multiple readers, but only 1 writer; reading has priority over
writing
There are three process types: Reader, Writer and
DB_Manager; all have direct access to database
PROCESS Reader (void) {
for (;;) {
send(DB_Manager, start_read);
receive (DB_Manager,message); /* wait for ok */
read from database
send(DB_Manager, end_read);
use data
} }
°
c Department of Computing, Imperial College London Operating Systems II 131/396
Writer
PROCESS Writer (void) {
for (;;) {
generate data
send(DB_Manager, start_write);
receive (DB_Manager, message); /* wait for ok */
write database
send(DB_Manager, end_write);
use data
} }
°
c Department of Computing, Imperial College London Operating Systems II 132/396
DB_Manager
PROCESS DB_Manager (void) {
int reader_count = 0;
int writing = FALSE;
for (;;) { source = receive_any(message);
switch (message) {
case start_read:
if (!writing) { send(source,OK);
reader_count += 1; }
else add_to_queue (source, reader_Q);
/* Writer busy, queue Reader */
case end_read:
reader_count -= 1;
if (reader_count==0 & !empty(writer_Q)) {
/* First Writer on queue can write */
source = remove_from_queue(writer_Q);
send(source,OK);
writing = TRUE;
}
°
c Department of Computing, Imperial College London Operating Systems II 133/396
DB_Manager (2)
case start_write:
if (reader_count==0 & !writing) {
send(source,OK);
writing = TRUE; }
else add_to_queue(source, writer_Q); /* DB in use */
case end_write:
writing = FALSE;
if (empty(reader_Q) & !empty (writer_Q)) {
source = remove_from_queue(writer_Q);
send(source,OK);
writing = TRUE; }
else while (!empty(reader_Q)) {
/* all queued Readers continue */
source = remove_from_queue(reader_Q);
send(source,OK);
reader_count += 1;
} } } }
°
c Department of Computing, Imperial College London Operating Systems II 134/396
Server Paradigm (2)
Advantages : .
modularity.
clear interfaces (messages).
mutual exclusion within manager.
Disadvantage : Overheads of message passing.
Implementation scheme :
void Server (void) {
for (;;) {
client = receive_any(request);
perform service request
send(client,reply);
} }
Server process always has exclusive access to its own data, so
mutual exclusion is automatic
°
c Department of Computing, Imperial College London Operating Systems II 135/396
Synchronous Receive
Using this approach, the sender blocks until the message is
received by the receiver. E.g. Occam (the receive primitive
remains unchanged). Notice that:
No OS buffering is required.
More efficient, since the message is copied only once (up to
twice in Asynchronous Send).
This solution allows for less parallelism.
A slow receiver slows the sender down.
Asynchronous Send : No receivers: messages queued.
Synchronous Send : No receivers: senders queued.
For both: receiver is queued if no message is available
°
c Department of Computing, Imperial College London Operating Systems II 136/396
Synchronous Receive: Queue
Queue of PCBs of senders whose
Destination PCB messages are not yet received
® ....... ¾
......
. ¾
......
.
Send_Q ª waiting waiting
proc q
next next ¼ next ¼
void receive(source,mess) {
if (source in [Link]) {
remove PCB from [Link];
copy mess from source ’s to receiver’s space;
ready(source); /* put in Ready Queue
* Message is received, so source can continue */
} else [Link] = waiting; /* for source */
}
°
c Department of Computing, Imperial College London Operating Systems II 137/396
Synchronous Send
void send(destination,mess)
{
if (destination waiting for message from sender) {
copy mess from sender’s to destination’s space;
ready(destination); /* unblock receiver
* blocked on receive and put in Ready Queue.
* Message is received, so sender can continue */
}
else {[Link] = waiting;
/* put sender to sleep, waiting for destination to accept
* message from queue */
insert current at end of destination’s Sender Queue;
} }
°
c Department of Computing, Imperial College London Operating Systems II 138/396
Additional Message Primitives
Time-outs : Can be used for synchronous send and receive
to limit the amount of time spent on waiting.
Looks like: receive(P,msg,time)
Conditional Receive : Allows the choice between receiving a
message only if one is waiting; else continue with other things.
This option permits the receiver to check for a message
without being blocked. This corresponds to polling for input
instead of waiting for interrupt as is the normal case; it’s a
busy wait
Indirect Naming : May be used instead of naming the process
from which a message is received or to which a message is
sent. Sender does not know name of receiver and receiver
does not know name of sender
°
c Department of Computing, Imperial College London Operating Systems II 139/396
Request Reply
Bi-directional communication that uses a combined send and
receive (reply) mechanism.
Synchronous - sender blocks while waiting for reply.
Time-out may be used to limit time for which sender (or
receiver) is blocked.
Receiver continues immediately after sending reply, as can be
guaranteed that the message it received immediately; the
sender was waiting for it.
Sender Process A Receiver Process B
..... receive(M,msg,time)
send-rec(B,req,time).......... ...
. ............. ..
............ .
..... send(A,reply)
°
c Department of Computing, Imperial College London Operating Systems II 140/396
Selective Receive
Select messages from multiple sources. As an alternative to
receive_any; e.g. Ada, Conic.
SELECT
WHEN G1 receive(p1,msg1)
DO ... END
OR
WHEN G2 receive(p2,msg2)
DO ... END
OR
DELAY (50)
END
Other alternatives: ELSE, TERMINATE
°
c Department of Computing, Imperial College London Operating Systems II 141/396
Mailbox
An OS data structure (a queue) independent of both sender and
receiver. Queues hold either processes or messages depending
on which type of communication primitive is being used. Permits
multiple senders and receivers. There may be bounded or
unbounded queues.
Senders Receivers
P1 Q ..... P4
Q .. ´..
Q
..... ´
...... ....... ....... ....... ´ ......
P2 .. .. P5
´..
..... Q
´ Tail Head QQ
.......
´ Mailbox
P3 P6
°
c Department of Computing, Imperial College London Operating Systems II 142/396
Ports or Sockets
Data structure, maintained by kernel, within a process, associated
to another process. The port holds name of source or destination,
and is used to pass messages through. Its name is system-wide
unique, and a process can have more than one port.
Process A Process B
send(pt1,msg) B ......
.. A receive(pt2,msg)
pt1 pt2
Needs a primitive for binding, bind(pt1,B), when binding
between ports and processes is not permanent; places name of
process in pt1 data structure. The OS picks up the name when
the message is sent.
°
c Department of Computing, Imperial College London Operating Systems II 143/396
Example: Mach
A system built as an extension of Accent, used in NeXTStep /
Openstep / Apple’s OS X (Darwin). It provides mailboxes, but
calls them ports. Mailbox provides message buffers (default size
8). Mach supports six basic abstractions for message passing.
task : Execution environment, unit of resource allocation.
thread : The basic unit of execution.
port : A one-way communication channel implemented as a
message queue managed by the kernel.
ports set : A group of ports, treated as a logical unit.
message : A collection of typed data objects used in
communication between threads.
memory object : An object usually residing in secondary
storage.
°
c Department of Computing, Imperial College London Operating Systems II 144/396
Mach (2)
The main outline of the message system is
Ports are data structures maintained by the kernel.
Ports have a system-wide unique name.
A port is not bound permanently to a single task.
A port can have many senders but only one receiver.
A task must have send rights to send to a port.
A task must have receive rights to receive from a port.
A task can have a number of ports at a time.
Messages are of variable length.
°
c Department of Computing, Imperial College London Operating Systems II 145/396
Mach (3)
Ports can be on remote computers - works both within a single
machine and across network. Use message passing to interact
with the Kernel. Message contains:
destination port.
reply port.
size.
operation.
typed data.
ports.
pointer to data segments.
°
c Department of Computing, Imperial College London Operating Systems II 146/396
Mach (4)
Some system calls related to the message mechanism
port_alloc : create port and allocate buffer space.
msg_send : asynchronous Send of message port. If mailbox is
full, sender can
Wait indefinitely until there is room.
Wait at most a number of milli-secs.
Immediate return.
Use temporary Kernel buffer (1 buffer per sending thread) -
thread then continues.
rcv_msg : blocking receive. Can be applied to a set of ports.
rpc_port : sender blocks waiting for a reply on a reply port
sent with the request.
°
c Department of Computing, Imperial College London Operating Systems II 147/396