Thema: SLAB-Allocator als Basis fuer kmalloc?

[FlashBurn]

Nope!

Also ich habe ein Objekt vom Typ SlabDesc (wo die ganzen Infos zum Slab drin stehen, z.B. wie groß ein Objekt ist, welches Alignment usw. und auch die Listen für die Objectcaches) und dieses Objekt brauchst du ja im Endeffekt nur einmal und zwar wenn du den Slab-Descriptor erzeugst und der wird vom Slab-Allocator geholt (deswegen gibt es da auch kein Henne-Ei-Problem, nur bei dem SlabDesc der die Objekte vom Typ SlabDesc beschreibt, aber den kann ich von Hand erstellen).

Wenn ein neuer Objectcache erstellt werden muss, muss man ja einfach nur ein paar Pages (die Info steht im SlabDesc) vom VMM geholt werden und die einzelnen Objekte müssen konstruiert werden (falls du das verwendest) und schon habe ich neue Objekte die ich dann rausgeben kann.

Dann gibt es da noch das Problem das man ja feststellen muss zu welchen Objectcache ein Object gehört (es sei denn du machst es wie einige einfache malloc() Implementationen und speicherst nen Pointer auf den Objectcache 4byte vor dem Object, aber dann müssen alle deine Objecte 4byte größer sein) und da habe ich mir was von Linux abgeguckt. Dort werden zu jeder physikalischen Page einige Infos gespeichert und ich speichere da unter anderem zu welchem Objectcache eine Page gehört. So muss man nur in einem Array nachgucken und bekommt nen Pointer auf den Objectcache (was O(1) ist). Vorher hatte ich das in Bäumen gespeichert (da bin ich dann den Baum nach der Adresse des Objects durchgegangen und ob die innerhalb eines Objectcaches liegt), aber das war mir zu Zeit-, Speicher- und Rechenaufwändig.

[erik.vikinger]

Hallo,


Warum so unendlich kompliziert?
Die SLABs können sich doch auch selber verwalten. Ich hab mir gedacht das in jeden Block (ich fordere für die SLABs immer Blöcke zu 512 kB an) vorne ein kleiner Header drin ist der Infos über die Anzahl der freien Objekte in diesem Block und einen Pointer auf das erste freie Objekt (soll dann nach LIFO-Prinzip arbeiten), dazu kommen dann noch ein Next-/Prev-Pointer-Pärchen damit die Blöcke als doppelt verkette Liste verwaltet werden können (die Liste soll nach der Anzahl an freien Objekten sortiert werden damit ich immer möglichst aus den vollsten Blöcken zuerst neue Objekte nehme). Es gibt dann also für jede Objekt-Größe eine solche SLAB-Block-Verkettung und jeweils einen Pointer (als statische Variable) der auf den SLAB-Block zeigt welcher am vollsten aber noch nicht ganz voll ist (damit das Allozieren neuer Objekte möglichst schnell geht). Dazu gibt es dann pro Objekt-Größe (als statische Variable) noch jeweils die Gesamt-Anzahl an SLAB-Blöcken und die Anzahl aller freien Objekte (wenn dieser Wert eine kritische Grenze unterschreitet wird ein neuer Block von der physischen Speicherverwaltung angefordert, diese Grenze muss aber so bemessen sein das die physische Speicherverwaltung selber noch problemlos arbeiten kann da diese ja auch kleine Objekte benötigt).

Von dem Objekt-Pointer auf dessen Größe schließen zu müssen empfinde ich als unnötig, da kann man auch kfree mit einen zweiten Parameter ausstatten das die Objekt-Größe angibt. Man weiß doch schließlich was man frei gibt! Und wenn die SLAB-Blöcke immer eine definierte Größe (Zweierpotenz) und ein passendes Alignment haben kommt man vom Objekt-Pointer immer sofort auf den Header des betreffenden SLAB-Blocks mit einer simplen AND-Operation.

Einen Typ "SlabDesc" möchte ich gar nicht haben da ich ja nur eine sehr überschaubare Anzahl an Objekt-Größen habe (die alle zur Compile-Zeit bekannt sind) und die entsprechenden SLAB-Parameter jeweils händisch bestimmen kann (welche dann als Konstanten in den Code kommen was dafür kleineren und schnelleren Code ergibt weil ja Speicherzugriffe fehlen).

Die CPU-lokalen Caches sind da eine zusätzliche Ebene drüber (auf die ich der Einfachheit halber im ersten Anlauf verzichten möchte) und dafür sollten die SLAB-Funktionen so aufgebaut werden das sie immer gleich 16 (oder ne andere Anzahl) Objekte auf einmal allozieren oder freigeben. Ich seh da jedenfalls kein Problem sowas später drüber zu stülpen um ordentliche Performance zu bekommen. Der komplette Speicherbedarf für diese Funktionalität ist zur gesamten Laufzeit konstant (es wird hierfür also kein malloc/free benötigt) und hängt nur von einer Information ab die man nicht zur Compile-Zeit hat: der Anzahl der CPUs.


Grüße
Erik

[FlashBurn]

Warum so unendlich kompliziert?

Also erstmal wurde der originale Slab-Allocator ja für monolithische Kernel entwickelt und da gelten ein paar andere Bedingungen und dann kommt noch hinzu das sich jeder andere Ziele für sein OS setzt. Zumal ich meine Variante nicht sondernlich kompliziert finde.

Was mich an deinem Konzept stören würde (aber das hat was mit den Zielen die wir erreichen wollen zu tun), ist das du immer Objectcaches von 512kb hast, ist mir viel zu groß. Dann hast du den Header vorne drin, ich würde ihn ja nach hinten packen. Denn dann kannst du ein besseres Alignment umsetzen (da du immer mit einem Alignment von 512kb anfängst), aber das hat auch den Nachteil, das du unter Umständen ganz schön verschnitt hast (obwohl das bei dieser Größe=512kb nicht das Problem sein sollte).
Dann kommt noch das Sortieren der Liste hinzu, das könnte ein Problem sein, aber theoretisch würdest du einen Objectcache max 1 Element nach hinten oder vorne schieben (?).

Dein Vorschlag kfree einen zweiten Parameter mit der größe mitzugeben, halte ich mal "dagegen", warum macht man das dann nicht schon seit Anfang an?

Ich habe diese SlabDescs auch nur deswegen dynamisch, weil ich halt die CPU Anzahl (und bei bestimmten Datenstrukturen die Größe) nicht zur Compilezeit kenne. Ansonsten hätte ich das auch so gemacht, alleine schon deswegen, weil man so weniger Speicher benötigt.

Das du immer gleich 16 (als Bsp.) Objekte mit einmal rausgeben willst, ist erstmal eine gute Idee, aber was machst du wenn die Anzahl an Objekten die in einem Objectcache ist, kein vielfaches von 16 ist? Dann hättest du ja nochmal Verschnitt.

Als letztes wäre noch meine Frage, wie du dann eine Datenstruktur haben willst, deren Größe erst zur Laufzeit bekannt ist (was ja auf die per CPU Caches zutrifft)?

[erik.vikinger]

Hallo,

Also erstmal wurde der originale Slab-Allocator ja für monolithische Kernel entwickelt und da gelten ein paar andere Bedingungen

Ja, da hast Du Recht, aber Du wolltest doch wimre einen Micro-Kernel und ich finde da sollte man sich schon mal die Mühe machen auch das Konzept passend umzuarbeiten.

Natürlich hat jeder andere Ziele für sein OS, wäre ja schlimm wenn es anders wäre, aber für die Bedürfnisse eines Micro-Kernels empfinde ich persönlich das Du etwas zu viel Komplexität da drin hast.

Das ich immer gleich 512 kB nehme hat bei mir einen einfachen Grund: die Descriptor-Tabellen sind auch 512 kB groß und in der 64 Bit-Version meiner CPU möchte ich eventuell 512 kB als kleinste Page-Größe benutzen (für ein 3-stufiges Paging, wenn ich kleinere Pages (z.B. 64 kB) möchte dann benötige ich auf jeden Fall ein 4-stufiges Paging). Diese 512 KB tauchen bei meiner CPU-Architektur auch noch an anderen Stellen auf und als so verschwenderisch empfinde ich die 512 kB auch nicht. Das Windows XP an dem ich gerade sitze sagt das im Moment 63 Prozesse mit 700 Threads zusammen knapp 800 MB Speicher verbrauchen, wenn auf mein System irgendwann einmal eine ähnliche Last kommt denke ich das mein Kernel deutlich weniger eigenen Verwaltungsspeicher verbraucht als Windows XP oder andere OSe (schon weil ich nicht für jeden Prozess ein eigenes Paging-Directory benötige) trotz den großzügigen 512 kB SLAB-Blöcken.

Ob der Header vorne oder hinten ist hat IMHO auf den Verschnitt keine Auswirkungen (der Header bleibt ja immer gleich groß) aber das Argument mit dem Alignment für die eigentlichen Objekte muss ich mir auf jeden Fall noch mal durch den Kopf gehen lassen, Danke für den Hinweis.

Dann kommt noch das Sortieren der Liste hinzu, das könnte ein Problem sein, aber theoretisch würdest du einen Objectcache max 1 Element nach hinten oder vorne schieben (?).

Ich kann nicht nachvollziehen worin Du beim Sortieren der SLAB-Block-Kette ein Problem siehst. Klar kostet das ab und an mal etwas Rechenleistung aber dafür hab ich beim Allozieren den Vorteil das ich bevorzugt die Blöcke benutze die eh schon recht voll sind und sobald diese ganz voll sind fallen sie aus der Suche nach freien Objekten ganz raus. Wenn Speicher immer nach dem LIFO-Prinzip alloziert und freigegeben werden würde würde sich das von ganz allein so ergeben aber in der Realität ist das eben nicht so, von daher möchte ich dem etwas nachhelfen. Ich erhoffe mir durch diese Sortierung dafür zu sorgen das immer nur möglichst wenige dieser Blöcke nur teilweise belegt sind. Falls das so in der Realität nicht funktioniert muss ich mir dann was anderes überlegen aber erst einmal möchte ich das so umsetzen.

Dein Vorschlag kfree einen zweiten Parameter mit der größe mitzugeben, halte ich mal "dagegen", warum macht man das dann nicht schon seit Anfang an?

Das ist doch kein Argument, selbst wenn ich der einzigste in diesem Universum wäre der das so macht. Warum soll ich es dem free unnötig kompliziert machen? Gerade in einem überschaubaren Micro-Kernel weiß ich doch immer was ich freigebe also kann ich diese Information auch gleich dem free mitgeben und ihm so die Mühe sparen das selber heraus finden zu müssen. Du hattest Dein Konzept dazu ja mal beschrieben und ich muss ehrlich sagen das mir persönlich das viel zu viel Speicher und CPU-Leistung kosten würde. Vor allem da ein zweites Parameter für free ja quasi gratis ist.

Für meine User-Mode-Heap-Umsetzung möchte ich ja ein zum SLAB ähnliches Konzept benutzen aber da ich dort immer FAR-Pointer habe sehe ich dem Pointer durch den Selector-Teil immer an was er für ein Objekt beschreibt. Mein Aufwand ist also ein einzelner simpler Tabellenzugriff.

Ich habe diese SlabDescs auch nur deswegen dynamisch, weil ich halt die CPU Anzahl (und bei bestimmten Datenstrukturen die Größe) nicht zur Compilezeit kenne.

Aber zur Boot-Zeit kennst Du doch die Anzahl der CPUs und ab da ist diese konstant. Oder möchtest Du das Hinzufügen und Entfernen von CPUs zur Laufzeit unterstützen?

Ansonsten hätte ich das auch so gemacht, alleine schon deswegen, weil man so weniger Speicher benötigt.

Dann mach es doch einfach so. Ich denke das die Einsparung an Speicher (bei Daten und Code) sicher nennenswert ist.

Das du immer gleich 16 (als Bsp.) Objekte mit einmal rausgeben willst, ist erstmal eine gute Idee, aber was machst du wenn die Anzahl an Objekten die in einem Objectcache ist, kein vielfaches von 16 ist? Dann hättest du ja nochmal Verschnitt.

Die 16 war ja auch nur so ein Vorschlag, ich könnte in den CPU-lokalen Cache auch immer 8 Objekte auf einmal vom SLAB-Allocator holen bzw. zurückgeben. Ich bin aber der Meinung das man den SLAB-Allocator dann schon so umbauen sollte das er mehrere Objekte mit einem Aufruf alloziert bzw. freigibt um eben die Kosten von mehreren Funktionsaufrufen zu sparen. Da die eigentlichen Benutzer von kmalloc/kfree ja dann nur noch den CPU-lokalen Cache benutzen benötigt der eigentliche SLAB-Allocator dann kein Interface mehr das einzelne Objekte behandeln kann. Ich kann mir sogar vorstellen das man diese CPU-lokalen Caches per define zur Compile-Zeit zuschaltbar macht ohne das man am restlichen Code etwas ändern müsste, so könnte man mal belastbare Messergebnisse liefern um zu sehen wie viel Performance diese Caches wirklich bringen.

Als letztes wäre noch meine Frage, wie du dann eine Datenstruktur haben willst, deren Größe erst zur Laufzeit bekannt ist (was ja auf die per CPU Caches zutrifft)?

Ich habe keine solchen Strukturen und mir fällt auch absolut keine Situation ein wo ich das brauchen könnte. Auch die Größe der CPU-lokalen Objekt-Caches ist bei mir schon zur Compile-Zeit bekannt (ich sehe da nichts dynamisches, der besteht doch aus X Pointern und ein paar Verwaltungsdaten) nur die Anzahl weiß ich eben erst wenn das OS gestartet wird. Ich möchte diese Objekt-Caches dann einfach beim Booten hinten an die Data-Sektion des Kernels ran hängen, so das ich zur Laufzeit auch immer möglichst einfach den richtigen Pointer ausrechnen kann (aus CPU-Nummer und Objekt-Typ).


Grüße
Erik

[rizor]

Hallo,

Also erstmal wurde der originale Slab-Allocator ja für monolithische Kernel entwickelt und da gelten ein paar andere Bedingungen

Ja, da hast Du Recht, aber Du wolltest doch wimre einen Micro-Kernel und ich finde da sollte man sich schon mal die Mühe machen auch das Konzept passend umzuarbeiten.

Natürlich hat jeder andere Ziele für sein OS, wäre ja schlimm wenn es anders wäre, aber für die Bedürfnisse eines Micro-Kernels empfinde ich persönlich das Du etwas zu viel Komplexität da drin hast.

Das ich immer gleich 512 kB nehme hat bei mir einen einfachen Grund: die Descriptor-Tabellen sind auch 512 kB groß und in der 64 Bit-Version meiner CPU möchte ich eventuell 512 kB als kleinste Page-Größe benutzen (für ein 3-stufiges Paging, wenn ich kleinere Pages (z.B. 64 kB) möchte dann benötige ich auf jeden Fall ein 4-stufiges Paging). Diese 512 KB tauchen bei meiner CPU-Architektur auch noch an anderen Stellen auf und als so verschwenderisch empfinde ich die 512 kB auch nicht. Das Windows XP an dem ich gerade sitze sagt das im Moment 63 Prozesse mit 700 Threads zusammen knapp 800 MB Speicher verbrauchen, wenn auf mein System irgendwann einmal eine ähnliche Last kommt denke ich das mein Kernel deutlich weniger eigenen Verwaltungsspeicher verbraucht als Windows XP oder andere OSe (schon weil ich nicht für jeden Prozess ein eigenes Paging-Directory benötige) trotz den großzügigen 512 kB SLAB-Blöcken.

Ich nehme selten Windows in Schutz, aber in diesem Fall sagen deine 800 MB nichts über die wirklich notwendige Menge an belegten MBs aus. Das das Ding so viel verwendet, hat den einfachen Grund, dass moderne OSes freien Speicher als Verschwendung ansehen. Windows arbeitet in diesen Fällen genau so wie Linux. "Nimm dir jeden freien SPeicher, den du finden kannst und gib ihn frei, falls jemand anders den Speicher benötigt." Das hat den einfachen Grund, dass die Dinger alles Chachen, was sie vermuten demnächst zu brauchen. 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.

So will ich es ja auch machen und dafür verwende ich den SLAB-Allocator. Ich möchte da auch so eine Art Defragmentierung des Speichers einbauen, dass bei SPeicherknappheit der Speicher umgelegt werden soll. Macht das System in manchen Situationen natürlich langsamer, aber das ist kurz vor einem OOM egal. Lieber warte ich etwas, bis mein System wieder flüssig läuft, bevor es einen OOM ausgibt.

Dein Vorschlag kfree einen zweiten Parameter mit der größe mitzugeben, halte ich mal "dagegen", warum macht man das dann nicht schon seit Anfang an?

Das ist doch kein Argument, selbst wenn ich der einzigste in diesem Universum wäre der das so macht. Warum soll ich es dem free unnötig kompliziert machen? Gerade in einem überschaubaren Micro-Kernel weiß ich doch immer was ich freigebe also kann ich diese Information auch gleich dem free mitgeben und ihm so die Mühe sparen das selber heraus finden zu müssen. Du hattest Dein Konzept dazu ja mal beschrieben und ich muss ehrlich sagen das mir persönlich das viel zu viel Speicher und CPU-Leistung kosten würde. Vor allem da ein zweites Parameter für free ja quasi gratis ist.
Compile-Zeit zuschaltbar macht ohne das man am restlichen Code etwas ändern müsste, so könnte man mal belastbare Messergebnisse liefern um zu sehen wie viel Performance diese Caches wirklich bringen.

Die Variante dürfte vermutlich auch schneller sein, da du dir so unnötiges nachschauen im Speicher schenken kannst. Das macht natürlich nichts, wenn der Speicher im Cache liegt, aber tut er das nicht, verbrätst du Takte, die du mit einem zweiten Parameter verhinderst. Außerdem ist es so gut wie sicher, dass der zweite Parameter im CPU Cache liegt.

Als letztes wäre noch meine Frage, wie du dann eine Datenstruktur haben willst, deren Größe erst zur Laufzeit bekannt ist (was ja auf die per CPU Caches zutrifft)?

Ich habe keine solchen Strukturen und mir fällt auch absolut keine Situation ein wo ich das brauchen könnte. Auch die Größe der CPU-lokalen Objekt-Caches ist bei mir schon zur Compile-Zeit bekannt (ich sehe da nichts dynamisches, der besteht doch aus X Pointern und ein paar Verwaltungsdaten) nur die Anzahl weiß ich eben erst wenn das OS gestartet wird. Ich möchte diese Objekt-Caches dann einfach beim Booten hinten an die Data-Sektion des Kernels ran hängen, so das ich zur Laufzeit auch immer möglichst einfach den richtigen Pointer ausrechnen kann (aus CPU-Nummer und Objekt-Typ).


Grüße
Erik

Naja, sobald du CPU-Hotplugin unterstützen möchtest, ist die ganze Geschichte dynamisch. Habe ich momentan auch noch nicht drin, soll aber irgendwann mal kommen. Dürfte aber eine riesige Baustelle für sich selbst werden, da da ja sehr viel mehr dran hängt.

[FlashBurn]

Klar kostet das ab und an mal etwas Rechenleistung aber dafür hab ich beim Allozieren den Vorteil das ich bevorzugt die Blöcke benutze die eh schon recht voll sind und sobald diese ganz voll sind fallen sie aus der Suche nach freien Objekten ganz raus.

Mir gefällt die Idee auch immer besser Das Sortieren sollte eigentlich nicht wirklich Rechenzeit kosten, weil du ja einen Objectcache max eine Postion nach vorne schiebst (es wird was alloziert) oder nach hinten (es wird was freigegeben). Da ich ja dann eh von der Objektadresse auf die Adresse von der Slab-Struktur komme brauche ich die vollen Objecktcaches auch nicht in einer extra Liste speichern (zu Debugging Zwecken wäre das natürlich trotzdem sinnvoll).

Das ist doch kein Argument, selbst wenn ich der einzigste in diesem Universum wäre der das so macht.

Das war übrigens ne ernst gemeinte Frage Ich denke mal das hat mal "damals" nicht so gemacht, weil man dann in jedem Objekt hätte speichern müssen wie groß es ist und (das wird viel wichtiger sein), malloc liefert nicht immer einen Block zurück der genauso groß sit wie angefordert, sondern der kann auch größer sein und dann nützt dir die Angabe bei free() nämlich nichts!

Aber zur Boot-Zeit kennst Du doch die Anzahl der CPUs und ab da ist diese konstant. Oder möchtest Du das Hinzufügen und Entfernen von CPUs zur Laufzeit unterstützen?

Also ich will kein Hotplugging von CPUs unterstützen. Allerdings hilft es mir auch nicht wenn ich zur Boot-Zeit weiß wie viele CPUs ich habe.
Mein SlabDesc sieht ungefähr so aus:

Code: [Auswählen]

struct SlabDesc {
 //alle möglichen Sachen und Listen die man halt so braucht
 void* CPUCaches[][4][2];
};
Das heißt ich habe pro CPU 2*4 Objekte. Einmal 4 Objekte die ich rausgeben kann (allozieren) und einmal 4 Objekte die ich freigeben kann (free).
Wie willst du es hinbekommen das der SlabDesc immer erst zur Bootzeit erstellt wird und wo willst du das hinpacken? Zumal ich dann entweder alle SlabDesc Symbole erst zur Boot-Zeit auflösen kann (und dann das Problem habe, wie bekomme ich meine Konstanten Daten da rein, ohne das ich das als extra Code habe) oder ich speichere die Pointer (so wie jetzt auch schon) in Variablen ab (wo ich mir dann auch erstmal die Symbole holen müsste).

Die 16 war ja auch nur so ein Vorschlag, ich könnte in den CPU-lokalen Cache auch immer 8 Objekte auf einmal vom SLAB-Allocator holen bzw. zurückgeben.

Auf was ich hinaus will ist, was passiert, wenn du ne ungerade Anzahl von Objekten in deinen 512kb hast?

[Svenska]

Hallo,

ein free(pointer, size) ist nicht unbedingt sinnvoll. Denn malloc() darf mehr rausgeben als gewünscht und realloc() darf dynamisch die Größe ändern. Das kann unter Umständen im Programm sehr aufwändig werden, da den Überblick bis zum free() vollständig zu behalten.

Ansonsten könnt ihr immer RAM-Verbrauch durch Rechenzeit ersetzen.

Ich sehe kein Problem darin, für ein SMP-fähiges Betriebssystem ein paar Kilobyte für CPU-Verwaltungsstrukturen zu opfern, welche dann mangels realer CPUs nicht genutzt werden. Jeder heute übliche Rechner hat RAM-Größen im Gigabytebereich und ob dein Kernel nun ein MB mehr oder weniger für elementare Dinge (!) verbraucht oder nicht, spielt keine Rolle. Wenn mein Firefox sich ein paar hundert MB greift, dann fallen die paar KB mehr oder weniger freier Speicher nicht ins Gewicht.

Gruß,
Svenska

[FlashBurn]

Sorry, wenn ich das mal wieder so sage, aber was du (Svenska) schreibst ist doch der Grund warum die Programme soviel Speicher verbrauchen! Alle denken ja, wir hams ja und keiner macht sich mehr nen Kopf darüber.

Zumal du besser sagen solltest besonders die x86 Architektur ist mit viel RAM "gesegnet" (obwohl ich das eher negativ sehe). Wenn du dann mal zu ARM guckst (auch wenn die RAM mäßig tierisch am Aufholen sind) sieht es wieder anders aus. Wenn ich mir noch überlege wie es "damals" war, als 128MB noch als viel galten und auch ausreichen war, selbst für Spiele.

Ich weiß das viele die Auto vergleiche hassen, aber das kennt nun mal jeder. Wenn das Öl nicht so teuer (und knapp) wäre, dann würden wir heute immernoch (?) mit Autos fahren die 20l und mehr fressen.

Und was den Speicherverbrauch von einem OS angeht, wie gesagt jeder setzt sich halt andere Ziele und ich möchte kein OS schreiben welches schon nur für ne einfach Konsole 16MB und mehr braucht.

Das die paar KB nicht ins Gewicht fallen mag ja für nen Mikrokernel stimmen, aber ab nem Hybriden kann das schon echt viel werden. Hätte denn jemand mal eine Zahl zur Hand wie viele verschiedene Objekttypen (die den Slab-Allocator nutzen) der Linux-Kernel hat und dann wäre (auch wenn es Off-Topic ist) die max CPU Anzahl auch mal interessant.

So und um nun auch mal eure Einstellung/Meinung ein wenig zu überspitzen. Ihr sagt also die meisten Sachen sollte man statisch machen. Na wenn ich meine ganzen Datenstrukturen statisch mache, die von der CPU Anzahl abhängen, dann bin ich wahrscheinlich irgendwo im MB bereich. Dann kommen bei mir noch die Datenstrukturen für die IRQs dazu, weil da kann ich ja auch nicht wissen wie viele es sind (obwohl es zu >99% wohl 24 oder weniger sein werden) und das geht noch weiter so
Weil wir haben ja genug RAM

Das Problem was ich einfach damit habe, ist die Einstellung, die ich auch in der Uni feststellen muss. Man hat ja genug Speicher, da können wir den auch verschwenden, fällt ja nicht auf oder bis irgendein Programm mal fertig ist, hat sich die durchschnittliche RAM-Menge ja eh wieder vergrößert.

Ansonsten könnt ihr immer RAM-Verbrauch durch Rechenzeit ersetzen.

Sicher das du bei dieser These mit dieser Wortwahl bleiben möchtest

[rizor]

So und um nun auch mal eure Einstellung/Meinung ein wenig zu überspitzen. Ihr sagt also die meisten Sachen sollte man statisch machen. Na wenn ich meine ganzen Datenstrukturen statisch mache, die von der CPU Anzahl abhängen, dann bin ich wahrscheinlich irgendwo im MB bereich. Dann kommen bei mir noch die Datenstrukturen für die IRQs dazu, weil da kann ich ja auch nicht wissen wie viele es sind (obwohl es zu >99% wohl 24 oder weniger sein werden) und das geht noch weiter so
Weil wir haben ja genug RAM

Hier möchte ich dir widersprechen. Den Rest empfinde ich genau so.
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?
Okay, große Linux-Distros machen das so (Deren Config nimmt 256 CPUs als Basis (Standard vom Kernel)), aber Gentoo z.B. baut ja keine Kernel. Das muss der Gentoo-User selber machen (in meinen Augen der gigantische Vorteil von Gentoo). Und jemand, der das macht, kennt auch die Anzahl an CPUs.
Also hat statisch definitiv seine Vorteile (außer beim CPU-Hotplugin)

[FlashBurn]

@rizor

Da wären wir dann wieder bei dem Thema, was man mit seinem OS erreichen möchte. Ganz ehrlich das was du beschreibst ist genau der Punkt warum Linux Windows nie ersetzen kann.

Es kann, meiner Meinung nach, nicht das Ziel sein, jedes Mal wenn ich mein OS auf nem anderen Rechner laufen lassen, neu kompilieren zu müssen.

Das wäre wie, das man erst Windows installieren müsste um dann Linux zu kompilieren und dann nutzen zu können und ich denke mal das will keiner

Auch diese Einstellung kann ich überspitzt so darstellen, dass ich dann sage, sowas wie PIC/IOAPIC oder PIT/APIC mache ich auch statisch und der jenige der mein OS nutzen will, muss halt wissen was für Hardware er dann vorsich hat um mein OS nutzen zu können.
Das nächste ist die Hemmschwelle, wenn ich ein OS erst kompilieren muss (und bei größeren OS dauert das schonmal ewig und ist meistens mit einigem Aufwand verbunden), dann will ich es auch nicht mehr ausprobieren!

[rizor]

Okay, das ist ein Argument.
Ich weiß nicht, wie Windows das intern handhabt, aber die machen bestimmt auch nicht alles dynamisch.
Natürlich ist das der Grund warum Linux den Nerd-Status nie verlieren wird, aber man kann das ganze ja auch noch etwas einfacher machen.
Für den OS-Installer könnte man ja einen Kernel verwenden, der alles erkennen kann und automatisch die Config anpasst und dann den passenden Kernel baut. Natürlich kannst du jetzt sagen, dass das ganze dann trotzdem nur auf einem System läuft, aber da gibt es ja auch Mittel und Wege. Man könnte z.B. Beim booten analysieren,ob noch alles passt. Wenn das nicht so ist, wird im Hintergrund ein Kernel gebaut, der sich anpasst und dann das System neu gestartet werden muss.
Ist halt alles eine Frage des Aufwands.
Aber die ganzen der zur Compiler-Zeit zu kennen hat in meinen Augen den riesigen Vorteil, dass du das gesamte System kennst und der Compiler den Kernel optimal bauen kann. Das dürfte dann zum Teil schneller sein, als deine zur Laufzeit aufgebauten Datenstrukturen.

[FlashBurn]

Es ist auch möglich, mit einigem Aufwand, das ich die Sache "emulieren" könnte. In dem Sinne, das ich meine Datenstrukturen, die dynamisch sind, kennen muss und mein Bootloader die dann zur Laufzeit erzeugt und hinten an das Datensegment ranhängt und dann die ganzen Symbole auflöst. Das sollte genauso wenig Speicher verbrauchen.

Also ich möchte kein System nutzen wollen, wo während eines Starts rebootet wird, weil der Kernel neu kompiliert werden muss. Zumal es sowas in der Art bzw. von der Idee her besser, schon gibt. TCC kompiliert doch den Kernel erst zur Bootzeit. Allerdings steigt damit natürlich die Bootzeit enorm an.

Ein anderes Problem was ich sehe, der Source-Code benötigt auch ne Menge Speicher (was wieder vorraussetzt das du deinen Source-Code mitliefern möchtest) und den müsstest du dann auch immer auf dem Bootmedium haben, wo wir dann wieder dabei wären, wir haben ja riesige Festplatten, wozu also mit dem Speicher geizen (und da regen sich die meisten immer auf, wieviel Speicher Windows immer auf der Festplatte belegt).

Dazu kommt das man das ja auch auf Anwendungen ummünzen könnte und ganz ehrlich, ich möchte die meisten Sachen einfach benutzen und nicht noch kompilieren müssen.

Wenn deine Zielgruppe, für dein OS, natürlich absolute Nerds sind ist das natürlich möglich, aber bedenke das sich dann nicht viele finden lassen werden die dein OS mal testen oder ausprobieren würden!

Ich muss auch ganz ehrlich sein, ich würde kein OS testen wollen, was ich erst noch kompilieren muss. Wäre mir der Aufwand viel zu groß für.

[Svenska]

Hallo,

Alle denken ja, wir hams ja und keiner macht sich mehr nen Kopf darüber.

Beachte bitte die Relationen. Es ging um statische(!) Datenstrukturen, in einer Größenordnung von weniger als einem Mega(!)byte und um Rechnersysteme, die sehr viel mehr RAM haben (weil SMP).

Außerdem ist es problemlos möglich, die Anzahl der Einträge zur Compilezeit begrenzen (oder nachträglich durch ein Relinken anzupassen). So funktionierten alte UNIX-Systeme.

Ihr sagt also die meisten Sachen sollte man statisch machen. Na wenn ich meine ganzen Datenstrukturen statisch mache, die von der CPU Anzahl abhängen, dann bin ich wahrscheinlich irgendwo im MB bereich.

Ja. Dafür verbrauchst du weniger Rechenzeit, weil du für den Zugriff auf die Strukturen nicht durch ewig viele Indirektionen gehen musst, außerdem sparst du Codegröße, weil die Zugriffsmuster viel einfacher sind.

Wenn du einen SMP-fähigen Kernel auf einem Uniprozessorsystem betreibst, dann führst du oft mehr Code aus als nötig (z.B. für Locking etc.). Dieser Code nimmt Platz weg. Ältere Prozessoren haben weniger CPU-Cache, also reduzierst du durch "mehr nutzloser Code" ohnehin die Leistung.

Willst du einen Kernel schreiben, der optimal auf einem 386er mit 4 MB RAM optimal performt, dann wird er auf einem Dual-Hexacore-System mit 64 GB RAM nur suboptimal laufen. Andersrum gilt das genauso. Du musst dir bewusst sein, dass du immer Kompromisslösungen benutzt.

Weil wir haben ja genug RAM

Ja, haben wir. Auf meinem System sind von 2 GB RAM mehr als die Hälfte für Plattencache eingeteilt. Eben weil wir genug RAM haben, können wir performancesteigernden Maßnahmen, wie z.B. aggressives Caching, sinnvoll einsetzen. Ich rede nicht von großflächiger Verschwendung.

Wenn der Compiler (für eine sinnvolle Verarbeitungszeit) nur 8 MB RAM hat, dann kann er nunmal nicht alle Optimierungen ausschöpfen. Hat er dagegen ein paar GB verfügbar, geht das plötzlich viel besser. Und wenn wir den Compiler in nur 64K quetschen müssen, dann ist das Ergebnis sogar grausam dagegen. Aber es gibt solche Compiler.

Das Problem was ich einfach damit habe, ist die Einstellung, die ich auch in der Uni feststellen muss. Man hat ja genug Speicher, da können wir den auch verschwenden, fällt ja nicht auf oder bis irgendein Programm mal fertig ist, hat sich die durchschnittliche RAM-Menge ja eh wieder vergrößert.

In der freien Wirtschaft zählt die Größe "Realzeit zwischen Idee und Vermarktung". Da ist für Qualität nur wenig Platz. In der Uni zählt "lässt sich theoretisch Beweisen", da spielt die Umsetzbarkeit nur eine untergeordnete Rolle.

Ansonsten könnt ihr immer RAM-Verbrauch durch Rechenzeit ersetzen.

Sicher das du bei dieser These mit dieser Wortwahl bleiben möchtest

Ich ersetze das Wort "immer" durch "fast immer". Und ja, bei der These bleibe ich; ich bin mir aber durchaus bewusst, dass es sowohl nach oben als auch nach unten praktische Grenzen gibt, ab der es sich nicht lohnt.

Gruß,
Svenska

[FlashBurn]

Außerdem ist es problemlos möglich, die Anzahl der Einträge zur Compilezeit begrenzen (oder nachträglich durch ein Relinken anzupassen).

Da müsstest du mal genauer werden. Ich verstehe nicht ganz wie das mit dem relinken funktionieren soll bzw. was das machen soll.

Wenn du einen SMP-fähigen Kernel auf einem Uniprozessorsystem betreibst, dann führst du oft mehr Code aus als nötig (z.B. für Locking etc.). Dieser Code nimmt Platz weg. Ältere Prozessoren haben weniger CPU-Cache, also reduzierst du durch "mehr nutzloser Code" ohnehin die Leistung.

Da hast du absolut recht!

Aber wie gesagt, zum Thema Usability finde ich es sehr schlecht wenn man ein Programm immer bzw. immer wenn man auf nem anderen Rechner ist (was auch portable Programme unmöglich macht bzw. unpraktikabel) neu kompilieren muss.

Willst du einen Kernel schreiben, der optimal auf einem 386er mit 4 MB RAM optimal performt, dann wird er auf einem Dual-Hexacore-System mit 64 GB RAM nur suboptimal laufen. Andersrum gilt das genauso. Du musst dir bewusst sein, dass du immer Kompromisslösungen benutzt.

Ich gehe dahin, das ich auf jeden Fall alte Systeme unterstützen will, aber SMP Systeme bevorzuge. Ansonsten sehe ich zu das meine Datenstrukturen und Algos in beiden Extremen halbwegs gleich effizient sind.

Zumal du mir doch wohl zustimmen musst, das es eigentlich nicht sein kann, dass ein OS welches nur eine Konsole zur Verfügung stellt schon 16MB und mehr braucht, oder?

Ich sags mal so, mit der Einstellung würde Linux aber nicht auf Routern oder anderen kleinen Geräten laufen und Handies wären noch langsamer!

In der freien Wirtschaft zählt die Größe "Realzeit zwischen Idee und Vermarktung". Da ist für Qualität nur wenig Platz. In der Uni zählt "lässt sich theoretisch Beweisen", da spielt die Umsetzbarkeit nur eine untergeordnete Rolle.

Da stimme ich dir nicht ganz zu. Ich habe allerdings noch keinerlei Erfahrung aus der freien Wirtschaft, aber wenn du ein Programm schreibst, dann musst du dich ja für irgend einen Algo und irgendeine Datenstruktur entscheiden, d.h. du denkst darüber nach und genau da kann man ansetzen. Denn seien wir ehrlich es wird sich oft nur für irgendeine Datenstruktur entschieden weil man keine besseren kennt (weil man sich nicht auf dem laufenden hält und/oder keine Ahnung hat) und sich sagt, Speicher ist ja genug da, was die anderen Programme dann machen ist ja egal.

Und ja, bei der These bleibe ich; ich bin mir aber durchaus bewusst, dass es sowohl nach oben als auch nach unten praktische Grenzen gibt, ab der es sich nicht lohnt.

Naja, um nur mal ein Bsp. zu nennen. Ich habe eine zeitlang für alle Sachen die über eine ID haben, einen AVL-Baum benutzt um die IDs zu verwalten und auf die Datenstrukturen zuzugreifen.
Jetzt verwende ich statt dessen ein Array und das verbraucht immer (da nur Pages gemappt werden wo auch Daten drin sind) weniger oder gleich viel (was nur zutrifft, wenn eine Page in Benutzung ist) Speicher ist aber um Welten schneller.

Es kommt nämlich durchaus auf das Problem an, ob man sagen kann das weniger Speicherverbrauch mehr Rechenzeit heißt.

[kevin]

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.

[erik.vikinger]

Hallo,

Mir gefällt die Idee auch immer besser Das Sortieren sollte eigentlich nicht wirklich Rechenzeit kosten, weil du ja einen Objectcache max eine Postion nach vorne schiebst (es wird was alloziert) oder nach hinten (es wird was freigegeben).

Ja, meine Ideen wissen oft zu gefallen.

Da ich ja dann eh von der Objektadresse auf die Adresse von der Slab-Struktur komme brauche ich die vollen Objecktcaches auch nicht in einer extra Liste speichern (zu Debugging Zwecken wäre das natürlich trotzdem sinnvoll).

Wozu Du die komplett vollen SLAB-Blöcke in einer extra Liste speichern möchtest verstehe ich nicht, ich möchte das als eine einzige doppelt verkettete Liste lassen und den statischen Pointer (quasi den Einsprungspunkt in diese Liste) will ich auf den vollsten nicht ganz vollen SLAB-Block zeigen lassen (von diesem Punkt aus kann man sich also oft in beide Richtungen durch die Liste bewegen). Zusätzlich möchte ich noch einen Pointer auf den leersten SLAB-Block haben um das Freigeben von diesen zu vereinfachen.

Das war übrigens ne ernst gemeinte Frage Ich denke mal das hat mal "damals" nicht so gemacht, weil man dann in jedem Objekt hätte speichern müssen wie groß es ist und (das wird viel wichtiger sein)

Mir ist klar das Deine Frage ernst gemeint ist aber ich Denke wir reden hier trotzdem von 2 verschiedenen Standpunkten. Ich rede von einem kleinen überschaubaren Micro-Kernel (gerade die dynamischen Speicherbedürfnisse eines Micro-Kernels sind IMHO sehr gut überschaubar weil man ja nur eine eng begrenzte und wohl bekannte Menge an unterschiedlichen Objekten benötigt) und nicht von einer generischen Heap-Implementierung (wie sie z.B. in einer libc drin ist, auch die User-Mode-libc zu meinem OS wird ein normales free implementieren, schon allein weil ich im User-Mode FAR-Pointer hab und die gewünschte Information ja daher auch gratis bekomme).

malloc liefert nicht immer einen Block zurück der genauso groß sit wie angefordert, sondern der kann auch größer sein und dann nützt dir die Angabe bei free() nämlich nichts!

Klar kann malloc auch größere Objekte liefern, solange free den selben Algorithmus benutzt um an die genormte Objektgröße zu kommen ist das doch auch in Ordnung.

Also ich will kein Hotplugging von CPUs unterstützen.

Das ist IMHO auch ganz gut, ansonsten holt man sich damit doch eine enorme Komplexität ins OS von der wohl kaum einer von uns tatsächlich profitieren könnte. Aber selbst wenn dann kann man ja auch einfach beim booten die Anzahl der Sockel bestimmen und so die maximal mögliche Anzahl an CPUs ausrechnen.

Allerdings hilft es mir auch nicht wenn ich zur Boot-Zeit weiß wie viele CPUs ich habe.

Warum nicht? Vor allem was geht besser wenn Du das erst noch später ermittelst? Wann genau ermittelt Dein OS denn die Anzahl der vorhandenen CPUs?

Ich möchte zur Verwaltung der SLABs folgende Struktur verwenden (für jede Objektgröße eine eigene) :

Code: [Auswählen]

struct t_SlabMng
{
  ulong  NumFreeObj;     //Anzahl an freien Objekten (kann bei ungeordneter Freigabe auch deutlich mehr als die Anzahl der Objekte in einem SLAB-Block sein)
  ulong  NumSlabBlocks;  //Anzahl der SLAB-Blöcke insgesamt
  void*  SlabList;       //Pointer auf den vollsten nicht ganz vollen SLAB-Block
  void*  SlabListLast;   //Pointer auf den leersten SLAB-Block (Ende der Liste)
  char   Lock;           //Lock-Variable für alle malloc/mfree für diese Objektgröße
  char   BlockAddActiv;  //wird auf 1 gesetzt solange eine Block-Add-Aktion aktiv ist
                         //(in der Zeit müssen alle anderen Anforderungen die nicht vom VMM kommen warten)
  void*  LocalCaches[];  //Pointer auf ein Array mit allen CPU-lokalen Caches
                         //(die Größe dieser Objekte ist zur Compile-Zeit bekannt und die Anzahl wird beim booten ermittelt,
                         // die CPU-Anzahl steht in einer globalen Variable)
};Ich denke das ich damit komplett hin komme, alles andere sind ja Konstanten die bereits zur Compile-Zeit bekannt sind. Den Speicher für die CPU-lokalen Caches möchte ich dem physischen Speicher entnehmen (genauso wie den jeweils ersten SLAB-Block auch) bevor ich den VMM mit dem dann noch freien Speicher initialisiere, das Freigeben dieser Strukturen ist ja nicht nötig also geht das problemlos als statischer Speicherverbrauch durch. Zugegriffen wird auf die CPU-lokalen Caches mit LocalCaches[currentCpuNum].* da sehe ich keine Probleme.

Auf was ich hinaus will ist, was passiert, wenn du ne ungerade Anzahl von Objekten in deinen 512kb hast?

Ah, jetzt hab ich verstanden auf was Deine Frage abzielt. Dann muss eben bevor die Bündelanforderung erfüllt werden kann noch ein neuer SLAB-Block per VMM alloziert werden, ob das nötig ist ergibt bei mir folgender Vergleich: if (slab.NumFreeObj <= (Anforderungsmenge + ObjektReserve)) { vmalloc(); }. Eine Bündelanforderung muss ja nicht alle Objekte aus einem SLAB nehmen sondern soll auch beim vollsten nicht ganz vollen SLAB-Block anfangen, theoretisch wäre es möglich das alle neuen Objekte aus unterschiedlichen SLAB-Blöcken kommen (und danach auch X Blöcke zusätzlich komplett voll sind).

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.

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?

Außerdem ist es so gut wie sicher, dass der zweite Parameter im CPU Cache liegt.

Dieser zweite Parameter für mein kfree ist eine Konstante die ich als Programmierer in den Quell-Code tippen kann da ich ja immer genau weiß was für ein Objekt ich da freigeben will. Zumindest in meinem Kernel kostet die gar nichts.

soll aber irgendwann mal kommen.

Was echt, Du willst CPU-Hotplugging unterstützen? Und ich dachte immer mein Projekt ist schon ziemlich ambitioniert. Auf was für einen Rechner möchtest Du das denn entwickeln/testen?

Dürfte aber eine riesige Baustelle für sich selbst werden, da da ja sehr viel mehr dran hängt.

Oh ja, das dürfte wirklich eine recht große und komplexe Baustelle werden.

Ansonsten könnt ihr immer RAM-Verbrauch durch Rechenzeit ersetzen.

Grundsätzlich kann ich dieser These zustimmen. Aber es gibt manchmal auch Lösungen die an beiden Seiten einen Vorteil bringen, z.B. das zweite Parameter für free bei einem SLAB-Allocator bringt mehr Performance weil man nicht erst aufwendig die Objekt-Größe ermitteln muss und spart Speicher weil eben einige Verwaltungsinformationen weg fallen (ja ich weiß das ich das auf einen exotischen Sonderfall (meinen Micro-Kernel) beziehe aber es gibt diese Fälle eben doch ab und an mal).

Wenn mein Firefox sich ein paar hundert MB greift, dann fallen die paar KB mehr oder weniger freier Speicher nicht ins Gewicht.

Grundsätzlich kann ich auch hier zustimmen aber möchte schon anmerken das man sich zumindest bemühen sollte mit den verfügbaren Ressourcen sparsam umzugehen. Zumindest hab ich kein großes Problem damit wenn man mit ein klein wenig Speicherverschwendung einiges an Performance rausholen kann, wenn aber der Performancegewinn nur marginal oder der zusätzliche Speicherverbrauch riesig wäre würde ich das wohl nicht machen, ist eben immer ein Kompromiss.

In der freien Wirtschaft zählt die Größe "Realzeit zwischen Idee und Vermarktung". Da ist für Qualität nur wenig Platz.

So ist es! Leider!


Das Neucompilieren eines OS (oder eines anderen Programms) würde ich als User auch nur dann in Betracht ziehen wenn ich dadurch einen echten Vorteil bekomme, z.B. eine spürbar höhere Performance oder einen spürbar niedrigeren Speicherverbrauch. Das Aufsetzen einer geeigneten Build-Umgebung ist meistens mit erheblichen Aufwand verbunden für den es schon einer ordentlichen Begründung bedarf. Prinzipiell möchte ich mit einem frisch ausgepackten OS/Programm zumindest überhaupt etwas anfangen können (auch wenn es da ein paar Aspekte gibt die nicht ganz optimal auf meinen konkreten PC abgestimmt sind).

Zumal du mir doch wohl zustimmen musst, das es eigentlich nicht sein kann, dass ein OS welches nur eine Konsole zur Verfügung stellt schon 16MB und mehr braucht, oder?

Das kommt auf die Qualitäten der Konsole an.
Der Punkt ist das hier viele eine möglichst hochperformante Speicherverwaltung realisieren wollen und da hat man oft einen gewissen Basisverbrauch (z.B. bei meinen riesigen SLAB-Blöcken) der sich erst mit steigender Systemauslastung wieder relativiert aber eben die Minimalanforderungen sehr hoch ausfallen lässt. In das Zeitalter wo es noch hieß "640 kB sind genug für alles" möchte ich aber definitiv auch nicht mehr zurück.


Grüße
Erik

[FlashBurn]

Wozu Du die komplett vollen SLAB-Blöcke in einer extra Liste speichern möchtest verstehe ich nicht, ich möchte das als eine einzige doppelt verkettete Liste lassen und den statischen Pointer (quasi den Einsprungspunkt in diese Liste) will ich auf den vollsten nicht ganz vollen SLAB-Block zeigen lassen (von diesem Punkt aus kann man sich also oft in beide Richtungen durch die Liste bewegen). Zusätzlich möchte ich noch einen Pointer auf den leersten SLAB-Block haben um das Freigeben von diesen zu vereinfachen.

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.
Was mir aber gefällt (im Hinblick auf den Speicherverbrauch) ist, dass die Liste der Anzahl der freien Objekte nach sortiert ist.

Klar kann malloc auch größere Objekte liefern, solange free den selben Algorithmus benutzt um an die genormte Objektgröße zu kommen ist das doch auch in Ordnung.

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.

Was mir auch nicht ganz klar ist, was du eigentlich immer mit der Objektgröße holen meinst. Wann brauchst du die denn? Nur wenn du einen neuen Objektcache erstellst und da wird bei dir einfach ne Instruktion sein, die die Größe in ein Register läd und bei mir wird sie von ner Stack-Variablen geladen. Da sollte Performance technisch nun wirklich kein Unterschied sein! Dafür ist mein Code dann kompakter.

Warum nicht? Vor allem was geht besser wenn Du das erst noch später ermittelst? Wann genau ermittelt Dein OS denn die Anzahl der vorhandenen CPUs?

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.

Was man vllt auch nochmal betonen sollte, du hast ja deine Segment und damit eine Art malloc/free und ich habe das gar nicht und kann nicht mal eben einen Block einer beliebigen Größe allozieren um den als Puffer für die per CPU Caches zu nehmen. Wobei wir da dann auch wieder wären, das du nen Pointer hast um auf deine CPU Caches zuzugreifen und ich habe auch einen Pointer dafür. Ist also im Endeffekt das gleiche, nur anders gelöst.

Eine Bündelanforderung muss ja nicht alle Objekte aus einem SLAB nehmen sondern soll auch beim vollsten nicht ganz vollen SLAB-Block anfangen, theoretisch wäre es möglich das alle neuen Objekte aus unterschiedlichen SLAB-Blöcken kommen (und danach auch X Blöcke zusätzlich komplett voll sind).

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?

Ich habe das (leider eher unperformant) so gelöst das halt 4x die Funktion aufgerufen werden muss, die immer ein Objekt aus nem Cache holt. Macht die Sache erstens einfacher und zweitens behalte ich mir so die Option vor (und nutze sie auch intensiv), dass ich Fälle habe, wo ich den per CPU Cache nicht nutzen will oder kann.

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.

Edit::

Jetzt sind mir meine Bedenken bezüglich der sortierten Liste doch wieder eingefallen.

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.

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.

[Svenska]

Hallo,

Außerdem ist es problemlos möglich, die Anzahl der Einträge zur Compilezeit begrenzen (oder nachträglich durch ein Relinken anzupassen).

Da müsstest du mal genauer werden. Ich verstehe nicht ganz wie das mit dem relinken funktionieren soll bzw. was das machen soll.

Wie das technisch genau umgesetzt wurde, weiß ich nicht. Konkret hatte ich bei nem alten Xenix die Möglichkeit, durch ein Konfigurationsprogramm die Limits im Kernel zu ändern (also max. Anzahl serieller Terminals / gleichzeitig aktiver Prozesse / gleichzeitig geöffneter Dateien usw.); anschließend wurde der Kernel aus den Objectfiles neu gelinkt. Die Sourcen waren also nicht verfügbar, aber die Objectfiles. Ich vermute, dass dort die Offsets geändert wurden und im Kernel dann Freiräume eingebaut wurden, in denen dann die Datenstrukturen lagen.

Aber wie gesagt, zum Thema Usability finde ich es sehr schlecht wenn man ein Programm immer bzw. immer wenn man auf nem anderen Rechner ist (was auch portable Programme unmöglich macht bzw. unpraktikabel) neu kompilieren muss.

Davon redet auch keiner. Du redest von müssen, ich rede von können. Wenn es dir also zufällig auf das letzte Byte im Kernel ankommen sollte, hast du durchaus die Möglichkeit, den Speicherverbrauch zu reduzieren. Du musst es aber nicht tun.

Guck dir doch die üblichen Linux-Distributionen an. Die sind nicht auf Speicher sparen ausgelegt.

Zumal du mir doch wohl zustimmen musst, das es eigentlich nicht sein kann, dass ein OS welches nur eine Konsole zur Verfügung stellt schon 16MB und mehr braucht, oder?

Ein Größenvergleich: Boote ich mein Netbook (i686) mit "init=/bin/sh", lande ich bei 4.6 MB (6 MB inkl. Plattencache). Boote ich mit "single", lande ich bei 12 MB (27 MB inkl. Plattencache). Starte ich ein vollwertiges System ohne X11 (Runlevel 2), verbraucht mein System schon 29 MB (60 MB inkl. Plattencache). In allen Fällen habe ich "nur" eine Shell. Aber, wie dir auffallen sollte, ist die Größe des Kernels gegenüber den Anwendungen vernachlässigbar klein.

Oder andersrum: Wenn jede Anwendung einen Speicherverbrauch von mindestens 64 MB RAM hat, dann ist es total egal, ob der Microkernel nun 1 MB oder 2 MB verbraucht.

Würde man bei deinem Auto-Beispiel so konsequent argumentieren wie du, dann hätten wir keine Autobahnen aus Straßen, sondern aus Schienen und würden ausschließlich elektrisch angetriebene Mobilität haben. Die Kosten dafür (Bau, Instandhaltung, Inflexibilität) machen es aber nicht sinnvoll. Also nehmen wir absichtlich einen höheren Benzin-/Dieselverbrauch in Kauf.

Ich sags mal so, mit der Einstellung würde Linux aber nicht auf Routern oder anderen kleinen Geräten laufen und Handies wären noch langsamer!

Guck dir mal in einem modernen Kernel an, was alles durch CONFIG_EMBEDDED abschaltbar oder änderbar wird. Dann siehst du vielleicht auch den Grund, warum Linux auf Routern mit 16 MB einigermaßen vernünftig läuft. Ein normaler Distributionskernel für x86_64 ist da jedenfalls nicht mehr gebrauchbar.

Du vergleichst Äpfel mit Birnen.

Ich habe allerdings noch keinerlei Erfahrung aus der freien Wirtschaft, aber wenn du ein Programm schreibst, dann musst du dich ja für irgend einen Algo und irgendeine Datenstruktur entscheiden, d.h. du denkst darüber nach und genau da kann man ansetzen.

Kann man nicht. Da wird sich nicht für einen Algorithmus und eine Datenstruktur entschieden, sondern da wird nach der erstbesten Bibliothek gesucht, die man anwenden kann und die die Aufgabe erledigt.

Da ist es schon zu spät, auf Effizienz zu achten. Oder andersrum: Es wird durchaus hochgradig optimiert, aber auf die Zeit bis zur Marktreife, nicht auf Effizienz des Ergebnisses.

Denn seien wir ehrlich es wird sich oft nur für irgendeine Datenstruktur entschieden weil man keine besseren kennt (weil man sich nicht auf dem laufenden hält und/oder keine Ahnung hat) und sich sagt, Speicher ist ja genug da, was die anderen Programme dann machen ist ja egal.

Nein. Wenn ich alle Daten vorrätig habe, dann habe ich weniger Arbeit. Also verbrauche ich Speicher, um mir damit später Arbeit zu vereinfachen (oder die Programmierzeit zu verkürzen).

Und ja, bei der These bleibe ich; ich bin mir aber durchaus bewusst, dass es sowohl nach oben als auch nach unten praktische Grenzen gibt, ab der es sich nicht lohnt.

Naja, um nur mal ein Bsp. zu nennen. Ich habe eine zeitlang für alle Sachen die über eine ID haben, einen AVL-Baum benutzt um die IDs zu verwalten und auf die Datenstrukturen zuzugreifen.

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.

Es kommt nämlich durchaus auf das Problem an, ob man sagen kann das weniger Speicherverbrauch mehr Rechenzeit heißt.

Es gibt immer noch mehr Möglichkeiten, den Speicherverbrauch oder die Rechenzeit zu minimieren. Ab einem gewissen Punkt lohnt es sich jedoch nicht mehr, weil die geringste Ersparnis zu enormen Performanceverlust führt oder umgekehrt.

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.

Gruß,
Svenska

[FlashBurn]

Du redest von müssen, ich rede von können. Wenn es dir also zufällig auf das letzte Byte im Kernel ankommen sollte, hast du durchaus die Möglichkeit, den Speicherverbrauch zu reduzieren. Du musst es aber nicht tun.

Naja, wenn ein Programm mit einem bestimmten Prozessorfeature kompiliert wurde (weil halt hochgradig optimeirt), dann muss ich das Programm auf nem Rechner wo die CPU dieses Feature nicht bietet neu kompilieren.
Baue ich mein Programm so auf, das ich sagen, entweder ich optimiere hochgradig (durch irgendwelche Flags eventuell auch im Code) oder ich mache es allgemein und packe alle Features rein, würde ich sagen macht es die Sache nur unnötig kompliziert und verlängert die Programmentwicklung. Besser ist es sich für eine Sache zu entscheiden (in meinem Fall also, alle Features rein und zur Laufzeit wird entschieden welches Feature genutzt wird).

Oder andersrum: Wenn jede Anwendung einen Speicherverbrauch von mindestens 64 MB RAM hat, dann ist es total egal, ob der Microkernel nun 1 MB oder 2 MB verbraucht.

Ich meinte das mit dem Speicherverbrauch eigentlich auch allgemein und nicht nur auf den Kernel bezogen.

Würde man bei deinem Auto-Beispiel so konsequent argumentieren wie du, dann hätten wir keine Autobahnen aus Straßen, sondern aus Schienen und würden ausschließlich elektrisch angetriebene Mobilität haben. Die Kosten dafür (Bau, Instandhaltung, Inflexibilität) machen es aber nicht sinnvoll. Also nehmen wir absichtlich einen höheren Benzin-/Dieselverbrauch in Kauf.

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.

Da wird sich nicht für einen Algorithmus und eine Datenstruktur entschieden, sondern da wird nach der erstbesten Bibliothek gesucht, die man anwenden kann und die die Aufgabe erledigt.

Ich kann da wie gesagt leider nicht aus Erfahrung sprechen, aber ich kann mich auch dann immer noch zw. verschiedenen Datenstrukturen entscheiden, auch wenn ich eine schon fertige Implementierung der Datenstruktur nehme.

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. Außerdem kann ein Algo der weniger Speicher verbraucht durchaus schneller sein, alleine schon weil man wahrscheinlich weniger Cachemisses hat und die sind richtig teuer.

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.

Eher umgedreht in meinem Fall. Ich möchte das mein OS auch mit wenig Speicher läuft, aber mit mehr Speicher wird es definitiv bei vielen Sachen schneller/besser laufen, weil dann z.B. weniger ausgelagert werden muss und sowas. Ich will dahin, das es läuft und zwar auf beiden extremen und das sollte machbar sein. Die Cachegröße an die vorhandene RAM-Größe anzupassen sollte kein Problem sein und muss sowieso gemacht werden.

Edit::

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!

[Svenska]

Hallo,

Naja, wenn ein Programm mit einem bestimmten Prozessorfeature kompiliert wurde (weil halt hochgradig optimeirt), dann muss ich das Programm auf nem Rechner wo die CPU dieses Feature nicht bietet neu kompilieren.

Darum ging es doch nicht. Konkret ging es um die paar KB, die du verschwendest, wenn du die per-CPU-Strukturen statisch einbindest. Um die paar KB einzusparen, machst du dir eine Menge Aufwand und meine Argumentation war "wozu eigentlich, dafür ist genug RAM da".

Optimierung auf CPU-Basis ist noch eine ganz andere Baustelle, siehe "int 0x80", "SYSENTER", "SYSCALL".

Besser ist es sich für eine Sache zu entscheiden (in meinem Fall also, alle Features rein und zur Laufzeit wird entschieden welches Feature genutzt wird).

Oder, dass halt der PIT verwendet wird und nicht der HPET.

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.

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.

Außerdem kann ein Algo der weniger Speicher verbraucht durchaus schneller sein, alleine schon weil man wahrscheinlich weniger Cachemisses hat und die sind richtig teuer.

Kann, muss aber nicht, das hängt konkret von der Umgebung ab. Wäre dir das wichtig, würdest du immer den langsameren, speichersparenden Algorithmus nehmen, denn so ein 486er hat nur 16K Cache... Die Aussage ist in jedem Fall nicht allgemeingültig, sonst würde man keine aufwändigeren Algorithmen verwenden.

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