Synchronous vs. asynchronous message passing

[jal]

Most (if not all) realtime OSes have synchronous message passing (blocking send; probably because of the realtime constraints?), most other OSes seem to use asynchronous message passing (non-blocking send) or a mix (e.g. MS Windows PostMsg vs. SendMsg). What are the reasons to choose one over the other? In which cases would you choose the one or the other? Are there any performance gains using the one or the other? If anyone could enlighten me I'd be much obliged.


JAL

[AndrewAPrice]

Why not support both?

[Candy]

I would say asynchronous, synchronous messaging is like doing stuff in one thread - and if you're doing stuff as if you're running one thread, why not do so?

[jal]

Why not support both?

I could, but I'd like to have a good reason to do so, not just 'because I can'.


JAL

[jal]

I would say asynchronous, synchronous messaging is like doing stuff in one thread - and if you're doing stuff as if you're running one thread, why not do so?

Well, like I said, in RTOSes, synchronous message passing is the rule, if not the only way. And "why not do so" is of course a relatively silly question, as message passing is *I*PC, i.e. between different processes.


JAL

[Solar]

I can only guess, but with "hard" RTOS, it is important that you are able to prove that something doesn't take longer than n, sometimes even more important than making n a smaller number. RTOS is not about doing as many things as possible in parallel, but doing things in a predictable time frame. I could imagine that synchronous IPC helps with that.

But as I said, that's guesswork, as I have touched RTOS technology only in theory (so far).

[Brendan]

Hi,

Most (if not all) realtime OSes have synchronous message passing (blocking send; probably because of the realtime constraints?), most other OSes seem to use asynchronous message passing (non-blocking send) or a mix (e.g. MS Windows PostMsg vs. SendMsg). What are the reasons to choose one over the other? In which cases would you choose the one or the other? Are there any performance gains using the one or the other? If anyone could enlighten me I'd be much obliged.

Synchronous messaging is like a function call, except execution is transfered to code in a different task rather than code in the same task. Asynchronous messaging is more like sending data over a network - the sender keeps running.

For synchronous messaging the message data goes directly from sender to receiver. For asynchronous messaging the message data needs to be stored somewhere inbetween (e.g. in the receiver's message queue). This means that (in general) asynchronous messaging has higher overhead.

However, for asynchronous messaging the sender keeps running. This means that for multi-CPU systems one task can send several messages to several other tasks and keep doing useful work (while other CPUs run the other tasks) until it receives the replies from the other tasks - everything can happen in parallel. For synchronous messaging you'd have to do everything in series - send the first message, wait for reply, send the next message, wait for reply, etc, then do the work you could've done while you were waiting. In general, asynchronous messaging is much better for scalability.

Also, asynchronous messaging can reduce the number of task switches. For example (for a single-CPU system), task A can send 100 messages to task B, then you can do a task switch to task B, task B can process the messages and send 100 replies and then you can do a task switch back to task A. In the same situation with synchronous messaging it'll cost you about 200 task switches.

Lastly, usually asynchronous messaging respects task priorities while synchronous messaging doesn't. For most implementations of synchronous messaging, if a high priority task sends a message to a low priority task then there's an immediate task switch (done as part of sending the message) and the low priority task gets CPU time, even if there's medium priority tasks ready to run.

IMHO asynchronous messaging is much much better. However, asynchronous messaging breaks the way people are used to programming. Because synchronous messaging is like a function call it doesn't make much difference to anyone who's used to procedural programming, but asynchronous messaging can completely change the way you do things (for e.g. using an event loop and state machine, rather than doing step A then step B then step C).

For an example, for synchronous messaging you might do something like:

Code: Select all

main() {
    int result = 0;

    send_FOO();
    send_BAR();

    do_calculation();

    send_FIRST();
    result += message.data;

    send_SECOND();
    result += message.data;

    send_THIRD();
    result += message.data;

    printf("The result was %d\n", result);
}

With asynchronous messaging you might do something like this:

Code: Select all

main() {
    char state_flags = 0;
    int result = 0;

    send_FOO();
    do {
        message = get_message();
        switch(message.ID) {
            case FOO_REPLY:
                send_BAR();
                break;
            case BAR_REPLY:
                send_FIRST();
                send_SECOND();
                send_THIRD();
                do_calculation();
                break;
            case FIRST_REPLY:
                result += message.data;
                state_flags |= 1;
                break;
            case SECOND_REPLY:
                result += message.data;
                state_flags |= 2;
                break;
            case THIRD_REPLY:
                result += message.data;
                state_flags |= 4;
                break;
        }
    } while (state_flags != 7);

    printf("The result was %d\n", result);
}

The asynchronous version looks much more complicated than the synchronous version. However, for the asynchronous version other CPUs can be handling the FIRST, SECOND and THIRD messages while this task is doing "do_calculation()".

To make the sychronous version do the FIRST, SECOND and THIRD messages and "do_calculation()" in parallel, you'd need to do something like:

Code: Select all

volatile result = 0;

main() {
    send_FOO();
    send_BAR();

    threadA = spawn_thread( handle_first );
    threadB = spawn_thread( handle_second );
    threadC = spawn_thread( handle_third );

    do_calculation();

    wait_for_thread_exit(threadA);
    wait_for_thread_exit(threadB);
    wait_for_thread_exit(threadC);

    printf("The result was %d\n", result);
}

handle_first() {
    send_FIRST();
    result += message.data;      // Needs to be atomic (use "LOCK ADD")
}

handle_second() {
    send_SECOND();
    result += message.data;      // Needs to be atomic (use "LOCK ADD")
}

handle_third() {
    send_THIRD();
    result += message.data;      // Needs to be atomic (use "LOCK ADD")
}

This is almost as good as the asynchronous version (it does things in parallel), but now we've got the additional overhead of 3 extra threads and need to deal with re-entrancy. In more complicated code the re-entrancy locking, etc can make things much worse than asynchronous messaging would have.


Cheers,

Brendan

[Candy]

Code: Select all

#include <deferred>

int main() {
    int result = 0;

    deferred<void> foo_call = defer(send, FOO);
    deferred<void> bar_call = defer(send, BAR);

    do_calculation();

    deferred<message> first_call = defer(send, FIRST);
    deferred<message> second_call = defer(send, SECOND);
    deferred<message> third_call = defer(send, THIRD);

    result = first_call->data + second_call->data + third_call->data;

    printf("The result was %d\n", result);
}

Do you like the concept?

[jal]

In general, asynchronous messaging is much better for scalability.

Hadn't thought of that, but good point.

Also, asynchronous messaging can reduce the number of task switches. (...)

True, assuming that sending a message doesn't make you loose your timeslice (because of executing a system call etc.).

Lastly, usually asynchronous messaging respects task priorities while synchronous messaging doesn't. For most implementations of synchronous messaging, if a high priority task sends a message to a low priority task then there's an immediate task switch (done as part of sending the message) and the low priority task gets CPU time, even if there's medium priority tasks ready to run.

Well, in (most?) RTOSes, the thread with the highest priority always runs, and all others not. So to prevent priority stealing (a lower priority task getting all the time when a higher priority task sends a message to an even lower priority task), the lower priority task can be priority boosted, making it all rather complex.

IMHO asynchronous messaging is much much better. However, asynchronous messaging breaks the way people are used to programming. Because synchronous messaging is like a function call it doesn't make much difference to anyone who's used to procedural programming, but asynchronous messaging can completely change the way you do things (for e.g. using an event loop and state machine, rather than doing step A then step B then step C).

Yeah, it does need another mindset, but I can see the advantages. Nice examples.

The asynchronous version looks much more complicated than the synchronous version. However, for the asynchronous version other CPUs can be handling the FIRST, SECOND and THIRD messages while this task is doing "do_calculation()".

'Handling' in a sense that it can put them in the receivers message queue (if it has any, of course). Otherwise the OS has to create a new thread for each message. Possible, but messy to synchronize.

To make the sychronous version do the FIRST, SECOND and THIRD messages and "do_calculation()" in parallel, you'd need to do something like: (...) This is almost as good as the asynchronous version (it does things in parallel), but now we've got the additional overhead of 3 extra threads and need to deal with re-entrancy. In more complicated code the re-entrancy locking, etc can make things much worse than asynchronous messaging would have.

The 3 extra threads may not be a problem, and even an advantage. But having to manually create them, that's a mess.

Thanks for the thorough explanation.


JAL

[Colonel Kernel]

@Brendan: Good summary of the issues there. I generally agree with what you're saying, but I need to nitpick a little.

Lastly, usually asynchronous messaging respects task priorities while synchronous messaging doesn't. For most implementations of synchronous messaging, if a high priority task sends a message to a low priority task then there's an immediate task switch (done as part of sending the message) and the low priority task gets CPU time, even if there's medium priority tasks ready to run.

I have a concrete counter-example to this: QNX. When a higher-priority thread receives a message from a lower-priority thread, it inherits the lower priority until it blocks to receive the next message. This prevents the kind of priority inversion problem you describe.

Also, your code example is interesting for two reasons: It shows the advantages of async messaging in terms of efficiency, while also showing how cumbersome it can be in a language like C. Which brings us to...

@Candy: That looks like a nice implementation of "futures". There are libraries being developed now that are similar, aren't there? Things that may be standardized in the near future? I'm thinking of Intel's Thread Building Blocks in particular...

[Brendan]

Hi,

@Brendan: Good summary of the issues there. I generally agree with what you're saying, but I need to nitpick a little.

Lastly, usually asynchronous messaging respects task priorities while synchronous messaging doesn't. For most implementations of synchronous messaging, if a high priority task sends a message to a low priority task then there's an immediate task switch (done as part of sending the message) and the low priority task gets CPU time, even if there's medium priority tasks ready to run.

I have a concrete counter-example to this: QNX. When a higher-priority thread receives a message from a lower-priority thread, it inherits the lower priority until it blocks to receive the next message. This prevents the kind of priority inversion problem you describe.

That sounds like it'd make things much worse. If a high priority thread (e.g. a network card driver) is sent a message from a very low priority thread, then it becomes very low priority and might not get any CPU time because it's very low priority; and (assuming rendezvous messaging) all other threads that are trying to send messages to the high priority thread block.

I'm wondering if you've got this around the wrong way - for e.g. when a lower-priority thread receives a message from a higher-priority thread, it inherits the higher priority until it blocks to receive the next message. This would work in the context of synchronous messaging, but I want to do things like have a text editor that sends a "document was modified" message to a low priority spell checking thread (which does spell checking in the background when the CPU isn't busy and sends a "no errors" reply or a "this word is wrong" reply).

Also, your code example is interesting for two reasons: It shows the advantages of async messaging in terms of efficiency, while also showing how cumbersome it can be in a language like C. Which brings us to...

Hehe - you should see how much fun it is in assembly..

@Candy: That looks like a nice implementation of "futures". There are libraries being developed now that are similar, aren't there? Things that may be standardized in the near future? I'm thinking of Intel's Thread Building Blocks in particular...

I think Intel's implementation uses the equivelent of "pthread_create()" and "pthread_join()", rather than "send_message()" and "wait_message()" - something that abstracts lower level thread management, rather than something that abstracts IPC.


Cheers,

Brendan

[Colonel Kernel]

That sounds like it'd make things much worse. If a high priority thread (e.g. a network card driver) is sent a message from a very low priority thread, then it becomes very low priority and might not get any CPU time because it's very low priority; and (assuming rendezvous messaging) all other threads that are trying to send messages to the high priority thread block.

I'm wondering if you've got this around the wrong way - for e.g. when a lower-priority thread receives a message from a higher-priority thread, it inherits the higher priority until it blocks to receive the next message. This would work in the context of synchronous messaging, but I want to do things like have a text editor that sends a "document was modified" message to a low priority spell checking thread (which does spell checking in the background when the CPU isn't busy and sends a "no errors" reply or a "this word is wrong" reply).

I think priority inheritance actually works both ways, although you're partly right -- the example I gave was the opposite of the example that is normally given. The problem of high-priority clients blocking on a low-priority server is something that servers have to be designed to deal with -- specifically, by having more than one thread available to handle requests. Messages in QNX are not sent to specific threads, they are sent to "channels". Each channel can have multiple sending or receiving threads blocked on it at a time.

I think Intel's implementation uses the equivelent of "pthread_create()" and "pthread_join()", rather than "send_message()" and "wait_message()" - something that abstracts lower level thread management, rather than something that abstracts IPC.

It may use pthreads under the hood, but the abstractions are what count. I can easily imagine retrofitting the "futures" abstraction on top of the async messaging system you have in BCOS.

After all, threading is really just a performance hack... Ideally, everything should be in a separate, isolated process, and thus all "lower level thread management" would be synonymous with IPC.

[Candy]

I think Intel's implementation uses the equivelent of "pthread_create()" and "pthread_join()", rather than "send_message()" and "wait_message()" - something that abstracts lower level thread management, rather than something that abstracts IPC.

It may use pthreads under the hood, but the abstractions are what count. I can easily imagine retrofitting the "futures" abstraction on top of the async messaging system you have in BCOS.

After all, threading is really just a performance hack... Ideally, everything should be in a separate, isolated process, and thus all "lower level thread management" would be synonymous with IPC.

Threading is the explicit way of programming what should've been parallel in the first place. The best way of using that is not by loading the programmer with figuring out what should be done in parallel but letting the support libraries figure out how to best parallellise the code that the programmer's written. The ideal way to do that is for the programmer to indicate what can be postponed until later allowing it to be run in a different thread. The threading should be completely encapsulated and not exposed to the user at all.

[Colonel Kernel]

Threading is the explicit way of programming what should've been parallel in the first place. The best way of using that is not by loading the programmer with figuring out what should be done in parallel but letting the support libraries figure out how to best parallellise the code that the programmer's written. The ideal way to do that is for the programmer to indicate what can be postponed until later allowing it to be run in a different thread. The threading should be completely encapsulated and not exposed to the user at all.

My point was that ideally, threading in the presence of shared mutable state should never have been allowed. Even with "futures", you still have to protect concurrent access to shared memory.

[jal]

My point was that ideally, threading in the presence of shared mutable state should never have been allowed. Even with "futures", you still have to protect concurrent access to shared memory.

So basically, you don't threads are a good idea at all? Only processes? That is possible of course, but creates a big overhead. Any shared information, even when never touched the same time, must be passed along via messages or the like.


JAL