das at FreeBSD.ORG
Thu Mar 3 13:36:54 GMT 2005
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
> >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
> >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
> 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:
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.
More information about the freebsd-hackers