972
edits
Message Passing Tutorial: Difference between revisions
m
Bot: Replace deprecated source tag with syntaxhighlight
| [unchecked revision] | [unchecked revision] |
No edit summary |
m (Bot: Replace deprecated source tag with syntaxhighlight) |
||
| (8 intermediate revisions by 4 users not shown) | |||
Line 1:
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
<
struct message {
src //the source process that sends the message
Line 8:
body //the body of the message (usually holds type and arguments, it's up to you)
}
</syntaxhighlight>
Sending and receiving must be atomic. This means you must prevent task switches until it's finished. I have two different
Blocking and non blocking: the sender can be blocked upon
You should maintain a queue for every process to record blocked waiting processes. This queue must not be a circular buffer, you can implement it as a simple chained list. I assume you have written the following functions already (they will be required by the tutorial):
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).▼
block(processid) //function to block a process
awake(processid) //function to unblock a process
isblocked(processid) //returns true if process is blocked
pushwaitqueue(recvpid,sendpid) //put sendpid on recvpid process' sender waiting queue
topwaitqueue() //get the last pid in queue
popwaitqueue() //get the last pid in queue and remove it from queue
</syntaxhighlight>
▲Now a few words on synchronization: if it's asynchronous, it means the sender is not interested whether the receiver accepts the message or not. It will send the message and move on (won't block). This also means the message could be lost, hence messaging is unreliable. On the other hand, a synchronous sender will wait (block) until the message is delivered, this creates a
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.▼
▲<source lang="c">
▲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 to by head, and head will be adjusted. On pop, the item will be read from the memory pointed to by tail, and tail will be adjusted. If head or tail reaches the end of the buffer, they will wrap around.
<syntaxhighlight lang="c">
struct circbuff {
int head; //index to queue start within buffer
Line 23 ⟶ 33:
message buffer[MAXITEMS]; //buffer to hold messages
}
</syntaxhighlight>
You could calculate the number of items in the buffer
== Asynchronous ==
===Sending===
Now let's start with sending a message, and not care about. This could lead to
<
void async_send(msg)
{
Line 43 ⟶ 54:
enable_task_switch();
}
</syntaxhighlight>
===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()
Line 58 ⟶ 69:
return (tmp);
}
</syntaxhighlight>
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);
while(topwaitqueue()!=NULL) awake(popwaitqueue());
}
enable_task_switch();
return (tmp);
}
</syntaxhighlight>
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
== 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)
{
Line 80 ⟶ 95:
return(async_recv()); //and we block waiting for the response
}
</syntaxhighlight>
=== Receiving ===
Likewise,
<
message consume(message); //function to do something with the message
void sync_recv()
Line 92 ⟶ 107:
async_send(tmp); //send it back to the caller
}
</syntaxhighlight>
==What is this good for?==
Synchronous messaging is often used to implement [[RPC|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 [[Unix Pipes|pipe]]s or [[socket]]s. Reading and writing from [[file]]s is also worked out by sending messages between the vfs process and the disk driver.
==Pitfalls==
This may seem to be easy, but don't forget it's only a tutorial. In the real world, you'll have to work a lot before your messaging code can became useful. Some
* check
* 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
* 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
==See Also==
| |||