lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Tue, 24 Apr 2007 11:01:39 -0700 From: "Li, Tong N" <tong.n.li@...el.com> To: Bill Huey <billh@...ppy.monkey.org> Cc: Jeremy Fitzhardinge <jeremy@...p.org>, Linus Torvalds <torvalds@...ux-foundation.org>, Ingo Molnar <mingo@...e.hu>, Nick Piggin <npiggin@...e.de>, Juliusz Chroboczek <jch@....jussieu.fr>, Con Kolivas <kernel@...ivas.org>, ck list <ck@....kolivas.org>, Bill Davidsen <davidsen@....com>, Willy Tarreau <w@....eu>, William Lee Irwin III <wli@...omorphy.com>, linux-kernel@...r.kernel.org, Andrew Morton <akpm@...ux-foundation.org>, Mike Galbraith <efault@....de>, Arjan van de Ven <arjan@...radead.org>, Peter Williams <pwil3058@...pond.net.au>, Thomas Gleixner <tglx@...utronix.de>, caglar@...dus.org.tr, Gene Heskett <gene.heskett@...il.com> Subject: Re: [REPORT] cfs-v4 vs sd-0.44 On Mon, 2007-04-23 at 18:57 -0700, Bill Huey wrote: > On Mon, Apr 23, 2007 at 05:59:06PM -0700, Li, Tong N wrote: > > I don't know if we've discussed this or not. Since both CFS and SD claim > > to be fair, I'd like to hear more opinions on the fairness aspect of > > these designs. In areas such as OS, networking, and real-time, fairness, > > and its more general form, proportional fairness, are well-defined > > terms. In fact, perfect fairness is not feasible since it requires all > > runnable threads to be running simultaneously and scheduled with > > infinitesimally small quanta (like a fluid system). So to evaluate if a > > Unfortunately, fairness is rather non-formal in this context and probably > isn't strictly desirable given how hack much of Linux userspace is. Until > there's a method of doing directed yields, like what Will has prescribed > a kind of allotment to thread doing work for another a completely strict > mechanism, it is probably problematic with regards to corner cases. > > X for example is largely non-thread safe. Until they can get their xcb > framework in place and addition thread infrastructure to do hand off > properly, it's going to be difficult schedule for it. It's well known to > be problematic. I agree. I just think calling the designs "perfectly" or "completely" fair is too strong. It might cause unnecessary confusion that overshadows the actual merits of these designs. If we were to evaluate specifically the fairness aspect of a design, then I'd suggest defining it more formally. > You announced your scheduler without CCing any of the relevant people here > (and risk being completely ignored in lkml traffic): > > http://lkml.org/lkml/2007/4/20/286 > > What is your opinion of both CFS and SDL ? How can you work be useful > to either scheduler mentioned or to the Linux kernel on its own ? I like SD for its simplicity. My concern with CFS is the RB tree structure. Log(n) seems high to me given the fact that we had an O(1) scheduler. Many algorithms achieve strong fairness guarantees at the cost of log(n) time. Thus, I tend to think, if log(n) is acceptable, we might want also to look at other algorithms (e.g., start-time first) with better fairness properties and see if they could be extended to be general purpose. > > I understand that via experiments we can show a design is reasonably > > fair in the common case, but IMHO, to claim that a design is fair, there > > needs to be some kind of formal analysis on the fairness bound, and this > > bound should be proven to be constant. Even if the bound is not > > constant, at least this analysis can help us better understand and > > predict the degree of fairness that users would experience (e.g., would > > the system be less fair if the number of threads increases? What happens > > if a large number of threads dynamically join and leave the system?). > > Will has been thinking about this, but you have to also consider the > practicalities of your approach versus Con's and Ingo's. I consider my work an approach to extend an existing scheduler to support proportional fairness. I see many proportional-share designs are lacking things such as good interactive support that Linux does well. This is why I designed it on top of the existing scheduler so that it can leverage things such as dynamic priorities. Regardless of the underlying scheduler, SD or CFS, I think the algorithm I used would still apply and thus we can extend the scheduler similarly. > I'm all for things like proportional scheduling and the extensions > needed to do it properly. It would be highly relevant to some version > of the -rt patch if not that patch directly. I'd love it to be considered for part of the -rt patch. I'm new to this, so would you please let me know what to do? Thanks, tong - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists