title: understanding priority arrays in linux kernel
body: <p>I am trying to understand how scheduler of Linux kernel works </p>
  
  <p>As given on this link</p>
  
  <p><a href="http://books.google.co.in/books?id=NXVkcCjPblcC&amp;lpg=PP1&amp;pg=PA47#v=onepage&amp;q&amp;f=false" rel="nofollow">http://books.google.co.in/books?id=NXVkcCjPblcC&amp;lpg=PP1&amp;pg=PA47#v=onepage&amp;q&amp;f=false</a>
  and following link
  <a href="http://www.informit.com/articles/article.aspx?p=101760&amp;seqNum=2" rel="nofollow">http://www.informit.com/articles/article.aspx?p=101760&amp;seqNum=2</a></p>
  
  <p>struct runque is basic data structure on which a scheduler runs</p>
  
  <p>it is </p>
  
  <pre><code>struct runqueue {
      spinlock_t     lock;        /* spin lock which protects this
                                     runqueue */
      unsigned long    nr_running;     /* number of runnable tasks */
      unsigned long    nr_switches;     /* number of contextswitches */
      unsigned long    expired_timestamp;  /* time of last array swap */
      unsigned long    nr_uninterruptible; /* number of tasks in
                                                 uinterruptible sleep */
      struct task_struct *curr;        /* this processor's currently
                                        running task */
      struct task_struct *idle;        /* this processor's idle task */
      struct mm_struct  *prev_mm;      /* mm_struct of last running task
                                        */
      struct prio_array  *active;       /* pointer to the active priority
                                          array */
      struct prio_array  *expired;      /* pointer to the expired
                                           priority array */
      struct prio_array  arrays[2];      /* the actual priority arrays */
      int         prev_cpu_load[NR_CPUS];/* load on each processor */
      struct task_struct *migration_thread;  /* the migration thread on this
                                                processor */
      struct list_head  migration_queue;   /* the migration queue for this
                                               processor */
      atomic_t      nr_iowait;      /* number of tasks waiting on I/O
                                     */
  }
  </code></pre>
  
  <p>above has two members </p>
  
  <pre><code>struct prio_array  *active;       /* pointer to the active priority
                                      array */
  struct prio_array  *expired;      /* pointer to the expired priority array */
  </code></pre>
  
  <p>and struct prio_array is defined as </p>
  
  <pre><code>struct prio_array {
      int        nr_active;      /* number of tasks */ 
      unsigned long   bitmap[BITMAP_SIZE]; /* priority bitmap */
      struct list_head queue[MAX_PRIO];   /* priority queues */
  };
  </code></pre>
  
  <p>I am not clear with following sentence </p>
  
  <p><strong>Question 1)</strong><br>
  <code>Each priority array contains one queue of runnable processors per priority level.</code> </p>
  
  <p>among the above definition of <code>struct prio_array</code> <strong>where is the que of runnable processors</strong> </p>
  
  <p>then it says </p>
  
  <blockquote>
  <pre><code>The priority arrays also contain a priority bitmap used to  
  </code></pre>
    
    <p>efficiently discover the highest priority runnable task in the  system.</p>
  </blockquote>
  
  <p>then it says 
  "With 140 priorities and 32-bit words, this is five."</p>
  
  <p>how does it comes at conclusion that this is five what is mathematical calculation behind it?</p>
  
  <p>the above are excerpts from chapter 4 of book which are published in 2nd link both contain same text.Just posted here for sake of clarity.</p>
  
  <p>*<em>UPDATE1 *</em>
  based on comments I just wanted to clarify what I am asking 
  author says </p>
  
  <blockquote>
    <p>BITMAP_SIZE is the size that an array of unsigned long typed
    variables would have to be to provide one bit for each valid priority
    level. With 140 priorities and 32-bit words, this is five.</p>
  </blockquote>
  
  <p><strong>Question 2)</strong><br>
  What I am not clear is one bit for each priority level is given and 140 priority levels are there so how is the array size coming 5 I am not getting the logic of BITMAP_SIZE calculation not 140/32=5</p>
  
  <p>it has some thing to do with following paragraph </p>
  
  <pre><code>    When a task of a given priority becomes runnable (that is,  
   its state becomes TASK_RUNNING), the corresponding bit in the 
  bitmap is set to one. For example, if a task with priority seven is 
  runnable, then bit seven is set
  </code></pre>
  
  <p>on links which is where array         </p>
  
  <pre><code> unsigned long   bitmap[BITMAP_SIZE]; /* priority bitmap */
  </code></pre>
  
  <p>is set so basically what I am not clear is how this array is getting set and see the Question 1 also if I am able to explain correctly.</p>
  
  <p><strong>UPDATE 2 and explanation of answer below</strong> </p>
  
  <p>With the answer below I am just adding a small explanation it might help some one in future 
  if they come here basically </p>
  
  <p>scheduler maintains a runque and the list of runnable processes each runnable process is on exactly one runqueue, the articles to whose links I gave have considered multi processor systems with many run ques, coming back to our situation with one processor and a runque with processes at various priority levels </p>
  
  <p>there are 140 priority levels each priority levels has different processes in TASK_RUNNING state say for example there can be many  process of priority 8 and so on (I took 8 just as example)
   struct runque points to priority array which tells</p>
  
  <pre><code>btimap[BITMAP] /* this is the priority level 
  struct list_head /* points to the start of list of processes of that run level
  </code></pre>
  
  <p>So a runque points to priority array and from priority array you can easily get the process 
  which needs to be executed in O(1) time.</p>