Message Passing Tutorial
It's always a problem to decide if you use asynchronous or synchronous message passing. In this article I'll show you how to have both. I'll use a pseudo-code to describe the algorithm, so you can implement it to your language environment. Note that I refer sender and receiver as processes, it can be easily adopted to threads.
Definitions
You should have a structure to be sent to another thread. I'll refer this as the message, and I assume you have these fields:
struct message {
src //the source process that sends the message
dst //the destination process that receives
body //the body of the message (usually holds type and arguments, it's up to you)
}
Sending and receiving must be atomic. This means you must prevent task switches until it's finished. I have two different timer in my OS, one for the wallclock, and another for preemption. So for me this means masking the latter, and reenabling it at the end. You could also use a mutex or semaphore to accomplish mutual exclusion.
Blocking and non blocking: sender can be blocked upon send, but not necessarily. Receiver must block if there's no message waiting. Blocking means the OS will remove the process from ready queue, and won't allocate CPU resource for it until the blockade canceled. When it happens, it simply puts back the process to ready queue (most likely to the top), so next time it gains CPU, it can run. Processes on the blocked queue will not use any CPU. This saves you from busy loop.
Now a few words on synchronization: if it's asynchronous, it means sender is not interested whether receiver accepts message or not. It will send the message and move on (won't block). This also means message could be lost. On the other hand synchronous sender will wait (block) until the message is delivered, this creates a randezvous point (so sender process and receiver process will run synchronized after message accepted).
Finally, circular buffer. It's a FIFO (First In, First Out) buffer. It's implemented by pointers (or indeces) head and tail. If you push something in a FIFO, it will be stored at the memory pointed by head, and head will be adjusted. On pop, item will be read from memory pointed by tail, and tail will be adjusted. If head or tail reaches the end of the buffer, they will wrap around.
struct circbuff {
int head; //index to queue start within buffer
int tail; //index to queue end within buffer
int count; //number of elements in buff
message buffer[MAXITEMS]; //buffer to hold messages
}
You could calculate the number of items in buffer by head-tail, but as being circular, there's a special case which cannot be handled without a count variable: head will be equal to tail if buffer is empty, and also when it's full.
Asynchronous
Sending
Now let's start with sending a message, and not care about. This could lead to loosing a message, which we can't afford, so we'll do a trick here. Despite of being asynchronous, we will block if receiver buffer is full, and we'll continue only after there's space for our message.
void async_send(msg)
{
disable_task_switch();
msg.src=current_process; //we must not rely on it's set
tmpbuff=map_buffer(msg.dst); //temporarily map destination's buffer into sender process' address space
if (tmpbuff.count==MAXITEMS) { //if receiver buffer is full, block
pushwaitqueue(msg.dst,current_process); //record this process in dst's sender queue
block(current_process);
}
push(tmpbuff,msg);
if(isblocked(msg.dst)) awake(msg.dst); //if destination process is blocked for receiving, awake it
unmap_buffer();
enable_task_switch();
}
Receiving
Doesn't matter whether it's synchronized or not, receiver must block if it's message queue is empty, and there's nothing to process.
circbuff buff;
message async_recv()
{
message tmp=NULL;
disable_task_switch();
if (buff.count==0) block(current_process); //if there's nothing to get, block
tmp=pop(buff);
while(topwaitqueue()!=NULL) awake(popwaitqueue()); //awake blocked processes waiting to send
enable_task_switch();
return (tmp);
}
It's possible that under very rare circumstances you want a non-blocking receive that returns NULL if there's no message waiting. I highly discourage, because it leads to a polling busy loop, but just in case, here you are:
message async_recvpoll()
{
message tmp=NULL;
disable_task_switch();
if (buff.count!=0) tmp=pop(buff);
enable_task_switch();
return (tmp);
}
Note that we count on recv being blocking to implement synchronous transfer. If you use the non-blocking code above, you'll have to take care of that of your own.
Synchronous
Sending
Okay, now that we have primitives for asynchronous sending and receiving, it's rather easy to implement synchronous transfer on top of them.
message sync_send(msg)
{
async_send(msg); //we send the message
return(async_recv()); //and we block waiting for the response
}
Receiving
Likewise,
message consume(message); //function to do something with the message
void sync_recv()
{
message tmp;
tmp=async_recv(); //wait for a message to arrive
tmp=consume(tmp); //process the message and return a response message
async_send(tmp); //send it back to the caller
}
What is this good for?
Synchronous messaging is often used to implement Remote Procedure Calls. You send the function code and it's arguments first, then consume() calls the appropriate function and creates a message with the results.
Most OS use some primitive messaging to implement more sophisticated IPC like pipes or sockets. Reading and writing from files is also worked out by sending messages between the vfs process and the disk driver.
Pitfalls
This seem to be easy, but don't forget it's a tutorial. In real world, you'll have to work a lot before your messaging code became useful. Some ideas:
- check if receiver is truly want to receive from sender.
- always check for loops: process A waiting for B to send, C waiting for A. Now it would be a disaster if B also waits for C.
- you should implement an alarm for sending. If delivering fails within a timeout, you should check the reasons, and maybe resending.
- you should have an unique id in every message to detect retransmission.
- normally userspace applications never have to receive messages without sending an acknowledge. So it's a good idea to tie asynchronous messaging to a capability flag or something similar.
- you should have a matrix of process ids recording who is allowed to send message to who. An application should never send message to a driver process directly (only through a library or system call).
See Also
Articles
Threads
External Links
- Message Passing on Wikipedia
- How do I implement curcular buffer in C?
- This is how Minix does message passing (see functions mini_send, mini_receive well documented).