Hello,

Thanks for this optimization, just some comments to make it a strict
improvement.

Donjuanplatinum, le mer. 30 sept. 2026 10:07:05 +0800, a ecrit:
> The scheduler currently use lineary search.

But it also uses a "low" value to avoid searching the whole array.

> +static inline int runq_findbit(const unsigned long *bitmap)

You could add a "low" parameter here.

> +{
> +     int i;
> +     unsigned long word;
> +
> +     for (i = 0; i < NRQS_BITMAP_SIZE; i++) {
> +             word = bitmap[i];
> +             if (word != 0) {
> +                     int bit;
> +#if defined(__GNUC__)
> +                     bit = __builtin_ctzl(word);
> +#else
> +                     for (bit = 0; bit < (sizeof(unsigned long) * 8); bit++) 
> {
> +                             if (word & (1UL << bit))
> +                                     break;
> +                     }
> +#endif
> +                     return i * (sizeof(unsigned long) * 8) + bit;
> +             }
> +     }
> +     return NRQS;
> +}
> +
>  /*
>   *   sched_tick increments once a second.  Used to age priorities.
>   */
> diff --git a/kern/sched_prim.c b/kern/sched_prim.c
> index c1b809be..5cb0ac50 100644
> --- a/kern/sched_prim.c
> +++ b/kern/sched_prim.c
> @@ -1198,6 +1198,7 @@ void update_priority(
>           runq_lock(rq);      /* lock the run queue */        \
>           checkrq((rq), "thread_setrun: before adding thread");       \
>           enqueue_tail(&(rq)->runq[whichq], &((th)->links));          \
> +         runq_setbit((rq)->bitmap, whichq);                          \
>                                                                       \
>           if (whichq < (rq)->low || (rq)->count == 0)                 \
>                (rq)->low = whichq;    /* minimize */                  \
> @@ -1221,6 +1222,7 @@ void update_priority(
>                                                                       \
>           runq_lock(rq);      /* lock the run queue */        \
>           enqueue_tail(&(rq)->runq[whichq], &((th)->links));          \
> +         runq_setbit((rq)->bitmap, whichq);                          \
>                                                                       \
>           if (whichq < (rq)->low || (rq)->count == 0)                 \
>                (rq)->low = whichq;    /* minimize */                  \
> @@ -1454,6 +1456,7 @@ struct run_queue *rem_runq(
>               checkrq(rq, "rem_runq: at entry");
>  #endif       /* DEBUG */
>               if (rq == th->runq) {
> +                     int pri;
>                       /*
>                        *      Thread is in a runq and we have a lock on
>                        *      that runq.
> @@ -1462,8 +1465,12 @@ struct run_queue *rem_runq(
>                       checkrq(rq, "rem_runq: before removing thread");
>                       thread_check(th, rq);
>  #endif       /* DEBUG */
> +                     pri = th->sched_pri;
>                       remqueue(&rq->runq[0], (queue_entry_t) th);
>                       rq->count--;
> +                     if (queue_empty(&rq->runq[pri])) {
> +                             runq_clrbit(rq->bitmap, pri);
> +                     }
>  #if  DEBUG
>                       checkrq(rq, "rem_runq: after removing thread");
>  #endif       /* DEBUG */
> @@ -1515,19 +1522,29 @@ thread_t choose_thread(
>  
>       simple_lock(&runq->lock);
>       if (runq->count > 0) {
> -         q = runq->runq + runq->low;
> -         for (i = runq->low; i < NRQS ; i++, q++) {
> -             if (!queue_empty(q)) {
> -                 th = (thread_t) dequeue_head(q);
> -                 th->runq = RUN_QUEUE_NULL;
> -                 runq->count--;
> +         i = runq_findbit(runq->bitmap);

And you can pass runq->low to runq_findbit.

> +         if (i >= NRQS) {
> +             panic("choose_thread: bitmap/count mismatch");
> +         }
> +         q = runq->runq + i;
> +         if (queue_empty(q)) {
> +             panic("choose_thread: bitmap points to empty queue");
> +         }
> +         th = (thread_t) dequeue_head(q);
> +         th->runq = RUN_QUEUE_NULL;
> +         runq->count--;
> +
> +         if (queue_empty(q)) {
> +             runq_clrbit(runq->bitmap, i);
> +             if (runq->count > 0)
> +                 runq->low = runq_findbit(runq->bitmap);

And here pass i+1.

> +             else
>                   runq->low = i;

? If the runq is empty, better set low to NRQS, so the next time a
thread is queued, low will be set to its priority.

> -                 simple_unlock(&runq->lock);
> -                 return th;
> -             }
> +         } else {
> +             runq->low = i;
>           }
> -         panic("choose_thread");
> -         /*NOTREACHED*/
> +         simple_unlock(&runq->lock);
> +         return th;
>       }
>       simple_unlock(&runq->lock);
>  
> @@ -1561,35 +1578,34 @@ thread_t choose_pset_thread(

And same in this function.

>       runq = &pset->runq;
>  
>       if (runq->count > 0) {
> -         q = runq->runq + runq->low;
> -         for (i = runq->low; i < NRQS ; i++, q++) {
> -             if (!queue_empty(q)) {
> -                 th = (thread_t) dequeue_head(q);
> -                 th->runq = RUN_QUEUE_NULL;
> -                 runq->count--;
> -                 /*
> -                  *  For POLICY_FIXEDPRI, runq->low must be
> -                  *  accurate!
> -                  */
> +         i = runq_findbit(runq->bitmap);
> +         if (i >= NRQS) {
> +             panic("choose_pset_thread: bitmap/count mismatch");
> +         }
> +         q = runq->runq + i;
> +         if (queue_empty(q)) {
> +             panic("choose_pset_thread: bitmap points to empty queue");
> +         }
> +         th = (thread_t) dequeue_head(q);
> +         th->runq = RUN_QUEUE_NULL;
> +         runq->count--;
> +         if (queue_empty(q))
> +             runq_clrbit(runq->bitmap, i);
> +
>  #if  MACH_FIXPRI
> -                 if ((runq->count > 0) &&
> -                     (pset->policies & POLICY_FIXEDPRI)) {
> -                         while (queue_empty(q)) {
> -                             q++;
> -                             i++;
> -                         }
> -                 }
> +         if ((runq->count > 0) &&
> +             (pset->policies & POLICY_FIXEDPRI)) {
> +                 runq->low = runq_findbit(runq->bitmap);
> +         } else
>  #endif       /* MACH_FIXPRI */
> -                 runq->low = i;
> +         {
> +             runq->low = i;
> +         }
>  #if  DEBUG
> -                 checkrq(runq, "choose_pset_thread");
> +         checkrq(runq, "choose_pset_thread");
>  #endif       /* DEBUG */
> -                 simple_unlock(&runq->lock);
> -                 return th;
> -             }
> -         }
> -         panic("choose_pset_thread");
> -         /*NOTREACHED*/
> +         simple_unlock(&runq->lock);
> +         return th;
>       }
>       simple_unlock(&runq->lock);
>  
> -- 
> 2.55.0
> 

Reply via email to