Date: Sat, 5 Mar 2005 17:48:01 +0200 From: Andrey Simonenko <simon@comsys.ntu-kpi.kiev.ua> To: Andriy Tkachuk <ant@emict.com> Cc: freebsd-hackers@freebsd.org Subject: Re: sched_ule, runqueues, priority, and O(1) sheduling question Message-ID: <20050305154800.GA468@pm514-9.comsys.ntu-kpi.kiev.ua> In-Reply-To: <000401c520d5$a6b6ae00$090210ac@BORJA> References: <000401c520d5$a6b6ae00$090210ac@BORJA>
next in thread | previous in thread | raw e-mail | index | archive | help
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()
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050305154800.GA468>