4. Implementation Notes

4.1 Job Scheduler

Getting the job scheduler to work correctly for all possible cases consumed more time than all the other parts of the program put together, and this is all because of the problems that daylight savings causes.

The ultimate goal is this: given a linear timestamp, determine the next linear timestamp after which a job must be run. "Linear time" means the number of seconds since an epoch, in this case the UNIX epoch, midnight GMT January 1st, 1970. To contrast, "local time" means the time in terms of years, months, days, hours, minutes, and seconds in the current locale.

The time specification for jobs is composed of a set of local time bitmaps quantifying under what time conditions the job should run, assuming the conditions are evaluated every minute. The maximum scheduling resolution is one minute.

The effective algorithm is to step through every possible minute until the local time matches all the conditions in the time specification. This would result in an algorithm that could take up to 527,040-1 steps to complete, which is far too big a number to evaluate on every job. So, the algorithm optimizes away all impossible cases to make much larger time jumps. For example, if the job cannot be scheduled on the current day, skip over the entire day instead of just the current minute.

There are two ways I approached this task. First, do all calculations in terms of local time, and return the linear time at the last step. Second, do as many calculations as possible in terms of linear time, which can be returned directly. Both methods start with the same input data: The current linear time, and a set of bitmasks representing under what time conditions the job should run.

The first method was the most straightforward to get mostly working, until I started to consider the implications of DST. During the transition from normal time to DST, an hour is skipped. This is no big deal, as mktime will (or can be made to) compensate by picking the next valid hour when presented with a "missing" hour. On the other hand, there are many gotchas when dealing with the duplicated hour. For example, hourly jobs need to get scheduled on both, but daily jobs on only one.

The second method was harder to get working initially, as the math is more complicated. Despite doing many calculations in terms of linear time, this method still needs to keep track of the local time, in order to check against the bitmaps as well as to determine things like when the next day or month should start. This approach proved to be much easier to work with, once the initial math was done, and easier to make work correctly with regards to DST transitions.