Thema: Verwaltung von Threads

[TheThing]

Hi,
so nach dem Abitur und vor dem Studium hat man ja doch relativ viel Zeit... Daher bin ich auch mal wieder über meinen Kernel bzw. mein OS gestolpert. Der einfachheit mal schnell ein Debian Wheezy in einer VM aufgesetzt, repository geklont und los ging der Spaß.
Dann erstmal jede Menge alte Debugging-Ausgaben entfernt, am Paging-Code geschraubt und mal wieder an der Überarbeitung des Multitaskings gebastelt. Dabei fiel mir folgendes auf: Ich habe zwar die Verwendung von Threads vorgesehen, allerdings ruft mein Scheduler die Threads stumpf nacheinander auf. Da Threads evtl. blockiert sein können, ist das nicht wirklich schön. Nachdem ich dann eine Weile rumprobiert hatte, kam ich zu dem Schluss, dass es ziemlich unpraktisch ist, wenn mein Scheduler versucht, eine Art Baumstruktur abzuarbeiten (Es gibt eine Linked-List mit Prozessen, jeder Prozess enhält eine Linked-List von Threads).
Daher stellt sich mir die Frage: Wie könnte man das besser lösen? Ich habe mir dazu bisher nur tyndur-Code angesehen. Der "alte" Kernel kann ja keine Threads, daher habe ich mir Kernel2 mal angesehen. Da komme ich allerdings nicht so ganz mit. Es werden ja scheinbar Listen genutzt, die der Scheduler stumpf durchlaufen kann. Allerdings gibt es da zwei Listen (threads_available und threads_scheduled). Wofür genau sind die zwei da, und wie werden sie benutzt?

Eine kleine Idee die ich gerade hatte (vielleicht macht Kernel2 das ähnlich?):
Ich nehme zwei Linked-Lists, in der einen hängen alle Threads, die zweite ist leer. Der Scheduler fängt dann an, aus der ersten Liste Threads zu nehmen. Ist der Thread lauffähig, wird er ausgeführt, wenn nicht, wandert er gleich in die zweite Liste. Ist ein Thread durchgelaufen, wandert er auch in die zweite Liste. Wenn die erste Liste leer ist, wird dann getauscht.
Allerdings stellt sich mir da noch eine Frage: Meine momentanen Verwaltungsstrukturen sind ja Baum-mäßig. Wenn ich jetzt Threads einfach in Listen lege, geht mir ja diese klare Zuordnung (Thread gehört zu Prozess) verloren. Wie soll ich dann die Prozesse effizient verwalten? Z.B. wenn ein Prozess gekillt werden muss.

Daher möchte ich hier mal wieder um Rat fragen. Welcher Ansatz ist da vernünftig? Was verwenden andere OS, um dieses Problem zu lösen?

Grüße,
TheThing

[kevin]

tyndur hat logischerweise diese Zuordnung von Threads zu Prozessen (in beide Richtungen, d.h. Threads haben einen Pointer auf ihren Prozess und Prozesse eine Liste von ihren Threads), aber das heißt ja nicht, dass der Scheduler diese Datenstrukturen direkt benutzen muss.

Der Scheduler in kernel2 packt immer alle lauffähigen Threads in eine Liste und arbeitet die dann einen nach dem anderen ab, bis die Liste leer ist. Anschließend wird sie wieder mit allen Threads aufgefüllt. Vermutlich auch nicht der allercleverste Algorithmus, den es gibt...

[MNemo]

Eine kleine Idee die ich gerade hatte (vielleicht macht Kernel2 das ähnlich?):
Ich nehme zwei Linked-Lists, in der einen hängen alle Threads, die zweite ist leer. Der Scheduler fängt dann an, aus der ersten Liste Threads zu nehmen. Ist der Thread lauffähig, wird er ausgeführt, wenn nicht, wandert er gleich in die zweite Liste. Ist ein Thread durchgelaufen, wandert er auch in die zweite Liste. Wenn die erste Liste leer ist, wird dann getauscht.

Hm… und wieso jetzt zwei listen? Wenn du die threads einfach hinten dranhängst sparst du dir das switchen. Und wenn du gleich Anfang und Ende der liste mit einander verbindest, kannst du dir auch gleich noch das Rausnehmen und Anfügen sparen und einfach auf dem Ring im Kreis laufen. Ich würde eventuell in einen Ring bzw. eine Liste nur die lauffähigen threads packen und alles was blockiert ist, in eine andere Liste um nicht ständig prüfen zu müssen ob der thread jetzt laufen darf oder nicht und potentiell viele threads nach einem lauffähigen durchsuchen zu müssen.

[Dimension]

@TeThing: kombiniere die Baumstruktur mit verketteten Listen für alle Taks und für die aktive Untermenge. Der Scheduler läuft dann konstant und nutzt die vollständige Liste für suspend/resume.

Gruß

[TheThing]

Ah, vielen Dank für die Antworten.

tyndur hat logischerweise diese Zuordnung von Threads zu Prozessen (in beide Richtungen, d.h. Threads haben einen Pointer auf ihren Prozess und Prozesse eine Liste von ihren Threads), aber das heißt ja nicht, dass der Scheduler diese Datenstrukturen direkt benutzen muss.

Hm, das klingt nach einer guten Idee. Was mir aber daran irgendwie nicht gefällt ist, dass ja dann jeder Thread in zwei Listen steht, einmal in der Liste des Prozesses und einmal in der Liste der Threads. Aber scheinbar bleibt mir ja da nichts anderes übrig.

@MNemo: Das klingt gut. Ich denke ich werde es so (oder so ähnlich) umsetzen.

[kevin]

Du kannst auch einfach die Liste aller Prozesse durchlaufen (die du sowieso irgendwo brauchst) und dann von den Prozessen ausgehend alle Threads dieser Prozesse.

[Svenska]

Hallo,

oder du behältst deine Baumstruktur für die Verwaltung und hast einen doppelt verketteten Ring im Scheduler, der auf die Baumelemente zeigt (und umgekehrt). Dein Scheduler muss dann nur den Ring entlanglaufen und wenn irgendwas mit den Prozessen passiert, wird der Ring aktualisiert.

Gruß,
Svenska

[Dimension]

Mit "kombinieren" war gemeint, dass die struct der Baumstruktur zusätzlich zu den Eigenschaften parent und childList die Eigenschaften taskNext und -Prev, sowie activeNext und -Prev zu bekommt. Optional können durch weitere verkettete Listen Prioritäten und Synchronisierung implementiert werden. Mir ist nicht klar, inwiefern dein Scheduler Kind-Prozesse unterstützt, aber auch hier sollte der Aufwand im Scheduler mit steigender Anzahl der Tasks ebenfalls konstant bleiben.

Gruß

[TheThing]

Ok, mein momentaner Plan sieht so aus, dass ich zwei doppelt-verkettete Listen für den Scheduler benutze. Eine mit laufenden Threads, die andere mit den blockierten. Die Listen beinhalten im Grunde nur einen Pointer, der auf die Thread-Struktur im Baum zeigt.
Um das ganze schön sauber zu halten, habe ich in den letzten Tagen an der Implementierung einer solchen Liste gebastelt und mich dabei grob an std::list aus C++ orientiert. Genau übernehmen geht ja nicht, da ich meinen Kernel ja in FreeBASIC schreibe.
Meine Liste kann momentan folgendes: push_front, push_back, pop_front und pop_back, dazu noch Konstruktor & Destruktor und das Überladen von new und delete, damit das ganze auch im Kernel klappt. Dazu hab ich noch einen Datentyp namens list_iterator gebaut, der grob C++-ähnliche Funktionen bereitstellt. Mit list.begin() und list.ending() kann ich mir dann so einen Iterator holen und mit list.remove() kann ich das Element an der Position des Iterators entfernen.
Ich denke dass es mir damit möglich sein sollte einen vernünftigen Scheduler zu bauen, und genau das werde ich dann wohl in den nächsten Tagen in Angriff nehmen.

@Dimension: Dein Vorschlag klingt auch sehr interessant. Das wäre ja dann im Endeffekt eine Verschmelzung der beiden Verwaltungsstrukturen zu einer einzigen. Bei richtiger Umsetzung würde mir das ein kmalloc() bei der Erstellung eines Threads ersparen. Eventuell werde ich auf diese Idee zurückgreifen, vor allem falls sich mein bisheriger Ansatz als zu langsam erweisen sollte (FreeBASIC ist nicht gerade ein Rennpferd, aber was solls).

Grüße,
TheThing