data structure with no timers active.

10.2 Simple Timers

Operating systems often implement multiple software timers that are based on a single hardware timer. A software timer can be represented by a timer number and an indication of when the timer expires . The implementation depends on the type of hardware timer available.

Suppose the hardware timer generates interrupts at regular short intervals called the clock tick time . The timer interrupt service routine monitors the time remaining on each timer (in terms of clock ticks ) and decrements this time for each tick of the clock. When a timer decrements to 0, the program takes the appropriate action. This approach is inefficient if the number of timers is large or if the clock tick time is short.

Alternatively, a program can keep the timer information in a list sorted by expiration time. Each entry contains a timer number and an expiration time. The first entry in the list contains the first timer to expire and the time until expiration (in clock ticks). The second entry contains the next timer to expire and the expiration time relative to the time the first timer expires, and so on. With this representation, the interrupt service routine decrements only one counter on each clock tick, but the program incurs additional overhead when starting a timer. The program must insert the new timer in a sorted list and update the time of the timer that expires immediately after the new one.

Exercise 10.1

For each of the two implementation approaches described above, what is the time complexity of the interrupt handler and the start timer function in terms of the number of timers?

Answer:

Suppose there are n timers. For the first method, the interrupt handler is O(n) since all timer values must be decremented. The start timer function is O(1) since a timer can be started independently of the other timers. For the second method, the interrupt handler is usually O(1) since only the first timer value must be decremented. However, when the decrement causes the first timer to expire, the next entry has to be examined to make sure it did not expire at the same time. This algorithm can degenerate to O(n) in the worst case, but in practice the worst case is unlikely . The start timer function is O(n) to insert the timer in a sorted array but can take less than O(n) if the timer data is represented by a more complex data structure such as a heap.

If the system has a hardware interval timer instead of a simple clock, a program can set the interval timer to expire at a time corresponding to the software timer with the earliest expiration. There is no overhead unless a timer expires, one is started, or one is stopped . Interval timers are efficient when the timer intervals are long.

Exercise 10.2

Analyze the interrupt handler and the start timer function for an interval timer.

Answer:

The interrupt handler is the same order as the clock tick timer above. The complexity of starting the timer depends on how the timers are stored. If the timers are kept in a sorted array, the start timer function is O(n).

The first version of the project uses an interval timer to implement multiple timers, replacing the hardware timer by a POSIX:XSI ITIMER_REAL timer. When ITIMER_REAL expires, it generates a SIGALRM signal. The SIGALRM signal handler puts an entry in an event list sorted by order of occurrence. Each entry just contains a timer number giving a timer that expired .

Figure 10.2 shows a simple implementation of five software timers represented by the timers data structure. The individual timers (designated by [0] through [4] ) are represented by long entries in the array active . An array entry of “1 represents a timer that is not active. The events array keeps a list of timers that have expired, and numevents holds the number of unhandled events. The running variable, which holds the timer number of the currently running timer, will be needed for later parts of the project.

Figure 10.2. The timers data structure with no timers active.

Start a timer by specifying a timer number and an interval in microseconds. Figure 10.3 shows the data structure after timer [2] is started for five seconds (5,000,000 microseconds). No timers have expired, so the event list is still empty.

Figure 10.3. The timers data structure after timer [2] has been set for five seconds.

Just writing the information into the active array in Figure 10.2 is not enough to implement a timer. The program must set the ITIMER_REAL timer for 5,000,000 microseconds. On delivery of a SIGALRM signal, the program must clear the active array entry and insert an entry in the events array. Figure 10.4 shows the timers data structure after ITIMER_REAL expires.

Figure 10.4. The timers data structure after timer [2] expires.