Timeouts

Sometimes a thread may need to put itself to sleep until something wakes it up. In particular it may sleep until it receives an expected event from another thread. If no event arrives within a reasonable time, the thread may need to take appropriate action, such as treating the non-event as an error.

Other times a thread may need to sleep for a pre-determined length of time, without expecting any other thread to wake it up.

For these situations, Cheap Threads offers a timeout facility.

By default, timeouts are disabled, in order to avoid the associated overhead in applications that don't need them. You can enable timeouts at compile time by defining the macro CT_TIMEOUT.

Waiting on a Timeout

To wait on a timeout, a thread may call the ct_wait_on_timeout function. Later, when the thread returns control to the scheduler, it is placed on a list of sleeping threads, where it may be awakened by a message or an enqueue.

In this respect ct_wait_on_timeout() is similar to the ct_wait function. What's different is that when you call ct_wait_on_timeout() you specify a waiting time. If no event awakens the waiting thread during that time interval, the scheduler itself will awaken the thread.

If some other event awakens the thread before the timeout expires, the timeout is cancelled. Therefore the thread will be awakened by the timeout or by some other event, but not both.

There is no built-in mechanism for the thread to determine whether it was invoked through a timeout or through some other means. The application can provide such mechanisms if necessary, for example by storing a status flag in the thread's private data.

Units of Time

The 1989 C Standard provides three types for representing time: time_t, clock_t, and struct tm. Of these, it defines units only for struct tm, where the tm_sec member represents seconds.

The other two are "arithmetic types capable of representing times" (7.12.1, ISO numbering), but the Standard specifies neither the underlying types nor the encoding. While a time_t typically represents seconds, and a clock_t typically represents fractions of a second, implementations are free to use other encodings. Likewise they may use floating point types instead of the more typical integral types.

Since the Standard does not portably recognize any unit of time shorter than a second, Cheap Threads defines its own representation of time in the header file ct.h: 

typedef struct		/* For timers */
{
	unsigned long tick; /* ticks */
	unsigned long era;  /* cycles of ULONG_MAX + 1 ticks */
} Ct_time;
The tick member represents multiples of some short unit of time, as chosen by the application. In some cases it might represent seconds, and in others it might represent milliseconds or microseconds, as measured by some non-portable system call.

The era member allows for overflow of the tick member. It represents (ULONG_MAX + 1) ticks.

As a practical matter, the era member will seldom be needed, because most programs won't run long enough for the tick member to overflow. However it is available for long-running programs that use short ticks.

Suppose, for example, that an application uses 1-microsecond ticks. Assuming that an unsigned long is 32 bits wide, the tick member will overflow within about 71 minutes. By using the era member for overflow, the application can keep managing timeouts for just over 584,542 years.

Tick Interval

By default, Cheap Threads defines a tick as one clock_t unit, based on the standard clock function. In many cases this approach will be good enough, though the application may have to convert from seconds by using the standard CLOCKS_PER_SEC macro.

This default assumes that a clock_t is an integral type. If your C implementation defines it as a floating point type, and you do not define your own timing function (see below), the timeout mechanism will fail at run time and halt the scheduler.

You can redefine the tick interval by calling ct_install_clock() to install your own timing function.

Internal Implementation

When a thread calls ct_wait_on_timeout(), the scheduler calculates a deadline by adding the interval to the current time and stores this deadline as an attribute of the thread.

Later, when the thread returns control to the scheduler, it is placed in the list of sleeping threads. Threads that are waiting on timeouts are placed at the head of the list, sorted by deadline. Other sleeping threads are added to the tail of the list, where their sequence within the list is not significant.

Between threads, the scheduler notes the current time and then examines the head of the sleeper list. If the current time is greater than the thread's deadline, the scheduler enqueues it for execution at the highest priority. It continues enqueuing successive threads until it finds a thread that is not waiting on a timeout, or whose timeout has not yet expired.

Home