Timer module is one of the key components of a protocol server. Almost all non-trivial protocols involve timeouts in their design. One of the biggest problems with software timers in multi-threaded systems is that they go off asynchronously, making the protection of session related data structures unavoidable. Even if per session data is isolated from other threads by storing them on the stack variables of the threads, callback functions invoked on timer expiry must access those data to update session state. AMPS provides the basic timer management APIs for the application developers. The key design goals of timer management APIs in AMPS are as follows:

• Timer implementation must be efficient. There should be no searching or sorting involved in any of the timer operations. Starting, stopping, and expiry processing of timers must be O(1) operations.
• The timer implementation must be scalable. The timer module must be able to manage long timeouts (of the order of at least 24 hours or more) without requiring large memory footprint.
• Timer callback functions must be called serially so that there is no need to protect access to shared session related data structures.
• Timer must be precise within a certain reasonable resolution (in the order of a few milliseconds). The shortest protocol related timeouts are usually in the order of milliseconds.

AMPS treats the timer as a high priority event in the system. The timer-tick event happens every k milliseconds where k is the resolution of the timer module. By default, k is 1 millisecond. A separate thread runs at a higher priority than any other thread in the application, including the main application thread, I/O agents and CPU agents. This thread sleeps for k milliseconds, then wakes up and sends an event to the main application via IPC mechanisms. It then goes back to sleep for another k milliseconds. The main application’s event manager processes the timer-tick event at a higher priority than any other event in the system. Also, after processing any event, it polls the timer event to see if the processing of the last event spanned more than k milliseconds. This way, it is guaranteed that no timer event would have to wait for more than the processing of a single non-timer event. This mechanism also makes it easy to determine which event (if any) is taking more than k milliseconds for processing. If the application developer detects such a handler, that one could then be divided further into multiple events so that each sub-component takes at most k milliseconds. The timer creation API allows the user to specify a callback function and an opaque data handle or pointer to be passed as argument to the callback.

Timer is implemented as a data structure based on the timing wheels idea presented in [8]. The data structure contains hierarchical arrays, each representing a counter of a digital clock.. This concept has previously been used in implementing Linux kernel timers. We have used four such arrays in AMPS. The first array represents milliseconds. Each slot in this array represents one tick or k milliseconds. The array contains 1000/k entries. This means that this array signifies the passing of a total of one second of time. This also implies that the milliseconds part of the timeout must be a multiple of k milliseconds. The next array represents seconds. It has 60 entries and signifies the passing of a total of one minute of time. Similarly, the next array represents minutes, has 60 entries and signifies a total of one hour of time. The last array represents hours, has 24 entries and signifies a total of one day of time.

Each entry in each array is a doubly linked list of timer callback functions. At each timer tick event, the event handler for the tick event traverses the list contained (if any) at the current array index, calling each callback function serially, and finally increments the array index by one to point. When the index of milliseconds array reaches the end of the array, the event handler replenishes the milliseconds array from the callback functions contained in the current index of the seconds array, and increments the index of the seconds array by one. The milliseconds array would then contain the timers due to expire within the next second. The event handler then increments the index of the seconds array by one. When the seconds array index reaches its end, the event handler replenishes it from the list of callbacks contained in the current index of the minutes array, and increments the index of the minutes array by one. The seconds array would then contain all the timers due to expire within the next minute. Similarly, the minutes array is replenished by hours array. This way, the milliseconds array index is incremented every tick, seconds array index incremented every second, minutes array index incremented every minute and hours array index incremented every one hour.

Note that the callbacks that are actually called are always contained in the milliseconds array. To make the discussion concrete, let’s consider the following example: