The posted message queue vs the input queue vs the message queue

Raymond Chen

Raymond


There are multiple ways of viewing the interaction between
posted messages and input messages.
MSDN prefers to view posted messages and input messages as
part of one giant pool of messages in a message queue,
with rules about which ones get processed first.
I, on the other hand, prefer to think of posted messages and
input messages as residing in different queues that are
processed in sequence.



By analogy, consider a business with a policy that
loyalty program members are served ahead of
regular customers.



One way of organizing this is to form a single queue,
but sorting them so members go to the front.
To call the next person in line, you just take whoever
is at the head of the queue.



AddToQueue(Customer c)
{
if (c is a member and the queue contains non-members) {
let n = the first non-member in the queue;
insert c in front of n;
} else {
insert c at the end of the queue;
}
}

GetNextCustomer()
{
if (there is somebody in the queue) {
return the first person in the queue;
}
// nobody is waiting
return null;
}



This approach works fine from a programmatic standpoint,
but people might not like it when they see others cutting
in front of them.
You might therefore choose to create two queues,
one for members and one for non-members:



AddToQueue(Customer c)
{
if (c is a member) {
insert c at end of member queue;
} else {
insert c at end of non-member queue;
}

GetNextCustomerInLine()
{
if (there is somebody in the member queue) {
return the first person in the member queue;
}
if (there is somebody in the non-member queue) {
return the first person in the non-member queue;
}
// nobody is waiting
return null;
}



Note that this second algorithm serves customers in exactly
the same order; the only difference is psychological.
Customers might resent the presence of a members line
since it reminds them that other people are getting
special treatment.
Or this algorithm may not be practical because
you don’t have room in your lobby for two lines.
You might choose yet another algorithm,
where you select members
at the time the customers
are served rather than when they arrive.
Everybody forms a single queue, but sometimes
a customer in the middle of the queue gets pulled out
for special treatment.
(Maybe they wear red hats so they are easy to spot.)



AddToQueue(Customer c)
{
insert c at end of queue;
}

GetNextCustomerInLine()
{
if (there is a member in the queue) {
return the first member in the queue;
}
// else only non-members remaining
if (there is somebody in the queue) {
return the first person in the queue;
}
// nobody is waiting
return null;
}



(Some banks use a variant of this algorithm
to

separate potential bank-robbers from the rest of the customers
.)



From the standpoint of determining
who gets served in what order,
all of these algorithms are equivalent.
One may be more efficient,
one may be easier to understand,
one may be easier to maintain,
one may be easier to debug,
but they all accomplish the same thing.



So go ahead and use whatever interpretation of the message queue you like.
They are all equivalent.



But the interpretation that I use is the one I presented

several years ago at the PDC
,
where the posted message queue and input queues are
considered separate queues.
I prefer that interpretation because it makes input queue attachment
easier to understand.



In the analogy above, I prefer viewing things in terms of the
second algorithm, with separate queues;
MSDN prefers viewing things in terms of the third algorithm,
with a single queue, but with some messages given preferential
treatment over others.



But as I’ve already noted, the outputs of the algorithms are the
same given the same inputs,
so it doesn’t matter how they are implemented internally,
since all you can observe as a program are the inputs and outputs.
It’s like the

multiple interpretations of quantum mechanics
:
They all attempt to describe the world from a particular viewpoint,
but at the end of the day, the world simply is,
and a description is just a description.




Next time, we’ll explore some consequences of the interaction
between posted messages and input messages.

Raymond Chen
Raymond Chen

Follow Raymond   

0 comments

Comments are closed.