Messages in this thread |  | | | From | Con Kolivas <> | | Subject | Re: [PATCH] Re: Pathological case identified from contest | | Date | Sun, 20 Oct 2002 17:33:20 +1000 |
| |
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Sun, 20 Oct 2002 01:19 pm, Jim Houston wrote: > Reply-to: jim.houston@attbi.com > --text follows this line-- > > Hi Ingo, > > I ran into the same problems with the scehduler behaving > badly under load and reported them in this email: > > http://marc.theaimsgroup.com/?l=linux-kernel&m=103133744217082&w=2 > > I was testing with the LTP and ran into a live-lock because > scheduler got into a stable state where it always picked the > same processes to run. See the earlier mail for the full > story. I exchanged a few messages with Andrea Arcangeli about > this problem and tried a couple of his patches. They prevented > the lockup but it got me started thinking about how to make the > scheduler more fair. > > The result is the following patch. It is against 2.5.40. > > The patch includes: > > - Code to calculate a traditional unix p_cpu style run > average. This is an exponentially decaying average > run time. Based on the process being found running. > I'm doing a first order aproximation for the exponential > function. > > I'm punishing processes that actually get to run rather > than rewarding proceses that sleep. The decaying average > means that the value represents the fraction of the cpu > the process has used. The current sleep average tends > to clamp to the limit values. > > - Code which gradually raises the priority of all of > the processes in the run queue. This increase is balanced > by making time slices shorter for more favorable priorites. > Rrocesses that consume there time slice with out sleeping > are moved to a less favorable priority. This replaces > the array switch. > > I have only done a little testing. I timed building the kernel > with/without this change and it made no difference. I also tested > with the witpid06 test which had cause the live-lock. > > I had been planning a few more changes but got side tracked with > real work. I was thinking about adding some feed back which would > adjust the rate at which the priorities of processes in the run > queue increase. I also wanted to play with nice. The patch currently > uses a weighted average of the prio and static_prio when it calculates > a new effective priority. > > The method I use to raise the priorities of the running processes is > to remap prio values for processes in the run queue. See the functions > queue_prio an real_prio. Changing the value of prio_ind changes all > of the priorities. I have not done anything to the process migration > code so it will migrate processes with random priorities. I don't > know if this will have any noticeable effect. > > I had fun playing with this. I hope others find it useful.
Hi Jim.
My problem turned out to be a bug in the pipe implementation. Nonetheless your patch sounded interesting so I gave it a run. Hopefully I patched it correctly to 2.5.44 as it compiled and ran ok. These are the benchmark results with contest that were different b/w 2.5.44 and your patched version:
process_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.5.44 [3] 90.9 76 32 26 1.27 2.5.44-jh [1] 186.5 37 76 63 2.61
xtar_load: Kernel [runs] Time CPU% Loads LCPU% Ratio 2.5.44 [3] 117.0 65 1 7 1.64 2.5.44-jh [1] 141.7 54 2 8 1.98
The rest of the results were otherwise similar. It seems your patch served to disadvantage kernel compilation in preference for more of the background load. Process_load runs 4*num_cpus processes and context switches between them continually, so I guess it is most obvious there where kernel compilation will still be on the same process in that time. Not sure how much that represents a real life situation. Xtar load is busy extracting a tar file while trying to do a kernel compilation, and in this case there are more unused cpu cycles with the total cpu% being lower.
Cheers, Con. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) iD8DBQE9slxAF6dfvkL3i1gRAkGXAJ9H7eg9JF0CBTdWSaqal7bbp61iWwCfeIal 2tgLO3WblzymxlJT0cszfDY= =UO49 -----END PGP SIGNATURE----- - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
|  |