Thema: Allgemeiner Ressourcen-Allocator

[Svenska]

Ich behaupte mal das jedes OS einen Syscall hast mit dem du Speicher allokieren kannst und das geht immer nur in vielfachen von PAGE_SIZE. Warum sollte sich auch der Kernel um alles was kleiner ist kümmern? Das macht dein malloc(), das wiederrum nutzt genau solch einen Syscall.

Richtig. Deswegen kann ich trotzdem ein malloc(12) machen und du musst es im Kernel auf Alignments ausrichten.

Wenn man nur ein kleines schnelles Programm oder einen eigenen Allocator schreiben will, wird man genau solch einen Syscall nutzen.

Richtig. Der Hauptnutznießer dieser API sind also Anwendungen, welche ganz genau die Interna des Systems kennen und nutzen wollen, um Performance zu schinden - und die Libraries, die ein allgemeineres Interface für Anwendungen bereitstellen. Letztere werden wahrscheinlich häufiger genutzt.

Das solltest du tun. Denn tust du es nicht, so stürzt das Programm in der nachfolgenden Anweisung ab (weil der Speicher nicht mehr vorhanden ist) und wenn du dann den Task killst, wird dein Kernel die vorhandenen Ressourcen freigeben wollen, was u.U. zu einem double-free() und damit zu einer Exception/Panic im Kernel führen kann.

Ich sags mal so, wenn das App scheiße baut und seinen eigenen Code freigibt, dann ne Exception bekommt und gekillt wird, wo ist das Problem?

Da ist kein Problem. Räumst du nicht auf, wenn ein Task endet/gekillt wird? Weil dann müsstest du alle Pages unmappen und den [physischen] RAM freigeben, der von diesem Task genutzt wurde. Das geht aber nur, wenn das Programm seinen Code eben nicht freigegeben hat (oder es abgefangen wurde).

Zu einem double-free() kann es bei mir nicht kommen. Ich hatte auch keine Lust mir ständig nen Kopf darüber zu machen wie oft ne Page gemappt ist und ob ich noch Copy-On-Write machen muss und sowas. Deswegen habe ich für jede Page (physische Adresse) nen Counter, wie oft die gemappt ist und wenn das mehr als 1 ist wird sie nicht freigegeben und wenn der Counter 1 ist dann wird sie erst freigegeben (und ist damit auch aus der PageTable raus).

Und wenn der Counter 0 ist, weil die Page schon vorher freigegeben wurde (weil das Programm sie eben selbst freigegeben hat und der Kernel das nochmal möchte)?

Das war nur ein Ansatz, ob es bei dir auftreten kann, weiß ich nicht.

Ich hab nen Mikrokernel und da sollte sich die API nun wirklich nicht ändern und wenn sie es doch tut, dann so schlimm das du das auch über Libraries nicht abfangen kannst.

Hä? Die API/ABI eines Kernels gibt an, wie Prozesse mit dem Kernel reden. Das betrifft damit auch jeden Treiberprozess.

Das sich die API von nem monolithen öfter ändert kann ich nachvollziehen. Denn der bietet ja wesentlich mehr Services an.

Auch da ändern sich nicht sämtliche APIs auf einen Schlag, sondern nur die des betreffenden Services. Die Aufgabe von Libraries ist es, Unterschiede in den Systemen wegzuabstrahieren, sodaß das Anwendungsprogramm sich nicht drum kümmern muss, auf welchem OS es läuft - wenn es das nicht will. Die Zahl der Anwendungen, die sich darum kümmern, ist gering.

3D-Spiele greifen auch nicht auf den Kernel direkt zu, sondern über Libraries wie OpenGL oder DirectX

Wir sind immernoch bei der Speicherverwaltung und da behaupte ich mal das die besseren Engines kein libc malloc() sondern ihren eigenen Allocator benutzen und dieser ruft direkt die Speicher-Funktionen vom OS auf (würde ich jedenfalls so machen, zwecks Performance).

Ich würde eher Funktionen wie memcpy() optimieren, aber davon abgesehen: Warum? Eher richte ich meine Zugriffe auf malloc() und Freunde so aus, wie das OS sie optimal verarbeitet. Schließlich soll mein App1.0 unter Kernel1.0 lauffähig sein, aber exakt das gleiche Binary auch unter Kernel2.0 ... und das geht nur, wenn ich eine Schicht dazwischen habe, die mir die Unterschiede zwischen Kernel1.0 und Kernel2.0 wegabstrahiert. Das ist üblicherweise die libc/libX11/etc.

Und die stellt auch optimierte Funktionen bereit.

Geht das bei SMP? Ints ausmachen wirkt doch nur für jede CPU...

Dazu musst du wissen das jede CPU sozusagen ihren eigenen kleinen Cache hat und deswegen reicht es wenn du die Ints ausmachst, denn in dem Moment ist die CPU ja belegt und die anderen CPUs greifen auf ihre kleinen Caches zu. Dadurch kannst du dir das Locking sparen (so fern in diesem kleinen Cache was drin ist).

Gut, das sind jetzt Details, aber trotzdem könnte eine andere CPU ja auf die gleichen Datenstrukturen zugreifen...

Also braucht dein Kernel keinen dynamisch reservierten Speicher

Doch, aber wenn du einen Syscall machst und der Kernel kann keinen Speicher mehr bekommen, dann wird halt ein Fehler zurück gegeben (vergleichbar mit malloc()= NULL).

Schon klar. Wie reagiert der Kernel aber, wenn diese Speicheranforderung essentiell wichtig war für den Fortbestand des Systems? Da sollte man durchaus Sicherheiten einbauen. In meiner Welt zumindest.

Und selbst wenn, dann geht das eben nicht.

Mein reden

Schlecht zitiert. Ein "es geht nicht" ist im Userspace akzeptabel, im Kernel hingegen nicht. Mit "Kernel" schließe ich auch explizit Hardwaretreiber mit ein. Sinn eines stabilen OSs ist, dass ein Userspaceprogramm unter keinen Umständen den Kernel gegen eine Wand fahren kann. Geht das, hast du einen DoS-Exploit.

Gruß,
Svenska

[FlashBurn]

Räumst du nicht auf, wenn ein Task endet/gekillt wird? Weil dann müsstest du alle Pages unmappen und den [physischen] RAM freigeben, der von diesem Task genutzt wurde. Das geht aber nur, wenn das Programm seinen Code eben nicht freigegeben hat (oder es abgefangen wurde).

Doch ich räume auf.

Das Problem welches du ansprichst wird bei mir von meinem Counter abgefangen. Meine vmmMap() erhöht den Counter und meine vmmUnmap() verringert den Counter.
Ist der Counter > 1 (bevor der Counter verringert wurde) dann wird die physische Adresse aus der PageTable gelöscht und kann nicht mehr freigegeben werden.
Ist der Counter = 1 (bevor der Counter verringer wurde) dann wird die physische Adresse in der PageTable stehen gelassen.
Mein Code der dann die ganzen Pages dann an den PMM weitergibt, der guckt ob der Wert in der PageTable ungleich 0 ist und gibt die Page nur dann an den PMM weiter.

Eher richte ich meine Zugriffe auf malloc() und Freunde so aus, wie das OS sie optimal verarbeitet. Schließlich soll mein App1.0 unter Kernel1.0 lauffähig sein, aber exakt das gleiche Binary auch unter Kernel2.0 ... und das geht nur, wenn ich eine Schicht dazwischen habe, die mir die Unterschiede zwischen Kernel1.0 und Kernel2.0 wegabstrahiert. Das ist üblicherweise die libc/libX11/etc.

Naja, erstmal ist das wieder auf Linux bezogen (und auch noch direkt für X11, das ist nicht wirklich portabel!), für Windows sollte das nicht zutreffen, bzw. ist es ja dort so das nicht alle Programme mit einer neueren Version laufen.
Und warum soll ich das nicht in einer eigenen Library abstrahieren. Der Punkt ist doch das du nie wissen kannst was für ein Allocator hinter malloc() steckt und wie effizient der ist und wenn du deinen eigenen schreibst kannst du alle Sachen die du schon weißt und die für die Speicherverwaltung wichtig sind, mit einfließen lassen und das geht bei malloc() halt nicht.
Aber eigentlich ist das auch egal, weil es nichts zum Thema beiträgt Wir sollten vllt mal eine Multi-Platform Engine angucken um es besser zu wissen.

Gut, das sind jetzt Details, aber trotzdem könnte eine andere CPU ja auf die gleichen Datenstrukturen zugreifen...

Nein! Jede CPU greift nur auf die Daten zu die zu ihrer CPU ID gehören und das kann ich garantieren weil ich den Code geschrieben habe. Denn wenn du jetzt argumentieren würdest dass das ja anderen Code nicht interessiert, dann gilt das gleiche für Locks. Nur weil du die benutzt müssen die andere nicht auch nutzen.

Wie reagiert der Kernel aber, wenn diese Speicheranforderung essentiell wichtig war für den Fortbestand des Systems? Da sollte man durchaus Sicherheiten einbauen.

Ich muss dir da schon recht geben, sowas wie nen Sicherheitspuffer sollte man zumindest im Kernel einbauen.
Denn bei mir ist es noch möglich eine relativ "lustige" Situation herbeizuführen. Es kann nämlich passieren das du keinen Speicher mehr freigeben kannst, weil kein Speicher mehr vorhanden ist

[erik.vikinger]

Hallo,

aber wen stört das?

Mich

Tja, pech!

Ich sollte mal erwähnen das ich mein OS dahin trimmen möchte, das es mit 4-8MB RAM lauffähig ist. Mein Fern-Ziel ist dann mit diesem RAM auch eine GUI zu haben (Win3.11 und Win95 haben das ja auch hinbekommen und laut der Meinung vieler ist Win Schrott und MS unfähig ).

Mit 4 bis 8 MB aus zu kommen ist schon ein ziemlich schwieriges Ziel. Vor allem ein hochperformanter SlabAllocator dürfte dem nicht gerade zuträglich sein weil er ja möglichst große Slabs will. Ich denke unter 32 bis 64 MB dürfte auch bei meinem OS nicht viel gehen, was vor allem am großzügigen SlabAllocator und daran das eine LDT 512 kBytes belegt liegt. Trotzdem bin ich der Meinung das, wenn mein OS bei 8GB RAM mit etlichen Programmen unter Action ist, es immer noch relativ sparsam mit RAM umgeht. Mein Designziel ist >1GB.

Ja wir reden vom selben Dokument.

Dann ist gut.

Du solltest die Blockgröße schon von der angeforderten Größe abhängig machen. Ein "new int" sollte also maximal eine 4KB-Page zurückgeben, ein "new buf[16M]" sollte 4 Pages je 4MB zurückgeben...

Für ein "new int" wird doch hoffentlich nicht eine eigene Page zurück gegeben sondern eher im Heap was passendes gesucht. Und wenn im Heap nichts mehr frei ist dann sollte die malloc-Implementierung auch nicht nur ne einzelne 4k-Page holen sondern vielleicht 128kB (oder ne ähnliche Größe) am Stück. Nur wenn malloc mehr als (sagen wir mal) 256kB am Stück zurück geben soll ist es vernünftig das direkt vom OS zu holen.

Code: [Auswählen]

.....Würde also so lange weitermachen, bis der reale Speicher bis aufs letzte Byte gefüllt ist.

Nur wenn er mit root-Rechten läuft, ansonsten bekommt er bereits vorher keinen neuen Speicher mehr (also nur noch NULL).

Was aber, wenn du übers Netzwerk swapst, dein TCP/IP-Stack aus Speichermangel größtenteils auf Platte liegt, der RAM randvoll ist und ein seltsames Paket im TCP/IP-Stack landet und verarbeitet werden muss? Du müsstest erstmal Teile deines TCP/IP-Stacks wieder in den RAM laden, wozu du Zeugs auslagern müsstest, was du nicht kannst, weil es den TCP/IP-Stack erfordert.

Erstmal finde ich ist TCP/IP ein wichtiger Treiber und sollte daher gar nicht ausgelagert werden (so fett wird der auch nicht sein das sich das lohnt) und außerdem schreibst Du da eher von komplexen Abhängigkeiten zwischen den Komponenten eines OS und die können noch ganz andere Probleme machen als nur knappen Speicher.

Naja, ich als Anwendungsprogrammierer erwarte schon von einem Flag, dass es exakt das tut, was ich möchte und nichts anderes.

Also ich erwarte das Flags genau das bewirkten was dokumentiert ist und nicht das was ich da gerne hinein interpretieren möchte. Wenn in der Doku steht das dieses Flag dazu dient dem OS zu sagen was ich machen will damit sich das OS möglichst optimal verhalten kann, falls es das auch wirklich kann, dann ist das Okay für mich. Es gibt ne Menge derartiger kann-Flags die eben dem OS sagen was für das Programm optimal wäre aber das OS nicht zu einem bestimmten Verhalten verpflichten. Solange das OS mir den Speicher, den ich in meinem virtuellen Adressraum haben will, auch wirklich zusichern kann sollte der malloc-Syscall auch erstmal funktionieren. Ob die Pages alle sofort oder erst später eingeblendet werden macht ja funktional keinen Unterschied sondern beeinflusst nur die Performance.

Daher würde ich eine Automatik machen (MAP_NOW wenn <16M, MAP_LAZY wenn größer). Ich bin der Meinung, dass kleine Blöcke sofort benutzt werden und große Blöcke nicht/teilweise.

Wenn wenn der Programmierer vom nächsten Programm Deine Meinung nicht kennt? Solche Automatismen haben immer den Nachteil das sie eben nie wirklich wissen was los ist sondern nur vermuten können und Vermutungen sind auch mal falsch (liegt in der Natur der Sache). Also da bevorzuge ich ein Flag das nur ne Empfehlung ist als das ich einen Automatismus haben möchte der von irgend welchen wagen Annahmen und Meinungen abhängt.

Niemals so, dass ich ein Flag explizit angebe und es dann ignoriert wird.

Du bist also der Meinung "lieber einen Syscall der nichts macht obwohl er eigentlich könnte wenn auch nicht ganz optimal als einen Syscall der versucht sich so gut wie möglich zu verhalten aber das nicht zusichert"? Diese Einstellung kann ich nicht nachvollziehen.

Sehe ich etwas anders, denn die Größe der "letzten Reserven" hängt von root ab. Wenn er nur "bash", "ps" und "kill" nutzen möchte, mag das sein - aber eventuell möchte er erstmal seine X11-Umgebung mit KDE starten, um darin nachzuschauen, was überhaupt kaputt ist...

Dann macht man die Größe der letzten Reserve eben konfigurierbar, entscheidend (für die Stabilität des OS) ist das es überhaupt eine gibt.
Ein root der bei Speicherknappheit erst mal KDE starten will ist IMHO auch selber schuld wenn das System mit Rums gegen die Wand fährt.

Daher bin ich der Meinung, dass - sofern im Kernel kein Speicher mehr da ist - der Prozess mit dem größten Speicherverbrauch gekillt werden sollte.

Also spätestens wenn Du mal nen halben Arbeitstag auf das Ende einer Simulation wartest und dann kurz vor Schluss das Simulationsprogramm noch mal etwas Speicher braucht und dann, nur weil es am meisten Speicher braucht, vom OS gekillt wird entwickelst Du eine andere Meinung. Das ModelSim kann wimre mit NULL von malloc so umgehen das es fragt ob es noch mal malloc versuchen soll oder ob es die Simulation abbrechen soll (und man wenigstens den bereits fertigen Teil der Simulationsergebnisse noch verwenden kann). In der Zeit wo das Fragefenster wartet kann man auch schnell noch ein paar andere Programme schließen und danach erst mal auf den "nochmal"-Knopf drücken. Ein OS das einfach nach belieben irgendwelche Prozesse killt möchte ich nicht haben, lieber soll es keinen unprivilegierten Programmen neuen Speicher geben so das diese Programme die Möglichkeit haben angemessen zu reagieren.

Allerdings ist ein Programm, welches so viel RAM für sich in Anspruch nimmt, dass es das System nahezu lahmlegt für den Rechner dann ohnehin ungeeignet und man sollte das Programm anpassen oder RAM nachstecken.

Das ist ja prinzipiell richtig aber sollte ich als User nicht auch die Möglichkeit haben erst mal andere Programme weg zu räumen bevor das eine Programm, das meinen Rechner bis zum Anschlag auslastet, gekillt wird und diesem Programm die Gelegenheit geben doch noch fertig zu werden?

Ein System, was konstant am Anschlag lebt, sollte man überdenken.

Das ist immer eine Frage der Rahmenbedingungen. Ich als Privatperson werde mir nicht einen neuen Rechner kaufen nur weil ich einmal im Monat ein Programm benutze das meinen Rechner bis an die Grenze bringt. Solange es doch noch irgendwie geht möchte ich diese Geldausgabe lieber vermeiden. Erst wenn das Programm dann doch die Grenze überschreitet so das ich keine Chance habe das durchlaufen zu lassen bin ich wirklich gezwungen einen neuen Rechner zu kaufen, ich erwarte von meinem OS das es mir ermöglicht es wenigstens zu versuchen ob das Programm irgendwie zum Abschluss kommt.

Wenn du allgemeine Treiber nutzt, ist das nicht möglich; deren Speicheranforderung kann sich stark unterscheiden, je nach Auslastung.

Durch was schwankt der Speicherverbrauch eines Treibers so stark? Wenn ich jetzt mal an einen SATA-AHCI-Treiber denke dann bekommt der maximal wie viele Jobs gleichzeitig? Sagen wir mal 100 und nehmen für jeden Job mal 4 kB zur internen Verwaltung (ist das zu wenig?) dann schwankt der RAM-Bedarf dieses Treiber um maximal 400kB. Wo ist da das Problem? Das sollte die malloc-Implementierung doch recht gut abfangen können so das der Treiber normalerweise gar keine Speicheranforderungen an den Kernel schickt.

Außerdem willst du wirklich 25% des RAMs für root reservieren? Das stelle ich mir grad in einem Rechenzentrum mit 64 GB RAM/Node vor...

Die 25% waren doch nur mal so dahingeschrieben, es wäre natürlich besser wenn man das konfigurieren kann so das root eben klar festlegen kann was er im Notfall als Reserve wirklich braucht (zuzüglich einen gewissen Überhang fürs OS).

Ich glaube Du hast nicht ganz verstanden was ich eigentlich ausdrücken wollte. Es geht mir nicht um Datenbanken o.ä. sondern um ein Szenario in dem ein Programm einen großen Bereich an virtuellem Speicher benötigt und diesen auch mit echten Daten befüllt aber dann zur weiteren Laufzeit nur einen kleinen Anteil davon tatsächlich benutzt, das bedeutet das von diesem Bereich durchaus ein hoher Anteil an Pages ausgelagert sein können ohne dass das negative Konsequenzen (für die Performance) hat. Das selbe trifft auch auf übliche Code-Bereiche zu, kaum ein Programm wird ständig all seinen Programm-Code ausführen.

Ich hab das schon so verstanden.

Sicher? Diesen Eindruck habe ich irgendwie nicht.

Ursprünglich ging es aber um die Verwaltung des virtuellen Speichers - jeder dort vorhandene Block wird (in meiner Welt) durch mehrere Pages ausgedrückt, d.h. die Verwaltung, welche Pages nun wirklich im RAM sind, liegt anderswo. Und wenn deine Rechtschreibprüfung jedes Wort in eine eigene Page (mit eigenem malloc) stopfen will, dann wird die Anwendung halt langsam. Der aktuelle Auslagerungszustand ist davon unabhängig und ich muss Blöcke auch nicht unbedingt vollständig ausgelagert haben.

Was hat das alles mit vollständig belegten aber nur dünn benutzen virtuellem Speicher zu tun? Wieso sollte ich für eine Rechtschreibprüfung jedes Wort in eine eigene Page legen?

Wenn man nur ein kleines schnelles Programm oder einen eigenen Allocator schreiben will, wird man genau solch einen Syscall nutzen.

Dann muss man sicher aber auch mit der exakten Funktionsweise des OS beschäftigen und sollte auch nicht jeden Speicherbedarf in 4kB-Häppchen decken sondern sich überlegen wie das Programm den Speicher benutzen möchte und in entsprechender Größe die Blöcke holen. Da fällt mir ein: willst Du bei Deinem Speicher-Mapping-Syscal für den virtuellen Speicher vorgeben können wo hin der Kernel die neuen Pages in den virtuellen Adressraum des Prozesses legen soll? Wenn ja dann lohnt es sich eventuell schon den virtuellen Speicher, der von der malloc-Implementierung für den Heap benutzt wird, in sehr kleinen aber zusammenhängenden Schritten zu vergrößern.

Ich hab nen Mikrokernel und da sollte sich die API nun wirklich nicht ändern

Warum nicht? Kann es nicht mal sein das Du zu einem bereits bestehenden Syscall noch ein Parameter hinzufügen möchtest?

und wenn sie es doch tut, dann so schlimm das du das auch über Libraries nicht abfangen kannst.

Trifft das auch auf Programme zu die nur von der libc (kein POSIX oder sonstwas) abhängig sind?
Es ist ja gerade die Aufgabe von Librarys sowas abzufangen und das funktioniert oft sogar über viele OSe hinweg, also warum soll das nicht zwischen verschiedenen Versionen eines OS funktionieren?

Wir sind immernoch bei der Speicherverwaltung und da behaupte ich mal das die besseren Engines kein libc malloc() sondern ihren eigenen Allocator benutzen und dieser ruft direkt die Speicher-Funktionen vom OS auf (würde ich jedenfalls so machen, zwecks Performance).

Die Hersteller der besseren Engines kaufen sich eine ordentlich hochperformante malloc-Implementierung (und bleiben in ihrem Code bei malloc).

das wenn kein Lock benutzt wird, eine Semaphore benutzt wird, aber die lohnt sich halt erst, wenn der kritische Bereich wirklich lange dauert (meine Meinung und ich weiß das erik das anders sieht).

Dann musst Du erst mal genau erklären was für Dich der Unterschied zwischen einem Lock und einer Semaphore ist. In meinem Kernel wird es nur simple Locks und eventuell Reader/Writer-Locks (obwohl mir da jetzt im Moment gar kein Anwendungsfall für einfällt) geben.


Grüße
Erik

[FlashBurn]

Mit 4 bis 8 MB aus zu kommen ist schon ein ziemlich schwieriges Ziel.

Bisher nicht Auch sollte der Speicher für ein Text-Mode OS reichen (was die meisten Hobby OSs ja sind).

Die bei MS müssen das ja auch irgendwie geschafft haben, dann schaffe ich das auch irgendwann

Vor allem ein hochperformanter SlabAllocator dürfte dem nicht gerade zuträglich sein weil er ja möglichst große Slabs will.

Wie kommst du darauf? Ich habe den SlabAllocator so verstanden und implementiert, das er versucht möglichst wenig Verschnitt zu haben und das mind. 8 Objekte in einem Slab drin sind bzw. sind mind. 8 Objekte in einem Slab wird der Slab nicht weiter vergrößert.

Und wenn im Heap nichts mehr frei ist dann sollte die malloc-Implementierung auch nicht nur ne einzelne 4k-Page holen sondern vielleicht 128kB (oder ne ähnliche Größe) am Stück. Nur wenn malloc mehr als (sagen wir mal) 256kB am Stück zurück geben soll ist es vernünftig das direkt vom OS zu holen.

Das ist genau der Punkt wo ich am meisten von "normalen" OSs abweiche. Denn was bitte ist ein Heap oder besser was ist an dem anders, als wenn du das OS nach Speicher fragst?

Bei mir gibt es den klassischen Heap nicht, sondern du fragst immer beim OS nach Speicher und bekommst nen Pointer zurück.

Da fällt mir ein: willst Du bei Deinem Speicher-Mapping-Syscal für den virtuellen Speicher vorgeben können wo hin der Kernel die neuen Pages in den virtuellen Adressraum des Prozesses legen soll?

Theoretisch möglich wäre es (habe eigentlich schon vor, noch ne Funktion mapAllocAt(uint32t start, uint32t size) zu schreiben), aber ich sehe noch keinen Bedarf dafür.

Kannst du mir denn ein paar (ok, es reicht auch einer) Gründe nennen (die ich nachvollziehen kann bzw. einsehe) warum man sowas unbedingt braucht?

Warum nicht? Kann es nicht mal sein das Du zu einem bereits bestehenden Syscall noch ein Parameter hinzufügen möchtest?

Ich wüsste halt im Moment nicht was sich bei den paar Syscalls ändern sollte, bzw. bis ich soweit bin, das ich wirkliche Anwendungen auf meinem OS laufen habe, sollte die API stabil sein.

Trifft das auch auf Programme zu die nur von der libc (kein POSIX oder sonstwas) abhängig sind?

Warum sollte das da nicht zutreffen. Nehmen wir mal an du hast nen Syscall da irgendetwas macht und du änderst hin dahingehend, das noch ein size-Parameter dazu kommt und den kannst du auch in der Library nicht rausbekommen, sondern den Wert weiß nur der User, wie willst du das wegabstrahieren?

Die Hersteller der besseren Engines kaufen sich eine ordentlich hochperformante malloc-Implementierung (und bleiben in ihrem Code bei malloc).

Also ich persönlich würde ja sowas wie nen SlabAllocator oder wenn es wirklich was bringt für bestimmte Objekte sogar nen eigenen Allocator benutzen.

Dann musst Du erst mal genau erklären was für Dich der Unterschied zwischen einem Lock und einer Semaphore ist. In meinem Kernel wird es nur simple Locks und eventuell Reader/Writer-Locks (obwohl mir da jetzt im Moment gar kein Anwendungsfall für einfällt) geben.

Ich muss dringend an meinem Ausdruck arbeiten

Mit Lock ist ne Spinlock oder halt ne Read-Write-Lock (was im Endeffekt auch ne Spinlock ist) gemeint, wo du busy-waiting machst und ne Semaphore wirst du als Thread schlafen gelegt und irgendwann wieder aufgeweckt.
Ich habe bisher auch noch keine Semaphore bei mir verwendet und denke auch nicht das ich eine brauchen werde, aber man kann ja nie wissen

[erik.vikinger]

Hallo,

Mit 4 bis 8 MB aus zu kommen ist schon ein ziemlich schwieriges Ziel.

Bisher nicht

Dann viel Glück dabei. Ließ mal ab hier.

Die bei MS müssen das ja auch irgendwie geschafft haben, dann schaffe ich das auch irgendwann

Win95 lief deswegen noch mit 4 MB weil es zu großen Teilen noch auf 16Bit-Code basierte und der (und auch dessen Daten) ist kleiner. Bei Win98 war wimre 8 MB das absolute Minimum um überhaupt den Desktop zu sehen von arbeiten kann man da noch nicht reden. Ich bin ehrlich der Meinung wenn Dein OS mindestens 32 MB will dann geht das völlig in Ordnung. Unter nem Pentium machts doch Dein OS auch nicht.

Wie kommst du darauf? Ich habe den SlabAllocator so verstanden und implementiert, das er versucht möglichst wenig Verschnitt zu haben und das mind. 8 Objekte in einem Slab drin sind bzw. sind mind. 8 Objekte in einem Slab wird der Slab nicht weiter vergrößert.

Also ich hab das SlabAllocator-Konzept eher so verstanden das man sich bemüht möglichst große Slabs zu benutzen um eben möglichst selten die normale page-basierte Speicherverwaltung zu belästigen. Ich möchte für meinem Kernel-Heap die Slabs 512 kBytes groß machen. Schau Dir noch mal dieses Magazin-Zeugs an und überlege wie viele Objekte Du schon allein brauchst um genügend Magazine (wo jedes ja wohl mindestens 8 Objekte aufnimmt) für 8 CPUs zu befüllen. Variable Magazin-Größe möchte ich nicht umsetzen, das ist mir zu viel Aufwand, ich denke eine feste Größe von 16 Objekten pro Magazin ist eine recht gute Basis.

Das ist genau der Punkt wo ich am meisten von "normalen" OSs abweiche. Denn was bitte ist ein Heap oder besser was ist an dem anders, als wenn du das OS nach Speicher fragst?

Der Heap ist dafür da Objekte mit beliebiger Größe möglichst optimal zu verwalten. Der, mit Pages arbeitende, VMM des OS-Kernels kann das nicht.

Bei mir gibt es den klassischen Heap nicht, sondern du fragst immer beim OS nach Speicher und bekommst nen Pointer zurück.

Wirklich? Bedeutet das wenn ich "new int" mache das ich dann ein komplette Page nur für die 4 Bytes bekomme (und 4092 Byte verschwende)? Was ist wenn ich extrem oft "new int" (oder für andere recht kleine Objekte) mache? Dann entsteht doch ein unheimlicher Verschnitt.

willst Du bei Deinem Speicher-Mapping-Syscal für den virtuellen Speicher vorgeben können wo hin der Kernel die neuen Pages in den virtuellen Adressraum des Prozesses legen soll?

Theoretisch möglich wäre es (habe eigentlich schon vor, noch ne Funktion mapAllocAt(uint32t start, uint32t size) zu schreiben), aber ich sehe noch keinen Bedarf dafür.

Kannst du mir denn ein paar (ok, es reicht auch einer) Gründe nennen (die ich nachvollziehen kann bzw. einsehe) warum man sowas unbedingt braucht?

Also wirklich brauchen tut man das IMHO nicht aber es macht die malloc-Implementierung leichter wenn man den Bereich im virtuellen Adressraum, der für den Heap benutzt wird, einfach so vergrößern kann und der Heap sich nicht über mehrere zusammenhanglose Stücken im virtuellen Adressraum verteilt. Im Prinzip habe ich das mit meinen Segmenten ja auch (nur das ich 32k solcher virtuellen Adressräume hab), ich kann jedes Segment beliebig vergrößern und auch verkleinern. Der Vorteil bei Deinem Flat-Memory-System ist das Du auch mitten aus diesem Bereich kleine Stücken wieder rauswerfen kannst, wogegen ich meine Segmente nur vorne und hinten beschneiden kann.

Ich wüsste halt im Moment nicht was sich bei den paar Syscalls ändern sollte

Das weiß man nie vorher. Aber ich bin mir sicher das auch Dein Kernel nicht von Anfang an perfekt ist, so wie jeder andere auch.

bzw. bis ich soweit bin, das ich wirkliche Anwendungen auf meinem OS laufen habe, sollte die API stabil sein.

Gerade erst dann wenn Du wirklich anfängst die ersten richtigen Programme laufen zu lassen merkst Du was alles noch nicht so ist wie es die Praxis gerne hätte und dann kommen die Änderungswünsche schneller als Die lieb ist. Meißle Deine Syscall-API lieber noch nicht in Stein, das hat mindestens Zeit bis die ersten größeren Programme ordentlich laufen, mach Dir lieber ein gutes Konzept wie Du die Syscall-API später mal bequem ändern kannst ohne das Du an irgend einer Stelle vergisst was anzupassen.

Trifft das auch auf Programme zu die nur von der libc (kein POSIX oder sonstwas) abhängig sind?

Warum sollte das da nicht zutreffen. Nehmen wir mal an du hast nen Syscall da irgendetwas macht und du änderst hin dahingehend, das noch ein size-Parameter dazu kommt und den kannst du auch in der Library nicht rausbekommen, sondern den Wert weiß nur der User, wie willst du das wegabstrahieren?

Sowas gibt es in der Standard-libc nicht. Alle Dienste die die libc laut C-Standard anbietet muss auch Deine libc-Implementierung können egal wie die Syscalls aussehen. Auf allen anderen OSen funktioniert das auch (die libc hat nach oben hin immer die selbe API), warum sollte das auf Deinem OS anders sein?

Die Hersteller der besseren Engines kaufen sich eine ordentlich hochperformante malloc-Implementierung (und bleiben in ihrem Code bei malloc).

Also ich persönlich würde ja sowas wie nen SlabAllocator oder wenn es wirklich was bringt für bestimmte Objekte sogar nen eigenen Allocator benutzen.

Dann schau Dir doch mal an wie die kommerziellen Heap-Librarys so arbeiten, da steckt oft ein optimierter SlabAllocator drin. Übrigens sind diese Librarys nicht portabel (was manchmal schon an verschiedenen Windows-Versionen scheitert) sondern der Hersteller verkauft Dir für jedes OS (unde jede Version davon) eine extra angepasste Library-Version (damit eben bei jedem OS die spezifischen Gegebenheiten optimal ausgereizt werden können).

Mit Lock ist ne Spinlock oder halt ne Read-Write-Lock (was im Endeffekt auch ne Spinlock ist) gemeint, wo du busy-waiting machst und ne Semaphore wirst du als Thread schlafen gelegt und irgendwann wieder aufgeweckt.

Aha, gut zu wissen, bevor wir später an einander vorbei schreiben. Semaphoren kann es in meinem OS-Kernel nicht geben, weil ununterbrechbar, die gibt es bei mir nur auf User-Mode-Ebene und müssen per Syscall vom Kernel angeboten werden (aber das kommt erst später).


Grüße
Erik

[FlashBurn]

Ich bin ehrlich der Meinung wenn Dein OS mindestens 32 MB will dann geht das völlig in Ordnung. Unter nem Pentium machts doch Dein OS auch nicht.

Ich habe gerade mal damn small linux ausprobiert und das läuft (halbwegs "normal") ab 24MB (waren es glaub ich).
Es ist sogar schwierig für mich mein OS mit nur 4MB zu testen (ist das momentane Minimum) und das geht auch nur in einem Emulator auf richtiger Hardware habe ich dann 8MB und die sind auch das Ziel.
Ich weiß auch gar nicht wo ich im Moment schon bin.

Also ich hab das SlabAllocator-Konzept eher so verstanden das man sich bemüht möglichst große Slabs zu benutzen um eben möglichst selten die normale page-basierte Speicherverwaltung zu belästigen.

Ich hatte mir auch mal direkt den Code angesehen und da war es noch so das sie versucht haben mind.8 Objekte in einen Slab zu bekommen und den Verschnitt unter einer bestimmte Grenze gehalten haben.

Ich möchte für meinem Kernel-Heap die Slabs 512 kBytes groß machen.

Da passen ja von meiner AVL-Struktur 26214 Objekte rein. Aber du bist da ja mit deinen Segmenten auch ein wenig "eingeschränkt" (muss jetzt kein Nachteil sein, jeder hat seine eigenen Ziele).

Schau Dir noch mal dieses Magazin-Zeugs an und überlege wie viele Objekte Du schon allein brauchst um genügend Magazine (wo jedes ja wohl mindestens 8 Objekte aufnimmt) für 8 CPUs zu befüllen. Variable Magazin-Größe möchte ich nicht umsetzen, das ist mir zu viel Aufwand, ich denke eine feste Größe von 16 Objekten pro Magazin ist eine recht gute Basis.

Ich habe dieses Konzept komplett anders implementiert. Bei mir ist ein Magazin immer 4 Objekte groß und jede CPU hat 2 Magazine, ein volles und ein leeres.
Sind beide leer wird eins wieder voll gemacht und sind beide voll wird eins leer gemacht (dafür werden jeweils die "normalen" SlabAllocator Funktionen aufgerufen, es geht von daher an dieser Stelle noch optimaler, aber es läuft erstmal).

Auch die Objekt-Initialisierung findet bei mir nicht statt wenn die Objekte in den Cache/Slab kommen, sondern wenn das Objekt rausgegeben wird (das selbe mit dem Dekonstruktor, da dann wenn das Objekt zurück gegeben wird).
Ich nutze diese Initialisierung im Moment sowieso nur dazu den Speicher des Objekts zu nullen.

Der Heap ist dafür da Objekte mit beliebiger Größe möglichst optimal zu verwalten. Der, mit Pages arbeitende, VMM des OS-Kernels kann das nicht.

Richtig, aber der Heap wird auch nur um ein vielfaches der Page-Größe vergrößert und darum kümmert sich ja malloc().

Wirklich? Bedeutet das wenn ich "new int" mache das ich dann ein komplette Page nur für die 4 Bytes bekomme (und 4092 Byte verschwende)? Was ist wenn ich extrem oft "new int" (oder für andere recht kleine Objekte) mache? Dann entsteht doch ein unheimlicher Verschnitt.

Nope. Wie gesagt ich habe schon ein malloc(), aber eben kein Heap der zusammenhängend ist und nach oben wächst.

Ich habe mit diesem Heap-Konzept so meine Probleme. Eine normale Speicheraufteilung sieht doch so aus, dass der Stack von Oben (oberes Ende des Adressraums) nach unten wächst und der Heap vom Ende des Programm Images nach Oben wächst.
Wo werden dann irgendwelche Libraries hingemappt und was ist wenn man mehrere Threads hat, die ja auch ihre Stacks brauchen und was ist mit den Lücken im Adressraum die ja irgendwann entstehen? Können die dann auch noch benutzt werden oder sind die weg?

Da ich das alles nicht so richtig nachvollziehen kann, habe ich mich dafür entschieden, das der "Heap" halt zerstückelt wird und das bekommt was frei ist. Im Endeffekt wächst alles bei mir nach Oben und auch die Größe des Stacks muss vorher bekannt sein (also der max. Wert).

Also wirklich brauchen tut man das IMHO nicht aber es macht die malloc-Implementierung leichter wenn man den Bereich im virtuellen Adressraum, der für den Heap benutzt wird, einfach so vergrößern kann und der Heap sich nicht über mehrere zusammenhanglose Stücken im virtuellen Adressraum verteilt.

Wieso ist das vorteilhafter? Der Heap wird im Endeffekt doch eh zerstückelt/fragmentiert und du verwaltest den Heap ja auch "nur" in irgendwelchen Datenstrukturen die mit Pointer auf einen bestimmten Speicherbereich zeigen, von daher ist es doch egal ob der zusammenhängend ist oder nicht.

Sowas gibt es in der Standard-libc nicht.

Ich muss wieder lesen üben Habe ich total überlesen das du die libc meinst.

Aha, gut zu wissen, bevor wir später an einander vorbei schreiben. Semaphoren kann es in meinem OS-Kernel nicht geben, weil ununterbrechbar, die gibt es bei mir nur auf User-Mode-Ebene und müssen per Syscall vom Kernel angeboten werden (aber das kommt erst später).

Heißt das auch um die CPU an einen anderen Thread abzugeben, musst du erst wieder zurück in den UserMode oder anders ausgedrückt, du kannst aus deinem Kernel heraus nicht deinen Scheduler aufrufen? Wie machst du es dann das du vom UserMode aus an den Scheduler abgeben kannst ohne das dieser von einem Timer aufgerufen wurde?

[Svenska]

Eher richte ich meine Zugriffe auf malloc() und Freunde so aus, wie das OS sie optimal verarbeitet. Schließlich soll mein App1.0 unter Kernel1.0 lauffähig sein, aber exakt das gleiche Binary auch unter Kernel2.0 ... und das geht nur, wenn ich eine Schicht dazwischen habe, die mir die Unterschiede zwischen Kernel1.0 und Kernel2.0 wegabstrahiert. Das ist üblicherweise die libc/libX11/etc.

Naja, erstmal ist das wieder auf Linux bezogen (und auch noch direkt für X11, das ist nicht wirklich portabel!), für Windows sollte das nicht zutreffen, bzw. ist es ja dort so das nicht alle Programme mit einer neueren Version laufen.

Doch. Die Windows-ABI ist seit Windows 3.0 vollständig stabil (GDI etc.), und wenn man von den modernen 64-Bit-Betriebssystemen absieht, die keine 16-Bit-Programme mehr unterstützen, dann geschah die Erweiterung des Systems immer durch Einfügen NEUER API-Funktionen.

Zumal bei Windows viele interne Kernelfunktionen nicht exportiert werden.

Und warum soll ich das nicht in einer eigenen Library abstrahieren. Der Punkt ist doch das du nie wissen kannst was für ein Allocator hinter malloc() steckt und wie effizient der ist und wenn du deinen eigenen schreibst kannst du alle Sachen die du schon weißt und die für die Speicherverwaltung wichtig sind, mit einfließen lassen und das geht bei malloc() halt nicht.

Ich kann ein paar Benchmarks auf übliche Optimierungen loslassen und eine OS-Weiche einbauen, welche malloc am effizientesten benutzt... oder meine Nutzung auf deine malloc-Implementierung abstimmen. Dein malloc sollte jedenfalls, wenn es schon mit Optimalwerten gefüttert wird, auch optimal arbeiten; und es sollte am besten auf deinen VMM abgestimmt sein.

Niemals so, dass ich ein Flag explizit angebe und es dann ignoriert wird.

Du bist also der Meinung "lieber einen Syscall der nichts macht obwohl er eigentlich könnte wenn auch nicht ganz optimal als einen Syscall der versucht sich so gut wie möglich zu verhalten aber das nicht zusichert"? Diese Einstellung kann ich nicht nachvollziehen.

Diese Einstellung unterliegt folgendem Gedanken: Wenn ich der Meinung bin, dass ich es besser weiß, dann soll sich nichts in meinen Weg stellen. Also entweder mir ist es egal oder ich traue dem System, dann gebe ich kein Flag an und alles geht wahrscheinlich so, wie ich es möchte (die Automatik). Wenn ich es besser weiß, dann gebe ich ein Flag an und erzwinge damit ein gewünschtes Verhalten auch auf die Gefahr hin, dass es schlechter ist. Dann möchte ich bitte nicht von der Automatik in die Ecke gedrängt werden.

Also spätestens wenn Du mal nen halben Arbeitstag auf das Ende einer Simulation wartest und dann kurz vor Schluss das Simulationsprogramm noch mal etwas Speicher braucht und dann, nur weil es am meisten Speicher braucht, vom OS gekillt wird entwickelst Du eine andere Meinung.

Ein Prozess darf nur [Limit hier einsetzen] des verfügbaren Speichers belegen und bekommt dann ein NULL vom malloc. Mir ging es darum, dass der verfügbare Speicher im System komplett ausgeschöpft ist (nicht durch einen einzelnen Prozess) und der Kernel seine internen Speicheranforderungen nicht mehr erfüllen kann. Dann eher killen als abstürzen.

Ein OS das einfach nach belieben irgendwelche Prozesse killt möchte ich nicht haben, lieber soll es keinen unprivilegierten Programmen neuen Speicher geben so das diese Programme die Möglichkeit haben angemessen zu reagieren.

Das hatte ich nicht gemeint.

Wenn du allgemeine Treiber nutzt, ist das nicht möglich; deren Speicheranforderung kann sich stark unterscheiden, je nach Auslastung.

Durch was schwankt der Speicherverbrauch eines Treibers so stark? Wenn ich jetzt mal an einen SATA-AHCI-Treiber denke dann bekommt der maximal wie viele Jobs gleichzeitig? Sagen wir mal 100 und nehmen für jeden Job mal 4 kB zur internen Verwaltung (ist das zu wenig?) dann schwankt der RAM-Bedarf dieses Treiber um maximal 400kB. Wo ist da das Problem? Das sollte die malloc-Implementierung doch recht gut abfangen können so das der Treiber normalerweise gar keine Speicheranforderungen an den Kernel schickt.

Ich denke da an so semi-offene WLAN-Treiber, wo die Hauptarbeit in der Firmware gemacht wird und die Aufgabe des Treibers nur darin besteht, der Firmware eine Umgebung bereitzustellen. Wieviel Speicher die Firmware dann für die Hardware benötigt, kannst du weder abschätzen noch beeinflussen.

Trifft das auch auf Programme zu die nur von der libc (kein POSIX oder sonstwas) abhängig sind?

Warum sollte das da nicht zutreffen. Nehmen wir mal an du hast nen Syscall da irgendetwas macht und du änderst hin dahingehend, das noch ein size-Parameter dazu kommt und den kannst du auch in der Library nicht rausbekommen, sondern den Wert weiß nur der User, wie willst du das wegabstrahieren?

Wenn du eine bash oder eine sonstige Anwendung auf dein System portierst, dann kennt diese den Wert auch nicht. Ansonsten implementierst du in der Library die Funktion zweimal: einmal die alte Variante ohne Größenangabe (die setzt den vorher verwendeten Standardwert) und einmal mit Größenangabe für neue Programme. Das nennt man Kompatiblitätshölle.

Sowas gibt es in der Standard-libc nicht.

Ich muss wieder lesen üben Habe ich total überlesen das du die libc meinst.

Du mochtest es nicht, wenn ich libc sage und wirfst mir Linux-Denke vor, also habe ich auf "Library" verallgemeinert. Solange du irgendwann Programme portieren möchtest, wirst du definitiv irgendwelche davon brauchen.

Gruß,
Svenska

[FlashBurn]

Du mochtest es nicht, wenn ich libc sage und wirfst mir Linux-Denke vor, also habe ich auf "Library" verallgemeinert. Solange du irgendwann Programme portieren möchtest, wirst du definitiv irgendwelche davon brauchen.

Naja, ich dachte da eher an OS spezifische Libraries wie unter Haiku die Kits und nicht an allgemeine wie libc oder QT und solche Konsorten. Das die API da gleichbleibt ist logisch, aber wenn ich halt so OS spezifische Sachen habe, kann ich das dann auch mit der Library meistens nicht abfangen.

Ich kann ein paar Benchmarks auf übliche Optimierungen loslassen und eine OS-Weiche einbauen, welche malloc am effizientesten benutzt... oder meine Nutzung auf deine malloc-Implementierung abstimmen. Dein malloc sollte jedenfalls, wenn es schon mit Optimalwerten gefüttert wird, auch optimal arbeiten; und es sollte am besten auf deinen VMM abgestimmt sein.

Ich meine vorallem das du ja nicht statisch linken wirst, sondern die libc als ne shared library nutzen wirst und da kannst du nicht wissen was für eine malloc() Implementation da gerade läuft. Deswegen nutzt du halt deine eigene und die ist direkt in deinem Programm mit drin.

[erik.vikinger]

Hallo,

Ich hatte mir auch mal direkt den Code angesehen und da war es noch so das sie versucht haben mind.8 Objekte in einen Slab zu bekommen und den Verschnitt unter einer bestimmte Grenze gehalten haben.

Naja, dann wird eben häufiger doch der VMM bemüht neue Slabs herbei zu schaffen.

Ich möchte für meinem Kernel-Heap die Slabs 512 kBytes groß machen.

Da passen ja von meiner AVL-Struktur 26214 Objekte rein.

So ist das ja auch gedacht. Der 512kB-Slab ist zwar erst mal ein dicker Brocken aber dafür hält der ne Weile. Und da bei meinem VMM die Größe des angeforderten Speicherblocks nicht in die zum Allozieren benötigte Zeit eingeht (ich hab ja beim Kernel-Heap kein Paging dahinter das erst mal alle PD-Einträge richten muss) will ich lieber etwas größer ansetzen.

Aber du bist da ja mit deinen Segmenten auch ein wenig "eingeschränkt" (muss jetzt kein Nachteil sein, jeder hat seine eigenen Ziele).

Ich denke ich werde den Kernel-Heap nicht auf Segmenten aufbauen sondern direkt auf den physischen Speicher ganz ohne Segmente und Paging, das bedeutet aber auch das ich den Kernel-Heap nicht im physischen RAM defragmentieren kann (das ist auch einer der Gründe warum ich lieber richtig große Slabs haben will). Aber eine endgültige Entscheidung hab ich da noch nicht getroffen.

Ich nutze diese Initialisierung im Moment sowieso nur dazu den Speicher des Objekts zu nullen.

Das wollte ich mir ganz sparen, wenn kmalloc ein Objekt liefert dann steht da irgendetwas drin und der entsprechende Code der mit diesem Objekt was machen will schreibt da eh rein was er für sinnvoll hält so das diese Initialisierung IMHO unnötig ist.

Ich habe mit diesem Heap-Konzept so meine Probleme. Eine normale Speicheraufteilung sieht doch so aus, dass der Stack von Oben (oberes Ende des Adressraums) nach unten wächst und der Heap vom Ende des Programm Images nach Oben wächst.

Ja, üblicherweise macht man das so.

Wo werden dann irgendwelche Libraries hingemappt und was ist wenn man mehrere Threads hat, die ja auch ihre Stacks brauchen und was ist mit den Lücken im Adressraum die ja irgendwann entstehen? Können die dann auch noch benutzt werden oder sind die weg?

Für Librarys und die vielen Stacks wird oft jeweils ein festgelegter Bereich in dem einen virtuellen Adressraum benutzt. Das ist ja gerade der Punkt wo ich meine Segmente im Vorteil sehe, jedes davon ist absolut unabhängig von den anderen. Bei mir hat quasi jeder Prozess bis zu 32k virtuelle Adressräume und theoretisch kann jeder dieser Adressräume bis nahe 4GB groß werden (solange die Summe aller Segmente in den Speicher passt). Meine Stacks sind daher auch in keinster Weise Limitiert außer natürlich von der tatsächlich vorhandenen Menge an Speicher (aber vermutlich werde ich auch ein Limit vorsehen bis zu dem der Kernel die Stacks automatisch vergrößert und darüber aber doch den Prozess killt).

auch die Größe des Stacks muss vorher bekannt sein (also der max. Wert).

Das ist aber ein konstruktives Limit in Deinem OS, damit schränkst Du die maximale Anzahl an Threads pro Prozess eventuell erheblich ein (wenn Du die Stacks zu groß machst) oder Deine Threads können sich nicht richtig auf dem Stack austoben (wenn Du diese zu klein machst).

Habe ich total überlesen das du die libc meinst.

Das ist einfach nur eine Library von vielen die es auf verschiedenen OSen gibt und die die entsprechenden OS-Services erfolgreich weg abstrahiert.

Heißt das auch um die CPU an einen anderen Thread abzugeben, musst du erst wieder zurück in den UserMode oder anders ausgedrückt, du kannst aus deinem Kernel heraus nicht deinen Scheduler aufrufen?

Doch, natürlich kann ich im Kernel-Mode den laufenden User-Mode-Thread wechseln. Wie soll das den auch sonst gehen? Ich hab sogar noch ein kleines Extra-Feature: der Scheduler muss kein RET machen und den ganzen Call-Chain vom Kernel-Mode wieder Rückwerts durchlaufen sondern er bereitet einfach alle Register mit den zuletzt vom Thread benutzten Werten vor und macht ein RFS (Return-From-Systemmode) und schon ist die CPU wieder im User-Mode und genau an der Stelle wo der Thread unterbrochen wurde. Das bedeutet vor allem das ich meine Dispatcher-Funktion von überall aus dem Kernel aufrufen kann, sie kommt nur nie zurück. Ein Mode-Wechsel beeinflusst bei mir nicht den Speicher (auch nicht den Stack, weder den User-Mode-Stack noch den CPU-spezifischen Kernel-Mode-Stack) sondern nur die Register und die Schatten-Register. Mit dem RFS ist auch der gesamte Kernel-Mode-Stack der aktuellen CPU verschwunden (also der Stack-Pointer vergessen) und wenn diese CPU wieder in den System-Mode wechselt (durch Syscall/Yield/IRQ/Exception oder eine abgelaufene Zeitscheibe) hat die CPU wieder einen frischen und jungfräulichen Kernel-Mode-Stack (also der Stack-Pointer steht wieder am Anfang).

Wie machst du es dann das du vom UserMode aus an den Scheduler abgeben kannst ohne das dieser von einem Timer aufgerufen wurde?

Dafür hab ich extra eine Yield-Instruktion vorgesehen die das selbe macht wie wenn der Zeitscheiben-Counter abgelaufen ist (so das ich dafür nicht extra einen Syscall benötige). Der Counter bleibt dabei erhalten so das der Kernel sieht wie viel von der Zeitscheibe noch übrig ist um das eventuell wohlwollend zu berücksichtigen (keine Ahnung ob ich sowas mal implementiere). Es wird aber auch blockierende Syscalls geben wo der aufrufende Thread zwar eine Aktion auslöst aber dann doch in seinem Thread-Descriptor gesichert und als blockiert markiert wird, anschließend ruft der Kernel dann den Dispatscher auf der den nächsten Thread aus der runnable-Liste holt. Irgendwann ist die ausgelöste Aktion fertig (aufgrund von externen Ereignissen) und der Thread wird wieder als runnable markiert, sein Zustand so geändert das in den gesicherten Registern die richtigen Rückgabewerte für den ursprünglichen Syscall drin sind und dann kommt der Thread in die runable Liste und wird irgendwann vom Dispatcher wieder aufgerufen. Der Thread macht dann mit dem Befehl weiter der unmittelbar hinter den ursprünglichen Syscall-Befehl steht und wertet ganz normal die Rückgabewerte aus. Ein Semaphore-Enter-Syscall ist da ein gutes Beispiel, der kommt entweder sofort wieder zurück (weil die Semaphore frei war) oder er blockiert (weil die Semaphore belegt ist) und irgendwann (wenn die Semaphore wieder frei gegeben wird) wird dieser Thread wieder als runnable markiert (also aufgeweckt) und ist dann neuer Besitzer der Semaphore.

Diese Einstellung unterliegt folgendem Gedanken: Wenn ich der Meinung bin, dass ich es besser weiß, dann soll sich nichts in meinen Weg stellen. Also entweder mir ist es egal oder ich traue dem System, dann gebe ich kein Flag an und alles geht wahrscheinlich so, wie ich es möchte (die Automatik). Wenn ich es besser weiß, dann gebe ich ein Flag an und erzwinge damit ein gewünschtes Verhalten auch auf die Gefahr hin, dass es schlechter ist. Dann möchte ich bitte nicht von der Automatik in die Ecke gedrängt werden.

Sorry, aber das kann ich immer noch nicht nachvollziehen. Wenn ich mit einem Flag das OS bitte sich auf eine bestimmte Art zu verhalten (weil das für mich ideal wäre) dann kann es sein dass das OS dem nachkommt und ich hab Glück oder das OS kann dem nicht nachkommen (weil es dafür einen triftigen Grund gibt) und dann muss ich eben damit klar kommen. Solange letzteres keine funktionalen Einschränkungen nach sich zieht kann ich an diesem Konzept nichts verwerfliches finden. Eine Automatik ist IMHO von vornherein zum Scheitern verurteilt weil sie (bzw. der Programmierer) nie die realen Bedingungen zur Laufzeit vorhersehen kann.

Wenn ich es besser weiß, dann gebe ich ein Flag an und erzwinge damit ein gewünschtes Verhalten auch auf die Gefahr hin, dass es schlechter ist.

Selbst wenn dieses Verhalten schlechter ist als wenn das OS Deiner Bitte nur "so gut es geht" nach kommt?

Was hältst Du dann eigentlich von den ganzen Read-Ahead-Mechanismen die mache File-APIs anbieten? Das sind auch nur kann-Angelegenheiten denen das OS nachkommen darf wenn es denn die Möglichkeit hat aber es eben nicht muss wenn es gerade nicht geht.

Mir ging es darum, dass der verfügbare Speicher im System komplett ausgeschöpft ist (nicht durch einen einzelnen Prozess)

Das hab ich schon so verstanden (das es um mehrere Prozesse geht), trotzdem sollte das OS nicht einfach den Prozess killen der am meisten Speicher braucht, das ist manchmal gerade der Prozess der mir als User am wichtigsten ist (oder aber auch der Prozess der gerade Amok läuft).

und der Kernel seine internen Speicheranforderungen nicht mehr erfüllen kann. Dann eher killen als abstürzen.

Diese Situation kann eigentlich nur root herbei schaffen, weil nur der auch noch das letzte bisschen Speicher aufbrauchen kann. Wenn es wirklich so weit kommt dann ist es natürlich egal welchen Prozess das OS killt denn daran ist dann definitiv root selber schuld.

Ich denke da an so semi-offene WLAN-Treiber, wo die Hauptarbeit in der Firmware gemacht wird und die Aufgabe des Treibers nur darin besteht, der Firmware eine Umgebung bereitzustellen. Wieviel Speicher die Firmware dann für die Hardware benötigt, kannst du weder abschätzen noch beeinflussen.

Auch hier sehe ich nicht warum der Speicherbedarf zur Laufzeit (also nach dem alle Vorbereitungshandlungen abgeschlossen sind) noch großartig schwanken sollte.

Deswegen nutzt du halt deine eigene und die ist direkt in deinem Programm mit drin.

Wenn Du eine eigene Heap-Library benutzen möchtest dann solltest Du aber auch eine haben die wirklich gut auf das aktuell benutzte OS abgestimmt/optimiert ist.


Grüße
Erik

[FlashBurn]

Naja, dann wird eben häufiger doch der VMM bemüht neue Slabs herbei zu schaffen.

Eine Möglichkeit das noch etwas weiter zu optimieren, wäre, wenn du dem SlabAllocator beim Erstellen der "Slab-Beschreibung" mitteilst wieviele Objekte du mind. in einem Objekt haben willst.
Denn du als Programmierer solltest ja eher wissen wieviel Objekte du so im Normalfall benötigst.

Würde ich jetzt aber deine Variante benutzen, könnte ich das mit den 8MB RAM für mein OS gleich knicken. Denn mit 512KB pro Objekt-Typ werde ich wohl schon bei über 8MB sein

Das ist aber ein konstruktives Limit in Deinem OS, damit schränkst Du die maximale Anzahl an Threads pro Prozess eventuell erheblich ein (wenn Du die Stacks zu groß machst) oder Deine Threads können sich nicht richtig auf dem Stack austoben (wenn Du diese zu klein machst).

Also mit vorher bekannt meine ich damit, wenn du den Thread erstellst, musst du die max Größe des Threads angeben.

Wie würdest du es denn auf x86 lösen bzw. wie wird es denn gelöst? Wäre nicht schlecht wenn mir mal jemand den Adressraumaufbau unter z.B. Linux erklären könnte, das ich das vielleicht mal verstehe

Wenn Du eine eigene Heap-Library benutzen möchtest dann solltest Du aber auch eine haben die wirklich gut auf das aktuell benutzte OS abgestimmt/optimiert ist.

Das sollte klar sein. Der SlabAllocator wurde ja auch in den UserSpace "übertragen", auf der einen Seite ist das bestimmt von Vorteil, aber auf der anderen Seite, wird wohl kaum ein normales Programm den SlabAllocator direkt nutzen, sondern nur über den Umweg von malloc() und da bringt er (meiner Meinung nach) nicht mehr so viel.

[Svenska]

Hallo,

Diese Einstellung unterliegt folgendem Gedanken: Wenn ich der Meinung bin, dass ich es besser weiß, dann soll sich nichts in meinen Weg stellen. Also entweder mir ist es egal oder ich traue dem System, dann gebe ich kein Flag an und alles geht wahrscheinlich so, wie ich es möchte (die Automatik). Wenn ich es besser weiß, dann gebe ich ein Flag an und erzwinge damit ein gewünschtes Verhalten auch auf die Gefahr hin, dass es schlechter ist. Dann möchte ich bitte nicht von der Automatik in die Ecke gedrängt werden.

Sorry, aber das kann ich immer noch nicht nachvollziehen. Wenn ich mit einem Flag das OS bitte sich auf eine bestimmte Art zu verhalten (weil das für mich ideal wäre) dann kann es sein dass das OS dem nachkommt und ich hab Glück oder das OS kann dem nicht nachkommen (weil es dafür einen triftigen Grund gibt) und dann muss ich eben damit klar kommen. Solange letzteres keine funktionalen Einschränkungen nach sich zieht kann ich an diesem Konzept nichts verwerfliches finden. Eine Automatik ist IMHO von vornherein zum Scheitern verurteilt weil sie (bzw. der Programmierer) nie die realen Bedingungen zur Laufzeit vorhersehen kann.

Naja, ich seh das allgemein etwas anders. Einmal sollte sich eine Automatik durchaus zur Laufzeit konfigurieren lassen, denn für jeden möglichen Anwendungsfall kann man es nicht konfigurieren - und wenn das OS aus einem bestimmten Grund der Meinung ist, mein Flag nicht erfüllen zu können, dann sollte es mir bescheidsagen und nichts tun.

Ich frage ja auch nicht im Supermarkt nach Vollmilch und kriege nur fettfreie Milch. Da kommt dann erstmal ein "gibts nicht" und ich muss selbst abhängig davon entscheiden. Wenn ich also ein MAP_NOW möchte, dann möchte ich entweder ein MAP_NOW oder garnichts. (Ich kann es ja danach nochmal ohne Flag probieren.)

Wenn ich es besser weiß, dann gebe ich ein Flag an und erzwinge damit ein gewünschtes Verhalten auch auf die Gefahr hin, dass es schlechter ist.

Selbst wenn dieses Verhalten schlechter ist als wenn das OS Deiner Bitte nur "so gut es geht" nach kommt?

Ja.

Was hältst Du dann eigentlich von den ganzen Read-Ahead-Mechanismen die mache File-APIs anbieten? Das sind auch nur kann-Angelegenheiten denen das OS nachkommen darf wenn es denn die Möglichkeit hat aber es eben nicht muss wenn es gerade nicht geht.

Ich bin der Meinung, dass ich Dinge erzwingen können muss, d.h. wenn ich ein (synchrones/blockierendes) Readahead anfordere, dann möchte ich auch einen Fehler zurückkriegen, wenn das nicht gelungen ist. Wenn ich kein Flag angebe, dann ist das deine kann-Entscheidung (die von einer Automatik gefällt wird).

Das hab ich schon so verstanden (das es um mehrere Prozesse geht), trotzdem sollte das OS nicht einfach den Prozess killen der am meisten Speicher braucht, das ist manchmal gerade der Prozess der mir als User am wichtigsten ist (oder aber auch der Prozess der gerade Amok läuft).

Welche Kriterien hast du denn sonst noch, wenn das System gerade vollständig an der Wand steht? Einfach zu sagen "wenn root das macht, dann ist er selbst schuld" ist nicht hinreichend; was passiert, wenn ein root-Prozess amokläuft und dieser Prozess inhärent ein root-Prozess sein muss (fsck, Treiber)?

Der OOM-Killer muss primitiv sein. Und wenn der kommt, dann ist sowieso irgendwas anderes komplett im Eimer. Bei dem geht es nur darum, einen betriebsfähigen Zustand wiederherzustellen, koste es was es wolle.

Ich denke da an so semi-offene WLAN-Treiber, wo die Hauptarbeit in der Firmware gemacht wird und die Aufgabe des Treibers nur darin besteht, der Firmware eine Umgebung bereitzustellen. Wieviel Speicher die Firmware dann für die Hardware benötigt, kannst du weder abschätzen noch beeinflussen.

Auch hier sehe ich nicht warum der Speicherbedarf zur Laufzeit (also nach dem alle Vorbereitungshandlungen abgeschlossen sind) noch großartig schwanken sollte.

Du hast keinerlei Kontrolle über die Firmware. Und ich kann mir durchaus vorstellen, dass ein Grafiktreiber plötzlich mangels Grafikspeicher anfängt, die Texturen in das System-RAM auszulagern, um überhaupt eine Darstellung zu ermöglichen. Man sollte das in Erwägung ziehen und entweder bewusst verhindern oder als Möglichkeit offenlassen. Zumindest sollte man darüber nachdenken.

Naja, ich dachte da eher an OS spezifische Libraries wie unter Haiku die Kits und nicht an allgemeine wie libc oder QT und solche Konsorten. Das die API da gleichbleibt ist logisch, aber wenn ich halt so OS spezifische Sachen habe, kann ich das dann auch mit der Library meistens nicht abfangen.

Auch da sollte die Library eine relativ stabile API/ABI anbieten, damit Programme auch bei sich wandelndem Kernel weiterhin funktionieren. Im besten Konzept überhaupt machst du es wie Microsoft und erweiterst deine API um neue Funktionen, fasst deine bereits vorhandenen aber nie wieder an (außer in der Implementierung).

Ich meine vorallem das du ja nicht statisch linken wirst, sondern die libc als ne shared library nutzen wirst und da kannst du nicht wissen was für eine malloc() Implementation da gerade läuft. Deswegen nutzt du halt deine eigene und die ist direkt in deinem Programm mit drin.

Ich gehe davon aus, dass die System-Library durchaus eine performante malloc-Implementation bereitstellt. Außerdem ist die Library selbst systemspezifisch und meine OS-Weiche kann ja auch die OS-Version mit berücksichtigen.

Gruß,
Svenska

[erik.vikinger]

Hallo,

wenn du dem SlabAllocator beim Erstellen der "Slab-Beschreibung" mitteilst wieviele Objekte du mind. in einem Objekt haben willst.

Ich habe nicht vor sowas automatisch zur Laufzeit machen zu lassen, für die paar Objektgrößen die ich in meinem Micro-Kernel benötige kann ich vorher zur Design-Zeit festlegen wie die einzelnen Slabs genau aufgebaut sein sollen.

Würde ich jetzt aber deine Variante benutzen, könnte ich das mit den 8MB RAM für mein OS gleich knicken. Denn mit 512KB pro Objekt-Typ werde ich wohl schon bei über 8MB sein

Ich bin mir nicht sicher was mein OS so brauchen wird um anzufangen aber wenn ich bedenke das ich bei der Lebendgeburt meines OS schon 3 Prozesse haben möchte (jeder braucht eine 512kB-LDT und natürlich seinen Code + Daten und Stack, für idle muss ich sogar mehrere Threads erstellen (für jede CPU einen) von denen jeder Stack benötigt), dazu kommen 5 oder 6 Slabs mit je 512kB und dann noch der Kernel-Code und für jede CPU einen Kernel-Mode-Stack. Ich schätze da sind bei 4 CPUs bereits 8MB weg, ohne jetzt mal Code + Daten der 3 Initial-Prozesse zu berücksichtigen (da ist z.B. eine RAM-Disk mit den weiteren Executables für Treiber usw. mit dabei). Ich denke wenn der Boot-Code nicht wenigstens 64MB vorfindet wird er gleich ablehnen müssen. Der Punkt ist aber das dieser Eigenbedarf des Kernel zur Laufzeit nicht mehr so stark ansteigen wird, außer ab und an mal einen neuen Slab wird der Kernel nicht viel benötigen. Der Task-Manager, von dem Windows-XP an dem ich gerade sitze, zeigt mir über 700 Threads von über 65 Prozessen an, ich weiß zwar nicht wie viel RAM der Windows-Kernel selber nur allein für deren Verwaltung benötigt aber das dürfte schon einiges sein. Spätestens bei einer derartigen Auslastung fallen meine großen Slabs auch nicht mehr ins Gewicht, dafür spare ich mir pro Prozess ein Paging-Directory.

Also mit vorher bekannt meine ich damit, wenn du den Thread erstellst, musst du die max Größe des Threads angeben.

Ich als Programmierer weiß aber nicht immer wie viel Stack meine Threads so brauchen werden. Gerade bei Workerthreads (die ja oft aus einem vorbestücktem Pool genommen werden) hängt die Stackbenutzung doch sicher auch mal von der konkreten Aufgabe ab die die einzelnen Threads dann tatsächlich bearbeiten.

Wäre nicht schlecht wenn mir mal jemand den Adressraumaufbau unter z.B. Linux erklären könnte, das ich das vielleicht mal verstehe

Da dürfte die Suchmaschine Deines geringsten Misstrauens doch sicher behilflich sein.

Der SlabAllocator wurde ja auch in den UserSpace "übertragen", auf der einen Seite ist das bestimmt von Vorteil, aber auf der anderen Seite, wird wohl kaum ein normales Programm den SlabAllocator direkt nutzen, sondern nur über den Umweg von malloc() und da bringt er (meiner Meinung nach) nicht mehr so viel.

Wenn der SlabAllocator hinter einem generischen malloc steckt dann muss er für jede übergebene Größe erst mal ermitteln mit welchem Slab-Pool er dann arbeiten soll, wie Aufwändig das ist kann ich jetzt auch nicht so genau sagen. In meinem Kernel kenne ich die möglichen Objekt-Type bereits im voraus und kann ein switch nehmen das sich mit sehr wenigen Assemblerbefehlen umsetzen lässt, aber in einem unbekannten User-Programm dürfte da ein Baum nötig werden und der kostet einfach jedes mal etwas Zeit. Die Frage ist einfach "Kann der SlabAllocator das mit seiner hohen Performance wieder rausholen?".

Naja, ich seh das allgemein etwas anders.

Tja, Meinungen sind eben doch verschieden!
Warum streiten wir uns eigentlich über ein Flag von FlushBurns OS? Soll er doch gleich 5 Varianten "MAP_IMMER_SOFORT", "MAP_MOEGLICH_SOFORT", "MAP_EGAL", "MAP_MOEGLICH_SPAETER" und "MAP_IMMER_SPAETER" machen und jeder von uns ist zufrieden.

Einmal sollte sich eine Automatik durchaus zur Laufzeit konfigurieren lassen

Und wer soll das konfigurieren? Meine Oma konfiguriert bestimmt nicht die Mapping-Optionen fürs Paging. Ich bleibe bei der Meinung das der Programmierer einer bestimmten Applikation noch am besten abschätzen kann was für sein Programm optimal wäre und was zumindest noch akzeptabel ist und dann eben das OS zwingt wenigstens das akzeptable einzuhalten und gleichzeitig bittet das Optimum zu versuchen.

und wenn das OS aus einem bestimmten Grund der Meinung ist, mein Flag nicht erfüllen zu können, dann sollte es mir bescheidsagen und nichts tun.

Und der zusätzliche Syscall kostet bald mehr als die Optimierung überhaupt hätte bringen können? Was ist wenn es um eine kleine Aktion geht die aber sehr oft ausgeführt wird?

Ich frage ja auch nicht im Supermarkt nach Vollmilch und kriege nur fettfreie Milch. Da kommt dann erstmal ein "gibts nicht"

Sicher, aber ein guter Verkäufer wird Dir noch im selben Atemzug die fettfreie Milch empfehlen.

Wenn ich also ein MAP_NOW möchte, dann möchte ich entweder ein MAP_NOW oder garnichts.

Das empfinde ich persönlich aber als Engstirnig. Dir entsteht doch kein funktionaler Nachteil wenn das MAP_NOW nicht komplett (sondern nur zum Großteil) erfüllt werden kann. Der einzigste Nachteil ist eine minimal geringere Performance.
Betrachte es mal von einer anderen Seite: normalerweise hast Du dieses Parameter nicht und musst Dich eh auf die Automatik vom OS verlassen aber bei FlashBurns OS gibt es die Möglichkeit diese Automatik wenigstens zu versuchen zu Deinen Gunsten zu beeinflussen. Egal wie Du das Flag benutzt Dir entsteht, gegenüber einem OS ohne dieses Flag, erst mal kein Nachteil. Du kannst also nur gewinnen.

Ich bin der Meinung, dass ich Dinge erzwingen können muss

Das ist aber unsozial! Gerade bei einem OS das die Wünsche von sehr vielen Programmen parallel erfüllen muss sollte man nicht alles mit Zwang machen sondern sich eher etwas kooperativer verhalten.

Wenn ich kein Flag angebe, dann ist das deine kann-Entscheidung (die von einer Automatik gefällt wird).

Automatik allein reicht aber oft nicht um eine gute Entscheidung zu treffen, oft ist es eben sinnvoll der Automatik wenigstens einen Hinweis zu geben.

Welche Kriterien hast du denn sonst noch, wenn das System gerade vollständig an der Wand steht?

Klar, keine mehr. Dann muss eben der allerletzte Notfallplan benutzt werden, egal welche Konsequenzen das hat. Wichtig ist mir das diese Situation unter "normalen" Umständen erst gar nicht eintritt.

Du hast keinerlei Kontrolle über die Firmware. Und ich kann mir durchaus vorstellen, dass ein Grafiktreiber plötzlich mangels Grafikspeicher anfängt, die Texturen in das System-RAM auszulagern, um überhaupt eine Darstellung zu ermöglichen. Man sollte das in Erwägung ziehen und entweder bewusst verhindern oder als Möglichkeit offenlassen. Zumindest sollte man darüber nachdenken.

Natürlich kann ein OS auch aufgrund eines Amok laufenden Treibers an die Wand gefahren werden und wenn dieser mit root-Rechten läuft (was wohl der Normalfall ist) dann ist das besonders kritisch weil der OOM-Killer sich wohl nicht traut den als ersten zu killen sondern sich erst mal an den normalen User-Prozessen schadlos hält. Das ist einer der Gründe warum root bei der Auswahl der Programme die er startet etwas mehr Sorgfalt walten lassen muss. Ich bin aber trotzdem der Meinung das 75% für den nichtauslagerbaren Speicher eine gute Obergrenze ist bei der dann der VMM erst mal Schluss macht weiteren Speicher an Prozesse (egal ob root oder nicht) zu vergeben sondern nur noch für den Kernel selber was hergibt. Mehr als 20% nichtauslagerbaren Speicher sollte es in einem normalen System eigentlich nicht geben.

machst du es wie Microsoft und erweiterst deine API um neue Funktionen, fasst deine bereits vorhandenen aber nie wieder an

Also es gibt in der inoffiziellen WIN-API durchaus immer wieder Änderungen, manchmal sogar von einem SP zum nächsten.


Grüße
Erik

[FlashBurn]

Ich als Programmierer weiß aber nicht immer wie viel Stack meine Threads so brauchen werden. Gerade bei Workerthreads (die ja oft aus einem vorbestücktem Pool genommen werden) hängt die Stackbenutzung doch sicher auch mal von der konkreten Aufgabe ab die die einzelnen Threads dann tatsächlich bearbeiten.

Du musst die Stacks deiner Threads so oder so beschränken. Denn wenn du mehrere hast, müssen die ja irgendwo hin in deinen Adressraum und somit gibt es dann Grenzen, nämlich da wo ein anderer Thread anfängt.
Da ich als OS nicht wissen kann wieviel Threads ein Programm wohl haben wird, gebe ich dem Programm halt die Möglichkeit die Stack-Größe selber zu wählen.
Was die maximale Größe eines Threads betrifft, die lässt sich rausbekommen. Man muss einfach nur wissen welche Funktionen werden aufgerufen und macht das für jede Funktion die aufgerufen kann wieder (also gucken welche Funktionen werden aufgerufen) und dann bekommst du auch nen maximalen Stackverbrauch.

Ich habe gerade mal geguckt, Standardgröße des Stacks ist unter Windows 1MB und unter Linux 2MB und man kann halt einfach bei der Thread-Erstellung angeben wie groß der Stack sein soll oder man gibt 0 an, dann entscheidet das OS.

Dazu dann die Frage, was ist die "richtige" Stackgröße? Spontan würde ich auch sagen, das 1MB ausreichend ist.

Da dürfte die Suchmaschine Deines geringsten Misstrauens doch sicher behilflich sein.

Ich habe sogar ein eBook zum Speichermanagement unter Linux und auch das konnte es mir nicht näher bringen

Wenn der SlabAllocator hinter einem generischen malloc steckt dann muss er für jede übergebene Größe erst mal ermitteln mit welchem Slab-Pool er dann arbeiten soll, wie Aufwändig das ist kann ich jetzt auch nicht so genau sagen.

Sollte gar nicht so schwierig und langsam sein. Man erstellt eh vorher (bei der Initialisierung von malloc()) Slabs mit einer Größe von 2er Potenzen.
Du musst dir ja nur das höchste Bit angucken und in der nächsten 2er Potenz liegt der Spass dann. Dann hast du einfach ein Array und könntest unter x86 sowas machen:

Code: [Auswählen]

int slot= _bsr(size)
struct slab_t *slab= arrayOfSlabs[slot + 1];
Das sollte verdammt schnell sein, vorallem im Vergleich zu einem malloc() das erst in einer Liste nach einer "perfekten" Größe sucht.

Warum streiten wir uns eigentlich über ein Flag von FlushBurns OS?

Ihr streitet euch wegen mir

[erik.vikinger]

Hallo,

Du musst die Stacks deiner Threads so oder so beschränken.

Nein, ich muss das bestimmt nicht tun, Du musst das tun. Ich lege jeden Stack in ein eigenes Segment und bin glücklich das ich mich nicht dafür interessieren brauch wie stark die Stacks nun wachsen. Selbst auf einen 32Bit-System hab ich kein Problem damit wenn 1 oder 2 Threads ihren Stack auf ein ganzes GB anwachsen lassen (so lange genügen RAM verbaut ist).

Denn wenn du mehrere hast, müssen die ja irgendwo hin in deinen Adressraum und somit gibt es dann Grenzen, nämlich da wo ein anderer Thread anfängt.

Genau so ist es. Dieses Problem müssen alle Flat-Memory-OSe irgendwie lösen also schaffst Du das auch.

Da ich als OS nicht wissen kann wieviel Threads ein Programm wohl haben wird, gebe ich dem Programm halt die Möglichkeit die Stack-Größe selber zu wählen.

Das klingt erst mal recht vernünftig aber nicht immer kann der Programmierer das vorhersehen.

Man muss einfach nur wissen welche Funktionen werden aufgerufen und macht das für jede Funktion die aufgerufen kann wieder (also gucken welche Funktionen werden aufgerufen) und dann bekommst du auch nen maximalen Stackverbrauch.

Und was ist mit Rekursion? Man kann nicht immer zuverlässig vorhersagen wie oft rekursiert wird.

Dazu dann die Frage, was ist die "richtige" Stackgröße? Spontan würde ich auch sagen, das 1MB ausreichend ist.

Das ist schwer zu beantworten, auf der einen Seite ist das Allozieren von Objekten auf dem Stack extrem schnell (und auch manche Algorithmen lassen sich rekursiv leichter umsetzen) aber auf der anderen Seite wissen die Programmierer das der Stack begrenzt ist und versuchen damit sparsam umzugehen (und setzen auch Rekursion nicht so gerne ein). Ich persönlich bin mit Stack nicht sehr sparsam und hatte auch schon mal eine entsprechende Schutzverletzung unter Windows weil mein Programm doch zu oft rekursiert hat. Wenn man es nicht gewohnt ist sich bei der Stackbenutzung zu zügeln dann kann man damit zwar sicher etwas Performace gewinnen aber auf den üblichen Flat-Memory-Systemen läuft man eben auch Gefahr das einem der Stack schneller aus geht als man will.

Man erstellt eh vorher (bei der Initialisierung von malloc()) Slabs mit einer Größe von 2er Potenzen.

Du willst Deine Slabs nur auf 2er-Potenzen auslegen? Das gibt aber eine fette Speicherverschwendung! Was ist wenn ich 1048576 Objekte mit 36 Bytes brauche, hab ich dann 28MB Verschnitt?


Grüße
Erik

[FlashBurn]

Nein, ich muss das bestimmt nicht tun, Du musst das tun.

Ahhhh, mit Du meinte ich ein OS auf einer "normalen" Architketur (also keine Segmente und eine MMU)

Und was ist mit Rekursion? Man kann nicht immer zuverlässig vorhersagen wie oft rekursiert wird.

Rekursion habe ich natürlich nicht beachtet, aber ganz ehrlich, bei nem Baum (als Bsp.) werde ich die maximale Rekursionstiefe kennen und wenn ich mal davon ausgehe, das du 4Byte Adresse und 3 Parameter mit jeweils 4Byte und 4 lokale Vriablen mit jeweils 4Byte hast, dann kannst du bei nem Stack von 512KB 16384 Rekursionen durchführen.
Bei so einer Anzahl würde ich dann schon überlegen ob ein anderer Algo nicht performanter ist.

Du willst Deine Slabs nur auf 2er-Potenzen auslegen? Das gibt aber eine fette Speicherverschwendung! Was ist wenn ich 1048576 Objekte mit 36 Bytes brauche, hab ich dann 28MB Verschnitt?

Das ist, so weit ich schonmal Code gesehen habe, die gängige Praxis. Bei deinem Bsp wäre z.B. ein SlabAllocator besser geeignet als ein allgemeines malloc().
Denn ich behaupte mal das du bei dem Bsp. jede malloc() Implementation in den "Wahnsinn" treibst, da wird dein Speicher ordentlich fragmentiert und du wirst auch nen sehr schönen Verschnitt haben.

[erik.vikinger]

Hallo,

mit Du meinte ich ein OS auf einer "normalen" Architketur

Definiere Bitte "normal"!

bei nem Baum (als Bsp.) werde ich die maximale Rekursionstiefe kennen

Es werden nicht nur Bäume per Rekusion verarbeitet, wimre gibt es auch einige mathematische Algorithmen die sich per Rekursion sehr einfach und effizient implementieren lassen.

wenn ich mal davon ausgehe, das du 4Byte Adresse und 3 Parameter mit jeweils 4Byte und 4 lokale Vriablen mit jeweils 4Byte hast

Und was ist mit den gesicherten Registern? Klar, bei ner statischen Funktion kann der Compiler da ziemlich tricksen um einiges einzusparen aber grundsätzlich sollte man sowas nicht außer acht lassen.

Bei so einer Anzahl würde ich dann schon überlegen ob ein anderer Algo nicht performanter ist.

Es soll aber wirklich Probleme geben die sich mit Rekursion am einfachsten und effizientesten lösen lassen.

Was ist wenn ich 1048576 Objekte mit 36 Bytes brauche, hab ich dann 28MB Verschnitt?

Das ist, so weit ich schonmal Code gesehen habe, die gängige Praxis.

Krass! Ich war mir nie so ganz sicher wie viele Segmente ich für den Heap (im User-Mode) benutzen sollte. Nur die 2er-Potenzen erschien mir einfach zu extrem verschwenderisch, bis zu knapp 50% Verschnitt empfinde ich einfach als unangemessen. Doppelt so viele Segmente, die dann im Abstand von Wurzel aus 2 benutzt werden, haben auch noch bis zu knapp 25% Verschnitt. Wenn ich unter 2% Verschnitt haben will dann muss ich mindestens 32 mal so viele Segmente benutzen wie ich Bits hab und das wäre schon eine ganze Menge von dehnen wohl etliche leer bleiben würden (und damit erst gar nicht erstellt werden müssten).

Bei deinem Bsp wäre z.B. ein SlabAllocator besser geeignet als ein allgemeines malloc().

Das würde ich stark bezweifeln, ein ganz simples malloc hat fast gar keinen Verschnitt außer das es zu jedem Objekt eine feste Anzahl an Bytes für die Verwaltung benötigt.


@All: Wie viel Verschnitt (inklusive der Verwaltungsinformationen) ist den für den User-Mode-Heap akzeptabel?


Grüße
Erik

[FlashBurn]

Definiere Bitte "normal"!

Hatte ich doch dahinter geschrieben, eine MMU und keine Segmente, halt FlatMemory mit Paging.

Es soll aber wirklich Probleme geben die sich mit Rekursion am einfachsten und effizientesten lösen lassen.

Ich behaupte mal das man jeden Algo in einen Iterativen Umschreiben kann (ja der Aufwand wird sich bei vielen Sachen wahrscheinlich nicht lohnen) oder man Rekursion iterativ simulieren.
Der eigentliche Punkt ist doch, du weißt wenn du Rekursion nimmst in welche Richtung das geht und wenn du mit 1MB Stack nicht hinkommst dann musst du deinen Code halt anpassen (z.B. in dem du nen Thread erstellst der nen größeren Stack hat).

Das würde ich stark bezweifeln, ein ganz simples malloc hat fast gar keinen Verschnitt außer das es zu jedem Objekt eine feste Anzahl an Bytes für die Verwaltung benötigt.

Das Problem ist, wenn du diese kleinen Anfragen (36Byte) hintereinander machst, ist es viel sinnvoller einmal viel Speicher zu allokieren, machst du die nicht hintereinander, fragmentiert dein Heap irgendwann so stark das du oft irgendwelche 36Byte Löcher hast die du nicht mehr nutzen kannst.
Denn genau das ist doch das Problem bei nem ganz einfachen malloc(), entweder der Speicher ist so fragmentiert das du dir um den Verschnitt keine Sorgen mehr machen musst, weil die Löcher genug Probleme machen oder du hast halt viel Verschnitt (aber nen schnelles malloc()) oder dein malloc() ist zu langsam und skaliert nicht.

Drehen wir den Spieß doch mal um. Hast du denn eine Idee wie man ein malloc() implementieren kann so dass man möglichst wenig Verschnitt hat, möglichst wenig Speicherverbrauch (die Verwaltung) und möglichst schnell ist und skalieren soll das ganz auch noch. Viel Spaß

Edit::

Wenn wir mal deine Slabs mit 512KB nehmen, da passen ja 14563 Objekte mit einer Größe von 36Byte rein und wenn ich jetzt mal den average-case nehme (auch der ist nur einfach so gewählt) wo ich 100 Elemente brauche, dann hast du mit deinen goßen Slabs einen Verschnitt von 99,31% das nenne ich mal Verschwendung

Was ich damit sagen will ist einfach nur, das man sich bei einem Allocator halt auf nen guten Mix aller Nachteile einlassen muss oder man weiß ziemlich genau was für ein Speicherverbrauch das Programm hat und kann dann optimieren.

[Svenska]

Einmal sollte sich eine Automatik durchaus zur Laufzeit konfigurieren lassen

Und wer soll das konfigurieren? Meine Oma konfiguriert bestimmt nicht die Mapping-Optionen fürs Paging.

Darum bringt das System eine sinnvolle Automatik mit. Die brauchst du ohnehin überall (auch die Frage, wie lange du wartest, bis du Anwendungen von einem überlasteten Core auf einen leeren Core umziehst, weil dir die Cache-Inhalte verlorengehen... wie lange du verzögertes Schreiben auf die Festplatte erlaubst, bis du die Buffer zwangsweise wegschreibst... wie groß deine Zeitscheiben sind...). Das sind alles Automatiken mit sinnvollen Standardwerten, die überall hinreichend gut, wenn auch nicht optimal performen.

Ich bleibe bei der Meinung das der Programmierer einer bestimmten Applikation noch am besten abschätzen kann was für sein Programm optimal wäre und was zumindest noch akzeptabel ist und dann eben das OS zwingt wenigstens das akzeptable einzuhalten und gleichzeitig bittet das Optimum zu versuchen.

Darum soll man die Automatik zur Laufzeit konfigurieren und mit Flags für einzelne Aktionen überschreiben können.

Und der zusätzliche Syscall kostet bald mehr als die Optimierung überhaupt hätte bringen können? Was ist wenn es um eine kleine Aktion geht die aber sehr oft ausgeführt wird?

Eine sinnvolle Automatik macht kleine, häufige Aktionen schnell und seltene, große Aktionen langsam, wenn es einen Kompromiss geben muss. Außerdem sind Prozesse, die extrem von solchen Dingen profitieren müssen, meist die Hauptkomponenten eines Systems - einen Webserver, der 99% seiner Zeit nichts tut, werde ich nicht stundenlang auf Durchsatz optimieren - und dann kann man halt das Standardverhalten der Anwendung angepasst zur Laufzeit ändern.

Ich frage ja auch nicht im Supermarkt nach Vollmilch und kriege nur fettfreie Milch. Da kommt dann erstmal ein "gibts nicht"

Sicher, aber ein guter Verkäufer wird Dir noch im selben Atemzug die fettfreie Milch empfehlen.

Und mir die Möglichkeit einer Entscheidung geben.

Wenn ich kein Flag angebe, dann ist das deine kann-Entscheidung (die von einer Automatik gefällt wird).

Automatik allein reicht aber oft nicht um eine gute Entscheidung zu treffen, oft ist es eben sinnvoll der Automatik wenigstens einen Hinweis zu geben.

Den sie entweder ignoriert (dann hätte ich den Hinweis nicht gebraucht) oder umsetzt (dann hätte ich es auch erzwingen können). Naja, ich sehe Computer als Dinge an, die tun was man ihnen sagt, nicht mehr und nicht weniger. Und wenn ich ihm sage "fahr da lang", dann möchte ich auch exakt diesen Weg haben. Wenn der Fahrlehrer mir einen ungültigen Weg vorgibt (Einbahnstraße), dann muss ich ihn ablehnen und mir einen neuen Weg geben lassen. Es ist nicht vorgesehen, dass ich mir selbstständig einen neuen Weg suche.

Das ist einer der Gründe warum root bei der Auswahl der Programme die er startet etwas mehr Sorgfalt walten lassen muss.

Durchaus richtig, allerdings ist das für ein normales OS meiner Meinung nach nicht ausreichend. Es sei denn, du hast zwei Systemadministrator-Accounts, von denen "toor" weniger Grenzen gesetzt sind (Treiber, Services) und "root" garkeine Grenzen hat.

Das umzusetzen ist aber wesentlich mehr Aufwand.

Ich bin aber trotzdem der Meinung das 75% für den nichtauslagerbaren Speicher eine gute Obergrenze ist bei der dann der VMM erst mal Schluss macht weiteren Speicher an Prozesse (egal ob root oder nicht) zu vergeben sondern nur noch für den Kernel selber was hergibt. Mehr als 20% nichtauslagerbaren Speicher sollte es in einem normalen System eigentlich nicht geben.

Ist eine gute Faustregel, sollte aber zusätzlich noch abhängig von vorhandenen RAM sein. Etwas in der Art "max(RAMSIZE*0.75 || RAMSIZE-200M)", aber das sind Details.

machst du es wie Microsoft und erweiterst deine API um neue Funktionen, fasst deine bereits vorhandenen aber nie wieder an

Also es gibt in der inoffiziellen WIN-API durchaus immer wieder Änderungen, manchmal sogar von einem SP zum nächsten.

Richtig, diese API ist aber nicht zu verwenden und wenn du es tust, bist du selbst schuld.

Die undokumentierte Windows-API entspricht den OS-Services von FlashBurn. Man kann sie als Anwendung benutzen, sollte sie aber in Libraries wegabstrahieren und dann diese Libraries benutzen.

Es soll aber wirklich Probleme geben die sich mit Rekursion am einfachsten und effizientesten lösen lassen.

Ich behaupte mal das man jeden Algo in einen Iterativen Umschreiben kann (ja der Aufwand wird sich bei vielen Sachen wahrscheinlich nicht lohnen) oder man Rekursion iterativ simulieren.

QuickSort? Ist ein rekursives Verfahren, für so ziemlich jeden Anwendungsfall optimal. Die Rekursionstiefe hängt vom Sortierzustand der Datenbasis ab.

Der eigentliche Punkt ist doch, du weißt wenn du Rekursion nimmst in welche Richtung das geht und wenn du mit 1MB Stack nicht hinkommst dann musst du deinen Code halt anpassen (z.B. in dem du nen Thread erstellst der nen größeren Stack hat).

Richtig. Lässt sich wieder über ein Flag lösen. Das OS erstellt z.B. immer 1MB Stack, wenn deine Anwendung extensiv Stackverbrauch betreibt, muss sie einen eigenen Thread mit mehr erstellen.

Der Linux-Kernelstack hat übrigens 8 KB. In der Konfiguration kann man auch auf 4 KB umstellen und gucken, welche Treiber damit nicht auskommen, damit diese gefixt werden können.

Drehen wir den Spieß doch mal um. Hast du denn eine Idee wie man ein malloc() implementieren kann so dass man möglichst wenig Verschnitt hat, möglichst wenig Speicherverbrauch (die Verwaltung) und möglichst schnell ist und skalieren soll das ganz auch noch. Viel Spaß

Da wären wir wieder bei meiner Aussage, dass Speicherverbrauch mal Rechenzeit eine Konstante ist. Du kannst eins gegen das andere eintauschen, musst aber einen Kompromiss finden.

Du optimierst extensiv für minimalen Speicherverbrauch (gcc -Os und entsprechende Algorithmen), Erik optimiert für hohe Ausführungsgeschwindigkeit (gcc -O3 und entsprechende Algorithmen). Beides zusammen geht nicht.

Gruß,
Svenska

[FlashBurn]

QuickSort? Ist ein rekursives Verfahren, für so ziemlich jeden Anwendungsfall optimal. Die Rekursionstiefe hängt vom Sortierzustand der Datenbasis ab.

Ich muss zugeben das ich mich schon eine Weile nicht mehr mit QuickSort beschäftigt habe. Ich bleibe aber dabei das man das weiß und somit einen größeren Stack "beantragen" kann.

Der Linux-Kernelstack hat übrigens 8 KB.

Meine Kernel-Threads bekommen auch nur 4KB Stack und damit hatte ich bisher keine Problem, aber bei mir wird da ja auch weniger gemacht.

Da wären wir wieder bei meiner Aussage, dass Speicherverbrauch mal Rechenzeit eine Konstante ist. Du kannst eins gegen das andere eintauschen, musst aber einen Kompromiss finden.

Glaube ich nicht. Denn es wird sich bestimmt irgendwann mal ein intelligenter Algo finden lassen, der alles ganz gut miteinander verreint. Bis dahin ist das natürlich richtig.

Du optimierst extensiv für minimalen Speicherverbrauch (gcc -Os und entsprechende Algorithmen), Erik optimiert für hohe Ausführungsgeschwindigkeit (gcc -O3 und entsprechende Algorithmen). Beides zusammen geht nicht.

Das stimmt so auch nicht. Also ich optimiere nicht extensiv für einen minimalen Speicherverbrauch, aber ich gehe auch nicht verschwenderisch mit dem Speicher um (ich habe einige Sachen die eher Geschwindigkeit als Speicherverbrauch bevorzugen).
Es gibt sogar nicht wenige Sachen wo ein -Os schnelleren Code erzeugt als einen -O3. Denn das Problem sind die Caches und wenn der Code zu groß wird (und die Caches voll sind und viel nachgeladen werden muss) kann es passieren das kleinerer Code (der "schneller" in die Caches passt) schneller abgearbeitet ist als eigentlich hoch optimierter Code (bestes Bsp. ist das unrollen einer Schleife).

[Svenska]

Hallo,

es gibt sicherlich verschiedene Algorithmen, aber es gibt für viele Problemstellungen mathematische Beweise über den minimalen Aufwand, den man treiben muss. Gedankenexperiment dazu ist, dass du ja Zwischenergebnisse entweder zwischenspeicherst (d.h. Speicher "verschwendest") oder für jeden Zwischenschritt neu ausrechnest (d.h. Rechenzeit "verschwendest") und das ist vom Algorithmus unabhängig.

Was den Unterschied zwischen "-O3" und "-Os" angeht, so findet das Loop-Unrolling auch nur begrenzt statt, z.B. 16x, ist aber auch abhängig von dem eingestellten Prozessor (und damit indirekt von der Cache-Größe der Prozessoren). Darum sind spezielle Optimierungen auch immer sehr spezifisch. Anderes Beispiel sind Intel Core2 gegen AMD Opteron, wo der Core2 ähnlich schnell ist, aber für die 64-Bit-Multiplikation die dreifache Zeit braucht. Im Endeffekt lohnt es sich dann, auf 32-Bit-Multiplikation (oder Addition, wenn das reicht) umzustellen.

Der Grundgedanke, dass RAM*CPU=const bei gegebener Optimierungarbeit gilt, bleibt.

Gruß,
Svenska