Nachrichten

81

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 02. November 2011, 17:25 »

Wenn du einen Prozess auf eine CPU festpinnst und alle anderen Prozesse von dieser CPU entfernst, dann hast du plötzlich die Möglichkeit, weiche Echtzeitanforderungen zu erfüllen.

Hmm, ich sage jetzt mal (ohne konkrete Erfahrung zu haben), das muss durch den Scheduler und einer geeigneteten Wahl der Thread-Priorität zu regeln sein.

Außerdem kann man durch das Festpinnen den Scheduler entlasten.

Meinen (einfachen/primitiven) Scheduler würde es eher noch komplexer machen und ihn nicht wirklich entlasten (was meinst du damit genau?).

Und der Thread wandert dann nicht zwischen den CPUs (und der Inhalt der Caches mit ihm).

Auch das sollte Aufgabe des Schedulers sein. Genau dieses Argument kann ich nur für Single-Threaded Anwendungen gelten lassen, weil wenn wir die Caches optimal ausnutzen wollen, dann sollten alle Threads auf der selben CPU laufen, was wieder Multithreading ad absurdum führen würde. Wimre sind die Caches beim Bulldozer pro "Dual"-Core gleich (was eins der Probleme unter Windows ist) und damit wäre das nicht so schlimm.

Zumal wir wieder sehr zum Thema Scheduling-Strategien abtriften Und ich bin immer noch nicht wirklich vom Festpinnen überzeugt. Wieviel macht denn der Cache aus und wieviel kann ein guter Scheduler retten?

82

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 02. November 2011, 17:06 »

Wenn man einen Prozess/Thread auf eine CPU festpinnen können möchte, muss man die CPU eindeutig identifizieren können. Von daher wäre das schon sinnvoll.

Das könnte man ja per Syscall lösen, aber ich stehe diesem Festpinnen eher skeptisch gegenüber. Wozu soll das gut sein, außer um Multithreading-Probleme zu beseitigen und dass ist aus meiner Sicht der falsche Weg dafür.

83

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 02. November 2011, 11:11 »

Wenn ich mich nicht täusche, hat Homix letztens erzählt, dass er auf seinem System nur jeden zweiten Index genutzt hat, weil bei seiner CPU das Hyperthreading deaktiviert ist.

Wäre bei mir auch kein Problem, da ich die ID´s selbst vergebe. Mein SMP-Startup Code serialisiert die Ausführung des Init Codes der CPUs und da wird einfach der Wert von nem Counter genommen. Von daher sollte man sich darüber keinen Kopf machen.

84

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 02. November 2011, 09:24 »

Aber CPUID liefert wimre nur eine physische CPU-Position, in der Art von Sockel/Core/Thread, und keine lineare Nummer, oder?

Weiß ich gerade auch nicht, aber braucht man die CPU-Nummer im UserSpace? Als Index für ein Array kannst du es schonmal nicht benutzen, denn die CPU könnte ja, während du den Index benutzt, gewechselt werden. Von daher wird ja z.B. beim Slab-Allocator im UserSpace die Thread-ID für sowas genommen.

Ich denke da z.B. an den CPU-lokalen Slot-Mechanismus eines SLAB-Allocators (auch im User-Mode) für den es essenziell wichtig ist möglichst performant an die CPU-Nummer zu kommen und auch das diese linear durchgezählt ist damit man eben die zugehörigen Datenstrukturen in einem simplen und schnellen Array ablegen kann.

Richtig, da war ja was Genau dafür nutze ich das ja auch.

Schon klar aber eigentlich gibt es doch nur 2 Quellen für neue Threads (die dann potentiell eine höhere Priorität haben können): einmal HW-IRQs und dann der CreateThread()-Syscall.

Es gibt noch einen 3. Grund, nämlich wenn ein Thread "aufgeweckt" wird, vom Schlafen oder vom Warten (z.B. Semaphore).

falls auf einer anderen CPU ein Thread mit einer niedrigeren Priorität läuft dann wird der Scheduler das spätestens am Ende von dessen Zeitscheibe merken

Ich weiß nicht wie lange deine Zeitscheiben so sind, aber wir reden da schon von mehreren ms und wenn du dann Audio und Video machst, könnte das schon zu dem Problem führen was ich ja unter Windows habe (knacksen im Sound und Bildstocken, auf nem QuadCore).

Das ist etwas was IMHO nur dann Sinn ergibt wenn jede CPU eine eigene runnable-Liste hat und der übergeordnete Scheduler die Last mal wieder fair über alle CPUs verteilen muss

Der Vorteil einer globalen runnable-Liste liegt für mich genau da, dass immer die Threads mit der höchsten Priorität laufen. Wenn ich das da auch nicht umsetze, kann ich ja gleich mehrere Listen (pro CPU eine) nehmen (was ich ja später auch noch vor habe).

Hm, darüber hab ich noch gar nicht wirklich nachgedacht, eigentlich bin ich der Meinung keine Rendez-Vous-Punkte zu benötigen aber das mit dem Panic erscheint mir dann doch wichtig. Beim normalen Shutdown wollte ich es eigentlich so machen das alle normalen Prozesse beendet werden und dann auch die ganzen Treiber entladen werden (wobei auch die Dateisysteme entmountet werden) und zum Schluss der init-Prozess einfach das Netzteil abschaltet, meinem OS-Kernel und der innersten Personality will ich gar nicht die Fähigkeit zum kontrollierten Abschalten geben.

Ich habe für sowas ne STOP-IPI. Damit kann man entweder alle, außer der sendenden, CPUs anhalten und kann halt z.B. nen kontrollierten Panic machen oder diese eine CPU den PC runterfahren lassen.

Wenn pro IRQ gleich mehrere Threads erstellt/geweckt werden müssen, was bei IRQ-Sharing ja leider gegeben ist, dann ergibt es natürlich Sinn diese mehreren Threads möglichst schnell auf mehrere CPUs zu verteilen aber dazu würde es doch eigentlich reichen wenn man die Restzeitscheibe der anderen CPUs auf 0 setzt so das diese direkt in den Scheduler gehen

Das halte ich ersten für Overhead (da ich durch eine Liste durchgehen muss) und zweitens, desto länger die Liste ist, desto schneller ist eine IPI-Nachricht. Dann kommt noch hinzu, dass es bei mir eher schwierig wird auf den APIC der anderen CPUs zu zugreifen (geht das überhaupt, dazu müsste man mindestens die physikalische Adresse der einzelnen APICs unterschiedlich setzen, aber ich glaube dass das trotzdem nicht geht).

85

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 01. November 2011, 20:56 »

Kann bei Dir auch der User-Space an die CPU-Nummer ran?

Jein, nicht über diese CPU-lokale-Struct, aber durch die CPUID Instruktion.

Ist die CPU-Nummer in den local-APICs wirklich linear durchgezählt (das wäre sehr nützlich um diese als Index für ein Array nutzen zu können)?

Auch wieder jein

Praktisch schon, theoretisch solltest du nicht darauf bauen. "Problem" ist, falls ein Kern defekt oder was weiß ich nicht ist, hat er trotzdem seine Nummer. Du hast ja z.B. bei ACPI eine Liste mit lokalen APICs und dort ist ja jedes Mal nen Flag ob die CPU in Ordnung ist. Praktisch fällt mir kein Szenario ein wo das mal vorkommen sollte, aber theoretisch ist es halt so.

Aber wieso willst du über ein Index in ein Array gehen, wenn du genau dafür doch sehr gut Segmente nutzen kannst?

Gar nicht. Diese Funktionalität ist auf meiner Plattform nicht vorgesehen, ich wüsste auch nicht wozu.

Also auf x86 brauchst du es für die TLBs und ich brauche es (in meiner naiven Sicht) für den Scheduler, weil ich der Meinung bin, das immer die Threads mit der höchsten Priorität laufen sollten. Also brauche ich die Möglichkeit die anderen CPUs zu benachrichtigen das es neue Threads mit höherer Priorität gibt. Etwas was ich bisher nur an einer Stelle brauche, sind Rendez-Vous Punkte und da machen sich IPI´s auch ganz gut, z.B. beim Panic um alle CPUs zu stoppen.

Für Dein OS würde mich mal der zweite Wert interessierten aber der ist dem Best-Case des ersten Wertes sehr ähnlich so das er relativ einfach zu ermitteln sein müsste.

Naja, der Handler im Kernel macht nix anderes als Nachrichten zu verschicken (und da kann man nur hoffen, das nicht zu viele Geräte den gleichen IRQ nutzen), was wiederrum ja pro Nachricht eine Thread Erstellung bedeutet und dann wird sofort auf diesen Thread gewechselt (sofern nicht ein anderer Treiber-Thread schon läuft). Wobei man natürlich noch "kurz" durch den Scheduler muss.

Interessant wäre es, ob es nicht für die Latenz gut wäre, wenn man bei mehreren Nachrichten die anderen CPUs in den Scheduler (per IPI) zwingt. Weil so würde die anderen CPUs erstmal bis zum Ende der Zeitscheibe arbeiten und dann feststellen das es neue Threads mit höherer Priorität gibt (da wären wir dann wieder bei Scheduling-Strategien).

86

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 01. November 2011, 19:00 »

Und wie kommst Du an den? Bzw. ganz generell, wie ermittelst Du die aktuelle CPU-Nummer (am besten linear von 0 bis Anzahl-1 durchnummeriert)?

Ich nutze das fs-Register für TLS und das gs-Register für die CPU-lokale-Struct, wo auch die CPU-Nummer drin steht (aber die würdest du auch durch den APIC bekommen und der ist immer an der selben Stelle gemappt).

Ich finde das extrem kompliziert, generell halte ich nicht sehr viel von IPIs, ich sehe darin keinen echten Nutzen bzw. eine extrem komplizierte Lösung für Probleme die auf einer anständig designten Plattform einfacher zu lösen wären oder erst gar nicht vorhanden wären. Mir ist klar das es bei x86 einige Dinge gibt die man ohne IPIs nur noch umständlicher gelöst bekommt, z.B. das globale TLB-Löschen auf allen CPUs, aber trotzdem empfinde ich dieses Konzept als ziemlich unelegant.

Wie löst du das denn auf deiner Architektur (andere CPUs benachrichtigen)?

Mich würde trotz allem mal interessieren was Dein OS für eine IRQ-Latenz bietet.

Mich auch

Was verstehst du denn darunter? Die Zeit vom feuern des IRQ´s bis zum Senden des EOI? Wie würde man sowas überhaupt messen?

Warum leitest Du IRQs nicht immer zu der CPU welche aktuell die SW mit der niedrigsten Priorität ausführt? Ich dachte eigentlich das es genau dafür dieses SW-Priority-Register im local-APIC gibt.

Wie soll ich es sagen ... genau das mache ich

Wenn ich so darüber nachdenke, kann die Situation das die anderen CPUs eine IPI-Nachricht bekommen müssen, im Falle von IRQs eh nie auftreten. Allerdings muss ich bei der If-Abfrage noch eine kleine Änderung vornehmen.
Wenn die Priorität des aktuellen Threads kleiner des neuen Threads ist, wird nur die aktuelle CPU in den Scheduler geschickt, ist die Priorität größer als die des neuen Threads, wird eine IPI-Nachricht versendet und wenn sie gleich ist wird gar nichts gemacht (und das ist dann für die IRQs wichtig).
Weil im Falle der IRQs kann es nur zu der Situation kommen, dass entweder der Thread der aktuellen CPU kleiner oder gleich ist, womit keine IPI-Nachricht nötig ist.

Da kommen wir aber zu einem Thema, was besser einem neuem Thread diskutiert wird, nämlich Scheduling-Strategien und sowas. Da zählt dann auch rein, wann man eine CPU im Ruhezustand lässt und wann man sie besser aufweckt. Denn es ist ja nicht immer nötig eine CPU aufzuwecken, bei einem IRQ z.B. würde ich lieber eine CPU nutzen die eh schon läuft als eine aufzuwecken.

Das Deine Vorstellung von einem Semaphor meiner Vorstellung von einem Event-Mechansimus (bei einigen Embedded/RT-OSen firmiert das auch unter dem Namen "Signal-Slot") ungefähr entspricht mag ja sein aber ich finde nicht das es deswegen das Selbe ist oder Beides gegeneinander ersetzbar/austauschbar wäre.

Was ist denn mit deinem Event möglich, was nicht mit einer Semaphore geht?

87

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 31. October 2011, 20:23 »

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.

Das Kopieren passiert so kurz danach, das die Daten auf jeden Fall noch im L1-Cache sind (selbst bei älteren CPUs). Den Thread-Discriptor zu bekommen ist nicht mal das Problem, wenn ich es genau überlege könnte ich sogar den Pointer für den Thread-State sehr einfach bekommen, indem ich den auch in meiner CPU-lokalen-Struct packe (sind es halt 4bytes mehr, aber das macht da gar nix). Auf den Stack müsste ich es aber trotzdem pushen, weil ich die gesicherten Werte später in genau den gleichen Registern wieder brauche (beim Verlassen des Syscalls zurück in den UserMode).

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?

Ich habe das Gefühl du sprichst von was anderem als ich

Was ich beschrieben habe, ist der Weg wie die anderen CPUs (bzw. eine) erfahren das es einen neuen Thread gibt, der eine potentiell höhere Priorität hat als die gerade laufenden Threads. Das hat nix mit dem Idle-Thread zu tun.

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 ).

Das ist ne ganz schlechte Idee, du weißt weder beim APIC noch bei den MSRs (da sogar noch weniger), welche Register auf welcher CPU frei sind und ob sie sich nicht mit der nächsten Generation schon geändert haben.
Ich weiß das du mehrere Debugging-Register hast und nicht unbedingt alle brauchst, von daher sollte das nicht das Problem sein, ansonsten bietet sich halt ne CPU-lokale-Struktur an (die ich über Segmente und, in meinem Fall, das gs-Register ansprechen kann).

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).

Ähm, das ist genau das was passiert wenn du mehrere Male kurz hintereinander bei einer Semaphore release() aufrufst

Also wenn du bei deinem Event event_wait() machst, wird der Thread der das macht, gequeuet, passiert bei einer Semaphore die man mit acquire() aufruft auch. Bei deinem Event wird dann von irgendwem event_trigger() aufgerufen und dieser Thread wird wieder "frei gelassen", passiert bei der Semaphore auch, wenn du release() aufrufst.

Ich sehe da immer noch keinen Unterschied.

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

Gut möglich das ich da im Moment etwas mit dem Vokabular durcheinander komme, aber ist das im Endeffekt nicht das gleiche?

88

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 31. October 2011, 16:05 »

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.

89

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 30. October 2011, 17:27 »

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).

90

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 30. October 2011, 16:04 »

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


91

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 30. October 2011, 11:46 »

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.

92

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 30. October 2011, 09:21 »

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.

93

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 21:47 »

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?

94

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 21:26 »

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).

95

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 21:01 »

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).

96

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 19:58 »

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.

97

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 19:36 »

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?

98

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 19:02 »

Dann musst Du mir noch mal genau erklären was Du eigentlich konkret vor hast.

Ziel dieses Thema´s war es eine Lösung für die weiter oben oft beschriebene Race-Condition zu finden, was ich ja auch in Form des Counters (fairerweise reicht der eigentlich nicht) habe.

Also nochmal, am Bsp. einer Semaphore im Kernel (die Ints sind aus). CPU A Thread 1 bekommt den Lock für die Semaphore dekrementiert den Counter und stellt fest das er warten muss, packt sich an das Ende der Warteliste, gibt den Lock wieder frei und ruft wait() auf.
CPU B Thread 2 bekommt den Lock genau nach CPU A, inkrementiert den Counter und stellt fest das er jemanden wecken muss, holt den ersten Thread aus der Liste (dummerweise ist das Thread 1) und macht für diesen Thread ein resume().

Jetzt mal in Code-Form:

Code: [Auswählen]

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

void
Sem::release()
{
    m_Lock.acquire();
   
    if(likely(Atomic::addTestNegZero(&m_Count,1))) {   
        Thread* t= m_Threads.removeHead();
       
        m_Lock.release();
       
        t->resume();
    } else {
        m_Lock.release();
    }
}

wait() und resume() sehen so aus:

Code: [Auswählen]

void
Thread::wait()
{
    if(likely(Atomic::subTestNeg(&m_WaitStatus,1))) {
        m_Status= THREAD_STS_WANTS_WAITING;
       
        Scheduler::reschedule();
    }
}

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

Ich gehe mal davon aus, dass Thread 1 auf jeden Fall das Dekrementieren seines m_WaitStatus vor dem resume() von Thread 2 schafft (anders rum wäre auch gar kein Problem).
Das Problem taucht da auf, wo die resume() Funktion Scheduler::addThread(this) aufruft und der Thread noch gar nicht durch den Scheduler durch ist. Das kann jetzt zu Problemen führen. Was ich so gelöst habe, dass diese Funktion den Thread nur hinzufügt, wenn er einen "vernünftigen" Status hat (wozu THREAD_WANTS_WAIT nicht dazu gehört).
Bevor mein Scheduler den Thread wirklich in den THREAD_STS_WAITING Status versetzt, überprüft er nocheinmal m_WaitStatus und ob das Warten wirklich nötig ist.

Könnte es da jetzt noch eine Race-Condition geben? Vorallem wenn man bedenkt, das wir in Richtung jeder Kern hat seine eigene Frequenz gehen und damit auch Code der eigentlich erst später erreicht werden sollte, zeitgleich mit anderem Code erreicht werden kann.

Aha, das ist jetzt aber was ganz anderes als am Anfang dieses Threads, oder hab ich da was übersehen?

Naja, es läuft alles auf obige Situation hinaus, nur um diese geht es mir im Endeffekt. Denn wenn ich das im Griff habe, ist das andere auch kein Problem mehr.

u.a. deswegen hallte ich das TimeOut-Parameter beim event_wait()-syscall für so wichtig

Wenn wir mein Race-Condition Problem geklärt haben, würde ich gerne wissen, wie man sowas vernünftig umsetzt. Ich habe da gar keine Idee, aber sowas wird ja doch ab und zu verwendet. (Gibt es bei einer Pipe unter Linux auch so nen Timeout?)

99

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 18:03 »

Da musst Du genau so oft in den Kernel wie mit Deiner Idee nur das Du das Problem mit den Race-Conditions grundsätzlich nicht bekommst.

Ich fürchte wir reden aneinander vorbei, mal wieder

Auf der einen Seite möchte ich wait()/resume() anbieten, die arbeiten mit den selben Thread-Variablen (Status-Flags und halt der Counter für die Waits) wie meine Semaphoren im Kernel (es geht ja auch bei einer Semaphore darum das ein Thread wartet, da kann diese Situation auch auftreten, wenn auch wesentlich unwahrscheinlicher).

Allgemein wollte ich halt wissen wie man damit umgeht das ein resume() vor einem wait() ankommen kann und das geht auch bei einer Semaphore im Kernel (wenn auch verdammt unwahrscheinlich bei einem nicht unterbrechbaren Kernel), vorallem bei einem der unterbrechbar ist.

Wenn das Problem gelöst ist, habe ich gleichzeitig das wait()/resume() aus dem UserSpace gelöst, da es die selben Thread-Variablen nutzt. Auch muss ich bei einer Futex (auch wenn da eine Semaphore im Kernel dahinter steckt) genau das selbe Problem lösen.

Übrigens müsstest Du mit Deiner Implementierung auch eine Liste mit den blockierten Threads pflegen damit derjenige der die Semaphore momentan hat auch weiß wen er wecken muss, und wenn Du diese Semaphore z.B. innerhalb von Shared-Memory einrichtest damit diese von mehreren Prozessen benutzt werden kann dann muss auch diese Liste komplett im Shared-Memory liegen (damit jeder eintragen/austragen kann) und dafür möchte in kein malloc bauen müssen (irgendwo her müssen ja die neuen Listen-Elemente kommen). Hast Du dafür schon eine gute Lösung?

Jetzt kommen wir zur anderen Seite. Der Counter der Futex ist im SharedMem also genau 4byte. Im Kernel wird dann ne ganz normale Semaphore benutzt, die als ID die physische Adresse des Counters der Futex hat.
Unter Linux wird das sogar so dynamisch gemacht, dass erst wenn ein Thread warten muss, eine Liste erstellt wird. Ich bin mir noch nicht sicher ob ich das auch so machen will, aber da der Thread ja höchstwahrscheinlich eh warten muss, kann man die Zeit auch vernachlässigen.

Das würde ich grundsätzlich nur innerhalb eines Prozesses erlauben. Die einzigste Ausnahme würde ich für Prozesse mit root-Rechten machen, sonst kannst Du z.B. keinen anständigen Task-Manager (sowas wie den "Process Explorer" von den Windows Sysinternals, schade das es ein Tool in der Qualität nicht für Linux gibt) programmieren. Eine komplexe Rechte-Verwaltung möchte ich auch nicht im Kernel haben, die möchte ich persönlich lieber im User-Mode haben.

Schön das wir uns da einig sind

Allerdings ist die Rechte-Sache eigentlich wieder nen eigenes Thema wert. Ich werde also fürs erste resume() nur auf Threads im selben Task zulassen. Gut das ich das transparent zu dem resume() im Kernel machen kann (indem der Syscall das überprüft und kein resume() aufgerufen wird.

Also nochmal ganz genau. Eine Futex ist nur ein Counter im UserSpace. Der Thread der den Wert des Counters ändert entscheidet auch ob er in den Kernel geht (zum Warten oder um einen anderen Thread aufzuwecken) oder nicht. Im Kernel wird nur eine Liste mit wartenden Threads verwaltet.
Wer mir jetzt mit Sicherheitsproblemen kommen möchte, die gleichen haben alle Synchonizationsprimitiven. Denn der Thread muss diese ja nicht nutzen um auf die Daten (lesend oder schreibend) zu zugreifen.
Man stelle sich nur vor ein Thread wartet auf Daten in einer Semaphore im Kernel, aber der andere Thread denkt sich, nee heute nicht und weckt den wartenden Thread halt einfach nicht auf. Dieses Problem ist mMn nicht zu lösen, solange jemand auf etwas wartet.

100

OS-Design / Re: Threads blockieren und wieder aufwecken

« am: 29. October 2011, 12:24 »

Das bedingungslose wait() ist offensichtlich nicht geeignet Dein Problem zu lösen. Warum schaust Du Dich nicht nach Alternativen um?

Es geht darum auch nen Futex zu implementieren bzw. dem User die Möglichkeit zu geben was eigenes auf basis von wait() und resume() zu entwickeln und vorallem geht es darum nicht für jede Aktion in den Kernel zu müssen.

In meiner (naiven) Welt hat ein Event (der natürlich im Kernel implementiert sein muss) ...

Sorry, schon mal schlecht Ich muss für jede Aktion in den Kernel ohne das es nötig wäre. Erfüllt leider nicht die Anforderungen. Um es nochmal zu sagen, ich habe Anforderungen und die müssen erfüllt werden.
Wenn ein Kunde ein Auto will, kannst du ihm doch nicht einfach nen Flugzeug hinstellen (du kannst schon, aber hast einen Kunden weniger ).

Wieso gehst du den unkonventionellen Weg (du machst es genau umgekehrt wie bei einer Semaphore) und nutzt nicht ne Semaphore dafür. Die gibt es schon und du musst nix neues erfinden was es schon gibt

Ansonsten bleibt nur noch zu sagen das wenn man einen Lock üblicherweise so lange benötigt das es sich für die wartenden Threads lohnt sich schlafen zu legen (was ja auch CPU-Zeit kostet) das es dann wohl meistens geschickter ist gleich eine Semaphore zu benutzen die komplett vom Kernel verwaltet wird. Für recht kurze Locks wartet man doch üblicherweise per PAUSE so das die von Dir beschriebenen Probleme eh nicht auftreten.

Ich weiß aber selbst zur Laufzeit nicht wie lange ich solch einen Lock halten werden, was also machen? Du bist doch auch nicht fürs Kopieren, aber wertvolle Zeit beim Spinnen verbraten?!

Spinlocks im UserSpace sind weder fair noch skalieren sie gut (dann kommt noch das nötige Locking des Speicherbuses dazu), sicher um nur 2 Variablen zu ändern funktioniert das, aber sobald ich entweder nicht sagen kann wie lange der Lock gehalten wird oder die Zeitspanne lange wird, ist ne Semaphore besser. Bekommt man allerdings meistens den Lock, lohnt es sich das man sich das in den Kernel Gehen sparen kann.

Ich frage, ob es einen sinnvollen Grund gibt, ein wakeup() for einem wait() zu machen. Nicht gleichzeitig, sondern irgendwann früher. Ich sehe keinen, deswegen habe ich da auch kein Problem.

Mir fällt kein Sinnvoller Grund ein, ein wakeup() vor einem wait() zu machen. Es kann aber mehr oder weniger Zeitgleich bzw ungünstig (wie schon mehrmals beschrieben) passieren und da hat man dann ne Race-Condition und das muss man ja irgendwie ausmerzen. Dazu halt der Counter und er ist halt einfacher zu implementieren wenn ich viele wakeup()´s vor einem wait() zulassen. Ansonsten müsste ich irgendwie gucken das er nie größer als 1 wird. Kann man wahrscheinlich per cmpxchg machen, bin mir gerade nicht sicher wie ich das genau machen könnte.

Die andere Frage ist dann, würde es denn Probleme geben, wenn man viele wakeup()´s vor einem wait() machen kann? Auch hat sich noch keiner dazu geäußert wie man es am besten löst das nicht jeder Thread jeden x-beliebigen Thread aufwecken kann. Alzu komplexe Rechte-Verwaltung wollte ich eigentlich nicht im Kernel haben.