Signs Of The Times

Time - The Final Frontier

Time is a most peculear aspect of operating systems...
...because it keeps changing...
...in small leaps...
...and not necessarily in one direction only...
...and it is not very exciting to deal with it.

Lets Get Into The Zone

What's in a time zone?
a description of distance from GMT
which might change on different times of the year (daylight savings time)
using rules governed by politics more then anything else.
so let us define a language for defining time zones, they said...

Zone Language - Rules

We're in Unix world - lets do it in a text file with rules:

Rule  US    1967  1973  -     Apr  lastSun  2:00  1:00  D

This rule is part of the 'US' rules family.
It applies to times between years 1967-1973, inclusive.
It applies to all years in this range (the '-' states that).
The rule takes effect on the last Sunday of April, on 2AM.
At which time we should add 1:00 hours to the local-time,
And we then change the variable-part of the abbreviation of the time-zone to 'D'.

Zone Language - Zones

Then we also need a zone line:

Zone  Australia/Adelaide  9:30    Aus         CST     1971 Oct 31 2:00

Which defines a zone named 'Australia/Adelaide',
which requires adding 9:30 hours to UTC in order to get to its "local time",
The rules applying to this zone belong to the 'Aus' rules family.
The format for the abbreviation of this time-zone is 'CST' (if it was 'C%T' it would mean that the variable-part is in the middle).
And finally, the UTC offset (or rules) change for this zone on '1971 Oct 31 2:00' - in which case there must be a continuation line specifying what happens right on this date.

Zone Language - Other Types Of Lines

There may be a Link lines, to specify an alternate name for a time zone.
There may be Leap lines, to specify a "jump" in time on a given date (e.g. a second is added on a given date, to compensate for the difference between the movements of the sun and the moon).

Compiling A Zone File

The OS does not read these text files to make time calculations.
We use the 'zic' compiler to turn them into binary files:
zic <text-file-name>
The resulting file will be placed in the system's standard directory (often /usr/share/timezone/), using the zone name (from the file) as the name of the resulting binary file (if there's a '/' - puts the file in a sub-directory).

The Flow Of time()

Time always advances, unless the timezone makes it jump backwards (e.g. switch from daylight saving time), or unless the system clock is set abroptly via a 'date' command or similar.
Thus, we should be careful about how we manage time calculations in code (e.g. never assume that a future time minus a past time gives a meaningful result).
We check the time with:
- time(NULL) - returns the number of seconds elapsed since 1/1/1970 at midnight, in UTC.
- localtime() - translates a given time based on the time zone. returns the time broken into its parts - year, month, day, hour...
  note: the 'month' field is 0-11, not 1-12.
  note 2: the 'year' field is the distance from 1900, not the full year (so year 2005 is represented as 105).
- mktime() - does the inverse of localtime, with the addition of strange handling of 'out-of-range' values in the various fields (see the man page...)

Handing Time Across Time Zones

Often an application operates across time-zones (either directly, e.g. a distributed application, or because it stores data into files).
The best policy is to manipulate time data in UTC.
Translate the time into local-time only just before presenting it to the user.
Failure to perform this will cost you hours of implementing hack over hack over hack...

Keeping Machines Synced In Time

We have various means for syncing time between machines:
one-time manual setting.
one-time semi-automatic setting.
repeated one-time semi-automatic setting.
fluent and fully automatic.

Manual Setting - The 'date' Command

To set the time on a machine, we may use the 'date' command:
```
date 0822004705
```
This has set the time to august (08) 22nd, 47 minutes past midnight (0047), on the year 2005 (05).
When we shut-down/reboot the machine, the OS scripts are likely to synchronize this new time to the hardware block, so it'll take effect during the next reboot.
NOTE: of-course, we must be 'root' in order to change the local time.

The Time Service

To be able to sync the time from a machine we don't have an account on, we have the time service(s).
Standard ports 'daytime' (13) and 'time' (37) are used to export these services, by xinetd.

'daytime' uses a text protocol:

[choo@simey ~]$ telnet 127.0.0.1 daytime
Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
22 AUG 2005 00:56:39 IDT
Connection closed by foreign host.
[choo@simey ~]$

'time' uses a binary protocol:

choo@simey ~]$ telnet 127.0.0.1 time
Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
Ƴw7Connection closed by foreign host.
[choo@simey ~]$

Semi-Automatic Time Setting

The 'rdate' command glues together the binary 'time' service with local time setting.

To read the time off a remote machine running the 'time' service:

[choo@simey ~]$ rdate 127.0.0.1
[127.0.0.1]     Mon Aug 22 00:58:06 2005
[choo@simey ~]$

To set the time of the local machine to that of the remote machine:

root@simey ~]# rdate -s 127.0.0.1
[root@simey ~]# date
Mon Aug 22 01:00:30 IDT 2005
[root@simey ~]#

Automating The Semi-Automatic 'rdate'

The most crude form of time synchronization will mean putting an 'rdate -s' command in a cron job.
How often to run this job? sometimes once a day will suffice.
If you need a more accurate clock (e.g. your machine's clock runs off quickly), you may want to run 'rdate' more often.
For some kind of operations this will not suffice (e.g. compiling source code that resides on an NFS server, which is edited via another machine - 'make' will not like even tiny time mismatches).

The "one-true-way" to synchronize time - NTP

NTP is the network-time-protocol that adjusts the time in a fluent manner.
NTP requires a server on one machine, and clients on other machines.
The clients will measure the time-differences (and the network delays), and will get the clock of the client synchronized with that of the server up to few milli-seconds.
This process is delicate, and can take several days to stabilize, if the network connection between the machines presents varying delays.
Now go read The NTP FAQ and HOWTO.

Sub-Second Sleeps

We all know how to sleep in our code using the 'sleep()' function.
(which uses ALRM signals, and is thus not useful in multi-threaded programs).
Sometimes we want to sleep for less then a second.
Let us avoid real-time constraints here, and deal with 'best-effort' attempts.

First Attempt - 'usleep()' or 'nanosleep()'

These functions will sleep a given ammount of time (usleep is BSDish and accepts micro-seconds, nanosleep is POSIX and accepts 'struct timespec', which contains nano-seconds).
nanosleep also tells us how much time is left to sleep, in case we were woken prematurely (e.g. by receiving a signal). More on the use of this later.
They both suffer from the Linux-timeslice effect - they will sleep at least the minimal time-resolution of the kernel (1/1024 on i386 hardware with a 2.6 kernel, 1/100 with a 2.4 kernel, etc).
Thus, to sleep less - we need to avoid sleeping at all, and use busy-wait.

Measuring Busy-Wait

How do we busy-wait? we just run a loop that does nothing.
Then we need to measure it: use gettimeofday() - it gives the time in micro-second accuracy (more or less).
Here is some silly code to delay for 30 micro-seconds, in busy-wait-3-secs.c.

The Twisted 'select()' Call

We know that select takes a time-out parameter, with micro-second accuracy.

Thus, one is tempted to use select for sleeping:

int rc;
struct timeval timeout;

timeout.tv_sec = 0;
timeout.tv_usec = 10;
rc = select(0, NULL, NULL, NULL, &timeout);

Of-course, select() is not better then nanosleep() - it sleeps in the system's clock resolution.
But it can also multiplex network connections (ha!) - so we can have timers combined in a network server or a GUI program (X is a network protocol, after all), using a single select-based loop...

Timers Using A Delta-List

To implement several timers using a single select() loop, we need to store a list of timers.
The natural list will be a delta-list - each entry contains the distance from the previous entry, rather then the UTC time we want the timer to set off on.
This is material for Introduction To Operating Systems 101.

Time Drifts With Delta Lists

What they also teach in "Intro To OS 101", is that timers tend to drift.
I.e, because we're not running on a real-time operating system, a sleep for X seconds may cause us to wake after X seconds + Y micro-seconds.
If we had a delta-list of timers, and each timer wakes up slightly too late, then after several timer set-off events, we'll start collecting a noticeable delay.

The Often-Forgotten EINTR

What they do NOT teach in "Intro To OS 101", is that system calls are sometimes aborted prematurely if the process running them received a signal.
In this case, the system call will return an error (-1), with errno set to EINTR.
If we don't handle these cases properly, we will either think we had a "real" error and abort the program, or we will not handle the premature awakening at all and start having a negative time-drift (or, time flowing faster then it should).

A Stable Implementation Of A Reccuring Timer

To conclude, following is a stable implementation of a reccuring timer.
stable-recurring-timer.c.
When handling a delta-list, we need to handle proper triggering of all the elapsed timers, if we were woken up too late. Consider this as an exercise.

Timing And Profiling

Two common methods for checking the efficiency of our code:
1. Timing - either timing the entire code, or adding timing caclulations into the code.
2. Profiling - using existing tools that perform this automatically.

Timing

The simple way to check wall-clock time:
```
date; my_program; date
```
Checking CPU time consumed by the process:
```
time my_program
```
Timing inside the code, by using gettimeofday() before and after some interesting code chunk, and calculating the difference.
Better perform the timing over many runs of the program/code-block, and print the average.
of even better, generate a log file and print a graph using gnuplot or a spreadsheet.

Profiling Using gprof and kprof

To profile our code, we need to compile each source file with the extra '-pg' flag of gcc, and link with the same '-pg' flag.
Running this code will generate a file named 'gmon.out'.
To view the output:
```
gprof -b
```
'Kprof' is a graphical tool to view the profiling data in a meaningful way.
Why not try it yourself, with some simple source code? (Here is how the output might look)

References

Originally written by

guy keren