Li, Tong N wrote:
Thanks for the excellent explanation. I think EEVDF and many algs alike
assume global ordering of all tasks in the system (based on virtual
time), whereas CFS does so locally on each processor and relies on load
balancing to achieve fairness across processors. It'd achieve strong
fairness locally, but I'm not sure about its global fairness properties
in an MP environment. If ideally the total load weight on each processor
is always the same, then local fairness would imply global fairness, but
this is a bin packing problem and is intractable ...
First, I am not assuming a global ordering of all tasks. As the current
implementation, EEVDF should maintain virtual time locally for each CPU.
EEVDF is a proportional time share scheduler, therefore the relative
weight and actual cpu share for each task varies when tasks join and
leave. There will be not bin-pack problem for such systems.
I understand that bin-pack problem does exist in Real-time world.
Suppose in a system has 2 cpus, there a 3 tasks, all of which needs to
finish 30ms work within a window of 50ms. Any 2 of them stay together
will exceeds the bandwidth of one cpu. There is a bin-pack problem,
unless the system has to be clever enough to break one of them down into
2 requests of 15ms/25ms, and execute them on different cpus at different
time without overlap, which is quite difficult :-)
In the proportional world, weights and cpu share are scale to fit with
the bandwidth of a cpu. Therefore putting 2 of them on one cpu is fine,
and the fairness for each cpu is preserved. On the other hand, moving
one task back and forth among 2 cpus do give better throughput and
better global fairness. I have not dig into the load balancing
algorithms of SMP yet, so I leave it aside for now, first thing first :-)
Thanks !
Ting
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
