We have used the term run queue frequently in this chapter. Let's take a moment to understand what a run queue is, where it is located, and how it is implemented. The run queue does not exist as a single structure. It is built by linking together all runnable threads on the system to appropriate queue headers. Which queue header a runnable kthread is linked to depends on its processor affinity, its priority, kt_pri and its scheduling policy stored in kt_schedpolicy (stored in the thread's kthread structure). To enter a processor's run queue, we start with the mp_threadhd structures. The structures are stored in a number of arrays (dependent on the number of processors and processor sets). Each of the per-processor run queues has 160 mp_threadhd_t elements, while the global POSIX run queue size is controlled by the kernel-tunable rtsched_numpri (default is 32). In either case each run queue header contains two words th_link and tn_rlink. The th_link points to the first thread in this specific run queue, and the th_rlink points to the last thread currently in the queue. Maintaining a dual linkage facilitates the linking of a kthread to either the front or back of its perspective queue. Threads are normally added to the back of a queue except in the case of preemption. The bulk of the run queue consists of the kt_link and kt_rlink pointers maintained in each individual kthread structure As an individual thread's state changes from run-able to blocked (sleeping), these linkage pointers are updated by the kernel as part of the overall scheduling process. These same pointers serve a dual purpose: they link a kthread to other kthreads in the same run queue or to other kthreads that are blocking on the same kernel service or I/O routine. kthreads blocking on the same kernel routine are said to be on a sleep queue. The kthread's present state (kt_stat) notes whether it is on a run queue or a sleep queue. Next, we explore the two types of run queues: global and per-processor. The Systemwide POSIX Run Queues As we have stated, the POSIX run queue is a global entity (one per pset). Each processor starts its search for runnable threads by first checking the POSIX run queue to see if it has any waiting threads. If not, it checks its own per-processor run queue. Figure 5-16 shows the basic principals of the POSIX real-time run queue. Figure 5-16. POSIX Global Real-Time Run Queue The beginning of the POSIX run queue from the kernel's point of view is a data structure named rtsched_info: Listing 5.7. q4 fields structure mp_threadhd This is the total number of runnable threads waiting on all queue's headers in this POSIX queue 0 0 4 0 int rts_nready This index points into the qp[] header array and directs the kernel to the best queue to search for a runnable ktrhead 4 0 4 0 int rts_bestq This is where the tunable number of POSIX queues is stored 8 0 4 0 int rts_numpri Timeslice value for the SCHED_RR policy (set to system timeslice value) 12 0 4 0 int rts_rr_timeslice Per priority timeslice for SCHED_RR2 policy (currently also set to system timeslice value) 16 0 4 0 * rts_timeslicep Pointer to the mp_threadhd array structure (the head of the header array) 20 0 4 0 * rts_qp A pointer to the spinlock used to make this queue mp-safe 24 0 4 0 * rts_lock Points to the pset to which this run queue is attached 28 0 4 0 * rts_pset A count of the number of waiting POSIX threads that have not specified an MPC_MANDATORY binding preference 32 0 4 0 int rts_nready_free To examine the POSIX rtsched run queues using q4, launch a q4 session against the running kernel: | # load all of the POSIX run queues | | q4> load struct rtsched_info from &rtsched_info | | q4> load struct mp_threadhd from rts_qp max rts_numpri | | q4> print x addrof th_link th_rlink | # next make a pile of all the kthreads on nonempty run queues | # (hint: empty queues point to themselves.) | | q4> keep th_thlink != addrof | | q4> load dthread_t from th_link next kt_link until addrof max 100 | # to see much you should try this on a multiprocessor system with running | # POSIX real-time processes |
Next, we will take a look at the per-processor run queues. Per-Processor Run Queues As with the POSIX queues, individual kthreads are linked together and to an appropriate mp_threadhd header structure. The headers are contained in an array within the mpinfo structure. Figure 5-17 shows the layout of the per-processor run queues. Figure 5-17. Per-Processor Run Queues For our purpose here, we are only interested in a small portion of the overall structure, that which deals with the run queue, the structure mp_rq. Listing 5.8. q4 fields structure mp_rp This index points into the qs[] header array and directs the kernel to the best queue to search for a runnable kthread 0 0 4 0 int bestq This is effectively the run queue average for the processor 4 0 4 0 int neavg_on_rq Number of waiting run-able kthreads not locked to any spu 8 0 4 0 int nready_free alpha semaphore-related information 12 0 4 0 int nready_free_alpha Number of waiting threads locked to this spu 16 0 4 0 int nready_locked alpha semaphore-related information used for mp synchronization 20 0 4 0 int nready_locked_alpha 24 0 4 0 int asema_ignored Thread migration information used by the mp load balancer 28 0 4 0 u_int ticks_last_migration 32 0 4 0 u_long cycles_last_migration Pointer to next horse in the FSS carousel (for use by PRM) 42 0 4 0 * nexthorse Spinlock for this processor's run queue 40 0 4 0 * run_queue_lock 44 0 4 0 * qs[0].th_link 48 0 4 0 * qs[0].th_rlink - - - - - - - - - - - 1316 0 4 0 * qs[159].th_link 1320 0 4 0 * qs[159].th_rlink |