OSDev.org

Heres an interesting question: How do you store time in your OS?

My plan is to use a signed 64bit counter measuring time in units of 2**-20 seconds since midnight January 1st 2000. This means there are 0x100000 ticks per second, each clock interrupt at 256Hz will increment the counter by 0x1000.

I will ignore leap seconds and my main system library will have a conversion function from my time (in TAI) to a more usable time (in UTC, maybe also split into fields for seconds, minutes, etc.). Conversion from a 64bit clock to a 32bit clock (1 tick per second) may also be supported.

So how about you?

My plan was to use a signed 128-bit counter measuring time in units of 2**-64 seconds since midnight January 1st 2001. This makes the upper 64-bit a second counter and the lower 64-bit a subsecond counter. This way, the upper half is trivially convertible to unix time and the upper half commonly suffices to compare differences. It also allows subsecond differences so that minute differences can be taken into account and even subcycle timings can be stored. I feel the format is more future-safe in 128-bit mode because there's only a very small chance that units smaller than 1/18th femtosecond can be measured accurately nor will it outlive the universe. that it'll outlive the universe.

I'm going to support leap years, but not leap seconds (just the calculable stuff please). Since my clock "starts" in 2001 the leap years are at an absolute offset from the start and the day number can be calculated exactly. I'm not entirely certain this is the best start date but I think it is. You can convert it to unix time without a seconds' thought, converting to Windows time can be done back & forth without much precision loss, conversion to DOS packed time format is also well possible (but I dislike DOS times since they overflow in 2108). Of course, you'll be able to read all of these as well with the library to the generic in-memory time format.

Well TAI is a linear number of seconds with no leap seconds or other conversion. The user libraries can deal with leap years.

As far as resolution goes, I prefer to stick to a 64-bit variable since it can be handled natively by the processor.

A couple of interesting time links:
http://news.bbc.co.uk/2/hi/science/nature/3486160.stm - Shortest time interval measured (2004, measured 100 attoseconds).
http://en.wikipedia.org/wiki/Planck_time - Planck Time, the shortest time it is theoretically possible to measure (approx. 10**-44 seconds)

Please forgive the tangents, this is likely to go off-topic pretty fast.

Related - OSFAQ: TimeDate.

I'm advocating mainly using the first 64 bits as resolution since it'll commonly be enough. This method doesn't cause a big conversion to and from unix time, it allows big enough numbers and it has more than enough bits of precision for any number I (or most others) will ever use.

Ah crap... there goes my precision. I'll redefine it as the smallest practical amount of time for normal use (a single cycle in a very optimized machine).

There I go again, wasting gazillions of attoseconds on this...

Hi,



The last version of my OS used an unsigned 64 bit milli-seconds counter, where 0x8000000000000000 was equal to the beginning of the year 2000 (in UTC). It didn't take into account leap seconds...

For the new version of my OS I'm planning to use a signed 64 bit counter that counts 1/65536[sup]ths[/sup] of a second, where zero is equal to the beginning of the year 2000 (in UTC). For the new version I will take into account leap seconds, so that a second is always a second long and a minute may not be 60 seconds long.

@Candy: The problem with using a 128 bit counter is that it's impossible (or at least incredibly difficult) to update it atomically on a 32 bit multi-CPU computer. This means using re-entrancy locks or something in the timer IRQ handler and in the "get_system_timer_tick()" routine, which I wouldn't like (deadlocks)...

The same problem occurs for a 64 bit timer on a 32 bit machine, but here there's a "trick" that can be used to avoid locking. Basically, the timer IRQ updates the lowest 32 bits of the counter only. Whenever a CPU reads the time it checks for overflow in the lowest 32 bits and updates it's own seperate copy of the higher 32 bits if overflow is detected. This works providing that the every CPU reads the time every 9 hours or so (if 1/65536[sup]ths[/sup] of a second is used). Because my scheduler uses this time count for measuring how long a thread was running, it's measured every thread switch and the "9 hours between reads" limit is never reached.


Cheers,

Brendan

Thanks zloba, I missed that page. It doesn't actually cover TAI, but is still very useful. I can add a feature to periodically (every 10 seconds or so) sync the clock to the RTC later on.

At the moment I'm getting ready to write my timer interrupt and switch from cooperative scheduling to pre-emptive scheduling. I thought I'd get the timekeeping code in there at the same time and just wanted some input. It's always interesting to hear how other people do things.

@Brendan: Given the resolution of the timers used (thousandths of a second) and the actual update interval (hundredths or tenths of a second), it would be pretty straight forward to add 1 to the counter before updating and subtract 1 when finished. Any reader would know the bottom bit is only set during an update, since each update will add a nice number to the counter (1000, 256 or whatever). So if the reader sees the lowest bit set it waits for it to un-set.

Just an idea, I'd never use it in practice since I don't like the idea of mixing data and meta-data. I'd just put a spinlock around all reads to/from the upper 32bits (my spinlocks are deadlock-safe, higher level stuff like mutexes and semaphores aren't).

What is the point of such accuracy ??? and this seems like a waste of cpu time. i use a precision of 1/ 100 but stored as 1 / 1000, and i convert only for mili-second delay loop, but the presition can be adjusted in run-time(all time base code like scheduling is based on a veriable of ticks per second)

Do you mean accuracy or resolution? I myself have a problem deciding which I mean.

Accuracy - difference between recorded time and real time.
Resolution - smallest amount of time you are able to record.

So yes there is a point to such accuracy but whether a resolution better than 1/1000 seconds is needed is questionable.

An interesting question is, given than both the PIT and RTC can generate interrupts at a 256Hz frequency, which is a better choice? Is one more accurate than the other, are they both similar or does accuracy differ depending on the computer (ie. one computer may have a more acurate PIT and the other may have a more accurate RTC)?

Hi,



Both timers can be relatively inaccurate (depending on the motherboard, a $2.00 kids watch can be more accurate), but I would hope the RTC is at least as accurate as the PIT (or has less drift) as it's intended to measure real time. It's hard to get good statistics for the accuracy of available timers though. In any case I'd recommend having some method of adjusting the drift, like the UNIX adjtime() function which could be used to manually correct drift or used in conjunction with NTP to automatically correct drift.

For timer resolution, the maximum possible resolutions are:

RTC - 122070 nano-second or 8192 Hz
PIT - 838 nano-second or 1.193181666666 MHz
HPET - 100 nano-second or 10 MHz
Local APIC - usually between 40 nano-second (25 MHz bus) and 1.25 nano-second (800 MHz bus) depending on front side bus speed

Of course the maximum possible resolutions aren't practical. For the ISA devices (RTC and PIT), often the chipset can't handle the higher frequencies and IRQs are lost. For all timers there's problems with IRQ overhead and IRQ latency.

For the "best possible" timing, I'd use the highest resolution timer the computer has with drift adjustment, and then dynamically set the frequency used by that timer. For example, for a slow 80486 you might want to reduce timer frequency to reduce timer IRQ overhead, while on a computer with four 3 GHz CPUs you might want to increase timer frequency to increase system timer resolution.


Cheers,

Brendan

Beware of counters that stop on the halt instruction. I think the RTC does that on some CPUs. Some Pentium 4s are the first Intel chips that do not suffer from this, to my knowledge.

That's all I have to contribute to this discussion though.

Would be pretty awkward if the RTC stopped counting. If you claim the TSC stops counting I'll believe it right off the bat, but I would be confused when the P4 "fixed" that.

Crap, I suck at life. You're right; TSC, not RTC. Too many abbreviations for my brain. Then again, I still hold that the P4 (or at least some) doesn't have this behavior as I have experienced it myself.