David Schultz 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 
> >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:

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 mailing list