A New Design for Timers

The next step in green threads is to make them preemptive: after one thread has run for a while, it needs to be stopped so a waiting thread can have a turn. Parrot has a mechanism for doing things after a set time called Timers which would be perfect for this. Unfortunately, they don't really work.

So I'm going to make them work, at least in my gsoc_threads branch.

The basic concept of timers is this: I want something to happen in the future, no sooner than X seconds from now. In order to accomplish this, the timers go in a list and the runtime system checks every once and a while to see if any of them are ready to run.

Currently in Parrot this work is done in the task scheduler. Future timers are stored in a wait list, and every time tasks are checked the entire list of future timers is scanned to see if any of them are ready. This is a relitively expensive operation, which means the system can't check for expired timers (or any asyncronous events) very frequently. Currently, tight compute loops may never trigger a check.

Convieniently, timers are one of the basic primitives that operating systems provide for applications. In POSIX, various system calls (e.g. setitimer) allow us to set an alarm and have a signal delivered to the application after a set amount of time. The signal handler can be used to set a flag which the run loop can check cheaply (and thus frequently). I'm not sure how to do this on Windows, but the worst case is an extra OS thread that does WaitOnMultipleThings() a lot.

So the general plan is this:

  • When a timer is set, insert it into a sorted list of timers.
  • If it's the soonest timer, set an alarm for it and mark it as alarmed.
  • When an alarm triggers, if the head of the timer list is ready to go, set the flag. If the new soonest timer is not marked alarmed, it marks it and sets an alarm.
  • When the runloop sees the flag set, it runs any expired timers and unsets the flag.

This can be extended to multiple OS threads (and thus runloops) with one simple change. Instead of a flag, there is an integer serial number. Instead of the flag being set, the serial is incremented. Each runloop remembers the last value of the serial, and if the new value is greater it runs expired timers.

With some luck this will:

  • Make timers run sooner with less overhead.
  • Fix tt #484 as a side effect.
  • Let me use timers for green thread preemption.
  • Not change the (questionable) timer API at all.