From owner-freebsd-hackers@FreeBSD.ORG Sat Mar 5 15:48:23 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 0C21216A4CE for ; Sat, 5 Mar 2005 15:48:23 +0000 (GMT) Received: from comsys.ntu-kpi.kiev.ua (comsys.ntu-kpi.kiev.ua [195.245.194.142]) by mx1.FreeBSD.org (Postfix) with ESMTP id CD60343D41 for ; Sat, 5 Mar 2005 15:48:20 +0000 (GMT) (envelope-from simon@comsys.ntu-kpi.kiev.ua) Received: from pm514-9.comsys.ntu-kpi.kiev.ua (pm514-9.comsys.ntu-kpi.kiev.ua [10.18.54.109]) (authenticated bits=0)j25FpbK9058465 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sat, 5 Mar 2005 17:51:38 +0200 (EET) Received: by pm514-9.comsys.ntu-kpi.kiev.ua (Postfix, from userid 1000) id 2B93FF2; Sat, 5 Mar 2005 17:48:01 +0200 (EET) Date: Sat, 5 Mar 2005 17:48:01 +0200 From: Andrey Simonenko To: Andriy Tkachuk Message-ID: <20050305154800.GA468@pm514-9.comsys.ntu-kpi.kiev.ua> References: <000401c520d5$a6b6ae00$090210ac@BORJA> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <000401c520d5$a6b6ae00$090210ac@BORJA> User-Agent: Mutt/1.4.2.1i X-Virus-Scanned: ClamAV 0.82/737/Tue Mar 1 08:22:18 2005 on comsys.ntu-kpi.kiev.ua X-Virus-Status: Clean cc: freebsd-hackers@freebsd.org Subject: Re: sched_ule, runqueues, priority, and O(1) sheduling question 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: Sat, 05 Mar 2005 15:48:23 -0000 On Fri, Mar 04, 2005 at 09:45:56PM +0530, Andriy Tkachuk wrote: > Hi folks. > > I wander how O(1) sheduling works in ULE. > In ule.pdf Jeff wrote: > > Threads are picked from the current queue in > priority order until the current queue is empty. > > As far as I understand the algorithm is O(n) > where n - number of READY TO RUN processes, > not all processes isn't it? As I understood, algorithm is O(1). Everything said below is only my point of view, please correct me if I'm wrong. All threads which are kept in the current queue, are really not kept in one physical queue. They are kept in several queues, number of this queues is less than number of priorities, so several priorities are indistinguishable in the queue. To find a thread with higher priority first non-empty queue should be find. There is a bitmap for all queues and each bit in this bitmap says if queue is empty or not. To find first nonzero bit special machine-dependent instruction is used (for x86 this is bsf), if a machine word is not enough to keep all bits, then several words are used. When first non-empty queue (that is queue with maximum priority) was found, everything what is needed, is removing first (last) thread from this queue. If the queue became empty its bit in the bitmap of all queue is cleared and it is set again if the queue becomes non-empty. Details: kern/sched_ule.c struct kseq{}, check what is ksq_next and what is ksq_curr sys/runq.h check comments in this file kern/kern_switch.c check runq_*() functions and runq_findbit(). Follow this path: mi_switch() -> sched_ule.c:sched_switch() -> choosethread() -> shced_ule.c:shced_choose() -> kseq_choose() -> runq_choose() kseq_runq_rem() -> runq_remove()