python multiprocessing shared queue re-ordering

Question

I have a server and several clients. They all share a task and results multiprocessing.Queue. However whenever a client finishes a task and puts result on results queue, I want the server to look at the results, and based on that, re-order the tasks queue.

This means of course popping everything off the tasks queue and re-adding. During this re-ordering process, I want the clients to block touching the tasks queue. My question is how I get the server to recognize when a task is added to the results queue and react by locking the tasks queue and reordering while protecting the queue. The invariant is that the server must re-order after every result returned before clients get a new task.

I suppose a simple (but wrong) way would be to have a multiprocessing.Value act as a boolean and whenever a result is added the client flips that to True, meaning a result has been added. The server could poll to get this value but ultimately it could miss another client coming in between polls and adding another result.

Any thoughts appreciated.

** The 'multithreading' tag is just because its very similar thought as in threading, I don't think the process/thread distinction here matters much.

Answer 1

Let's try some code - some progress is better than none ;-) Part of the problem is to ensure that nothing gets taken from the task queue if the result queue has something in it, right? So the queues are intimately connected. This approach puts both queues under the protection of a lock, and uses Conditions to avoid any need for polling:

Setup, done in server. taskQ, resultQ, taskCond and resultCond must be passed to the client processes (lock need not be explicitly passed - it's contained in the Conditions):

import multiprocessing as mp
taskQ = mp.Queue()
resultQ = mp.Queue()
lock = mp.Lock()
# both conditions share lock
taskCond = mp.Condition(lock)
resultCond = mp.Condition(lock)

Client gets task; all clients use this function. Note that a task won't be consumed so long as the result queue has something in it:

def get_task():
    taskCond.acquire()
    while taskQ.qsize() == 0 or resultQ.qsize():
        taskCond.wait()
    # resultQ is empty and taskQ has something
    task = taskQ.get()
    taskCond.release()
    return task

Client has result:

with resultCond:
    resultQ.put(result)
    # only the server waits on resultCond
    resultCond.notify()

Server loop:

resultCond.acquire()
while True:
    while resultQ.qsize() == 0:
        resultCond.wait()
    # operations on both queues in all clients are blocked now
    # ... drain resultQ, reorder taskQ ...
    taskCond.notify_all()

Notes:

1. qsize() is usually probabilistic, but because all queue operations are done while the lock is held, it's reliable in this context.

2. In fact, because all queue operations are protected by our own lock here, there's really no need to use mp.Queues. For example, an mp.Manager().list() would work too (any shared structure). Perhaps a list would be easier to work with when you're rearranging tasks?

3. One part I don't like much: when the server does taskCond.notify_all(), some clients may be waiting to get a new task, while others may be waiting to return a new result. They may run in any order. As soon as any client waiting to return a result gets a chance, all clients waiting to get a task will block, but before then tasks will be consumed. "The problem" here, of course, is that we have no idea a new result is waiting before something is actually added to the result queue.

For the last one, perhaps changing the "client has result" code to:

resultQ.put(result)
with resultCond:
    resultCond.notify()

would be better. Unsure. It does make it significantly harder to reason about, because it's then no longer true that all queue operations are done under the protection of our lock.