lkml.org 
[lkml]   [2005]   [Oct]   [19]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: kernel/timer.c design
    Ingo,

    Thanks for the excellent description of the timer wheel
    implementation.

    Ingo Molnar wrote:
    > One cost is the burstiness of processing: a single step of cascading can
    > take many timers to be processed (if they happen to be in that same
    > bucket)...

    > But there's a hidden win as well from this approach: if a timer is
    > removed before it expires, we've saved the remaining cascading steps!
    > This happens surprisingly often: on a busy networked server, the
    > majority of the timers never expire, and are removed before they have to
    > be cascaded even once.

    Unfortunately, this means that the actual costs of the wheel
    implementation vary depending on the relationship between HZ,
    the average timeout duration, and the bucket mappings (which,
    as you say, can be adjusted for size reasons.) This is one of
    the downsides of the wheel implementation. It's very difficult
    to tell in advance whether a particular timer load
    will cascade or not, making the costs (although bounded)
    unexpectedly variable.

    One solution (even suggested by Linus) for high resolution
    timers was to increase HZ and skip timer ticks. Unfortunately,
    this has a dramatic affect on the cost of cascading, and on
    the maximum duration available for timers. (By increasing
    HZ, you push more timers to higher tiers in the wheel, which
    means you potentially end up cascading them more often,
    even when they are removed before expiry.) These types
    of unexpected consequences are one good reason for avoiding
    use of the wheel for high res timers.

    =============================
    Tim Bird
    Architecture Group Chair, CE Linux Forum
    Senior Staff Engineer, Sony Electronics
    =============================

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-10-19 19:51    [W:0.183 / U:430.028 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site