[Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted

Glyph glyph at twistedmatrix.com
Tue Dec 13 23:45:54 EST 2011


On Dec 13, 2011, at 2:04 PM, Andrew Francis wrote:

> Now at time T, there are eight reindeer and two elves ready. At T+1, an additional  reindeer and elf are ready (their timestamps are the same, timer resolution notwithstanding). However the Twisted reactor will serialise the events and trigger the callback. For argument, let us pretend the elvesArrive callback is activated and that wakes Santa. Santa consults with the elves. The problem is that all nine reindeer were ready and the priority rule is broken. I am not sure, from inside the callback, one could check to see if nine reindeer were indeed ready.

This strikes me as a problem with the way that quantum physics works more than the way that Twisted's reactor works :).  Broadly speaking, no two events can happen at the exact same time; even if they did, relativity says you wouldn't be able to tell if they happened at the exact same time unless they also happened to be exactly the same distance away from you.  (But then "you" would have to be exactly one atom big, which is a pretty demanding size to build a sensor.)

Even if it were possible in reality, once a network gets involved, you have a bunch of additional bits of technology serializing everything.  If your computer has one ethernet card, the reindeer and the elves have to report their readiness either in separate ethernet frames in one order or the other, or in one order or another within the same ethernet frame.  (If it has two ethernet cards, you still only have one PCI bus, et cetera.)

Despite the fundamentally sequential nature of reality, Twisted reactor's scheduling mechanism does leave some things to be desired; the quantum time-slice of Twisted is effectively one reactor iteration, and there aren't really any tools for working with those.  There's some latency between becoming aware of some work that needs to be done (select(), or your chosen multiplexor, returning) and actually doing the work (calling doRead, doWrite, or your timed event), but you don't get to decide on priorities once Twisted's aware of the work; they're executed in a quasi-arbitrary order.

Ultimately however, the order of the work will be arbitrary; if it's not influenced by the vagaries of Twisted's scheduler, it will be influenced by something in the kernel scheduler that you don't understand or can't control, or in the IP stack, or in a switch on your network, or in your hosting provider's firewall configuration, or something on a client machine that you truly have no influence over at all.  Having something give priority to an event that occurs at "the same" time given all of these potential sources of interference is basically pointless.

The only reason that the Santa problem, expressed as a thread-synchronization problem, has to deal with "simultaneous" arrival of 9 reindeer and 3 elves is a quirk of thread scheduling: the Santa thread can be ready to run but not running.  When the final reindeer arrives, a final elf may arrive before the scheduler decides it's time to give Santa a chance to run, and then Santa has the opportunity to make the choice between the two.  In an event-driven system, this state doesn't naturally exist: when you call Deferred.callback(), the callback runs the relevant application code immediately.

Even in a preemptively threaded system though, the notion of simultaneity is pretty arbitrary; you don't get much control over how long Santa will be left in the ready-to-run-but-not-running state.  If you really care about Santa giving priority to the reindeer, then the system requires another input: how long should Santa sleep after the elves become ready, before deciding to go with the elves rather than the reindeer?  Effectively in a threaded system Santa is sleeping, just for a very small and not configurable amount of time.

-glyph

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://twistedmatrix.com/pipermail/twisted-python/attachments/20111213/ef77e3c1/attachment.htm 


More information about the Twisted-Python mailing list