Autor Thema: Nicht unterbrechbarer Kernel  (Gelesen 9877 mal)

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« am: 09. October 2011, 23:35 »
Jetzt habe ich mich gerade damit angefreundet (und angefangen entsprechenden Code zu schreiben) das ich einen nicht unterbrechbaren MikroKernel schreibe und schon fallen mir die ersten Probleme auf (Designphase mal wieder übersprungen -> erik ;)).

Also erstmal sollte man sich darüber im Klaren sein, das es auf x86 keinen 100%ig nicht unterbrechbaren Kernel gibt. Zumindest nicht wenn man nicht auf "hlt" oder andere Stromsparmechanismen verzichten möchte.

Ein anderes Problem ist mir erst jetzt bewusst geworden. Die Zeit die im Kernel verbracht wird, kann schonmal verdammt lange werden, nämlich dann wenn der User Speicher haben möchte.
Stellen wir uns einfach vor, wir sind auf einem Single-Core System (funktioniert auch auf nem Dual-Core System, wo alle CPUs gleichzeitig in den Kernel gehen und Speicher wollen, desto mehr CPUs desto unwahrscheinlicher wird es) und der User will z.B. 1GB Speicher haben.
Das Nachgucken und Besorgen eines Bereiches vom UserSpace der groß genug ist, sollte relativ schnell gehen (kann also vernachlässigt werden), aber das Besorgen der nötigen Pages ist ein Teil des Problems. Wir reden also von 1048576 4kb Pages und weil es mir um den worst-case geht, kann ich auch keine 4mb Pages nehmen. Da für jede Page der PMM aufgerufen werden muss und dieser mit einem Lock geschützt ist, rechnen wir mal so über den Daum gepeilt mit 20 Instruktionen (das ist schon wenig) pro Page, macht schonmal 20971520 Instruktionen und ich bin großzügig und rechne mal mit nur 2 Takten pro Instruktion, macht 41943040 Takte.

Jetzt gehe ich mal von 100MHz aus, ein Takt entspricht also 10ns und für obige Takte entspricht das dann 419430400ns was 419,4304ms macht und das nur um die Pages zu holen, da sind die noch nicht mal gemappt. Auch bei 1000MHz wird es nicht besser mit 41,94304ms, die dafür gebraucht werden.

Wie soll man sowas also lösen?

Ja man könnte für sowas (bzw. ist es der einzige Fall der mir einfällt, der so lange dauern könnte und natürlich der entgegengesetzte Fall, das Freigeben) Punkte einrichten, wo der Kernel dann unterbrechbar ist, aber wo würde man diese Punkte hinpacken? Weil ich will den Kernel dann z.B. nicht bei 4 Pages unterbrechen.

Ein weiteres Problem (was relativ einfach zu lösen ist) ist, dass ein Thread ja seine Zeitscheibe abgeben kann und dazu geht er per Syscall in den Kernel. Dort wird dann der Scheduler aufgerufen und der wählt einen neuen Thread aus. Problem ist hier nun, das der Scheduler immer aus dem Kernel springt, als wenn es ein IRQ wäre, aber in diesem Fall darf kein EOI gesendet werden. Das lässt sich lösen, dass man einfach jedes Mal wenn man in den Kernel springt, ein Flag setzt ob der Grund ein IRQ war oder nicht, aber das müsste man auch noch für jeden Thread speichern (wie er in den Kernel gekommen ist). Denn wenn der Thread per Syscall reingekommen ist, will man natürlich auch wieder auf dem Weg heraus (Sysret oder Sysexit).

Kleine Idee am Rande, ist es möglich, wenn ich weiß das der Thread zurück in den UserSpace geht, dass ich jedes Mal mit Sysret/Sysexit aus dem Kernel gehe (ich kann ja vorher nen EOI senden und das Page Directory wechseln, sowie andere nötige Sachen machen)? Damit könnte ich sogar ISRs ein wenig beschleunigen. Denn die sollten schneller sein als ein iret.

Auch müssen jedes Mal die Register, die beim Eintritt in den Kernel auf dem per CPU Kernel-Stack gespeichert werden, in der Thread-Struktur gespeichert werden, was auch nochmal ein paar Takte kostet.

Ein anderes Problem, welches aber auch für einen unterbrechbaren Kernel zutrifft, ist halt das Abgeben der Zeitscheibe. Denn dazu wird in den Kernel gesprungen und der Scheduler wird aufgerufen, dort (im Scheduler) müssen die Ints aus sein und genau in der Zeit kann es passieren das der Timer-IRQ feuert und dann gequeuet wird. Es wird ein neuer Thread ausgesucht und der Scheduler springt zurück in den UserSpace und was wird als erstes gemacht? Es wird wieder in den KernelSpace gesprungen, weil ja der IRQ abgearbeitet werden muss.

Kann man dagegen irgendetwas machen oder muss man damit leben? Auch das Abschalten oder maskieren hilft ja nicht, weil ja Zeit bis dahin vergeht wo ja ein IRQ auftreten kann.

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #1 am: 09. October 2011, 23:47 »
Ich sehe da kein Problem. Optimiere für den Average Case, wenn du keine harten Echtzeitbedingungen einhalten musst und mache den Worst Case entweder selten oder unattraktiv.

Mir fällt kein sinnvoller Einsatzzweck für deinen geschilderten Fall ein.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #2 am: 10. October 2011, 00:30 »
Hallo,


Designphase mal wieder übersprungen
Du kennst Deine Fehler ganz genau und machst diese trotzdem. Mal so unter uns zwei, ist das Deiner Meinung nach intelligentes verhalten? SCNR :evil:

Also erstmal sollte man sich darüber im Klaren sein, das es auf x86 keinen 100%ig nicht unterbrechbaren Kernel gibt. Zumindest nicht wenn man nicht auf "hlt" oder andere Stromsparmechanismen verzichten möchte.
Dann leg doch das HLT in den User-Mode, ach Mist, geht ja auf x86 nicht, sorry für die blöde Idee.

Wir reden also von 1048576 4kb Pages
Das sind aber schon 4 GB Speicher und nicht bloß 1 GB! :?

ich bin großzügig und rechne mal mit nur 2 Takten pro Instruktion
Das ist nicht großzügig sondern naiv, vor allem weil ja einige Speicherzugriffe dabei sind.

Wie soll man sowas also lösen?
Ich war jetzt echt versucht da Segmente vorzuschlagen aber ich weiß ja dass das hier keiner hören will.

Punkte einrichten, wo der Kernel dann unterbrechbar ist
Dann kannst du auch gleich direkt den Scheduler aufrufen. Prinzipiell eine interessante Idee aber wenn man eine zeitaufwendige Aktion ausführt dann dauert die eben etwas, dort auch noch ständig zu unterbrechen kostet unterm Strich nur noch mehr Zeit (Cache-Trashing usw.), ich persönlich halte davon nix.

Ein weiteres Problem (was relativ einfach zu lösen ist) ist, dass ein Thread ja seine Zeitscheibe abgeben kann und dazu geht er per Syscall in den Kernel....
Warum geht der Thread zum Abgeben der Zeitscheibe per Syscall in den Kernel? Der kann doch auch INT 0x?? benutzen (0x?? durch den IRQ-Vector des Timer-IRQs ersetzen). In meinem System ist es auch nicht vorgesehen das zum aktiven Abgeben der Zeitscheibe der normale Syscall benutzt wird, ich habe extra einen Befehl vorgesehen der das selbe macht wie der abgelaufene Zeitscheiben-Counter. Außerdem willst Du doch bei Multi-Core bestimmt den Local-APIC-Timer für die Zeitscheiben benutzen.

dort (im Scheduler) müssen die Ints aus sein und genau in der Zeit kann es passieren das der Timer-IRQ feuert und dann gequeuet wird. Es wird ein neuer Thread ausgesucht und der Scheduler springt zurück in den UserSpace und was wird als erstes gemacht? Es wird wieder in den KernelSpace gesprungen, weil ja der IRQ abgearbeitet werden muss.
Und dieser Zeitscheibe-Abgelaufen-IRQ (falls es den einer ist) schmeißt den frischen Thread auch gleich wieder von der CPU runter. So ein Pech aber auch. Ich fürchte damit wirst Du leben müssen oder Du baust etwas ein das der Scheduler am Ende prüft ob der Zeitscheiben-Timer gerade einen IRQ auslösen möchte und quittiert das einfach so das wenn dann die CPU die INTs wieder enabled eben kein Timer-IRQ mehr ansteht. Bei Level-Triggered-IRQs gibt es ja nichts persistentes im IRQ-Controller, bei Edge-Triggered-IRQs hast Du da schon eher ein Problem. Aber wenn Du für die Zeitscheiben den Local-APIC-Timer benutzt musst Du den am Ende des Schedulers eh frisch aufziehen und damit hat sich doch hoffentlich auch dessen IRQ erledigt.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #3 am: 10. October 2011, 10:43 »
Zitat von: svenska
Mir fällt kein sinnvoller Einsatzzweck für deinen geschilderten Fall ein.
Naja, wie erik schon richtig erkannt hatte, habe ich mich bei der Anzahl der Pages schonmal vermacht, aber das ein Programm, meinetwegen 64MB Speicher haben will und dann der PC für die gesamt Zeitspanne blockiert ist (da ja auch keine IRQs mehr angenommen werden) und das vielleicht noch von einem Task mit niedriger Priorität, kann doch schonmal vorkommen.
Und selbst bei 64MB reden wir hier von mehreren ms (schon bei meiner naiven Rechnung) und ich denke das macht sich sehr wohl für den User bemerkbar.

Zitat von: erik
Du kennst Deine Fehler ganz genau und machst diese trotzdem. Mal so unter uns zwei, ist das Deiner Meinung nach intelligentes verhalten?
Nennen wir es faules Verhalten ;)

Ich bin halt spontan und merke dann später erst was ich mir da aufgehalst habe.

Zitat von: erik
Das sind aber schon 4 GB Speicher und nicht bloß 1 GB!
Wenigstens einer der aufpasst ;) Jap, aber auch mit 1GB wird es nicht schöner.

Zitat von: erik
Das ist nicht großzügig sondern naiv, vor allem weil ja einige Speicherzugriffe dabei sind.
Ich weiß, ich wollte auch nur zeigen, dass man sich das nicht mal schön rechnen kann.

Zitat von: erik
Dann kannst du auch gleich direkt den Scheduler aufrufen. Prinzipiell eine interessante Idee aber wenn man eine zeitaufwendige Aktion ausführt dann dauert die eben etwas, dort auch noch ständig zu unterbrechen kostet unterm Strich nur noch mehr Zeit (Cache-Trashing usw.), ich persönlich halte davon nix.
Da ich gestern eh nicht richtig schlafen konnte, habe ich mir darüber nochmal ein paar Gedanken gemacht.

Meine Idee dafür ist, da ich eh Kernel-Threads haben will, brauche ich auch die Möglichkeit zw. Kernel-Threads und User-Threads zu unterscheiden (Kernel-Threads haben ihren eigenen Stack und User-Threads benutzen den per CPU Kernel-Stack) und beim Allozieren und Deallozieren lege ich ein Anzahl von Schleifendurchläufen fest (vllt 512) und wenn mehr als 512 4kb Pages benötigt werden, wird der Thread zu einem Kernel-Thread und bekommt seinen eigenen Stack. Es werden dann die 512 Schleifendurchläufe gemacht (wobei eine 4mb Page als nur ein Schleifendurchlauf zählt) und danach werden die Ints angemacht und es wird "pause" ausgeführt. Damit hat die CPU zeit, eventuell gequeuete IRQs abzuarbeiten.
Die Ints werden dann wieder ausgemacht und es werden bis zu weitere 512 durchläufe gemacht.

Das sollte Performancemäßig ein guter Kompromiss sein und ich sollte damit die meisten Speicheranforderungen ohne extra Kernel-Stack ausführen können.

Zitat von: erik
Warum geht der Thread zum Abgeben der Zeitscheibe per Syscall in den Kernel? Der kann doch auch INT 0x?? benutzen (0x?? durch den IRQ-Vector des Timer-IRQs ersetzen).
Hmm, den Fall habe ich noch gar nicht betrachtet, weil das auch nen potentieller Angriffspunkt ist. Denn ein Programm könnte dann ja munter einfach irgendwelche IRQs auslösen und das wäre ja sehr unschön.
Konnte man das nicht irgendwie begrenzen welche Ints aus dem UserSpace aufgerufen werden können?

Zumal direkt den IRQ des Timer´s aufzurufen auch unschön wäre, weil ich so nicht einfach feststellen kann, ob nun der Timer oder der User den IRQ ausgelöst haben (gut da ich eh immer den Timer-Counter auslöse kann ich das).

Zitat von: erik
Und dieser Zeitscheibe-Abgelaufen-IRQ (falls es den einer ist) schmeißt den frischen Thread auch gleich wieder von der CPU runter.
Nope, das fange ich ganz geschickt ab, entweder es ist wirklich mit einmal ein Thread verfügbar der ne höhere Priorität hat oder aber der Thread wird weiter ausgeführt da seine Zeitscheibe ja noch nicht aufgebraucht ist.

Zitat von: erik
oder Du baust etwas ein das der Scheduler am Ende prüft ob der Zeitscheiben-Timer gerade einen IRQ auslösen möchte und quittiert das einfach so das wenn dann die CPU die INTs wieder enabled eben kein Timer-IRQ mehr ansteht. Bei Level-Triggered-IRQs gibt es ja nichts persistentes im IRQ-Controller, bei Edge-Triggered-IRQs hast Du da schon eher ein Problem.
Ich wüsste nicht wie ich das so ohne weiteres feststellen sollte, ob der Timer noch nen IRQ ausgelöst hat (während ich den Counter lese und wieder neu schreibe) und ein fach per gut Glück nen EOI zu senden ist auch keine gute Idee, dann kann es ja passieren, das ich vllt den falschen IRQ "wegwerfe" (was so oder so ein Problem ist).

Was ist mit meiner Idee, dass ich mir immer merke wie ich in den Kernel gekommen bin (also ob es nen Syscall oder nen IRQ war) und dann bei nem IRQ nen EOI sende, aber immer mit der optimalen Methode aus dem Kernel gehe (also nicht iret, sondern Sysret/Sysexit)? Das sollte doch eigentlich keine Probleme geben?

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #4 am: 10. October 2011, 14:31 »
[dass] aber das ein Programm, meinetwegen 64MB Speicher haben will und dann der PC für die gesamt Zeitspanne blockiert ist (da ja auch keine IRQs mehr angenommen werden) und das vielleicht noch von einem Task mit niedriger Priorität, kann doch schonmal vorkommen.
Willst du harte Echtzeitbedingungen erfüllen oder nicht? Und wenn ja, in welcher Größenordnung?

Und selbst bei 64MB reden wir hier von mehreren ms (schon bei meiner naiven Rechnung) und ich denke das macht sich sehr wohl für den User bemerkbar.
Darum macht man ja auch Copy on Write... dann verteilt sich das Problem von "ich will jetzt aber ganz viel RAM" in eine Reihe von Pagefaults.

In Summe ist das natürlich langsamer, aber auf Latenzen hin betrachtet besser. Das ist der Kompromiss, den du finden musst. Du kannst ja auch beides machen: COW für Allokationen größer 16 MB, direktes Bereitstellen sonst.

Gruß,
Svenska

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #5 am: 10. October 2011, 15:37 »
Zitat von: svenska
Willst du harte Echtzeitbedingungen erfüllen oder nicht? Und wenn ja, in welcher Größenordnung?
Nein will ich nicht, aber es wäre mehr als nur unschön, wenn das System gerade hängt nur weil Speicher angefordert wird.

Zitat von: svenska
Darum macht man ja auch Copy on Write... dann verteilt sich das Problem von "ich will jetzt aber ganz viel RAM" in eine Reihe von Pagefaults.
Ich glaube das hatten wir schonmal und es lief darauf hinaus, dass das Programm es am besten wissen sollte und man es nicht im OS so festschreiben sollte bzw. halt normal COW und wenn das Programm besondere Wünsche hat, dann muss es das angeben.

Du kennst dich ja auch ein wenig mit Linux aus, wie war das eigentlich damals mit dem Big-Kernel-Lock, theoretisch würde man ja die Ints ausmachen, aber bei nem Monolithen geht das nicht, also konnte es passieren, dass ein Thread der den Lock hält alle andere die in den Kernel wollten blockiert oder? Dann sollte das doch am besten als Mutex implementiert gewesen sein?!
Denn dort könnte ja rein theoretisch das selbe Problem bestehen.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #6 am: 10. October 2011, 17:42 »
Hallo,


aber das ein Programm, meinetwegen 64MB Speicher haben will und dann der PC für die gesamt Zeitspanne blockiert ist (da ja auch keine IRQs mehr angenommen werden) und das vielleicht noch von einem Task mit niedriger Priorität, kann doch schonmal vorkommen.
Und selbst bei 64MB reden wir hier von mehreren ms (schon bei meiner naiven Rechnung) und ich denke das macht sich sehr wohl für den User bemerkbar.
Um ehrlich zu sein denke ich das Du dieses Problem etwas überschätzt. Klar kann der PC mal für ein paar Millisekunden "einfrieren" wenn ein Task echt mal eine große Menge Speicher am Stück anfordert aber wie oft kommt das vor? Ich behaupte mal die überwiegend meisten Speicheranforderungen die der OS-Kernel für die Applikationen durchführen muss liegen im einstelligen MByte Bereich. Ein Programm das einen wirklich großen Puffer anfordert kann dabei oft auch mit MAP-Lazy leben.

Und noch ne andere Idee: was ist wenn Deine Kernel-API gar keine größeren Speicheranforderungen mit MAP-Now akzeptiert? Das kannst Du doch als Kernel-Programmierer durchaus so festlegen und Du als libc-Programmierer baust bei größeren Speicheranforderungen etwas ein das dann immer nur einen entsprechend großen virtuellen Speicherbereich mit MAP-Lazy alloziert und wenn der User-Code trotzdem MAP-Now will dann gibt es in der libc (also noch im User-Mode) eine kleine Schleife die diesen Speicher, nachdem er mit MAP-Lazy alloziert wurde, in passenden Stückchen vom Kernel auch mit echten Pages hinterlegen lässt. Auf diese Weise kannst Du den nichtunterbrechbaren Worst-Case recht zuverlässig auf ein vertretbares Maß beschränken, einzigster Nachteil ist das Du bei richtig großen Speicheranforderungen mehrere Syscalls brauchst aber das sollte eigentlich nur sehr selten sein. Ansonsten sehe ich das so wie Svenska das bei derartig riesigen Buffern durchaus auch MAP-Lazy angebracht ist wobei eine Automatik natürlich auch immer ihre Nachteile hat.

Meine Idee dafür ist, da ich eh Kernel-Threads haben will, brauche ich auch die Möglichkeit zw. Kernel-Threads und User-Threads zu unterscheiden (Kernel-Threads haben ihren eigenen Stack und User-Threads benutzen den per CPU Kernel-Stack) und beim Allozieren und Deallozieren lege ich ein Anzahl von Schleifendurchläufen fest (vllt 512) und wenn mehr als 512 4kb Pages benötigt werden, wird der Thread zu einem Kernel-Thread und bekommt seinen eigenen Stack. Es werden dann die 512 Schleifendurchläufe gemacht (wobei eine 4mb Page als nur ein Schleifendurchlauf zählt) und danach werden die Ints angemacht und es wird "pause" ausgeführt. Damit hat die CPU zeit, eventuell gequeuete IRQs abzuarbeiten.
Die Ints werden dann wieder ausgemacht und es werden bis zu weitere 512 durchläufe gemacht.
Ich hab echt den Eindruck das Du Dir immer die maximal umständlichsten Lösungen ausdenkst. Willst Du ernsthaft die Thread-Art zur Laufzeit ändern? Ich kann nur wiederholen das Simplizität ein essentiell wichtiges Design-Paradigma ist.

den Fall habe ich noch gar nicht betrachtet, weil das auch nen potentieller Angriffspunkt ist.
Welche INTs eine User-Mode-SW alles nutzen kann kann man in der IDT individuell festlegen, von daher sehe ich da kein Sicherheitsrisiko wenn man gezielt den INT-Vector freigibt auf den der Timer-IRQ gemappt ist (solange dieser IRQ nicht geshared ist). Und das feststellen ob das ein echter IRQ oder ein SW-INT war ist ganz einfach:if ( *((short*)(thread_state.saved_ip - 2)) == ((short)0x??CD) )

Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #7 am: 10. October 2011, 18:07 »
Zitat von: erik
Um ehrlich zu sein denke ich das Du dieses Problem etwas überschätzt.
Kann gut sein, passiert mit oft.

Zitat von: erik
Klar kann der PC mal für ein paar Millisekunden "einfrieren" wenn ein Task echt mal eine große Menge Speicher am Stück anfordert aber wie oft kommt das vor?
Das hat auf nem halbwegs modernen System nicht einmal vorzukommen, egal was für ne Situation es gibt!

Zitat von: erik
Und noch ne andere Idee: was ist wenn Deine Kernel-API gar keine größeren Speicheranforderungen mit MAP-Now akzeptiert?
Ich kann jetzt nicht sagen, wie sehr die Performance einbrechen würde wenn bei z.B. einem 64mb Buffer, ab z.B. 4mb für jede Page eine Exception geworfen wird, aber das dürfte nicht zu verachten sein.
Warst du nicht eh ein Verfechter davon, dass das viel zu viel Zeit braucht und das man den Programmierer wählen lässt?

Zumal wieso ist hier die Methode, die Anwendung wie ein Baby zu behandeln gut?

Zitat von: erik
Ich hab echt den Eindruck das Du Dir immer die maximal umständlichsten Lösungen ausdenkst.
Auch das ist eine Lösung. Ich versuche halt oft nicht die Bedingungen zu ändern (bei deinem Bsp. Map-Lazy ab einer bestimmten Speichermenge), sondern den Weg.

Zitat von: erik
Willst Du ernsthaft die Thread-Art zur Laufzeit ändern?
Du stellst dir das komplexer vor als es ist. Ich würde einfach nur nen neuen Stack allozieren und den als per CPU-Stack eintragen und den aktuellen Stack in der Thread-Struktur speichern. Mehr wäre das nicht und da meine Kernel-Stacks 4kb groß sind, ist das auch nicht Zeitaufwendig.
Wenn man dann noch ein wenig Caching betreibt, dass man z.B. die Stacks danach nicht freigibt, sondern in eine Liste packt, ist nur das erste Mal "teuer".

Zitat von: erik
Ich kann nur wiederholen das Simplizität ein essentiell wichtiges Design-Paradigma ist.
Darüber lässt sich jetzt streiten. Es kommt halt drauf an was man erreichen will. Ne Liste ist immer einfacher als z.B. nen Baum und trotzdem wirst du bei den entsprechenden Fällen nen Baum wählen. Ist das dann deswegen ein schlechtes Design?

Zitat von: erik
von daher sehe ich da kein Sicherheitsrisiko wenn man gezielt den INT-Vector freigibt auf den der Timer-IRQ gemappt ist (solange dieser IRQ nicht geshared ist).
Das stimmt, dann müsste ich das nur in meiner libos einbauen, weil der Timer-IRQ ja nicht immer auf den selben Int gemappt ist (PIT und lokaler-APIC). Da muss ich nochmal genauer drüber nachdenken. Wieso haben das andere OS nicht? Soweit ich weiß ist yield() immer ein Syscall.

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #8 am: 10. October 2011, 20:20 »
Zitat von: erik
Klar kann der PC mal für ein paar Millisekunden "einfrieren" wenn ein Task echt mal eine große Menge Speicher am Stück anfordert aber wie oft kommt das vor?
Das hat auf nem halbwegs modernen System nicht einmal vorzukommen, egal was für ne Situation es gibt!
Das nennt man dann aber harte Echtzeitanforderungen... die willst du ja auch nicht.

Ich kann jetzt nicht sagen, wie sehr die Performance einbrechen würde wenn bei z.B. einem 64mb Buffer, ab z.B. 4mb für jede Page eine Exception geworfen wird, aber das dürfte nicht zu verachten sein.
Was willst du jetzt - höchsten Durchsatz oder geringste Latenz? Beides geht nicht. Definiere "Performance" und was du erreichen willst.

Warst du nicht eh ein Verfechter davon, dass das viel zu viel Zeit braucht und das man den Programmierer wählen lässt?
Du erfindest doch hier die Probleme. :-P

Zitat von: erik
Ich hab echt den Eindruck das Du Dir immer die maximal umständlichsten Lösungen ausdenkst.
Ich ebenfalls.

Ich versuche halt oft nicht die Bedingungen zu ändern (bei deinem Bsp. Map-Lazy ab einer bestimmten Speichermenge), sondern den Weg.
Äh, ...hä? Ein anderer Codepfad bei anderen Anforderungen ist für mich ein anderer "Weg".

Es kommt halt drauf an was man erreichen will. Ne Liste ist immer einfacher als z.B. nen Baum und trotzdem wirst du bei den entsprechenden Fällen nen Baum wählen.
Und am Ende des Tages möchtest du dann doch ein Array benutzen, weil es den Cache besser ausnutzt und daher im Normalfall doch schneller ist.

Ist das dann deswegen ein schlechtes Design?
Wenn du Dinge kompliziert machst, die nicht kompliziert sein müssen - ja.

Wie das Big Kernel Lock im Detail implementiert wurde, ist mir egal. Aber ja, wenn ein Thread das Lock hält, darf kein anderer Thread in den Kernel bzw. wird dort blockiert. Diese Locks kann sich eine normale Anwendung allerdings nicht holen, also auch nicht das System blockieren.

Gruß,
Svenska

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #9 am: 10. October 2011, 20:31 »
Zitat von: svenska
Das nennt man dann aber harte Echtzeitanforderungen... die willst du ja auch nicht.
Ich kenne jetzt nicht die genau Definition von harten Echtzeitanforderungen, aber so wie ich das interpretiere, haben die dann nicht alle OS? Weil es lässt sich bestimmt ne Obergenze finden, in der alle Aktionen fertig werden und das ist dann die Anforderung ;)

Zitat von: svenska
Was willst du jetzt - höchsten Durchsatz oder geringste Latenz? Beides geht nicht. Definiere "Performance" und was du erreichen willst.
Ich würde gerne einen guten Kompromiss eingehen ;)

Sprich wenn ich die Speicheranforderung unterbrechbar mache, dann kostet das im best-case unwesentlich mehr Zeit, aber der Zugriff auf den Speicher im Programm ist auf jeden Fall wesentlich schneller. Dabei muss ich dann halt den Kompromiss im Kernel eingehen.

Zitat von: svenska
Und am Ende des Tages möchtest du dann doch ein Array benutzen, weil es den Cache besser ausnutzt und daher im Normalfall doch schneller ist.
Kann durchaus passieren ;) Kommt halt auf den Fall an.

Zitat von: svenska
Diese Locks kann sich eine normale Anwendung allerdings nicht holen, also auch nicht das System blockieren.
Diese Aussage verstehe ich nicht. Jede Anwendung kann bzw. muss doch in den Kernel und kann sich damit sehr wohl den Lock holen oder was meinst du?

Edit::

Ich habe mir nochmal meine Mapping-Funktion angeguckt und mind. nochmal der selbe Aufwand kommt fürs Mapping dazu. Also ist auch COW keine Lösung weil ja die Flags gesetzt und die TLB Einträge gelöscht werden müssen. MAP_LAZY wäre auch nicht viel besser, es müssen ja auch Flags gesetzt und die TLB Einträge gelöscht werden.

Dann kommt noch hinzu, dass ein Prozess entweder seinen Speicher nicht Stück für Stück freigibt oder beendet werden muss. Das Freigeben ist auch wieder teuer und kann unter Umständen richtig lange dauern. Selbst wenn die Anwendung nicht viel Speicher angefordert haben sollte, so nutzt sie vllt viele Libs und die müssen auch alle erstmal wieder geunmappt werden und wenn da dann ein paar 100MB zusammenkommen und überprüft werden muss ob der Speicher freigegeben werden kann oder ob er zum SharedMemory (z.B. Libs) gehört, könnte es schonmal passieren dass das gesamte System für eine Sekunde oder sogar länger hängt.

Ich denke das Problem ist nicht zu unterschätzen. Denn wie erik schon sagte, meine Rechnung ist naiv.
« Letzte Änderung: 10. October 2011, 21:33 von FlashBurn »

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #10 am: 11. October 2011, 00:50 »
Hallo,

Zitat von: svenska
Das nennt man dann aber harte Echtzeitanforderungen... die willst du ja auch nicht.
Ich kenne jetzt nicht die genau Definition von harten Echtzeitanforderungen, aber so wie ich das interpretiere, haben die dann nicht alle OS? Weil es lässt sich bestimmt ne Obergenze finden, in der alle Aktionen fertig werden und das ist dann die Anforderung ;)
Nein, weil kein OS eine solche Zeit garantiert. Kannst du auch garnicht, weil z.B. jeder einzelne Festplattenzugriff sich mehrere Minuten hinziehen kann (wenn der Sektor kaputt ist und die Software versucht, da noch Daten runterzukratzen) oder das OS komplett abstürzt/panict. Harte Echtzeit gibt es daher meist nur auf Controllern mit einem RTOS drauf (und einem sehr kleinem, vollständig verstandenem System außenrum) , die dann in ein "normales" PC-gestütztes System eingekoppelt sind.

Dabei geht es um Garantien, auch im allerschlimmerschlimmsten worst case.

Sprich wenn ich die Speicheranforderung unterbrechbar mache, dann kostet das im best-case unwesentlich mehr Zeit, aber der Zugriff auf den Speicher im Programm ist auf jeden Fall wesentlich schneller.
Sprich, wenn ein malloc() nicht am Stück, sondern mit zig Kontextwechseln zwischendurch stattfinden kann, beeinträchtigt das die Performance nicht, wenn aber erst bei Benutzung alloziiert wird, dann schon? Komische Milchmädchenrechnungen machst du da...

Zitat von: svenska
Diese Locks kann sich eine normale Anwendung allerdings nicht holen, also auch nicht das System blockieren.
Diese Aussage verstehe ich nicht. Jede Anwendung kann bzw. muss doch in den Kernel und kann sich damit sehr wohl den Lock holen oder was meinst du?
Das Lock gibt es nur, während ein Syscall ausgeführt wird. Syscalls terminieren aber üblicherweise irgendwann, auch bei kaputten Eingaben, und das Lock wird auch nur genommen, wenn es notwendig ist.

Irgendwann werden wir mal Benchmarks mit deinem Betriebssystem machen und schauen, ob all deine Probleme wirklich relevant und gut gelöst sind. 8-) Ich vermute ja, dass die Probleme zwar existieren, aber real fast keine Rolle spielen - und wenn doch, dann in Spezialfällen, für die es gutes Werkzeug gibt.

Gruß,
Svenska

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #11 am: 11. October 2011, 11:17 »
Zitat von: svenska
Sprich, wenn ein malloc() nicht am Stück, sondern mit zig Kontextwechseln zwischendurch stattfinden kann, beeinträchtigt das die Performance nicht, wenn aber erst bei Benutzung alloziiert wird, dann schon? Komische Milchmädchenrechnungen machst du da...
Also, erstmal reden wir besser nicht vom malloc(), sondern von vmmAlloc() (was im Kernel stattfindet, ansonsten könnte ein falscher Eindruck entstehen) und dann wäre bei meinem altem Design (und ich gehe mal von aus, bei jedem anderen Monolithen und nicht unterbrechbaren MikroKernel auch) genau das passiert. Es hätten theoretisch zig Kontextwechsel stattfinden können, entweder weil die Zeitscheibe abgelaufen ist oder weil ein IRQ gefeuert hat. Solange getade kein Lock gehalten wurde, war mein letztes Design unterbrechbar (und ne Lock wurde immer nur sehr kurz gehalten).
Sprich schlechter ist es nicht geworden und einen Kontextwechsel pro 4kb Page ist wesentlich mehr als max. ein Kontextwechsel pro 512 4kb Pages! Also ich finde das keine Milchmädchenrechnung.

Ich habe einfach im Hinterkopf, dass ich auf meinem Desktop unter Windows ein Treiberproblem habe und da sind die Ints einfach zu lange aus und deswegen habe ich Soundprobleme (knarksen und sowas). Das scheint immer nur aufzutreten, wenn auf die HDDs zugegriffen wird und manchmal auch wenn auf ein ODD zugegriffen wird.

Genau solche Probleme möchte ich vermeiden und deswegen will ich es auf gar keinen Fall das die Ints alzu lange aus sind.

Zitat von: svenska
Irgendwann werden wir mal Benchmarks mit deinem Betriebssystem machen und schauen, ob all deine Probleme wirklich relevant und gut gelöst sind.
Sehr gerne und ich weiß schon jetzt das es besser geht, ich es nur nicht besser weiß.

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #12 am: 11. October 2011, 14:54 »
Hallo,


Das hat auf nem halbwegs modernen System nicht einmal vorzukommen, egal was für ne Situation es gibt!
Ich würde wetten das jeder von uns dieses "einfrieren" mehrmals pro Tag an seinem PC erlebt (egal ob da Windows oder Linux drauf läuft), diese Situationen sind nur normalerweise kurz genug das wir sie nicht bewusst wahrnehmen können. Schau doch einfach mal in den Linux-Kernel (der Windows-Kernel ist uns ja leider verschlossen) rein ob da die Speicherverwaltung unterbrechbar ist. Wirklich harte Echtzeitbedingungen werden, wie Svenska schon korrekt schrieb, nur in kleinen und 100% perfekt überschaubaren System erreicht, alles andere ist viel zu komplex (was auf Desktop-PCs ganz besonders zutrifft) um sowas auch nur annähernd gewährleisten zu können.

Wenn Du Dir bei der Speicherverwaltung auf Deinem 32 Bit-System, wo es nur um GBs und ein paar Hunderttausend Pages geht, schon solche Sorgen machst was denkst Du was uns auf fetten 64 Bit-System, wo es um TBs und ein paar Hundertmillionen Pages geht, erst erwartet? Eigentlich müsste bei diesem Gedanken doch jeder intelligente Mensch auf die Idee kommen das Paging als alleiniges Werkzeug zur Speicherverwaltung eine technologische Sackgasse darstellt, weil es einfach irgendwann nicht mehr benutzbar ist.

Warst du nicht eh ein Verfechter davon, dass das viel zu viel Zeit braucht und das man den Programmierer wählen lässt?
Ja, stimt, ich habe doch auch nur vorgeschlagen dieses Problem in die libOS zu verlagern indem der Kernel zu große Speicheranforderungen mit MAP-Now ablehnt. Damit hast Du in der libOS 5 bis 10 Zeilen C-Code (also eine kleine Schleife die den Mapping-Syscall in mehreren Häppchen aufruft) mehr aber dafür keine Probleme im Kernel und das Interface zum normalen User-Code (z.B. mmap) bleibt trotzdem gleich.

Wieso haben das andere OS nicht? Soweit ich weiß ist yield() immer ein Syscall.
Mein System wird yield() definitiv nicht als Syscall haben sondern als Inline-Assembler-Macro, also Bitte nicht solche Verallgemeinerungen. ;)
Das viele andere OS das per Syscall machen liegt eventuell daran das diese nicht gut designt sind, oder? Vermutlich hat die anständige Planungsphase gefehlt. ;)


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #13 am: 11. October 2011, 16:28 »
Zitat von: erik
Ich würde wetten das jeder von uns dieses "einfrieren" mehrmals pro Tag an seinem PC erlebt (egal ob da Windows oder Linux drauf läuft), diese Situationen sind nur normalerweise kurz genug das wir sie nicht bewusst wahrnehmen können.
Wenn diese Situationen kurz genug sind, dass man sie nicht wahrnimmt ist das ja in Ordnung, aber wenn der Sound schon aussetzt, dann ist das nicht mehr in Ordnung (ich rede hier von mehreren ms bis zu theoretisch Sekunden).

Zitat von: erik
Wenn Du Dir bei der Speicherverwaltung auf Deinem 32 Bit-System, wo es nur um GBs und ein paar Hunderttausend Pages geht, schon solche Sorgen machst was denkst Du was uns auf fetten 64 Bit-System, wo es um TBs und ein paar Hundertmillionen Pages geht, erst erwartet?
Wenn man mal von meiner alten Mapping-Funktion absieht (meine aktuelle Funktion braucht keinen Lock), war meine Speichervaltung unterbrechbar.

Allerdings werde ich das mit dem Mapping dann auch so lösen, dass das in mehreren Schritten passieren wird (wie beim Allozieren der Pages).

Zitat von: erik
ich habe doch auch nur vorgeschlagen dieses Problem in die libOS zu verlagern indem der Kernel zu große Speicheranforderungen mit MAP-Now ablehnt. Damit hast Du in der libOS 5 bis 10 Zeilen C-Code (also eine kleine Schleife die den Mapping-Syscall in mehreren Häppchen aufruft) mehr aber dafür keine Probleme im Kernel und das Interface zum normalen User-Code (z.B. mmap) bleibt trotzdem gleich.
Aber ob ich die Schleife nun im Kernel oder UserSpace habe ist doch erstmal egal, aber die Kontextwechsel sind verdammt teuer.

Um auch nochmal auf das MAP_NOW zurück zu kommen. Ist es nicht schon aus Effizienz-Sicht besser alles gleich zu mappen, als die teuren Exceptions das machen zu lassen?
Das wird doch nur zwecks Swapping und overcommitment gemacht (??).

Zitat von: erik
Das viele andere OS das per Syscall machen liegt eventuell daran das diese nicht gut designt sind, oder? Vermutlich hat die anständige Planungsphase gefehlt.
Kommt drauf an was alles gemacht wird und welchen Zustand der Scheduler erwartet. Bei mir ging es nur darum, dass ich den IRQ direkt im Handler hatte und daher konnte ich den nicht nochmal dafür nutzen, aber eigentlich hätte ich das auch machen können. Nur war es bei mir einfacher, weil ich so ne Funktion (vorallem für die Kernel-Threads) hatte und nicht nen Int (was im Kernel eh über ne Funktion gelöst werden muss, da ich den Int ja erst zu Laufzeit kenne).

Svenska

  • Beiträge: 1 792
    • Profil anzeigen
Gespeichert
« Antwort #14 am: 11. October 2011, 16:39 »
MAP_NOW: Der Speicher wird schneller alloziiert, steht direkt zur Verfügung und blockiert während der Alloziierung Teile des Systems.
MAP_LAZY: Der Speicher wird erst auf Anfrage alloziiert und blockiert das System nicht, dafür ist es Langsamer.
Wieder der Kompromiss zwischen Performance (MAP_NOW) und Latenz (MAP_LAZY).

MAP_LAZY erspart u.U. das Swapping und macht Overcommitment erst möglich.

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #15 am: 11. October 2011, 17:35 »
Zitat von: svenska
Wieder der Kompromiss zwischen Performance (MAP_NOW) und Latenz (MAP_LAZY).
Nur das man das mit der Latenz ja lösen kann, nur ist es halt dann nicht mehr ganz so simpel (aber nicht viel komplexer, ist ja nur ne Schleife mehr, die man eh im UserSpace dann spätestens haben müsste).

erik.vikinger

  • Beiträge: 1 277
    • Profil anzeigen
Gespeichert
« Antwort #16 am: 11. October 2011, 17:40 »
Hallo,


Wenn diese Situationen kurz genug sind, dass man sie nicht wahrnimmt ist das ja in Ordnung, aber wenn der Sound schon aussetzt, dann ist das nicht mehr in Ordnung (ich rede hier von mehreren ms bis zu theoretisch Sekunden).
In meiner (sicherlich naiven) Welt ist die Soundkarte ein busmasterfähiges Gerät das man problemlos mit Sounddaten für die nächsten 500 ms beschicken kann, ich sehe da eigentlich gar kein Problem. Auf einem typischen Desktop-PC ist es IMHO nicht so extrem ungewöhnlich das die CPU mal für ne halbe Sekunde nicht zur Verfügung steht so dass das restliche System eigentlich damit umgehen können sollte.

Aber ob ich die Schleife nun im Kernel oder UserSpace habe ist doch erstmal egal, aber die Kontextwechsel sind verdammt teuer.
Ich wollte Dir damit auch keine Alternative zu den vielen Kontextwechseln anbieten (wenn die Speicheroperation unterbrechbar sein soll dann gibt es eben teure Kontextwechsel) sondern Dir zeigen das man mit wenigen Zeilen im User-Mode ein Problem lösen kann für das man im Kernel-Mode deutlich mehr Zeilen benötigt. Einen konzeptionell nichtunterbrechbaren Kernel dann doch wieder unterbrechbar zu machen und Thread-Arten ändern (inklusive zusätzlichen Stack allozieren) usw. ist mMn ein riesiger Haufen Code der vor allem jede Menge potentielle Bugs in Deinen Kernel holt. Du kennst doch sicher das KISS-Prinzip.

da ich den Int ja erst zu Laufzeit kenne).
Das Du die INT-Nummer erst zur Laufzeit kennst ist doch gar kein Problem, zumindest für die User-Mode-Programme. Da bastelst Du ein kleines Assembler-Modul für die yield()-Funktion :.public  yield
.extern  SYSTEM_YIELD_INT_NUMBER
.align 4
yield:
    db    0xCD
    db    SYSTEM_YIELD_INT_NUMBER
    ret
Dann muss der Linker nur noch für SYSTEM_YIELD_INT_NUMBER einen Relocations-Eintrag ins Executable packen (ELF sollte sowas können) und Dein Kernel erkennt beim Laden dieses Label und reloziert die richtige Nummer rein, voilà und fertig ist Dein flexibler yield-Mechanismus.


Grüße
Erik
Reality is that which, when you stop believing in it, doesn't go away.

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #17 am: 11. October 2011, 18:18 »
Zitat von: erik
Auf einem typischen Desktop-PC ist es IMHO nicht so extrem ungewöhnlich das die CPU mal für ne halbe Sekunde nicht zur Verfügung steht so dass das restliche System eigentlich damit umgehen können sollte.
Also erstmal was ist denn für dich ein typischer Desktop-PC?

Ich erinnere mich daran, dass das Video oft am Audio synchronisiert wird und da weiß ich nicht wie das im Detail passiert und wieviel da gebuffert wird. Auch weiß ich nicht in wie weit man die Soundkarte Anweisungen mitteilen kann, hole in der und der Zeit von da und da Daten ab und spiele es dann ab (oder die Daten vorher schicken und sagen zu welchem Zeitpunkt es abgespielt werden soll).

Zitat von: erik
Ich wollte Dir damit auch keine Alternative zu den vielen Kontextwechseln anbieten (wenn die Speicheroperation unterbrechbar sein soll dann gibt es eben teure Kontextwechsel)
Wie kommt ihr eigentlich darauf, dass da immer teuere Kontextwechsel passieren. Die können passieren, müssen aber nicht. Genauso wie die innerhalb eines Monolithen passieren können (wenn man keinen Spinlock hält und die Ints an sind).

Nur habe ich so den Vorteil das ich das viele Interrupt an und ausmachen (was auf älteren CPUs nämlich verdammt teuer ist und das bei meinem alten Spinlock-Code richtig oft passiert ist) auf einmal an und wieder ausmachen alle 512 Schleifendurchläufe reduziere.

Zitat von: erik
Einen konzeptionell nichtunterbrechbaren Kernel dann doch wieder unterbrechbar zu machen und Thread-Arten ändern (inklusive zusätzlichen Stack allozieren) usw. ist mMn ein riesiger Haufen Code der vor allem jede Menge potentielle Bugs in Deinen Kernel holt.
Ich brauche eh Kernel-Threads, also sind die schonmal vorhanden und wie gesagt, das Thread-Art ändern besteht nur aus einem Pointer der entweder vorhanden ist oder nicht, mehr ist das nicht (so ist es jedenfalls geplant, ob da nicht doch noch Schwierigkeiten auftauchen weiß ich nicht).

Davon ausgehend das die Codezeilen-Anzahl bei beiden Varianten (einmal Schleife im Kernel und einmal im UserSpace) gleich sind, sind die Bugs doch eh statistisch gleich vorhanden ;) Gut einmal werden sie dann im UserSpace sein, was die Sache aber nicht besser macht, weil es trotzdem ein wichtiger Systemteil bleibt.

Zitat von: erik
Du kennst doch sicher das KISS-Prinzip.
Ja, aber ... ;)

Wie man das nun interpretiert ist so eine Sache, es liegt auch immer im Auge des Betrachters. Das hatten wir doch erst, wozu dann nen Baum nehmen, der ist nun wirklich nicht mehr KISS, sondern die Liste oder das Array.

Die ganzen technischen Sachen sind nicht mehr KISS. Wenn man mehr Effizienz will, muss man leider oft auf KISS verzichten. Denn KISS wäre bei einem OS mMn ganz eindeutig ein nicht unterbrechbarer Monolith, aber wirklich effizient und praktikabel ist das nicht.

Zitat von: erik
Das Du die INT-Nummer erst zur Laufzeit kennst ist doch gar kein Problem, zumindest für die User-Mode-Programme. Da bastelst Du ein kleines Assembler-Modul für die yield()-Funktion :
So ähnlich habe ich das schon gemacht, dass wäre nicht das Problem.

Edit::

Nicht das ich irgendwie eine schlechte Meinung vom Linux-Kernel hätte ;) aber folgendes ist nicht in Ordnung:

freier RAM: 39mb= "8619*4kB 127*8kB 59*16kB 41*32kB 15*64kB 7*128kB 0*256kB 0*512kB 0*1024kB 0*2048kB 0*4096kB = 39604kB"

Sobald man jetzt zusammenhängende >128kb braucht startet der OOM Killer. Wenn ich mich recht entsinne liegt es daran, das im Kernel nur identity gemappt wird (??). Gut das ist jetzt wahrscheinlich KISS, aber das soll gut sein? Sorry, aber dann doch lieber komplexer und nicht solche Probleme.
« Letzte Änderung: 11. October 2011, 21:09 von FlashBurn »

kevin

  • Administrator
  • Beiträge: 2 767
    • Profil anzeigen
Gespeichert
« Antwort #18 am: 11. October 2011, 21:19 »
Mein System wird yield() definitiv nicht als Syscall haben sondern als Inline-Assembler-Macro, also Bitte nicht solche Verallgemeinerungen. ;)
Ist das ein Widerspruch? Syscalls laufen doch in der Regel auch durch ein bisschen Assemblercode?

Zitat
Das viele andere OS das per Syscall machen liegt eventuell daran das diese nicht gut designt sind, oder? Vermutlich hat die anständige Planungsphase gefehlt. ;)
Was macht denn dein Assemblercode, wenn nicht in irgendeinem Sinn einen Syscall? Das einzige, was ohne Zusammenarbeit mit dem OS ginge wäre wohl irgendein Äquivalent zu hlt - aber das ist ja nicht wirklich ein yield? Oder anders gesagt: Was designst du anders und wieso ist ein Syscall falsch/nicht designt?
Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.

FlashBurn

  • Beiträge: 844
    • Profil anzeigen
Gespeichert
« Antwort #19 am: 11. October 2011, 21:30 »
Wobei mir gerade auffällt, das ein Syscall auf neueren (und auch einigen älteren) CPUs wesentlich schneller als ein "int TIMER_IRQ" ist.

 

Einloggen