From owner-freebsd-current@FreeBSD.ORG Fri Jan 5 00:05:18 2007 Return-Path: X-Original-To: current@freebsd.org Delivered-To: freebsd-current@FreeBSD.ORG Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 37DD016A417; Fri, 5 Jan 2007 00:05:18 +0000 (UTC) (envelope-from jroberson@chesapeake.net) Received: from webaccess-cl.virtdom.com (webaccess-cl.virtdom.com [216.240.101.25]) by mx1.freebsd.org (Postfix) with ESMTP id EF05213C441; Fri, 5 Jan 2007 00:05:17 +0000 (UTC) (envelope-from jroberson@chesapeake.net) Received: from [10.0.0.1] (216-160-98-154.tukw.qwest.net [216.160.98.154]) (authenticated bits=0) by webaccess-cl.virtdom.com (8.13.6/8.13.6) with ESMTP id l0505EC0028075 (version=TLSv1/SSLv3 cipher=DHE-DSS-AES256-SHA bits=256 verify=NO); Thu, 4 Jan 2007 19:05:16 -0500 (EST) (envelope-from jroberson@chesapeake.net) Date: Thu, 4 Jan 2007 16:03:51 -0800 (PST) From: Jeff Roberson X-X-Sender: jroberson@10.0.0.1 To: David Xu In-Reply-To: <200701050749.49058.davidxu@freebsd.org> Message-ID: <20070104155755.Y552@10.0.0.1> References: <20070104005625.D1508@10.0.0.1> <459CCBA1.40305@freebsd.org> <200701050749.49058.davidxu@freebsd.org> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Cc: Kip Macy , current@freebsd.org Subject: Re: ULE 2.0 X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 05 Jan 2007 00:05:18 -0000 On Fri, 5 Jan 2007, David Xu wrote: > On Friday 05 January 2007 03:31, Kip Macy wrote: >> 4BSD is robust, but I wouldn't say it scales well. The way its decay >> scheduling is implemented is very centered around having one queue. The >> algorithm also does not have any way of taking more complex topologies >> multi-package vs. multi-core vs. multi-thread into account. The scheduler >> isn't FreeBSD's biggest scaling problem, but it will definitely wear thin >> with time. >> >> >> -Kip > > I am not sure 4BSD was designed for single queue, I only know > it is just a dynamic priority alogrithm for time-sharing process. Well you are right in that it can be retrofitted to be more multi-cpu aware. Still I think it will be important on big system to get rid of the O(n) traversal of all threads. > Within large system, you may have to split resource into some > regions and hierarchies, each region will have a load average, > (current we only have single load average), thread may always > have affinity with region resources, the region may have a global > run queue which for example is designed for real-time thread or > kernel thread which should be run as soon as possible, > user or less important thread can be on per-cpu queue. > Current, the problem in ULE and Linux scheduler is they don't > care priority balance, a CPU may have many high priority threads > while another CPU may only have few of them, while all alogrithm > are designed based on priority scheduling, this problem can In ULE we try to handle realtime threads on the cpu that dispatched them so they get the lowest possible latency. I have noticed this problem of priority disparity myself. Part of it was that with the two queue system it was not as practical to try to balance based on priority because priority meant less than queue position. This is fixed in the new ULE. ULE does try to move higher priority threads to inactive CPUs when it does migrate, but there could be periods of short-term imbalance. It's hard to solve these without cache thrashing the run queues. > not be ignored, I have a two CPUs priority balance algorithm based > on Solaris idea,the algorithm is also cache-affinity, I must say it have > best performance when running mysql super-smack, normally I can 8% > better performance on 2-cpu system, it is still 4BSD, I don't have algorithm > for 4 cpu or more yet. since we use blockable mutex and priority > propagation, I think priority is important, if spinlock is widely used, I agree with your statement that priority is very important and that ULE did not honor it as well before. Could you tell me what the solaris algorithm is? I looked at it once and remember thinking it was quite simple and preferred to run the highest priority thread at all times, but I don't remember exactly what the algorithm was. > each spinlock looks like a critical region, then priority is less important, > Linux widely uses spinlock, it might be only of reason why it still works. I believe you are right here as well. Thanks, Jeff > > Regards, > David Xu > _______________________________________________ > freebsd-current@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-current > To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org" >