Efficient time checking using the interval timer

[sje]

Efficient time checking using the interval timer

Unix systems have several interval timers available for each process. One of these timers measures real time (e.g., wall clock time), and this is the one to use for efficient time checking.

An interval timer works by periodically sending the Unix signal SIGALARM to the calling process. In Symbolic, the real time interval timer is called to send this signal at the rate of 100 Hz. This signal is caught by a routine which increments a variable representing the tick count. A microsecond counter is also incremented.

In the search, a time check is done at each node by comparing the tick counter to a limit representing the nominal time allocation for the search. This enables the search to do time management without the need to do a costly system call at each node. This also means that the time checking is entirely independent of the speed of the hardware or the complexity of the position.

To set a signal handler, the routine is signal(). To set an interval timer, the routine is setitimer().

Note 1: When deactivating an interval timer, the process should wait three intervals for it to go away.

Note 2: When an interval timer sends its signal, any active sleep calls in the process will return early with an EINTR result.

Note 3: The 100 Hz rate works well, but for super fast time controls, a higher rate might work better although it will increase overhead. For casual games, a 1 Hz timer should be sufficient.

[Codesquid]

A word of caution on signals: A signal handler can potentially be called at any time, during any operation.

Inside of a signal handler, a lot of functionality is not available as one is only supposed to call async-signal-safe functions. Calling an unsafe function can yield to very subtle, hard to find bugs. See man 7 signal for details.

For example, the malloc family of functions is not async-signal-safe. If you were to call malloc in a signal handler and the handler happens while malloc was being called, you'll likely end up with heap corruption.

Apart from that, using signals works fine.

[sje]

Inside of a signal handler, a lot of functionality is not available as one is only supposed to call async-signal-safe functions.

Symbolic has several signal catchers, and none of them call any functions. What the handlers do is to assign a couple of variables which are later read by threads which do further processing.

A signal handler has to be fast, because if a signal occurs before its handler finishes from a previous call, the program may crash.

[bob]

Inside of a signal handler, a lot of functionality is not available as one is only supposed to call async-signal-safe functions.

Symbolic has several signal catchers, and none of them call any functions. What the handlers do is to assign a couple of variables which are later read by threads which do further processing.

A signal handler has to be fast, because if a signal occurs before its handler finishes from a previous call, the program may crash.

What does that mean? There are two parts to a signal. When it occurs and how many occur. Signals do NOT count. If multiple signals happen you might see your handler invoked one time. But I have NEVER had a crash of any kind. We use 'em in my network programming course all the time, particularly when writing threaded servers. SIGCHLD's can happen anywhere, even while you are in the handler...

[sje]

I'm referring to signals of the same signal number. Example: If a handler is processing a SIGINT signal and another SIGINT signal occurs before the handler is finished, then the program will be killed.

Maybe things have changed, but this is the way it used to be and I think it's the same today.

[syzygy]

Efficient time checking using the interval timer

Unix systems have several interval timers available for each process. One of these timers measures real time (e.g., wall clock time), and this is the one to use for efficient time checking.

An interval timer works by periodically sending the Unix signal SIGALARM to the calling process. In Symbolic, the real time interval timer is called to send this signal at the rate of 100 Hz. This signal is caught by a routine which increments a variable representing the tick count. A microsecond counter is also incremented.

In the search, a time check is done at each node by comparing the tick counter to a limit representing the nominal time allocation for the search. This enables the search to do time management without the need to do a costly system call at each node. This also means that the time checking is entirely independent of the speed of the hardware or the complexity of the position.

Why not simply set up SIGALARM to trigger when the allocated time actually runs out? I don't see the need for the indirection of a separate 100 Hz counter.

When SIGARLM is triggered, the handler sets a flag. This flag can then be checked at each node.

For portability, use sigaction().

[sje]

Why not simply set up SIGALARM to trigger when the allocated time actually runs out? I don't see the need for the indirection of a separate 100 Hz counter.

The tick counter is used for multiple purposes, not just the search time check. For example, Symbolic has a progress meter class. and an instance of this class accesses the tick counter to fire every 25 ticks to update a progress display on long tasks like book compilation.

Also, the search time check actually has several different nominal time limits: per node, per candidate move, and per iteration. So it would take three different timers for a single SIGALRM each, but only one timer is available.

----

The idea for using a ticker came from my work back in 1986 when a Macintosh Plus was my development machine. Its operating system included a global tick counter which ran at about 60 Hz counting the number of display refreshes since the system boot.

[bob]

I'm referring to signals of the same signal number. Example: If a handler is processing a SIGINT signal and another SIGINT signal occurs before the handler is finished, then the program will be killed.

Maybe things have changed, but this is the way it used to be and I think it's the same today.

Why? In most OS systems, once you set a handler for SIGNIT it remains for all time. Ditto for SICGHLD (which I just verified).

[syzygy]

Why not simply set up SIGALARM to trigger when the allocated time actually runs out? I don't see the need for the indirection of a separate 100 Hz counter.

The tick counter is used for multiple purposes, not just the search time check. For example, Symbolic has a progress meter class. and an instance of this class accesses the tick counter to fire every 25 ticks to update a progress display on long tasks like book compilation.

Also, the search time check actually has several different nominal time limits: per node, per candidate move, and per iteration. So it would take three different timers for a single SIGALRM each, but only one timer is available.

I'm not entirely sure what those timers, but I assume you want to stop the search if any of those timers run out. The solution is to set the SIGALRM timer to the earliest one. Whenever a timer setting changes due to developments during the search (e.g. finishing of an iteration, or dropping of the score), it is easy to reset the SIGARLM timer again to the earliest one.

With your current approach it seems you need to check, at every node, the tick counter against all of the three timers (unless you already determine the earliest time out moment as per my suggestion).

[syzygy]

I'm referring to signals of the same signal number. Example: If a handler is processing a SIGINT signal and another SIGINT signal occurs before the handler is finished, then the program will be killed.

Maybe things have changed, but this is the way it used to be and I think it's the same today.

Why? In most OS systems, once you set a handler for SIGNIT it remains for all time. Ditto for SICGHLD (which I just verified).

Using signal() is problematic here.

Portability
The only portable use of signal() is to set a signal's disposition to SIG_DFL or SIG_IGN. The semantics when using signal() to establish a signal handler vary across systems (and POSIX.1 explicitly permits this variation); do not use it for this purpose.

POSIX.1 solved the portability mess by specifying sigaction(2), which provides explicit control of the semantics when a signal handler is invoked; use that interface instead of signal().

In the original UNIX systems, when a handler that was established using signal() was invoked by the delivery of a signal, the disposition of the signal would be reset to SIG_DFL, and the system did not block delivery of further instances of the signal. System V also provides these semantics for signal(). This was bad because the signal might be delivered again before the handler had a chance to reestablish itself. Furthermore, rapid deliveries of the same signal could result in recursive invocations of the handler.

BSD improved on this situation by changing the semantics of signal handling (but, unfortunately, silently changed the semantics when establishing a handler with signal()). On BSD, when a signal handler is invoked, the signal disposition is not reset, and further instances of the signal are blocked from being delivered while the handler is executing.

The situation on Linux is as follows:

* The kernel's signal() system call provides System V semantics.

* By default, in glibc 2 and later, the signal() wrapper function does not invoke the kernel system call. Instead, it calls sigaction(2) using flags that supply BSD semantics. This default behavior is provided as long as the _BSD_SOURCE feature test macro is defined. By default, _BSD_SOURCE is defined; it is also implicitly defined if one defines _GNU_SOURCE, and can of course be explicitly defined. On glibc 2 and later, if the _BSD_SOURCE feature test macro is not defined, then signal() provides System V semantics. (The default implicit definition of _BSD_SOURCE is not provided if one invokes gcc(1) in one of its standard modes (-std=xxx or -ansi) or defines various other feature test macros such as _POSIX_SOURCE, _XOPEN_SOURCE, or _SVID_SOURCE; see feature_test_macros(7).)

* The signal() function in Linux libc4 and libc5 provide System V semantics. If one on a libc5 system includes <bsd/signal.h> instead of <signal.h>, then signal() provides BSD semantics.

Behaviour on Linux depends on your compilation flags...