Run Queues

   

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

graphics/05fig16.gif


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

graphics/05fig17.gif


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 



HP-UX 11i Internals
HP-UX 11i Internals
ISBN: 0130328618
EAN: 2147483647
Year: 2006
Pages: 167

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net