From owner-freebsd-hackers Thu Aug 22 7:34:16 2002 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 E3E9537B400; Thu, 22 Aug 2002 07:34:13 -0700 (PDT) Received: from HAL9000.homeunix.com (12-232-220-15.client.attbi.com [12.232.220.15]) by mx1.FreeBSD.org (Postfix) with ESMTP id 52D8943E3B; Thu, 22 Aug 2002 07:34:13 -0700 (PDT) (envelope-from dschultz@uclink.Berkeley.EDU) Received: from HAL9000.homeunix.com (localhost [127.0.0.1]) by HAL9000.homeunix.com (8.12.5/8.12.5) with ESMTP id g7MEYprK000441; Thu, 22 Aug 2002 07:34:51 -0700 (PDT) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.5/8.12.5/Submit) id g7MEYpu8000440; Thu, 22 Aug 2002 07:34:51 -0700 (PDT) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Thu, 22 Aug 2002 07:34:51 -0700 From: David Schultz To: Mario Sergio Fujikawa Ferreira Cc: FreeBSD-hackers@FreeBSD.ORG Subject: Re: Creating a sysctl? (mission impossible) Message-ID: <20020822143451.GA322@HAL9000.homeunix.com> Mail-Followup-To: Mario Sergio Fujikawa Ferreira , FreeBSD-hackers@FreeBSD.ORG References: <20020820180222.927.qmail@exxodus.fedaykin.here> <20020822030842.GA22058@HAL9000.homeunix.com> <20020822125455.376.qmail@exxodus.fedaykin.here> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20020822125455.376.qmail@exxodus.fedaykin.here> Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG Thus spake Mario Sergio Fujikawa Ferreira : > Well, the high overhead has usually been due to the design > implementation. It is usually due to the data structure used for > holding the processes in the scheduler. Aside from that, the only > really expensive call is random(). I am trying to use least expensive > design in this code but I am aware of this possible caveat. Waldspurger presents one possible PRNG for this purpose in his paper. Nevertheless, I think much of the overhead is inherent in precise lottery scheduling, since you have to consider all runnable processes in the odds at each context switch. Stride scheduling is much nicer in this regard, in addition to offering dependable response times. Berkeley's undergrad OS course actually has students implement a simplification of lottery scheduling as a component of the class project. It's an off-the-wall idea because they don't teach anything about PS schedulers in general, nor do they properly cover the relative merits of lottery scheduling. Fortunately, the task is trivial because the implementation is for a toy OS and efficiency is a non-issue. Best of luck on your project. I'm interested in seeing how your scheduler works out in a real operating system. (I was actually surprised to learn that someone had ported David Petrou's lottery scheduler from FreeBSD 2.2.) To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message