Re: sched_ule, runqueues, priority, and O(1) sheduling question

From: Andrey Simonenko (simon_at_comsys.ntu-kpi.kiev.ua)
Date: 03/05/05

  • Next message: ALeine: "Re: FUD about CGD and GBDE" 
    Date: Sat, 5 Mar 2005 17:48:01 +0200
To: Andriy Tkachuk <ant@emict.com>

    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()
    _______________________________________________
    freebsd-hackers@freebsd.org mailing list
    http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
    To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org"

  • Next message: ALeine: "Re: FUD about CGD and GBDE"

    Relevant Pages

    • Re: Lahman, how ya doing?
      ... >> A priority queue is an interesting idea. ... So Timer just enqueues the event on the right queue. ... >effectively starts at the same time on the current tick. ... >was triggered just gets time-sliced based on priority. ...
      (comp.object)
    • Re: Lahman, how ya doing?
      ... Suppose you had 64 Thermometers and at run time you wanted to give priority to some of them dynamically (e.g., where the temperature gradient was greatest) because processing all 64 samples at once can't be done in a single "tick". ... So Timer just enqueues the event on the right queue. ... So I addressed both the bitmap processing basics via indexed OR mask and the deferredBitmap variable assumption about bit count. ...
      (comp.object)
    • Re: cooperative multitasking scheme
      ... >> equal priority or where priorities aren't specifically used. ... where I choose not to use preemption at ... the action of the timing event is to move the process from the sleep queue ... I very much appreciate having a sleep queue. ...
      (comp.arch.embedded)
    • Re: Best way to design multithreading application
      ... The data acquisition is more important than UI updates, ... adding it to a Queue 1 as it acquires more. ... B, which is medium-to-high priority, loops over and over, and when it ... But when the threads involved are dependent on each other, as they are here, it makes little sense to make one thread higher priority than another, and for the reason you note: you really do need each of these threads to, at least on average, process the data at the same rate, otherwise you will eventually consume all your resources (memory in this case, though having the UI lag behind the actual processing is probably not desirable either). ...
      (microsoft.public.dotnet.framework)
    • Re: So... What are the alternatives? Was: I dont use an RTOS because...
      ... This configuration parameter decides whether or not preemption is allowed. ... queue will be treated as though they have equal priority. ... The real-time clock serves two primary purposes in my O/S. ...
      (comp.arch.embedded)