Thema: Eigene CPU

[erik.vikinger]

Hallo,

.... Anschließend werden die Code-Segmente assembliert. Dazu gibt es eine Vorrunde in der bei allen Befehlen geprüft wird wie groß sie mindestens werden damit jeder Befehl ein Initial-Offset bekommen kann. Dann soll der gesamte Code so lange immer wieder assembliert und optimiert werden bis sich das best-mögliche Ergebnis eingestellt hat (das Abbruchkriterium wird mir sicher einiges an Kopfzerbrechen bereiten).

Da steckt ein Fehler drin. Wenn man die Befehle versucht zu schrumpfen könnte es sein das nicht das kleinst mögliche Ergebnis dabei raus kommt.

Code: [Auswählen]

Label1:
    b Label2
    viel_Code;
    b Label1
Label2:Hierbei könnte es passieren das beide Sprünge gerade so nicht in die nächst kleinere Größer überführt werden können weil sie sich quasi gegenseitig blockieren, also die Entfernung auf Grund des "viel Code" gerade so zu groß ist für die nächst kleinere Größe aber wenn die Sprünge kleiner wären dann würde es eben gehen.
Das bedeutet das ich die Befehle in der Vorrunde erst mal auf die kleinste Möglichkeit setzen muss, falls das Label noch nicht auflösbar ist, und dann solange iterativ vergrößert wird bis die Größe aller Befehle gerade so ausreicht.


Danke an XanClic für diesen Hinweis, im IRC.


Grüße
Erik

[erik.vikinger]

Hallo,

(plus einen MAC-Befehl, den halte ich für nützlich)

Dir ist klar das ein MAC-Befehl ein 3 Operanden-Befehl ist?
In der Form "rA = rA + (r2 * r3)" must Du mindestens 3 Operanden angeben. Du kannst den Accu gerne auf 1 Bit reduzieren oder auch ganz weg lassen aber r2 und r3 müssen IMHO schon sein.


Mal ne andere Frage:
Wie groß würdet ihr die Pages in einem 64 Bit-System mindestens machen?
Ich würde gerne entweder 512 kBytes mit einem 3-stufigem Paging oder 64 kByte mit einem 4-stufigem Paging machen (Page-Descriptoren sind immer 16 Bytes, es ist dann auch jede beliebige größere Zweier-Potenz als Page-Größe möglich). 512 kBytes sind IMHO schon reichlich groß und unterlaufen etwas das Lokalitäts-Prinzip, dafür wird der TLB mit steigender Page-Größe immer effektiver. Bei 64 kByte wird dafür das Page-Directory etwas Speicherhungriger und jeder zusätzliche Level kostet wieder etwas Performance. Beim swappen auf HDD dürfte es kaum einen großen Unterschied geben, die mittlere Zugriffszeit ist deutlich länger als es dauert ein paar MByte zu lesen/schreiben.
Oder würdet ihr die Page-Table-Walker-Hardware ganz weg lassen und das der SW überantworten (viele CPUs machen das so)?
Oder eine Mischform? Beim Itanium z.B. gibt es eine Art großen TLB-L2-Cache im Speicher der von der HW durchsucht werden kann aber von der SW befüllt/verwaltet wird, der hat aber wegen dem Hash-Algorithmus ein paar Probleme mit variablen Page-Größen.
Wäre interessant was andere so dazu denken.


Grüße
Erik

[Svenska]

Dir ist klar das ein MAC-Befehl ein 3 Operanden-Befehl ist?
In der Form "rA = rA + (r2 * r3)" must Du mindestens 3 Operanden angeben. Du kannst den Accu gerne auf 1 Bit reduzieren oder auch ganz weg lassen aber r2 und r3 müssen IMHO schon sein.

Ne, war mir nicht klar.
So rückblickend stellt sich da auch die Frage der Ergebnisvermittlung, da ich mit dem jetzigen Ansatz nur ein Ergebnisregister beschreiben kann, d.h. eine Multiplikation zweier 8-Bit-Register nicht zurücksichern kann. Bäh. Pfui. Wie kannst du nur sowas sagen?

Damit fällt ein Hardwaremultiplizierer eh flach. Allerdings hätte ich bevorzugt die 4-Operandenfassung des Befehls genommen (A = B + C * D), da ich vermute, dass diese nützlicher ist. Aber die Hälfte der Register, die ja auch vorher geladen werden müssen (=6 Takte für 3 Immediates plus Multiplikation) macht das ganze etwas schwieriger.

Mal ne andere Frage:
Wie groß würdet ihr die Pages in einem 64 Bit-System mindestens machen?

Ich würde das bevorzugt von der Größe der zu erwartenden Codes und Daten abhängig machen. Wenn deine Anwendungen viele und große Daten verarbeiten (Puffer), dann würde ich die Pagegröße schon größer ansetzen als bei Durchlaufverarbeitung (z.B. ständige FFT). Vielleicht so nen Faktor 1,5 auf die Durchschnitts-Puffergröße abgeschätzt auf die nächste Zweierpotenz?

Für ein Allzwecksystem würde ich die Pagegröße klein machen, da du sonst recht viel Speicher verschwendest; das hängt dann aber auch wieder von der Verwaltung im Betriebssystem ab, inwieweit Anwendungen ihre Pages miteinander teilen können.

Abgesehen davon habe ich mich mit Paging nicht weiter beschäftigt und bitte daher um Entschuldigung, falls der Post etwas arg ahnungslos wirkt.

edit: Wenn du natürlich das Paging nur als Auslagerungsmöglichkeit für deine Segmente nutzt, kannst du als Richtmaß einerseits die Segmentgrößen nehmen, andererseits aber die Pages einfach sehr groß machen, in der Annahme, dass Paging nur bei Speicherknappheit (und damit wahrscheinlich sehr selten) aktiv wird.

Gruß,
Svenska

[erik.vikinger]

Hallo,

So rückblickend stellt sich da auch die Frage der Ergebnisvermittlung, da ich mit dem jetzigen Ansatz nur ein Ergebnisregister beschreiben kann, d.h. eine Multiplikation zweier 8-Bit-Register nicht zurücksichern kann.

Du könntest für das High-Byte vom Ergebnis auch ein extra Spezial-Register vorsehen (die 8 Bit PICs machen das so), aber um dieses Register lesen und schreiben (ohne schreiben kannst Du in einem IRQ-Handler nicht multiplizieren) zu können wirst Du wieder zusätzliche Befehle brauchen die wiederum Bits benötigen. Ein ekliges Dilemma.
Wenn Dein Ergebnis volle Größe hat solltest Du übrigens zwischen Signed und Unsigned unterscheiden können, was noch mal ein Bit im Befehl kostet. Genau das war der Grund warum ich neben den 20 Bit und 39 Bit Befehlen noch eine Variante mit 60 Bit haben wollte, damit mir nicht für interessante Befehle die Bits ausgehen.

Bäh. Pfui. Wie kannst du nur sowas sagen?

Ich bin eben ein fieser Mensch.

Allerdings hätte ich bevorzugt die 4-Operandenfassung des Befehls genommen (A = B + C * D), da ich vermute, dass diese nützlicher ist.

Die 4 Operandenvariante hat IMHO kaum Vorteile, der MAC-Befehl wird vorwiegend für DSP-Algorithmen und ähnliches Zeugs benutzt und da werden die Ergebnisse vieler Multiplikationen aufakkumuliert. Für sowas hab ich auch extra "R1:R2 = R1:R2 + ( R3 * R4 )", es gibt auch eine Version mit - anstatt +. 6 Operanden (für "R1:R2 = R3:R4 +/- ( R5 * R6 )") hätte ich aber nicht untergebracht, 4 unabhängige Operanden hab ich nur wenn der Akku nicht aus 2 Registern besteht "R1 = R2 +/- ( R3 * R4 )".

Ich würde das bevorzugt von der Größe der zu erwartenden Codes und Daten abhängig machen.

Das kann ich aber nicht vorhersagen. Es soll ja ein Allzweck-System werden.

Für ein Allzwecksystem würde ich die Pagegröße klein machen, da du sonst recht viel Speicher verschwendest; das hängt dann aber auch wieder von der Verwaltung im Betriebssystem ab, inwieweit Anwendungen ihre Pages miteinander teilen können.

Das mit der Speicherverschwendung (gerade bei kleinen Programmen) ist natürlich ein Problem (erinnert irgendwie an die Cluster-Größe bei FAT). Da die Basis-Adresse der Segmente wohl auf 64 kByte aligned ist (vielleicht auch weniger, da muss ich mal genau überlegen wie viele Bits ich in den Segment-Descriptoren wirklich für Flags brauche) können sich natürlich mehrere Segmente in einer größeren Page befinden.

Wenn du natürlich das Paging nur als Auslagerungsmöglichkeit für deine Segmente nutzt, kannst du als Richtmaß einerseits die Segmentgrößen nehmen, andererseits aber die Pages einfach sehr groß machen, in der Annahme, dass Paging nur bei Speicherknappheit (und damit wahrscheinlich sehr selten) aktiv wird.

Paging möchte ich vor allem für die Speicherdefragmentierung und andere Tricks nutzen aber natürlich auch zum swappen, falls ich mit meinem Projekt so weit komme das sich das lohnt.
Wichtig ist mir vor allem dass das Paging möglichst wenig Performance kostet und sich mit vertretbarem Aufwand im FPGA umsetzen lässt.


Grüße
Erik

[Svenska]

Ich hatte als Gedanken einen Instruktionsbus, wo auf der steigenden Taktflanke die Daten eingelesen werden und auf der fallenden Flanke das Ergebnis ausgegeben wird. Da die meisten Befehle implizit mit dem Akkumulator arbeiten (der also zusätzlich eigene Leitungen in die ALU hat, aber damit nur lesbar ist), hätte ich für das Ergebnis somit nur 8 Bit (plus die Steuerleitungen zur Registerauswahl).

Damit lässt sich keine direkte Multiplikation realisieren; alternativ könnte ich natürlich einfach zwei Befehle haben (einen für den High-, einen für den Low-Teil), aber das kostet mich einen weiteren Opcode, den ich nicht habe. Es wird wohl doch auf eine simple LEFT SHIFT-Operation hinauslaufen.

Den Unterschied zwischen signed und unsigned wird die CPU nicht kennen, das ist dann Software. Und wenn ich das Einserkomplement nehme, dann ist das eben so, auch wenn das die Unterscheidung zwischen "-0" und "+0" erlaubt.

Wenn dieses Monster fertig ist, werde ich vielleicht möglicherweise über eine sinnvollere CPU nachdenken, aber Bits sind halt teuer und richtig aufwändig, daher spare ich an jeder Stelle.

Mehrere Segmente innerhalb einer Page halt ich für nicht besonders zweckmäßig, eher dann eine Pagegröße, die mit den Segmentbasisadressen korreliert. Eine andere Idee wäre es, nicht den gesamten Adressraum in Pages aufzuteilen, sondern nur einen kleinen Teil. Da das Paging nur für Tricksereien verwendet wird, braucht es ja nicht unbedingt vollständig aktiv zu sein. Defragmentieren wäre dann natürlich schwieriger/langsamer, aber wie oft muss das geschehen? Wenn du die Programme etwas daraufhin anpasst [vgl. NOMMU-uClinux, welches aber nicht defragmentiert], sollte das ohnehin nicht nötig sein. Du sparst dann viele Bits und vermutlich einige Komplexität in der MMU ein.

Swappen kannst du, grundsätzlich genügend RAM vorausgesetzt, auch mit ganzen Segmenten. Das hat natürlich eine gröbere Granularität, wenn du das gesamte Codesegment auslagern musst, weil die Anwendung grad nicht aktiv ist. Bei mehreren aktiven Tasks sollte das aber nicht weiter stören.

Ich vermute mal, dass die 64 Bit-Variante aus praktischem Ansatz (Befehlslänge usw.) entsteht und nicht aus der Bedingung, da mehr als 4 GB RAM einzubauen. Wenn deine MMU also immer nur 4 GB abdecken kann, wäre das also kein Problem. Und wenn du mehr RAM hast, musst du halt die 4 GB-Blöcke getrennt defragmentieren.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Ich hatte als Gedanken einen Instruktionsbus, wo auf der steigenden Taktflanke die Daten eingelesen werden und auf der fallenden Flanke das Ergebnis ausgegeben wird. Da die meisten Befehle implizit mit dem Akkumulator arbeiten (der also zusätzlich eigene Leitungen in die ALU hat, aber damit nur lesbar ist), hätte ich für das Ergebnis somit nur 8 Bit (plus die Steuerleitungen zur Registerauswahl).

Der Akku sollte aber auch immer beschrieben werden können, er sollte also auch für das Ergebnis eine eigene Verbindung zur ALU haben. Außerdem hattest Du doch mal 2 Akkus im Plan, da könnte ja jeder Akku eigene Verbindungen zur ALU haben, damit währe "A1:A0 = A1:A0 + ( R2 * R3 )" möglich und Du müsstest nur 2 normale Register im Befehl codieren. Ich weiß das kostet Lötarbeit, aber für umsonst gibt es eben auch keine TTL-CPU.

Den Unterschied zwischen signed und unsigned wird die CPU nicht kennen, das ist dann Software.

Diese Unterscheidung in SW zu machen hallte ich für ungeschickt, um aus einem Unsigned errechnetem Ergebnis von 2 Signed Faktoren das richtige Ergebnis zu machen braucht der Compiler viele Befehle da kann er auch gleich händisch multiplizieren.

Und wenn ich das Einserkomplement nehme, dann ist das eben so, auch wenn das die Unterscheidung zwischen "-0" und "+0" erlaubt.

Was, Du willst ernsthaft über Einerkomplement nachdenken?!? Dann denke vielleicht doch über eine eigene Programmiersprache nach. Ich weiß das C da keine Vorgaben macht aber viele existierende Programme gehen einfach davon aus. Ich hatte es auch noch nie mit einer CPU zu tun die nicht mit dem Zweierkomplement arbeitet, mit so einer Idee wirst Du noch mehr inkompatibel zur restlichen Welt.

Wenn dieses Monster fertig ist, werde ich vielleicht möglicherweise über eine sinnvollere CPU nachdenken, aber Bits sind halt teuer und richtig aufwändig, daher spare ich an jeder Stelle.

Vielleicht solltest Du für Deine CPU erst mal einen Simulator programmieren damit Du ein Gefühl für den geplanten Befehlssatz bekommst. Wenn Du dann mit dem Ergebnis zufrieden bist kannst Du immer noch überlegen wie sich das per TTL realisieren lässt. Ein Simulator sollte für Deine CPU ja nun nicht so schwer sein, bestimmt gibt Dir chris12 die nötigen Tipps.

Mehrere Segmente innerhalb einer Page halt ich für nicht besonders zweckmäßig

Warum? Pages dienen doch bei mir nicht direkt der Speicherverwaltung. Und da ich jede beliebige Zweier-Potenz (>= kleinste Page-Size) erlauben will, um die TLB-Effizienz so hoch wie möglich zu halten, wird es sowieso der Regelfall sein das sich in einer Page mehrere Segmente befinden. Zum swappen werden die Pages natürlich auf die kleinste Größe reduziert.

Eine andere Idee wäre es, nicht den gesamten Adressraum in Pages aufzuteilen, sondern nur einen kleinen Teil.

Das habe ich eh vor. Der Speicher in dem z.B. die Peripherie liegt benötigt kein Paging.

Wenn du die Programme etwas daraufhin anpasst [vgl. NOMMU-uClinux, welches aber nicht defragmentiert], sollte das ohnehin nicht nötig sein.

Die Programme extra dafür anpassen möchte ich eigentlich nicht. Den Speicher von Flat-Memory-Programmen kann man ja auch gar nicht defragmentieren (wegen Pointern usw.), also kann uCLinux das nicht tun.

Swappen kannst du, grundsätzlich genügend RAM vorausgesetzt, auch mit ganzen Segmenten. Das hat natürlich eine gröbere Granularität, wenn du das gesamte Codesegment auslagern musst, weil die Anwendung grad nicht aktiv ist. Bei mehreren aktiven Tasks sollte das aber nicht weiter stören.

Meinst Du das ernst?? Komplette Code/Daten-Segmente auszulagern ist schon wirklich sehr strange. Für gewöhnlich ist es so das von allen Programmen immer etwas aktiv ist, und wenn es nur ein Signal-Handler ist der ab und an mal Nachrichten vom OS abhandelt. Das heißt das von jedem Programm wohl ein paar Pages im RAM bleiben müssen. Der Trick des Swapping per Paging ist das von jeden Programm nur das absolute Minimum im RAM bleibt, nur auf 0 wird sich das Minimum nicht reduzieren lassen. Segmentweises Swapping halte ich persönlich für keine gute Idee, auch wenn Du nicht der erste bist der das vorschlägt.

Ich vermute mal, dass die 64 Bit-Variante aus praktischem Ansatz (Befehlslänge usw.) entsteht und nicht aus der Bedingung, da mehr als 4 GB RAM einzubauen.

Sicher nicht im ersten Anlauf, da werde ich wohl mit höchstens 1 GByte auskommen müssen , aber grundsätzlich möchte ich schon mehr als 4 GByte RAM ermöglichen.

Wenn deine MMU also immer nur 4 GB abdecken kann, wäre das also kein Problem. Und wenn du mehr RAM hast, musst du halt die 4 GB-Blöcke getrennt defragmentieren.

Das defragmentieren hatte ich mir eher anders vorgestellt. Wenn es nötig ist dann wird ein Paging-Directory erstellt das den physischen RAM 1:1 mappt und zusätzlich nochmal in einem virtuellem Bereich hinter dem RAM, dann wird das Paging eingeschaltet und alle Segement-Basis-Adressen in den virtuellen Bereich verlegt, danach werden die Pages im physischen Speicher umsortiert und das Paging für den virtuellen Bereich immer mit angepasst, als letztes wird der 1:1 Bereich wieder auf 1:1 gebracht, die Segment-Basis-Adressen wieder in den 1:1 Bereich verlegt und das Paging abgeschaltet. Das Problem ist eher das dieser Vorgang Zeit kostet und in dieser Zeit das OS natürlich trotzdem Speicherveraltungsaufgaben (Segmente anlegen/löschen/vergrößern/verkleinern) wahrnehmen muss.


Grüße
Erik

[erik.vikinger]

Hallo,

Und wenn du mehr RAM hast, musst du halt die 4 GB-Blöcke getrennt defragmentieren.

Das wird nicht klappen wenn Segmente existieren die größer als 4 GB sind, was ja auf einer 64 Bit-Architektur möglich sein soll.

Das defragmentieren hatte ich mir eher anders vorgestellt.....

Ich hab da noch mal drüber nachgedacht.
Das Paging an sich bleibt besser immer angeschaltet und als benutzter Bereich wird Platz oberhalb des physischen RAM genommen.
Eine Memory-Map könnte etwa so aussehen (auf einer 32Bit-Plattform):

• 0 MB - 64 MB : Boot-Device (enthält Ur-Boot-ROM, Flash mit Kernel-Images, etwas SRAM und anderes Zeugs)
• 64 MB - 1 GB : Bereich für die Peripherie (PCI-Devices)
• 1 GB - 2 GB : physischer RAM
• 2 GB - 4 GB : virtueller Speicher, nur für diesen Bereich ist das Paging aktiv

Das OS verwaltet den linearen Speicher für den physischen RAM ganz normal. Wenn dann ein Segment vergrößert werden soll das zwischen 2 anderen liegt und deshalb nicht einfach so wachsen kann dann wird nur der zusätzliche Speicher an einer anderen Stelle (oder mehreren Stellen) im RAM alloziert, anschließend wird ein passender Bereich für das vergrößerte Segment (in einem Stück) im virtuellem Speicher alloziert und ein Mapping ins Paging-Directoy eingetragen dass das gesamte Segment aus dem physischen RAM in den virtuellen Speicher spiegelt (in möglichst großen Pages), dann wird die Basis-Adresse und die Größe im Segmentdescriptor geändert (das muss anderen CPUs irgendwie signalisiert werden, am besten mit einer Broadcast-Message), der SYSCALL zum vergrößern des Segments ist nun beendet. Als nächstes wird der Memory-Management-Dämon (User-Mode-Prozess mit geringer Priorität) aktiv der einen neuen zusammenhängenden Bereich im physischen RAM für das Segment sucht und alloziert, dann wird Page-Weise kopiert (in möglichst kleinen Pages) und immer das Mapping für den virtuellen Speicher mit angepasst. Wenn das fertig ist werden die alten Speicher-Bereiche des Segments freigegeben, die Segment-Basis-Adresse aktualisiert (zeigt jetzt wieder auf physischen Speicher für den kein Paging benutzt wird) und als letztes wird das Mapping aus dem Paging-Directory gelöscht und der virtuelle Speicher freigegeben. Das Segment ist damit verschoben ohne dass das User-Space-Programm das gemerkt hat. Falls im physischen RAM keine geeignet große Lücke für das vergrößerte Segment existiert müssen andere Segmente eben erst zusammen geschoben werden, das geschieht auf die selbe Art und so ähnlich wie bei einem klassischen Festplatten-Defragmentierer. Das zusammen schieben kann auch prophylaktisch im Hintergrund geschehen damit im Ernstfall schneller gehandelt werden kann.

Swapping lässt sich in dieses Konzept auch integrieren indem Segmente von dehnen Teile ausgelagert wurden im virtuellen Speicher bleiben und deren Mapping eben nur teilweise auf physischen Speicher zeigt (der Rest ist ausgelagert). Wenn der Memory-Management-Dämon merkt das die Summe der Segmentgrößen kleiner als der physische Speicher ist dann werden alle Segmente im physischen Speicher zusammen geschoben und fehlende Pages von der Platte eingelesen um dann die Basis-Adressen wieder in den physischen Speicher zu verlegen damit das Paging nicht benutzt werden muss. Swapping ist aber definitiv recht weit hinten auf meiner Dringlichkeitsliste.

Ich denke das kann so funktionieren, die größte Schwierigkeit ist eher das sich die Situation immer wieder (u.a. mitten in den Verschiebe-Vorgängen) ändert und der Memory-Management-Dämon dann immer wieder einen neuen Plan entwickeln muss.


Grüße
Erik

[Svenska]

Hallo,

ich hatte vor, den Akku direkt mit der ALU zu verbinden (und wenn es zwei gibt, schiebe ich ein Gatter dazwischen zur Selektion), so dass ich nur ein einziges Register lesen muss. Beide Akkus gemeinsam als Zielregister wird es eher nicht geben. Wenn ich keine Hardwaremultiplikation habe, dann brauche ich auch keine Entscheidung über signed/unsigned treffen; das oberste Bit der letzten Operation bleibt dann einfach ein Flag und gut ist.

Den Speicher von Flatmem-Programmen kann man wirklich nicht defragmentieren, aber man kann - angenommen, die Segmente sind hinreichend groß - die Segmente im physischen RAM verschieben. Dazu benötigt man kein Paging, die Programme dürfen dann aber keine Verweise über Segmentgrenzen erlauben. Das Swappen von ganzen Segmenten ist an sich gar nicht so abwegig, das meinte ich schon ernst. Einerseits vereinfacht es die Implementation, andererseits ist es eine Notlösung, die nie auftreten sollte. Das Umsortieren des Speichers (Verschieben der Segmente) erfordert ohnehin eine wie auch immer geartete Auslagerung.

Swapping effizient zu machen bringt meiner Meinung nach wenig, aber das hängt auch grundsätzlich vom Anwendungszweck ab. Mein System mit derzeit 2 GB RAM unter Linux fängt nur damit an, wenn irgendein Programm Amok läuft. Effektiv wird es nie genutzt.

Meine Meinung ist es, auf Paging ganz zu verzichten oder aber es vollständig zu implementieren und dann auch zu nutzen. Alles andere ist verschwendetes Silizium. Zumal mich die Defragmentierung irgendwie an einen Garbage Collector erinnert...  Zum richtigen Defragmentieren ist es eigentlich nicht nötig, wenn du die gesamte Segmentverwaltung dem Betriebssystem obliegt und Programme nur ihre eigenen Segmente und ein unverschiebbares Systemsegment verwenden können. Mit Paging könntest du das Defragmentieren durch ein Ummappen sehr schnell lösen und im Hintergrund später die reale Umsortierung machen, das halte ich aber (insbesondere bei mehreren CPUs) für ein sehr kompliziertes Unterfangen.

Gibt es vielleicht die Möglichkeit, nur sehr wenige Pages (vielleicht 16) zu erlauben, und damit die Größe der Pagetable stark zu begrenzen? Diese ließe sich eventuell als Gatter realisieren und der Pagetable-Lookup wäre dann kostenlos. Für Tricksereien ist das möglicherweise auch hinreichend.

Segmentierung finde ich prinzipiell toll, nur die damit einhergehenden Probleme (die es nur für knappes oder zersplittertes RAM gibt) finde ich schwierig zu lösen. Dynamische Segmentgrößen vereinfachen das etwas. In meiner Implementierung wäre das Defragmentieren allerdings atomisch, so dass der Kernel sich ungestört um die Speicherverwaltung kümmern kann. Damit gibst du dann allerdings die Echtzeitfähigkeit komplett auf - es sei denn, die Programme sind "lieb".

Naja, sind alles nur Gedankensplitter.

Gruß,
Svenska

[erik.vikinger]

Hallo,

ich hatte vor, den Akku direkt mit der ALU zu verbinden

So soll es ja auch sein, der Akku hat nen direkten Draht zur ALU damit jeder Befehl ihn immer benutzen kann.

Wenn ich keine Hardwaremultiplikation habe, dann brauche ich auch keine Entscheidung über signed/unsigned treffen; das oberste Bit der letzten Operation bleibt dann einfach ein Flag und gut ist.

Bei den Strichrechnungen im Zweierkomplement gibt es keinen Unterschied zwischen signed und unsigned, wie das im Einerkomplement ist weiß ich gar nicht. Da fällt mir ein das die ganzen eingebauten Operatoren in VHDL auch alle vom Zweierkomplement ausgehen, eine CPU mit Einerkomplement in VHDL zu entwickeln dürfte ziemlich frustrierend sein.

Ohne HW-Multiplikation muss der Compiler diese übernehmen, ich glaube der gcc hat dafür ne Reihe buildins die auf (zu) kleinen CPUs benutzt werden können.

aber man kann - angenommen, die Segmente sind hinreichend groß - die Segmente im physischen RAM verschieben.

Hä?? Was hat die Größe der Segmente damit zu tun?

Dazu benötigt man kein Paging,

Dann muss das verschieben atomar sein, das betreffende Programm muss während dieser Zeit schlafen. Bei großen Segmenten ist das schon ziemlich doof, das will ich den Programmen nicht zumuten. Bei SMP muss der OS-Kernel dann auch noch sicherstellen das wirklich keiner der Threads des betreffenden Programms auf anderen CPUs laufen, ist zwar machbar aber umständlich. Bei "beerbten" Segmenten (wegen shared Memory oder IPC) ist das noch schwieriger, weil man noch mehr Programme (alle ihre Threads) deaktivieren muss. Das atomare verschieben von Segmenten würde quasi das gesamte System lahmlegen.

die Programme dürfen dann aber keine Verweise über Segmentgrenzen erlauben.

Was genau meinst Du? Offsets für ein bestimmtes Segment dürfen nur vom dessen Minimum bis zu dessen Maximum gehen (beides ist bei mir im Segment-Descriptor eingetragen, bei x86 gibt es kein Minimum dort fangen Segmente immer mit Offset 0 an), alles andere löst beim Speicherzugriff eine Exception aus. So einen Mist wie die unflexieble Segmentierung im x86-Real-Mode will ich definitiv nicht machen.

Das Swappen von ganzen Segmenten ist an sich gar nicht so abwegig, das meinte ich schon ernst.

Das bedeutet aber dass das betreffende Programm komplett deaktiviert ist wenn eines seiner Segmente nicht im RAM ist. Wenn z.B. ein großes Office-Programm (falls sowas jemals auf meinem OS laufen sollte) für jeden Tastendruck wieder komplett in den Speicher muss obwohl der Key-Event-Handler nur den Text um einen Buchstaben erweitern müsste und nur das aktualisieren der Bildschirmdarstellung über die GUI antriggern müsste. Das stelle ich mir wahrlich nicht praktikabel vor. Ich möchte den linearen Speicher wirklich im Hintergrund bei laufendem System defragmentieren können, wenn das nicht geht ist das Konzept mit der Segmentierung IMO nicht tragfähig.

Das Umsortieren des Speichers (Verschieben der Segmente) erfordert ohnehin eine wie auch immer geartete Auslagerung.

Nicht unbedingt. Das ich die Segmente, während des defragmentierens, virtuell in einen anderen Bereich verlagern möchte dient eher der Performance (hat aber auch noch ein paar praktische Gründe), dann müssen die anderen Segmente, die direkt im physischen Speicher angesprochen werden, nicht das Paging benutzen. Man könnte die Segmente, während des defragmentierens, auch im normalen linearen Speicher lassen aber dann müsste man für diesen Bereich, in dem der physische Speicher eigentlich immer 1:1 gemappt ist, das Paging anschalten und das kostet etwas Performance bei allen Programmen. Wenn nur das eine Segment in einem speziellen Bereich liegt dann ist nur das eine Programm betroffen und das auch nur bei Zugriffen auf das eine Segment welches gerade verschoben/defragmentiert wird.
Der Performanceverlust durch das Paging kann durchaus hoch sein, das 4-stufige Paging von x86_64 im Long-Mode soll angeblich ca. 20% kosten. Deshalb versuchen AMD und Intel die TLBs möglichst groß und flexibel zu machen und die OSe versuchen möglichst große Pages zu nutzen um diesen negativen Effekt möglichst klein zu halten.

Swapping effizient zu machen bringt meiner Meinung nach wenig, aber das hängt auch grundsätzlich vom Anwendungszweck ab. Mein System mit derzeit 2 GB RAM unter Linux fängt nur damit an, wenn irgendein Programm Amok läuft. Effektiv wird es nie genutzt.

Das Swapping ist sicher nicht besonders performancerelevant aber eine zügige Arbeitsweise wird bestimmt nicht schaden.

Meine Meinung ist es, auf Paging ganz zu verzichten oder aber es vollständig zu implementieren und dann auch zu nutzen. Alles andere ist verschwendetes Silizium.

Da hast Du völlig recht. Deshalb möchte ich Paging ordentlich implementieren und es genau dafür nutzen wofür es einst ersonnen wurde "virtuelle Speichermehrung". Das dazu noch ein bisschen sonstige Speicher-Magie kommt ist bei Segmentierung natürlich mehr als nur willkommen.

Zum richtigen Defragmentieren ist es eigentlich nicht nötig, wenn du die gesamte Segmentverwaltung dem Betriebssystem obliegt und Programme nur ihre eigenen Segmente und ein unverschiebbares Systemsegment verwenden können.

Ich verstehe nicht was Du damit meinst. Natürlich dürfen Programme nur innerhalb ihrer eigenen Segmente arbeiten (der Kernel darf natürlich mehr). Die eigenen Segmente, welche alle in der zum Programm gehörenden LDT stehen, sind quasi der Kontext. Die Programme haben dabei keinen Einfluss darauf wo sich ihre Segmente im linearen Speicher befinden, das wissen die noch nicht mal (außer natürlich Geräte-Treiber die ihrem Gerät mitteilen müssen wo im physischen Speicher das Gerät Daten ablegen/holen soll, dazu muss ein Segment aber gelockt werden und ist damit nicht mehr verschiebbar, sieh Dir dazu mal XMS an).

Mit Paging könntest du das Defragmentieren durch ein Ummappen sehr schnell lösen und im Hintergrund später die reale Umsortierung machen, das halte ich aber (insbesondere bei mehreren CPUs) für ein sehr kompliziertes Unterfangen.

Ja, genau darum geht es mir. Das ich mir da keine leichte Übung vorgenommen hab ist mir bewusst. Warum sollte das mit mehreren CPUs schwerer werden?

Gibt es vielleicht die Möglichkeit, nur sehr wenige Pages (vielleicht 16) zu erlauben ....

Das ist viel zu grob. Ein Segment muss bei mir immer mindestens eine minimale Page (also das was das Paging als kleinste Page unterstützt, 4 kByte auf der 32 Bit-Version meiner Plattform, das ist dann auch das minimale Alingment der Segment-Basis-Adresse) ausfüllen, diese minimale Page können sich nicht mehrere Segmente teilen (sonst wäre das defragmentieren nicht möglich). Erst wenn größere Pages benutzt werden können in einer größeren Page auch mehrere Segmente drin liegen. Die Segmentierung weiß davon ja nichts und die größeren Pages dienen nicht der Verwaltung sondern nur der Performance (so wie auf allen anderen Plattformen auch).

Segmentierung finde ich prinzipiell toll, nur die damit einhergehenden Probleme (die es nur für knappes oder zersplittertes RAM gibt) finde ich schwierig zu lösen.

Segmentierung, gefällt mir schon lange. Aber ich finde die ist selbst im 386-Protected-Mode nur sehr halbherzig umgesetzt. Theoretisch ließe sich meine OS-Idee auch dort umsetzen aber da gibt es keinen Pfad zu 64 Bit (im Long-Mode gibt es keine Segmentierung mehr), außerdem finde ich die PC-Plattform (mitsamt der CPU-Architektur) einfach nur echt Scheiße.

Dynamische Segmentgrößen vereinfachen das etwas.

Dynamische Segmente sind für mein Konzept die Kern-Idee, ohne dem geht nichts davon.

In meiner Implementierung wäre das Defragmentieren allerdings atomisch, so dass der Kernel sich ungestört um die Speicherverwaltung kümmern kann. Damit gibst du dann allerdings die Echtzeitfähigkeit komplett auf - es sei denn, die Programme sind "lieb".

Atomische Defragmentierung will ich nicht. Programme die freiwillig auf bestimmte Segmente mal nicht zugreifen stelle ich mir auch sehr schwierig vor, da müsste man vor jedem Speicherzugriff erst den Segment-Selector prüfen ob der auf der roten Liste, mit den momentan verbotenen Segmenten, steht.

Naja, sind alles nur Gedankensplitter.

Dafür ist dieser Thread doch da.


Grüße
Erik

[Svenska]

Hallo,

aber man kann - angenommen, die Segmente sind hinreichend groß - die Segmente im physischen RAM verschieben.

Hä?? Was hat die Größe der Segmente damit zu tun?

Wenn der RAM voll ist, kannst du ganze Segmente nicht mehr ohne Auslagerung verschieben, ausgegangen von "kein Paging".

Dazu benötigt man kein Paging,

Dann muss das verschieben atomar sein, das betreffende Programm muss während dieser Zeit schlafen. Bei großen Segmenten ist das schon ziemlich doof, das will ich den Programmen nicht zumuten.

Also mein Core2Duo hat unter Linux eine Speicherperformance von ~2 GB/s. Um also ein paar MB umherzuschieben, gehen dir ein paar Mikrosekunden (maximal ms) verloren.

Schlafen legen müsstest du nur die beiden Programme, deren Segmente gerade umhergeschoben werden.

Bei SMP muss der OS-Kernel dann auch noch sicherstellen das wirklich keiner der Threads des betreffenden Programms auf anderen CPUs laufen, ist zwar machbar aber umständlich. Bei "beerbten" Segmenten (wegen shared Memory oder IPC) ist das noch schwieriger, weil man noch mehr Programme (alle ihre Threads) deaktivieren muss. Das atomare verschieben von Segmenten würde quasi das gesamte System lahmlegen.

Das System sollte an sich schon nicht stehenbleiben, nur hängt bei mir im Hinterkopf halt immernoch der Gedanke, wann denn die Defragmentierung nötig ist. Das ist sie kurz vorm Swappen (oder bei hinreichend langer Uptime mit vielen sich schlecht verhaltenden(*) Programmen). Also im Zweifelsfall fast nie.

Wenn meine Festplatte beschäftigt ist (oder der Auslagerungsmarathon beginnt), dann steht mein Linux auch komplett. Für ein Allzwecksystem ist das relativ normal, und alles unter ner gelegentlichen Viertelsekunde merkt man nicht.

(*): Schlecht verhalten tun sich Programme, welche einen großen Puffer alloziieren, diesen nutzen und etwas ausrechnen, für das Ergebnis aber keinen weiteren Puffer alloziieren, sondern nur den nicht mehr genutzten Teil freigeben. Sehr schlimm wird das, wenn im Puffer dann der letzte Teil behalten und der große erste Teil freigegeben wird. Das ist den uClibc-Leuten aufgefallen und stellt für diese ein großes Problem dar.

die Programme dürfen dann aber keine Verweise über Segmentgrenzen erlauben.

Was genau meinst Du? Offsets für ein bestimmtes Segment dürfen nur vom dessen Minimum bis zu dessen Maximum gehen (beides ist bei mir im Segment-Descriptor eingetragen, bei x86 gibt es kein Minimum dort fangen Segmente immer mit Offset 0 an), alles andere löst beim Speicherzugriff eine Exception aus. So einen Mist wie die unflexieble Segmentierung im x86-Real-Mode will ich definitiv nicht machen.

Achso, naja ich gehe immer davon aus, dass ein Segment bei 0 anfängt (ist für mich einer der Hauptvorteile) und eine Segmentnummer dazukommt. Wenn du den Zugriff auf programmfremde Segmente hardwareseitig unterbindest (Speicherschutz), ist das kein Problem mehr. Ich kenne halt nur die simple Mechanik des 8086 Wenn dort ein Programm anfängt mit "ich will aber 0x5:0x00f0" (z.B. die IPC-Tabelle eines anderen Prozesses), kannst du Segment 5 derweil ja nicht verschieben. Mit Speicherschutz geht das eh nicht, also ist es egal.

Das Swappen von ganzen Segmenten ist an sich gar nicht so abwegig, das meinte ich schon ernst.

Das bedeutet aber dass das betreffende Programm komplett deaktiviert ist wenn eines seiner Segmente nicht im RAM ist. Wenn z.B. ein großes Office-Programm (falls sowas jemals auf meinem OS laufen sollte) für jeden Tastendruck wieder komplett in den Speicher muss obwohl der Key-Event-Handler nur den Text um einen Buchstaben erweitern müsste und nur das aktualisieren der Bildschirmdarstellung über die GUI antriggern müsste. Das stelle ich mir wahrlich nicht praktikabel vor.

Wenn der RAM alle ist, verlierst du mindestens einen Faktor 100-1000 für den RAM-Zugriff, ob du nun das Office-Paket komplett oder zu einem Großteil ausgelagert hast, spielt da eine untergeordnete Rolle. Am besten, man sieht genug RAM vor, seit wenigen Jahren ist das ja endlich möglich. Swapping ist eine Notlösung und war (auch) einen Grund für Paging überhaupt. Der einzige Vorteil mit Paging ist die feinere Granlarität und damit die Möglichkeit, geringe Knappheit gut abzufangen.

Davon würde ich aber nicht mehr ausgehen; dann lieber genug physischen RAM (ggf. nachsteckbar) vorsehen.

Ich möchte den linearen Speicher wirklich im Hintergrund bei laufendem System defragmentieren können, wenn das nicht geht ist das Konzept mit der Segmentierung IMO nicht tragfähig.

Hängt vom Anwendungsfall ab.

Das Umsortieren des Speichers (Verschieben der Segmente) erfordert ohnehin eine wie auch immer geartete Auslagerung.

Nicht unbedingt. ...

Wenn du Umsortieren musst, weil der RAM knapp wird, dann schon. Ich hätte dann halt auf ein Zwischenmedium ausgelagert, du lagerst in den virtuellen Adressraum aus. Das Umsortieren bei zu sehr zerstückeltem RAM sollte dagegen auch im physischen Bereich nicht zu lange dauern, da es dort meist um viele sehr kleine Segmente geht, für die noch Platz vorhanden sollte. Sonst ist der RAM voll und es tritt Fall 1 ein.

Wenn in der Zeit des Defragmentierens die Gesamtsystemleistung um 5-25% sinkt (du möchtest sicherlich kein 4stufiges Paging haben), stört das auch nicht weiter, wäre sogar eine starke Verbesserung gegenüber dem Halt der betreffenden Programme. Bei einer angenommenen Performance von 200 MIPS verlierst du dann vielleicht 20-30 MIPS, das merkt man nichtmal - solange man die Anwendung nicht auf die CPU zuschneidet (d.h. Echtzeitbetrieb).

Swapping effizient zu machen bringt meiner Meinung nach wenig, aber das hängt auch grundsätzlich vom Anwendungszweck ab. Mein System mit derzeit 2 GB RAM unter Linux fängt nur damit an, wenn irgendein Programm Amok läuft. Effektiv wird es nie genutzt.

Das Swapping ist sicher nicht besonders performancerelevant aber eine zügige Arbeitsweise wird bestimmt nicht schaden.

Ich würde versuchen vorzusorgen, dass dieser Fall nie eintritt. Er sollte ohnehin sehr selten sein.

Mit Paging könntest du das Defragmentieren durch ein Ummappen sehr schnell lösen und im Hintergrund später die reale Umsortierung machen, das halte ich aber (insbesondere bei mehreren CPUs) für ein sehr kompliziertes Unterfangen.

Ja, genau darum geht es mir. Das ich mir da keine leichte Übung vorgenommen hab ist mir bewusst. Warum sollte das mit mehreren CPUs schwerer werden?

Im Endeffekt sortierst du den physischen Speicher ja trotzdem um, auch wenn die MMU dazwischen sitzt. Du müsstest halt atomar dafür sorgen, dass für jedes verschobene Fragment eines Segments die Pagingtabelle korrekt ist. Sonst hat das Programm zwar eine nette virtuelle Adresse zum Arbeiten und greift trotzdem ins Leere, wenn die MMU auf den falschen Speicher zeigt (der da gerade wegverschoben wurde).

Gibt es vielleicht die Möglichkeit, nur sehr wenige Pages (vielleicht 16) zu erlauben ....

Das ist viel zu grob. ...

Zum Defragmentieren würde es aber reichen, wenn du nämlich je zwei Segmente in das Paging aufnimmst und dann im Hintergrund sortierst. Da die Tabelle dann extrem klein bleibt, kannst du sie in ein spezielles Register eintragen, wo die Lookups kostenlos sind und du keine Performance verlierst. Paging kostet ja nur deshalb so viel, weil die Pagingtabelle im RAM liegt und du dadurch Unmengen an zusätzlichen RAM-Zugriffen hast, die vom Cache nur ungenügend abgefedert werden können. Oder seh ich da grundsätzlich was falsch?

In meiner Implementierung wäre das Defragmentieren allerdings atomisch, so dass der Kernel sich ungestört um die Speicherverwaltung kümmern kann. Damit gibst du dann allerdings die Echtzeitfähigkeit komplett auf - es sei denn, die Programme sind "lieb".

Atomische Defragmentierung will ich nicht. Programme die freiwillig auf bestimmte Segmente mal nicht zugreifen stelle ich mir auch sehr schwierig vor, da müsste man vor jedem Speicherzugriff erst den Segment-Selector prüfen ob der auf der roten Liste, mit den momentan verbotenen Segmenten, steht.

Naja, wenn du keinen Speicherschutz hast, dann kann sich jedes Programm eine Segmentnummer zusammenbauen und dort zugreifen. Wenn du das nicht möchtest, dann musst du bei jedem Segmentzugriff nachschauen, ob das betreffende Segment in der weißen Liste des Prozesses steht...

Gruß,
Svenska

[erik.vikinger]

Hallo,

Wenn der RAM voll ist, kannst du ganze Segmente nicht mehr ohne Auslagerung verschieben, ausgegangen von "kein Paging".

Ach so, Du bist von mit ohne Paging ausgegangen. Paging ist für mich integraler Bestandteil meines Konzepts, und damit implizit immer mit dabei.

Also mein Core2Duo hat unter Linux eine Speicherperformance von ~2 GB/s.

Meine FPGA-Lösung kommt hoffentlich auf mehr als ein Zwanzigstel davon (also etwa gut 100 MBytes/s Kopier-Transferrate), und dafür werde ich mich schon anstrengen müssen. Damit möchte ich sicher nicht Segmente mit eventuell mehreren GBytes atomar verschieben müssen. Vielleicht wird es mehr wenn der Kopiervorgang von der CPU gemacht wird an welcher der Speicher dran hängt, damit würde man wenigstens die Latenzzeiten der Kommunikation zwischen den CPUs umgehen und die DRAM-Controller im Spartan 6 bringen bestimmt auch deutlich mehr als 200 MBytes/s.

Um also ein paar MB umherzuschieben

Die Segmente können schon richtig groß werden, es hindert doch niemand die Programme daran mal ordentlich Speicher zu allozieren. Zumindest dürfen speicherhungrige Programme kein KO-Kriterium für mein Konzept sein.

Das System sollte an sich schon nicht stehenbleiben,

Aber die Auswahl an lauffähigen Prozessen könnte schon erheblich eingeschränkt sein. Außerdem dürften vor allem Programme die gerade im User-Focus stehen (und daher auf User-Aktionen reagieren müssen) am ehesten ihre Segmente vergrößern wollen und da fallen dem User Totzeiten natürlich als erstes auf.

nur hängt bei mir im Hinterkopf halt immernoch der Gedanke, wann denn die Defragmentierung nötig ist. Das ist sie kurz vorm Swappen (oder bei hinreichend langer Uptime mit vielen sich schlecht verhaltenden(*) Programmen). Also im Zweifelsfall fast nie.

Naja, das ist wie auf einer Festplatte, nach langer Benutzung wird die Belegung des physischen Speichers schon ziemlich zerklüftet sein. Ich denke es wird ziemlich schnell passieren das Defragmentierung nötig wird, mit steigender Speicherauslastung natürlich noch schneller. Ich befürchte das ich da selbst mit möglichst intelligenter Segment-Allozierung (z.B. Best-Fit oder hinter jedem Segment was frei lassen) nicht lange ohne Defragmentieren auskomme.

Wenn meine Festplatte beschäftigt ist (oder der Auslagerungsmarathon beginnt), dann steht mein Linux auch komplett.

Also mein Linux steht da nicht komplett, das Linux versucht doch als erstes Pages auszulagern die schon eine Weile nicht mehr benutzt wurden. Durch das Auslagern wird zwar die Platte beschäftigt (was ansich keine CPU-Zeit kostet) aber wenn Linux die Pages gut wählt dann merken die Programme davon gar nichts. Ich gehe davon aus das die Page-Ersetzungs-Strategien von Linux ziemlich gut sind.

Schlecht verhalten tun sich Programme, welche einen großen Puffer alloziieren, diesen nutzen und etwas ausrechnen, für das Ergebnis aber keinen weiteren Puffer alloziieren, sondern nur den nicht mehr genutzten Teil freigeben. Sehr schlimm wird das, wenn im Puffer dann der letzte Teil behalten und der große erste Teil freigegeben wird.

Das wäre aber bei meinen Segmenten eventuell auch ein Problem. Der Heap eines Programms liegt in mehreren Segmenten für unterschiedliche Objekt-Größen (ich denke da so an vielleicht 6 bis 10 Segmente, also von 64 Bytes an für jede weitere 4er-Potenz ein extra Heap-Segment) um die interne Fragmentierung möglichst klein zu halten, damit wäre ein realloc recht aufwendig wenn dabei das Objekt in ein anderes Segment verschoben wird. Diese Probleme treffen aber auch Programme auf Flat-Memory-Systemen, okay da kann man immerhin mitten aus dem virtuellen Raum einfach ein paar Pages freigeben falls diese komplett unbenutzt sind. Wenn wir von einem Programm ausgehen das sehr viele kleine Blöcke, mit leicht unterschiedlicher Größe, alloziert und in ungeordneter Reihenfolge teilweise wieder frei gibt dann dürften ziemlich viele Pages nur teilweise benutzt sein also das Programm deutlich mehr virtuellen Speicher belegen als eigentlich notwendig währe. Diese innere Fragmentierung in Grenzen zu halten ist Aufgabe der malloc-Implementierung in der libc (da kann ich aus einem reichhaltigem Fundus unterschiedlichster Ansätze und Forschungstheorien wählen), gegen die externe Fragmentierung hat mein OS die Segmente die es nach belieben Defragmentieren kann.
Da jedes Segment für sich unabhängig wachsen kann hab ich mit den mehreren Heap-Segmenten auch keine Probleme, wenn ein Flat-Memory-Programm in seinem einen virtuellen Adressraum mehrere Bereiche für unterschiedlich große Objekte vorsieht (aus denen malloc/realloc sich bedienen) dann könnte es passieren das dieser Bereich überproportional wächst und ihm ein anderer Bereich im Weg ist (die libc weiß ja nicht was das Programm für Objekte erstellt, es gibt bestimmt auch Programme wo 90% des Speicherbedarfs auf Objekte mit immer gleicher Größe entfällt). Bei meinem Konzept kann jedes Segment für sich und unabhängig wachsen, nur der verfügbare RAM (+ Swap-Space) geben da die Grenzen vor. Dieses Flat-Memory-Problem tritt auch bei Programmen mit sehr vielen Threads auf, wenn dann mal einer dieser Threads sehr viel Stack benötigt kann es sein das in dem virtuellen Adressraum wo der Stack hinwachsen möchte schon ein anderer Stack liegt. Bei meinen Heap-Segmenten soll meine libc auch das Schrumpfen unterstützen falls dort am Ende wieder viel freier Speicher entsteht, bei den Stack-Segmenten bin ich mir nicht sicher ob der OS-Kernel das können soll (dazu müsste der Stack-Pointer beobachtet werden). Mit meinen dynamischen Segmenten umgehe ich die klassischen Probleme des Speicher-Layouts von Flat-Memory-Programmen.

Das ist den uClibc-Leuten aufgefallen und stellt für diese ein großes Problem dar.

Okay, uCLinux hat schon aufgrund seines Konzeptes ein paar Probleme mehr. Da werden die Nachteile aus verschiedenen Welten kombiniert (und die jeweiligen Vorteile beseitigt), Speicherverwaltung ganz ohne Hardwareunterstützung ist eben nicht so einfach.

Achso, naja ich gehe immer davon aus, dass ein Segment bei 0 anfängt (ist für mich einer der Hauptvorteile) und eine Segmentnummer dazukommt.

Das meine Segmente nicht bei 0 anfangen müssen ist eher ein nettes Zusatzfeature, außerdem hatte ich in den Descriptoren noch Platz. Die meisten Segmente werden wohl ihre Offsets ganz normal bei 0 anfangen lassen.

Wenn du den Zugriff auf programmfremde Segmente hardwareseitig unterbindest (Speicherschutz)

Ja, das habe ich vor.

Ich kenne halt nur die simple Mechanik des 8086 ...

An den x86-Real-Mode denken die meisten Leute wenn das Wort "Segmentierung" fällt (falls sie alt genug sind). Die Möglichkeiten die bereits der 386-Protected-Mode bietet (auch wenn das nur ein bescheidener Vorgeschmack auf richtige Segmentierung ist) sind selbst unter den erfahrenen Programmierern der überwiegenden Mehrheit völlig unbekannt. Wenn ich mit Leuten über meine Ideen rede dann darf ich immer erst mal anfangen zu erklären was dynamische Segmentierung wirklich ist.

Wenn der RAM alle ist, verlierst du mindestens einen Faktor 100-1000 für den RAM-Zugriff,

Aber nur auf Speicher der auch wirklich ausgelagert wurde.

ob du nun das Office-Paket komplett oder zu einem Großteil ausgelagert hast, spielt da eine untergeordnete Rolle.

Das sehe ich anders. Viele Programme benutzen, über einen kurzen bis mittleren Zeitraum betrachtet, nur einen kleinen Teil des allozierten Speichers. Von einem Programm zwangsläufig alles auslagern zu müssen, anstatt nur den tatsächlich unbenutzten Teil rauszuwerfen, erscheint mir wahrlich ungeschickt. Ersteres bedeutet dass das Programm komplett lahmgelegt ist und Letzteres kann bedeuten das es ohne (spürbare) Einschränkungen weiter arbeitet. Für jeden Tastendruck in einem Office-Programm mal eben über 100 MBytes einzulesen (und andere 100 MBytes vorher rauszuwerfen) ist sicher nicht praktikabel.

Swapping ist eine Notlösung und war (auch) einen Grund für Paging überhaupt. Der einzige Vorteil mit Paging ist die feinere Granlarität und damit die Möglichkeit, geringe Knappheit gut abzufangen.

Paging ist IMHO die einzigste Möglichkeit Knappheit für alle Programme fair abzufangen.

Ich möchte den linearen Speicher wirklich im Hintergrund bei laufendem System defragmentieren können, wenn das nicht geht ist das Konzept mit der Segmentierung IMO nicht tragfähig.

Hängt vom Anwendungsfall ab.

Mein geplanter Anwendungsfall ist ein allgemein nutzbarer PC. Daher darf ich auch keine Annahmen über die Programme machen. Es muss z.B. auch möglich sein Segmente zu erstellen die größer als der physische RAM sind, dass das nicht unbedingt geschickt/performant ist ist mir klar.

Wenn du Umsortieren musst, weil der RAM knapp wird, dann schon.

RAM-Knappheit ist der Grund fürs Swappen nicht fürs Defragmentieren.

Ich hätte dann halt auf ein Zwischenmedium ausgelagert, du lagerst in den virtuellen Adressraum aus. Das Umsortieren bei zu sehr zerstückeltem RAM sollte dagegen auch im physischen Bereich nicht zu lange dauern, da es dort meist um viele sehr kleine Segmente geht, für die noch Platz vorhanden sollte. Sonst ist der RAM voll und es tritt Fall 1 ein.

Ich glaube Du gehst davon aus das jeder Aufruf von malloc in einem User-Space-Programm ein neues Segment liefert. Das wäre echte Speicher-Verschwendung und für das OS ziemlich aufwändig. Den Heap verwalten die Programme selber, mit ihrer libc (die natürlich auch von mir kommen muss), siehe oben. Außerdem würden mir dann ziemlich schnell die Einträge in der LDT ausgehen. Natürlich können die Programme für bestimmte Dinge auch zusätzliche Segmente anfordern, z.B. ein Verschlüsselungsprogramm könnte die Keys in einem extra Segment halten und dieses Segment gegen das Swappen sperren lassen damit die unverschlüsselten Keys nicht auf die Platte kommen. Die Segmente in meinem System werden im Durchschnitt eher ziemlich groß sein.

Wenn in der Zeit des Defragmentierens die Gesamtsystemleistung um 5-25% sinkt (du möchtest sicherlich kein 4stufiges Paging haben), stört das auch nicht weiter, wäre sogar eine starke Verbesserung gegenüber dem Halt der betreffenden Programme. Bei einer angenommenen Performance von 200 MIPS verlierst du dann vielleicht 20-30 MIPS, das merkt man nichtmal - solange man die Anwendung nicht auf die CPU zuschneidet (d.h. Echtzeitbetrieb).

Die Performance sinkt beim Defragmentieren nur in den betroffenen Segmenten und das ist natürlich nicht so arg schlimm (vor allem weniger schlimm als wenn alle Programme leiden müssten). Um diesen Verlust so klein wie nur möglich zu halten soll das OS möglichst große Pages verwenden (deshalb will ich möglichst viele Page-Größen unterstützen) und der flexible TLB (der mit allen Page-Größen gut zurecht kommt) soll sein übriges dazu tun. Im 32 Bit-System wird nur ein 2-stufiges Paging verwendet (vom 586 abgeschaut, nur mit mehr unterstützen Page-Größen). Bei der 64 Bit-Ausführung bin ich mir noch nicht sicher, mit einem 3-stufigem Paging läuft das auf 512 kByte als kleinste Page-Größe hinaus (ist dann schon recht oft eine gewisse Speicher-Verschwendung) und mit nem 4-stufigem Paging komme ich auf 64 kByte als kleinste Page-Größe (was im Hinblick auf den Verschnitt schon etwas freundlicher aussieht, aber wohl etwas schlechter performt). Ich möchte mit den guarded-Page-Tables aber Abkürzungen durch die Tabellen ermöglichen, so das die 4 Stufen (bei den 64 kByte-Pages) sich auf 2 reduzieren lassen wenn nur 1 TByte oder weniger virtueller Speicher benötigt wird.
Ob ich im Spartan 6 überhaupt annähernd 200 MIPS erreiche wage ich stark zu bezweifeln, ich hoffe auf etwa 50 MIPS zu kommen und damit einem 486 mit 100 MHz Paroli bieten zu können, das erfordert natürlich leistungsfähige Befehle und einen guten Compiler. Ich denke gegen den 486 werden mein riesiges Register-File und die 3-Operanden-Befehle den entscheidenden Vorteil bringen, die 486 hatten noch kein Register-Renaming und ein damit verbundenes großes physisches Register-File, so das ich für den selben Algorithmus deutlich weniger Speicherzugriffe und MOV-Befehle benötige.

Warum sollte das mit mehreren CPUs schwerer werden?

Im Endeffekt sortierst du den physischen Speicher ja trotzdem um, auch wenn die MMU dazwischen sitzt. Du müsstest halt atomar dafür sorgen, dass für jedes verschobene Fragment eines Segments die Pagingtabelle korrekt ist. Sonst hat das Programm zwar eine nette virtuelle Adresse zum Arbeiten und greift trotzdem ins Leere, wenn die MMU auf den falschen Speicher zeigt (der da gerade wegverschoben wurde).

Ja. Ich möchte die betreffende Page (zerstückelt in die kleinste Page-Größe) zum Verschieben als nicht-präsent markieren, alle anderen CPUs per Broadcast-Message informieren diesen Bereich aus dem TLB zu tilgen, den Inhalt kopieren und als letztes die neue physische Adresse in die Page-Table Eintragen und wieder als präsent markieren. Falls während der kurzen Zeit des umkopierens auf einer der anderen CPUs eine Page-Not-Present-Exception auftritt dann wird der Exception-Handler im Paging-Directory feststellen was Sache ist und einfach aktiv warten (pollen) bis der Kopier-Vorgang abgeschlossen ist (also die Page wieder benutzbar ist) und dann wieder zum Programm zurückkehren, wenn die CPU dann den Speicherzugriff noch mal probiert geht wieder alles. Das Programm (bzw. der eine Thread) friert für nicht mal eine Millisekunde (bei 100 MByte/s und 4 kByte/Page sind das 40 µs) ein und schon geht es weiter, ich denke das ist tolerabel und auch sicher recht selten (wäre schon ein guter Zufall wenn das Programm genau in dem Moment was von genau der Page will wo diese gerade verschoben wird).

Zum Defragmentieren würde es aber reichen, wenn du nämlich je zwei Segmente in das Paging aufnimmst und dann im Hintergrund sortierst.

Hä?? Was hat defragmentieren mit sortieren zu tun und warum soll das genau 2 Segmente betreffen? Es ist durchaus möglich das mehrere Segmente der Defragmentierung bedürfen da sie vor kurzem vergrößert werden sollten aber nicht wachsen konnten weil dahinter schon was anderes lag (und kurzerhand in den virtuellen Speicher umgemappt wurden).

Paging kostet ja nur deshalb so viel, weil die Pagingtabelle im RAM liegt und du dadurch Unmengen an zusätzlichen RAM-Zugriffen hast, die vom Cache nur ungenügend abgefedert werden können. Oder seh ich da grundsätzlich was falsch?

Das siehst Du ganz genau richtig.
Ich frage mich wie das wird wenn wir tatsächlich etliche TByte RAM haben und Programme benutzen die das auch nutzen (wollen), dann sind die virtuellen Adressräume bei den Flat-Memory-Systemen nicht mehr so dünn besetzt und damit einige Abkürzungen durch die Paging-Tabellen nicht mehr möglich, auch das Konzept des Itanium dürfte dann problematisch werden.

Naja, wenn du keinen Speicherschutz hast, dann kann sich jedes Programm eine Segmentnummer zusammenbauen und dort zugreifen.

Richtig guter Speicherschutz ist das Kern-Ziel welches ich mit meiner Segmentierung erreichen will.

Wenn du das nicht möchtest, dann musst du bei jedem Segmentzugriff nachschauen, ob das betreffende Segment in der weißen Liste des Prozesses steht...

Jain, die LDT wird natürlich nicht bei jedem Speicherzugriff befragt sondern nur wenn ein Selector in ein Segment-Register geladen werden soll bzw. wenn der Segment-Descriptor in die zugehörigen Shadow-Register geladen/decodiert wird. Eine Leaf-Funktion die nur mit den als Parameter übergebenen Pointen und globalen Variablen arbeitet braucht sowas überhaupt gar nicht zu tun. Auch sonst werde ich alles unternehmen damit die LDT möglichst selten benötigt wird.


Grüße
Erik

[Svenska]

Hallo,

Um also ein paar MB umherzuschieben

Die Segmente können schon richtig groß werden, es hindert doch niemand die Programme daran mal ordentlich Speicher zu allozieren. Zumindest dürfen speicherhungrige Programme kein KO-Kriterium für mein Konzept sein.

Naja, nur wenn du sehr viele sehr große Segmente hast, ist das Problem der Fragmentierung nicht gegeben, denn die tritt hauptsächlich bei sehr kleinen (bzw. von vorne verkürzten) Segmenten auf. Das sind in der Regel nur ein paar MB oder sogar weniger.

Wenn du natürlich möglichst fleißig Segmente zusammenfassen möchtest, damit die Segmente möglichst groß werden und du innerhalb der Segmente den Verwaltungsaufwand hast, dann kommt zu der externen Fragmentierung (Segmente im physischen Adressraum) auch noch interne Fragmentierung (malloc/realloc in den Segmenten) dazu. Stell ich mir unangenehm vor.

Das System sollte an sich schon nicht stehenbleiben,

Aber die Auswahl an lauffähigen Prozessen könnte schon erheblich eingeschränkt sein. Außerdem dürften vor allem Programme die gerade im User-Focus stehen (und daher auf User-Aktionen reagieren müssen) am ehesten ihre Segmente vergrößern wollen und da fallen dem User Totzeiten natürlich als erstes auf.

Das meinte ich mit begrenzter Echtzeitfähigkeit. Den Programmen das beizubringen ist ja kein Problem, gewisse Segmente braucht man nicht verschieben, wenn man sie im Voraus günstig platziert (z.B. Treiber).

Ich befürchte das ich da selbst mit möglichst intelligenter Segment-Allozierung (z.B. Best-Fit oder hinter jedem Segment was frei lassen) nicht lange ohne Defragmentieren auskomme.

Ich vermute mal schon, allerdings immer unter der Annahme von genügend physischem RAM.

Den Garbage-Collector in die Idlezeit zu verlegen mag übrigens auch gut gehen, und in einem normalen System sind die meisten Anwendungen eh nicht aktiv. Sie werden nur aktiv, wenn sie vom System (oder von der Hardware) gerufen werden; bei einer Uptime von nem knappen Monat finden sich bei mir einige Prozesse mit CPU-Zeit von Sekunden. Die kann man prinzipiell immer verschieben.

Auf einem normalen PC hast du in der Regel genug Idle-Zeit für solche Spielereien, ansonsten kannst du die natürlich jederzeit auch garantieren. (Wobei garantierter Leerlauf eher nach Überhitzungsschutz klingt...)

Wenn meine Festplatte beschäftigt ist (oder der Auslagerungsmarathon beginnt), dann steht mein Linux auch komplett.

Also mein Linux steht da nicht komplett, das Linux versucht doch als erstes Pages auszulagern die schon eine Weile nicht mehr benutzt wurden. Durch das Auslagern wird zwar die Platte beschäftigt (was ansich keine CPU-Zeit kostet) aber wenn Linux die Pages gut wählt dann merken die Programme davon gar nichts. Ich gehe davon aus das die Page-Ersetzungs-Strategien von Linux ziemlich gut sind.

Das mag sein, aber wenn die Maus ruckelt und auf Tastendrücke keine Reaktion kommt, dann steht für den Nutzer das System (bis der OOM-Killer anläuft). Ansonsten tritt das Phänomen nicht auf. In dem Augenblick, wo Pages ausgelagert werden müssen, die noch gebraucht werden, ist ohnehin alles verloren. Bis zu diesem Zeitpunkt kann man Buffers/Caches einfach wegwerfen.

Das ist den uClibc-Leuten aufgefallen und stellt für diese ein großes Problem dar.

Okay, uCLinux hat schon aufgrund seines Konzeptes ein paar Probleme mehr. Da werden die Nachteile aus verschiedenen Welten kombiniert (und die jeweiligen Vorteile beseitigt), Speicherverwaltung ganz ohne Hardwareunterstützung ist eben nicht so einfach.

Besser als uClinux geht es fast nicht. Trotz der ganzen Probleme, die mit der Speicherfragmentierung einhergehen, läuft das System trotzdem. Gut, in der Regel mit relativ einfachen und kleinen Programmen, aber "out of memory" bei zerstückeltem RAM gibt es selten unter 75% RAM-Auslastung. Und solche Situationen merkt man auch schon früher als Fall für den Garbage Collector.

Wenn der RAM alle ist, verlierst du mindestens einen Faktor 100-1000 für den RAM-Zugriff,

Aber nur auf Speicher der auch wirklich ausgelagert wurde.

Nicht während des Aus- und wieder Einlagerns. Die halte ich für das größte Problem, denn während der Kernel sein Speichermanagement mit der Festplatte abquatschen muss, geht nicht wirklich viel. Besonders, wenn die Page, in der der Taskzustand steht, fehlt und das Programm nicht als schlafend markiert werden kann. Ich halte das Speichermanagement für zu kritisch, als dass man nebenher die unbelasteten Anwendungen weiterlaufen lassen könnte.

Sicher, alle anderen Programme können am Ende des Marathons weiterlaufen, das Problem sehe ich heutzutage aber eher darin, dass irgendein Programm amok läuft, schnell viel RAM füllt, das System in die Ecke drängt bis es dann vom Kernel OOM-gekillt wird.

Swap als Arbeitsgrundlage braucht man mMn nicht mehr. Dazu ist RAM zu billig geworden.

ob du nun das Office-Paket komplett oder zu einem Großteil ausgelagert hast, spielt da eine untergeordnete Rolle.

Das sehe ich anders. Viele Programme benutzen, über einen kurzen bis mittleren Zeitraum betrachtet, nur einen kleinen Teil des allozierten Speichers. Von einem Programm zwangsläufig alles auslagern zu müssen, anstatt nur den tatsächlich unbenutzten Teil rauszuwerfen, erscheint mir wahrlich ungeschickt.

Muss das Programm denn nur aus drei Segmenten bestehen? Wer hindert dich denn daran, für die Eventhandler ein eigenes Segment vorzusehen (welches dann, da es eh zu klein ist, nicht ausgelagert würde)?

Ersteres bedeutet dass das Programm komplett lahmgelegt ist und Letzteres kann bedeuten das es ohne (spürbare) Einschränkungen weiter arbeitet. Für jeden Tastendruck in einem Office-Programm mal eben über 100 MBytes einzulesen (und andere 100 MBytes vorher rauszuwerfen) ist sicher nicht praktikabel.

Der Tastendruck gehört entweder woanders verarbeitet, oder aber das Office-Paket nicht ausgelagert, wenn es eh noch benutzt wird.

Ich möchte den linearen Speicher wirklich im Hintergrund bei laufendem System defragmentieren können, wenn das nicht geht ist das Konzept mit der Segmentierung IMO nicht tragfähig.

Hängt vom Anwendungsfall ab.

Mein geplanter Anwendungsfall ist ein allgemein nutzbarer PC. Daher darf ich auch keine Annahmen über die Programme machen. Es muss z.B. auch möglich sein Segmente zu erstellen die größer als der physische RAM sind, dass das nicht unbedingt geschickt/performant ist ist mir klar.

Außerdem gehst du davon aus, dass die Programme von der Segmentierung nichts wissen (oder mitkriegen können), und somit dein System nicht entlasten können. Das sehe ich wie, wenn sich zwei Deutsche auf Englisch unterhalten - es funktioniert, ist aber schon im Ansatz falsch. Wenn du den Programmen keine segmentfreundliche Nutzung zugestehst, dann kann das nicht performant werden, einfach weil du auf der falschen Architektur arbeitest.

Heutzutage ist es ja (für größere Projekte) auch üblich, dass man möglichst nicht regelmäßig den Cache kaputtmacht. Solche Rücksichtnahme auf die reale Architektur muss vorhanden sein...

Wenn du Umsortieren musst, weil der RAM knapp wird, dann schon.

RAM-Knappheit ist der Grund fürs Swappen nicht fürs Defragmentieren.

Vor dem Swappen kommt zwangsweise ein Defragmentieren, um die letzten Speicherreste auszukratzen. Und bei genügend RAM (oder nicht genügend RAM-Auslastung) gibt es keinen Grund zu defragmentieren.

Die Segmente in meinem System werden im Durchschnitt eher ziemlich groß sein.

Womit du innerhalb der Segmente den Aufwand hast. Andererseits sparst du Unmengen FAR-Pointer ein, wenn die Anzahl der Segmente der Anwendung größer wird als die Anzahl der lokalen Segmentregister...

Warum sollte das mit mehreren CPUs schwerer werden?

Im Endeffekt sortierst du den physischen Speicher ja trotzdem um, auch wenn die MMU dazwischen sitzt. Du müsstest halt atomar dafür sorgen, dass für jedes verschobene Fragment eines Segments die Pagingtabelle korrekt ist. Sonst hat das Programm zwar eine nette virtuelle Adresse zum Arbeiten und greift trotzdem ins Leere, wenn die MMU auf den falschen Speicher zeigt (der da gerade wegverschoben wurde).

Ja. ...

Klingt gut. Wobei ich die möglicherweise auftretenden Probleme bei mehreren CPUs weder ab- noch einschätzen kann.

Zum Defragmentieren würde es aber reichen, wenn du nämlich je zwei Segmente in das Paging aufnimmst und dann im Hintergrund sortierst.

Hä?? Was hat defragmentieren mit sortieren zu tun und warum soll das genau 2 Segmente betreffen? Es ist durchaus möglich das mehrere Segmente der Defragmentierung bedürfen da sie vor kurzem vergrößert werden sollten aber nicht wachsen konnten weil dahinter schon was anderes lag (und kurzerhand in den virtuellen Speicher umgemappt wurden).

Ich halte defragmentieren als einen Oberbegriff, nämlich wann immer die physische RAM-Aufteilung geändert werden muss. Und das betrifft grundsätzlich immer zwei Segmente - das Quell- und das Zielsegment. Wenn du die beiden in das Paging verlagerst (bzw. ein paar mehr für stark unterschiedliche Größen), kannst du die im Hintergrund deine Speichermagie betreiben.

Was ich damit grundsätzlich sagen möchte, wenn du ohne Paging auskommen möchtest (es im Normalfall also eh nicht nutzen möchtest), dann brauchst du auch nicht die volle Flexibilität von Paging. Verschwendetes Silizium.

Für mich klingt es nach einer ausgewachsenen Nutzung von Paging und Segmentierung (was ich persönlich auch sehr gut finde) mit dem Designziel, die Pagingeinheit grundsätzlich abgeschaltet zu lassen. Nur wozu dann vollwertig implementieren? Außerdem rede ich (für meine Begriffe) immer von Randbedingungen, seltenen Ereignissen - die zu optimieren bringt mMn wenig.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Naja, nur wenn du sehr viele sehr große Segmente hast, ist das Problem der Fragmentierung nicht gegeben, denn die tritt hauptsächlich bei sehr kleinen (bzw. von vorne verkürzten) Segmenten auf. Das sind in der Regel nur ein paar MB oder sogar weniger.

Wieso sollte die Fragmentierung bevorzugt mit kleinen Segmenten auftreten? Gerade für kleine Segmente wird sich doch noch eher eine passende Lücke finden lassen als für große Segmente. Ein Segment das nur eine Page (kleinste Page-Größe) belegt kann gar nicht fragmentieren.

Wenn du natürlich möglichst fleißig Segmente zusammenfassen möchtest, damit die Segmente möglichst groß werden und du innerhalb der Segmente den Verwaltungsaufwand hast, dann kommt zu der externen Fragmentierung (Segmente im physischen Adressraum) auch noch interne Fragmentierung (malloc/realloc in den Segmenten) dazu. Stell ich mir unangenehm vor.

Ja, das möchte ich. Die interne Fragmentierung werde ich aber mit meinen unabhängigen dynamischen Segmenten deutlich besser in den Griff bekommen als das ein Flat-Memory-Programm je könnte.

gewisse Segmente braucht man nicht verschieben, wenn man sie im Voraus günstig platziert (z.B. Treiber).

Die Segmente für .code , .const und .data sind in ihrer Größe fest, die werden von hinten anfangend in den physischen Speicher gepackt. Die Heap-Segmente und Stack-Segmente sind flexibel und kommen von vorne anfangend in den physischen Speicher. Der Micro-Kernel in meinem OS weiß nicht was ein Treiber ist, der wird alle Programme gleich gut behandeln. Es wird aber eine Möglichkeit geben Segmente zu locken damit sie garantiert nicht verschoben werden (Treiber werden das nutzen), so ein Segment wird dann auch sofort nach vorne verlegt (der Treiber blockiert also während seiner Initialisierung ein bisschen wegen dem sofortigem verschieben oder das Segment wird gleich als gelockt erstellt), damit ist das Segment aber auch nicht mehr in seiner Größe änderbar.

Ich befürchte das ich da selbst mit möglichst intelligenter Segment-Allozierung (z.B. Best-Fit oder hinter jedem Segment was frei lassen) nicht lange ohne Defragmentieren auskomme.

Ich vermute mal schon, allerdings immer unter der Annahme von genügend physischem RAM.

Das hängt sehr davon ab wie neue Programme gestartet und beendet werden oder die Programme ihre (Heap-/Stack-)Segmente vergrößern/schrumpfen. Solange die RAM-Auslastung unter 50% bleibt sollte Defragmentieren kaum nötig sein, wird aber trotzdem mal auftreten (vor allem beim wachsen von Segmenten, da kann immer mal was anderes im Weg sein).

Auf einem normalen PC hast du in der Regel genug Idle-Zeit für solche Spielereien,

Du kennst Seti@Home oder seine Nachfolger? Von genügend Idle-Zeiten auszugehen ist meiner Meinung nach so eine Annahme die einem früher oder später richtig Ärger macht. Solche Annahmen will ich nicht treffen und auch nicht ins Design meiner Plattform einfließen lassen!

ansonsten kannst du die natürlich jederzeit auch garantieren.

Wie? Mal abgesehen davon das sowas IMHO Quatsch ist.

(Wobei garantierter Leerlauf eher nach Überhitzungsschutz klingt...)

lol

In dem Augenblick, wo Pages ausgelagert werden müssen, die noch gebraucht werden, ist ohnehin alles verloren.

Das soll ja die Page-Ersetzungs-Strategie möglichst verhindern. Die ist natürlich auch nicht perfekt und dann gibt es ein paar kurze Wartezeiten (wobei wenn die Page-Not-Present-Exception noch während des Schreibens auf die Festplatte kommt könnte der Exception-Handler die Page einfach wieder als gültig markieren und den Schreibvorgang als ungültig), aber im Durchschnitt wird die schon gut funktionieren. Wenn es gar nicht mehr anders geht fliegen IMHO die Programme mit der niedrigsten Priorität als erstes raus (die habens dann natürlich extrem schwer).

Besser als uClinux geht es fast nicht. Trotz der ganzen Probleme, die mit der Speicherfragmentierung einhergehen, läuft das System trotzdem.

Klar, in Anbetracht der Möglichkeiten die uCLinux hat ist das Ergebnis natürlich hervorragend.

aber "out of memory" bei zerstückeltem RAM gibt es selten unter 75% RAM-Auslastung. Und solche Situationen merkt man auch schon früher als Fall für den Garbage Collector.

Bei mir wird dann das Defragmentieren anspringen wenn sich für ein neues Segment nicht mehr physischer Speicher am Stück findet oder wenn ein Segment nicht einfach wachsen konnte und deshalb physisch zerteilt werden musste. Andere Gründe für das Defragmentieren fallen mir nicht ein. Einen "Garbage Collector" wird es bei mir nicht geben, kann ich mir momentan auch nicht vorstellen was der machen sollte. Das einzigste was mir einfällt sind Programme die ihren Speicher freiwillig, auf Bitte vom OS-Kernel, wieder hergeben. Ein File-System-Cache wäre da ein gutes Beispiel, normale User-Programme trifft das eher nicht.

denn während der Kernel sein Speichermanagement mit der Festplatte abquatschen muss, geht nicht wirklich viel.

Das "abquatschen" (Verwaltungsstrukturen im Speicher ändern) dürfte bei der Performance heutiger PC-CPUs vernachlässigbar sein und der eigentliche Datentransfer wird vom Festplatten-Host-Controller selbstständig erledigt, da kann die CPU sich längst wieder um die Programme kümmern.

Besonders, wenn die Page, in der der Taskzustand steht, fehlt

Ein OS das seine eigenen Verwaltungsstrukturen auslagert hat es auch nicht besser verdient.

Ich halte das Speichermanagement für zu kritisch, als dass man nebenher die unbelasteten Anwendungen weiterlaufen lassen könnte.

Wieso? Wenn man alles ordentlich mit spinlocks o.ä. absichert sehe ich da keine Probleme. Ein passendes Konzept zu entwerfen ist sicher nicht trivial (das werde ich bestimmt früher spüren als mir lieb ist) aber nicht unmöglich. Im Linux-Kernel versucht man doch auch diesen "Big-Kernel-Lock" zu beseitigen damit der Kernel auch unter Last noch die Wünsche der Programme befriedigen kann, gerade auf einem massiven SMP-System ist das nötig.

das Problem sehe ich heutzutage aber eher darin, dass irgendein Programm amok läuft, schnell viel RAM füllt, das System in die Ecke drängt bis es dann vom Kernel OOM-gekillt wird.

Solche Programme sind natürlich ein Ärgernis. Trotzdem soll das OS auch damit einigermaßen geschickt umgehen können. Hier wären vielleicht Memory-Quotas eine Lösung. Sowas wurde, hier im Forum, schon mal diskutiert http://lowlevel.brainsware.org/forum/index.php?topic=2256. Wenn mein OS mit Amok laufenden Programmen einigermaßen (also besser als Windows) umgehen kann dann bin ich zufrieden.

Swap als Arbeitsgrundlage braucht man mMn nicht mehr. Dazu ist RAM zu billig geworden.

ACK
Aber ganz auf Swapping verzichten kann/darf man trotzdem nicht (außer im Embedded-Bereich wo man vorher weiß welche Programme laufen werden). Swapping muss in meinem Konzept ordentlich vorgesehen sein, auch wenn ich das sicher nicht gleich beim ersten Anlauf umsetzen werde.

ob du nun das Office-Paket komplett oder zu einem Großteil ausgelagert hast, spielt da eine untergeordnete Rolle.

Das sehe ich anders. Viele Programme benutzen, über einen kurzen bis mittleren Zeitraum betrachtet, nur einen kleinen Teil des allozierten Speichers. Von einem Programm zwangsläufig alles auslagern zu müssen, anstatt nur den tatsächlich unbenutzten Teil rauszuwerfen, erscheint mir wahrlich ungeschickt.

Muss das Programm denn nur aus drei Segmenten bestehen?

Nein, die Programme werden schon ein paar Segmente mehr benötigen. Aber da die Größe der Segmente wohl in Pages (Größe der kleinsten unterstützen Page, in der 64 Bit-Variante also mindestens 64 kBytes) gemessen wird, entsteht eine Menge Verschnitt wenn man alles auf zu viele kleine Segmente verteilt. Außerdem kann die LDT maximal 32767 Segmente aufnehmen, damit will ich schon etwas sparsam umgehen.

ein eigenes Segment vorzusehen (welches dann, da es eh zu klein ist, nicht ausgelagert würde)?

Wieso sollten kleine Segmente nicht ausgelagert werden?

Der Tastendruck gehört entweder woanders verarbeitet

Und Wo? Wenn nicht im Office-Paket?

oder aber das Office-Paket nicht ausgelagert

Genau das ist der Punkt wo ich sage das Paging die einzigste Möglichkeit ist um Knappheit für alle Programme gleich fair abzufangen. Man kann doch schließlich nicht große Programme komplett im RAM lassen nur weil ein kleiner Teil davon benötigt wird. Ich denke jedes Programm muss etwas geben damit auch bei (leichter) Knappheit alle Programme noch einigermaßen arbeiten können.

Außerdem gehst du davon aus, dass die Programme von der Segmentierung nichts wissen (oder mitkriegen können), und somit dein System nicht entlasten können. Das sehe ich wie, wenn sich zwei Deutsche auf Englisch unterhalten - es funktioniert, ist aber schon im Ansatz falsch. Wenn du den Programmen keine segmentfreundliche Nutzung zugestehst, dann kann das nicht performant werden, einfach weil du auf der falschen Architektur arbeitest.

Ja, Du hast (in gewissen Grenzen) recht. Solange Segmentierung allgemein belächelt wird hab ich aber keine andere Wahl. Wirklich alles selber programmieren will ich nicht, ich will auch mal ein nützliches Tool portieren können. Natürlich muss die libc genau wissen wie die Segmente zu nutzen sind, auch all die anderen Librarys welche die Dienste des OS, oder der Personality, dem eigentlichen User-Space-Programm zugänglich machen sollten wissen das sie es mit Segmentierung zu tun haben. Wenn ich mir normale C-Programme ansehe dann gehen die erstmal von gar keiner Architektur aus, ich glaube auch nicht das in den C/C++-Specs dazu was drin steht. Es ist Aufgabe des Compilers die tatsächliche Ziel-Architektur angemessen (also möglichst optimal) zu bedienen.

Wie sollten den normale User-Programme mithilfe der Segmentierung mein System entlasten?

Heutzutage ist es ja (für größere Projekte) auch üblich, dass man möglichst nicht regelmäßig den Cache kaputtmacht. Solche Rücksichtnahme auf die reale Architektur muss vorhanden sein...

Da gebe ich Dir natürlich recht. Rücksicht auf Caches und dergleichen nehmen die Programmierer aber nicht für das Betriebssystem oder die Plattform sondern für die Performance des Programms, also aus Eigennutz. Die Existenz und Wirkungsweise von Caches hat physische Ursachen um die auch ich nicht herum komme, so das all diese Tricks eben auch auf meiner Plattform funktionieren werden (wenn auch auf einem deutlich niedrigerem Niveau).

RAM-Knappheit ist der Grund fürs Swappen nicht fürs Defragmentieren.

Vor dem Swappen kommt zwangsweise ein Defragmentieren, um die letzten Speicherreste auszukratzen.

Wieso? Defragmentieren bringt keinen zusätzlichen freien physischen Speicher sondern verteilt diesen nur anders. Defragmentieren und Swappen sind 2 völlig verschiedene Dinge mit völlig verschiedenen Ursachen und völlig verschiedenen Konzepten, die nur beide (zufällig) das selbe Paging benutzen um ihre jeweilige Aufgabe zu erfüllen.

Und bei genügend RAM (oder nicht genügend RAM-Auslastung) gibt es keinen Grund zu defragmentieren.

Jedenfalls nur sehr selten.

Womit du innerhalb der Segmente den Aufwand hast.

So wie in einem Flat-Memory-Programm auch, nur das ich mit den unabhängigen Segmenten ein paar Freiheitsgrade mehr hab um die interne Fragmentierung im Zaum zu halten.

Andererseits sparst du Unmengen FAR-Pointer ein, wenn die Anzahl der Segmente der Anwendung größer wird als die Anzahl der lokalen Segmentregister...

Hä? FAR-Pointer brauch ich doch trotzdem, der Compiler weiß doch nicht vorher wo die Speicherblöcke real liegen. Ein Pointer hat genau drei verschiedene Quellen: 1. der Compiler muss eine statische Variable referenzieren (aus .const oder .data, das passiert beim Linken), oder der Compiler muss eine lokale Variable referenzieren (also die Adresse von etwas ermitteln das auf dem Stack liegt, dafür muss der Compiler etwas Code erzeugen) und 3. kommt als Rückgabewert von malloc/realloc (das ist mein Part, ob ich da unbedingt Assembler für benötige weiß ich noch nicht). Alles andere ist reine Pointer-Arithmetik.

Ich halte defragmentieren als einen Oberbegriff, nämlich wann immer die physische RAM-Aufteilung geändert werden muss. Und das betrifft grundsätzlich immer zwei Segmente - das Quell- und das Zielsegment. Wenn du die beiden in das Paging verlagerst (bzw. ein paar mehr für stark unterschiedliche Größen), kannst du die im Hintergrund deine Speichermagie betreiben.

Wieso "Quellsegment" und "Zielsegment"? Ich kopiere doch nicht den Inhalt von einem Segment in ein anderes sondern verschiebe (in Wirklichkeit natürlich kopieren) die Pages aus denen ein Segment besteht. Das Segment befindet sich für diesen Vorgang zwar im virtuellen Speicher und seine Pages sing möglicherweise total über den physischen Speicher zerstreut, aber es ist trotzdem nur ein Segment an dem gerade gearbeitet wird.

Was ich damit grundsätzlich sagen möchte, wenn du ohne Paging auskommen möchtest (es im Normalfall also eh nicht nutzen möchtest), dann brauchst du auch nicht die volle Flexibilität von Paging. Verschwendetes Silizium.

Ohne ein vollwertiges Paging bringt mir die Segmentierung aber zu viele Nachteile (zum DOS will ja niemand zurück). Natürlich kostet das Silizium aber ohne kommt kein gescheites System bei raus.

Für mich klingt es nach einer ausgewachsenen Nutzung von Paging und Segmentierung (was ich persönlich auch sehr gut finde) mit dem Designziel, die Pagingeinheit grundsätzlich abgeschaltet zu lassen.

Ganz genau. Ich will das Paging haben weil ich damit ne Menge Magie veranstalten kann aber ich will es nicht ständig benutzen müssen weil es Performance kostet. Wenn ich auf die Magie verzichte dann kostet das aber noch mehr Performance (z.B. atomares Verschieben von Segmenten ist IMHO ein absolutes KO-Kriterium).

Außerdem rede ich (für meine Begriffe) immer von Randbedingungen, seltenen Ereignissen - die zu optimieren bringt mMn wenig.

Das Defragmentieren soll natürlich möglichst selten vorkommen aber wenn es dann, wenn es gebraucht wird, nicht richtig funktioniert ist IMHO mein Konzept totaler Mist (mal abgesehen davon das die meisten Leute die Segmentierung eh als totalen Mist bewerten).


Grüße
Erik

[Svenska]

Hallo,

Naja, nur wenn du sehr viele sehr große Segmente hast, ist das Problem der Fragmentierung nicht gegeben, denn die tritt hauptsächlich bei sehr kleinen (bzw. von vorne verkürzten) Segmenten auf. Das sind in der Regel nur ein paar MB oder sogar weniger.

Wieso sollte die Fragmentierung bevorzugt mit kleinen Segmenten auftreten? Gerade für kleine Segmente wird sich doch noch eher eine passende Lücke finden lassen als für große Segmente. Ein Segment das nur eine Page (kleinste Page-Größe) belegt kann gar nicht fragmentieren.

Das Problem sind große Segmente, die zu (sehr) kleinen Segmenten schrumpfen, beispielsweise ein Netzwerkpuffer, in dem Netzwerkdaten gesammelt werden, bis dann nach dem Header die Nutzdaten kommen und der Header weggeschnitten wird. Dann hast du nämlich ein kleines Loch vor oder hinter dem nächsten Segment. Mach das so lange, bis du den Speicher voll hast mit kleinen Segmenten, die von kleinen Löchern umgeben sind und der nächste (große) Puffer kann nicht mehr alloziiert werden.

Große Segmente, die groß bleiben (oder kleine Segmente, die nur kurz gebraucht werden) spielen in der Fragmentierung keine Rolle. Wenn doch, hast du zuwenig RAM.

gewisse Segmente braucht man nicht verschieben, wenn man sie im Voraus günstig platziert (z.B. Treiber).

Die Segmente für .code , .const und .data sind in ihrer Größe fest, die werden von hinten anfangend in den physischen Speicher gepackt. Die Heap-Segmente und Stack-Segmente sind flexibel und kommen von vorne anfangend in den physischen Speicher. Der Micro-Kernel in meinem OS weiß nicht was ein Treiber ist, der wird alle Programme gleich gut behandeln. Es wird aber eine Möglichkeit geben Segmente zu locken damit sie garantiert nicht verschoben werden (Treiber werden das nutzen), so ein Segment wird dann auch sofort nach vorne verlegt (der Treiber blockiert also während seiner Initialisierung ein bisschen wegen dem sofortigem verschieben oder das Segment wird gleich als gelockt erstellt), damit ist das Segment aber auch nicht mehr in seiner Größe änderbar.

Genau das meinte ich. Und wenn du systemkritische Segmente in der Form erzeugen kannst, werden die auch von paginglosem Defragmentieren nicht betroffen sein.

Ich befürchte das ich da selbst mit möglichst intelligenter Segment-Allozierung (z.B. Best-Fit oder hinter jedem Segment was frei lassen) nicht lange ohne Defragmentieren auskomme.

Ich vermute mal schon, allerdings immer unter der Annahme von genügend physischem RAM.

Das hängt sehr davon ab wie neue Programme gestartet und beendet werden oder die Programme ihre (Heap-/Stack-)Segmente vergrößern/schrumpfen. Solange die RAM-Auslastung unter 50% bleibt sollte Defragmentieren kaum nötig sein, wird aber trotzdem mal auftreten (vor allem beim wachsen von Segmenten, da kann immer mal was anderes im Weg sein).

Ja, und solange es selten auftritt... Das ist ja meine Ausgangssituation.

Auf einem normalen PC hast du in der Regel genug Idle-Zeit für solche Spielereien,

Du kennst Seti@Home oder seine Nachfolger? Von genügend Idle-Zeiten auszugehen ist meiner Meinung nach so eine Annahme die einem früher oder später richtig Ärger macht. Solche Annahmen will ich nicht treffen und auch nicht ins Design meiner Plattform einfließen lassen!

Klar, läuft bei mir. Und?

ansonsten kannst du die natürlich jederzeit auch garantieren.

Wie? Mal abgesehen davon das sowas IMHO Quatsch ist.

Wenn das Betriebssystem sich eine gewisse CPU-Zeit zur Selbstverwaltung genehmigt, sehe ich darin kein Problem. Damit könnte man dann sogar weiche Echtzeitanforderungen bearbeiten; harte Echtzeit kriegst du auf einem Allzweck-System ohnehin nicht hin.

Swap als Arbeitsgrundlage braucht man mMn nicht mehr. Dazu ist RAM zu billig geworden.

ACK
Aber ganz auf Swapping verzichten kann/darf man trotzdem nicht (außer im Embedded-Bereich wo man vorher weiß welche Programme laufen werden). Swapping muss in meinem Konzept ordentlich vorgesehen sein, auch wenn ich das sicher nicht gleich beim ersten Anlauf umsetzen werde.

ein eigenes Segment vorzusehen (welches dann, da es eh zu klein ist, nicht ausgelagert würde)?

Wieso sollten kleine Segmente nicht ausgelagert werden?

Nun, die könnte man locken...

Der Tastendruck gehört entweder woanders verarbeitet

Und Wo? Wenn nicht im Office-Paket?

Im Hauptprogramm aus 50 MB Code? Im Datensegment aus 400 MB Daten? Oder vielleicht doch in einem Event-Handler-Segment (bevorzugt gelockt)?

Ich denke jedes Programm muss etwas geben damit auch bei (leichter) Knappheit alle Programme noch einigermaßen arbeiten können.

Ich sehe leiche Knappheit als nicht vorhanden. Entweder die Ressourcen (bes. RAM) sind da, oder sie fehlen komplett. Bei Speichergrößen im GB-Bereich sehe ich ein paar fehlende KB als sehr unwahrscheinlich an. Und wenn es im Zig-MB-Bereich liegt, dann gibt das bereits spürbare Probleme, weil die meisten Programme, die viel RAM belegen, eben auch viel RAM nutzen.

Wie sollten den normale User-Programme mithilfe der Segmentierung mein System entlasten?

Wenn sie gewisse Rücksicht auf das System nehmen, z.B. Eventhandler in eigene gelockte Segmente verlagern oder Segmente eben nicht stark verkleinern, sondern wegwerfen und sich ein kleines Segment nehmen, dann entlastet das die Verwaltung auch. Du versuchst ja auch nicht, ein Serversystem auf 'nem DSP laufenzulassen. Der ist dafür halt nicht gebaut. (Es geht, Linux läuft ja auf manchen. Deswegen ist es trotzdem nicht das geeignetste System.)

Da gebe ich Dir natürlich recht. Rücksicht auf Caches und dergleichen nehmen die Programmierer aber nicht für das Betriebssystem oder die Plattform sondern für die Performance des Programms, also aus Eigennutz.

Haste Recht. Doof, so ein Egoismus. Trotzdem sollte man schon einigermaßen dafür sorgen, dem System nicht mehr Last aufzubrummen als notwendig.

Gegenbeispiel dafür ist Java. Hauptsache langsam. Oder Flash.

RAM-Knappheit ist der Grund fürs Swappen nicht fürs Defragmentieren.

Vor dem Swappen kommt zwangsweise ein Defragmentieren, um die letzten Speicherreste auszukratzen.

Wieso? Defragmentieren bringt keinen zusätzlichen freien physischen Speicher sondern verteilt diesen nur anders. Defragmentieren und Swappen sind 2 völlig verschiedene Dinge mit völlig verschiedenen Ursachen und völlig verschiedenen Konzepten, die nur beide (zufällig) das selbe Paging benutzen um ihre jeweilige Aufgabe zu erfüllen.

Auf einer segmentierten Architektur führt Fragmentierung dazu, dass du keine großen, zusammenhängenden freien Speicherblöcke mehr hast. Durch Defragmentierung kannst du durch Umschichten der Segmente solche Blöcke erzeugen, die - je nach Stückelung der vorhandenen Segmente - genügend große Blöcke erzeugen und damit das Swapping nicht erforderlich machen.

Fragmentierung ist eine Stufe der RAM-Knappheit (es ist kein nutzbarer Speicher da), im Gegensatz zum Swapping (es ist kein Speicher da).

Andererseits sparst du Unmengen FAR-Pointer ein, wenn die Anzahl der Segmente der Anwendung größer wird als die Anzahl der lokalen Segmentregister...

Hä? FAR-Pointer brauch ich doch trotzdem, der Compiler weiß doch nicht vorher wo die Speicherblöcke real liegen. Ein Pointer hat genau drei verschiedene Quellen: 1. der Compiler muss eine statische Variable referenzieren (aus .const oder .data, das passiert beim Linken), oder der Compiler muss eine lokale Variable referenzieren (also die Adresse von etwas ermitteln das auf dem Stack liegt, dafür muss der Compiler etwas Code erzeugen) und 3. kommt als Rückgabewert von malloc/realloc (das ist mein Part, ob ich da unbedingt Assembler für benötige weiß ich noch nicht). Alles andere ist reine Pointer-Arithmetik.

Wenn die verwendeten Segmentnummern zum Task gehören, braucht das Programm sich im Regelfall nicht um FAR-Pointer scheren (ein Datenzugriff geht nach .data, ein Codezugriff nach .code usw). Problematisch wird es erst, wenn du Segmentregister umladen musst - also FAR-Pointer dereferenzierst - denn das lässt sich nicht vermeiden. Klingt das überhaupt logisch?...

Ich halte defragmentieren als einen Oberbegriff, nämlich wann immer die physische RAM-Aufteilung geändert werden muss. Und das betrifft grundsätzlich immer zwei Segmente - das Quell- und das Zielsegment. Wenn du die beiden in das Paging verlagerst (bzw. ein paar mehr für stark unterschiedliche Größen), kannst du die im Hintergrund deine Speichermagie betreiben.

Wieso "Quellsegment" und "Zielsegment"? Ich kopiere doch nicht den Inhalt von einem Segment in ein anderes sondern verschiebe (in Wirklichkeit natürlich kopieren) die Pages aus denen ein Segment besteht. Das Segment befindet sich für diesen Vorgang zwar im virtuellen Speicher und seine Pages sing möglicherweise total über den physischen Speicher zerstreut, aber es ist trotzdem nur ein Segment an dem gerade gearbeitet wird.

Du hast ein Quellsegment, welches du verschieben möchtest und (ein oder mehrere) Zielsegmente, die da liegen, wo du das Quellsegment hinhaben möchtest. Die musst du vorher also sichern, ob im virtuellen Adressraum, (im physischen Adressraum, sofern genug Platz) oder auf Platte. So viele müssen das nicht unbedingt sein, außerdem muss oder sollte man große Segmente eh nur selten verschieben müssen, eher die kleinen drum herum.

Was ich damit grundsätzlich sagen möchte, wenn du ohne Paging auskommen möchtest (es im Normalfall also eh nicht nutzen möchtest), dann brauchst du auch nicht die volle Flexibilität von Paging. Verschwendetes Silizium.

Ohne ein vollwertiges Paging bringt mir die Segmentierung aber zu viele Nachteile (zum DOS will ja niemand zurück). Natürlich kostet das Silizium aber ohne kommt kein gescheites System bei raus.

Naja, ich würde mit dem Paging gezielt die Probleme der Segmentierung abschwächen/entfernen wollen. Wenn das Konzept sich dann als nicht tragbar erweist, kann man sich immernoch um was anderes bemühen - oder Segmentierung endgültig als Mist abstempeln.

Für mich klingt es nach einer ausgewachsenen Nutzung von Paging und Segmentierung (was ich persönlich auch sehr gut finde) mit dem Designziel, die Pagingeinheit grundsätzlich abgeschaltet zu lassen.

Ganz genau. Ich will das Paging haben weil ich damit ne Menge Magie veranstalten kann aber ich will es nicht ständig benutzen müssen weil es Performance kostet. Wenn ich auf die Magie verzichte dann kostet das aber noch mehr Performance (z.B. atomares Verschieben von Segmenten ist IMHO ein absolutes KO-Kriterium).

Naja, dann ist das eben so.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Das Problem sind große Segmente, die zu (sehr) kleinen Segmenten schrumpfen, beispielsweise ein Netzwerkpuffer, in dem Netzwerkdaten gesammelt werden, bis dann nach dem Header die Nutzdaten kommen und der Header weggeschnitten wird. Dann hast du nämlich ein kleines Loch vor oder hinter dem nächsten Segment. Mach das so lange, bis du den Speicher voll hast mit kleinen Segmenten, die von kleinen Löchern umgeben sind und der nächste (große) Puffer kann nicht mehr alloziiert werden.

Na und? So lange in Summe genügend freier Speicher vorhanden ist kann dieser auch für ein großes Segment alloziert werden. Dieses große Segment hat dann seine lineare Basis-Adresse nicht mehr direkt im physischen Speicher (weil es ja eben nicht mehr an einem Stück im physischen Speicher liegt) sondern im virtuellen Speicher (und dort werden die einzelnen physischen Stücke zu einem virtuellem Ganzen per Paging zusammengesetzt).
Der virtuelle Speicher ist ein Teilbereich des linearen Speichers aber es gibt dort keinen physischem Speicher, siehe http://lowlevel.brainsware.org/forum/index.php?topic=2470.msg27750#msg27750. Die dort gezeigte Memory-Map repräsentiert den linearen Speicher, überall dort wo auch physischer Speicher vorhanden ist (oder Memory-Mapped-I/O) ist der lineare Speicher 1:1 mit dem physischen Speicher identisch, nur dort wo unter dem linearen Speicher nichts liegt ist der virtuelle Bereich des linearen Speichers (nur dort ist das Paging aktiv). Ich weiß das ist etwas verwirrend und gänzlich anders als das was man sonst so kennt. Der lineare Speicher ist nur eine Abstraktion die entweder 1:1 oder per Paging auf den physischen Speicher verweist, die Segmente setzen immer auf den linearen Speicher auf damit man sie Defragmentieren und Swappen kann.

Aus meiner Sicht gibt es 2 Arten von Speicher-Defragmentierung in meinem System:

• Ein vorhandenes Segment soll vergrößert werden kann aber nicht wachsen weil was anderes im Weg ist, also muss der zusätzliche Teil wo anders im physischen Speicher alloziert werden und beide Teile werden dann erst im virtuellem Speicher zu einem Stück, dort hin wird auch die lineare Basis-Adresse gelegt. Das heißt das Segment gibt es 2 mal im linearen Speicher, ein mal in mehreren Teilen in dem Bereich der den physischen Speicher 1:1 repräsentiert und ein mal im virtuellem Speicher wo das Segment in einem ganzen Stück sichtbar ist. Das Defragmentieren besteht nun darin das im physischen Speicher ein neuer zusammenhängender Bereich für das zerteile Segment alloziert wird, das heißt es belegt dann kurzzeitig sogar den doppelten physischen Speicher (da könnte man bestimmt noch geschickt optimieren, siehe 2. Variante) und ist sogar 3 mal im linearen Speicher enthalten (ein mal zerteilt, ein mal am Stück aber noch ohne Inhalt und ein mal im virtuellen Speicher), und das Segment nun Page-Weise von den alten physischen Bereichen in den neuen physischen Bereich umkopiert wird. Das Mapping für den virtuellen Speicher wird immer mit aktualisiert so dass das Programm davon nichts merkt, es arbeitet ja mit der virtuellen Version des Segments. Wenn dieser Vorgang fertig ist werden die alten Bereiche im physischen Speicher frei gegeben, damit ist das Segment nur noch ein mal im physischen Speicher (und damit auch im 1:1-Teil des linearen Speichers) vorhanden, und als letztes kann dann die Basis-Adresse des Segments wieder direkt in den physischen Speicher zeigen und damit den virtuellen Speicher freigeben.
• Falls ein Segment neu erstellt werden soll oder für das Kopierziel eines vorhandenen zerteilten Segments kein ausreichender zusammenhängender physischer Speicher vorhanden ist dann müssen auch andere Segmente (die wahrscheinlich gar nicht selber fragmentiert sind) verschoben werden. Hierfür sind dann etwas komplexere Defragmentierungs-Algorithmen nötig, eine Variante könnte sein einfach alle Segmente nach vorne zusammen zu schieben und Dinge die im Weg sind kurzzeitig nach hinten weg zu schaffen (so wie ein klassischer Festplatten-Defragmentierer, kennt da jemand ein paar gute Algorithmen?). So einen Umschichtungsprozess könnte man eventuell auch anstoßen ohne das tatsächlich Segmente fragmentiert sind, einfach zur Prophylaxe. Diese Variante hat zwar den Vorteil das eigentlich nur physischer Speicher für eine Page (kleinste Page-Größe) zusätzlich zur Verfügung stehen muss aber könnte auch etwas komplizierter sein als die 1. Variante, zusätzlich muss man andauernd die Speicher-Verwaltung vom OS-Kernel bemühen um physische Pages zu allozieren und wieder frei zu geben.

Ich denke solange die Speicherauslastung gering ist dürfte die Variante 1 die bessere Wahl sein obwohl damit der freie physische Speicher immer mehr fragmentiert, um dem vorzubeugen bzw. echte Segment-Fragmentierung bei hoher Speicherauslastung zu bekämpfen muss man die 2. Variante benutzen.

Vor dem Swappen kommt zwangsweise ein Defragmentieren, um die letzten Speicherreste auszukratzen.

Wieso? Defragmentieren bringt keinen zusätzlichen freien physischen Speicher sondern verteilt diesen nur anders. Defragmentieren und Swappen sind 2 völlig verschiedene Dinge mit völlig verschiedenen Ursachen und völlig verschiedenen Konzepten, die nur beide (zufällig) das selbe Paging benutzen um ihre jeweilige Aufgabe zu erfüllen.

Auf einer segmentierten Architektur führt Fragmentierung dazu, dass du keine großen, zusammenhängenden freien Speicherblöcke mehr hast.

Das stimmt, bedeutet aber nicht das der noch vorhandene freie Speicher nicht mehr nutzbar ist. Genau dafür (und zum Swappen) will ich ordentliches Paging haben.

Durch Defragmentierung kannst du durch Umschichten der Segmente solche Blöcke erzeugen, die - je nach Stückelung der vorhandenen Segmente - genügend große Blöcke erzeugen und damit das Swapping nicht erforderlich machen.

Solange noch genügend freier Speicher vorhanden ist, egal wie zerstreut der auch ist, kann ich den auch nutzen (Dank dem Paging). Swapping ist wirklich nur für tatsächliche RAM-Knappheit erforderlich.

Du hast ein Quellsegment, welches du verschieben möchtest und (ein oder mehrere) Zielsegmente, die da liegen, wo du das Quellsegment hinhaben möchtest. Die musst du vorher also sichern, ob im virtuellen Adressraum, (im physischen Adressraum, sofern genug Platz) oder auf Platte. So viele müssen das nicht unbedingt sein, außerdem muss oder sollte man große Segmente eh nur selten verschieben müssen, eher die kleinen drum herum.

Ein Festplatten-Defragmentierer kann die Dateien auch nicht wo anders hin auslagern, der braucht einfach nur mindestens einen freien Cluster zum arbeiten. Wie groß die Segmente sind, die defragmentiert werden müssen, spielt für den Defragmentierer keine Rolle.

Bei Speichergrößen im GB-Bereich sehe ich ein paar fehlende KB als sehr unwahrscheinlich an. Und wenn es im Zig-MB-Bereich liegt, dann gibt das bereits spürbare Probleme, weil die meisten Programme, die viel RAM belegen, eben auch viel RAM nutzen.

Wenn auf einem Rechner mit X GByte RAM gerade 32 kBytes fehlen dann ist es eben so und das OS muss schauen was es auslagern kann, was bei dieser kleinen Menge natürlich kein Problem ist. Wenn etliche MBytes fehlen dann muss das OS auch schauen was raus kann und da dürfte es in vielen Programmen einiges geben was nicht ständig gebraucht wird. Klar bei winzigen Programme die mit ein paar kBytes genau eine Aufgabe erledigen ist da wenig zu holen aber bei einem fetten Office-Paket dürfte da bestimmt einiges gehen.

... oder Segmente eben nicht stark verkleinern, sondern wegwerfen und sich ein kleines Segment nehmen, dann entlastet das die Verwaltung auch.

Wieso sollte das anlegen eines neuen Segmentes und das löschen eines vorhandenen Segmentes weniger kosten als das einfache schrumpfen eines vorhandenen Segmentes? (mal davon abgesehen das ersteres 2 SYSCALLs und letzteres nur 1 SYSCALL braucht) Beim Verkleinern entsteht eben eine neue Lücke bzw. eine vorhandene Lücke neben dem Segment wird größer, das neu erstellen (und Daten umkopieren?) ist IMHO einiges aufwendiger. Wenn sich für das neue Segment nicht zufällig eine genau passende Lücke findet dann bleibt auch wieder ne Lücke übrig.

Der Tastendruck gehört entweder woanders verarbeitet

Und Wo? Wenn nicht im Office-Paket?

Im Hauptprogramm aus 50 MB Code? Im Datensegment aus 400 MB Daten? Oder vielleicht doch in einem Event-Handler-Segment (bevorzugt gelockt)?

Für den Event-Handler extra Segmente anzulegen ist ne Verschwendung (Page-Verschnitt) und stelle ich mir außerdem schwierig/umständlich vor (der bräuchte ein eigenes Heap-System u.a.m., der Compiler müsste den Code/Daten nach X? Kriterien über mehrere Segmente verteilen). Genau da kann das Paging was rausreißen in dem es dafür sorgt das nur die Pages im RAM bleiben müssen die auch tatsächlich benötigt werden. Warum sollte ich die Programme komplexer machen wenn der gewünschte Effekt mit dem Swapping per Paging von ganz alleine kommt? Außerdem wäre diese Komplexität in den Programmen immer drin auch wenn gar nicht geswappt werden muss und swappen ist ja eher die Ausnahme als die Regel und für Ausnahmen muss man doch nicht unbedingt so sehr optimieren. Normale Segmente zu locken ist IMHO kontraproduktiv, das OS sollte selber entscheiden dürfen was es raus wirft und was nicht. Je mehr gelockt wird desto weniger Freiheiten hat das OS.

Und wenn du systemkritische Segmente in der Form erzeugen kannst, werden die auch von paginglosem Defragmentieren nicht betroffen sein.

Gelockte Segmente sind weder vom Defragmentieren noch vom Swapping betroffen und genau deshalb muss ich damit sehr sparsam sein sonst werden die normalen Programme zu arg blockiert. Sein Segment zu locken ist für die anderen Programme unfair (natürlich haben die trotzdem was von funktionierenden Triebern) und deshalb soll das nur gemacht werden wenn es tatsächlich zwingenst erforderlich ist.

ein eigenes Segment vorzusehen (welches dann, da es eh zu klein ist, nicht ausgelagert würde)?

Wieso sollten kleine Segmente nicht ausgelagert werden?

Nun, die könnte man locken...

Warum sollten normale User-Programme anfangen dürfen ihre Segmente einfach/unkontrolliert zu locken und damit eventuell wichtigen System-Programmen den Speicher wegnehmen?

Auf einem normalen PC hast du in der Regel genug Idle-Zeit für solche Spielereien,

Du kennst Seti@Home oder seine Nachfolger? Von genügend Idle-Zeiten auszugehen ist meiner Meinung nach so eine Annahme die einem früher oder später richtig Ärger macht. Solche Annahmen will ich nicht treffen und auch nicht ins Design meiner Plattform einfließen lassen!

Klar, läuft bei mir. Und?

Dann weißt Du ja das man sich nicht auf Idle-Zeiten verlassen kann. Das einzigste wovon man ausgehen kann ist dass das OS sicherstellen muss das alle Programme einen fairen Zugang zur Ressource "CPU-Zeit" bekommen.

Wenn das Betriebssystem sich eine gewisse CPU-Zeit zur Selbstverwaltung genehmigt, sehe ich darin kein Problem.

Ich sehe da schon ein Problem. Natürlich muss man dem OS-Kernel für die Aufgaben die man von ihm erledigt haben will auch angemessene Zeit zugestehen, aber das er von sich aus anfängt die CPU zu benutzen finde ich persönlich falsch.

Trotzdem sollte man schon einigermaßen dafür sorgen, dem System nicht mehr Last aufzubrummen als notwendig.

Natürlich, das tun die Programmierer ja auch. Es ist meine Aufgabe als Plattform-Designer dafür zu sorgen das diese Bemühungen auch auf meiner Plattform zum Erfolg führen. Dinge wie ein kleiner Cache-Foot-Print u.ä.m. führen auch bei mir zum Ziel.

Gegenbeispiel dafür ist Java. Hauptsache langsam. Oder Flash.

Ich hab selber schon Java-Applets programmiert und bin durchaus der Meinung das ich für den Komfort das mein Applet überall läuft ein klein wenig Performance opfern kann (so groß ist dieser Performance-Verlust bei Java nun wirklich nicht). Eine Wetter-Simulation wird man bestimmt nicht in Java programmieren, wenn jemand extra dafür etliche Millionen Euro für die Hardware ausgibt wird er auch jedes MIPS bis aufs letzte ausquetschen wollen. Ich hab mal gehört das man manchmal auf solchen Super-Computern gar kein richtiges OS hat, einfach damit möglichst wenige CPU-Takte für was anderes als die eigentliche Aufgabe drauf gehen.

Wenn die verwendeten Segmentnummern zum Task gehören, braucht das Programm sich im Regelfall nicht um FAR-Pointer scheren (ein Datenzugriff geht nach .data, ein Codezugriff nach .code usw). Problematisch wird es erst, wenn du Segmentregister umladen musst - also FAR-Pointer dereferenzierst - denn das lässt sich nicht vermeiden.
Klingt das überhaupt logisch?...

Äh, nein, das klingt für mich nicht besonders logisch.
Da der Compiler nicht im voraus weiß ob der Pointer, den eine Funktion als Parameter bekommt, auf .const oder .data oder einem der Heap-Segmente oder ganz wo anders hin zeigt kann er auch nicht sagen das der Speicher-Zugriff über eines der vordefinierten Segment-Register geht. Deshalb will ich ja 16 Segment-Register haben, von denen etwa 10 zur freien Verfügung stehen (also nicht vordefiniert sind), um dem Compiler möglichst viele Freiheiten zu lassen.

Naja, ich würde mit dem Paging gezielt die Probleme der Segmentierung abschwächen/entfernen wollen.

Ganz genau darum geht es, aber dafür ist IMHO ordentliches Paging erforderlich. Im Gegensatz zum Paging auf anderen Plattformen ist mein Paging über alle CPUs synchron, es gibt also nur ein Paging-Directory das von allen CPUs benutzt wird, ich hab daher kein TLB-Trashing beim Task-Wechsel. Das ist aber auch der Grund warum ich nie Linux, oder irgend ein anderes Flat-Memory-OS, portieren kann. Es wäre aber auch totaler Unsinn ein ungeeignetes OS zu portieren.

Wenn das Konzept sich dann als nicht tragbar erweist, kann man sich immernoch um was anderes bemühen - oder Segmentierung endgültig als Mist abstempeln.

Bis jetzt sehe ich keine Probleme in meinem Konzept, ich denke es wird gut funktionieren.


Grüße
Erik

PS.: Ich hab die einzelnen Diskussionspunkte etwas defragmentiert.

PPS.: Falls ich oben ein bisschen den Oberlehrer in mir gezeigt hab bitte nicht übel nehmen. Ich hab irgendwie den unbestimmten Eindruck das wir in ein paar Details an einander vorbei reden und da wollte ich noch mal richtig erklären.

[Svenska]

Hallo,

PPS.: Falls ich oben ein bisschen den Oberlehrer in mir gezeigt hab bitte nicht übel nehmen. Ich hab irgendwie den unbestimmten Eindruck das wir in ein paar Details an einander vorbei reden und da wollte ich noch mal richtig erklären.

Äh, ja. Nix Oberlehrer. Danke, das war richtig so.

Jetzt kann ich einiges besser nachvollziehen und verstehe teilweise auch den Gedankengang dahinter.

Also hast du den physischen Speicher in einem 1:1 Mapping in der Page-Tabelle (und das ganze so gebaut, dass damit genau kein Performance-Verlust auftritt) und dahinter virtuellen Speicher, der durch die MMU geroutet wird.
Somit ist also Paging mehr oder weniger ständig aktiv, wird aber designtechnisch möglichst umgangen.

Das einzige, was ich noch sehe, ist der physisch nutzbare Adressraum von nur 1 GB RAM (statt 4 GB) - in der 32-Bit-Variante - aber so viel möchtest du da wohl eh nicht anbasteln.

Ich bin mal gespannt, was dabei rauskommt. Gut klingen tut es.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Also hast du den physischen Speicher in einem 1:1 Mapping in der Page-Tabelle (und das ganze so gebaut, dass damit genau kein Performance-Verlust auftritt)

Jain, es gibt in dem 1:1-Bereich gar kein Paging. Ich will dafür extra Range-Register vorsehen die der Paging-Unit nur einen bestimmten Bereich erlauben, alles andere geht immer dran vorbei und ist im Paging-Directory nicht präsent.

und dahinter virtuellen Speicher, der durch die MMU geroutet wird.

Genau. Nur Segmente, deren lineare Basis-Adresse nicht im 1:1-Bereich sondern im virtuellen Bereich liegt, sind vom Paging betroffen und können dann auch aus mehreren Teilen bestehen.

Somit ist also Paging mehr oder weniger ständig aktiv, wird aber designtechnisch möglichst umgangen.

Ja, das Paging ist immer aktiv aber es liegen meistens keine Segmente in dem Bereich wo Paging auch wirkt so das es meistens gar nicht benutzt wird.

Das einzige, was ich noch sehe, ist der physisch nutzbare Adressraum von nur 1 GB RAM (statt 4 GB) - in der 32-Bit-Variante - aber so viel möchtest du da wohl eh nicht anbasteln.

Dieses Problem ist mir auch schon aufgefallen. Irgendeinen Bereich im linearen Speicher brauche ich um dort hin die Segmente virtuell "auszulagern" damit sie noch in einem Stück sichtbar bleiben (das geht im 1:1-Bereich mit fragmentierten Segmenten ja eben nicht). Dieser Bereich sollte möglichst deutlich größer als der physisch vorhandene Speicher sein damit ich dort nicht so schnell in Bedrängnis gerate, schließlich gibt es auch dort externe Fragmentierung wenn ich dort immer Segmente rein mappe und dann wieder raus nehme. Andererseits werden dort immer nur wenige Segmente drin sein (meistens wohl nur ein einziges) so das der Druck wohl doch nicht so hoch ist.
Das der lineare Speicher auf der 32Bit-Version meiner Plattform recht eng ist, im Hinblick auf den machbaren physischen Speicher, ist mir klar. Genau deshalb ist mir der Pfad hin zu 64 Bit so wichtig. Wenn ich davon aus gehe das der virtuelle Speicher doppelt so groß wie der physische Speicher sein sollte (und noch etwas Memory-Mapped-I/O dazu muss) dann wird es dort erst bei 2^62 Bytes physischen Speicher eng und bis da hin ist noch ein ganz klein wenig Zeit.

Als Alternative kann ich immer noch das Paging im ganzen linearen Speicher aktivieren und das Paging-Enable-Bit in den Segment-Descriptoren nutzen (so wie ich mir das ursprünglich vorgestellt hatte bevor ich mir nähere Gedanken zum defragmentieren machte) so das immer nur die Segmente die fragmentiert sind das Paging nutzen. Trotzdem benötige ich einen Bereich im linearen Speicher in den die Segmente virtuell hin können (um an einem Stück sichtbar zu bleiben) wenn sie fragmentiert sind und sich so nicht mehr ohne Paging nutzen lassen.

Es bleibt also noch einiges zu grübeln bevor ich auch nur in die Nähe von "fertig" komme.

Ich bin mal gespannt, was dabei rauskommt.

Ja, gespannt bin ich auch.

Gut klingen tut es.

Das sollte es auch langsam, nach dem ich nun schon 4 Jahre drüber brüte.


Grüße
Erik

[kevin]

Ich habe ja das nicht alles mitgelesen, dafür ist es mir zu viel. Aber vielleicht ist es ja trotzdem nicht völlig vorbei:

Jain, es gibt in dem 1:1-Bereich gar kein Paging. Ich will dafür extra Range-Register vorsehen die der Paging-Unit nur einen bestimmten Bereich erlauben, alles andere geht immer dran vorbei und ist im Paging-Directory nicht präsent.
[...]
Nur Segmente, deren lineare Basis-Adresse nicht im 1:1-Bereich sondern im virtuellen Bereich liegt, sind vom Paging betroffen und können dann auch aus mehreren Teilen bestehen.

Warum nimmst du nicht ein Flag für die Segmente her, das aussagt, ob Paging für dieses Segment aktiviert ist? Das erscheint mir irgendwie eleganter als irgendwelche magischen Speicherbereiche zu haben.

[erik.vikinger]

Hallo,

Warum nimmst du nicht ein Flag für die Segmente her, das aussagt, ob Paging für dieses Segment aktiviert ist? Das erscheint mir irgendwie eleganter als irgendwelche magischen Speicherbereiche zu haben.

Das hab ich doch auch ein paar Sätze später geschrieben.

Das löst aber nicht das Problem das ich die Segmente im linearen Speicher immer am Stück brauche und wenn es im physischen Speicher keinen geeigneten Frei-Bereich gibt (wo ich das Segment kurzerhand einblenden könnte und wo es dann im Hintergrund auch physisch hin defragmentiert/verschoben wird), dann muss das Segment erst mal wo anders hin "ausgelagert" werden (nur dort ist dann das Paging nützlich, weshalb es etwas Sinn macht es auch nur dort aktiv zu haben).

Mir ist da noch die Idee gekommen als "Virtual-Swap-Out-Arrea" den Memory-Mapped-I/O-Bereich zu nehmen. Dann würden in diesem Bereich des linearen Speichers 2 Sorten an Segmenten existieren. Solche mit gesetztem Paging-Enable-Bit die per Paging in (eins oder) mehrere Teilstücke des normalen physischen Speichers zeigen und andere mit gelöschtem Paging-Enable-Bit die am Paging vorbei auf die Peripherie-Speicher zeigen. Diese Idee klingt aber selbst für meine Verhältnisse ziemlich verrückt.

Prinzipiell bin ich schon daran interessiert auf die Paging-Range-Register zu verzichten und ich hätte auch gerne mehr physischen Speicher in meiner Memory-Map (jedenfalls mehr als 1/4), die Frage ist nur wie ich das angehe.


Grüße
Erik

[kevin]

Das hab ich doch auch ein paar Sätze später geschrieben.

Wie gesagt, ihr schreibt mir zu viel, um alles zu lesen.

Das löst aber nicht das Problem das ich die Segmente im linearen Speicher immer am Stück brauche und wenn es im physischen Speicher keinen geeigneten Frei-Bereich gibt (wo ich das Segment kurzerhand einblenden könnte und wo es dann im Hintergrund auch physisch hin defragmentiert/verschoben wird), dann muss das Segment erst mal wo anders hin "ausgelagert" werden (nur dort ist dann das Paging nützlich, weshalb es etwas Sinn macht es auch nur dort aktiv zu haben).

Wenn du mit dem Defragmentieren anfängst, ist das Segment doch am Stück. Warum es nicht einfach dort lassen, wo es ist, während Paging aktiv ist? Oder wenn dir der Quellbereich nciht gefällt, nimmst du eben den Zielbereich her - den brauchst du genauso in zusammenhängender Form, wenn du Paging irgendwann wieder ausschalten willst.

Wenn es keinen passenden Bereich gibt, hast du doch sowieso verloren, oder?