Also, under Windows it is possible to change the resolution of the scheduler - see timeBeginPeriod() and timeEndPeriod().
That's rather dangerous, as it can have adverse affects on the rest of the system (especially older systems) and you'll be in for problems if your program dies without calling timeEndPeriod. Under Linux, the timer is configurable (250hz, 100hz, 1000hz, IIRC), so you should not assume any kind of granularity when resting. If you rest(0), it will get back to you ASAP after checking other threads. If you rest more, it will get back to you ASAP after the time is over. That's all you can gaurantee.
// DO NOT sleep for less than 16ms
// Most OS timers are not accurate under 16ms
Why shouldn't you sleep for less than 16ms, even if that's the granularity you get? What's the difference if you rest for 1ms and get back in 16ms, or rest for 16ms and get back in 16ms? In fact, trying to match it like that can cause you more problems if it checks your process just ahead of schedule, sees that you want to sleep a bit more, then goes another round without you.
Your granularity is determined b y a number of factors, not the least of which is how much CPU time the other processes take. Even with a 10ms timeslice, if you rest for 1ms, and after 5ms, no process wants to use the CPU, the OS will see your thread and wake you up (thereby causing you to sleep for 5ms, instead of 10 or 16).
There is another issue, though. Allegro's timers themselves are very innaccurate, so you shouldn't use them to time your logic if you can help it. Every single running timer is run on the same thread, so after resting and being woken up to run your callback (incurring the 5~10ms delay), it'll check all other timers to see if they want to run. And if one of them happens to want to, you'll get a longer delay.