When you share an input queue, you have to wait your turn


Now that we've had a quick introduction to asynchronous input, let's look at some of the details. Remember, this is a peek under the hood at how the sausage is made. The algorithm described here is not part of the API contract and it can change at any time, as long as it services the overall goal of serializing input.

Let's start by looking at how things worked in the 16-bit world. Even though 16-bit Windows didn't use the term thread (since each application was single-threaded), I will still use the term since that makes the transition to the 32-bit world more straightforward.

As a point of terminology, I say that a message belongs to a thread if the message targets a window which belongs to that thread. Equivalently, the thread owns the message.

Now, the goal is to dispatch input messages in chronological order: Only the thread which owns the next input message can retrieve it. All other input must wait their turn to come to the front of the input queue.

In 16-bit Windows, all input gets added to a system-wide input queue, and the basic algorithm used by Peek­Message and Get­Message for retrieving messages from the input queue goes like this.

  • Look at the first message in the input queue:
    • If the message belongs to some other thread, then stop. Return no message to the caller.
    • Otherwise, return the message we found.
  • If there are no messages in the input queue, then there is no input. Return no message.

All the rest is tweaking the boundary cases.

For example, suppose there are two input messages in the input queue, message 1 for thread A, and message 2 for thread B. Thread A calls Get­Message, and the above algorithm returns message 1 to thread A, at which point the new "first message" is message 2, and if thread B calls Get­Message, it will get message 2.

The catch is that according to the above algorithm, thread B can be told about message 2 before thread A has finished processing message 1. You've introduced a race condition that breaks the rule that input is processed sequentially: Thread B can race ahead of thread A and start processing message 2 before thread A can even get started processing message 1.

To fix this, we add a new state to the input queue that says "Yea, I just gave somebody an input message, and I'm waiting for that thread to finish processing it before I will hand out another input message."

  • (New!) If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
  • (New!) If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting. (We finished processing it and have come back for more!)
  • Look at the first message in the input queue:
    • If the message belongs to some other thread, then stop. Return no message to the caller.
    • Otherwise, (New!) mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
  • If there are no messages in the input queue, then there is no input. Return no message.

Okay, we fixed a race condition. But now there's a new problem: Suppose thread A retrieves an input message (and therefore puts the input queue into the "waiting for thread A" state), and then thread A sends a message to thread B, and thread B wants to display a dialog box or a menu. According to the rules as we have them so far, we would have a deadlock: That Send­Message call will not return to the first thread until the modal UI is complete, but the modal UI cannot complete because the input queue is waiting for thread A to finish processing the input message.

The fix for this special case is that if a thread asks for an input message, and it is handling an inbound Send­Message, then the input queue declares that any in-progress input message has finished processing. One way of interpreting this rule is to say, "If a thread sends a message to another thread, then that implicitly completes input processing."

  • (New!) If the input queue is waiting for another thread to finish processing an input message, and the current thread is processing an inbound sent message, then mark the input queue as no longer waiting.
  • If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
  • If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting.
  • Look at the first message in the input queue:
    • If the message belongs to some other thread, then stop. Return no message to the caller.
    • Otherwise, mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
  • If there are no messages in the input queue, then there is no input. Return no message.

Recall that you are allowed to pass a message range filter and a window handle filter to the Peek­Message and Get­Message functions. The above algorithm was developed on the assumption that there was no message retrieval filter. First, let's add the message range filter to the algorithm:

  • If the input queue is waiting for another thread to finish processing an input message, and the current thread is processing an inbound sent message, then mark the input queue as no longer waiting.
  • If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
  • If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting.
  • Look at the first message in the input queue which satisfies the message range filter (New!):
    • If the message belongs to some other thread, then stop. Return no message to the caller.
    • Otherwise, mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
  • If there are no messages in the input queue which satisfy the message range filter (New!), then there is no input. Return no message.

That wasn't so hard. If you pass a message range filter, then we care only about messages that pass the filter in determining which one is "at the head of the input queue". Without this additional rule, you wouldn't be able to "peek into the future" to see if, for example, there is a mouse message in the input queue sitting behind the keyboard message that is at the front of the input queue.

Adding the window handle filter is a little trickier, because we still want to let input be processed in order (among messages which satisfy the message range filter).

  • If the input queue is waiting for another thread to finish processing an input message, and the current thread is processing an inbound sent message, then mark the input queue as no longer waiting.
  • If the input queue is waiting for another thread to finish processing an input message, then stop and return no message.
  • If the input queue is waiting for the current thread to finish processing an input message, then mark the input queue as no longer waiting.
  • Look at the first message in the input queue which satisfies the message range filter and (New!) either belongs to some other thread or belongs to the current thread and matches the window handle filter.
    • If the message belongs to some other thread, then stop. Return no message to the caller.
    • Otherwise, mark the input queue as waiting for the current thread to finish processing an input message, and return the message we found.
  • If no such message exists, then there is no input. Return no message.

In other words, the window handle is used to control which message is ultimately retrieved, but it does not let you deny another thread access to input which matches the message range filter.

Whew, that's how 16-bit Windows dispatched input.

How do we port this to 32-bit Windows and asynchronous input?

First, we give each thread group its own input queue, rather than having a single system-wide input queue.

Second, whenever the above algorithm says the input queue, change it to say the calling thread's input queue.

And that's it!

In the absence of thread attachment, each thread has its own input queue, so most of the above rules have no effect. For example, You will never see a message that belongs to another thread, because messages that belong to other threads go into those other threads' input queues, not yours. You will never find that your input queue is waiting for another thread, because no other threads have access to your input queue. In the case where there is only one thread associated with an input queue, the algorithm simplifies to

  • Return the first message in the input queue that satisfies both the message range filter and the window handle filter, if any.

It's only if you start attaching threads to each other that you have multiple threads associated with a single input queue, and then all these extra rules start to have an effect.

Next time, we'll explore some of the consequences of synchronous input by writing some poorly-behaving code and observing how the system responds. Along the way, we'll discover an interesting paradox introduced by the above algorithm.

Exercise: The alternative interpretation I gave above does not match the description of the rule, because the rule allows any thread processing an inbound Send­Message to clear the input queue's wait state. Why does the actual rule permit any thread clear the wait state, instead of first checking that the inbound Send­Message is coming from the thread that the input queue is waiting for?

Comments (15)
  1. laonianren says:

    I'm confused.  16-bit Windows was coöperatively multi-tasked, so how can thread B retrieve the next message if thread A is still busy?

    Thread A can yield control by calling GetMessage or SendMessage but in both of these cases the algorithm explicitly unblocks the input queue.

    Under what circumstance can thread B be executing yet fail to retrieve an input message because thread A is still busy processing one?

    [If you call PeekMessage with a filter that excludes all input, then the "retrieve messages from the input queue" code is never entered and the input queue remains locked. I didn't make that part clear in the article, sorry. -Raymond]
  2. Brian_EE says:

    @laonianren: When ThreadA explicitly calls Yield() periodically while performing a computing intensive task in order to be nice to the rest of the system.

  3. foo says:

    > Why does the actual rule permit any thread clear the wait state, instead of first checking that the inbound Send­Message is coming from the thread that the input queue is waiting for?

    As long as you have absolutely no follow-up questions, I would answer: "to avoid deadlock?"

  4. John Doe says:

    @foo, yes, but a specific deadlock.

    If you're processing a sent message that made you enter a modal dialog or pop-up menu, you have to handle input messages. You can only handle them if PeekMessage or GetMessage get input messages within SendMessage, or more properly, within the not-yet-finished processing of a sent message.

    Otherwise, the modal dialog or pop-up menu would not react to input. If you require user action to close a modal dialog or pop-up menu (Esc, the X button, selecting a menu item, a shortcut, etc), then your application would freeze.

    However, the OS would not freeze, you're yielding at PeekMessage or GetMessage.

  5. Joshua says:

    C# 5's new asynchrony keywords hypothetically make it possible to launch modal dialog boxes without a blocking nested message loop. For instance, you could do something like this:

    var result = await MessageBox.ShowAsync(…);

    My only question is, why isn't the WPF team looking into things like this?

    [Not really. The MessageBox class will still presumably have a window procedure, and if a message handler wants to await something, it will have to capture a continuation which includes a foreign stack, which violates the everybody needs to be in on the joke rule. -Raymond]
  6. Joshua: It is my understanding that async/await is merely a task-based implementation of threading that generates a state machine at compile-time, and that UI operations (such as msgbox) usually are performed on the main thread. At least, that is true for Win32 and Windows Forms, as far as I'm aware. WPF may have changed this.

  7. Jerome says:

    @Michael Burgwin

    Joshua's argument still holds. There's nothing stopping you implementing your "asynchronous wait" however you like, wrapping Show or ShowDialog, and then when you're done, switch back to the GUI ExecutionContext (via an abstraction using TaskSchedulers). At the end, it will just end up doing a PostMessage back to the GUI thread of course, but along the way you can be on the ThreadPool, or using your own threads, however you implement it. I've done something similar in Winforms.

    Not sure how relevant this is though.

  8. Jerome says:

    Oops. Writing nonsense… ExecutionContext should have been SynchronizationContext

  9. Neil says:

    Let's say that we're running Win16, and applications A and B use libraries L and M respectively that create windows W and X respectively that handle private messages. Since we know the message is private, both libraries used WM_USERFIRST for the message number. Now if library L tries to peek for WM_USERFIRST in window W, application A will actually yield to application B because library M previously posted a WM_USERFIRST message to window X. If instead the libraries had used registered (i.e. different) window messages then this wouldn't have happened. Subtle!

    [Not sure what you're getting at here. WM_USER is not an input message so the input queue code never runs. If Library L tries to peek for a message for window W, it may or may not yield to window X (depending on PM_NOYIELD), but the message number is irrelevant. -Raymond]
  10. Allgaeuer says:

    I don't understand why the addition of the message range filter to the algorithm is in consistent with the goal of serializing input.

    Suppose we have Thread A and Thread B. They are attached. In the input queue, there is Message 1(Addressed to Thread A and of Type X), Message 2(Addressed to Thread B and of Type X) and Message 3(Headed to Thread A and of Type Y).

    Now Thread A asks of a new Message of Type Y.

    The algorithm will check Message 1 => wrong Type. Message 2 => Wrong address. Message 3 => BINGO.

    Now the algorithm will check if the message belongs to some other thread: Nope!

    The message will be returned.

    In this case, Thread A bypasses Message 2 for Thread B.

    Shouldn’t the "either belongs to some other thread or belongs to the current thread and" added already at the point of adding the message range filter to the algorithm?

    [This is okay because thread A said, "Ignore messages of type X. I'm interested only in messages of type Y, even if there is a message of type X that is higher priority." (This happens a lot. For example, peeking ahead to see if the ESC key has been pressed while processing a mouse drag operation. It is the way you "peek into the future".) The serialization then occurs only among messages of type Y. -Raymond]
  11. Joshua says:

    Hmmm. Who is this other Joshua. I don't know a way to do it for MessageBox, but for all other modal dialogs, CreateDialogBox can launch them without stacking a second message loop.

    [There is no second message loop, but there is a second message procedure and therefore some frames out of your control if you decide to go async inside a message handler. -Raymond]
  12. John says:

    > Why does the actual rule permit any thread clear the wait state

    To avoid a deadlock that involves another thread that in response to the first send message sends a message to a 3rd thread.

    Why isn't this rule revised for 32-bit? Shouldn't the state change happen when SendMessage is called?

    [The case of the forwarded message is the deadlock I had in mind. What if you are sending a message to another thread and that thread does not request input? For example, you may simply have sent LB_ADDSTRING to add an item to a list box. You don't want to clear the input state yet. -Raymond]
  13. John says:

    > You don't want to clear the input state yet

    But do I want to clear the input state if the sent message was sent by a thread that not related and does not share the same input queue?

    [If it doesn't share the same input queue, then your queue is (probably) not locked, so the unlock is harmless. Yes, there is a small hole here, but the question is whether closing it is worth the complexity and introducing a silent breaking change. -Raymond]
  14. Neil says:

    Sorry, I had failed to make the distinction of the input queue.

  15. Jo says:

    I am missing some info. Can anyone please correct me?

    But If one thread includes a message filter and chooses to see only selected messages, Will it block other threads while leaving unprocessed messages? Using this algorithm "Look at the first message in the input queue and If the message belongs to some other thread, then stop. Return no message to the caller." . The other threads without a message filter always see the unprocessed message that is addressed to the thread which has a filter in the front of the queue.

    [This is exactly the subject of tomorrow's article, alluded to at the end of the article. -Raymond]

Comments are closed.

Skip to main content