Ian Pratt
2005-Jun-08 21:29 UTC
RE: [Xen-devel] [PATCH] Yield to VCPU hcall, spinlock yielding
> > IMO, I don''t think this alone is enough to encourage task > migration. > > The primary motivator to steal is a 25% or more load imbalance, and > > one extra fake kernel thread will probably not be enough to > trigger this. > > The kernel thread is needed at the very least to ensure that > all user programs on the de-scheduled CPU are available for > migration. In an important case, a program on the > de-scheduled CPU holds a futex, and another CPU goes idle > because its program blocks on the futex. We''d want the idle > CPU to pick up the futex holder, and I''m assuming (with very > little actual knowledge) that the Linux scheduler would make > that happen.We might be able to come up with a cheaper hack for doing this. The notifaction scheme is already on the expensive side, and adding two extra passes through the scheduler could totally doom it.> I''d view your "cpu_power" proposal as orthogonal to (or > perhaps complementary to) our ideas on preemption > notification. It''s aimed more at load-balancing and fair > scheduling than specifically at the problems that arise with > the preemption of lock holders. On the apparent CPU speed > issue, does Linux account in any way for different interrupt > loads on different processors? Is a program just out of luck > if it happens to get scheduled on a processor with heavy > interrupt traffic, or will Linux notice that it''s not making > the same progress as its peers and shuffle things around? It > seems that your cpu_power proposal might have something to > contribute here.I don''t see it as orthogonal -- I think something like it is needed to make the notification scheme result in any benefit, otherwise no work will get migrated from the de-scheduled CPU. I''m just not sure how easy it will be to add into the rebalance function. Ian _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Bryan S Rosenburg
2005-Jun-09 12:37 UTC
RE: [Xen-devel] [PATCH] Yield to VCPU hcall, spinlock yielding
"Ian Pratt" <m+Ian.Pratt@cl.cam.ac.uk> wrote on 06/08/2005 05:29:21 PM:> We might be able to come up with a cheaper hack for doing this. The > notifaction scheme is already on the expensive side, and adding two > extra passes through the scheduler could totally doom it.I agree that whether we can tolerate the cost of preemption notification interrupts is still very much an open question. I doubt that the additional costs of unblocking and blocking a kernel thread will be decisive. I don''t view the high-priority kernel thread idea as a "hack". In conjunction with CONFIG_PREEMPT, it is a straight-forward solution to a real problem: From the notification interrupt handler, how do you get the kernel to yield as quickly as possible but only at such time as no kernel locks are held? A newly-unblocked high-priority thread will run at exactly the right time, with no new hacking on Linux locking or scheduling code. - Bryan _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Orran Y Krieger
2005-Jun-09 18:13 UTC
RE: [Xen-devel] [PATCH] Yield to VCPU hcall, spinlock yielding
"Ian Pratt" <m+Ian.Pratt@cl.cam.ac.uk> wrote on 06/08/2005 05:29:21 PM:> > I''d view your "cpu_power" proposal as orthogonal to (or > > perhaps complementary to) our ideas on preemption > > notification. It''s aimed more at load-balancing and fair > > scheduling than specifically at the problems that arise with > > the preemption of lock holders. On the apparent CPU speed > > issue, does Linux account in any way for different interrupt > > loads on different processors? Is a program just out of luck > > if it happens to get scheduled on a processor with heavy > > interrupt traffic, or will Linux notice that it''s not making > > the same progress as its peers and shuffle things around? It > > seems that your cpu_power proposal might have something to > > contribute here. > > I don''t see it as orthogonal -- I think something like it is needed to > make the notification scheme result in any benefit, otherwise no work > will get migrated from the de-scheduled CPU.I don''t get it. If an application lock is important, and all the app threads block on it except the one of the preempted processor, and the preempted processor has two threads on it (the high priority kernel and the app that was preempted), then we have one (or more) idle processors and one processor with two threads. Hopefully the scheduler is smart enough to move the preempted thread over. So, the base scheme should result in processors from staying idle.... A scheme like described above would be great, but without any changes we have a scheme that keeps processors from going idle I think.> I''m just not sure how easy it will be to add into the rebalance > function. > > Ian_______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Andrew Theurer
2005-Jun-09 18:59 UTC
Re: [Xen-devel] [PATCH] Yield to VCPU hcall, spinlock yielding
Orran Y Krieger wrote:> > > "Ian Pratt" <m+Ian.Pratt@cl.cam.ac.uk> wrote on 06/08/2005 05:29:21 PM: > > > I''d view your "cpu_power" proposal as orthogonal to (or > > > perhaps complementary to) our ideas on preemption > > > notification. It''s aimed more at load-balancing and fair > > > scheduling than specifically at the problems that arise with > > > the preemption of lock holders. On the apparent CPU speed > > > issue, does Linux account in any way for different interrupt > > > loads on different processors? Is a program just out of luck > > > if it happens to get scheduled on a processor with heavy > > > interrupt traffic, or will Linux notice that it''s not making > > > the same progress as its peers and shuffle things around? It > > > seems that your cpu_power proposal might have something to > > > contribute here. > > > > I don''t see it as orthogonal -- I think something like it is needed to > > make the notification scheme result in any benefit, otherwise no work > > will get migrated from the de-scheduled CPU. > > I don''t get it. If an application lock is important, and all the app > threads block on it except the one of the preempted processor, and the > preempted processor has two threads on it (the high priority kernel > and the app that was preempted), then we have one (or more) idle > processors and one processor with two threads. Hopefully the > scheduler is smart enough to move the preempted thread over. So, the > base scheme should result in processors from staying idle.... A > scheme like described above would be great, but without any changes we > have a scheme that keeps processors from going idle I think.I take it this assumes nothing else is running on that domain? I agree in this ideal scenerio, it would work (assumming the app threads waiting for the lock are not busy waiting), but what about apps which have other threads which don''t wait on that particular lock, keeping the other cpus busy, or a domain with more than one app running? In those cases the load balance would probably not happen, and I would think we need more than just the high prio kernel thread to move the desired task to a active virtual cpu. I''m not saying it''s all or none either. Gettng the kernel thread implemented is probably the next logial step. I would just like to follow through with some extra logic if possible.> > > I''m just not sure how easy it will be to add into the rebalance > > function.There is already an abstractoin of "load" for each cpu in 2.6.11. We just need some bits there. I will take a look. -Andrew _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Orran Y Krieger
2005-Jun-09 19:49 UTC
Re: [Xen-devel] [PATCH] Yield to VCPU hcall, spinlock yielding
habanero@us.ltcfwd.linux.ibm.com wrote on 06/09/2005 02:59:56 PM:> I take it this assumes nothing else is running on that domain? I agree > in this ideal scenerio, it would work (assumming the app threads waiting> for the lock are not busy waiting), but what about apps which have other> threads which don''t wait on that particular lock, keeping the other cpus> busy, or a domain with more than one app running? In those cases the > load balance would probably not happen, and I would think we need more > than just the high prio kernel thread to move the desired task to a > active virtual cpu.The key place where this came up in our internal discussions was running big HPC apps and big data bases... In both those cases, the dominant situation is your ideal scenario. In a multiprogrammed environment, you have the problem even without a hypervisor, i.e., a process holding a lock can be preempted by another process. Currently, Linux doesn''t do any schedular aware synchronizaiton, so presumably this is not viewed as a problem. If some day this is viewed as a problem, then the preemption upcall could be used by whatever mechanism linux chooses to implement. I am not convinced that we need a special purpose solution for virtualization... _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel