Ceci est la version HTML du fichier http://www.geocities.com/kejriwal_nidhi/ece6277classpr/Downloads/FreeBSDscheduler.pdf. Lorsque G o o g l e explore le Web, il crée automatiquement une version HTML des documents récupérés. Pour créer un lien avec cette page ou l'inclure dans vos favoris/signets, utilisez l'adresse suivante : http://www.google.com/search?q=cache:diS3q4oMK_sC:www.geocities.com/kejriwal_nidhi/ece6277classpr/Downloads/FreeBSDscheduler.pdf+scheduler+FreeBSD&hl=fr&ie=UTF-8. Google n'est ni affilié aux auteurs de cette page ni responsable de son contenu. Les termes de recherche suivants ont été mis en valeur :  scheduler  freebsd

---

Page 1

The FreeBSD scheduler

10/28/01

Antonis Argyriou

Introduction

FreeBSD is a UNIX operating system for the Intel x86 platform based on UC

Berkeley's 4.4BSD-Lite release. FreeBSD's scheduler is a typical decay usage

priority scheduler. The scheduler employs a multi-level feedback queue in which

processes with equal priority reside on the same run-queue. The scheduler runs

processes round-robin from the highest priority non-empty runqueue. Long

(100ms) time slices make TLB and cache state flushing infrequent, imposing

minimal overhead on CPU-bound processes. The scheduler favors interactive

processes by lowering the priority of processes as they consume CPU time and

by preempting processes before their quanta expire if a higher priority sleeping

process wakes up. The scheduler prevents starvation by periodically raising the

priority of processes that have not recently run. FreeBSD's scheduler also

employs higher priorities for processes holding kernel resources. These kernel

priorities cause processes to release high-demand kernel resources quickly,

reducing the contention for these resources.

Further details

The FreeBSD scheduler has 32 runqueues for each "class" of scheduling

policies. With the term "class" we mean the normal FreeBSD process, real time

process or idle processes. The runqueues for normal processes consist of 128

priorities. These priotity levels are split into groups of 4, and every group of them

is mapped to a specific runqueue. For example in the runqueue with number 0,

there will be the processes that have priorities from 0-3. So 4*32=128. The first

50 priority levels (I will have to verify that) are reserved for kernel related

processes. Real time scheduled process have only 32 priority levels. Each of

these priority levels is dedicated to a runqueue. The scheduler decides which

processes to run next by, locating the process with the highest priority in the first

non-empty queue. The order in which the queues are searched is RT, normal,

idle.

Code samples

A)

in this part you can see the function that chooses the next process to run by

searching all the runqueues. The

"queuebits"

is a 32 bit word, in which each bit is

"1" if the respective runqueue (0-31) is not empty.

Reference:

/usr/src/sys/kern/kern_switch.c

chooseproc(void)

{

struct proc *p;

struct rq *q;

u_int32_t

*which;

u_int32_t

pri;

---

Page 2

#ifdef SMP

u_char

id;

#endif

if (rtqueuebits) {

pri = ffs(rtqueuebits) - 1;

q

=

&rtqueues[pri];

which

=

&rtqueuebits;

} else if (queuebits) {

pri = ffs(queuebits) - 1;

q

=

&queues[pri];

which

=

&queuebits;

} else if (idqueuebits) {

pri = ffs(idqueuebits) - 1;

q

=

&idqueues[pri];

which

=

&idqueuebits;

} else {

return

NULL;

}

p = TAILQ_FIRST(q);

B)

in this part you can see the function that adds processes to their respective

runqueue by examining the "class" in which they belong. It also adds this process

to the end off the respective runqueue.

Reference:

/usr/src/sys/kern/kern_switch.c

void

setrunqueue(struct proc *p)

{

struct rq *q;

u_int8_t

pri;

KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));

if (p->p_rtprio.type ==

RTP_PRIO_NORMAL

) {

pri

=

p->p_priority

>>

2;

q

=

&queues[pri];

queuebits

|=

1

<<

pri;

}

else if (p->p_rtprio.type ==

RTP_PRIO_REALTIME

||

p->p_rtprio.type ==

RTP_PRIO_FIFO

) {

pri

=

p->p_rtprio.prio;

q

=

&rtqueues[pri];

rtqueuebits |= 1 << pri;

} else if (p->p_rtprio.type ==

RTP_PRIO_IDLE

) {

pri

=

p->p_rtprio.prio;

q

=

&idqueues[pri];

idqueuebits |= 1 << pri;

} else {

panic("setrunqueue: invalid rtprio type");

}

p->p_rqindex = pri;

TAILQ_INSERT_TAIL(q, p, p_procq);

}

---

Page 3

C)

in this part it is depicted the exact point in the code where the function

chooseproc() is called. Note that this file is machine dependent and thus it

contains critical parts of the kernel in assembly for the x86. Before in fact the

system enters this part of the code it disables interrupts.

Reference:

/usr/src/sys/i386/i386/swtch.s

sw1a:

call _chooseproc

/* trash ecx, edx, ret eax*/

testl

%eax,%eax

CROSSJUMP(je, _idle, jne)

(1)

/* if no proc, idle */

movl

%eax,%ecx

(1)

When no processes are on the runqueue, cpu_switch() (is the function that

this part of the code is included) branches to _idle to wait for something to come

ready.

D)

Here it is presented the function that computes the priorities every hz ms

(100). There are however other functions that decide upon the recompution of

priorities of processes with other characteristics.

Reference:

/usr/src/sys/kern/kern_synch.c

/*

* Recompute process priorities, every hz ticks.

*/

/* ARGSUSED */

static void

schedcpu(arg)

void

*arg;

{

register fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);

register struct proc *p;

register int realstathz, s;

realstathz = stathz ? stathz : hz;

LIST_FOREACH(p, &allproc, p_list) {

/*

* Increment time in/out of memory and sleep time

* (if sleeping). We ignore overflow; with 16-bit int's

* (remember them?) overflow takes 45 days.

*/

p->p_swtime++;

if (p->p_stat == SSLEEP || p->p_stat == SSTOP)

p->p_slptime++;

p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT;

/*

* If the process has slept the entire second,

* stop recalculating its priority until it wakes up.

*/

if (p->p_slptime > 1)

continue;

s = splhigh();

/* INTERRUPTS DISABLED HERE!!!!*/

---

Page 4

/*

* p_pctcpu is only for ps.

*/

#if

(FSHIFT

>=

CCPU_SHIFT)

p->p_pctcpu += (realstathz == 100)?

((fixpt_t) p->p_cpticks) << (FSHIFT - CCPU_SHIFT):

100 * (((fixpt_t) p->p_cpticks)

<< (FSHIFT - CCPU_SHIFT)) / realstathz;

#else

p->p_pctcpu += ((FSCALE - ccpu) *

(p->p_cpticks * FSCALE / realstathz)) >> FSHIFT;

#endif

p->p_cpticks

=

0;

if (p->p_priority >= PUSER) {

if ((p != curproc) &&

#ifdef SMP

p->p_oncpu == 0xff &&

/* idle */

#endif

p->p_stat == SRUN &&

(p->p_flag & P_INMEM) &&

(p->p_priority / PPQ) != (p->p_usrpri / PPQ)) {

remrunqueue(p);

p->p_priority

=

p->p_usrpri;

(2)

setrunqueue(p);

}

else

p->p_priority

=

p->p_usrpri;

}

splx(s); /*INTERRUPTS ENABLED AGAIN*/

}

vmmeter();

wakeup((caddr_t)&lbolt);

timeout(schedcpu, (void *)0, hz);

}

(2)

When the scheduler finds a process which satisfies some constraints (in the if

statement), it changes its priority to new user defined priority value. This is done

by removing the process from the one runqueue and inserting it to the other