Date: Sat, 14 Aug 1999 05:51:17 +0800 From: Peter Wemm <peter@netplex.com.au> To: "Brian McGroarty" <BMCGROARTY@high-voltage.com> Cc: "Alan Cox" <alc@cs.rice.edu>, "Josep Maria M. Blanquer" <blanquer@cs.ucsb.edu>, "freebsd-smp" <freebsd-smp@FreeBSD.ORG> Subject: Re: Questions Message-ID: <19990813215117.717011C1E@overcee.netplex.com.au> In-Reply-To: Your message of "Fri, 13 Aug 1999 15:11:00 CST." <6E585390B950D31186D50008C7333C82@high-voltage.com>
next in thread | previous in thread | raw e-mail | index | archive | help
"Brian McGroarty" wrote: > Does this selection mode skew overall processor allocation measurably? > > I imagine allocation is severely skewed by roundrobin() between schedcpu() > calls, but then the high p_estcpu bumps the favored task down a run level > queue, compensating with a moment of being starved a processor. > > The worst case would then be a high priority task with a goodly sized pool of > others a few run queue levels down. The process would race and then bob down, > float up as p_estcpu is averaged down through schedcpu() calls, soon climb a > layer back up for its higher priority, then race and pitch downward again. To give a better picture of what's going on: - we have 128 scheduler "priority levels" at present. - these levels are mapped onto 32 run queues. ie: levels 0, 1, 2, 3 would get inserted into run queue 0. 4,5,6,7 go in queue 1, etc. - we keep a queue busy bit which indicates which queues have something. Under the old algorithm, at switch time, we would pick off the process from the head of the highest priority queue and run it. When it's quantum was up, it would be placed at the back of it's runlevel queue. That's it. If we have 3 processes in the priority range 0,1,2,3, then they get even cpu time for the whole second until the next reschedule happens to rebalance things up. Under my initial hack, instead of just taking the leading process from the highest prority queue, it walks the queue instead and takes the first process that was last on the current cpu. When finishing, it gets put on the back of it's queue and selection happens again. As terry says, this is *far* from optimal, but subjectively it seems to work a heck of a lot better than what we have now. The main flaws: - we only reschedule() once every second, which means that if we get 4 processes in the top queue, and 3 were on cpu 0 and one was last on cpu 1, then cpu0 will split itself between 3 processes for a whole second and cpu1 will spend all it's time on the 4th process. - if the 4th process happens to be a nice 19 process that's been kicked up to top priority due to starvation, then it could well run at higher priority than a the three normal processes if it had the whole cpu to itself. This lack of granularity really sucks and hurts a lot when running things like rc5des etc in the background, even on a single cpu system. It's very spectacular when you have a graphical program running. For one second, it runs at full speed. The next second, it runs at half speed as it's sharing the top run queue with rc5des. Then, it's back to full speed again, and so on every second. I made a few tweaks here a while ago to enable speeding up the scheduler that fixed this, but bde said he had other patches to fix it properly. I ended up frying my patch set somehow and never got back to it. When bde committed his changes, it made little difference here. I think it now takes 1/4 of a second for the lower priority process to loose the top priority now. I think the SMP "BETTER_CLOCK" stuff does similar things. Cheers, -Peter To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-smp" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19990813215117.717011C1E>