From owner-freebsd-hackers@FreeBSD.ORG  Fri Mar  4 16:17:26 2005
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
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 D930116A4CE
	for <freebsd-hackers@freebsd.org>;
	Fri,  4 Mar 2005 16:17:26 +0000 (GMT)
Received: from mail.emict.com (brig.emict.com [212.90.172.42])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 8A76843D54
	for <freebsd-hackers@freebsd.org>;
	Fri,  4 Mar 2005 16:17:26 +0000 (GMT)	(envelope-from ant@emict.com)
Received: from BORJA (unknown [203.199.120.221])
	by mail.emict.com (Postfix) with ESMTP id B6B573551D
	for <freebsd-hackers@freebsd.org>;
	Fri,  4 Mar 2005 18:17:23 +0200 (EET)
Message-ID: <000401c520d5$a6b6ae00$090210ac@BORJA>
From: "Andriy Tkachuk" <ant@emict.com>
To: <freebsd-hackers@freebsd.org>
Date: Fri, 4 Mar 2005 21:45:56 +0530
MIME-Version: 1.0
Content-Type: text/plain;
	format=flowed;
	charset="koi8-r";
	reply-type=original
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2900.2180
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180
X-Mailman-Approved-At: Fri, 04 Mar 2005 16:36:07 +0000
Subject: 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
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 04 Mar 2005 16:17:27 -0000

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?

thanks,
  Andriy.