Re: [patch 13/15] sched: expire slack quota using generationcounters

From: Peter Zijlstra
Date: Wed Apr 06 2011 - 07:26:41 EST

On Wed, 2011-04-06 at 00:22 -0700, Paul Turner wrote:
> scratches head... erm right, I meant to pair this with a read barrier
> on querying the generation but balked when I realized that still
> yields an lfence on x86 since I didn't want to introduce that to the
> update_curr() path.
> While we can probably do away with the barrier completely (it's not
> critical that we line them up perfectly with the new generation), I've
> been thinking about this one and I think I have something a little
> nicer that also reduces the shared cache hits.
> We can take advantage of the fact that sched_clocks are already
> synchronized within 2 jiffies and store the quota's expiration,
> instead of a generation, when we refresh.
> This effectively yields a fairly simple control flow (we can use
> rq->clock since we're always paired with update_rq_clock operations):
> a) our rq->clock < expiration always implies quota is valid
> Obviously if our cpu clock is ahead of the one that issued the quota,
> our quota is still valid since the real deadline is even further
> behind
> Even if our cpu's clock is behind the max 1.99 jiffies the amount of
> time that the stale quota can remain valid is basically already within
> our potential margin of error since for a long running process we
> check on each tick edge anyway.
> b) our rq->clock > expiration
> Again there's two cases, if our cpu clock is behind (or equal) then
> the deadline has indeed passed and the quota is expired. This can be
> confirmed by comparing the global deadline with our local one (the
> global expiration will have advanced with quota refresh for this to be
> true).
> We can also catch that our cpu is potentially ahead -- by the fact
> that our rq->clock > expiration but that the global expiration has not
> yet advanced. In this case we recognize that our quota is still valid
> and extend our local expiration time by either the maximum margin of
> error or some fraction there of (say 1 jiffy) which is guaranteed to
> push us back in case a) above. Again this is within our existing
> margin of error due to entity_tick() alignment.
> This ends up looking a lot simpler and avoids much of the pressure on
> the global variable since we need to compare against it in the case
> where our clock passes expiration, once a quota period (as the
> extension will put us in case a where we know we don't need to
> consider it).
> This ends up simpler than the generation muck and can be introduced
> cleanly earlier in the series, avoiding the churn mentioned above.
> Make sense?

Yes, that ought to work.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at