Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

kernel/sched.c

struct rq {

...

t_rq rt;

...

}

The run queue is very straightforward — a linked list is sufficient^33 :

kernel/sched.c

struct rt_prio_array {

DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */

struct list_head queue[MAX_RT_PRIO];

};

struct rt_rq {

struct rt_prio_array active;

};

All real-time tasks with the same priority are kept in a linked list headed byactive.queue[prio],and

the bitmapactive.bitmapsignals in which list tasks are present by a set bit. If no tasks are on the list,

the bit is not set. Figure 2-23 illustrates the situation.

Increasing prio

Figure 2-23: Run queue of the

real-time scheduler.

The analog ofupdate_curfor the real-time scheduler class isupdate_curr_rt: The function keeps track

of the time the current process spent executing on the CPU insum_exec_runtime. All calculations are

performed with real times; virtual times are not required. This simplifies things a lot.

2.7.3 Scheduler Operations

To enqueue and dequeue tasks is simple: The task is placed or respectively removed from the appropriate

list selected byarray->queue + p->prio, and the corresponding bit in the bitmap is set if at least one task

is present, or removed if no tasks are left on the queue. Notice that new tasks are always queued at the

end of each list.

The two interesting operations are how the next task is selected and how preemption is handled. Con-

siderpick_next_task_rt, which handles selection of the nexttask first. The code flow diagram is shown

in Figure 2-24.

(^33) SMP systems require some more elements for load balancing, but these do not concern us here.