Cooperative/Non-preemptive threading avoiding threadlooks?

Question

Any creative ideas to avoid deadlocks on a yield or sleep with cooperative/non-preemptive multitasking without doing an O/S Thread.Sleep(10)? Typically the yield or sleep call will call back into the scheduler to run other tasks. But this can sometime produce deadlocks.

Some background:

This application has enormous need for speed and, so far, it's extremely fast as compared to other systems in the same industry. One of the speed techniques is cooperative/non-preemptive threading rather then the cost of a context switch from O/S threads.

The high level design a priority manager which calls out to tasks depending on priority and processing time. Each task does one "iteration" of work and returns to wait its turn again in the priority queue.

The tricky thing with non-preemptive threading is what to do when you want to a particular task to stop in the middle of work and wait for some other event from a different task before continuing.

In this case, we have 3 tasks, A B and C where A is a controller that must synchronize the activity of B and C. First, A starts both B and C. Then B yields so C gets invoked. When C yields, A sees they are both inactive, decides it's time for B to run but not time for C yet. Well B is now stuck in a yield that has called C, so it can never run.

Sincerely, Wayne

Answer 1

I think that probably the cleanest way to handle this is to separate yielding (a thread deciding it has processed enough for a while) from blocking (waiting for a specific event). That makes it relatively easy to give time to threads that have yielded, but avoid a deadlock from trying to run a thread that's blocked. Generally, you want to do a topological sort on what thread is blocking on what other thread, so you can give time to the thread(s) others are waiting on. This should give a DAG -- any cycle in the graph indicates a deadlock.

Answer 2

Well, realized the ideal solution to this would be if the C# language supports true "continuations" to unwide the stack and continue where left off later.

In the absence of that we are making our own makeshift replacement by allow the tasks in this situation to set an "isInterrupted" flag to true and return--thereby unwinding stack.

Then when the scheduler wants to schedule processing time to that task again, it will see the isInterrupted and skip the processing that was already done to jump right to the interrupt location using simple if statement.

Sincerely, Wayne