Objects contained in a multiprocessing.Queue object are not comming out
of the queue in the same order as they went in. For instance, if I put
in object1, object2 and object3 in this very time sequence from multiple
processes, they can end up comming out of the queue as object2, object1
then object3 instead of the original order.

When using the threading module instead of multiprocessing everything is
fine.

The provided test script adds strings to the queue with timestamps.
These messages are not ordered by timestamp when they are printed. This
is an output of the test script with format "[pid@time] message":

[2120@00406] Got lock
[2120@02424] Released lock
[2121@02426] Got lock
[2121@04439] Released lock
[...]
[2121@16459] Released lock
[2120@16461] Got lock
[2121@18464] Got lock
[2120@18462] Released lock
[2121@20466] Released lock

Using print to print the message immediatly prints the messages in the
right order.

See this mailing-list thread for details:
http://groups.google.com/group/comp.lang.python/browse_thread/thread/11a5c4ce4ff4382d/033dcd3607eacbf9

Tested using Python 2.6.1 on Mac OS 10.5 and Linux 2.6.26

Rather than providing strict ordering of Queue input/output, perhaps a
separate or derived class (PriorityQueue?) should be provided just for
that matter (heapq-based?).

The Queue module design should be followed as closely as possible.  It
provides FIFO order as the default, with options for LIFO and priority
order.

I agree, at very least it should provide the same default behavior that 
Queue does, however, it is not obvious to me how to resolve this in 
mp.Queue

That's why I was suggesting to leave Queue as it is and provide a
separate PriorityQueue. With a PriorityQueue the user is free to put
(timestamp, object) tuples in it if he wants a strict chronologic
ordering. He can also use sequence numbers instead of timestamps, etc.

Jesse, can you explain the cause of the bug?  Maybe that will inspire
someone to come up with an idea for a fix.

As a note to myself: adding a simple print to the multiprocessing.Queue 
put method, I can see the calls occurring from the children in order, 
for example:

obj:  0.025193 [proc1] Got lock
obj:  0.227725 [proc1] Released lock
obj:  0.228401 [proc2] Got lock
obj:  0.430501 [proc2] Released lock
obj:  0.431082 [proc0] Got lock
obj:  0.633048 [proc0] Released lock
obj:  0.633723 [proc4] Got lock
obj:  0.835692 [proc4] Released lock
obj:  0.836262 [proc3] Got lock
obj:  1.038197 [proc3] Released lock
obj:  1.038753 [proc1] Got lock
obj:  1.239288 [proc1] Released lock
obj:  1.240079 [proc2] Got lock
obj:  1.440773 [proc2] Released lock
obj:  1.441577 [proc0] Got lock
obj:  1.642142 [proc0] Released lock
obj:  1.642959 [proc4] Got lock
obj:  1.843331 [proc4] Released lock
obj:  1.844178 [proc3] Got lock
obj:  2.044549 [proc3] Released lock

Also attaching the process-based script

On a put to the queue, the object is appended onto a deque (self._buffer) 
- this buffer is managed by a thread (_start_thread) which is handed the 
_feed method as the target. I suspect the bug is actually in the _feed 
method.

I think it would be nice to update the documentation if this isn't
resolved yet. The patch adds a warning that FIFO behavior is not
guaranteed.

I just got surprised by this, and I agree that updating the doc would be nice, because as of now, it states quite explicitly that "the Queue and JoinableQueue types are multi-producer, multi-consumer FIFO queues".

Updated doc patch

Are you sure this needs to be a warning?  We try to use them very sparingly.

(Also note the 3-space indent for reStructuredText markup.)