Date: Thu, 3 Mar 2005 08:36:15 -0500 From: David Schultz <das@FreeBSD.ORG> To: Julian Elischer <julian@elischer.org> Cc: Ashwin Chandra <ashcs@ucla.edu> Subject: Re: sched_4BSD Message-ID: <20050303133615.GA16479@VARK.MIT.EDU> In-Reply-To: <4222D5A2.9010301@elischer.org> References: <001a01c51d6d$d50ce500$abe243a4@ash> <4222D5A2.9010301@elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050303133615.GA16479>