Thema: SLAB-Allocator als Basis fuer kmalloc?

[rizor]

Ach du grosser Gott... Das wird ja eine riesige Diskussion, bei der man nicht mal ein paar Stunden fehlen kann, da man ansonsten den Ueberblick verliert xD

Also sagen die 800 MB für den Kernel nur aus, dass deine Prozesse nicht viel Speicher benötigen und Windows somit mehr für sich nimmt.

Nein, die 800 MB sind der Verbrauch der 63 Prozesse selber, was der Kernel tatsächlich für sich verbraucht (ohne Caches und ohne Treiber usw.) sagt der Taskmanager nicht so deutlich.

Achso, dann habe ich dich falsch verstanden. Nicht so deutlich? Windows verheimlicht das doch komplett, oder? Mein NT Kernel (Win7) soll momentan angeblich nur 84kB verbrauchen, was ich aber fuer ein verdammt grosses Geruecht halte.
Das ist ja auch bekannt, dass Microsoft da die Werte etwas schoent.

Wenn man das statisch macht, kannst du Speicher sparen, da du davon ausgehst, dass derjenige, der den Kernel baut, weiß wie viel Kerne er verwendet. Du kannst dem Compiler ja sagen, dass dein System auf zwei CPUs gebaut werden soll. Wenn es nicht stimmt, ist der User des Kernels selber schuld. Im Prinzip genau so, wie es Linux macht. Natürlich hast du einen größeren Speicherverbrauch wenn du mehr Kerne angibst, aber warum solltest du das tun?

Ist das immer noch so? Ich meine, in Erinnerung zu haben, dass das zu ändern schon vor zwei, drei Jahren im Gespräch war. Du kannst auf jeden Fall davon ausgehen, dass das nicht so ist, weil es toll wäre, sondern eher weil es so schön einfach zu implementieren war. Auf kurz oder lang wird das also dynamisch werden.

Das kommt vermutlich auf das Subsystem an. Ich weiss, dass der Scheduler damit nicht mehr arbeitet. Die Funktionen des Schedulers fuer das Hotplugging sind mir schon haeufig genug auf die Fuesse gefallen.
Aber mir ist so, als wenn der Kernel das in manchen Systemen noch macht.

Ich möchte da auch so eine Art Defragmentierung des Speichers einbauen, dass bei SPeicherknappheit der Speicher umgelegt werden soll.

Du willst in einem Flat-Memory-System den Speicher defragmentieren? Da bin ich jetzt aber mal neugierig, wie?

Das habe ich noch nicht bis ins letzte Detail durchdacht, aber jeder Cache soll eine Funktion bieten, die defrag heisst und die der SLAB-Allocator aufrufen kann, sobald er vom OOM-Detector gerufen wird. Das Ganze soll dann so ablaufen, dass jeder Cache analysiert wird und geschaut wird, ob eine Defragmentierung (also die Erstellung komplett leerer Slabs) moeglich ist. Falls ihm ein Szenario einfaellt, ruft er defrag auf. Als Uebergabe ist es einmal das Objekt, das bewegt werden soll und dann die neue Position des Objekts. Nun versucht Defrag das zu organisieren (kennt die dahinter liegende Datenstruktur bereits). Falls die Datenstruktur eine Verknuepfung zu anderen hat, muss natuerlich die Gueltigkeit der Daten gewaehrleistet sein. Es kann auch sein, dass Defrag sagt, dass das nicht moeglich ist, dann hat der SLAB-Allocator pech gehabt.
Da es sich aber um den Kernel handelt, sollten alle teilnehmenden Komponenten ja durchaus kooperativ sein.
Also meine Defragmentierung zwingt niemanden, sondern bittet hoeflich.
Frei nach dem Motto: "Lieber SLAB-User, bitte versuche mal den Inhalt des Objekts in ein anderes Objekt zu legen und melde mir das Resultat." Wenn das geklappt hat, kann der SLAB-Allocator frei gewordene SLABs sofort an die virtuelle und damit an die physische Speicherverwaltung weiterreichen. Das soll natuerlich der letzte Ausweg sein. So eine Art alles oder nichts. Wenn der SLAB-Allocator die Defrag-Methoden aufruft, ist die Wahrscheinlichkeit sehr hoch, dass es bei fehlgeschlagenen Defragmentierungen zu einem OOM kommt.

Und ja, irgendwann mal moechte ich CPU-Hotplugging unterstuetzen. Ist aber sehr weit hinten. Bis dahin koennen das die x86 mit Sicherheit auch, falls sie es nciht sogar schon koennen. Linux unterstuetzt das zumindest unter den x86ern.

Wenn du dein Betriebssystem auf 640K optimierst, dann wird es auf großen Maschinen nicht optimal laufen. Das solltest du bedenken - hat dein Ziel viel RAM, solltest du ihn auch nutzen.

Auf den ersten Blick hast du natuerlich recht, aber was bringt dir ein Kernel der viel Speicher BRAUCHT und nicht mit weniger umgehen kann. Das bringt dir nichts, sobald du Anwendungen hast, die viel Speicher brauchen (berechtigter Weise).
Ich bin der Meinung, dass ein Kernel jedes freie Byte verwenden sollte, aber nur wenn es kein anderer braucht. Das macht ein modernes OS aus. Ich will meinen Kernel auch so schreiben, dass er so viel wie moeglich an Daten Cached, diese aber auch in "Rekordzeit" wegwerfen kann, damit Anwendungen den Speicher bekommen koennen. Also im Prinzip eine Art Weak-Malloc im Kernel.
Ich bin mir nur noch nicht sicher, ob es wirklich sinnvoll ist ein Weak-Malloc zu implementieren oder ob man nicht lieber die Subsysteme um Speicher bitten soll.
Natuerlich braucht ein OS ein Mindestmass an Speicher (keine Frage), aber das sollte in meinen Augen im kB-Bereich (max. 64 oder so) liegen. Dadurch wird das gesamte System natuerlich extrem langsam, aber es ist immer noch besser als ein OOM-Fehler, weil der Kernel meint, dass er auf kein Byte Speicher verzichten kann, das er sich reserviert hat.

[rizor]

Da der Quote-Button nicht mehr wollte, gibt es jetzt halt einen Doppel-Post...

Hallo,

Würde man bei deinem Auto-Beispiel so konsequent argumentieren wie du, dann hätten wir keine Autobahnen aus Straßen, sondern aus Schienen (...)

Da kann ich dir nicht ganz folgen. Zumal es mir darum ging, wenn wir (und das gilt wahrscheinlich für fast alle Probleme) keinen Zwang zu Effizienzverbesserungen bekommen, dann belassen wir es dabei.

Schienen haben wesentlich weniger Gleitreibung und sind daher effizienter für den Transport. Dennoch wird Transport im großen Stil auf der Straße durchgeführt.

Das erinnert mich irgendwie an die Aepfel und die Birnen...
Ein alter Lehrer meinte mal: Nicht alles was hinkt, ist ein Vergleich.

Wenn du noch mehr Speicher sparen möchtest, dann verwaltest du die IDs garnicht zentral, sparst dir also die Datenstruktur komplett, und iterierst bei jeder ID-Anfrage durch sämtliche vorhandenen Objekte. Das ist wesentlich langsamer, kostet aber garkeinen Speicher.

Ich will ja nicht so wenig Speicher wie nur äußerst möglich verbrauchen, sondern so wenig wie mit der Leistung zu vereinbaren und da ist viel möglich, wenn man die richtigen Algos nutzt.

Merkste was? Das ist eine Kompromisslösung. Du kannst den Speicherverbrauch noch weiter auf Kosten der Performance reduzieren. Das ergibt sich aus meiner These: Du kannst beide gegeneinander eintauschen. Vom Verhältnis ist keine Rede.

Das hat doch auch nie jemand bestritten, oder?
Natuerlich musst du immer einen Komprimiss finden, aber ich finde es auch nicht sinnvoll, wenn du 10 % mehr Speicher brauchst, damit du 1-2 % mehr Performance erreichst. Das ist mir der Zeitgewinn nicht wert, da mein Kernel auch auf Systemen mit wenig Speicher irgendwann mal laufen soll (z.B. MIPS und die ganzen Konsorten)

Ich möchte das mein OS auch mit wenig Speicher läuft, [...] weil dann z.B. weniger ausgelagert werden muss und sowas.

Also doch Windows 95 bei 4 MB RAM. Es geht, ist aber nicht benutzbar.

Gruß,
Svenska

Gewagte These. Wer bei Win95 von einem modernen OS (nach heutigen Massstaeben) spricht, gehoert gesteinigt .
Es kommt ganz klar auf das Einsatzgebiet des OSes an. Daran wird Microsoft mit Sicherheit hart gearbeitet haben oder es noch tun, da sie ja mit Win8 auch ARM unterstuetzen wollen. Wenn sie da dann mit mindestens einem GB RAM ankommen, erhalten sie eher Mitleid oder Spott als wirkliche Partner.
Wenn du einen Kernel nur auf x86 und Nachfolger laufen lassen willst, kannst du natuerlich mit Speicher um dich schmeissen, da es bestimmt niemanden mehr gibt, der weniger als ein oder zwei GB Speicher verwendet.

[Svenska]

Von einem "modernen" OS war nicht die Rede. Und man kann auch das "OS" noch diskutieren, tu ich aber nicht.

Du kannst auch ein normales Windows extrem klein konfigurieren, siehe beispielsweise Windows XP embedded. Jedes bessere Android-Gerät hat inzwischen 512 MB RAM verbaut (gut, meins hat nur 256 MB - dafür hat es 64 MB Swap im internen Flash). Ein Netbook mit Windows 8 und ARM wird mindestens 1 GB RAM verbaut haben, vielleicht sogar 2 GB; der Einsatzzweck ist ein anderer. Ich bezweifle, dass es Häme hagelt, wenn Win8 sinnvoll nur ab 1 GB aufwärts läuft (aber auf der Verpackung 512 MB steht).

Auf den ersten Blick hast du natuerlich recht, aber was bringt dir ein Kernel der viel Speicher BRAUCHT und nicht mit weniger umgehen kann. Das bringt dir nichts, sobald du Anwendungen hast, die viel Speicher brauchen (berechtigter Weise).

Wenn die Anwendungen trotzdem genug Speicher haben, interessiert es mich nicht weiter (geht). Brauchen die Anwendungen dagegen richtig viel Speicher, interessiert es mich auch nicht mehr (dann geht es ohnehin nicht). Der Bereich dazwischen ist relativ klein (und kann teilweise mit Swap abgefangen werden).

Wenn der Kernel viel Speicher braucht, kannst du eh nichts dagegen machen. Interessant ist die Frage, wieviel Speicher der Kernel nicht braucht, aber gerne hat (Caches mal ausgenommen). Wenn der Kernel inklusive alles 10 MB braucht und 20 MB nimmt, dann kann das angemessen sein, das hängt vom Kernel ab. Ein paar KB interessieren da nicht.

Der meiste RAM geht in den Hardwaretreibern und Anwendungen verloren, nicht im Kernel. Also sehe ich das Optimierungspotential eher dort - auch, wenn das OS-Dever nicht hören wollen.

Ich will meinen Kernel auch so schreiben, dass er so viel wie moeglich an Daten Cached, diese aber auch in "Rekordzeit" wegwerfen kann, damit Anwendungen den Speicher bekommen koennen. Also im Prinzip eine Art Weak-Malloc im Kernel.

Ähnlich wie Plattencache. Finde ich sinnvoll.

Natuerlich braucht ein OS ein Mindestmass an Speicher (keine Frage), aber das sollte in meinen Augen im kB-Bereich (max. 64 oder so) liegen. Dadurch wird das gesamte System natuerlich extrem langsam, aber es ist immer noch besser als ein OOM-Fehler, weil der Kernel meint, dass er auf kein Byte Speicher verzichten kann, das er sich reserviert hat.

Dann riskierst du durch amoklaufende Prozesse einen Denial-of-Service, statt einen kontrollierten Absturz. Es ist in meinen Augen nicht sinnvoll, für jeden potentiellen Fehler eine Fallbacklösung zu haben; ein Ende mit Schrecken ist in meinen Augen sinnvoller.

[erik.vikinger]

Hallo,

Ich sags mal so, ob du nun alles in einer Liste hast, die sortiert ist und dir trotzdem den Anfang der vollen Elemente, den Anfang der Elemente mit mind. einem freien Objekt und den Anfang der komplett freien Element merkst oder ob du 3 Listen hast, sollte nun wirklich egal sein.

Ich habe aber nur 2 Pointer in die eine Liste, für die ganz vollen Blöcke benötige ich keinen Pointer (wenn eines der Objekte dort freigegeben werden soll dann hat free ja einen passenden Pointer und ansonsten muss ich die vollen SLAB-Blöcke doch nicht anfassen).

Was mir aber gefällt (im Hinblick auf den Speicherverbrauch) ist, dass die Liste der Anzahl der freien Objekte nach sortiert ist.

Der Hintergedanke dazu ist nicht primär der Speicherverbrauch sondern eher das ich damit versuchen will möglichst wenige nicht ganz volle Blöcke zu haben um insgesamt möglichst wenige SLAB-Blöcke pro Objektgröße zu benötigen. Klar hat das auch positive Auswirkungen auf den Gesamtspeicherverbrauch (weil ich versuche den Verschnitt zu minimieren) aber es geht mir dabei auch um Effizienz beim Allozieren (deswegen möchte ich diese Kette sortiert haben).

Mal was anderes, du sprichst zwar ständig von malloc/free, aber wenn ich dein Konzept richtig verstanden habe, dann hast du die doch gar nicht, sondern nur nen Slab-Allocator, wo du auch noch für jedes Objekt ne andere Funktion aufrufst.

Sehr gut beobachtet. Ja ich will in meinem Micro-Kernel nur einen SLAB-Allocator haben und das sein Interface kmalloc/kmfree heißt ist eher eine nostalgische Entscheidung als rational begründet. Zumindest liefert mir dieses System den Kernel-Heap. Ob ich bei beiden Funktionen ein Parameter hab das mir den Gewünschten Objekttyp angibt (ist kein Integer mit der Größe sondern ein enum mit dem Typ, das enum lässt sich effizienter mit einem switch verarbeiten) oder ob ich dieses Funktionspärchen gleich mehrfach habe (für jeden Objekttyp eines) und dafür immer ein Parameter spare hab ich noch nicht endgültig entschieden aber ich tendiere momentan schon eher zur zweiten Lösung. Die zweite Lösung produziert zwar insgesamt etwas mehr Code weil ja einiges mehrfach vorhanden ist aber dafür sind die Funktionen an sich deutlich kleiner und schneller weil die SLAB-Parameter als Konstanten direkt in den Befehlen mit drin sind und nicht erst aus dem Speicher geholt werden müssen.

Damit wollte ich eigentlich nur ausdrücken, da ich ja die Objektgröße für SlabDesc dynamisch beim Initialisieren festlege, ändert auch die Tatsache, das ich die CPU Anzahl zur Bootzeit kenne, nichts daran.

Ah, jetzt begreife ich was Du meinst. Du möchtest also alle SLAB-Parameter (wie z.B. auch die Größe der SLAB-Blöcke und damit der Anzahl an Objekten pro Block) erst beim booten festlegen damit Du da möglichst ein Optimum aus verfügbaren RAM und bestmöglicher Performance raus holen kannst? Hm, ist eine interessante Idee aber wäre mir persönlich viel zu Aufwendig, für Systeme mit weniger als 2 GB RAM muss ich mein OS sowieso nicht planen von daher habe ich mich bei den 512 kB SLAB-Block-Größe an anderen Kriterien orientiert.

Was man vllt auch nochmal betonen sollte, du hast ja deine Segment

Nein, nicht im Kernel, der arbeitet direkt und flach auf dem physischen Speicher. Segmente habe ich eigentlich nur im User-Mode aber der Kernel hat auch die Möglichkeit über Segmente (und damit optional auch mit Paging) auf Speicher zuzugreifen.

kann nicht mal eben einen Block einer beliebigen Größe allozieren

Mein VMM kann auch nur mit Pages als kleinste Einheit umgehen, diese kleinen Datenstrukturen soll bei mir der Boot-Code direkt hinter dem Kernel "allozieren" und die dann ermittelte Endadresse auf die nächste Page-Grenze aufrunden und das als Anfangswert des linearen Speichers dem VMM geben so das der dann den restlichen Speicher verwaltet. Objekte mit beliebiger Größe kann mein Kernel auch nicht zur Laufzeit allozieren sondern nur während des Bootens (also während die Lebendgeburt vorbereitet wird). Ich denke das ich damit genug Freiheiten hab, da ich ja während der Laufzeit keinen Bedarf mehr an beliebigen Objektgrößen habe.

Jetzt wird es nämlich interessant. Wie gibst du die dann zuück? Machst du aus den Objekten eine Liste? Wie löst du es, dass du ja auch jedes Mal nachgucken musst, ob überhaupt noch ein freies Objekt in dem Cache ist?

Wie ich das im Deteil lösen möchte hab ich mir noch nicht überlegt, das wird sich dann beim programmieren ergeben, aber ich könnte mir vorstellen da ich ja immer ganze Magazine befüllen/leeren muss das ich einfach die Adresse eines Magazins als Parameter mitgebe und die Funktion intern das mit ner Schleife abarbeitet (ein Magazin ist ja nur ein simples Array mit bekannter Anzahl an Pointern). Dieses Interne Interface, zwischen den CPU-lokalen Magazin-Mechanismen und dem eigentlichen SLAB-Allocator, ist dann auch nicht mehr öffentlich für den restlichen Code des Kernels. Der Kernel sieht immer noch nur das kmalloc/kmfree-Pärchen (das auch immer noch die selbe API und ABI bietet) und ist glücklich. Eine Möglichkeit an den CPU-lokalen Caches dran vorbei zu arbeiten möchte ich nicht schaffen aber wahrscheinlich werde ich diesen Mechanismus nicht für alle Objektgrößen aktivieren. Für das Erstellen von Threads möchte ich ja einen eigenen Cache-Mechanismus haben in dem dann nicht nur der Thread-Descriptor (der vom SLAB-Allocator kommt) sondern auch immer ein zugehöriges Stack-Segment (das vom VMM kommt) gemeinsam verwalten möchte, das Erstellen/Löschen von Threads ist ja für die Performance meines IPC-Systems von entscheidender Bedeutung. Für die Prozess-Descriptoren werde ich wohl auch keine CPU-lokalen Caches benötigen da das nicht ganz so oft vorkommt.

In das Zeitalter wo es noch hieß "640 kB sind genug für alles" möchte ich aber definitiv auch nicht mehr zurück.

Schon alleine wegen der Herausforderung würde ich das gerne machen bzw. habe mich ja auch vor fast 10 Jahren noch damit befasst.

Hm, nein Danke, ich denke das meine derzeitige Herausforderung anspruchsvoll genug ist.

Stell dir vor du hast eine List mit 100 Objectcaches und alle haben nur zwei Objekte rausgegeben und jetzt gibst du genau beim ersten Objectcache der List ein Objekt frei und musst jetzt 99 Listeneinträge durchgehen nur um die Liste sortiert zu halten.

So eine Situation ist zwar äußerst unperformant aber auch extrem unwahrscheinlich. Das müsste man schon mit viel Aufwand absichtlich so hintricksen und da mein Kernel nur von mir programmiert wird kann ich da ja aufpassen. Dieses Szenario ist in etwa so praxisrelevant wie das mit nur jeder zweiten Pages belegt, ist zwar theoretisch möglich aber dürfte in der Realität faktisch nie auftreten.

Um das Problem zu umgehen würde ich insgesamt 4 Pointer für Objectcaches nutzen, 2 um eine doppelt verkettete Liste für alle Objectcaches mit der gleichen Anzahl freier Objekte zu machen und zwei um diese Listen miteinander zu verbinden.

Und was ist wenn von den 100 SLAB-Blöcken 20 zu 1/4 belegt, 20 zu 2/4 belegt, 20 zu 3/4 belegt und 40 ganz voll sind? Das Auslagern von Blöcken mit identischem Füllgrad in extra Listen halte ich für keine gute Idee. Ist IMHO viel zu Aufwändig, kostet ne Menge extra Pointer und dürfte in der Praxis einfach fast nie auftreten. Eben um solchen Situationen vorzubeugen möchte ich die Kette ja sortiert halten und das Allozieren immer bei den möglichst vollen SLAB-Blöcken beginnen.

Auch die freie Wirtschaft wird irgendwann lernen, dass alles immer schnell nichts bringt. Ganz aktuell, siehe Sony
Der Schaden ist oft höher wenn man etwas zu schnell veröffentlich als wenn man gründlich arbeitet!

Das möchte man annehmen, ja, aber die vergangenen Jahrzehnte zeigen uns das der (Image-)Schaden durch ein fehlerhaftes Produkt durchaus nicht allzu hoch ist. Redet heute noch jemand über den FDIV-Bug des Pentium? Klar hat der Intel etwas Geld (Rückrufaktion) und Ansehen (bei den professionellen/wissenschaftlichen Kunden) gekostet aber insgesamt hat Intel das ziemlich gut weggesteckt. In der freien Wirtschaft läuft das wie bei einer Rinderherde: es knallt irgendwo, alle Viecher gucken sich kurz um und dann wird munter weiter gegrast.

Ach du grosser Gott... Das wird ja eine riesige Diskussion, bei der man nicht mal ein paar Stunden fehlen kann, da man ansonsten den Ueberblick verliert xD

Wie wahr!

Frei nach dem Motto: "Lieber SLAB-User, bitte versuche mal den Inhalt des Objekts in ein anderes Objekt zu legen und melde mir das Resultat." Wenn das geklappt hat, kann der SLAB-Allocator frei gewordene SLABs sofort an die virtuelle und damit an die physische Speicherverwaltung weiterreichen. Das soll natuerlich der letzte Ausweg sein. So eine Art alles oder nichts. Wenn der SLAB-Allocator die Defrag-Methoden aufruft, ist die Wahrscheinlichkeit sehr hoch, dass es bei fehlgeschlagenen Defragmentierungen zu einem OOM kommt.

Na ob das was wird? Dafür müsstest Du bei allen Clients Deines SLAB-Allocators ja extra Code einbauen, mal von dem zusätzlichen Bug-Potential abgesehen wird das wohl schon mehr Speicher fressen als das freigeben von ein oder zwei SLAB-Blöcken bringen kann. Sorry, aber diese Idee halte ich nicht für zielführend.

Und ja, irgendwann mal moechte ich CPU-Hotplugging unterstuetzen. Ist aber sehr weit hinten. Bis dahin koennen das die x86 mit Sicherheit auch, falls sie es nciht sogar schon koennen. Linux unterstuetzt das zumindest unter den x86ern.

x86 kann CPU-Hotplugging schon seit vielen Jahren, wimre gab es sogar mal PentiumPro-Systeme die das können aber sowas hat für gewöhnlich nicht Otto-Normalverbraucher unter/auf seinem Schreibtisch zu stehen. CPU-Hotplugging gibt es eigentlich nur bei fetten und teuren Servern für Mission-Critical-Applicationen.

Ich bezweifle, dass es Häme hagelt, wenn Win8 sinnvoll nur ab 1 GB aufwärts läuft (aber auf der Verpackung 512 MB steht).

Sehe ich ganz genauso. Speicher ist heute so billig (und auch sparsam) das man davon problemlos zu viel einbauen kann damit er auch immer reicht. Ich denke bei ARM wird man momentan mit Hochdruck daran arbeiten endlich den Anschluss an die 64Bit-Welt zu schaffen (in der Hinsicht ist ARM der letzte Nachzügler) um noch mehr Speicher benutzen zu können. Ich vermute die Vielfalt bei den ARM-Befehlssätzen wird damit noch größer werden weil man ja vom kleinsten Embedded-Mikrocontroller bis zum fetten Server-Prozi alles unterstützen möchte (gerade das fette Ende fehlt ARM derzeit ja noch in der Produktpalette).


Grüße
Erik

[FlashBurn]

Merkste was? Das ist eine Kompromisslösung. Du kannst den Speicherverbrauch noch weiter auf Kosten der Performance reduzieren. Das ergibt sich aus meiner These: Du kannst beide gegeneinander eintauschen. Vom Verhältnis ist keine Rede.

Mir gefällt an deiner These nicht (was leider die meisten so sehen und auch lernen), das sie irgendwo sagt, das ein Algo der weniger Speicher verbraucht als ein anderer auch langsamer sein muss und das ist halt nicht der Fall.
Dass deine Theorie an den beiden Extremen korrekt ist, möchte ich nicht mal bezweifeln, aber in der Mitte ist es halt auch oft genug nicht so.

Also doch Windows 95 bei 4 MB RAM. Es geht, ist aber nicht benutzbar.

Stimmt wohl, war aber eigentlich auch mit 8MB noch unbenutzbar, aber so 16MB waren schon ganz gut damals. Was dazu ganz gut passt, gab es jemals eine Linux-Distribution die da mithalten konnte (soll jetzt nichts gegen Linux werden)? Denn ich erinnere mich noch recht gut, das KDE damals ganz schön Speicher wollte, damit man halbwegs damit arbeiten konnte.

Der meiste RAM geht in den Hardwaretreibern und Anwendungen verloren, nicht im Kernel. Also sehe ich das Optimierungspotential eher dort - auch, wenn das OS-Dever nicht hören wollen.

Das ändert aber nichts daran, das man auch im Kernel nicht verschwenderisch sein muss Aber ansonsten kann ich dir nur zustimmen. Allerdings beweisen die Konsolen immer das es auch anders gehen kann, da müssen die Programmierer zwar mal ihren Kopf benutzen, aber immerhin.

Du möchtest also alle SLAB-Parameter (wie z.B. auch die Größe der SLAB-Blöcke und damit der Anzahl an Objekten pro Block) erst beim booten festlegen damit Du da möglichst ein Optimum aus verfügbaren RAM und bestmöglicher Performance raus holen kannst? Hm, ist eine interessante Idee aber wäre mir persönlich viel zu Aufwendig

Naja, was heißt schon aufwendig Ich meine du hast ja auch ne Art Formel wie du die Anzahl der Objekte pro SLAB berechnest. Du lässt das deinen Compiler machen und ich berechne das einmal zur Laufzeit. Bekomme aber weniger Verschnitt bzw. die Speicherauslastung dürfte bei mir geringer sein.

Mein VMM kann auch nur mit Pages als kleinste Einheit umgehen, diese kleinen Datenstrukturen soll bei mir der Boot-Code direkt hinter dem Kernel "allozieren" und die dann ermittelte Endadresse auf die nächste Page-Grenze aufrunden und das als Anfangswert des linearen Speichers dem VMM geben so das der dann den restlichen Speicher verwaltet. Objekte mit beliebiger Größe kann mein Kernel auch nicht zur Laufzeit allozieren sondern nur während des Bootens (also während die Lebendgeburt vorbereitet wird).

Genau dieses "Verfahren" wende ich auch bei einiges Sachen an, aber für die Slabs wäre mir das einfach zu aufwendig

So eine Situation ist zwar äußerst unperformant aber auch extrem unwahrscheinlich. Das müsste man schon mit viel Aufwand absichtlich so hintricksen und da mein Kernel nur von mir programmiert wird kann ich da ja aufpassen.

Also ich behaupte mal das du da als Programmierer nicht wirklich Einfluss drauf hast. Das hängt ja z.B. davon ab wann die Programme gestartet und wann sie beendet werden und das ist ja mehr oder weniger zufällig.
Es gibt da so ein Bsp, wo genau dieser worst-case nicht so toll ist, ich sag nur DoS. Wimre wurden die IP-Adressen (?) unter Linux eine zeitlang in einem normalen Baum gespeichert und da war ein DoS ziemlich einfach, aber inzwischen speichern sie sowas in nem Red-Black-Tree (oder schon wieder was neues?) und dadurch wurde der DoS schwieriger.

Ich weiß gar nicht mehr was es damals unter Windows war, was mich immer geärgert hatte, ein Programm hat praktisch den ganzen Computer unbenutzbar gemacht.

Und was ist wenn von den 100 SLAB-Blöcken 20 zu 1/4 belegt, 20 zu 2/4 belegt, 20 zu 3/4 belegt und 40 ganz voll sind?

Ich sehe da gerade kein Problem. Zumal ich sowas schon woanders einsetze, weil es weniger Speicher verbraucht und schneller ist. Nämlich für meinen VMM, der alle freien Bereiche, einmal nach der Adresse sortiert und einmal nach der Größe und da fasse ich auch alle Bereiche mit der gleichen Größe zusammen und habe so nur einen Eintrag in meinem Baum.

Mir fällt spontan QNX als gutes Bsp für ein OS ein, welches wenig Speicher braucht und trotzdem benutzbar ist bzw. in bestimmten Bereichen sogar bevorzugt wird.

[erik.vikinger]

Hallo,

Naja, was heißt schon aufwendig Ich meine du hast ja auch ne Art Formel wie du die Anzahl der Objekte pro SLAB berechnest. Du lässt das deinen Compiler machen und ich berechne das einmal zur Laufzeit. Bekomme aber weniger Verschnitt bzw. die Speicherauslastung dürfte bei mir geringer sein.

Ich wollte dieses ausrechnen eigentlich in meinem Kopf machen und damit dann ein paar Defines füttern aber das dem Compiler zu überlassen ist natürlich auch ne gute Idee. Wie Du mit der selben Formel (die Du nur zu einem anderen Zeitpunkt rechnest) auf weniger Verschnitt kommen möchtest verstehe ich aber nicht. Der wesentliche Unterschied zwischen unseren Konzepten dürfte sein das ich mit 512 kB ziemlich große SLAB-Blöcke benutze und Du wohl eher kleinere Stücke nehmen möchtest um den anfänglichen Speicherverbrauch klein zu halten. Dafür wirst Du öfters die kostspielige Aktion des Hinzufügens eines weiteren SLAB-Block durchführen müssen als ich. Wenn wir beide von einem Objekttyp erst mal ein paar hunderttausend Stück alloziert haben dürfte sich der resultierenden Gesamtspeicherverbrauch (also inklusive Verschnitt durch die SLAB-Verwaltung usw.) kaum noch wesentlich unterschieden (außer das bei Deinen kleineren SLAB-Blöcken eventuell ein minimal größerer prozentualer Verschnitt ist). Und genau da kommen wir wieder zur eigentlichen Zielstellung für das OS. Ich möchte das mein OS auf einem System mit deutlich mehr als 1 GB Speicher und dicken Work-Loads ordentlich performt und Du möchtest eben das Dein OS auch auf Systemen mit wenig Speicher überhaupt angemessen benutzbar ist. Zwischen unseren Zielvorstellungen liegen mindestens 2 Zehnerpotenzen und demzufolge unterscheiden sich auch unsere Konzepte.

Mal eine andere Frage: wie möchtest Du eigentlich das Freigeben von komplett unbenutzten SLAB-Blöcken managen? Willst Du die sofort freigeben oder möchtest Du damit lieber etwas warten? Wenn Du sofort frei gibst kann es sehr schnell passieren das Du kurz darauf wieder einen SLAB-Block vom VMM holen musst da es ja möglich ist das der Speicherverbrauch nur kurzzeitig so niedrig war.
Ich schätze ich werde erst frei geben wenn mindestens 2 SLAB-Blöcke komplett leer sind oder mindestens noch mal die Anzahl an Objekten die in einen SLAB-Block passt über mehrere andere SLAB-Blöcke frei ist. Auch wenn ich pro Objektgröße nur mit einem einzigen SLAB-Block starte so denke ich das ich zur Laufzeit nie unter 3 SLAB-Blöcke kommen möchte (also bei nur noch 3 SLAB-Blöcken wird keiner mehr an den VMM zurück gegeben egal wie leer die auch sind). Der Grund dafür ist das bei mir das Initialisieren eines neuen SLAB-Blocks recht aufwendig ist, ich möchte das jeder SLAB-Block seine eigenen freien Objekte als Stack verwaltet und dazu muss ich in jedes Objekt einmal schreibend Zugreifen um eben eine einfach verkette Liste aufzusetzen. Ich denke das ich hier auf jeden Fall bereit bin etwas Speicherverschwendung in Kauf zu nehmen um dafür den Heap zu beschleunigen. Eventuell könnte man dieses Verhalten auch an die Menge des freien physischen Speichers ankoppeln. Wenn noch viel RAM frei ist warum sollte der Heap dann seine SLAB-Blöcke überhaupt zurück geben?

Genau dieses "Verfahren" wende ich auch bei einiges Sachen an, aber für die Slabs wäre mir das einfach zu aufwendig

Ich wende dieses Verfahren bei sehr vielen Dingen an, ich muss ne Menge an Speicher für den Kernel reservieren was ich nicht zur Compile-Zeit bestimmen kann. Auf meiner Architektur benötigt man für jede CPU einen individuellen Kernel-Stack (da mein Kernel ja prinzipiell nicht unterbrechbar ist reicht auch einer pro CPU), dazu kommen dann z.B. die Verwaltungsstrukturen für die HW-IRQs (was der IRQ-Controller maximal kann sehe ich ja auch erst beim booten) und eben auch die SLAB-Verwaltungsstrukturen. Den jeweils ersten SLAB-Block pro Objektgröße muss ich auch auf diese Weise "allozieren" da ja der VMM ohne den Heap nicht arbeiten kann (er soll ja für das Allozieren seiner Verwaltungsstrukturen kmalloc benutzen). Wenn die Speicherverwaltung dann soweit vorbereitet ist, das sie nun auch funktioniert, kann ich die normalen Funktionen des Kernels zum Anlegen der ersten 3 Prozesse benutzen (da z.B. auch der Scheduler den Heap benötigt um damit die Liste der runnable Threads aufzubauen).

Das hängt ja z.B. davon ab wann die Programme gestartet und wann sie beendet werden und das ist ja mehr oder weniger zufällig.

Klar ist das zufällig aber deswegen sortiere ich ja die SLAB-Blöcke um da ein möglichst günstiges Verhalten im Kernel zu haben. Und spätestens mit den CPU-lokalen Caches wird das System so stark entkoppelt das sich solche Situationen kaum noch herbeiführen lassen.

der alle freien Bereiche, einmal nach der Adresse sortiert und einmal nach der Größe und da fasse ich auch alle Bereiche mit der gleichen Größe zusammen und habe so nur einen Eintrag in meinem Baum.

Für den VMM ist das tatsächliche eine gute Idee, das muss ich mir auf jeden Fall notieren.

Mir fällt spontan QNX als gutes Bsp für ein OS ein, welches wenig Speicher braucht und trotzdem benutzbar ist bzw. in bestimmten Bereichen sogar bevorzugt wird.

QNX unterschiedet bei Syscall nach 2 Kategorien: die mit deterministischen Zeitverbrauch und die mit nicht vorhersehbaren Zeitverbrauch. Das Memory-Management fällt meines Wissens nach in die zweite Kategorie weswegen man üblicherweise versucht den gesamten Speicherbedarf einer Applikation beim Booten/Initialisieren zu allozieren und während der eigentlichen Laufzeit auf malloc/free möglichst verzichtet. Diese Strategie wird wimre in nahezu allen harten Real-Time-Applikationen benutzt. Auch unsere Memory-Management-Konzepte würden nicht wirklich für harte Echtzeit taugen. Eine generische Speicherverwaltung die immer O(1) arbeitet stelle ich mir persönlich unmöglich vor.


Grüße
Erik

[FlashBurn]

Wie Du mit der selben Formel (die Du nur zu einem anderen Zeitpunkt rechnest) auf weniger Verschnitt kommen möchtest verstehe ich aber nicht.

Da habe ich mich total falsch ausgedrückt, aber du hast es dann schon richtig verstanden. Ich werde bis zu einem gewissen Punkt weniger Speicher als du verbrauchen und ab dem dann mehr. Verschnitt könnte bei mir auch größer sein, aber nur wenn die Objekte nicht genau in einen Slab reinpassen.

wie möchtest Du eigentlich das Freigeben von komplett unbenutzten SLAB-Blöcken managen? Willst Du die sofort freigeben oder möchtest Du damit lieber etwas warten?

Das ist so ein Problem. Ich habe mir noch nichts konkretes überlegt, aber implementiert ist die Variante von Linux (ich denke doch mal das ich gelesen hatte, dass Linux das so macht) und zwar gibst du von dir (der Slab-Allocator) nie den Speicher wieder frei, sondern das wird immer von außen angestoßen. Sprich man müsste einen Thread laufen lassen, der immer mal wieder den Speicherstand kontrolliert und wenn er eine bestimmte Schwelle unterschreitet rufst du ne Funktion auf, wo durch alle Objekttypen gegangen wird und die freien Slabs freigegeben werden. Diese Strategie kann man sicherlich noch verfeinern und hier ist leider auch ein monolith klar im Vorteil. Denn das kann meiner Meinung nach nur im Kernel funktionieren oder würde es Sinn machen das ein Programm ne Art Callback beim Kernel registriert und der kann dann aufgerufen werden um Speicher zu bekommen?
Ansonsten wäre auch meine Idee gewesen, nur Slabs freizugeben, wenn eine bestimmte Anzahl freier Slabs vorhanden ist (das wird man wohl durch probieren rausfinden müssen, was sich dort anbietet).

Eine generische Speicherverwaltung die immer O(1) arbeitet stelle ich mir persönlich unmöglich vor.

Ich habe mir angewöhnt mit dem immer und dem nie eher vorsichtig umzugehen. Die Geschichte sollte uns da eines besseren belehren Die Menschen waren immer zu 100% überzeugt das gewisse Dinge unmöglichen sind und heute sind sie möglich.
Aber mit den momentan bekannten Algos hast du recht. Obwohl ich mir vorstellen könnte das es möglich ist, aber das wäre dann wohl ein sehr gutes Bsp. den ganzen Leuten mal zu zeigen das ein O(1) Algo langsamer sein kann als z.B. ein O(n) Algo (auf nem Computer mit endlichen Ressourcen).

[Svenska]

Merkste was? Das ist eine Kompromisslösung. Du kannst den Speicherverbrauch noch weiter auf Kosten der Performance reduzieren. Das ergibt sich aus meiner These: Du kannst beide gegeneinander eintauschen. Vom Verhältnis ist keine Rede.

Mir gefällt an deiner These nicht (was leider die meisten so sehen und auch lernen), das sie irgendwo sagt, das ein Algo der weniger Speicher verbraucht als ein anderer auch langsamer sein muss und das ist halt nicht der Fall.

Das stimmt nicht: Da steht nicht, dass kleinere Algorithmen langsamer sein müssen. Da steht was von können. Und davon, dass es potentiell immer noch andere Möglichkeiten gibt - du kannst ja die Grundidee ändern, dann werden die Algorithmen vielleicht sogar komplett überflüssig. Also "thinking outside the box".

Das ändert aber nichts daran, das man auch im Kernel nicht verschwenderisch sein muss

Definiere "verschwenderisch". In einem Serverbetriebssystem opfert man lieber 10% des RAMs für 2% der Performance, auf einem eingebetteten System macht man es eher umgekehrt. Es gibt halt keine Größe, die überall funktioniert.

Ich kenne einen Fall, da wurden in einen chronisch überlasteten Datenbankserver einfach 16 GB RAM nachgesteckt. Plötzlich lief fast die gesamte Datenbank aus dem RAM und das System war schnell. In der Größenordnung spielen selbst 64 MB Verschwendung im Kernel keine Rolle mehr.

Aber ansonsten kann ich dir nur zustimmen. Allerdings beweisen die Konsolen immer das es auch anders gehen kann, da müssen die Programmierer zwar mal ihren Kopf benutzen, aber immerhin.

Auf Konsolen gelten andere Gesetze, weil du nämlich eine Plattform hast, wo du jegliche Hardware kennst und damit optimal zuschneiden kannst. Das geht auf dem PC prinzipiell nicht. Wenn die Konsole 256 MB RAM hat, dann brauchst du keine Kompromisse suchen, damit es bei weniger RAM gerade noch so und bei mehr RAM noch viel besser geht.

Mir fällt spontan QNX als gutes Bsp für ein OS ein, welches wenig Speicher braucht und trotzdem benutzbar ist bzw. in bestimmten Bereichen sogar bevorzugt wird.

Mit QNX kenne ich mich nicht aus, aber in jeder Nische hast du ein gutes System, welches dort optimal läuft, woanders aber versagt.

Eine generische Speicherverwaltung die immer O(1) arbeitet stelle ich mir persönlich unmöglich vor.

Ich habe mir angewöhnt mit dem immer und dem nie eher vorsichtig umzugehen. Die Geschichte sollte uns da eines besseren belehren Die Menschen waren immer zu 100% überzeugt das gewisse Dinge unmöglichen sind und heute sind sie möglich.

Naja, du musst zwischen "unmöglich" und "unrealistisch" unterscheiden. Ich stimme Erik insofern zu, dass eine Speicherverwaltung, wie sie von heutigen Systemen benötigt wird, nicht in O(1) machbar ist.

mal zu zeigen das ein O(1) Algo langsamer sein kann als z.B. ein O(n) Algo (auf nem Computer mit endlichen Ressourcen).

Das eine ist Geschwindigkeit, das andere ist Skalierbarkeit. Du kannst wieder das eine gegen das andere eintauschen. Inzwischen bevorzugt man lieber skalierende und langsamerere Algorithmen als umgekehrt, sofern die Grundeinbuße nicht zu hoch ist.

Gruß,
Svenska

[FlashBurn]

Definiere "verschwenderisch". In einem Serverbetriebssystem opfert man lieber 10% des RAMs für 2% der Performance, auf einem eingebetteten System macht man es eher umgekehrt. Es gibt halt keine Größe, die überall funktioniert.

Also ja es ist richtig das es (leider?) keine Größe gibt die überall funktioniert. Allerdings ist das wahrscheinlich auch ein gutes Bsp. das man sich keinen Kopf macht, weil man keinen Zwang hat (bzw. ist es billiger mehr RAM zu kaufen als zu "denken"). Denn wäre es nicht möglich den RAM so stark zu vergrößern, würde man bestimmt versuchen nen anderen Algo/Datenstruktur zu nutzen und würde wahrscheinlich effizienter arbeiten, aber so erweitert man einfach den RAM und das Problem wird halt wieder in die Zukunft verschoben (woher kenne ich das nur ).

Auf Konsolen gelten andere Gesetze, weil du nämlich eine Plattform hast, wo du jegliche Hardware kennst und damit optimal zuschneiden kannst. Das geht auf dem PC prinzipiell nicht.

Naja, aber man könnte ja einen mind. RAM vorgeben (so wie es auch schon gemacht wird) und das ganz so gestalten das es nach oben hin (also mehr RAM) skaliert, aber das es auch mit dem mind. RAM gut funktioniert. Z.B. so dass man mit etwas mehr als dem Konsolen RAM arbeiten kann (weil das OS und sowas ja auch RAM braucht), aber wenn mehr RAM zur Verfügung steht kann man den nutzen. Allerdings sieht es ja anscheinend so aus, dass man auf dem PC immer von deutlich mehr RAM ausgeht und daher nicht so clever arbeiten muss.

Im Endeffekt kann man daraus ne philosophische Aussage drauß machen, ohne Zwang kein (oder besser kaum) Fortschritt!

[erik.vikinger]

Hallo,

Ich werde bis zu einem gewissen Punkt weniger Speicher als du verbrauchen und ab dem dann mehr.

Ganz genau. Du wirst aber für gewöhnlich auch den dickeren Prozessor haben als ich. Wenn ich mit meiner CPU alles richtig mache werde ich etwa das Niveau der untersten Pentiums erreichen und wenn ich mir richtig Mühe gebe vielleicht sogar das Niveau eines mittleren Pentium und wenn ich mir noch mehr Mühe gebe (und auch etwas Glück dazu kommt) eventuell das Niveau eines unteren PentiumPro. Dafür werde ich mit Sicherheit immer mindestens 2 GB RAM haben und dieser RAM wird auf meinem eigenen FPGA-Board etwa 400MHz-DDR2 mit mindestens 128Bit-Datenbusbreite sein, das heißt ich habe deutlich mehr RAM und auch deutlich schnelleren RAM (sowohl mehr Speicherbandbreite als auch kürzere Latenzzeiten) als ein typisches Pentium- oder PentiumPro-System zur Verfügung und genau deswegen werde ich diesen RAM auch einsetzen wenn ich dafür mehr Performance erreichen kann. Ist eben alles eine Frage der Rahmenbedingungen und Zielsetzungen.

Verschnitt könnte bei mir auch größer sein, aber nur wenn die Objekte nicht genau in einen Slab reinpassen.

Selbst wenn die Objekte genau in den SLAB-Block passen wirst Du mehr Verschnitt haben da Du ja mehr SLAB-Blöcke brauchst und jeder Block seinen Header hat.

und zwar gibst du von dir (der Slab-Allocator) nie den Speicher wieder frei, sondern das wird immer von außen angestoßen.

Hm, auch ne Variante. Solange noch genug physischer Speicher frei ist sehe ich für den Kernel-Heap auch keine Notwendigkeit da etwas her zu geben. Auf der anderen Seite geht dieser Speicher damit eventuell dem VFS-Cache o.ä. verloren. Ich hab zwar eine komfortable Möglichkeit in meinem Kernel mit der ich in regelmäßigen Abständen mal prüfen kann ob es sich lohnt ein paar SLAB-Blöcke frei zu geben aber von der Idee bin ich nicht so sehr angetan. Ich denke auch das dieses Konzept eher für einen Monolithen geeignet ist als für einen Micro-Kernel, das ist aber auch nur so ein Bauchgefühl und keine fundierte Analyse. Wenn Du also mal beides ausprobieren und uns dann das Ergebnis berichten möchtest wären wir alle sicher sehr Dankbar.

Ansonsten wäre auch meine Idee gewesen, nur Slabs freizugeben, wenn eine bestimmte Anzahl freier Slabs vorhanden ist (das wird man wohl durch probieren rausfinden müssen, was sich dort anbietet).

Diese Lösung ist IMHO auch recht billig zu bekommen, da man ja eh am Ende von free den Freie-Objekte-Zähler inkrementieren muss kann man den auch gleich mit einer Konstanten vergleichen um zu prüfen ob es sich überhaupt lohnt mal nachzusehen ob man etwas frei geben könnte. Diese Konstante sollte etwa das Doppelte von der Anzahl an Objekten pro SLAB-Block sein, würde ich jetzt mal so sagen aber genauer (falls das überhaupt genauer geht) wird man das auch nur mit Versuchen und Benchmarks ermitteln können.

Ich habe mir angewöhnt mit dem immer und dem nie eher vorsichtig umzugehen.

Deswegen hab ich ja "stelle .... vor" geschrieben. Wenn mir jemand einen Speicherverwaltungsalgorithmus zeigen kann der in O(1) arbeitet und die 1 auch wirklich konkurrenzfähig klein ist dann bin ich sofort überzeugt.
Natürlich passieren solche Quantensprünge immer mal wieder aber die sind trotzdem ziemlich selten. In der täglichen Praxis muss man eben meistens Kompromisse schließen, der Trade-Off aus Rechenleistung und Speicherverbrauch ist da nur ein Beispiel von vielen.

In einem Serverbetriebssystem opfert man lieber 10% des RAMs für 2% der Performance, auf einem eingebetteten System macht man es eher umgekehrt.

Wenn ich einem Vorgesetzten so eine Art von Problem erklärt hab hab ich auch schon oft die Gegenfrage "was kostet eigentlich der nächst größere Chip" bekommen. Man kann nicht nur Speicherverbrauch und CPU-Verbrauch gegeneinander eintauschen sondern auch beides gegen Geld. Und da auch die Man-Stunde des Programmierers Geld kostet (wenn er sich Mühe geben muss den Kompromiss aus Speicherverbrauch und CPU-Verbrauch in eine gute Balance zu bekommen) kann es eben sein das ein ökonomisch denkender Manager auch einfach mal die kosteneffizienteste Lösung nimmt.

Denn wäre es nicht möglich den RAM so stark zu vergrößern, würde man bestimmt versuchen nen anderen Algo/Datenstruktur zu nutzen und würde wahrscheinlich effizienter arbeiten, aber so erweitert man einfach den RAM und das Problem wird halt wieder in die Zukunft verschoben (woher kenne ich das nur ).

Wenn das Deine ehrliche Einstellung ist dann empfehle ich Dir einen C64. Der ist gut Dokumentiert und es gibt selbst heute noch eine treue Entwicklergemeinde die immer fähige Hände sucht. Ich hab auf dem C64 schon Dinge gesehen für die ein PC locker die hundertfache Rechenleistung des C64 brauchen würde wenn ich das implementieren müsste. Ich habe da noch ein paar Kontakte also wenn Du wirklich eine Herausforderung suchst dann bin ich Dir da gerne behilflich.

Naja, aber man könnte ja einen mind. RAM vorgeben (so wie es auch schon gemacht wird) und das ganz so gestalten das es nach oben hin (also mehr RAM) skaliert, aber das es auch mit dem mind. RAM gut funktioniert.

Das wird nur selten funktionieren. Die Fähigkeit zum Skalieren kostet etwas und dieser Preis kann dann wenn diese Fähigkeit nicht nutzbar ist (also bei der Standardausstattung) schon zu hoch sein.

Im Endeffekt kann man daraus ne philosophische Aussage drauß machen, ohne Zwang kein (oder besser kaum) Fortschritt!

Das kann ich ruhigen Gewissens unterschreiben.
Nicht umsonst heißt es "Not macht erfinderisch".


Grüße
Erik

[FlashBurn]

Du wirst aber für gewöhnlich auch den dickeren Prozessor haben als ich. Wenn ich mit meiner CPU alles richtig mache werde ich etwa das Niveau der untersten Pentiums erreichen

Ich kann den zwar durchaus haben, aber mein Ziel sind genau die Pentiums (und bei einigen Sachen brauche ich dann doch neuere Computer, wie z.B. den HPET) und davon habe ich auch einfach genug zum Testen.

Wenn das Deine ehrliche Einstellung ist dann empfehle ich Dir einen C64.

Auf der einen Seite sehr verlockend, aber auf der anderen muss ich sagen, wenn ich nur halb so viel Können hätte wie solche Demo-Programmierer, würde ich jetzt nicht noch immer studieren

Ich bin immer wieder hin und weg, wenn ich sehe was solche Leute aus der Hardware rausholen, aber dafür fehlt mir leider die nötige Kreativität und mein Mathe ist inzwischen so schlecht, das ich nicht mal mehr das Abitur schaffen würde

Das wird nur selten funktionieren. Die Fähigkeit zum Skalieren kostet etwas und dieser Preis kann dann wenn diese Fähigkeit nicht nutzbar ist (also bei der Standardausstattung) schon zu hoch sein.

Diese Aussage ist insofern interessant, da dass ich auch implezieren würde, das ein Spiel immer den gleichen Speicher belegt (wenn die gleichen Rahmenbedingungen geltern, außer dem RAM)?! Sprich in dem Sinne wäre es also das gleiche wie auf einer Konsole.

[erik.vikinger]

Hallo,

davon habe ich auch einfach genug zum Testen.

Aha, hast Du zufällig auch einen mehrfach PentiumPro in Deiner Sammlung?

Auf der einen Seite sehr verlockend, aber auf der anderen muss ich sagen, wenn ich nur halb so viel Können hätte wie solche Demo-Programmierer, würde ich jetzt nicht noch immer studieren

Ja, das ist sehr verlockend aber auch einigermaßen zeitintensiv. Vor über 10 Jahren hab ich an sowas mitprogrammiert aber meistens nur irgendwelche Low-Level-Sachen wie die Dekompressoren da die Demos ja oft mit 64 kB o.ä. aus kommen mussten (als Dateigröße, nicht als RAM-Belegung). Heute sind die Tage dieser Demos vorbei, einfach weil es gute 3D-Grafikkarten gibt. In heutigen Demos geht es nur noch darum die 3D-Daten für Direct-X oder OpenGL passend vorzubereiten und dann alles laufen zu lassen, für mich persönlich hat dieses Thema damit seinen Reiz verloren. Ich kenne übrigens einen der hat extra lange studiert eben weil er das kann, um dafür genügend Freizeit zu haben was neben einem Job nicht mehr so gut funktioniert.

Ich bin immer wieder hin und weg, wenn ich sehe was solche Leute aus der Hardware rausholen, aber dafür fehlt mir leider die nötige Kreativität

Das die Hardware oft mehr kann als die Konstrukteure sich bewusst sind gibt es nicht nur beim C64, als ich das erste mal auf meinem eigenen PC (damals ein 486 mit 80 MHz und einer ISA-GraKa mit 512 kB) 3D-Graphik in Echtfarben (die ISA-GraKa kann definitiv nur palettenbasierte Darstellung) gesehen hab war ich echt platt, wenn ich das nicht mit eigenen Augen gesehen hätte hätte ich es nicht geglaubt. Ich weiß bis heute nicht genau wie dieser Trick funktioniert.

und mein Mathe ist inzwischen so schlecht, das ich nicht mal mehr das Abitur schaffen würde

Also wenn Du Dein Mathe als so schlecht einstufst dann wirst Du auch im Job ernste Schwierigkeiten bekommen. Gerade in technischen Berufen (ich gehe jetzt mal davon aus das Du etwas mit Programmieren o.ä. machen möchtest) muss man in Mathe immer fit sein. Da ich selber nicht mal Abi hab musste ich in den vergangenen 10 Jahren immer mal wieder etwas für mich neues lernen und das geht zwar dank des Internets einigermaßen gut aber toll ist das auch nicht.

Diese Aussage ist insofern interessant, da dass ich auch implezieren würde, das ein Spiel immer den gleichen Speicher belegt (wenn die gleichen Rahmenbedingungen geltern, außer dem RAM)?! Sprich in dem Sinne wäre es also das gleiche wie auf einer Konsole.

Wenn Du die Compilerschalter mit in die Rahmenbedingungen einbeziehst könnte das tatsächlich zutreffen. Aber in den Spielen die für mehrere Plattformen parallel raus kommen werden sicher auch jeweils passende Versionen der 3D-Engine eingesetzt. Wimre gibt es die großen 3D-Engines in verschiedenen Ausführungen die zwar nach oben hin immer das selbe API haben aber intern an die entsprechende Plattform ganz genau angepasst sind. Also der zugrunde liegende Source-Code insgesamt (unter Einbeziehung aller Librarys) für ein und das selbe Spiel dürfte sich doch von Plattform zu Plattform erheblich unterscheiden. Auch an den Daten (Texturen usw.) wird es sicher erhebliche Unterschiede geben, während für die Konsolen 2 Auflösungen (TV + HDTV) reichen muss in der PC-Version sehr viel mehr drin sein (zuzüglich der erforderlichen Flexibilität im Code).


@rizor:
Wenn Du wirklich einen SLAB-Allocator als generische Heap-Implementierung benutzen möchtest (also alles was malloc liefert aus nem SLAB kommen soll) dann würde ich mir an Deiner Stelle noch mal die Größenstaffelung überlegen. Selbst eine Wurzel-2-Staffelung erzeugt immer noch einen enormen Verschnitt (bis zu 50%), wenigstens 16 Abstufungen pro Zweierpotenz (mit logarithmischen Abständen) würde ich schon machen. Auch solltest Du die Größe der Objekte die tatsächlich aus einem SLAB kommen sollen beschränken, einen 16MB-Puffer aus einem SLAB zu holen ist IMHO Quatsch. Wimre holt der Hoard Memory Allocator (eine Heap-Implementierung für den User-Space) für Objekte größer 256 kB auch direkt virtuellen Speicher vom OS.


Grüße
Erik

[FlashBurn]

Aha, hast Du zufällig auch einen mehrfach PentiumPro in Deiner Sammlung?

Jap, konnte auf dem bisher leider noch nicht testen (aber der läuft), da das eines der Boards ist, was bei meinen Eltern ist und da komme ich in letzter Zeit so selten hin.

Also wenn Du Dein Mathe als so schlecht einstufst dann wirst Du auch im Job ernste Schwierigkeiten bekommen.

Ich denke mal da wäre es sinnvoller nen neuen Thread im Off-Topic Forum aufzumachen. Was mich immer wundert ist, das ich genug Kommiltonen kenne, die zwar Mathe gut können, aber von Programmieren keine Ahnung haben bzw. kein "Gespür" dafür.

Wenn Du die Compilerschalter mit in die Rahmenbedingungen einbeziehst könnte das tatsächlich zutreffen.

Das überrascht mich dann doch ein wenig. Allerdings denke ich mal das man die Engines so programmiert, dass sie einen bestimmten Speicher benötigen und als mindest Angabe an RAM macht man dann soviel dass das OS nicht zuviel swappen muss.
Obwohl das eigentlich auch logisch ist, ich meine auf der Konsole musst du dich selbst drum kümmern, das nachgeladen werden muss und auf nem PC macht dass das OS für dich (das Swappen).

@rizor

Die Frage die ich mir stellen würde, warum brauchst du ein allgemeines malloc() in einem Mikrokernel (du schreibst doch einen?)?

[erik.vikinger]

Hallo,

Jap, konnte auf dem bisher leider noch nicht testen (aber der läuft), da das eines der Boards ist, was bei meinen Eltern ist und da komme ich in letzter Zeit so selten hin.

Ahh, wie viele CPUs mit welchem Takt und welcher L2-Cache-Größe und wie viel RAM von welchem Typ und Geschwindigkeit stecken denn da drin? Ich suche ja immer noch eine adäquate Herausforderung für meine CPU-Entwicklung, ich hab zwar hier nen K6 (der ja auch Out-of-Order-Execution usw. kann) denn ich auf eine passende Taktfrequenz runtertakten könnte aber der ist eben alleine auf seinem Board. Und ein aktueller Core-irgendwas oder Athlon wäre einfach kein fairer Vergleich.

Was mich immer wundert ist, das ich genug Kommiltonen kenne, die zwar Mathe gut können, aber von Programmieren keine Ahnung haben bzw. kein "Gespür" dafür.

Gerade dieses "Gespür" hat eben nichts mit mathematischer Intelligenz o.ä. zu tun. Ich persönlich betrachte es nicht als verwunderlich das viele Mathematiker und auch Physiker keine guten Programmierer sind, für die wurden ja extra Programmiersprachen wie Fortran erschaffen (nur leider lernt man damit auch nicht wirklich programmieren). Aber wenn dann sollten wir das wohl wirklich in einem extra Thead näher diskutieren.

Allerdings denke ich mal das man die Engines so programmiert ....

Auf einer Konsole wird eine komplett andere Implementierung der Engine eingesetzt als auf dem PC, nur das Interface zum eigentlichen Spiel ist identisch. Und auch im Spiel selber werden sicher einige Features bzw. Einstellmöglichkeiten per Compilerschalter abgeschalten bzw. beschnitten. Ich vermute mal das die Entwickler erst mal das Spiel generisch mit maximalen Features entwickeln und das dann das Ergebnis für die jeweilige Zielplattform zurechtgestutzt wird. Für den PC wird dieses Zurechtstutzen wohl sehr knapp ausfallen aber für die verschiedenen Konsolen wird wohl mindestens das Auswechseln der drunter liegenden Engine und das Ausdünnen der Textur-Daten anfallen (Dinge die sicher zum Großteil komplett automatisiert ablaufen, als Teil des Build-Prozesses).


Grüße
Erik

[FlashBurn]

Ahh, wie viele CPUs mit welchem Takt und welcher L2-Cache-Größe und wie viel RAM von welchem Typ und Geschwindigkeit stecken denn da drin?

Also aus dem Kopf kann ich dir sagen, das es (leider nur) ein Dual-Board ist mit 200MHz 512kbL2 und noch PS/2-RAM verwendet. Ich habe auch ein Board für eine PPro CPU mit SD-RAM, aber das habe ich noch nicht zum Laufen bekommen. Allerdings habe ich einige Dual-Pentium Boards und auch Pentium 2 Boards (auch die ersten, die mit 233-300MHz liefen). Wo dann schon SD-RAM eingesetzt wurde.

Das kann man dann ja immernoch sehen, ich ziehe bald um und da könnte ich eigentlich mal anfangen alles zu katalogisieren, weil ich inzwischen doch den Überblick verloren habe.

[FlashBurn]

So ich benutze jetzt mal den Thread für mein Problem.

Der Linux Slab-Allocator unterstützt ja das Konstruieren und Destruieren von Objekten. Das habe ich auch schon drin, allerdings noch nicht an der richtigen Stelle. Ich mache das im Moment erst wenn das Objekt rausgegeben wird oder wenn es wieder freigegeben wird.
Richtig wäre es aber, wenn man das Objekt konstruiert wenn ein einer Objectcache erstellt wird. Hier habe ich nun das Problem das ja beim Konstruieren ein Fehler auftreten könnte, aber was macht man in dem Moment?

Der Sinn ist es, dass man z.B. einen Konstruktor übergeben kann und wenn ein Objectcache erstellt wird, kann z.B. bei Threads, gleich ne Thread-ID geholt werden und der Kernel-Stack (weil das ja Dinge sind die sich nicht verändern). Damit wird das über die gesamte Lebenszeit (solange also der Obejctcache besteht) nur einmal gemacht und man kann z.B. schneller Threads erstellen (was ja bei mir und erik wichtig ist).

[erik.vikinger]

Hallo,

Richtig wäre es aber, wenn man das Objekt konstruiert wenn ein einer Objectcache erstellt wird. Hier habe ich nun das Problem das ja beim Konstruieren ein Fehler auftreten könnte, aber was macht man in dem Moment?

Warum ist dieses Vorgehen Richtig? Ich bin mir jetzt nicht ganz sicher aber wimre sichert der C++-Standard zu das der Konstruktor dann aufgerufen wird nachdem das new erfolgreich Speicher geholt hat oder wenn das Objekt anfängt gültig zu sein und der Destruktor dann wenn das Objekt nicht mehr gültig ist oder als erstes beim delete. Davon abzuweichen birgt IMHO zu viele Risiken, eines davon hast Du ja gerade gefunden. Meiner Meinung nach hast Du dann etwa folgende Optionen: (1) Du gibst beim ersten Problem den gesamten SLAB-Block wieder frei (also löscht auch alle bereits erfolgreich konstruierten Objekte), (2) Du markierst die fehlerhaft konstruierten Objekte speziell damit sie später nicht rausgegeben werden (falls gar keines der Objekte erfolgreich erstellt werden kann könnte man auch wieder den gesamten SLAB-Block freigeben), (3) so wie 1 oder 2 nur das Du im Fehlerfall dem aktuellen Speicheranfrager NULL zurück gibst, (4) Du machst diesen Vorgang grundsätzlich in einem extra Kontext in dem Du solche Fehler auch anständig behandeln kannst. Ich bin ja der Meinung das alle Varianten erhebliche Nachteile haben und würde daher grundsätzlich davon abraten. Das Problem ist IMHO das die möglichen Fehler zu komplex sind und man sie auch nicht einfach ignorieren kann. Ich persönlich würde ja zu (3) tendieren weil dort immer noch der konsistenteste End-Zustand (inklusive in den CPU-lokalen Magazinen usw.) bei raus kommt (bei Erfolgreich aber auch bei Fehler). Eine weitere Möglichkeit wäre es den Konstruktionsvorgang auf 2 Phasen aufzuteilen, der erste Konstruktor (welcher beim SLAB-Block initialisieren aufgerufen wird) darf nur weiteren Speicher (z.B. Deinen Kernel-Mode-Stack bei Threads) anfordern und der zweite Konstruktor (der dann aufgerufen wird wenn das Objekt tatsächlich rausgegeben wird) macht dann den Rest (z.B. IDs holen). Auf diese Weise wären die Fehler bei der SLAB-Block-Erstellung wenigstens immer nur reine Out-of-Memory-Fehler so das der Rückgabewert NULL insgesamt auch konsistent ist (auch wenn das Objekt das Du jetzt eigentlich raus geben möchtest ja fertig vorhanden ist) und es ist IMHO auch ein guter Kompromiss aus Performance und geringer Komplexität.


Grüße
Erik

[FlashBurn]

Der Vorteil dieses Vorgehens ist doch, das du nicht jedes Mal ein Objekt konstruieren musst, wenn du Speicher allozierst und wieder destruieren musst, wenn du den Speicher wieder freigibst. Sondern dass das Objekt immer einen genau definierten Zustand hat, wenn du es bekommst und du es in dem Zustand auch wieder freigibst. So sparst du dir zusätzliche Arbeit (was auch ein Grund für den Slab-Allocator war).
Und genau dieser Thread-Pool ist wie gemacht dafür.
Im Endeffekt sind das Allozieren von Stack und ID beides nur OOM-Fehler (weil du ne neue ID nur nicht bekommen kannst, wenn kein Speicher mehr da ist um das Array zu erweitern).
Ich werde dann wohl Variante 1 implementieren, weil das die sinnvollste ist (mMn).

Da hast du dann mit deinen großen Slabs wieder Vorteile, weil bei dir schnell viele Threads erzeugt werden können, ohne das irgendwas nachgeladen werden muss. Allerdings den Nachteil (je nach dem was für Ziele man hat), dass ich (weil du ja nur einen Kernelstack pro CPU hast) dann auch zuviele Kernelstacks hätte und das frisst dann auch ganz schön (MB Bereich).

[erik.vikinger]

Hallo,

Der Vorteil dieses Vorgehens ist doch, das du nicht jedes Mal ein Objekt konstruieren musst, wenn du Speicher allozierst und wieder destruieren musst, wenn du den Speicher wieder freigibst. Sondern dass das Objekt immer einen genau definierten Zustand hat, wenn du es bekommst und du es in dem Zustand auch wieder freigibst. So sparst du dir zusätzliche Arbeit (was auch ein Grund für den Slab-Allocator war).

Ich kann mir nicht helfen aber das erscheint mir doch sehr suspekt. In meinem Konzept hab ich sowas jedenfalls nicht vorgesehen, ich möchte die Objekte erst befüllen nachdem sie rausgegeben wurden.

Im Endeffekt sind das Allozieren von Stack und ID beides nur OOM-Fehler (weil du ne neue ID nur nicht bekommen kannst, wenn kein Speicher mehr da ist um das Array zu erweitern).

Wenn Du das so zusichern kannst ist das natürlich auch Okay. Aber kannst Du das auch bei den anderen Objekt-Typen zu 100% zusichern?

Ich werde dann wohl Variante 1 implementieren, weil das die sinnvollste ist (mMn).

Was ist mit Variante 3? Ich meine wenn Du ein Magazin von dem CPU-lokalen Cache neu befüllen möchtest weil es die State-Maschine der Magazinverwaltung so vorsieht und Du das aber nicht machst, könnte es dann nicht sein das Deine Magazinverwaltung in einem ungültigen (bzw. normal nicht erreichbaren) Zustand wäre? Ich kenne ja nicht Dein System aber dieser Aspekt lässt mich da insgesamt etwas abschrecken.

Vor allem sehe ich in diesem Vorgehen insgesamt keinen so großen Vorteil, was in das Objekt rein soll weiß man doch zum Großteil erst wenn man es wirklich benötigt. Der Thread-Cache ist da sicher eine Ausnahme aber gerade hierfür wollte ich einen speziellen CPU-lokalen Cache bauen (der im wesentlichen auf dem selben Magazinverwaltungsmechanismus basiert) und nicht nur den Thread-Descriptor sondern auch einen zugehörigen User-Mode-Stack und eventuell eine ID enthält (wobei ich persönlich IDs nur ungern so kurzfristig recyceln würde).

Da hast du dann mit deinen großen Slabs wieder Vorteile, weil bei dir schnell viele Threads erzeugt werden können, ohne das irgendwas nachgeladen werden muss. Allerdings den Nachteil (je nach dem was für Ziele man hat), dass ich (weil du ja nur einen Kernelstack pro CPU hast) dann auch zuviele Kernelstacks hätte und das frisst dann auch ganz schön (MB Bereich).

Mit einem nichtunterbrechbaren Kernel würdest Du auch nur einen Kernel-Mode-Stack pro CPU benötigen.


Grüße
Erik

[FlashBurn]

Aber kannst Du das auch bei den anderen Objekt-Typen zu 100% zusichern?

Ich kann das, aber um sicher zu gehen, würde ich das in die Anforderungen an den Slab-Allocator mit aufnehmen. Zumal mir auch nichts anderes einfällt außer OOM, was da in einem Konstruktor schief gehen könnte (im Kernel)!?

Ich meine wenn Du ein Magazin von dem CPU-lokalen Cache neu befüllen möchtest weil es die State-Maschine der Magazinverwaltung so vorsieht und Du das aber nicht machst, könnte es dann nicht sein das Deine Magazinverwaltung in einem ungültigen (bzw. normal nicht erreichbaren) Zustand wäre? Ich kenne ja nicht Dein System aber dieser Aspekt lässt mich da insgesamt etwas abschrecken.

Naja, das mit der Magazinverwaltung ist nicht das Problem, weil mein Slab-Allocator erstmal nur einzelne Objekte rausgibt und d.h. die werden auch dort, wenn ein neuer Slab erstellt wird, konstruiert. Ich brauche das, da ich ein oder zwei Objekte habe die den Magazinlayer nicht benutzen sollen (zwecks Verschwendung). Alle anderen Objekttypen rufen dann die Funktionen auf, die den Magazinlayer benutzen und da der eigentliche Slab-Allocator keine Magazine kennt, gibt es auch keine Probleme mit halbvollen Magazinen oder solchen Späßen.

wobei ich persönlich IDs nur ungern so kurzfristig recyceln würde

Damit wäre man dann auch nicht POSIX-kompatibel, aber das kann ich lösen, indem ich immer beim Freigeben hinten an die freie Liste ranhänge und beim Allozieren immer vom Anfang wegnehme (wenn nur ein Objekt in dem Slab ist, funktioniert das natürlich auch nicht).
Aber ich sehe da erstmal nicht so das Problem (kann aber gut sein, das es da welche gibt, dann immer her damit), zumal du eh irgendwann anfangen musst die IDs zu recyceln.

Vor allem sehe ich in diesem Vorgehen insgesamt keinen so großen Vorteil, was in das Objekt rein soll weiß man doch zum Großteil erst wenn man es wirklich benötigt.

Naja, sowas wie IDs (und im Falle von Threads der Stack) muss ich doch nicht jedes Mal neu machen (vorallem wenn es relativ teuer ist), wenn es auch anders geht.

Mit einem nichtunterbrechbaren Kernel würdest Du auch nur einen Kernel-Mode-Stack pro CPU benötigen.

Naja, da würde ich dann mal Messungen machen müssen (wenn der Kernel soweit steht), was bestimmte Syscalls oder Exceptions an Zeit kosten und wenn das in Ordnung ist. Dann kann ich das auch so machen, aber dann muss ich meine Thread-Struktur vergrößern, weil da ja dann alle Register mit drin gespeichert werden müssen und was viel schwieriger sein wird, ich müsste zusehen, dass ich so ziemlich alle Spinlocks wegbekomme.