Der Scheduler

Der Scheduler ist definiert in sched.c. Die Funktion, welche den als nächstes laufenden Prozess aufruft heißt schedule(). Jeder Prozess hat hierbei eine Zeitscheibe zur Verfügung, in der er maximal auf der CPU laufen kann. Auch hat jeder Prozess eine dynamisch berechnete Priorität, diese sagt dem Scheduler, welcher Prozess als nächstes auf der CPU laufen kann.
Bei Systemen mit mehreren Prozessoren läuft auf jedem Prozessor ein eigener Scheduler (SMP). Die Felder im task_struct, die für den Scheduler interessant sind, sind folgende:

p->need_resched: Dieses Feld gibt an, daß der Scheduler bei der nächsten Möglichkeit aufgerufen werden soll.
p->counter: Speichert die Anzahl der Takte, die ein Prozess in dieser Scheduling-Runde noch laufen darf. Ist die Anzahl kleiner oder gleich null, wird p->nedd_resched gesetzt, da ein neuer Prozess die CPU dann besetzen kann.
p->priority: Gibt die Priorität des Prozesses an
p->rt_priority: Gibt die Priorität eines Echtzeitprozesses an.
p->policy: Gibt die Scheduling Policy an. In dieser ist vermerkt, wie der Prozess vom Scheduler zu behandeln ist. Es gibt drei Scheduling Klassen:
- SCHED_OTHER: Dies sind normale UNIX Prozesse
- SCHED_FIFO: Dies sind Echtzeitprozesse. Sie werden in jedem Fall SCHED_OTHER Prozessen vorgezogen. Acuh können sie nicht von normalen Prozessen unterbrochen werden. Es gibt drei Möglichkeiten Echtzeitprozesse zu unterbrechen: a. Er wandert in eine Waitqueue und wartet auf ein externes Ereignis. b. Er verläßt freiwillig die CPU c. Er wird von einem anderen Echtzeitprozess mit einer höheren Priorität verdrängt.
- SCHED_RR: Dies sind Round Robin Echtzeitprozesse. Beim RoundRobin Verfahren hat jeder Prozess die gleiche Zeitspanne zur Verfügung. Ist diese verstrichen, so kommt der nächste Prozess an die Reihe. Unter Linux werden diese Prozesse genauso behandelt wie die Echtzeitprozesse, mit dem Unterschied, daß sie an das Ende der Runqueue gestetzt werden, wenn sie den Prozessor verlassen

Schauen wir uns nun die schedule() Funktion im Detail an:

	if (!current->active_mm) BUG();

Als erstes wird getestet, ob der immoment aktive Prozess Speicher hat, falls nicht ist irgendetwas schiefgelaufen.

	prev = current;
	this_cpu = prev->processor;

Die lokale Variable prev wird auf den Prozess gestezt, der als letztes gelaufen ist. Die Variable this_cpu merkt sich für welche CPU dieser Scheduler arbeitet.

	if (in_interrupt())
		goto scheduling_in_interrupt;

Falls der Scheduler innerhalb eines Interrupt Handlers aufgerufen wurde liegt ein Fehler vor und es wird ein Fehler ausgegeben.

	release_kernel_lock(prev, this_cpu);

Das globale Kernel Lock wird aufgehoben.

sched_data = & aligned_data[this_cpu].schedule_data;

In diesem struct, den es pro CPU einmal gibt wird gespeichert welcher Prozess immoment läuft und wie lange es her ist, daß der Scheduler aufgerufen wurde.

spin_lock_irq(&runqueue_lock);

Nun wird ein Runqueue lock gesetzt.

if (prev->policy == SCHED_RR)
		goto move_rr_last;
move_rr_back:

Als nächstes wird sich hier um die Round Robin Prozesses gekümmert. Da diese erst in der nächsten Runde wieder drankommen, wird der eben gelaufene an das Ende der Runqueue gepackt.

switch (prev->state) {
		case TASK_INTERRUPTIBLE:
			if (signal_pending(prev)) {
				prev->state = TASK_RUNNING;
				break;
			}
		default:
			del_from_runqueue(prev);
		case TASK_RUNNING:;
	}
	prev->need_resched = 0;

Falls der letzte Task sich weiterhin im TASK_RUNNING state befindet, wird er dort gelassen. Wenn er sich im TASK_INTERRUPTABLE befindet und der Makro signal_pending true zurückliefert, wird der Task in den Running state gebracht. Signale dienen zur Kommunikation zwischen Prozessen. Wenn ein Signal 'pending' ist, heißt dies, daß es zwar abgeschickt, aber noch nicht empfangen wurde. Um ein Signal zu empfangen, muß sich der natürlich im Running state befinden, damit er es bearbeiten kann.
Bei sämtlichen anderen states wird der Prozess von der Runqueue entfernt.

next = idle_task(this_cpu);
	c = -1000;
	if (prev->state == TASK_RUNNING)
		goto still_running;

still_running_back:
	list_for_each(tmp, &runqueue_head) {
		p = list_entry(tmp, struct task_struct, run_list);
		if (can_schedule(p, this_cpu)) {
			int weight = goodness(p, this_cpu, prev->active_mm);
			if (weight > c)
				c = weight, next = p;
		}
	}

Nun wird ermittelt, welcher Prozess die höchste Priorität hat und somit als nächstes laufen wird. Hierzu wird in c die höchste gefundene Priorität gespeichert. In next speichern wir den dazugehörigen Prozess, also den Kandidaten, der wahrscheinlich als nächstes drankommen wird.
Als erstes wird hier der idle_task genommen. Dieser bekommt eine äußerst niedrige Priorität (-1000), in der Hoffnung, daß sich ein Prozess findet, der eine höhere Priorität hat.
Dann wird der Task überprüft, der eben gelaufen ist. Falls er sich immer noch im state TASK_RUNNING befindet, wird c für ihn neu berechnet und der Scheduler merkt sich ihn als nächsten Kandidaten, der besser ist als der idle_task.
Nun werden alle Prozesse der Runqueue untersucht, ob sich ein Prozess findet, der ein besserer Kandidat ist.
Dieses geschieht mittels der goodness() Funktion:

static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{
	int weight;

	/*
	 * select the current process after every other
	 * runnable process, but before the idle thread.
	 * Also, dont trigger a counter recalculation.
	 */
	weight = -1;
	if (p->policy & SCHED_YIELD)
		goto out;

	/*
	 * Non-RT process - normal case first.
	 */
	if (p->policy == SCHED_OTHER) {
		/*
		 * Give the process a first-approximation goodness value
		 * according to the number of clock-ticks it has left.
		 *
		 * Don't do any other calculations if the time slice is
		 * over..
		 */
		weight = p->counter;
		if (!weight)
			goto out;
			
#ifdef CONFIG_SMP
		/* Give a largish advantage to the same processor...   */
		/* (this is equivalent to penalizing other processors) */
		if (p->processor == this_cpu)
			weight += PROC_CHANGE_PENALTY;
#endif

		/* .. and a slight advantage to the current MM */
		if (p->mm == this_mm || !p->mm)
			weight += 1;
		weight += 20 - p->nice;
		goto out;
	}

	/*
	 * Realtime process, select the first one on the
	 * runqueue (taking priorities within processes
	 * into account).
	 */
	weight = 1000 + p->rt_priority;
out:
	return weight;
}

Hier wird zunächst überprüft, ob SCHED_YIELD gesetzt wurde, falls ja, wird eine -1 zurückgeliefert.
Nun wird sich um die Standardprozesse (SCHED_OTHER) gekümmert. Falls der Prozess in dieser Runde keine Zeit mehr zur Verfügnung hat, so wird ebenfalls -1 zurückgeliefert. Die Priorität des Prozesses (also die Zeit, die er noch zur Verfügung hat) wird in der lokalen Variable weight gespeichert, dadurch werden Prozesse bevorzugt, die noch nicht viel CPU Zeit abbekommen haben. Somit werden interaktive Prozesse gegenüber sog. NumberCruchern bevorzugt. Dies macht auch Sinn, da ein Benutzer keine Lust hat lange auf die Reaktion des Rechners bei einer Eingabe zu warten (z.B. bei einem Editor), während es bei einem Compiler viel weniger auffällt, wenn er 2 Sekunden länger braucht.
Falls wir uns in einem SMP System befinden, wird dem Prozess ein großer 'Vorsprung' gegeben, falls er auch schon letztes Mal auf dieser CPU lief. Das Makro PROC_CHANGE_PENALTY ist abhängig davon auf welchem System Linux läuft. Falls der Prozess denselben Speicher benutzt, der gerade geladen ist, wird ihm ebenfalls ein kleiner Vorteil mitgegeben, da man sich hier viele Neuinitialisierungen erspart und dies einen Geschwindigkeitsvorteil mi sich bringt.
Wenn Prozesse nett zu anderen Prozessen sein wollen, dann können sie das nice Feld setzen. Dieses Feld gibt anderen Prozessen etwas von ihrer Rechenzeit ab.
Echtzeitprozessen wird ein sehr großer Vorteil eingräumt, damit sie auf jeden Fall vor allen anderen Prozessen an die Reihe kommen.

if (!c)
		goto recalculate;

Falls nun bei allen Prozessen nur null bei der Prioritätsvergabe herausgekommen ist, so ist augenscheinlich eine Runde vorbei und der Scheduler berechnet bei allen Prozessen p->counter neu. Hierbei werden nicht nur die Prozesse in der Runqueue angefasst, sondern wirklich alle Prozesse.
Von diesem Moment an ist es klar, daß der in prev gespeicherte Prozess als nächstes an die Reihe kommt. Bei SMP Systemen wird nun dem Process Descriptor noch mitgegeben, daß der jetztige Prozess gerade auf dieser CPU läuft, damit kein anderer Scheduler ihn auch zum laufen bringen möchte. Außerdem wird hier noch der sched_data struct aktualisiert.
Ansonsten wird der ausgewählte Prozess zum laufen gebracht.