Re: Scheduler changes?
On Sun, 11 Jun 2000, Luigi Rizzo wrote: > Hi, > i understand that this means maybe a somwthat > large change in the system, but what do you think > if we have a lok at implementing the CPU scheduler using > weights instead of strict priorities ? > Do we have parts of the kernel which rely on priority > to implement locking etc ? > > This would not be too different from what the EclipseBSD people > did, and the code i recently committed to dummynet can be easily > reused to this purpose, and it is efficient. > > With a little bit of guidance (I am not too familiar with that area > of the code) i think we can do something good with little > effort. I've been thinking about this a lot. As for the current scheduler, a NICE_WEIGHT of 1.8 seems to work nicely; see the attached patch. I have been looking more into making things more like Eclipse. I have to say I'm very impressed with their work in implementing QoS, and we would do well to update some of our ancient designs to a model that resembles theirs. I'm looking at their process and disk scheduler now, after reading their network scheduling paper from the Usenix proceedings. I'm very interested in finding a better algorithm than the current one, yes :) > cheers > luigi -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' Index: sys/kern/kern_synch.c === RCS file: /usr2/ncvs/src/sys/kern/kern_synch.c,v retrieving revision 1.95 diff -u -r1.95 kern_synch.c --- sys/kern/kern_synch.c 2000/07/04 11:25:23 1.95 +++ sys/kern/kern_synch.c 2000/07/08 00:20:23 @@ -916,7 +916,7 @@ if (p->p_rtprio.type == RTP_PRIO_NORMAL) { newpriority = PUSER + p->p_estcpu / INVERSE_ESTCPU_WEIGHT + - NICE_WEIGHT * (p->p_nice - PRIO_MIN); + (p->p_nice - PRIO_MIN) * NICE_WEIGHT; newpriority = min(newpriority, MAXPRI); p->p_usrpri = newpriority; } Index: sys/sys/proc.h === RCS file: /usr2/ncvs/src/sys/sys/proc.h,v retrieving revision 1.106 diff -u -r1.106 proc.h --- sys/sys/proc.h 2000/06/22 22:27:16 1.106 +++ sys/sys/proc.h 2000/07/08 00:21:14 @@ -405,10 +405,10 @@ * the range 100-256 Hz (approximately). */ #defineINVERSE_ESTCPU_WEIGHT 8 /* 1 / (priorities per estcpu level) */ -#defineNICE_WEIGHT 1 /* priorities per nice level */ +#defineNICE_WEIGHT 9 / 5 /* priorities per nice level */ #definePPQ (128 / NQS) /* priorities per queue */ #defineESTCPULIM(e) \ -min((e), INVERSE_ESTCPU_WEIGHT * (NICE_WEIGHT * PRIO_TOTAL - PPQ) + \ +min((e), INVERSE_ESTCPU_WEIGHT * (PRIO_TOTAL * NICE_WEIGHT - PPQ) + \ INVERSE_ESTCPU_WEIGHT - 1) extern u_long ps_arg_cache_limit;
Re: Scheduler changes?
Hi, i understand that this means maybe a somwthat large change in the system, but what do you think if we have a lok at implementing the CPU scheduler using weights instead of strict priorities ? Do we have parts of the kernel which rely on priority to implement locking etc ? This would not be too different from what the EclipseBSD people did, and the code i recently committed to dummynet can be easily reused to this purpose, and it is efficient. With a little bit of guidance (I am not too familiar with that area of the code) i think we can do something good with little effort. cheers luigi > On Sun, 11 Jun 2000, Jacob A. Hart wrote: > > > On Fri, Jun 09, 2000 at 08:28:06PM -0400, Brian Fundakowski Feldman wrote: > > > > > >The diff should make a process at -20 which uses all available CPU > > > schedule just slightly the ahead of a process at +20 which uses no CPU. > > > A process which uses full CPU at 0 niceness would have a priority of > > > 128, whereas a process using no CPU at 0 niceness would have a priority > > > of 90. All processes will always have a priority less than or equal to > > > 128, which is the priority at which a process with a niceness of +20 > > > always runs at. A +20 process won't get better priority than anything > > > else, period. Try it out, see how it works for you:) > > > > I tried this patch today. > > > > While it didn't quite fix the problem, it sure made for some interesting > > pacman gameplay. ;-) > > Yeah, I tried it out myself. I didn't actually think beforehand (hence the > testing...) why it would be bad for a process of niceness -20 to always > have better than the last priority in every case... I tried it with > MAME and it took a long time before my "escape" key event registered > (X not getting run...). > > I'm thinking of ways to make the algorithm both good for people who need > (err... want) low-priority background processes only to run when there's > free time, and high-priority processes run but not to the exclusion of > everything else. The whole scheduling algorithm proper is quite tricky > to do very well; previously, it had most of the properties we want, but > it also easily allowed for deadlocks. > > > Using idprio as Volodymyr suggested seems to be a viable workaround. You > > mentioned in another message that idprio could potentially deadlock my > > machine, though. Under what conditions could this happen (and how likely > > is it to occur)? > > > > > > -jake > > > > -- > > Jacob A. Hart <[EMAIL PROTECTED]> > > Powered by: FreeBSD 5.0-CURRENT #18: Sun Jun 11 19:25:03 EST 2000 > > > > -- > Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / > [EMAIL PROTECTED]`--' > > > > To Unsubscribe: send mail to [EMAIL PROTECTED] > with "unsubscribe freebsd-current" in the body of the message > To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Sun, 11 Jun 2000, Jacob A. Hart wrote: > On Fri, Jun 09, 2000 at 08:28:06PM -0400, Brian Fundakowski Feldman wrote: > > > >The diff should make a process at -20 which uses all available CPU > > schedule just slightly the ahead of a process at +20 which uses no CPU. > > A process which uses full CPU at 0 niceness would have a priority of > > 128, whereas a process using no CPU at 0 niceness would have a priority > > of 90. All processes will always have a priority less than or equal to > > 128, which is the priority at which a process with a niceness of +20 > > always runs at. A +20 process won't get better priority than anything > > else, period. Try it out, see how it works for you:) > > I tried this patch today. > > While it didn't quite fix the problem, it sure made for some interesting > pacman gameplay. ;-) Yeah, I tried it out myself. I didn't actually think beforehand (hence the testing...) why it would be bad for a process of niceness -20 to always have better than the last priority in every case... I tried it with MAME and it took a long time before my "escape" key event registered (X not getting run...). I'm thinking of ways to make the algorithm both good for people who need (err... want) low-priority background processes only to run when there's free time, and high-priority processes run but not to the exclusion of everything else. The whole scheduling algorithm proper is quite tricky to do very well; previously, it had most of the properties we want, but it also easily allowed for deadlocks. > Using idprio as Volodymyr suggested seems to be a viable workaround. You > mentioned in another message that idprio could potentially deadlock my > machine, though. Under what conditions could this happen (and how likely > is it to occur)? > > > -jake > > -- > Jacob A. Hart <[EMAIL PROTECTED]> > Powered by: FreeBSD 5.0-CURRENT #18: Sun Jun 11 19:25:03 EST 2000 > -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
>Using idprio as Volodymyr suggested seems to be a viable workaround. You >mentioned in another message that idprio could potentially deadlock my >machine, though. Under what conditions could this happen (and how likely >is it to occur)? idprio can lead to a system hang due to priority inversion. For example, suppose that an idprio process does disk I/O and locks a critical resource (such as the vnode for the '/' directory) prior to doing that. Then also suppose that a normal process is in a permanent run state (loop: goto loop). When the I/O completes on the idprio process, it will never be given an opportunity to release the vnode lock. Eventually just about everything in the system will deadlock waiting on that resource and the system will essentially hang. The work-around for this is to temporarily increase the priority of idprio processes while they execute in the kernel, but this hasn't yet been implemented. The above scenario can happen pretty easily if you have an idprio process doing a normal mix of file operations - all you need then is normal priority process(es) to eat all the CPU for long periods - even a few seconds can be very annoying to interactive users. -DG David Greenman Co-founder, The FreeBSD Project - http://www.freebsd.org Manufacturer of high-performance Internet servers - http://www.terasolutions.com Pave the road of life with opportunities. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Sun, Jun 11, 2000 at 08:03:22PM +1000, Jacob A. Hart wrote: > Using idprio as Volodymyr suggested seems to be a viable workaround. You > mentioned in another message that idprio could potentially deadlock my > machine, though. Under what conditions could this happen (and how likely > is it to occur)? That things were beautifully described in [id|rt]prio man page. idprio makes process idle, so it gets only time slices left _after_ ditributing them among normal processes. rtprio makes process priority realtime so each time slice is distributed to this process and only leftover went to system. If you make rtprio dnetc, the system near hangs and understands only three buttons but one minute after pressing them.. ;) So using idprio would not hang the machine. -- [WBR], Arcade Zardos. [AIST] [SAT Astronomy//Think to survive!] [mp3.aist.net] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Fri, Jun 09, 2000 at 08:28:06PM -0400, Brian Fundakowski Feldman wrote: > >The diff should make a process at -20 which uses all available CPU > schedule just slightly the ahead of a process at +20 which uses no CPU. > A process which uses full CPU at 0 niceness would have a priority of > 128, whereas a process using no CPU at 0 niceness would have a priority > of 90. All processes will always have a priority less than or equal to > 128, which is the priority at which a process with a niceness of +20 > always runs at. A +20 process won't get better priority than anything > else, period. Try it out, see how it works for you:) I tried this patch today. While it didn't quite fix the problem, it sure made for some interesting pacman gameplay. ;-) Using idprio as Volodymyr suggested seems to be a viable workaround. You mentioned in another message that idprio could potentially deadlock my machine, though. Under what conditions could this happen (and how likely is it to occur)? -jake -- Jacob A. Hart <[EMAIL PROTECTED]> Powered by: FreeBSD 5.0-CURRENT #18: Sun Jun 11 19:25:03 EST 2000 PGP signature
Re: Scheduler changes?
On Sat, Jun 10, 2000 at 10:56:00AM +0300, Volodymyr Kostyrko wrote: > > I think this is not the clear solution for descibed problem 'couse the > dnetc client still gets a priority and still have the share of time while > other programs might run. For me idprio works great. Just change last > string in the starting shell scipt. > > idprio 31 su nobody -c "$dir/dnetc -quiet" 2>/dev/null >/dev/null & I had no idea this wonderful little utility existed. It's a godsend! Thanks. -jake -- Jacob A. Hart <[EMAIL PROTECTED]> Powered by: FreeBSD 5.0-CURRENT #17: Fri Jun 9 21:58:34 EST 2000 "One world, one web, one program" -- Microsoft promotional ad "Ein Volk, ein Reich, ein Fuehrer" -- Adolf Hitler To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Sat, 10 Jun 2000, Volodymyr Kostyrko wrote: > On Fri, Jun 09, 2000 at 08:28:06PM -0400, Brian Fundakowski Feldman wrote: > >It's an issue. Nice values count for less than before due to fixes > > that Luoqi Chen made (and I committed). The behavior now isn't optimal, > > but it is better than the system locking up. NICE_WEIGHT might be okay > > to keep at 2. Try the attached diff; I'm pretty sure it won't blow > > things up :) > >The diff should make a process at -20 which uses all available CPU > > schedule just slightly the ahead of a process at +20 which uses no CPU. > > A process which uses full CPU at 0 niceness would have a priority of > > 128, whereas a process using no CPU at 0 niceness would have a priority > > of 90. All processes will always have a priority less than or equal to > > 128, which is the priority at which a process with a niceness of +20 > > always runs at. A +20 process won't get better priority than anything > > else, period. Try it out, see how it works for you:) > > I think this is not the clear solution for descibed problem 'couse the dnetc >client still gets a priority and still have the share of time while other programs >might run. For me idprio works great. Just change last string in the starting shell >scipt. There is no clear solution at all... try it out. Of _course_ it still gets a share of the time. If it didn't, then it could deadlock the system (like idprio and rtprio both can). > idprio 31 su nobody -c "$dir/dnetc -quiet" 2>/dev/null >/dev/null & > > -- > [WBR], Arcade Zardos. [AIST] [SAT Astronomy//Think to survive!] [mp3.aist.net] -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Fri, Jun 09, 2000 at 08:28:06PM -0400, Brian Fundakowski Feldman wrote: >It's an issue. Nice values count for less than before due to fixes > that Luoqi Chen made (and I committed). The behavior now isn't optimal, > but it is better than the system locking up. NICE_WEIGHT might be okay > to keep at 2. Try the attached diff; I'm pretty sure it won't blow > things up :) >The diff should make a process at -20 which uses all available CPU > schedule just slightly the ahead of a process at +20 which uses no CPU. > A process which uses full CPU at 0 niceness would have a priority of > 128, whereas a process using no CPU at 0 niceness would have a priority > of 90. All processes will always have a priority less than or equal to > 128, which is the priority at which a process with a niceness of +20 > always runs at. A +20 process won't get better priority than anything > else, period. Try it out, see how it works for you:) I think this is not the clear solution for descibed problem 'couse the dnetc client still gets a priority and still have the share of time while other programs might run. For me idprio works great. Just change last string in the starting shell scipt. idprio 31 su nobody -c "$dir/dnetc -quiet" 2>/dev/null >/dev/null & -- [WBR], Arcade Zardos. [AIST] [SAT Astronomy//Think to survive!] [mp3.aist.net] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Sun, 28 May 2000, Jacob A. Hart wrote: > I remember the scheduler bug you're talking about. My system feels much > the same as it did during 4.0-CURRENT when that bug was active. I had a > collection of wrapper scripts for CPU intensive programs that suspended > rc5des, ran the program, then reenabled it again. Should have held on to > them, I guess. Check out http://people.FreeBSD.org/~green/mean.c. > > If this change > > fixes things for you, please report it asap, since my understanding is > > that this problem is rather elusive and annoying. > > No, it didn't work, unfortunately. To test it, I renice'd rc5des to a > couple of different values while encoding an MP3. It's an issue. Nice values count for less than before due to fixes that Luoqi Chen made (and I committed). The behavior now isn't optimal, but it is better than the system locking up. NICE_WEIGHT might be okay to keep at 2. Try the attached diff; I'm pretty sure it won't blow things up :) The diff should make a process at -20 which uses all available CPU schedule just slightly the ahead of a process at +20 which uses no CPU. A process which uses full CPU at 0 niceness would have a priority of 128, whereas a process using no CPU at 0 niceness would have a priority of 90. All processes will always have a priority less than or equal to 128, which is the priority at which a process with a niceness of +20 always runs at. A +20 process won't get better priority than anything else, period. Try it out, see how it works for you:) -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' --- /usr/src/sys/sys/proc.h Fri May 26 20:15:46 2000 +++ /home/green/tmp/proc.h Fri Jun 9 20:13:30 2000 @@ -405,10 +405,10 @@ * the range 100-256 Hz (approximately). */ #defineINVERSE_ESTCPU_WEIGHT 8 /* 1 / (priorities per estcpu level) */ -#defineNICE_WEIGHT 1 /* priorities per nice level */ +#defineNICE_WEIGHT 2 /* priorities per nice level */ #definePPQ (128 / NQS) /* priorities per queue */ #defineESTCPULIM(e) \ -min((e), INVERSE_ESTCPU_WEIGHT * (NICE_WEIGHT * PRIO_TOTAL - PPQ) + \ +min((e), INVERSE_ESTCPU_WEIGHT * (NICE_WEIGHT * PRIO_TOTAL / 2 - PPQ) + \ INVERSE_ESTCPU_WEIGHT - 1) extern u_long ps_arg_cache_limit; To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Mon, 29 May 2000, Bruce Evans wrote: > Scheduling was broken in -current on 2004/04/30 11:33:44 PDT. "nice -20" in > -current does essentially the same thing as "nice -10" in 4.0 (not enough > even in 4.0). hmmm... so there's a few years to wait before we have to worry.. :-) > > Bruce > > -- :{ [EMAIL PROTECTED] Andy Farkas System Administrator Speednet Communications http://www.speednet.com.au/ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Sun, 28 May 2000, Jacob A. Hart wrote: > I remember the scheduler bug you're talking about. My system feels much > the same as it did during 4.0-CURRENT when that bug was active. I had a Scheduling was broken in -current on 2004/04/30 11:33:44 PDT. "nice -20" in -current does essentially the same thing as "nice -10" in 4.0 (not enough even in 4.0). Bruce To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Sat, May 27, 2000 at 12:38:36PM -0700, Doug Barton wrote: > > Try setting the nice value for rc5 to something lower than 20, but > higher than the highest (lowest) value running on your system. There was > a bug with the scheduler in the past that items run at nice 20 were > actually getting more cpu than they were supposed to. I remember the scheduler bug you're talking about. My system feels much the same as it did during 4.0-CURRENT when that bug was active. I had a collection of wrapper scripts for CPU intensive programs that suspended rc5des, ran the program, then reenabled it again. Should have held on to them, I guess. > If this change > fixes things for you, please report it asap, since my understanding is > that this problem is rather elusive and annoying. No, it didn't work, unfortunately. To test it, I renice'd rc5des to a couple of different values while encoding an MP3. When niced at: +10 rc5des chewed ~40-45% CPU +15 rc5des chewed ~35-40% CPU +20 rc5des chewed ~25-30% CPU If there's any other information I can provide, just let me know. -jake -- Jacob A. Hart <[EMAIL PROTECTED]> Powered by: FreeBSD 5.0-CURRENT #9: Fri May 26 07:39:27 EST 2000 I believe the technical term is "Oops!" PGP signature
Re: Scheduler changes?
"Jacob A. Hart" wrote: > > On Fri, May 26, 2000 at 04:01:05PM +0200, Sheldon Hearn wrote: > > > > > > On Fri, 26 May 2000 13:19:49 +1000, "Jacob A. Hart" wrote: > > > > > For the past couple of weeks I've noticed rc5des isn't playing friendly with > > > the other processes on my system. When running a CPU intensive task (such > > > as a buildworld, MP3 encoder, or xmame) rc5des hogs around 20-30% CPU even > > > though, by default, it is niced at +20. > > > > As a datapoint, I have a one week old (2000-05-18) CURRENT box that runs > > setiathome all day every day. When builds kick in, setiathome gets > > relagated to the single-digit percentiles in top's display of CPU users. > > This is only true when serious building is happening; those aspects of > > the build that I can imagine are more I/O than CPU intensive give > > setiathome a fighting chance. Try setting the nice value for rc5 to something lower than 20, but higher than the highest (lowest) value running on your system. There was a bug with the scheduler in the past that items run at nice 20 were actually getting more cpu than they were supposed to. If this change fixes things for you, please report it asap, since my understanding is that this problem is rather elusive and annoying. Thanks, Doug -- "Live free or die" - State motto of my ancestral homeland, New Hampshire Do YOU Yahoo!? To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Scheduler changes?
On Fri, May 26, 2000 at 04:01:05PM +0200, Sheldon Hearn wrote: > > > On Fri, 26 May 2000 13:19:49 +1000, "Jacob A. Hart" wrote: > > > For the past couple of weeks I've noticed rc5des isn't playing friendly with > > the other processes on my system. When running a CPU intensive task (such > > as a buildworld, MP3 encoder, or xmame) rc5des hogs around 20-30% CPU even > > though, by default, it is niced at +20. > > As a datapoint, I have a one week old (2000-05-18) CURRENT box that runs > setiathome all day every day. When builds kick in, setiathome gets > relagated to the single-digit percentiles in top's display of CPU users. > This is only true when serious building is happening; those aspects of > the build that I can imagine are more I/O than CPU intensive give > setiathome a fighting chance. Yep. That makes sense. What puzzles me, though, is the behaviour for processes that aren't I/O bound. Here are two top snapshots taken while encoding an MP3 stream directly from a .wav file on disk. In both cases, the processes were given ample time to "stabilize" (ie. were left running for about two minutes before the snapshot was taken). Kernel from 26th May: last pid: 23929; load averages: 1.66, 0.85, 0.44up 1+09:10:34 17:01:31 35 processes: 3 running, 32 sleeping CPU states: 69.6% user, 28.4% nice, 0.8% system, 1.2% interrupt, 0.0% idle Mem: 65M Active, 33M Inact, 20M Wired, 4480K Cache, 22M Buf, 772K Free Swap: 256M Total, 256M Free PID USERNAME PRI NICE SIZERES STATETIME WCPUCPU COMMAND 23929 root 79 0 7656K 2024K RUN 0:59 67.56% 66.55% lame 174 root 81 20 952K 436K RUN320:40 30.27% 30.27% rc5des Kernel from 29th April: last pid: 235; load averages: 1.93, 1.02, 0.45up 0+00:06:00 17:09:10 26 processes: 3 running, 23 sleeping CPU states: 100% user, 0.0% nice, 0.0% system, 0.0% interrupt, 0.0% idle Mem: 12M Active, 49M Inact, 16M Wired, 12K Cache, 22M Buf, 47M Free Swap: 256M Total, 256M Free PID USERNAME PRI NICE SIZERES STATETIME WCPUCPU COMMAND 235 root 62 0 7684K 2260K RUN 2:15 98.44% 98.34% lame 174 root 68 20 952K 584K RUN 2:57 0.00% 0.00% rc5des Check out that rc5des process -- hogging (on average) about 30% CPU in the first case! My system feels noticibly sluggish too. The rc5des process interferes with just about everything (xmame, for example, is unplayable unless I disable it). I think I'll stick with the April 29th kernel for now ;-) -jake -- Jacob A. Hart <[EMAIL PROTECTED]> Powered by: FreeBSD 5.0-CURRENT #4: Sat Apr 29 07:29:02 EST 2000 Loose bits sink chips. PGP signature
Re: Scheduler changes?
On Fri, 26 May 2000 13:19:49 +1000, "Jacob A. Hart" wrote: > For the past couple of weeks I've noticed rc5des isn't playing friendly with > the other processes on my system. When running a CPU intensive task (such > as a buildworld, MP3 encoder, or xmame) rc5des hogs around 20-30% CPU even > though, by default, it is niced at +20. As a datapoint, I have a one week old (2000-05-18) CURRENT box that runs setiathome all day every day. When builds kick in, setiathome gets relagated to the single-digit percentiles in top's display of CPU users. This is only true when serious building is happening; those aspects of the build that I can imagine are more I/O than CPU intensive give setiathome a fighting chance. Ciao, Sheldon. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message