Thema: Task-Scheduler und Speichermanager - konstante Performance

[Dimension]

Ich will hier kurz den Task-Scheduler und den Speichermanager aus meinem Kernel vorstellen und Details zur Implementierung verraten.

Der Scheduler

Nachdem ich über längere Zeit nicht mehr am Kernel gearbeitet habe, bin ich nun endlich wieder dazu gekommen. In den letzten Tagen habe ich am Scheduler gearbeitet. Anforderungen an diesen waren: Taskwechsel in konstanter Zeit, Prioritäten, gewichtete Verteilung der Ausführungszeit und die Strukturierung in Unter-Tasks. Ein Programm soll über seine Rechenzeit frei verfügen und an Unterprogramme verteilen können, aber keinesfalls Programme überhalb seiner Position im Baum beeinträchtigen. Damit wird verhindert, dass sich das System "aufhängt" und nicht mehr auf Benutzereingaben reagiert.

Die Tasks sind zu einer Liste verkettet. Wenn ein Task seine Ausführungszeit verbraucht hat, wird der nächste Task aufgerufen. Die Ausführungszeit des Schedulers wird mitgezählt, Abweichungen zur geplanten Zeit werden auf die nächsten Slice angerechnet. Durch Timeout-Interrupts wird garantiert, dass kein Task seine Ausführungszeit um das Vielfache überschreitet. Die Unter-Tasks sind ebenfalls alle in dieser Liste enthalten. Sobald ein Task mit höherer Priorität aktiv wird, wird die Liste an Beginn und Ende des übergeordneten Containers aufgetrennt und ein anderes Stück eingefügt. Die Position im Teilstück wird gespeichert. Die parallelen Pfade liegen alle im Speicher vor, sind jedoch erstmal nicht mit der Liste verkettet. Suspend/Resume, Spawn/Terminate und Änderung der Priorität arbeiten zuerst auf der Baumstruktur und aktualisieren dann die Liste in konstanter Zeit.

Ich habe mir Gedanken gemacht über die Anzahl der Taskwechsel pro Sekunde (Overhead), die maximale Antwortzeit von Tasks mit hoher Priorität, sowie das Intervall, bis ein Task nach seiner Ausführung wieder aufgerufen wird.

Folgende Konfiguration war das Resultat:

2G Takte/sek
800 aktive Prozesse (Äquivalent)
256K Takte/Zeitscheibe
8K Zeitscheiben/sek
100ms Intervall für erneuten Aufruf eines Tasks
0.125 ms/Zeitscheibe
< 1ms maximale Antwortzeit (des aktiven Tasks mit der höchten Priorität)

Die Speicherverwaltung

Vor dem Scheduler habe ich an der Speicherverwaltung gearbeitet. Die Anforderungen an diese waren: malloc, free und realloc in konstanter Zeit und keine Fragmentierung oder Performanceverlust nach sehr langer Uptime.

Der Speicher wird in 4KB-Seiten verwaltet. Bereiche kleiner 4KB werden innerhalb der Seite in einer Bitmap verwaltet, Bereiche größer 4KB werden aus mehreren 4KB-Seiten zusammengesetzt. Welche Seiten aneinander gereiht werden, steht in einer Tabelle. Elemente eines Vektors oder andere Zugriffe mit Offset dürfen die Seitengrenze nicht überlappen. Elementare Datenstrukturen, sowie die Funktionen memset(), memcpy() und memcmp() habe ich entsprechend implementiert. Details zu jeder einzelnen Seite stehen in einer weiteren Tabelle, dort sind die Seiten in diversen Listen verkettet. Seiten mit freien Slots kleiner 4KB, Slots in der Tabelle für große Bereiche oder die nächste freie Seite können in konstanter Zeit gefunden werden.

Ich habe mir auch Methoden für effizientes garbage Collecting überlegt, bin aber zu keinem Ergebnis gekommen. Als einzige Möglichkeit ohne Auswirkungen auf die Performance sehe ich die Implementierung in Hardware.

Gruß