On Mon, Feb 28, 2005, Julian Elischer wrote: > Ashwin Chandra wrote: > >I wanted to get some clarification about the 4BSD scheduler. I am sort of > >confused why there are two forms of scheduling, one done between processes > >and > >another done between threads in a process. The priority calculations seem > >to be > >done only with processes and I assume that the global run queue holds > >processes, > >not threads. Also why is there only 1 run queue for 1 CPU. What happens to > >blocked processes and ready to be runned processes? > > Part of the challenge of adding threads to a system is to make it hard for > a threaded process to "flood" the system run queues so that other processes > get no cpu time. > > The scheme in the current freeBSD schedulers is a "crude" method, by which > only a limitted number of threads per process are allowed to be added to > the system run queue. RUnnable hreads fo r aprocess are kept on a run queue > for the process and only the highest N prioriy hreads are actually put on > the > system run queue. > > This is by no means the best way, but rather the > easiest way. I am hoping that some PhD candidate somewhere will decide > that thread scheduling is his topic and will figure out a better way > of doing this.
I think most of the PhD theses in that area were written over a decade ago. ;-) Carl Waldspurger comes to mind in particular. The UC Berkeley CSUA, which runs a shell box often supporting hundreds of simultaneous users, implemented one of those ideas in FreeBSD 4.X a long time ago. The basic idea, called lottery scheduling, is that each user gets some number of tickets, say 1000. Users use their tickets to ``fund'' their processes, and each process in the system gets a share of the CPU proportional to the number of tickets it has. Their algorithm is randomized, but more sophistocated approaches such as stride scheduling are deterministic. Patches are available at: http://www.csua.berkeley.edu/computing/software/lottery-sched.html One of the nice features of something like this over standard Unix priority scheduling is that problems such as starvation just don't happen. The ticket quota idea is also a nice way to deal with the problem you mention. IIRC, Luigi had a weighted fair queuing scheduler for 4.X as well. This is basically the same idea viewed from a networking person's point of view. _______________________________________________ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "[EMAIL PROTECTED]"
