Queues

Listen Implementation

Es kommt relativ häufig vor, daß der Scheduler alle Prozesse, die gerade Laufen, TASK_RUNNING, durchsehen muß. Wenn er jedesmal die gesamte Liste der Prozesse durchlaufen müßte und sich dabei nur die mit dem entsprechenden state Feld heraussuchen müßte, wäre die eine ziemliche Verschwendung von Resourcen. Einfacher ist es hier weitere Listen einzuführen.
Alle Prozesse, die nun gerade am Laufen sind, werden in einer Liste mit dem Namen runqueue zusammengefasst.
Die Prozesse, die gerade am Laufen sind werden in der runqueue zusammengefasst. Prozesse, die sich in den Zuständen TASK_INTERRUPTABLE oder TASK_UNINTERRUPTABLE befinden warten auf unterschiedliche Ereignisse, die nicht aus den Prozess Descriptoren hervorgehen. Somit sind sie auch in verschiedenen Listen zusammengefasst, die man als waitqueues bezeichnet.
Prozesse, die sich in den Zuständen TASK_STOPPED oder TASK_ZOMBIE befinden, sind in keinen weiteren queues zusammengefasst, da sie entweder über die PID oder über die Eltern-Kind-Beziehung gefunden werden.

Alle oben genannten queues werden mittels einer Listenstruktur, die in list.h definiert ist, gebaut. Man bezeichnet sie deswegen auch list.h implementation. Im Kernel 2.2 gab es für die runqueue und die waitqueues noch eigene Implementationen, diese ist jedoch aufgegeben worden zugunsten der jetztigen effizienteren Lösung.
Die zentrale Datenstruktur hierbie ist der struct list_head:

struct list_head {
	struct list_head *next, *prev;
};

struct list_head

Zum Erzeugen und Initialisieren einer neuen Liste gibt es drei verschiedene Makros:

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

INIT Makros

Jeder dieser Makros initialisiert eine leere Liste, indem der prev und next Pointer auf sich selber zeigen. Sie sind für verschiedene Situationen geschrieben.
Wie auch bei der Prozessliste gibt es auch hier ein Makro, welches alle Elemente durchgeht:

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

list_for_each Makro

Im Gegensatz zu einer üblichen verlinkten Liste fällt hier auf, daß es kein Feld in list_head gibt, welches die Daten hält. Dies stellt die Frage, wo die Nutzaten sind. Wenn wir uns hierzu nochmal den task_struct anschauen, sehen wir das für die run_list der Typ ein head_list ist (Man beachte: kein Pointer!). Möchte man nun alle Elemente der Liste durchgehen, so kann man dies mit list_for_each tun, man erhält dann allerdings immer nur einen struct head_list. Um an die eigentlichen Nutzdaten zu kommen, benötigt man das Makro list_entry:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

list_entry Makro

Dies hat drei Parameter:
- ptr: Den Pointer auf den entsprechenden list_head
- type: Den Typ des structs, in dem der list_head sitzt.
- member: Der Name des Feldes von list_head.
Der Rückgabewert ist ein Pointer auf den struct, in dem der head_list struct sich befindet.
Dieses Makro arbeitet dabei folgendermaßen:
Mittels (unsigned long)(&((type *)0)->member) ermittelt man den Abstand zwischen dem Anfang des member structs und der Stelle an der der struct, in dem er Mitglied ist anfängt. Dies wird nun nun von ptr abgezogen. Nun haben wir die Adresse an der der struct anfängt und brauchen diese nur noch in den entsprechenden Typ casten.
Ein Beispiel hierfür ist die Stelle im Scheduler in der er überprüft, welche Prozess die höchste Priorität hat:

static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;

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;
		}
	}

aus: sched.c

Hier wird die runqueue mit dem LIST_HEAD Makro erzeugt. *tmp ist der Pointer, der uns als Laufvariable durch die Liste dient. Mittels list_for_each laufen wir durch die Liste. Um nun den jeweiligen task_struct zu erhalten, nutzen wir das list_entry Makro und speichern den Rückgabewert in p.