From owner-freebsd-hackers Fri Aug 16 4:23:33 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 8A7A637B40D for ; Fri, 16 Aug 2002 04:23:28 -0700 (PDT) Received: from avocet.mail.pas.earthlink.net (avocet.mail.pas.earthlink.net [207.217.120.50]) by mx1.FreeBSD.org (Postfix) with ESMTP id 0D1AE43E6A for ; Fri, 16 Aug 2002 04:23:28 -0700 (PDT) (envelope-from tlambert2@mindspring.com) Received: from pool0003.cvx22-bradley.dialup.earthlink.net ([209.179.198.3] helo=mindspring.com) by avocet.mail.pas.earthlink.net with esmtp (Exim 3.33 #1) id 17ffBt-0004iI-00; Fri, 16 Aug 2002 04:22:54 -0700 Message-ID: <3D5CDF48.9C9B30ED@mindspring.com> Date: Fri, 16 Aug 2002 04:17:28 -0700 From: Terry Lambert X-Mailer: Mozilla 4.79 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Jonathon McKitrick Cc: freebsd-hackers@freebsd.org Subject: Re: When to consider the new scehduler? References: <20020816104037.GA58453@dogma.freebsd-uk.eu.org> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable 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 Jonathon McKitrick wrote: > A couple of months ago, I saw a note on daemonnews that there was a > patch for a proportional share scheduler. When would this work better > than the existing priority feedback scheduler? > = > NOTE: Please CC me, as I am not currently subscribed. Thanks. Basically, you use it if you expect the system to be overloaded, and don't want to spend the engineering effort to prevent/handle the overload, and astill want the system to degrade gracefully. The "fixed" scheduling class used to support the X server in the UnixWare/SVR4.0.2/SVR4.2 case is, in the limit, a proportional share scheduler. Rather than addressing the lack of working set quotas that caused some programs (e.g. the linker) to thrash a large number of pages out, the fixed scheduling class was added to permit the X server sufficient CPU to trash the pages back in; it didn't fix the problem, and there was a lot of useless page thrashing, but the result was that the X server had sufficiently good interactive response to fullfill the "move mouse -> wiggle cursor" requirement amd avoid cognitive dissonance on the part of the user attached to the mouse. 8-). Here is an introduction from a moderately good paper on the subject. Note that not all proportional share schedulers implement all the attributes described here, and most are not O(1). I can't comment on Luigi's work in detail, because I haven't studied it in detail (soft real time systems are not very interesting to me unless they support deadlining). Abstracted from: http://www.cs.utah.edu/flux/papers/ps-rtss01/RegehrRTSS01wip.pdf | There are compelling reasons to use proportional share | scheduling techniques to support multimedia and other | soft real-time applications on general-purpose operating | systems. First, proportional share (PS) schedulers are | a good match for existing infrastructure such as a peri-odic | timer interrupt and mechanisms for assigning priori-ties | to applications=97priorities can be mapped to shares in | a proportional-share environment. Second, PS schedulers | provide stronger guarantees to applications than do tradi-tional | time-sharing schedulers: they allocate a specific frac-tion | of the CPU to each thread, and some schedulers provide | error bounds on the allocation rate. Third, PS schedulers | have clear semantics during underload: excess CPU time | is allocated fairly, in contrast with some reservation-based | schedulers that must idle or back off to a secondary scheduling | policy once all application budgets are exhausted. FWIW, here's a paper on an O(1) proportional share scheduler. It's not incredibly interesting, except in that it tries to implement fair queueing: http://citeseer.nj.nec.com/nieh01virtualtime.html For my money, the algorithm to use in networking equipment, in which you want to optimize packet throughput, is Weighted Fair Share Queueing (as in the IBM/UMass work on QLinux, which also implements Lazy REceiver Processing; see the QLinux site at http://lass.cs.umass.edu/software/qlinux/ ). -- Terry To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message