Linux Run Queue

There is one runqueue per processor.  In a run queue, there are 2 priority arrays - one active and one expired.  the array contains a bitmap with each bit reflect if there is any task in the corresponding priority list head.  Task with its timeslice used up will be transferred to the expired array.  Scheduler will schedule task in the active array.  When all task exhausted its timeslice, scheduler will switch the active and expire array.  When a task is transfer to the expire queue, its timeslice is also calculated.  This approach avoids a long delay during priority queue switching time.