14. Aug 2023
Lesedauer 7 Min.
Doppelt verkettet
Das eigene Betriebssystem, Teil 9
Bevor das Kaos OS Multitasking lernt, sind noch einige Vorarbeiten erforderlich.
dotnetpro
Die beiden vorangegangenen Folgen dieser Serie haben sich intensiv mit der virtuellen Hauptspeicherverwaltung beschäftigt [1] und es wurde ein einfacher virtueller Memory-Manager implementiert, welcher mithilfe eines Page Fault Handlers virtuelle Hauptspeicheradressen auf physische Page Frames mappen kann. Außerdem wurde ein einfacher Heap-Manager implementiert [2], der in der Lage ist, Hauptspeicherbereiche auf Byte-Ebene zu allokieren und wieder freizugeben. Auf Basis dieser Funktionalität dreht sich in dieser Folge alles um das Thema Multitasking. Das Ziel: Das Eigenbau-Betriebssystem soll mehrere Tasks parallel verarbeiten können. Allerdings sind dafür zunächst einige Vorarbeiten durchzuführen. Wirklich eingebaut wird das Multitasking erst im nächsten Heft.Der zuletzt implementierte Heap-Manager ist auf der Basis einer einfachen Datenstruktur in der Lage, Hauptspeicherbereiche auf Byte-Ebene zu verwalten. Der Heap-Manager bietet dafür die Funktionen malloc() und free() an, die Sie vielleicht von der C-Programmierung kennen. Beim Heap-Manager handelt es sich um eine der wichtigsten Komponenten eines Betriebssystems, die immer dann benötigt wird, wenn dynamischer Hauptspeicher allokiert werden soll – also auch beim Multitasking.Zunächst soll gezeigt werden, wie Sie eine einfache doppelt verkettete Liste implementieren, da sehr viele Betriebssystem-Funktionen auf dieser Datenstruktur aufbauen.
Eine doppelt verkettete Liste
Die Idee: Jeder Eintrag in der Liste zeigt mithilfe von zwei Zeigern sowohl auf den vorangegangenen als auch auf den nachfolgenden Eintrag (Bild 1). Damit kann man sich in der Liste einfach und ohne Umwege vorwärts und rückwärts bewegen.
Prinzipeiner doppelt verketteten Liste(Bild 1)
Autor
Neben diesen Zeigern müssen dann auch noch die eigentlichen Nutzdaten des Listeneintrags gespeichert und zusätzlich ein Schlüssel (Key) angelegt werden, um jeden Eintrag eindeutig zu identifizieren und auffinden zu können.Über die einzelnen Listeneinträge hinaus wird noch eine weitere Datenstruktur gebraucht, nämlich die Liste selbst. Diese Struktur speichert in einem Zeiger eine Referenz auf den ersten Listeneintrag und zudem die Anzahl der aktuell in der Liste vorhandenen Einträge. Listing 1 zeigt die Definitionen von Liste und Listeneintrag in Form von C-Strukturen. Wie Sie dort sehen, verwendet die Datenstruktur List zusätzlich einen Funktionszeiger (PrintFunctionPtr), über den Sie eine Funktion zuweisen können, welche Listeneinträge auf dem Bildschirm ausgibt. Dieser Funktionszeiger wird in der Funktion PrintList() verwendet; er ermöglicht Ihnen, eine spezifische Ausgabeform für alle unterschiedlichen Arten von Listeneinträgen vorzunehmen.
Listing 1: List und ListEntry
typedef struct <span class="hljs-type">ListEntry</span> <br/>{ <br/> void *<span class="hljs-type">Payload</span>; <br/> unsigned long <span class="hljs-type">Key</span>; <br/> struct <span class="hljs-type">ListEntry</span> *<span class="hljs-type">Next</span>; <br/> struct <span class="hljs-type">ListEntry</span> *<span class="hljs-type">Previous</span>; <br/>} <span class="hljs-type">ListEntry</span>; <br/><br/>typedef struct <span class="hljs-type">List</span> <br/>{ <br/> int <span class="hljs-type">Count</span>; <br/> <span class="hljs-type">ListEntry</span> *<span class="hljs-type">RootEntry</span>; <br/> void (*<span class="hljs-type">PrintFunctionPtr</span>)(void); <br/>} <span class="hljs-type">List</span>;
Um eine neue Liste anzulegen, nutzen Sie die Funktion NewList(), die über malloc() einen neuen Datenblock auf dem Heap allokiert, der so groß ist wie die Datenstruktur List. Im Hintergrund wird hier dann ein Page Fault ausgelöst, wodurch über den physischen Memory-Manager ein neuer Page Frame im Hauptspeicher allokiert wird. In Listing 2 sehen Sie den Code der Funktion NewList().
Listing 2: Anlegen einer neuen Liste
List *NewList() <br/>{ <br/> // Allocate a new List structure on the Heap <br/> List *list = malloc(sizeof(List)); <br/> list-&gt;Count = 0; <br/> list-&gt;RootEntry = 0x0; <br/><br/> return list; <br/>}
In der neu angelegten Liste können Sie nun über die Funktion AddEntryToList() einen neuen Eintrag zur doppelt verketteten Liste hinzufügen. Hierzu wird einfach beginnend vom Wurzeleintrag (RootEntry) der letzte Eintrag der Liste ermittelt und der neue Eintrag am Ende hinzugefügt. Listing 3 zeigt die dafür genutzte Funktion AddEntryToList().
Listing 3: Listeneinträge hinzufügen
void AddEntryToList( <br/> List *List, <br/> void *Payload, <br/> unsigned long Key) <br/>{ <br/> ListEntry *newEntry = NewListEntry( <br/> Payload, Key); <br/><br/> if (!List-&gt;RootEntry) <br/> { <br/> // Add the first, initial entry to the List <br/> List-&gt;RootEntry = newEntry; <br/> } <br/> else <br/> { <br/> ListEntry *currentEntry = List-&gt;RootEntry; <br/><br/> // Move to the end of the List <br/> while (currentEntry-&gt;Next) <br/> currentEntry = currentEntry-&gt;Next; <br/><br/> // Add the new entry to the end of the List <br/> currentEntry-&gt;Next = newEntry; <br/> newEntry-&gt;Previous = currentEntry; <br/> } <br/><br/> // Increment the number of List entries <br/> List-&gt;Count++; <br/>}
Da jedem neuen Listeneintrag ein eindeutiger Schlüssel zugewiesen wurde, lassen sich die Listeneinträge anhand dieses Schlüssels auch wiederfinden. Dazu dient die Funktion GetEntryFromList(), siehe Listing 4.
Listing 4: Listeneintrag finden
ListEntry *GetEntryFromList( <br/> List *List, <br/> unsigned long Key) <br/>{ <br/> ListEntry *currentEntry = List-&gt;RootEntry; <br/> int currentIndex; <br/><br/> while (currentEntry != 0x0) <br/> { <br/> if (currentEntry-&gt;Key == Key) <br/> return currentEntry; <br/><br/> currentEntry = currentEntry-&gt;Next; <br/> } <br/><br/> // The List entry was not found <br/> return (void *)0x0; <br/>}
Das Entfernen eines Eintrags aus der doppelt verketteten Liste erledigt die in Listing 5 gezeigte Funktion RemoveEntryFromList(). Wie Sie am Ende des Listings sehen, wird der vom gelöschten Listeneintrag belegte Hauptspeicher durch Aufruf der Funktion free() wieder freigegeben, damit kein Memory Leak entstehen kann.
Listing 5: Listeneintrag löschen
void RemoveEntryFromList( <br/> List *List, <br/> ListEntry *Entry) <br/>{ <br/> ListEntry *nextEntry = 0x0; <br/> ListEntry *previousEntry = 0x0; <br/><br/> if (Entry-&gt;Previous == 0x0) <br/> { <br/> List-&gt;RootEntry = Entry-&gt;Next; <br/> List-&gt;RootEntry-&gt;Previous = 0x0; <br/> } <br/> else <br/> { <br/> previousEntry = Entry-&gt;Previous; <br/> nextEntry = Entry-&gt;Next; <br/> previousEntry-&gt;Next = nextEntry; <br/> nextEntry-&gt;Previous = previousEntry; <br/> } <br/><br/> List-&gt;Count--; <br/> free(Entry); <br/>} Page Frame Tracking
Im sechsten Teil dieser Artikelserie [3] wurde ein einfacher physischer Memory-Manager implementiert, der die unterschiedlichen freien Regionen des Hauptspeichers verwalten kann, die vom BIOS während des Bootvorgangs gemeldet werden. Implementiert wurde hierfür die Funktion AllocatePageFrame(), die einen neuen, 4 KByte großen physischen Page Frame allokiert und dies in einer Bitmap Mask vermerkt. Die Funktion AllocatePageFrame() wird innerhalb des Page Fault Handlers der virtuellen Speicherverwaltung aufgerufen.In einer späteren Phase der Betriebssystem-Entwicklung gilt es dann aber auch in der Lage zu sein, physisch allokierte Page Frames wieder freizugeben. Dazu dient die Funktion ReleasePageFrame(), die allerdings bisher noch nicht implementiert wurde.Das Problem mit dieser Funktion ist, dass Sie für das Freigeben eines physischen Page Frames einerseits die Page-Frame-Nummer wissen müssen, aber zusätzlich auch, in welcher Bitmap Mask der Page Frame allokiert wurde.Daher ist es erforderlich, beide Informationen bereits beim Allokieren eines Page Frames in einer passenden Datenstruktur zu speichern und diese Information in eine doppelt verkettete Liste einzutragen.Ich habe diese komplette Funktionalität Page Frame Tracking genannt, da mithilfe einer Liste mitprotokolliert wird, welche physischen Page Frames allokiert wurden, damit diese zu einem späteren Zeitpunkt wieder freigegeben werden können. Listing 6 zeigt die Definition der Datenstrukturen PageFrame und TrackedPageFrameListEntry, die für die doppelt verkettete Liste benötigt werden. Das Einfügen eines allokierten Page Frames in diese Liste erledigt die Funktion AddPageFrameToTrackedList(), die im Rahmen der Funktion AllocatePageFrame() des physischen Memory-Managers aufgerufen wird. Dieser Funktion werden die Page-Frame-Nummer und der Index der Memory Region übergeben, in der das Allokieren des Page Frames vorgenommen wurde, vergleiche Listing 7.Listing 6: Datenstrukturen für das Page Frame Tracking
typedef struct PageFrame <br/>{ <br/> unsigned long PageFrameNumber; <br/> unsigned int MemoryRegionIndex; <br/>} PageFrame; <br/><br/>typedef struct TrackedPageFrameListEntry <br/>{ <br/> struct TrackedPageFrameListEntry *Previous; <br/> struct TrackedPageFrameListEntry *Next; <br/> PageFrame *PageFrame; <br/>} TrackedPageFrameListEntry; Listing 7: AddPageFrameToTrackedList()
List *TrackedPageFrames = 0x0; <br/><br/>static void AddPageFrameToTrackedList( <br/> unsigned long PageFrameNumber, <br/> int MemoryRegionIndex) <br/>{ <br/> if (IsHeapInitialized() == 1) <br/> { <br/> if (TrackedPageFrames == 0x0) <br/> TrackedPageFrames = NewList(); <br/><br/> PageFrame *pageFrame = <br/> (PageFrame *)malloc(sizeof(PageFrame)); <br/> pageFrame-&gt;PageFrameNumber = <br/> PageFrameNumber; <br/> pageFrame-&gt;MemoryRegionIndex = <br/> MemoryRegionIndex; <br/><br/> AddEntryToList( <br/> TrackedPageFrames, pageFrame, <br/> PageFrameNumber); <br/> } <br/>}
Nachdem nun alle allokierten Page Frames automatisch mitprotokolliert und in der doppelt verketteten Liste TrackedPageFrames gespeichert werden, können diese vom Kernel mit ReleasePageFrame() auch wieder freigegeben werden. Der Funktion wirddie gewünschte Page-Frame-Nummer als Parameter übergeben, siehe Listing 8.
Listing 8: Page Frame freigeben
void ReleasePageFrame( <br/> unsigned long PageFrameNumber) <br/>{ <br/> BiosInformationBlock *bib = <br/> (BiosInformationBlock *)BIB_OFFSET; <br/> PhysicalMemoryLayout *memLayout = <br/> bib-&gt;PhysicalMemoryLayout; <br/> ListEntry *entry = GetEntryFromList( <br/> TrackedPageFrames, PageFrameNumber); <br/> PageFrame *frame = <br/> (PageFrame *)entry-&gt;Payload; <br/><br/> if (frame != 0x0) <br/> { <br/> PhysicalMemoryRegionDescriptor <br/> *descriptor = <br/> &amp;memLayout-&gt;MemoryRegions <br/> [frame-&gt;MemoryRegionIndex]; <br/> unsigned long *bitmapMask = <br/> (unsigned long *)descriptor-&gt; <br/> BitmapMaskStartAddress; <br/> PageFrameNumber = PageFrameNumber – <br/> (descriptor-&gt;PhysicalMemoryStartAddress <br/> / PAGE_SIZE); <br/><br/> ClearBit(PageFrameNumber, bitmapMask); <br/> RemoveEntryFromList( <br/> TrackedPageFrames, entry); <br/> free(frame); <br/> } <br/>} Kernel Mode und User Mode
Bevor wir uns nun an die Implementierung des Multitaskings wagen, gilt es sich zuvor noch mit den Feinheiten des sogenannten Kernel Modes und des User Modes zu beschäftigen. Eine x64-CPU bietet die Möglichkeit an, CPU-Instruktionen in vier unterschiedlichen Sicherheitsstufen – den sogenannten Privilege Levels – auszuführen. Bild 2 illustriert dieses Konzept.
Kernel Modeund User Modes(Bild 2)
Autor
Code, der im Ring 0 läuft, kann uneingeschränkt alle CPU-Instruktionen ausführen und auf den kompletten Hauptspeicher zugreifen. In modernen Betriebssystemen werden daher OS-Kernel und Gerätetreiber immer im Ring 0 ausgeführt, da diese eine vollständige Hardware-Kontrolle benötigen.Auf der anderen Seite hat Code, der im Ring 3 abläuft, die geringste Sicherheitseinstufung, darf daher nicht alle CPU-Instruktionen ausführen und hat nur auf ausgewählte Hauptspeicherbereiche Zugriff, die das OS-Kernel für Ring-3-Code freigegeben hat.Anwendungsprogramme werden daher immer im Ring 3 ausgeführt, damit diese bei einer fehlerhaften Programmierung nicht das komplette Betriebssystem zum Absturz bringen. Die Ringe 1 und 2 hat Intel ursprünglich für Gerätetreiber geplant; sie werden aber in aktuellen Betriebssystemen nicht verwendet.Ring-3-Code kann beispielsweise nicht auf Input/Output-Ports zugreifen, die zum Lesen und Schreiben von Disk-Sektoren über die ATA-PIO-Schnittstellen benötigt werden. Und auch das Bewegen des Cursors im 80 x 25-Textmodus auf dem Bildschirm erfolgt über Output-Ports, auf die Code im Ring 3 keinen Zugriff hat. Ring-3-Code hat folglich keine direkte Möglichkeit, auf Hardware-Komponenten zuzugreifen. Dadurch wird die Stabilität eines modernen Betriebssystems gewährleistet.Damit Anwendungsprogramme (im Ring 3) mit Hardware-Komponenten zusammenarbeiten können, muss es möglich sein, dass Anwendungsprogramme Funktionen im OS-Kernel (im Ring 0) aufrufen. Dafür muss ein OS-Kernel sogenannte System Calls anbieten. Wie Code, der im Ring 3 läuft, über System Calls mit Kernel-Code im Ring 0 zusammenarbeitet, wird in einer späteren Folge dieser Artikelserie gezeigt.Um nun Code in unterschiedlichen Privilege Levels in einem Betriebssystem ausführen zu können, muss der OS-Kernel für jeden unterstützten Ring Einträge in einer sogenannten Global Descriptor Table (GDT) hinterlegen. Diese Einträge werden als Segmente bezeichnet. Für das Eigenbau-Betriebssystem werden die folgenden Segmente definiert:
- Code Segment für Ring 0.
- Data Segment für Ring 0.
- Code Segment für Ring 3.
- Data Segment für Ring 3.
- Task State Segment (TSS).
Listing 9: Global Descriptor Table initialisieren
void InitGdt() <br/>{ // Initialize the GDT <br/> gdtPointer.Limit = sizeof(GdtEntry) * <br/> (GDT_ENTRIES + 1); <br/> gdtPointer.Base = (unsigned long)gdtEntries; <br/> memset(gdtEntries, 0, <br/> sizeof(GdtEntry) * (GDT_ENTRIES + 1)); <br/><br/> // Initialize the TSS <br/> memset(tssEntry, 0, sizeof(tssEntry)); <br/><br/> // The NULL Descriptor <br/> GdtSetGate(0, 0, 0, 0, 0); <br/><br/> // The Code Segment Descriptor for Ring 0 <br/> GdtSetGate(1, 0, 0, <br/> GDT_FLAG_RING0 | GDT_FLAG_SEGMENT | <br/> GDT_FLAG_CODESEG | GDT_FLAG_PRESENT, <br/> GDT_FLAG_64_BIT); <br/><br/> // The Data Segment Descriptor for Ring 0 <br/> GdtSetGate(2, 0, 0, <br/> GDT_FLAG_RING0 | GDT_FLAG_SEGMENT | <br/> GDT_FLAG_DATASEG | GDT_FLAG_PRESENT, 0); <br/><br/> // The Code Segment Descriptor for Ring 3 <br/> GdtSetGate(3, 0, 0, <br/> GDT_FLAG_RING3 | GDT_FLAG_SEGMENT | <br/> GDT_FLAG_CODESEG | GDT_FLAG_PRESENT, <br/> GDT_FLAG_64_BIT); <br/><br/> // The Data Segment Descriptor for Ring 3 <br/> GdtSetGate(4, 0, 0, <br/> GDT_FLAG_RING3 | GDT_FLAG_SEGMENT | <br/> GDT_FLAG_DATASEG | GDT_FLAG_PRESENT, 0); <br/><br/> // The TSS Entry <br/> GdtSetGate(5, (unsigned long)tssEntry, <br/> sizeof(TssEntry), 0x89, 0x40); <br/><br/> // Install the new GDT <br/> GdtFlush((unsigned long)&amp;gdtPointer); <br/>} Listing 10: Scharfschalten der GDT
[GLOBAL GdtFlush] <br/>; Loads the GDT table <br/>GdtFlush: <br/> CLI <br/> ; The first function parameter is provided in <br/> ; the RDI register on the x64 architecture <br/> ; RDI points to the variable gdtPointer <br/> ; (defined in the C code) <br/> LGDT [RDI] <br/> ; Load the TSS <br/> ; This is the 6th entry from the GDT <br/> ; with the requested RPL of 3 <br/> MOV AX, 0x2B ; <br/> LTR AX <br/> STI <br/> RET
So viel für diesmal. In der kommenden Folge dieser Serie wird nach all den gerade durchgeführten Vorarbeiten das Multitasking per Timer-Interrupt implementiert.
Fussnoten
- Klaus Aschenbrenner, Virtuelle Adressen, Das eigene Betriebssystem, Teil 7, dotnetpro 7/2023, Seite 102 ff., http://www.dotnetpro.de/A2307DIYOS
- Klaus Aschenbrenner, Heap-Manager, Das eigene Betriebssystem, Teil 8, dotnetpro 8/2023, Seite 91 ff., http://www.dotnetpro.de/A2308DIYOS
- Klaus Aschenbrenner, Memory-Management, Das eigene Betriebssystem, Teil 6, dotnetpro 6/2023, Seite 108 ff., http://www.dotnetpro.de/A2306DIYOS
