Page MenuHomeFreeBSD
Files F173666091

D60031.diff
No OneTemporary
Actions

D60031.diff
View Options

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -1976,9 +1976,29 @@
rmlock.9 rm_wowned.9 \
rmlock.9 rm_wunlock.9
MLINKS+=runqueue.9 choosethread.9 \
- runqueue.9 procrunnable.9 \
- runqueue.9 remrunqueue.9 \
- runqueue.9 setrunqueue.9
+ runqueue.9 RQ_MAX_PRIO.9 \
+ runqueue.9 RQ_NQS.9 \
+ runqueue.9 RQ_PPQ.9 \
+ runqueue.9 RQ_PRI_TO_QUEUE_IDX.9 \
+ runqueue.9 RQSW_BIT.9 \
+ runqueue.9 RQSW_BIT_IDX.9 \
+ runqueue.9 RQSW_BPW.9 \
+ runqueue.9 RQSW_BSF.9 \
+ runqueue.9 RQSW_FIRST_QUEUE_IDX.9 \
+ runqueue.9 RQSW_IDX.9 \
+ runqueue.9 RQSW_NB.9 \
+ runqueue.9 RQSW_PRI.9 \
+ runqueue.9 RQSW_TO_QUEUE_IDX.9 \
+ runqueue.9 runq_add.9 \
+ runqueue.9 runq_add_idx.9 \
+ runqueue.9 runq_choose.9 \
+ runqueue.9 runq_choose_fuzz.9 \
+ runqueue.9 runq_findq.9 \
+ runqueue.9 runq_first_thread_range.9 \
+ runqueue.9 runq_init.9 \
+ runqueue.9 runq_is_queue_empty.9 \
+ runqueue.9 runq_not_empty.9 \
+ runqueue.9 runq_remove.9
MLINKS+=rwlock.9 rw_assert.9 \
rwlock.9 rw_destroy.9 \
rwlock.9 rw_downgrade.9 \
diff --git a/share/man/man9/runqueue.9 b/share/man/man9/runqueue.9
--- a/share/man/man9/runqueue.9
+++ b/share/man/man9/runqueue.9
@@ -20,115 +20,305 @@
.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
.\"
-.Dd August 15, 2010
+.Dd September 25, 2026
.Dt RUNQUEUE 9
.Os
.Sh NAME
.Nm choosethread ,
-.Nm procrunnable ,
-.Nm remrunqueue ,
-.Nm setrunqueue
-.Nd manage the queue of runnable processes
+.Nm RQ_MAX_PRIO ,
+.Nm RQ_NQS ,
+.Nm RQ_PPQ ,
+.Nm RQ_PRI_TO_QUEUE_IDX ,
+.Nm RQSW_BIT ,
+.Nm RQSW_BIT_IDX ,
+.Nm RQSW_BPW ,
+.Nm RQSW_BSF ,
+.Nm RQSW_FIRST_QUEUE_IDX ,
+.Nm RQSW_IDX ,
+.Nm RQSW_NB ,
+.Nm RQSW_PRI ,
+.Nm RQSW_TO_QUEUE_IDX ,
+.Nm runq_add ,
+.Nm runq_add_idx ,
+.Nm runq_choose ,
+.Nm runq_choose_fuzz ,
+.Nm runq_findq ,
+.Nm runq_first_thread_range ,
+.Nm runq_init ,
+.Nm runq_is_queue_empty ,
+.Nm runq_not_empty ,
+.Nm runq_remove
+.Nd manage queues of runnable threads
.Sh SYNOPSIS
-.In sys/param.h
.In sys/proc.h
-.Vt "extern struct rq itqueues[]" ;
-.Vt "extern struct rq rtqueues[]" ;
-.Vt "extern struct rq queues[]" ;
-.Vt "extern struct rq idqueues[]" ;
+.In sys/runq.h
+.Fd "#define RQ_MAX_PRIO (255)"
+.Fd "#define RQ_NQS (howmany(RQ_MAX_PRIO + 1, RQ_PPQ))"
+.Fd "#define RQ_PPQ (1)"
+.Fn RQ_PRI_TO_QUEUE_IDX pri
+.Fn RQSW_BIT idx
+.Fn RQSW_BIT_IDX idx
+.Fd "#define RQSW_BPW (sizeof(rqsw_t) * NBBY)"
+.Fn RQSW_BSF word
+.Fn RQSW_FIRST_QUEUE_IDX word_idx word
+.Fn RQSW_IDX idx
+.Fd "#define RQSW_NB (howmany(RQ_NQS, RQSW_BPW))"
+.Fd "#define RQSW_PRI \(dq%#lx\(dq"
+.Fn RQSW_TO_QUEUE_IDX word_idx bit_idx
.Ft struct thread *
.Fn choosethread "void"
-.Ft int
-.Fn procrunnable "void"
.Ft void
-.Fn remrunqueue "struct thread *td"
+.Fn runq_add "struct runq *rq" "struct thread *td" "int flags"
+.Ft void
+.Fn runq_add_idx "struct runq *rq" "struct thread *td" "int idx" "int flags"
+.Ft struct thread *
+.Fn runq_choose "struct runq *rq"
+.Ft struct thread *
+.Fn runq_choose_fuzz "struct runq *rq" "int fuzz"
+.Ft int
+.Fn runq_findq "struct runq *rq" "int lvl_min" "int lvl_max" "runq_pred_t *pred" "void *pred_data"
+.Ft struct thread *
+.Fn runq_first_thread_range "struct runq *rq" "int lvl_min" "int lvl_max"
.Ft void
-.Fn setrunqueue "struct thread *td"
+.Fn runq_init "struct runq *rq"
+.Ft bool
+.Fn runq_is_queue_empty "struct runq *rq" "int idx"
+.Ft bool
+.Fn runq_not_empty "struct runq *rq"
+.Ft bool
+.Fn runq_remove "struct runq *rq" "struct thread *td"
.Sh DESCRIPTION
-The run queue consists of four priority queues:
-.Va itqueues
-for interrupt threads,
-.Va rtqueues
-for realtime priority processes,
-.Va queues
-for time sharing processes, and
-.Va idqueues
-for idle priority processes.
-Each priority queue consists of an array of
-.Dv NQS
-queue header structures.
-Each queue header identifies a list of runnable processes of equal priority.
-Each queue also has a single word that contains a bit mask identifying
-non-empty queues to assist in selecting a process quickly.
-These are named
-.Va itqueuebits ,
-.Va rtqueuebits ,
-.Va queuebits ,
-and
-.Va idqueuebits .
-The run queues are protected by the
-.Va sched_lock
-mutex.
+A run queue holds runnable threads in priority-indexed queues.
+Lower indices have higher scheduling priority.
+The scheduler supplies the synchronization needed to protect a run queue;
+the run queue functions do not lock it themselves.
+.Ss Data structures
+The
+.Vt "struct runq"
+contains an array
+.Va rq_queues
+of
+.Dv RQ_NQS
+queues and an
+.Va rq_status
+member of type
+.Vt "struct rq_status" .
+Each
+.Vt "struct rq_queue"
+is a tail queue of threads at one queue index.
+The
+.Vt "struct rq_status"
+contains
+.Va rq_sw ,
+an array of
+.Dv RQSW_NB
+status words of type
+.Vt rqsw_t .
+A set bit in this array means that the corresponding queue is non-empty.
+The type
+.Vt runq_pred_t
+defines the predicate accepted by
+.Fn runq_findq .
+.Ss Macros
+.Bl -tag -width "RQSW_FIRST_QUEUE_IDX(word_idx, word)" -compact
+.It Dv RQ_MAX_PRIO
+The maximum thread priority, currently 255.
+The minimum is zero.
+.It Dv RQ_PPQ
+The number of priorities per queue, currently one.
+.It Dv RQ_NQS
+The number of queues, rounded up from
+.Dv RQ_MAX_PRIO + 1
+divided by
+.Dv RQ_PPQ .
+.It Fn RQ_PRI_TO_QUEUE_IDX pri
+Converts a priority to a queue index by dividing it by
+.Dv RQ_PPQ .
+.It Dv RQSW_BPW
+The number of bits in one
+.Vt rqsw_t
+status word.
+.It Dv RQSW_PRI
+The
+.Xr printf 9
+format string for a status word.
+.It Dv RQSW_NB
+The number of status words needed to cover
+.Dv RQ_NQS
+queues.
+.It Fn RQSW_IDX idx
+Returns the status word index for queue
+.Fa idx .
+.It Fn RQSW_BIT_IDX idx
+Returns the bit position within that status word for queue
+.Fa idx .
+.It Fn RQSW_BIT idx
+Returns a status word with only the bit for queue
+.Fa idx
+set.
+.It Fn RQSW_BSF word
+Returns the zero-based index of the least significant set bit in a
+nonzero status word.
+.It Fn RQSW_TO_QUEUE_IDX word_idx bit_idx
+Converts a status word index and a bit position to a queue index.
+.It Fn RQSW_FIRST_QUEUE_IDX word_idx word
+Returns the queue index of the least significant set bit in a nonzero
+status word.
+.El
+.Ss Functions
+The
+.Fn choosethread
+function asks the active scheduler for the next thread, removes that
+thread from its run queue, marks it running, and returns it.
+If there is no runnable thread, it returns the CPU's idle thread.
+During a kernel panic, it skips threads that are neither system threads
+nor marked to run during the panic.
.Pp
-.Fn procrunnable
-returns zero if there are no runnable processes other than the idle process.
-If there is at least one runnable process other than the idle process, it
-will return a non-zero value.
-Note that the
-.Va sched_lock
-mutex does
-.Em not
-need to be held when this function is called.
-There is a small race window where one CPU may place a process on the run queue
-when there are currently no other runnable processes while another CPU is
-calling this function.
-In that case the second CPU will simply travel through the idle loop one
-additional time before noticing that there is a runnable process.
-This works because idle CPUs are not halted in SMP systems.
-If idle CPUs are halted in SMP systems, then this race condition might have
-more serious repercussions in the losing case, and
-.Fn procrunnable
-may have to require that the
-.Va sched_lock
-mutex be acquired.
+The
+.Fn runq_init
+function initializes an empty run queue.
.Pp
-.Fn choosethread
-returns the highest priority runnable thread.
-If there are no runnable threads, then the idle thread is returned.
-This function is called by
-.Fn cpu_switch
-and
-.Fn cpu_throw
-to determine which thread to switch to.
-.Fn choosethread
-must be called with the
-.Va sched_lock
-mutex held.
+The
+.Fn runq_is_queue_empty
+function returns whether the queue at index
+.Fa idx
+is empty.
.Pp
-.Fn setrunqueue
-adds the thread
+The
+.Fn runq_add
+function inserts
.Fa td
-to the tail of the appropriate queue in the proper priority queue.
-The thread must be runnable, i.e.\&
-.Va p_stat
-must be set to
-.Dv SRUN .
-This function must be called with the
-.Va sched_lock
-mutex held.
+into the queue selected by its
+.Va td_priority .
+The
+.Fn runq_add_idx
+function instead inserts it into the queue at
+.Fa idx ,
+which may differ from the index derived from its priority.
+Both functions insert at the tail of the selected queue, except when
+.Fa flags
+contains
+.Dv SRQ_PREEMPTED ,
+in which case they insert at the head.
+They record the selected index in
+.Va td_rqindex .
.Pp
-.Fn remrunqueue
-removes thread
-.Fa td
-from its run queue.
-If
+The
+.Fn runq_remove
+function removes
.Fa td
-is not on a run queue, then the kernel will
-.Xr panic 9 .
-This function must be called with the
-.Va sched_lock
-mutex held.
+from the queue recorded in its
+.Va td_rqindex .
+It returns
+.Dv true
+if that queue is empty after removal and
+.Dv false
+otherwise.
+.Pp
+The
+.Fn runq_findq
+function searches non-empty queues with indices from
+.Fa lvl_min
+through
+.Fa lvl_max ,
+inclusive, in increasing index order.
+It calls
+.Fa pred
+for each such queue until the predicate accepts one.
+The predicate has the type:
+.Bd -literal -offset indent
+bool pred(int idx, struct rq_queue *queue, void *pred_data);
+.Ed
+.Pp
+The
+.Fa pred_data
+argument is passed to the predicate unchanged and may be used for input
+or output.
+The function returns the first accepted queue index, or \-1 if none
+is accepted.
+.Pp
+The
+.Fn runq_first_thread_range
+function returns the first thread in the lowest-index non-empty queue
+between
+.Fa lvl_min
+and
+.Fa lvl_max ,
+inclusive.
+It returns
+.Dv NULL
+if all queues in that range are empty.
+.Pp
+The
+.Fn runq_not_empty
+function returns whether any queue in
+.Fa rq
+contains a thread.
+It does not modify the run queue.
+The 4BSD scheduler also uses it for a racy check without holding the
+scheduler lock.
+.Pp
+The
+.Fn runq_choose
+function returns the first thread in the lowest-index non-empty queue,
+or
+.Dv NULL
+if the run queue is empty.
+The
+.Fn runq_choose_fuzz
+function searches queues in the same order.
+When
+.Fa fuzz
+is greater than one, it examines up to that many threads at the head
+of the selected queue and prefers the first one that last ran on the
+current CPU.
+Otherwise, it returns the first thread in that queue.
+It also returns
+.Dv NULL
+if the run queue is empty.
+Neither function removes the selected thread.
+.Sh EXAMPLES
+The following fragment initializes a run queue, adds a runnable thread,
+and takes the next thread from it.
+The scheduler supplies
+.Fa rq
+and the runnable thread
+.Fa td .
+The scheduler must hold the lock protecting
+.Fa rq
+while adding, choosing, and removing threads.
+.Bd -literal -offset indent
+struct thread *next;
+
+runq_init(rq); /* Once, before using the run queue. */
+
+/* The scheduler lock is held from here. */
+runq_add(rq, td, 0); /* td is runnable. */
+next = runq_choose(rq);
+if (next != NULL)
+ (void)runq_remove(rq, next);
+.Ed
+.Pp
+The following example finds the first queue containing at least two
+threads.
+.Fn runq_findq
+calls it only for non-empty queues.
+.Bd -literal -offset indent
+static bool
+has_two_threads(int idx __unused, struct rq_queue *q,
+ void *data __unused)
+{
+ struct thread *first;
+
+ first = TAILQ_FIRST(q);
+ return (TAILQ_NEXT(first, td_runq) != NULL);
+}
+
+idx = runq_findq(rq, 0, RQ_NQS - 1, has_two_threads, NULL);
+.Ed
+.Pp
+The result is \-1 if no queue has two threads.
.Sh SEE ALSO
-.Xr cpu_switch 9 ,
+.Xr queue 3 ,
.Xr scheduler 9 ,
.Xr sleepqueue 9
diff --git a/sys/sys/runq.h b/sys/sys/runq.h
--- a/sys/sys/runq.h
+++ b/sys/sys/runq.h
@@ -45,6 +45,8 @@
struct thread;
+/* NOTE: Keep in sync with runqueue.9. */
+
/*
* Run queue parameters.
*/

File Metadata

Mime Type
text/plain
Expires
Mon, Sep 28, 2:16 PM (20 h, 4 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
39691439
Default Alt Text
D60031.diff (11 KB)

Event Timeline