Книга: Real-Time Concepts for Embedded Systems
11.6.2 Hierarchical Timing Wheels
11.6.2 Hierarchical Timing Wheels
The timer overflow problem presented in the last section can be solved using the hierarchical timing wheel approach.
The soft-timer facility needs to accommodate timer events spanning a range of values. This range can be very large. For example accommodating timers ranging from 100ms to 5 minutes requires a timing wheel with 3,000 (5 ? 60 ? 10) entries. Because the timer facility needs to have a granularity of at least 100ms and there is a single array representing the timing wheel,
10 ? 100ms = 1 sec
10 entries/sec
60 sec = 1 minute
60 ? 10 entries / min
therefore:
5 ? 60 ? 10 = total number of entries needed for the timing wheel with a granularity of 100ms.
A hierarchical timing wheel is similar to a digital clock. Instead of having a single timing wheel, multiple timing wheels are organized in a hierarchical order. Each timing wheel in the hierarchy set has a different granularity. A clock dial is associated with each timing wheel. The clock dial turns by one unit when the clock dial at the lower level of the hierarchy wraps around. Using a hierarchical timing wheel requires only 75 (10 + 60 + 5) entries to allow for timeouts with 100ms resolution and duration of up to 5 minutes.
With a hierarchical timing wheels, there are multiple arrays, therefore
10 ? 100ms = 1 sec
10 entries/sec
the 1st array (leftmost array as shown in Figure 11.16)
Figure 11.16: A hierarchical timing wheel.
60 sec = 1 minute
60 entries / min
the 2nd array (middle array shown in Figure 11.16)
5 entries for 5 minutes
3rd array
therefore:
5 + 60 + 10 = total number of entries needed for the hierarchal timing wheels.
The reduction in space allows for the construction of higher precision timer facilities with a large range of timeout values. Figure 11.16 depicts this concept.
For example, it is possible to install timeouts of 2 minutes, 4 seconds, and 300 milliseconds. The timeout handler is installed at the 2-minute slot first. The timeout handler determines that there are still 4.3 seconds to go when the 2 minutes is up. The handler installs itself at the 4-second timeout slot. Again, when 4 seconds have elapsed, the same handler determines that 300 milliseconds are left before expiring the timer. Finally, the handler is reinstalled at the 300-millisecond timeout slot. The real required work is performed by the handler when the last 300ms expire.
Оглавление книги
