Use bit-map to speed up priority queue.
The scheduler currently use lineary search. So track priority qeueue in
a bitmap will make searching more efficiency by using ctzl instead of
scanning all the queues.
>From 0a0cd42eba6420f8d527aa4a69903983e1b74c60 Mon Sep 17 00:00:00 2001
From: Donjuanplatinum <[email protected]>
Date: Wed, 30 Sep 2026 09:51:29 +0800
Subject: [PATCH] sched: use bit-map instead of linear search
---
kern/processor.c | 6 ++++
kern/sched.h | 45 ++++++++++++++++++++++++
kern/sched_prim.c | 88 ++++++++++++++++++++++++++++-------------------
3 files changed, 103 insertions(+), 36 deletions(-)
diff --git a/kern/processor.c b/kern/processor.c
index 485eb51b..4531920c 100644
--- a/kern/processor.c
+++ b/kern/processor.c
@@ -140,6 +140,9 @@ void pset_init(
simple_lock_init(&pset->runq.lock);
pset->runq.low = 0;
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]));
}
@@ -192,6 +195,9 @@ void processor_init(
simple_lock_init(&pr->runq.lock);
pr->runq.low = 0;
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 74331f15..8d23ebeb 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,45 @@ 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 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);
+ 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);
+ else
runq->low = i;
- 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(
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
--
DonjuanPlatinum, Yifei Yao <[email protected]>
GPG: 1C9E EEE5 4C8E D5A8 3039 1C87 A9F6 8632 D259 40E6
满堂兮美人 忽独与余兮目成
