From owner-freebsd-current@FreeBSD.ORG Sat Aug 14 08:14:23 2004 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 47BD116A4CE; Sat, 14 Aug 2004 08:14:23 +0000 (GMT) Received: from apollo.backplane.com (apollo.backplane.com [216.240.41.2]) by mx1.FreeBSD.org (Postfix) with ESMTP id 2872943D45; Sat, 14 Aug 2004 08:14:23 +0000 (GMT) (envelope-from dillon@apollo.backplane.com) Received: from apollo.backplane.com (localhost [127.0.0.1]) i7E8ELla012732; Sat, 14 Aug 2004 01:14:21 -0700 (PDT) (envelope-from dillon@apollo.backplane.com) Received: (from dillon@localhost) by apollo.backplane.com (8.12.9p2/8.12.9/Submit) id i7E8ELYF012731; Sat, 14 Aug 2004 01:14:21 -0700 (PDT) (envelope-from dillon) Date: Sat, 14 Aug 2004 01:14:21 -0700 (PDT) From: Matthew Dillon Message-Id: <200408140814.i7E8ELYF012731@apollo.backplane.com> To: Don Lewis References: <200408140723.i7E7NFE5004108@gw.catspoiler.org> cc: jroberson@chesapeake.net cc: freebsd-current@FreeBSD.org cc: rwatson@FreeBSD.org Subject: Re: nice handling in ULE (was: Re: SCHEDULE and high load situations) X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 14 Aug 2004 08:14:23 -0000 :It seems like ULE would work properly if threads were always prepended :to the run queue, except when they exhaust their time slice when they :should be put at the end. Yes, that's how it ought to work. It's precisely the algorithm I used in several embedded projects in the past, the only difference being that the fair share scheduling queues in those projects were actually headless circular queues (the current task always being the 'head' of the circular queue). When the current task's quantum is lost it is simply left on the queue and skipped, making the next task the head which if you think about it magically places the task that ran its quantum to 0 at the end. If you do it this way then you can focus all your attention in picking proper quantums for the tasks on the queue. In the block/wakeup case the task being woken up is always placed just after the currently running task, effectively the 'front' of the queue. This is absolutely essential for any IPC oriented system (with synchronous messages flying back and forth), which is what those embedded projects used. I even went so far as to optimizing the blocking case by letting the thread slide (not removing it from the queue) until the scheduler saw it again and that it was still blocked. The wakeup case would check if the thread was already the 'next' thread on the queue (which was most of the time in an even oriented IPC based system), thus completely optimizing out both the block/dequeue and the wakeup/requeue code for the critical path. Those were the days :-) -Matt Matthew Dillon