Suggestions for lightweight, thread-safe scheduler
- by nirvanai
I am trying to write a round-robin scheduler for lightweight threads (fibers). It must scale to handle as many concurrently-scheduled fibers as possible. I also need to be able to schedule fibers from threads other than the one the run loop is on, and preferably unschedule them from arbitrary threads as well (though I could live with only being able to unschedule them from the run loop).
My current idea is to have a circular doubly-linked list, where each fiber is a node and the scheduler holds a reference to the current node. This is what I have so far:
using Interlocked = System.Threading.Interlocked;
public class Thread {
internal Future current_fiber;
public void RunLoop () {
while (true) {
var fiber = current_fiber;
if (fiber == null) {
// block the thread until a fiber is scheduled
continue;
}
if (fiber.Fulfilled)
fiber.Unschedule ();
else
fiber.Resume ();
//if (current_fiber == fiber) current_fiber = fiber.next;
Interlocked.CompareExchange<Future> (ref current_fiber, fiber.next, fiber);
}
}
}
public abstract class Future {
public bool Fulfilled { get; protected set; }
internal Future previous, next;
// this must be thread-safe
// it inserts this node before thread.current_fiber
// (getting the exact position doesn't matter, as long as the
// chosen nodes haven't been unscheduled)
public void Schedule (Thread thread) {
next = this; // maintain circularity, even if this is the only node
previous = this;
try_again:
var current = Interlocked.CompareExchange<Future> (ref thread.current_fiber, this, null);
if (current == null)
return;
var target = current.previous;
while (target == null) {
// current was unscheduled; negotiate for new current_fiber
var potential = current.next;
var actual = Interlocked.CompareExchange<Future> (ref thread.current_fiber, potential, current);
current = (actual == current? potential : actual);
if (current == null)
goto try_again;
target = current.previous;
}
// I would lock "current" and "target" at this point.
// How can I do this w/o risk of deadlock?
next = current;
previous = target;
target.next = this;
current.previous = this;
}
// this would ideally be thread-safe
public void Unschedule () {
var prev = previous;
if (prev == null) {
// already unscheduled
return;
}
previous = null;
if (next == this) {
next = null;
return;
}
// Again, I would lock "prev" and "next" here
// How can I do this w/o risk of deadlock?
prev.next = next;
next.previous = prev;
}
public abstract void Resume ();
}
As you can see, my sticking point is that I cannot ensure the order of locking, so I can't lock more than one node without risking deadlock. Or can I? I don't want to have a global lock on the Thread object, since the amount of lock contention would be extreme. Plus, I don't especially care about insertion position, so if I lock each node separately then Schedule() could use something like Monitor.TryEnter and just keep walking the list until it finds an unlocked node.
Overall, I'm not invested in any particular implementation, as long as it meets the requirements I've mentioned. Any ideas would be greatly appreciated. Thanks!
P.S- For the curious, this is for an open source project I'm starting at http://github.com/nirvanai/Cirrus
