Samuel Thibault <[email protected]> writes: > 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. > Hi Samuel,
Thanks for your review. I have attached the updated patch.
>From f87604ccc3659a457592905b282d9c064dd1d028 Mon Sep 17 00:00:00 2001 From: Donjuanplatinum <[email protected]> Date: Tue, 17 Nov 2026 20:30:20 +0800 Subject: [PATCH] sched: use a bitmap to speed up run queue lookup * kern/processor.c (pset_init, processor_init): Add bitmap init. * kern/sched.h (NRQS_BITMAP_SIZE, run_queue, runq_setbit, runq_clrbit) (runq_findbit): New functions and constant. * kern/sched_prim.c (thread_select, rem_runq, choose_thread) (choose_pset_thread, do_runq_scan): Use bitmap-based run queue lookup. --- kern/processor.c | 10 +++- kern/sched.h | 50 ++++++++++++++++ kern/sched_prim.c | 146 +++++++++++++++++++++++++++++----------------- 3 files changed, 152 insertions(+), 54 deletions(-) diff --git a/kern/processor.c b/kern/processor.c index 485eb51b..8bc60c0e 100644 --- a/kern/processor.c +++ b/kern/processor.c @@ -138,8 +138,11 @@ void pset_init( int i; simple_lock_init(&pset->runq.lock); - pset->runq.low = 0; + pset->runq.low = NRQS; pset->runq.count = 0; + for (i = 0; i < NRQS_BITMAP_SIZE; i++) { + pset->runq.bitmap[i] = 0; + } for (i = 0; i < NRQS; i++) { queue_init(&(pset->runq.runq[i])); } @@ -190,8 +193,11 @@ void processor_init( int i; simple_lock_init(&pr->runq.lock); - pr->runq.low = 0; + pr->runq.low = NRQS; pr->runq.count = 0; + for (i = 0; i < NRQS_BITMAP_SIZE; i++) { + pr->runq.bitmap[i] = 0; + } for (i = 0; i < NRQS; i++) { queue_init(&(pr->runq.runq[i])); } diff --git a/kern/sched.h b/kern/sched.h index 1f33f018..b6193681 100644 --- a/kern/sched.h +++ b/kern/sched.h @@ -62,11 +62,17 @@ #endif /* STAT_TIME */ #define NRQS 65 /* 65 run queues per cpu */ +/* + * Bitmap size for priority tracking. + */ +#define NRQS_BITMAP_SIZE ((NRQS + (sizeof(unsigned long) * 8) - 1) / (sizeof(unsigned long) * 8)) + struct run_queue { queue_head_t runq[NRQS]; /* one for each priority */ decl_simple_lock_data(, lock); /* one lock for all queues, shall be taken at splsched only */ + unsigned long bitmap[NRQS_BITMAP_SIZE]; /* priority bitmap */ int low; /* low queue value */ int count; /* count of threads runable */ }; @@ -158,6 +164,50 @@ struct shift { typedef struct shift *shift_t, shift_data_t; +/* + * Bitmap operations for run queue priority tracking. + */ + +static inline void runq_setbit(unsigned long *bitmap, int pri) +{ + bitmap[pri / (sizeof(unsigned long) * 8)] |= + (1UL << (pri % (sizeof(unsigned long) * 8))); +} + +static inline void runq_clrbit(unsigned long *bitmap, int pri) +{ + bitmap[pri / (sizeof(unsigned long) * 8)] &= + ~(1UL << (pri % (sizeof(unsigned long) * 8))); +} + +static inline int runq_findbit(const unsigned long *bitmap, int low) +{ + int i; + unsigned long word; + const int bits_per_long = sizeof(unsigned long) * 8; + + for (i = low / bits_per_long; i < NRQS_BITMAP_SIZE; i++) { + word = bitmap[i]; + + if (i == low / bits_per_long) + word &= ~0UL << (low % bits_per_long); + + 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 * bits_per_long + 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 8cf2ab27..f89b0c53 100644 --- a/kern/sched_prim.c +++ b/kern/sched_prim.c @@ -564,12 +564,13 @@ static thread_t thread_select( } else { queue_t q; - - /* - * If there is a thread at hint, grab it, - * else call choose_pset_thread. - */ - q = pset->runq.runq + pset->runq.low; + int pri; + /* + * If there is a thread at hint, grab it, + * else call choose_pset_thread. + */ + pri = pset->runq.low; + q = pset->runq.runq + pri; if (queue_empty(q)) { pset->runq.low++; @@ -578,20 +579,27 @@ static thread_t thread_select( else { thread = (thread_t) dequeue_head(q); thread->runq = RUN_QUEUE_NULL; - pset->runq.count--; + pset->runq.count--; + if (queue_empty(q)) + runq_clrbit(pset->runq.bitmap, pri); + + if (pset->runq.count == 0) + { + pset->runq.low = NRQS; + } #if MACH_FIXPRI /* * Cannot lazy evaluate pset->runq.low for * fixed priority policy */ - if ((pset->runq.count > 0) && - (pset->policies & POLICY_FIXEDPRI)) { - while (queue_empty(q)) { - pset->runq.low++; - q++; - } + else if (queue_empty(q) && + (pset->policies & POLICY_FIXEDPRI)) { + pset->runq.low = runq_findbit(pset->runq.bitmap, pri + 1); } -#endif /* MACH_FIXPRI */ +#endif /* MACH_FIXPRI */ + else { + pset->runq.low = pri; + } #if DEBUG checkrq(&pset->runq, "thread_select: after"); #endif /* DEBUG */ @@ -1198,6 +1206,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 +1230,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 +1464,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 +1473,16 @@ 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 (runq->count == 0) + { + runq->low = NRQS; + } #if DEBUG checkrq(rq, "rem_runq: after removing thread"); #endif /* DEBUG */ @@ -1515,19 +1534,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--; - runq->low = i; - simple_unlock(&runq->lock); - return th; - } + i = runq_findbit(runq->bitmap, runq->low); + 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, i + 1); + else + runq->low = NRQS; + } else { + runq->low = i; } - panic("choose_thread"); - /*NOTREACHED*/ + simple_unlock(&runq->lock); + return th; } simple_unlock(&runq->lock); @@ -1561,35 +1590,42 @@ thread_t choose_pset_thread( 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, runq->low); + 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 (runq->count == 0) + { + runq->low = NRQS; + } + /* + * For POLICY_FIXEDPRI, runq->low must be + * accurate! + */ #if MACH_FIXPRI - if ((runq->count > 0) && - (pset->policies & POLICY_FIXEDPRI)) { - while (queue_empty(q)) { - q++; - i++; - } - } + else if (queue_empty(q) && + (pset->policies & POLICY_FIXEDPRI)) { + runq->low = runq_findbit(runq->bitmap, i + 1); + } #endif /* MACH_FIXPRI */ - runq->low = i; + else { + 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); @@ -1936,10 +1972,16 @@ do_runq_scan( * see it. So we remove the thread * from the runq to make it safe. */ - remqueue(q, (queue_entry_t) thread); + remqueue(q, (queue_entry_t)thread); runq->count--; thread->runq = RUN_QUEUE_NULL; + if (queue_empty(q)) + runq_clrbit(runq->bitmap, q - runq->runq); + if (runq->count == 0) + { + runq->low = NRQS; + } stuck_threads[stuck_count++] = thread; if (do_thread_scan_debug) printf("do_runq_scan: adding thread %p\n", thread); -- 2.56.0
-- Donjuanplatinum, Yifei Yao <[email protected]> GPG: 1C9E EEE5 4C8E D5A8 3039 1C87 A9F6 8632 D259 40E6 满堂兮美人 忽独与余兮目成
