Thema: Threads blockieren und wieder aufwecken

[erik.vikinger]

Hallo FlashBurn,


das Problem entsteht IMHO dadurch das Du in acquire() zuerst m_Lock.release() und danach t->wait() machst, sobald Du diese Reihenfolge umkehrst ist Dein Race-Condition-Problem komplett gelöst. Aber ich schätze mal t->wait() kommt nicht sofort sondern erst nach dem Wecken wieder zurück, das ist IMHO eine ungünstige Kernel-Architektur. Bei meinem Kernel wird es möglich sein das ein Thread sich schlafen legt aber nicht sofort die CPU frei gibt (per Scheduler o.ä.) so das er noch andere Dinge erledigen kann bevor er den Scheduler aufruft.

Diese Race-Condition mit irgendwelchen Stati im Thread-Descriptor zu lösen erscheint mir auf jeden Fall viel zu umständlich und zu kompliziert, das bläht IMHO nur den Scheduler unnötig auf.


Grüße
Erik

[FlashBurn]

das Problem entsteht IMHO dadurch das Du in acquire() zuerst m_Lock.release() und danach t->wait() machst, sobald Du diese Reihenfolge umkehrst ist Dein Race-Condition-Problem komplett gelöst. Aber ich schätze mal t->wait() kommt nicht sofort sondern erst nach dem Wecken wieder zurück, das ist IMHO eine ungünstige Kernel-Architektur.

Jap, genau das ist das Problem. Wird also nix mit einer schnellen Semaphore.

Diese Race-Condition mit irgendwelchen Stati im Thread-Descriptor zu lösen erscheint mir auf jeden Fall viel zu umständlich und zu kompliziert, das bläht IMHO nur den Scheduler unnötig auf.

Also ob ich nun Code für die Stati habe (welchen ich so oder so brauche) oder die Locks im Scheduler behandeln muss, kommt doch bestimmt aufs gleiche raus.

Ich könnte mir gerade vorstellen, das ich ne spezielle Funktion im Scheduler habe, wo ich ein reschedule durchführe, aber auch die Adresse einer Spinlock mit übergeben und erst wenn der Thread wirklich im Warten-Zustand ist, wird der Lock freigegeben. Damit wird der Lock aber "verdammt lange" gehalten und ich hätte trotzdem noch ein Problem mit wait() und resume()

Was schlägst du denn vor?

Edit::

Wenn ich folgendes verwende:

Code: [Auswählen]

void
Thread::resume()
{
    if(likely(Atomic::addTestZero(&m_WaitStatus,1) && m_Status == THREAD_STS_WAITING))
        Scheduler::addThread(this);
}

Müsste doch das Problem auch schon weg sein oder?

[erik.vikinger]

Hallo,

Was schlägst du denn vor?

Mein Vorschlag ist nach wie vor m_Lock.release() und t->wait() zu vertauschen, das dürfte IMHO die Race-Condition am zuverlässigsten beseitigen. Vor allem bleibt so der Scheduler von Locks usw. verschont (ein schlanker Scheduler ohne unnützen Code, der nur selten nötig ist, bringt auch mehr Performance).


Grüße
Erik

[FlashBurn]

Mein Vorschlag ist nach wie vor m_Lock.release() und t->wait() zu vertauschen, das dürfte IMHO die Race-Condition am zuverlässigsten beseitigen. Vor allem bleibt so der Scheduler von Locks usw. verschont

Das geht ja leider nicht, da wait() erst zurück kommt, wenn der Thread wieder aufgeweckt wird. Den zweiten Satz verstehe ich gar nicht, was meinst du damit, dass der Scheduler von Locks verschont bleibt? Wenn du dann in den Scheduler gehst (nachdem du den Lock freigegeben hast), hast ja wieder das Problem, das ja der Thread schonwieder in der ReadyQueue sein kann, bevor du überhaupt den Thread abgegeben hast.

[erik.vikinger]

Hallo,

Das geht ja leider nicht, da wait() erst zurück kommt, wenn der Thread wieder aufgeweckt wird.

Das ich das für doof halte hab ich ja schon geschrieben. Dieses wait muss doch nur den Zustand des Threads (also alle Register usw.) passend sichern und den Status auf BLOCKED_FOR_EVENT setzen, danach kann es doch problemlos wieder zurück kommen und muss nicht zwangsläufig den Scheduler bitten einen anderen Thread auf die CPU zu holen. Ich sehe da einfach kein Problem.

Den zweiten Satz verstehe ich gar nicht, was meinst du damit, dass der Scheduler von Locks verschont bleibt? Wenn du dann in den Scheduler gehst (nachdem du den Lock freigegeben hast), hast ja wieder das Problem, das ja der Thread schonwieder in der ReadyQueue sein kann, bevor du überhaupt den Thread abgegeben hast.

Es kann sogar noch schlimmer kommen: nachdem der Thread das m_Lock.release() ausgeführt hat könnte auf einer anderen CPU dieser Thread bereits wieder in die runnable-Liste geholt werden (durch ein Sem::release()) und auf noch einer weiteren CPU sogar ausgeführt werden bevor der Thread auf der ersten CPU dann den Scheduler aufruft (falls die CPU 1 mit einem so extrem geringem Takt läuft dass das alles zwischen einem RET und einem CALL dieser CPU passieren kann). Der Thread könnte also theoretisch zwei mal parallel auf zwei verschiedenen CPUs laufen, das ist aber auch überhaupt gar kein Problem weil der Thread auf der ersten CPU ja nichts kritisches mehr tut (er ändert auf jeden Fall nichts mehr im Thread-Descriptor usw.).
Damit das der Scheduler von den Locks verschont bleibt meine ich das im Scheduler eben keinerlei Code für diese Dinge drin sein muss. Du weißt doch: KISS.


Grüße
Erik

[FlashBurn]

Dieses wait muss doch nur den Zustand des Threads (also alle Register usw.) passend sichern und den Status auf BLOCKED_FOR_EVENT setzen, danach kann es doch problemlos wieder zurück kommen und muss nicht zwangsläufig den Scheduler bitten einen anderen Thread auf die CPU zu holen. Ich sehe da einfach kein Problem.

Da wären wir wieder bei sinnlosem Zeit Verbraten

Zumal ich nicht ganz verstehe wie der Thread dann die CPU abgibt und da wäre dann noch ein Problem, welches du eventuell nicht bedacht hast, KernelThreads. Die speichern ihren Zustand auf dem Stack und wenn der gleiche Thread (und damit der gleiche Stack) auf 2 verschiedenen CPUs läuft ist das ganz schlecht

Es kann sogar noch schlimmer kommen: nachdem der Thread das m_Lock.release() ausgeführt hat könnte auf einer anderen CPU dieser Thread bereits wieder in die runnable-Liste geholt werden (durch ein Sem::release()) und auf noch einer weiteren CPU sogar ausgeführt werden bevor der Thread auf der ersten CPU dann den Scheduler aufruft (falls die CPU 1 mit einem so extrem geringem Takt läuft dass das alles zwischen einem RET und einem CALL dieser CPU passieren kann). Der Thread könnte also theoretisch zwei mal parallel auf zwei verschiedenen CPUs laufen, das ist aber auch überhaupt gar kein Problem weil der Thread auf der ersten CPU ja nichts kritisches mehr tut (er ändert auf jeden Fall nichts mehr im Thread-Descriptor usw.).

Wie oben beschrieben ist das leider sehr wohl ein Problem für KernelThreads (und die braucht man auf x86 sowieso, zwecks "hlt"). Für UserThreads ist es für unterbrechbare Kernel ein Problem (wieder der Stack).

[kevin]

Svenska meinte im IRC, ich soll hier ruhig klugscheißen, also tue ich das hiermit: Ein Semaphor ist männlich und heißt genau so, Semaphore sind mehrere davon.

[FlashBurn]

Ein Semaphor ist männlich und heißt genau so, Semaphore sind mehrere davon.

Das stimmt so nicht ganz Wenn du von der eingedeutschten Variante redest, dann hast du recht, bei der englischen nicht. Ich versuche immer die englischen Begriffe zu verwendet, da das eingedeutschte mitunter gar nichts mehr mit dem Original zu tun hat (Stack -> Keller).

[erik.vikinger]

Hallo,

Da wären wir wieder bei sinnlosem Zeit Verbraten

Wieso? Das Sichern der CPU-Register und Setzen des Status muss doch sowieso gemacht werden. Ich mache im Endeffekt genau das selbe wie Du auch, nur in anderer Reihenfolge.

Zumal ich nicht ganz verstehe wie der Thread dann die CPU abgibt

Indem er den Scheduler aufruft und dieser einfach den nächst besten Thread aus der runnable-Liste holt und diesen lädt aber eben ohne vorher irgendwas zu sichern (das wurde ja bereits in wait() gemacht). Ich trenne diese 2 Dinge nur, sonst nichts.

und da wäre dann noch ein Problem, welches du eventuell nicht bedacht hast, KernelThreads.

Doch, bedacht hab ich das, in meinem Konzept sind Kernel-Stacks immer CPU-lokal und das müsste doch eigentlich auch bei x86 gehen. Dafür hab ich aber keine Kernel-Threads, obwohl IMHO auch das lösbar ist (bei x86, inklusive HLT).


Grüße
Erik

[FlashBurn]

Indem er den Scheduler aufruft und dieser einfach den nächst besten Thread aus der runnable-Liste holt und diesen lädt aber eben ohne vorher irgendwas zu sichern

Das Sichern wird bei mir entweder beim Kernel-Eintritt (UserThread) oder halt aufm Stack (KernelThread) gemacht. Bei letzterem bin ich mir gerade nicht sicher, ob ich den Teil nicht vllt bei meinem aktuellen Code vergessen habe

Doch, bedacht hab ich das, in meinem Konzept sind Kernel-Stacks immer CPU-lokal und das müsste doch eigentlich auch bei x86 gehen.

Habe ich ja auch, aber halt nicht für KernelThreads, die brauchen ihren eigenen Stack.

Dafür hab ich aber keine Kernel-Threads, obwohl IMHO auch das lösbar ist (bei x86, inklusive HLT).

Wie?

[Svenska]

Svenska meinte im IRC, ich soll hier ruhig klugscheißen, also tue ich das hiermit: Ein Semaphor ist männlich und heißt genau so, Semaphore sind mehrere davon.

Och, jetzt bin ich wieder schuld oder was?

[FlashBurn]

Beim Durchgehen meines Codes ist mir aufgefallen, dass der aktuelle Code unter SMP und KernelThreads noch gar nicht funktionieren würde. Denn der Scheduler braucht seinen eignen Stack, würde er den Stack vom Thread mitbenutzen und der Thread läuft dann miteinmal auf einer anderen CPU bevor der Scheduler fertig ist, würde auf der anderen CPU der Stack vom Scheduler überschrieben werden.
Das hatte ich halt immer so gelöst, dass der Scheduler seinen eigenen Stack bekommt.

Durch diesen Kniff bin ich jetzt auf folgende Lösung gekommen. Ich habe eine Thread::prepareToWait() Methode und diese speichert den aktuellen State des Threads (wenn es ein UserThread ist, direkt in der Thread-Struct und ansonsten halt auf dem Stack) und wechsele zum Scheduler-Stack der CPU. Dadurch befindet sich der Thread dann im Warten-Status, kann auf einer anderen CPU wieder laufen, aber er kann auch noch auf der aktuellen CPU eventuelle Arbeit fertigstellen.

Damit hätte ich dann folgenden Code:

Code: [Auswählen]

void
Sem::acquire()
{
    m_Lock.acquire();
   
    if(likely(Atomic::subTestNeg(&m_Count,1))) {
        Thread* t= Thread::getCurrThread();
       
        m_Threads.addTail(t);

        t->prepareToWait()
       
        m_Lock.release();
       
        Scheduler::reschedule();
    } else {
        m_Lock.release();
    }
}

Womit ich zwar immernoch ein Problem mit wait()/resume() habe, aber wenn anstatt des einfachen Counters ne komplette Semaphore dafür nutze (was ja leider "mehr" Code bedeutet) dürfte dass dann auch zuverlässig funktionieren.

Oder hat jemand da noch ne andere Idee für?

Edit::

Toll, ist mir jetzt gerade auch an der Variante ein Problem aufgefallen

Ich muss irgendwie an die EIP für die Rücksprungadresse von Sem::acquire() rankommen, weil ansonsten der Lock für die Semaphore nochmal freigegeben wird und das kann ja wieder zu Problemen führen. Also nochmal daran pfeilen.

[erik.vikinger]

Hallo,

Och, jetzt bin ich wieder schuld oder was?

Ja, einer muss eben den Kopf hin halten und wenn sich jemand findet der im IRC die Finger nicht still halten konnte (das muss auch niemand abstreiten, ich bin Zeuge) dann darf er im Forum ruhig den Sündenbock spielen.

Das Sichern wird bei mir entweder beim Kernel-Eintritt (UserThread)

Warum? Es gibt doch bestimmt auch viele Syscalls wo gar nicht alle Register gesichert werden müssen. Ich sichere immer nur dann wenn es wirklich nötig ist und auch nur das was die ABI vorschreibt. Ich weiß dass das bei x86 mit dem zentralen Einsprungspunkt (wo alles durch muss) eben anders gelöst wird und die paar Register kosten auch nicht die Welt, aber wirklich als elegant empfinde ich das nicht.

oder halt aufm Stack (KernelThread) gemacht

Warum wird das nicht auch im Thread-Descriptor gesichert? Das ist doch schon wieder eine unnötige Fallunterscheidung.

Dafür hab ich aber keine Kernel-Threads, obwohl IMHO auch das lösbar ist (bei x86, inklusive HLT).

Wie?

Für die spezifischen Kernel-Stacks der Kernel-Threads benötigt man schlussendlich doch eine Fallunterscheidung (das wäre für mich ein wichtiger Grund auf Kernel-Threads gleich ganz zu verzichten) im Scheduler und für HLT muss eben unmittelbar vorher STI und unmittelbar hinterher CLI benutzt werden aber damit hier der Scheduler nicht noch eine Fallunterscheidung wegen dem Sichern/Wiederherstellen von Registern benötigt sollten die Idle-Threads ihre Register selber vor dem HLT im Thread-Descriptor sichern und hinter dem HALT von dort wieder laden aber auch das ist IMHO nicht so arg schlimm.

Das hatte ich halt immer so gelöst, dass der Scheduler seinen eigenen Stack bekommt.

Sorry, wenn ich das wieder so deutlich raus hängen lass aber KISS ist Dir wirklich nicht sonderlich vertraut oder? Wenn Du schon CPU-lokale Kernel-Mode-Stacks hast wozu benötigst Du dann noch extra (auch CPU-lokal?) Scheduler-Stacks? Ich habe wirklich den Verdacht das Du für jedes Problem die kompliziertest mögliche Lösung suchst (und auch findest) nur um dann noch einen extra dicken Haufen zusätzlicher Probleme zu bekommen (für die Du dann auch wieder die maximalst umständlichste Lösung suchst).

Durch diesen Kniff bin ich jetzt auf folgende Lösung gekommen. Ich habe eine Thread::prepareToWait() Methode und diese ....

Das heißt das Du aus 2 Funktionsaufrufen 3 gemacht hast ohne dadurch an Funktionalität zu gewinnen? Ich nehme an Du kannst Dir meine Begeisterung geradezu bildlich vorstellen.
Zum Fertigstellen von Arbeiten gibt es doch den CPU-lokalen Kernel-Mode-Stack, das heißt das nach wait() die CPU in gar keinem Thread-Kontext mehr läuft (das einzigste was daran noch erinnert ist der Wert in CR3 aber das ist im Kernel wurscht weil der Kernel ja in allen PDs identisch ist).

Womit ich zwar immernoch ein Problem mit wait()/resume() habe

Genau dagegen würde meine Idee mit den Events nachhaltig helfen.

Ich muss irgendwie an die EIP für die Rücksprungadresse von Sem::acquire() rankommen, weil ansonsten der Lock für die Semaphore nochmal freigegeben wird und das kann ja wieder zu Problemen führen. Also nochmal daran pfeilen.

Entweder darfst Du aus wait() nicht zwei mal raus kommen (so will ich das in meinem Kernel machen) oder Du machst das mit einem Rückgabewert wie bei fork().


Grüße
Erik

[FlashBurn]

Warum? Es gibt doch bestimmt auch viele Syscalls wo gar nicht alle Register gesichert werden müssen.

Es werden auch nur die wichtigsten Register gesichert (die, die die ABI vorschreibt), was auf alle Syscalls zutrifft.

Warum wird das nicht auch im Thread-Descriptor gesichert? Das ist doch schon wieder eine unnötige Fallunterscheidung.

Weil wir dann ja wieder unnötiges Kopieren hätten. Denn die Daten liegen ja schon auf dem Stack, von dort würde man sie dann in den Thread-Discriptor kopieren um sie dann später wieder aus dem Thread-Discriptor zurück auf den Stack kopieren würde (und somit effektiv die gleichen Daten mit den gleichen Daten überschreibt).
Zumal ich die Fallunterscheidung trotzdem bräuchte, weil die Position wo auf den CPU-lokalen-Stack kopiert wird ist immer die gleiche, bei dem KernelThread nicht. Bzw. muss ich mir bei UserThreads immmer den CPU-lokalen-Stack holen und bei KernelThreads steht der Stack-Pointer ja im Thread-Discriptor.

das wäre für mich ein wichtiger Grund auf Kernel-Threads gleich ganz zu verzichten

Geht halt nicht, bei mir läuft z.B. immer ein Thread-Killer-Thread im Hintergrund mit, der Threads (und wenn nötig ganze Tasks) komplett aus dem Speicher entfernt, was halt am einfachsten in einem extra Thread ist. Wie willst du das eigentlich lösen?

Sorry, wenn ich das wieder so deutlich raus hängen lass aber KISS ist Dir wirklich nicht sonderlich vertraut oder?

Ich kenne es, aber ob ich immer auf KISS komme, steht auf nem ganz anderem Blatt. Zumal diese Lösung noch von meinem "alten" Kernel stammt.

Das heißt das Du aus 2 Funktionsaufrufen 3 gemacht hast ohne dadurch an Funktionalität zu gewinnen?

Wieso habe ich nicht an Funktionalität gewonnen? Es ist dann so, dass der eigentliche Thread nicht mehr läuft, sondern seinen neuen Status (in dem Fall blockiert) hat und auch auf einer anderen CPU wieder laufen kann.

Genau dagegen würde meine Idee mit den Events nachhaltig helfen.

Ich sehe immer noch nicht, was deine Events von ganz normalen Semaphoren unterscheidet? Ich will diese auch genau dafür benutzen.

Entweder darfst Du aus wait() nicht zwei mal raus kommen (so will ich das in meinem Kernel machen) oder Du machst das mit einem Rückgabewert wie bei fork().

Spontan habe ich keine Idee, wie ich das mit den Rückgabewerten machen sollte. Wie willst du es denn verhindern nicht zwei mal aus wait() zurück zukommen? Ich werde das halt über die Rücksprungadresse lösen. Im Falle der KernelThreads würde die Rücksprungadresse die von Sem::acquire() sein und im Falle von UserThreads würde er sogar gleich wieder zurück in den UserMode springen (da kann ich mir ja das ganze zurück gespringe, aus dem Syscall wieder raus, sparen).

Ich bin gerade dabei, meinen kompletten Ansatz wie ich mit Threads im Scheduler umgehe, umzuschreiben. Mein neuer Scheduler (es geht da nur um den eigentlichen IRQ Handler) holt nur noch einen neuen Thread und packt einen Thread nur zurück in eine Queue, wenn der Status des Threads Running ist. Bei allen anderen Threads wird davon ausgegangen das sie schon an der richtigen Stelle sind, das wiederum wird schon im Kernel vor dem Scheduler gemacht, so dass der Scheduler wieder ein Stückchen kürzer und einfacher ist.

Dein Hinweis mit, dass ich ja schon nen CPU-lokalen-Stack habe und nicht extra nen Scheduler-lokalen-Stack brauche, werde ich nochmal überdenken. Ich brauche auf jeden Fall die Fallunterscheidung zw Kernel- und UserThreads. Problem ist einfach, das der IRQ-Handler (vom Timer) die Register ja auf dem gerade aktuellen Stack sichert und das kann einmal ein CPU-lokaler-Stack oder ein KernelThread-Stack sein. Um dann nicht noch nachgucken zu müssen (im IRQ-Stub-Code, bevor der eigentliche Scheduler aufgerufen wird) um was es sich handelt, ist es halt einfacher nen "anderen" Stack zu nehmen. Ich sollte vllt dazu sagen, dass ich dafür nicht extra nen Stack bzw. Speicher allozieren. Ich habe ja meine Idle-Threads und die brauchen nicht mal annähernd die 4kb Stack, also nutze ich die eine Hälfte für den KernelThread-Stack und die andere Hälfte ist der Scheduler-Stack (geht da ich ja für jede CPU nen Idle-Thread habe).
Wenn du dann wieder sagst, dazu habe ich ja den CPU-lokalen-Stack, dann müsste ich ja wieder ne Unterscheidung machen oder der Thread müsste seinen State selbst sichern (was auch einer Unterscheidung gleich kommt). So ist das nen ganz normaler KernelThread wo ich auf nix achten muss.

[FlashBurn]

Ich hoffe jetzt endlich ein halbwegs vernünftige Lösung gefunden zu haben.

Also das man nicht zwei mal aus wait() zurückkommt, habe ich nicht hinbekommen und wüsste auch nicht wie ich das vernünftig (ohne die komplette wait() Funktion in Assembler zu schreiben) lösen könnte.
Bleibt ja nur noch die Variante das ich das ganze, wie bei fork(), durch den Rückgabewert löse. Auch das war nicht wirklich einfach, hat ne ganze Weile gedauert bis ich festgestellt habe, dass das unter einer Hochsprache nicht wirklich (oder doch?) zu lösen ist.

Mein neuer Code sieht jetzt so aus:

Code: [Auswählen]

void
Sem::acquire()
{
    m_Lock.acquire();
   
    if(likely(Atomic::subTestNeg(&m_Count,1))) {
        Thread* t= Thread::getCurrThread();
       
        m_Threads.addTail(t);
       
        if(Scheduler::changeCurrThreadStatus(THREAD_STS_WAITING)) {
            m_Lock.release();
           
            Scheduler::reschedule();
            unreachable();
        }
    } else {
        m_Lock.release();
    }
}

void
Thread::wait()
{   
    m_Wait.acquire();
}

void
Thread::resume()
{
    m_Wait.release();
}

Thread::m_Wait ist jetzt eine Semaphore. Die Funktion Scheduler::changeCurrThreadStatus() ändert den Status des gerade laufenden Threads, im Falle von UserThreads wird mit dem Stack gar nix weiter gemacht (was auch heißt, das sobald man eine Semaphore im Kernel verwendet, danach wieder in den UserMode gesprungen wird, sprich ich darf im Kernel keine Semaphoren zur Synchronisation von Kernel-Code einsetzen) und im Falle von KernelThreads (das eigentliche Problem) wird der komplette Stack (nur das was wirklich in Benutzung ist) in den CPU-lokalen-Stack kopiert, auf diesen umgestellt und auf dem alten Stack wird ein Interrupt-Stack-Frame erstellt (damit der Scheduler ohne Probleme und Verrenkungen zurückspringen kann). Letzteres musste in einer extra, in Assembler geschriebenen, Funktion gemacht werden.

Der Grund warum ich diese in Assembler schreiben musste ist einfach, ich weiß nicht was für Code der Compiler erzeugt und wie genau der Stack aussieht. Der Code ist auch recht kurz:

Code: [Auswählen]

schedChangeToNoContextThread:
    push ebp
    mov ebp,esp
   
    mov esp,[ebp+8]
    ;create the stack frame for the scheduler
    pushfd
    push dword 0x8
    push dword .endOriginalThread
    pushad
    push ds
    push es
    push gs
       
    mov eax,esp
   
    mov esp,ebp
    pop ebp
    ret
;----------------------------
align 0x10
.endOriginalThread:
    xor eax,eax
   
    mov esp,ebp
    pop ebp
    ret
;----------------------------


[erik.vikinger]

Hallo,

Weil wir dann ja wieder unnötiges Kopieren hätten. Denn die Daten liegen ja schon auf dem Stack

Wieso kopieren? Wieso legst du die Register überhaupt auf den Stack und nicht gleich in den Thread-Descriptor? Okay, bei nem HW-Interrupt oder einer Exception muss man alle Register sichern aber dazu benötigt man ein oder zwei Register um eine Adresse laden zu können und die 2 Register müssen ersteinmal auf den Stack und von da aus dann in den Thread-Descriptor aber die 2 zusätzlichen PUSHs und POPs kosten auf einer halbwegs aktuellen CPU nicht viel (ich würde mit insgesamt 2 Takten rechnen).

Zumal ich die Fallunterscheidung trotzdem bräuchte, weil die Position wo auf den CPU-lokalen-Stack kopiert wird ist immer die gleiche, bei dem KernelThread nicht. Bzw. muss ich mir bei UserThreads immmer den CPU-lokalen-Stack holen und bei KernelThreads steht der Stack-Pointer ja im Thread-Discriptor.

Ich verstehe absolut nicht wozu hier eine Fallunterscheidung nötig ist, PUSH und POP arbeiten immer korrekt egal wo der Stack-Pointer steht.

bei mir läuft z.B. immer ein Thread-Killer-Thread im Hintergrund mit, der Threads (und wenn nötig ganze Tasks) komplett aus dem Speicher entfernt, was halt am einfachsten in einem extra Thread ist. Wie willst du das eigentlich lösen?

Also das Erstellen und Löschen von ganzen Prozessen werde ich wohl direkt beim jeweiligen Syscall (oder im Exception-Handler) machen, ansonsten hab ich fürs Defragmentieren (was auf jeden Fall nicht mehr am Stück passieren kann) noch einen DoIdle-Syscall vorgesehen der immer vom Idle-Thread aufgerufen wird und prüft ob in der Job-Queue was drin ist, falls ja wird das (teilweise) abgearbeitet und der Rückgabewert signalisiert dem Idle-Thread das er kein HLT ausführen soll (sondern per YIELD die CPU wieder abgeben soll) oder die Queue ist leer und der DoIdle-Syscall kehrt sofort zurück und der Rückgabewert signalisiert das der Idle-Thread diese Zeitscheibe lang die CPU per HLT-Befehl schlafen lassen soll.

Ich sehe immer noch nicht, was deine Events von ganz normalen Semaphoren unterscheidet? Ich will diese auch genau dafür benutzen.

Ich hatte doch schon mehrmals geschrieben das Du diesen Event-Mechanismus anstatt wait()/resume() mit Deinem Semaphor verwenden sollst. Das war aber auch noch als ich dachte das Du von einem Semaphor im User-Mode ausgehst, müsste aber innerhalb des Kernels auch funktionieren. Falls der Semaphor frei ist wird natürlich weder Dein wait() noch mein event_wait() benötigt, auch das ist unabhängig davon ob der Semaphor im Kernel oder im User-Mode liegt.

Wie willst du es denn verhindern nicht zwei mal aus wait() zurück zukommen?

In meinem event_wait() wird einfach der Zustand des Threads (die Register) im Thread-Descriptor gesichert und sein Status von RUNNING auf BLOCKED_FOR_EVENT gesetzt. Bei den Registern wird für IP (ist bei mir R63) die Adresse im User-Mode hinter dem Syscall-Befehl benutzt und an sonsten werden die Register im Thread-Descriptor so belegt als würde der Thread gerade aus dem Syscall raus kommen. Damit ist event_wait() fertig und kehrt zurück, die CPU läuft damit nicht mehr im Kontext dieses Threads. Beim event_trigger() wird dann nur noch das Register mit dem Rückgabewert im Thread-Descriptor passend gesetzt und der Status auf RUNNABLE geändert und dann der Thread in die runnable-Liste des Schedulers eingetragen (die Blockade ist damit vorbei). Der Scheduler lädt dann irgendwann diesen Thread und er kommt unmittelbar hinter dem Syscall zurück und die Register sind genau so wie sie nach diesem Syscall sein sollen.

Bei Deinen Kernel-Threads würde ich das ganz genau so machen nur das die Rücksprungadresse nicht hinter einem INT/SYSCALL/SYSENTER sondern hinter einem CALL liegt.


Das verdrehen des Stack wird wohl kaum in einer Hochsprache funktionieren, dazu musst Du zumindest Teile von wait() in Assembler implementieren, aber das sind doch nur ne gute Hand voll Zeilen (zusammen mit einem anständigen Beschreibungstext sollte das auch in vielen Jahren noch wartbar sein und dürfte nicht mehr als eine Bildschirmseite belegen).


Grüße
Erik

[FlashBurn]

Wieso kopieren? Wieso legst du die Register überhaupt auf den Stack und nicht gleich in den Thread-Descriptor? Okay, bei nem HW-Interrupt oder einer Exception muss man alle Register sichern aber dazu benötigt man ein oder zwei Register um eine Adresse laden zu können und die 2 Register müssen ersteinmal auf den Stack und von da aus dann in den Thread-Descriptor aber die 2 zusätzlichen PUSHs und POPs kosten auf einer halbwegs aktuellen CPU nicht viel (ich würde mit insgesamt 2 Takten rechnen).

Naja, ich muss erstmal an den Thread State rankommen, an den Thread-Discriptor komme ich leicht ran, aber dann muss ich ja noch einen gewissen Wert da drauf addieren um an die Adresse für den State zu kommen und das wird halt unter C++ mehr schwierig als leicht. Denn das ganze passiert ja in Assembler und da habe ich keinen Zugriff auf die Offsets von den class Membern.

Dann kommt noch hinzu, warum bei einem HW-IRQ oder einigen Exceptions die Daten in den Thread-Discriptor schreiben, ich pushe sie einfach auf den Stack und wenn der Code fertig ist, wird er wieder vom Stack gepopt (und ich brauche nicht auf den Thread-Discriptor zugreifen, was schonmal ein Cache-Miss sparen kann). Viel einfacher als wenn ich mich mit dem Kopieren rumquählen müsste. Zumal ist das Kopieren nicht langsamer als ein "pushad"?

Ich verstehe absolut nicht wozu hier eine Fallunterscheidung nötig ist, PUSH und POP arbeiten immer korrekt egal wo der Stack-Pointer steht.

Richtig, mir ging es darum wie ich die Daten dann wieder aus dem Thread-Discriptor auf den Stack bekomme und da habe ich eine Stelle wo ich den CPU-lokalen-Stack herbekomme und eine andere Stelle wo ich den KernelThread-Stack herbekomme. Also eine Unterscheidung.

Also das Erstellen und Löschen von ganzen Prozessen werde ich wohl direkt beim jeweiligen Syscall (oder im Exception-Handler) machen

Das Thema hatten wir ja schon, dass mir das zu lange dauert um die Ints dabei auszulassen. Zumal ich halt mit dem Löschen immer so meine Probleme hatte (bei nem unterbrechbaren Kernel), da man dem Thread ja nicht so einfach seinen Stack wegnehmen kann. Auch das Freigeben des PD´s ist eher schwierig oder sagen wir grob fahrlässig, während es noch in Benutzung ist.

ansonsten hab ich fürs Defragmentieren (was auf jeden Fall nicht mehr am Stück passieren kann) noch einen DoIdle-Syscall vorgesehen der immer vom Idle-Thread aufgerufen wird und prüft ob in der Job-Queue was drin ist, falls ja wird das (teilweise) abgearbeitet und der Rückgabewert signalisiert dem Idle-Thread das er kein HLT ausführen soll (sondern per YIELD die CPU wieder abgeben soll) oder die Queue ist leer und der DoIdle-Syscall kehrt sofort zurück und der Rückgabewert signalisiert das der Idle-Thread diese Zeitscheibe lang die CPU per HLT-Befehl schlafen lassen soll.

Und das nennst du KISS, ich verstehe dabei nur Bahnhof und hört sich aufwendig an. (OT: Mein Idle-Thread läuft solange bis er unterbrochen wird, wie lange das ist, weiß ich vorher gar nicht unbedingt)

Ich hatte doch schon mehrmals geschrieben das Du diesen Event-Mechanismus anstatt wait()/resume() mit Deinem Semaphor verwenden sollst.

Das habe ich schon so verstanden und mache ich ja jetzt auch. Ich wollte nur von dir wissen, wieso du genau den umgekehrten Weg einer Semaphore gehst (was den Counter betrifft). Zumal sich das bei dir so anhört als wenn du nen extra Typ event hast und das verstehe ich halt nicht, weil dein event ist nix anderes als ne Semaphore (so habe ich das jedenfalls verstanden).

Bei Deinen Kernel-Threads würde ich das ganz genau so machen nur das die Rücksprungadresse nicht hinter einem INT/SYSCALL/SYSENTER sondern hinter einem CALL liegt.

Jap und genau das war das Problem, welches in einer Hochsprache nicht zu lösen ist. Deswegen habe ich mir ja eine kleine Assembler-Funktion geschrieben die einen anderen Rückgabewert hat (0 für den eigentlichen Thread und den Pointer zum KernelThread-Stack bei dem Thread der ohne Kontext läuft).

Das verdrehen des Stack wird wohl kaum in einer Hochsprache funktionieren, dazu musst Du zumindest Teile von wait() in Assembler implementieren, aber das sind doch nur ne gute Hand voll Zeilen (zusammen mit einem anständigen Beschreibungstext sollte das auch in vielen Jahren noch wartbar sein und dürfte nicht mehr als eine Bildschirmseite belegen).

Naja, den Stack würde ich nicht innerhalb von wait() verdrehen (weiß auch nicht ob man das vernünftig hinbekommt), sondern halt in einer extra Funktion (in Assembler).

[erik.vikinger]

Hallo,

Naja, ich muss erstmal an den Thread State rankommen ....

Ja, das ist allerdings ein schwieriges Problem das Du da durch die von Dir verwendete Hochsprache bekommst. Ist es nicht möglich dieses Offset in einem C++-Modul zu ermitteln und als Wert zu exportieren so das zur Link-Zeit dieses Offset auch in den Assembler-Modulen verfügbar ist? Ich weiß nicht ob klar ist was ich meine aber ich denke das dürfte ein eleganter Weg sein Dein Problem zu lösen. Auch aus diesem Grund werde ich bei meinen Kernel wohl doch einige Teile komplett in Assembler haben. Ich habe als Programmierer damit zwar einen höheren Aufwand, insbesondere was die Verwaltung der Thread-Zustände (die bei meiner CPU etwa 90 Register umfassen) angeht, aber dafür sind viele Probleme erst gar nicht existent. Eventuell definierst du den Thread-State aber auch noch mal als dediziertes Struct (mit fest definiertem Layout) und bindest das als Member in Deine Klasse ein und speicherst Dir immer auch direkt die virtuelle Adresse dieses Structs zum aktuellen Thread ab (z.B. im local-APIC, siehe unten).

Dann kommt noch hinzu, warum bei einem HW-IRQ oder einigen Exceptions die Daten in den Thread-Discriptor schreiben, ich pushe sie einfach auf den Stack und wenn der Code fertig ist, wird er wieder vom Stack gepopt (und ich brauche nicht auf den Thread-Discriptor zugreifen, was schonmal ein Cache-Miss sparen kann).

Wenn Du sicher bist das Du nach dem HW-IRQ oder der Exception noch den selben Thread weiterlaufen lässt ist es natürlich eine minimal schnellere Alternative direkt auf den CPU-lokalen Kernel-Mode-Stack zu sichern (Du sparst dadurch das Ermitteln der richtigen Adresse aber das eigentliche Abspeichern der Register dürfte in etwa gleich schnell sein). Auf meiner CPU habe ich großen Wert darauf gelegt das die CPU das möglichst optimal unterstützt und deswegen benötige ich auch nur einen einzigen Assembler-Befehl um an die Adresse des Thread-Descriptors zu kommen (der wird vom Scheduler immer in einem extra CPU-lokalen Controll-Register abgelegt, schau doch mal bei der local-APIC-Spec ob es da nicht irgendein Register gibt das Du bei x86 für diesen Zweck missbrauchen/gebrauchen kannst, auf den jeweils lokalen APIC sollte man doch von jeder CPU aus identisch zugreifen können ohne erst ermitteln zu müssen auf welcher CPU man gerade ist) und beim Wechsel vom User-Mode in den Kernel-Mode werden bei meiner CPU auch immer 8 Register in Schattenregister gesichert so das ich sofort (zumindest ein paar) freie Register habe (das hab ich mir bei ARM abgeschaut und ist IMHO extrem nützlich).

Das Thema hatten wir ja schon, dass mir das zu lange dauert um die Ints dabei auszulassen.

Mir ist klar was Du meinst und für mein System hab ich da auch schon drüber nachgedacht solche Dinge in den Hintergrund zu verlegen (wobei gerade das Erstellen neuer Prozesse eher nicht in den Hintergrund sollte damit das möglichst zügig geht), aber ich denke darüber mach ich mir erst dann konkrete Gedanken wenn ich belastbare Performance/Latenz-Messungen habe.

Zumal ich halt mit dem Löschen immer so meine Probleme hatte (bei nem unterbrechbaren Kernel), da man dem Thread ja nicht so einfach seinen Stack wegnehmen kann. Auch das Freigeben des PD´s ist eher schwierig oder sagen wir grob fahrlässig, während es noch in Benutzung ist.

Das mit dem Stack ist doch kein Problem da Du ja eigentlich immer den CPU-lokalen Kernel-Mode-Stack nutzen solltest, auch das mit dem PD ist nicht gar so schlimm denn schließlich ist doch der Kernel in allen PDs identisch (und nur den brauchst Du doch noch um nach dem Löschen per Scheduler einen anderen Thread auf die CPU zu holen) so das Du hier jedes beliebige PD nutzen kannst (ich würde dafür das PD Deines idle-Prozesses empfehlen, oder auch von init je nach dem was bei Dir sicher immer läuft).

Und das nennst du KISS

Ja, eine Job-Queue (per Lock gesichert damit nix kaputt geht) und den Syscall-Rückgabewert davon abhängig machen ob ein Job verfügbar war (und auch abgearbeitet wurde also die Ilde-Zeitscheibe im Kernel genutzt wurde) ist doch nun wahrlich keine Rocket-Science. Und im User-Mode im idle-Prozess je nach Rückgabewert entweder HLT (Job-Queue im Kernel war leer also aktuelle Zeitscheibe verschlafen) oder YIELD (Kernel hat gearbeitet also erst mal wieder anderen Thread holen) auszuführen ist auch nicht so wild.

Mein Idle-Thread läuft solange bis er unterbrochen wird, wie lange das ist, weiß ich vorher gar nicht unbedingt

Ist bei meinem nicht anders, aber innerhalb des Kernels (im DoIdle-Syscall) kann nicht unterbrochen werden da mein Kernel ja nicht unterbrechbar ist.

wieso du genau den umgekehrten Weg einer Semaphore gehst (was den Counter betrifft)

Hä, hier verstehe ich nur Bahnhof.

Zumal sich das bei dir so anhört als wenn du nen extra Typ event hast und das verstehe ich halt nicht, weil dein event ist nix anderes als ne Semaphore (so habe ich das jedenfalls verstanden).

Diese Events sind bei meinem Kernel eine eigene Art von Service, sowas kenne ich auch von einigen anderen Embedded-OSen und finde das auch sehr praktisch. Wie Du das mit einem Semaphor vergleichen kannst verstehe ich nicht, es wird doch hierbei nichts beschützt o.ä. sondern es kann einfach eine beliebige Anzahl an Threads auf ein Ereignis warten und es wird dann immer genau ein Thread geweckt wenn ein Ereignis auftritt. Das nicht nur Threads sondern auch Ereignisse gequeued werden können liegt einfach daran das sonst eben die von Dir beschriebene Race-Condition auftreten kann, die hierbei benutzte Lösung erachte ich als sehr zuverlässig. Ich habe diesen Mechanismus (auf anderen OSen) schon oft in der Praxis benutzt und hatte damit auch nie Probleme.


Grüße
Erik

[FlashBurn]

Ist es nicht möglich dieses Offset in einem C++-Modul zu ermitteln und als Wert zu exportieren so das zur Link-Zeit dieses Offset auch in den Assembler-Modulen verfügbar ist?

Das geht wohl (ich weiß dass das andere OS auch so machen), aber ich habe keine Ahnung wie, zumal ein "pushad" wesentlich einfacher ist als ein oder 2 Register zu pushen um dann die restlichen Register und die gepushten im Thread-State zu sichern.
Fairerweise muss ich zugeben, dass ich bei den Syscalls z.B. doppelt sichere, einmal auf dem Stack und dann nochmal vom Stack in die Thread-Struct. Vorallem um das Speichern in der Thread-Struct in einer Hochsprache machen zu können.

Wenn Du sicher bist das Du nach dem HW-IRQ oder der Exception noch den selben Thread weiterlaufen lässt ist es natürlich eine minimal schnellere Alternative direkt auf den CPU-lokalen Kernel-Mode-Stack zu sichern (Du sparst dadurch das Ermitteln der richtigen Adresse aber das eigentliche Abspeichern der Register dürfte in etwa gleich schnell sein).

Sicher bin ich da nicht und du weist mich da auf ein Problem in meinem Design hin (was ich mit dem neuen Kernel noch nicht bedacht habe). Bei einem HW-IRQ wird ja ein Thread aufgeweckt oder erstellt, was zwangsläufig (da ich die Treiber-IRQ-Threads mit Realtime-Priorität laufen lassen möchte) den Scheduler auf den Plan ruft. Bei mir wird das auf einem SMP-System so gehandhabt, dass ich überprüfe ob die Priorität des neuen Threads größer der des aktuellen Threads ist (dann wird sofort der Scheduler nur auf dieser CPU aufgerufen und ich speichere den State im Moment in der Situation noch nicht ) oder nicht (dann wird eine lowest-priority IPI-Nachricht an alle CPUs - exklusive der wo der Code läuft - gesendet).
Das Empfangen der IPI-Nachricht kommt ja durch den APIC als normaler Interrupt an, was ich nochmal nachgucken muss, ob ich da dann auch nen EOI senden muss oder nicht, weil im Moment mache ich das.

Das Sichern der Register dürfte per "popad" schneller sein, ersten denke ich mal das es optimiert ist und zweitens erfordert es weniger Speicherzugriffe und es müssen wesentlich weniger Instruktionen verarbeitet werden. Das ist allerdings auf MikroKontrollern (bei ARM weiß ich es nicht) schön gelöst, da sind die Register auch nochmal im Speicher gemappt, womit man das ganze leichter bewerkstelligen kann.

der wird vom Scheduler immer in einem extra CPU-lokalen Controll-Register abgelegt, schau doch mal bei der local-APIC-Spec ob es da nicht irgendein Register gibt das Du bei x86 für diesen Zweck missbrauchen/gebrauchen kannst, auf den jeweils lokalen APIC sollte man doch von jeder CPU aus identisch zugreifen können ohne erst ermitteln zu müssen auf welcher CPU man gerade ist

Geht sogar viel einfacher (die APIC Register sollte man für sowas nicht nutzen), man kann dafür einfach nen Debugging-Register nutzen.

Das mit dem Stack ist doch kein Problem da Du ja eigentlich immer den CPU-lokalen Kernel-Mode-Stack nutzen solltest

Jetzt ja, aber auf nem unterbrechbaren Kernel hast du sowas ja nicht.

Hä, hier verstehe ich nur Bahnhof.

Du queuest in deinem Event Threads und es wird immer nur einer aufgeweckt. Fällt dir da nix auf? Das klingt für mich verdammt nach einer Semaphore. Was ich mit dem Counter meine, ist dass du fire()->release() als dekrementieren implementierst und bei einer Semaphore ist es inkrementieren. Wieso gehst du da genau den umgekehrten Weg? Hat das nen speziellen Grund?

Wenn du eine Semaphore nicht so siehst das sie zum Schützen, sondern zum Synchronisieren da ist, macht das schon Sinn nen Event mit einer Semaphore zu verlgeichen.
Deswegen nutze ich ja jetzt eine für wait()/resume() und auch mein waitForThread() nutzt eine.

[erik.vikinger]

Hallo,

zumal ein "pushad" wesentlich einfacher ist als ein oder 2 Register zu pushen um dann die restlichen Register und die gepushten im Thread-State zu sichern.

Einfacher mit Sicherheit, aber den Performance-Vorsprung von PUSHAD schätze ich minimal ein. Das teuerste dürfte sein die Adresse des Thread-Descriptors zu holen.

Fairerweise muss ich zugeben, dass ich bei den Syscalls z.B. doppelt sichere, einmal auf dem Stack und dann nochmal vom Stack in die Thread-Struct. Vorallem um das Speichern in der Thread-Struct in einer Hochsprache machen zu können.

Hm, ich bin mir gar nicht mal so sicher ob das wirklich eine schlechte/unperformante Lösung ist, das Kopieren (vom Stack zum Thread-Descriptor) ließt doch aus Speicher der mit extrem hoher Wahrscheinlichkeit noch im L1-Cache ist und das Schreiben wird beide male (beim PUSHAD wie beim MOVSD) per Write-Allocation bequem und unsichtbar im Hintergrund erledigt. Da es bei x86 ja wohl nicht ganz so einfach ist die Adresse des richtigen Thread-Descriptors schnell zu bekommen und man auch immer erst mal ein oder zwei Register aus dem Weg schaffen muss könnte die Variante mit PUSHAD im INT-Assembler-Stub und dann Kopieren im Hochsprachenteil tatsächlich sogar die Schnellste aller möglichen Lösungen auf x86 sein.

.... dann wird eine lowest-priority IPI-Nachricht an alle CPUs - exklusive der wo der Code läuft - gesendet

Also das klingt wirklich unelegant, dagegen ist doch meine Job-Queue für die Idle-Aufgaben des Kernels noch ein Kinderspiel. Generierst Du für einen IRQ wirklich X andere IRQs (IPIs)? Hast Du schon mal die IRQ-Latenz in Deinem OS gemessen?

Übrigens sind bei ARM (und den meisten anderen GP-CPUs auch) die Register nicht noch zusätzlich im Speicher gemappt, ich kenne eigentlich auch nur die 8Bit-AVRs wo es das gibt.

Geht sogar viel einfacher (die APIC Register sollte man für sowas nicht nutzen), man kann dafür einfach nen Debugging-Register nutzen.

Also ich bin schon der Meinung das der local-APIC für genau solche Dinge da ist (oder zumindest sein sollte). Das mit dem Debug-Register ist zwar ne nette Idee (kannte ich noch gar nicht) aber spätestens wenn Du mal vernünftig Debuggen willst wird Dir das Register fehlen. Ich bin mir aber sicher das man auch bei den MSRs (kommt den lokalen Controll-Registern auf meiner CPU auch am nächsten) einige Register finden wird die sich für sowas benutzen lassen und das ganz ohne das man da auf irgendeine wichtige Funktionalität verzichten muss. Spontan würden mir da z.B. die MTRRs einfallen, von den flexiblen MTRRs gibt es einige und ich denke das es recht unwahrscheinlich ist dass das BIOS wirklich alle davon benötigt (und selbst wenn doch hat es zumindest keine funktionalen Einschränkungen wenn man eines davon missbraucht sondern man beeinflusst nur die Perfomance ).

Du queuest in deinem Event Threads und es wird immer nur einer aufgeweckt. Fällt dir da nix auf?

Nö, da fällt mir nix auf! Warum auch? Wenn z.B. ein Event gleich mehrere Male kurz hintereinander getriggert wird dann werden auch kurz hintereinander mehrere Threads geweckt (falls den genügend warten).

Das klingt für mich verdammt nach einer Semaphore.

Also für mich nicht aber vielleicht hab ich auch nur ein Problem mit meinen Ohren. SCNR

Was ich mit dem Counter meine, ist dass du fire()->release() als dekrementieren implementierst und bei einer Semaphore ist es inkrementieren. Wieso gehst du da genau den umgekehrten Weg? Hat das nen speziellen Grund?

Das der Counter im positiven die wartenden Threads zählt und im negativen die gequeueten Events ist purer Zufall (würde andersherum schließlich ganz genauso funktionieren), ich werde mich schwer hüten daraus irgendeine höhere Bedeutung abzuleiten.

Wenn du eine Semaphore nicht so siehst das sie zum Schützen, sondern zum Synchronisieren da ist, macht das schon Sinn nen Event mit einer Semaphore zu verlgeichen.

Selbst zum Synchronisieren ist diese Art von Event IMHO nicht wirklich geeignet, höchstens zum Serialisieren.


Grüße
Erik