Re: [ANNOUNCE] LinSched for v3.3-rc7

From: Michael Wang
Date: Sun Jul 22 2012 - 23:04:18 EST

Is there any latest info about the linsched?
I've not seen any updates so I'm not sure whether it is in the status to
accept patches or still need some rebuilding?

Michael Wang

On 03/15/2012 11:58 AM, Paul Turner wrote:
> Hi All,
> [ Take 2, gmail tried to a non text/plain component into the last email .. ]
> Quick start version:
> Available under linsched-alpha at:
> git:// .linsched
> NOTE: The branch history is still subject to some revision as I am
> still re-partitioning some of the patches. Once this is complete, I
> will promote linsched-alpha into a linsched branch at which point it
> will no longer be subject to history re-writes.
> After checking out the code:
> cd tools/linsched
> make
> cd tests
> ./ basic_tests
> << then try changing some scheduler parameters, e.g. sched_latency,
> and repeating >>
> (Note: The basic_tests are unit-tests, these are calibrated to the
> current scheduler tunables and should strictly be considered sanity
> tests. Please see the mcarlo-sim work for a more useful testing
> environment.)
> Extended version:
> First of all, apologies in the delay to posting this -- I know there's
> been a lot of interest. We made the choice to first rebase to v3.3
> since there were fairly extensive changes, especially within the
> scheduler, that meant we had the opportunity to significantly clean up
> some of the LinSched code. (For example, previously we were
> processing kernel/sched* using awk as a Makefile step so that we could
> extract the necessary structure information without modifying
> sched.c!) While the code benefited greatly from this, there were
> several other changes that required fairly extensive modification in
> this process (and in the meanwhile the v3.1 version became less
> representative due to the extent of the above changes); which pushed
> things out much further than I would have liked. I suppose the moral
> of the story is always release early, and often.
> That said, I'm relatively happy with the current state of integration,
> there's certainly some specific areas that can still be greatly
> improved (in particular, the main simulator loop has not had as much
> attention paid as the LinSched<>Kernel interactions and there's a long
> list of TODOs that could be improved there), but things are now mated
> fairly cleanly through the use of a new LinSched architecture. This
> is a total re-write of almost all LinSched<>Kernel interactions versus
> the previous (2.6.35) version, and has allowed us to now carry almost
> zero modifications against the kernel source. It's both possible to
> develop/test in place, as well as being patch compatible. The
> remaining touch-points now total just 20 lines! Half of these are
> likely mergable, with the other 10 lines being more LinSched specific
> at this point in time, I've broken these down below:
> The total damage:
> include/linux/init.h | 6 ++++++ (linsched ugliness,
> unfortunately necessary until we boot-strap proper initcall support)
> include/linux/rcupdate.h | 3 +++ (only necessary to allow -O0
> compilation which is extremely handy for analyzing the scheduler using
> gdb)
> kernel/pid.c | 4 ++++ (linsched ugliness,
> these can go eventually)
> kernel/sched/fair.c | 2 +- (this is just the
> promotion of 1 structure and function from static state which weren't
> published in the sched/ re-factoring that we need from within the
> simulator)
> kernel/sched/stats.c | 2 +-
> kernel/time/timekeeping.c | 3 ++- (this fixes a time-dilation
> error due to rounding when our clock-source has ns-resolution, e.g.
> shift==1)
> 6 files changed, 17 insertions(+), 3 deletions(-)
> Summarized changes vs 2.6.35 (previous version):
> - The original LinSched (understandably) simplified many of the kernel
> interactions in order to make simulation easier. Unfortunately, this
> has serious side-effects on the accuracy of simulation. We've now
> introduced a large portion of this state, including: irq and soft-irq
> contexts (we now perform periodic load-balance out of SCHED_SOFTIRQ
> for example), support for active load-balancing, correctly modeled
> nohz interactions, ipi and stop-task support.
> - Support for record and replay of application scheduling via perf.
> This is not yet well integrated, but under tests exist the tools to
> record an applications behavior using perf sched record, and then play
> it back in the simulator.
> - Load-balancer scoring. This one is a very promising new avenue for
> load-balancer testing. We analyzed several workloads and found that
> they could be well-modeled using a log-normal distribution.
> Parameterizing these models then allows us to construct a large (500)
> test-case set of randomly generated workloads that behave similarly.
> By integrating the variance between the current load-balance and an
> offline computed (currently greedy first-fit) balance we're able to
> automatically identify and score an approximation of our distance from
> an ideal load-balance. Historically, such scores are very difficult
> to interpret, however, that's where our ability to generate a large
> set of test-cases above comes in. This allows us to exploit a nice
> property, it's much easier to design a scoring function that diverges
> (in this case the variance) than a nice stable one that converges. We
> can then catch regressions in load-balancer quality by measuring the
> divergence in this set of scoring functions across our set of
> test-cases. This particular feature needs a large set of
> documentation in itself (todo), but to get started with playing with
> it see Makefile.mcarlo-sims in tools/linsched/tests. In particular to
> evaluate the entire set across a variety of topologies the following
> command can be issued:
> make -j <num_cpus * 2 > -f Makefile.mcarlo-sims
> (The included 'diff-mcarlo-500' tool can then be used to make
> comparisons across result sets.)
> - Validation versus real hardware. Under tests/validation we've
> included a tool for replaying and recording the above simulations on a
> live-machine. These can then be compared to simulated runs using the
> tools above to ensure that LinSched is modelling your architecture
> reasonably appropriately. We did some reasonably extensive
> comparisons versus several x86 topologies in the v3.1 code using this;
> it's a fundamentally hard problem -- in particular there's much more
> clock drift between events on real hardware, but the results showed
> the included topologies to be a reasonable simulacrum under LinSched.
> What's to come?
> - More documentation, especially about the use of the new
> load-balancer scoring tools.
> - The history is very coarse right now as a result of going through a
> rebase cement-mixer. I'd like to incrementally refactor some of the
> larger commits; once this is done I will promote linsched-alpha to a
> stable linsched branch that won't be subject to history re-writes.
> - KBuild integration. We currently build everything out of the
> tools/linsched makefiles. One of the immediate TODOs involves
> re-working the arch/linsched half of this to work with kbuild so that
> its less hacky/fragile.
> - Writing up some of the existing TODOs as starting points for anyone
> who wants to get involved.
> I'd also like to take a moment to specially recognize the effort of
> the following contributors, all of whom were involved extensively in
> the work above. Things have come a long way since the 5000 lines of
> "#ifdef LINSCHED", the current status would not be possible without
> them.
> Ben Segall, Dhaval Giani, Ranjit Manomohan, Nikhil Rao, and Abhishek
> Srivastava
> Thanks!
> --
> 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

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