Message Passing Tutorial: Difference between revisions
Jump to navigation
Jump to search
| [unchecked revision] | [unchecked revision] |
Content deleted Content added
| Line 1: | 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. |
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 == |
== Definitions == |
||
You should have a structure to be sent to another |
You should have a structure to be sent to another process. I'll refer to this as the message, and I will assume you have these fields: |
||
<source lang="c"> |
<source lang="c"> |
||
struct message { |
struct message { |
||
| Line 9: | Line 9: | ||
} |
} |
||
</source> |
</source> |
||
Sending and receiving must be atomic. This means you must prevent task switches until it's finished. I have two different |
Sending and receiving must be atomic. This means you must prevent task switches until it's finished. I have two different timers 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 |
Blocking and non blocking: the sender can be blocked upon sending a message, but this does not necessarily have to be so. The 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 resources for it until the blockade is cancelled. When it happens, it simply puts the process back into the ready queue (most likely to the top). Processes on the blocked queue will not use any CPU time. This prevents a [[busy loop]]. |
||
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 (will be required by the tutorial): |
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): |
||
<source lang="c"> |
<source lang="c"> |
||
block(processid) //function to block a process |
block(processid) //function to block a process |
||
| Line 23: | Line 23: | ||
</source> |
</source> |
||
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, messaging is unreliable. On the other hand synchronous sender will wait (block) until the message is delivered, this creates a |
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 rendezvous point (so the sender process and the receiver process will run synchronized after the message is accepted). Also because the sender knows when and if the message has arrived, it's a reliable messaging system. |
||
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. |
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. |
||
<source lang="c"> |
<source lang="c"> |
||
struct circbuff { |
struct circbuff { |
||
| Line 34: | Line 34: | ||
} |
} |
||
</source> |
</source> |
||
You could calculate the number of items in buffer |
You could calculate the number of items in the buffer using the head and tail variables, but as being circular, there's a special case which cannot be handled without a count variable: head will be equal to tail if the buffer is empty, and also when it's full. |
||
== Asynchronous == |
== Asynchronous == |
||