From owner-freebsd-hackers@FreeBSD.ORG Thu Mar 3 13:36:54 2005 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 57B4416A4CE for ; Thu, 3 Mar 2005 13:36:54 +0000 (GMT) Received: from VARK.MIT.EDU (VARK.MIT.EDU [18.95.3.179]) by mx1.FreeBSD.org (Postfix) with ESMTP id BD88243D46 for ; Thu, 3 Mar 2005 13:36:53 +0000 (GMT) (envelope-from das@FreeBSD.ORG) Received: from VARK.MIT.EDU (localhost [127.0.0.1]) by VARK.MIT.EDU (8.13.3/8.13.1) with ESMTP id j23DaFoQ016548; Thu, 3 Mar 2005 08:36:15 -0500 (EST) (envelope-from das@FreeBSD.ORG) Received: (from das@localhost) by VARK.MIT.EDU (8.13.3/8.13.1/Submit) id j23DaF76016547; Thu, 3 Mar 2005 08:36:15 -0500 (EST) (envelope-from das@FreeBSD.ORG) Date: Thu, 3 Mar 2005 08:36:15 -0500 From: David Schultz To: Julian Elischer Message-ID: <20050303133615.GA16479@VARK.MIT.EDU> Mail-Followup-To: Julian Elischer , Ashwin Chandra , freebsd-hackers@FreeBSD.ORG References: <001a01c51d6d$d50ce500$abe243a4@ash> <4222D5A2.9010301@elischer.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4222D5A2.9010301@elischer.org> cc: freebsd-hackers@FreeBSD.ORG cc: Ashwin Chandra Subject: Re: sched_4BSD X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 03 Mar 2005 13:36:54 -0000 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.