From: Shailabh N. <na...@us...> - 2001-10-08 13:53:33
|
Sven, There is atleast one other Lottery Scheduler implementation : http://www.cs.rochester.edu/u/sanders/linux-scheduler-proj/lottery_scheduler/lottery_scheduler.html There are some other fair schedulers for Linux, pointers to which can be found at http://web.gnu.walfield.org/mail-archive/linux-kernel/2000-August/0340.html The Open Source Development Lab has multiprocessor machines available for testing. Please check out http://www.osdl.org Good luck, Shailabh Nagar Enterprise Linux Group, IBM TJ Watson Research Center (914) 945 2851, T/L 862 2851 "Sven Dehmlow privat" <sve...@we...>@lists.sourceforge.net on 10/07/2001 12:07:27 PM Sent by: lse...@li... To: <lse...@li...> cc: Subject: [Lse-tech] Lottery Scheduling Hi, My name is Sven Dehmlow and before you ask: Yes, I'm new to this list. I'm a seventeen years old Linux kernel hacker wannabee from Hamburg/Germany. I'm currently working on a lottery scheduler for Linux. After reading what this project is about I think a lottery scheduler may fit into it. Lottery scheduling means a fair scheduler (not the 'fairscheduler'!) which has the same small overhead while handling many processes as while handling only a few processes. It is very fast, flexible and easy to manage. I think that is what you're looking for. As written above I'm not a 'real' hacker. I hope I can find some help with the implementation of the lottery scheduler. Well, implementing it isn't such a big thing, but I want to implement it the best way possible. Also I don't have any access to a multi processor machine. I hope to find someone in this project who is willing to test the lottery scheduler on his multi processor machine. Sven -----BEGIN GEEK CODE BLOCK----- Version: 3.12 GCS d- s: a--- C++++ UL+++ P++ L++++ E- W+ N+ !o K- w--- !O M- V- PS+ PE++ Y-- PGP++ t--- 5-- X+ R- tv- b+ DI+ D- G++ !e h! r- y? ------END GEEK CODE BLOCK------ _______________________________________________ Lse-tech mailing list Lse...@li... https://lists.sourceforge.net/lists/listinfo/lse-tech |
From: Sven D. p. <sve...@we...> - 2001-10-08 14:42:03
|
> > Sven, > > I'm not one of the 'insiders' on this list either, but I've done a fair > amount of work on schedulers in my day. > > While I understand in general, the concepts of a lottery scheduler, I'd > like to hear of some of the specifics of your implementation. As always: What I've got is not what I want... I've got: A working scheduler that works like this: The number of tickets is equal to the 'priority' of each process. The scheduler is called to find a process for a processor (I use the 'HP scheduler plug-in' patch -> I don't have to care about many things): 1.) 'list_for_each()' process and get the sum of all tickets that exist. 2.) Get a random number ('get_random_bytes()' or simple 'Park/Miller') which isn't bigger than the sum of all tickets 3.) 'list_for_each()' process. Sum up the tickets from process to process until this amount is equal or bigger than the random number and take the last listed process. What I want: In my opinion a perfect lottery scheduler should work as follows: a.) The process hasn't only one amount of tickets for all cpus, it has an amount of tickets for each cpu. For example if it runs in a 8 cpu system it can have 100 tickets for cpu1, 200 for cpu2, ... and 1200 for cpu8. This feature makes lottery scheduling more flexible and very interesting for systems with different cpus. Tell me if I'm wrong, but from my point of view Linux makes no difference between cpus and this may cause unfairness. b.) The sum of all tickets are not calculated as this costs much cpu-time. If a process is made runnable it's tickets are added and if it is made unrunable it's tickets are removed form an counter. c.) I'm not sure, but it maybe that if we schedule too often Linux has no random numbers left. The solution is to take the real random number ('get_random_bytes()') as the seed for a fast Park/Miller random number generator. If there are no processes to schedule and the idle process is the next to run we can refresh the seed of the Park/Miller random number generator. d.) Compensation tickets. They make sure that the scheduler stays very (very, very...) fair. [e.)] more ideas are always welcome > > And yes, if it looks good, I ought to be able to 'test' it on machines up > to 8-ways, maybe more. Thank you, but I would like to implement the scheduler described above first. Testing my current one is waste in time as it isn't perfect and is missing those wonderful features that make lottery scheduling interesting. I'm sure that I can't implement such a scheduler alone and even if it wouldn't be perfect. If I convinced somebody that a lottery scheduler as describd above is useful and needed I would like to suggest to implement it together. Sven |
From: Sven D. p. <sve...@we...> - 2001-10-08 14:48:49
|
> Sven, > > There is atleast one other Lottery Scheduler implementation : > http://www.cs.rochester.edu/u/sanders/linux-scheduler-proj/lottery_sch eduler/lottery_scheduler.html > There are some other fair schedulers for Linux, pointers to which can be > found at > http://web.gnu.walfield.org/mail-archive/linux-kernel/2000-August/0340 .html Their lottery scheduler implementation is very similar to my current one. It isn't very useful compared with other fair schedulers. Please read my last mail for further informations. > > The Open Source Development Lab has multiprocessor machines available for > testing. Please check out > http://www.osdl.org > > Good luck, Thank you! Sven |