On 07.08.2017 18:55, Peter Zijlstra wrote: > On Mon, Aug 07, 2017 at 06:32:16PM +0300, Alexey Budankov wrote: >> On 07.08.2017 12:13, Peter Zijlstra wrote: >>> On Mon, Aug 07, 2017 at 10:39:13AM +0200, Peter Zijlstra wrote: >>>> On Mon, Aug 07, 2017 at 10:17:46AM +0300, Alexey Budankov wrote: >>>>> Makes sense. The implementation becomes a bit simpler. The drawbacks >>>>> may be several rotations of potentially big tree on the critical path, >>>>> instead of updating four pointers in case of the tree of lists. >>>> >>>> Yes, but like said, it allows implementing a better scheduler than RR, >>>> allowing us to fix rotation artifacts where task runtimes are near the >>>> rotation window. >> >> Could you elaborate more on the artifacts or my be share some link to the >> theory? > > In the extreme, if you construct your program such that you'll never get > hit by the tick (this used to be a popular measure to hide yourself from > time accounting)
Well, some weird thing for me. Never run longer than one tick? I could imaging some I/O bound code that would fast serve some short messages, all the other time waiting for incoming requests. Not sure if CPU events monitoring is helpful in this case. > , you'll never rotate the counters, even though you can > rack up quite a lot of runtime.> > By doing a runtime based scheduler, instead of a tick based RR, we'll > still get rotation, and the tick will only function as a forced > reprogram point. > >>>> A slightly more complicated, but also interested scheduling problem is >>>> the per-cpu flexible vs the per-task flexible. Ideally we'd rotate them >>>> at the same priority based on service, without strictly prioritizing the >>>> per-cpu events. >>>> >>>> Again, that is something that should be possible once we have a more >>>> capable event scheduler. >>>> >>>> >>>> So yes, cons and pros.. :-) >>> >>> Also, I think for AVL tree you could do the erase and (re)insert >>> combined and then rebalance in one go, not sure RB allows the same >>> thing, but it might be fun looking into. >> >> Not sure if AVL is more practical here. You get better balancing what gives >> you faster average search for the price of longer modifications >> so yes, need to measure and compare ... :-) > > Oh, I wasn't suggesting using AVL (the last thing we need is another > balanced tree in the kernel), I was merely wondering if you could do > compound/bulk updates on RB as you can with AVL. Aww, I see. >
