Thema: Allgemeiner Ressourcen-Allocator

[FlashBurn]

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

Das kommt halt auf den Algo an. Es gibt Algos die sind schnell, aber haben nen ganz schönen Verschnitt, es gibt Algos die sind nicht so schnell und haben nicht so viel Verschnitt und es gibt inzwischen Algos die sind schnell und haben nicht so viel Verschnitt (und die wären ja deiner Meinung nach nicht möglich).
Um es genauer zu sagen, gibt es halt inzwischen O(1) Implemenationen, die schnell sind und wenig Verschnitt haben.

[erik.vikinger]

Hallo,

Definiere Bitte "normal"!

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

Und warum ist gerade das "normal"? Und jetzt komm mir bitte nicht mit Statistik!

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

Richtig, ich (als Programmierer) weiß wenn ich Rekursion benutze aber ich weiß nicht im voraus wie tief die zur Laufzeit wirklich geht.
Denke an:

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

Und genau diesen Sortierzustand kennt man nicht im voraus! Also ist es besser wenn der Stack in seiner Größe möglichst flexibel ist und gerade das kann ein Flat-Memory-OS eben nicht bieten.
Stell Dir vor Du hast 100 Worker-Threads die immer wieder solche Aufgaben bekommen, ab und an mal ist eine dieser Aufgaben etwas komplexer und der Thread benötigt (zeitweise) deutlich mehr Stack. Für alle Worker-Threads im von vornherein den maximal benötigten Stack zu geben geht nicht weil Dir damit der virtuelle Adressraum aus geht. Also was machst Du? Du brichst bei einer bestimmten Rekursionstiefe ab und greifst auf einen langsameren Backup-Algorithmus zurück (der nicht so viel Stack benötigt).

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

"Nichts leichter als das!" dachte sich der große Erik und es geschah das der genialste Code aus seinen geschmeidigen Händen sprudelte um sich über der klappernden Tastatur zu ergießen so wie das reinste Wasser aus den ewigen Quellen des geheiligten Flusses sprudelt um ins unendliche Meer zu strömen.
Einige Stunden später stellte der große Erik dann entsetzt fest das sein Code nicht gegen doppeltes free (mit dem selben Pointer) gefeit ist.
Tja, es war eine wirklich gute Idee mit extremer Performance (natürlich nur wenn man unabhängige Segmente hat) aber dieser Makel beim free lässt sich leider nur umständlich und unperformant beheben, aber ich will noch mal ein paar Nächte drüber schlafen (ich könnte ja die Verwaltungsinformationen doch in ein extra Segment auslagern, damit kämme zum Verschnitt durch Aufrunden der Objektgröße noch ein fester Overhead für die Belegt/Frei-Information).

Wenn wir mal deine Slabs mit 512KB nehmen ....

Bei meinen 512kB-Slabs hab ich im Schnitt immer etwa einen halben Slab unbelegt und damit 256kB Verschnitt. Da ich nur etwa 6 Objekt-Größen in meinem Kernel hab kann ich damit recht gut Leben. Ein paar dieser Objekte (z.B. der Thread-Descriptor) sind aber schon recht groß so das ich auch bemüht bin innerhalb eines Slabs nicht zu viel Verschnitt zu haben und da ich (wegen einfacher Verwaltung) nur eine Slab-Größe haben möchte muss ich eben einen Kompromiss finden. Aber das sind alles bereits zur Design-Zeit bekannte Größen die ich mal (wenn alles einigermaßen fertig ist) gegeneinander abgleichen muss um dann einen möglichst optimalen Kompromiss zu finden.

Darum bringt das System eine sinnvolle Automatik mit.

Naja, ob eine Automatik immer ein sinnvolles Ergebnis liefert würde ich doch mal bezweifeln, aber lassen wir das.
Schade das Du ausgerechnet auf Sätze wie diesen nicht eingegangen bist:

Betrachte es mal von einer anderen Seite: normalerweise hast Du dieses Parameter nicht und musst Dich eh auf die Automatik vom OS verlassen aber bei FlashBurns OS gibt es die Möglichkeit diese Automatik wenigstens zu versuchen zu Deinen Gunsten zu beeinflussen. Egal wie Du das Flag benutzt Dir entsteht, gegenüber einem OS ohne dieses Flag, erst mal kein Nachteil. Du kannst also nur gewinnen.

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

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

Und mir die Möglichkeit einer Entscheidung geben.

Ich betrachte das Flag als Möglichkeit dem OS gleich im voraus Deine Entscheidung mitzuteilen. Du sagst also wie Du es gern hättest falls überhaupt eine Wahlmöglichkeit besteht und wenn die Wahl nicht möglich ist musst du eh mit dem auskommen was geht. Das i-Tüpfelchen wäre noch wenn Dir das OS zusätzlich mitteilt was es gemacht hat, so kannst Du Dich dem (also dem was das OS als Maximum für Dich tun konnte) so gut es geht anpassen.

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

Den sie entweder ignoriert (dann hätte ich den Hinweis nicht gebraucht) oder umsetzt (dann hätte ich es auch erzwingen können).

Du weißt aber nicht im voraus welche von beiden Situationen dann zur Laufzeit tatsächlich herrscht. Eben deswegen ist es gut wenn Du dem OS für beide Fälle sagen kannst was Dir am liebsten wäre.

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

ACK! Mal abgesehen davon das doch immer mal wieder ein schlauer Mensch eine geniale Idee hat wie man ein bestimmtes Problem doch einfacher lösen kann, aber das kommt nur recht selten vor.
Ein gutes Beispiel ist da die Kryptographie, mancher Algorithmus der vor 20 Jahren noch als absolut unknackbar (selbst mit unbegrenzter Rechenleistung und unbegrenzter Speicherkapazität) angesehen wurde lässt sich heute mit nem simplen programmierbaren Taschenrechner (der auch schon vor 20 Jahren existierte) knacken.


Grüße
Erik

[FlashBurn]

Und warum ist gerade das "normal"? Und jetzt komm mir bitte nicht mit Statistik!

Normal ist für gewöhnlich das was die Mehrheit ist und das dürften FlatMemory Modelle sein. Ich weiß auch nicht warum dem so ist, aber es wird schon seinen Grund haben.

Und genau diesen Sortierzustand kennt man nicht im voraus! Also ist es besser wenn der Stack in seiner Größe möglichst flexibel ist und gerade das kann ein Flat-Memory-OS eben nicht bieten.

Und trotzdem wird QuickSort benutzt, was mir sagt, das es irgendwie lösbar ist. Zumal müsstest du doch den worst-case anhand der Datenmenge abschätzen können bzw. spontan fällt mir ein,halt nen QuickSort zu "simulieren". Ich meine damit, dass du deine Datenmenge in mehrere Teile einteilst und die erst sortierst (im Endeffekt das was QuickSort macht) und wenn du die sortiert hast, sortierst du die ganze Datenmenge, da die Teilmengen schon sortiert sind, müsste das ganze ja jetzt mit weniger Rekursionen auskommen.
Es gibt immer einer Lösung ob die schnell und elegant ist sei mal dahin gestellt.

(natürlich nur wenn man unabhängige Segmente hat)

Es ist schön das du uns die Vorteile deiner Architektur zeigen kannst, aber was die Diskussion betrifft ist das immer schlecht, weil wir ja eigentlich Probleme diskutieren die eine FlatMemory Architektur betrifft.
Das wäre wie, ich habe nen Algo gefunden der alle anderen auf Single CPU Systemen schlägt, aber auf SMP Systemen ist er grotten schlecht (und die Diskussion war wie man es auf SMP Systemen schnell lösen kann).

Was eure (erik und svenska) Diskussion betrifft, sehe ich es wie erik. Du sagst dem OS wie du es gerne hättest und das OS versucht es so gut es geht umzusetzen.
Kann man mit einem Navi vergleichen. Du willst die schnellste Strecke nehmen und fährst Autobahn, dass Navi weiß aber das auf der Autobahn Stau ist (was du nicht weißt) also wird es dich umleiten, obwohl du eigentlich Autobahn gefahren wärst.

Ein gutes Beispiel ist da die Kryptographie, mancher Algorithmus der vor 20 Jahren noch als absolut unknackbar (selbst mit unbegrenzter Rechenleistung und unbegrenzter Speicherkapazität) angesehen wurde lässt sich heute mit nem simplen programmierbaren Taschenrechner (der auch schon vor 20 Jahren existierte) knacken.

Mal davon abgesehen dass das überall so ist (anderes Bsp. der Mensch wird nie fliegen können, Erde ist Zentrum des Universums, der Mensch wird nie seinen Planeten verlassen usw.), bin ich der Meinung man sollte was solche Sachen betrifft sich nie festlegen. Denn es kann immer neues Wissen hinzukommen und miteinmal ist es doch möglich oder anders.

[Svenska]

Hallo,

Um es genauer zu sagen, gibt es halt inzwischen O(1) Implemenationen, die schnell sind und wenig Verschnitt haben.

Zeige mir bitte einen O(1) Sortier- und einen O(1)-Suchalgorithmus.

Schade das Du ausgerechnet auf Sätze wie diesen nicht eingegangen bist:

Betrachte es mal von einer anderen Seite: normalerweise hast Du dieses Parameter nicht und musst Dich eh auf die Automatik vom OS verlassen aber bei FlashBurns OS gibt es die Möglichkeit diese Automatik wenigstens zu versuchen zu Deinen Gunsten zu beeinflussen. Egal wie Du das Flag benutzt Dir entsteht, gegenüber einem OS ohne dieses Flag, erst mal kein Nachteil. Du kannst also nur gewinnen.

Nun, das ist unbestreitbar korrekt und da ich merke, dass ich mit meiner Meinung auf verlorenem Posten stehe, wollte ich da nicht weiter argumentieren... Ich bin halt nach wie vor der Meinung, dass es in jedem Fall die Möglichkeit geben sollte, ein bestimmtes Verhalten zu erzwingen. Und die Lösung mit MAP_NOW/MAP_LAZY/MAP_AUTO/MAY_MAP_NOW/MAY_MAP_LAZY ist für uns alle akzeptabel.

Ein gutes Beispiel ist da die Kryptographie, mancher Algorithmus der vor 20 Jahren noch als absolut unknackbar (selbst mit unbegrenzter Rechenleistung und unbegrenzter Speicherkapazität) angesehen wurde lässt sich heute mit nem simplen programmierbaren Taschenrechner (der auch schon vor 20 Jahren existierte) knacken.

Das betrifft aber nur ganz wenige Aufgabenstellungen. Viele Aufgabenstellungen sind hinreichend auf ihre Optimierbarkeit bewiesen.

Normal ist für gewöhnlich das was die Mehrheit ist und das dürften FlatMemory Modelle sein. Ich weiß auch nicht warum dem so ist, aber es wird schon seinen Grund haben.

Sagen wirs mal so... Segmentierung auf x86 ist entstanden, weil 8-Bit-Rechner nur 16-Bit-Adressräume (64K) hatten und sich das aus Kompatiblitätsgründen besser mit Segmentierung simulieren lässt als mit flat memory. Später stellte sich aber heraus, dass damalige Compiler mit Segmentierung überhaupt nicht umgehen konnten, einmal aufgrund der Kosten für Segmentregisterwechsel (teilweise wurde jeder Zugriff mit Neuladen von DS/ES erledigt), andererseits die Compiler auch keine sinnvolle Einteilung in Segmente vornehmen konnten. Da 8-Bit-Anwendungen aber oft von Hand in Assembler programmiert und auch immer von Hand in Overlays geteilt wurden, spielte das bei der Einführung keine Rolle.

Also entstanden Flat-Memory-Systeme auf 32-Bit-Rechnern, als der Adressraum groß genug war und man sich den Segmentierungsaufwand sparen konnte. Der Grund liegt in den Compilern der 80er Jahre. Heutige Compiler könnten da wesentlich effizienter optimieren.

Und trotzdem wird QuickSort benutzt, was mir sagt, das es irgendwie lösbar ist. Zumal müsstest du doch den worst-case anhand der Datenmenge abschätzen können bzw. spontan fällt mir ein,halt nen QuickSort zu "simulieren". Ich meine damit, dass du deine Datenmenge in mehrere Teile einteilst und die erst sortierst (im Endeffekt das was QuickSort macht) und wenn du die sortiert hast, sortierst du die ganze Datenmenge, da die Teilmengen schon sortiert sind, müsste das ganze ja jetzt mit weniger Rekursionen auskommen.

Du wendest auf die Teilmengen z.B. Bubblesort an, wenn der Stack aufgebraucht ist.

Es gibt immer einer Lösung ob die schnell und elegant ist sei mal dahin gestellt.

Vergleiche mal die Laufzeit von Bubblesort und Quicksort für n Elemente (1k < n < 100k) und entscheide dann, ob dir solche Lösungen gefallen oder du nicht lieber doch den Stack allgemein größer baust. RAM ist heutzutage billig und in ausreichender Menge verfügbar.

Kann man mit einem Navi vergleichen. Du willst die schnellste Strecke nehmen und fährst Autobahn, dass Navi weiß aber das auf der Autobahn Stau ist (was du nicht weißt) also wird es dich umleiten, obwohl du eigentlich Autobahn gefahren wärst.

Ich möchte aber vorher davon erfahren. Außerdem muss ich beim Navi diese Funktion auch einschalten - ich habe die Möglichkeit, ein Wunschverhalten zu erzwingen.

bin ich der Meinung man sollte was solche Sachen betrifft sich nie festlegen. Denn es kann immer neues Wissen hinzukommen und miteinmal ist es doch möglich oder anders.

Es gibt Dinge, die sind mathematisch bewiesen und die Beweise sind mathematisch korrekt geführt worden. Das ist dann so und jede Implementierung dessen ist begrenzt. Sicherlich kann man jetzt argumentieren, dass die Mathematik vielleicht nicht korrekt ist, aber da gibt es ein Gegenbeispiel: Newtons Theorie ist nach wie vor gültig, aber mit Einschränkungen. Einstein hat Newtons Theorie nicht widerlegt, sondern erweitert. Genauso wird die Mathematik immer erweitert und jede noch so tolle Grundidee wird die jetzige Mathematik enthalten. Damit bleiben die Ergebnisse auch weiterhin gültig. Und wenn eine Aufgabe schon theoretisch nur in O(n^2) lösbar ist, so trifft dies auf jede noch so geniale Implementation zu (oder schlechter).

So Dinge wie Turing-Vollständigkeit sind zwar unglaublich dröge und unspannend, aber die Ergebnisse dessen sollte man auch als Praktiker nie wegerklären wollen. Es gibt nach wie vor Aufgabenstellungen, die theoretisch in O(n) lösbar sein sollten, es aber keinen Algorithmus gibt, der dies in unter O(e^n) lösen kann. Den muss man finden. Aber es gibt ihn nicht überall.

Gruß,
Svenska

[Jidder]

Zeige mir bitte einen O(1) Sortier- und einen O(1)-Suchalgorithmus.

Code: [Auswählen]

#define popcount(x) __builtin_popcount(x)

/* Sortiert die Bits in einem Integer */
unsigned sort(unsigned x)
{
return (1 << popcount(x)) - 1;
}

[Svenska]

Erklär mal.

[Jidder]

Wenn das an mich gerichtet war: Ja, ich gebe ja zu, dass der Code nicht besonders lustig war ... Aber immerhin gibt es mal wieder eine kurze Antwort hier im Thread.

[FlashBurn]

Zeige mir bitte einen O(1) Sortier- und einen O(1)-Suchalgorithmus.

Schonmal was von nem O(1) Scheduler gehört, der macht ja im Endeffekt auch nichts anderes als sortieren und suchen. Du musst die Menge der Elemente nur weit genug einschränken und schon geht das

Bestes Bsp. wäre sogar ein malloc() wo ein SlabAllocator dahinter steckt der nur Blöcke mit 2er Potenzen hat.

Und ein anderes Bsp. was ich neulich gefunden habe: http://rtportal.upv.es/rtmalloc/

Vergleiche mal die Laufzeit von Bubblesort und Quicksort für n Elemente (1k < n < 100k) und entscheide dann, ob dir solche Lösungen gefallen oder du nicht lieber doch den Stack allgemein größer baust. RAM ist heutzutage billig und in ausreichender Menge verfügbar.

Aber was ist mit meiner Idee QuickSort halt in Schritten anzuwenden?

Zumal es ja darum ging das du ab einer bestimmten Anzahl von Threads die Stacks nicht mehr vergrößern kannst und da hilft dann auch mehr RAM nicht mehr, sondern eine Lösung ist 64bit Architektur.

Die andere Lösung wären Stacks die nicht zusammenhängend sind. Ich habe sowas mal im Zusammenhang mit Linux gelesen, weiß aber nicht mehr wo das war oder wie das funktionieren soll.

Und wenn eine Aufgabe schon theoretisch nur in O(n^2) lösbar ist, so trifft dies auf jede noch so geniale Implementation zu (oder schlechter).

Wimre dann hatte ich in theoretischer Informatik mal, das man bei genau solchen Problemen sich einfach "bessere" Bedingungen (z.B. die Menge der Elemente einschränken o.ä.) schafft damit man die Probleme halt schneller lösen kann.

[erik.vikinger]

Hallo,

Normal ist für gewöhnlich das was die Mehrheit ist

Ja, wenn auch eine seltsame Definition! Und die Mehrheit sind Herdentiere die einfach irgendeinem Leithammel hinterher trotten? Du warst es doch der hier mehrfach für neue Wege plädiert hat.

Ich weiß auch nicht warum dem so ist, aber es wird schon seinen Grund haben.

Die Gründe hat svenska ja recht gut zusammengefasst. Das DS/ES permanent neu geladen werden müssen liegt vor allem daran das es nur diese 2 frei benutzbaren Segmentregister auf x86 gibt. Schau Dir mal MOVS an, das ist das selbe Problem wie bei "Akkumulator-Zentriert", wenn man sich auf eine einzelne zentrale Ressource konzentriert dann ist die einfach überlastet und kann nicht skalieren (schade eigentlich das für die Segmentregister und deren Shadows nie Registerrenaming eingeführt wurde). Ich hab 16 Segmentregister und jeder Speicherzugriff kann jedes davon frei benutzen (nur beim letzten gibt es ein paar Einschränkungen da es für das Code-Segment reserviert ist).

Und trotzdem wird QuickSort benutzt, was mir sagt, das es irgendwie lösbar ist.

Quicksort wird nur da eingesetzt wo die Menge der Daten (und damit die maximalste Rekursionstiefe) überschaubar ist, so das der Programmierer sich sicher sein kann das der Stack reicht.

(natürlich nur wenn man unabhängige Segmente hat)

Es ist schön das du uns die Vorteile deiner Architektur zeigen kannst, aber was die Diskussion betrifft ist das immer schlecht, weil wir ja eigentlich Probleme diskutieren die eine FlatMemory Architektur betrifft.

Sorry, aber ich entwickle eben eine Architektur mit Segmentierung (da hab ich auch nie ein Geheimnis draus gemacht!!) und daher ist das auch das worauf ich mich (oft aber nicht immer) beziehe. Ich denke das ich mich recht gut in die Bedürfnisse und Probleme einer Flat-Memory-Architektur hineinversetzen kann und auch entsprechend passende Antworten gebe, umgedreht erscheint mir das ziemlich selten (jedenfalls kann ich mich nur vereinzelt daran erinnern gut auf Segmentierung passende Antworten bekommen zu haben). Bitte nicht falsch verstehen, ich weiß das ich hier der Exot bin und erwarte auch nicht das ich von den "Normalen" exakt passende Antworten bekomme aber wenigstens etwas Toleranz wäre nicht schlecht.
Ich denke übrigens das ich meinen Heap doch mit 2 Segmenten pro Objekt-Größe ausstatten werde, das sogt nicht nur für ein zuverlässiges free sondern auch dafür das der User-Code erstmal keine Chance hat meine Verwaltungsstrukturen zu manipulieren (auch wenns nur "Security by Obscurity" ist, aber da mein Kernel die Segmentselectoren mit einem echten RNG vergibt ist das Okay).

.... (und die Diskussion war wie man es auf SMP Systemen schnell lösen kann)

Der Titel dieser Diskussion lautet "Allgemeiner Ressourcen-Allocator", insbesondere das erste Wort suggeriert mir das es hier nicht um eine bestimmte Architektur geht.

Nun, das ist unbestreitbar korrekt und da ich merke, dass ich mit meiner Meinung auf verlorenem Posten stehe, wollte ich da nicht weiter argumentieren...

Okay, Thema erledigt.

Und die Lösung mit MAP_NOW/MAP_LAZY/MAP_AUTO/MAY_MAP_NOW/MAY_MAP_LAZY ist für uns alle akzeptabel.

Dann weiß FlashBurn ja jetzt wie er das umsetzen muss.

Das betrifft aber nur ganz wenige Aufgabenstellungen. Viele Aufgabenstellungen sind hinreichend auf ihre Optimierbarkeit bewiesen.

Natürlich, ich wollte mit der Kryptographie auch nur mal eine der wenigen Ausnahmen zeigen.

Heutige Compiler könnten da wesentlich effizienter optimieren.

Ob das stimmt werde ich sicher bald rausbekommen, aber ich bin guter Dinge.

RAM ist heutzutage billig und in ausreichender Menge verfügbar.

Aber der eine virtuelle Adressraum ist eben begrenzt und kann auch noch fragmentieren (und es gibt keine Möglichkeit zum defragmentieren, genau das hab ich ja mit meinen Segmenten). Cool wäre es wenn man mehrere Paging-Directorys hätte (auf x86 also mehrere CR3) und man bei jedem Speicherzugriff eines davon wählen könnte, dann hätte man mehrere unabhängige Adressräume. Aber bei dem riesigen Speicherverbrauch für die vielen Paging-Directorys erscheint mir die Segmentierung dann doch die bessere Wahl zu sein (obwohl das Ergebnis schon ziemlich ähnlich ist).

Außerdem muss ich beim Navi diese Funktion auch einschalten - ich habe die Möglichkeit, ein Wunschverhalten zu erzwingen.

Natürlich, niemand will Dir das Recht auf einen guten Stau wegnehmen (außer die Grünen vielleicht).

Bestes Bsp. wäre sogar ein malloc() wo ein SlabAllocator dahinter steckt der nur Blöcke mit 2er Potenzen hat.

Aber auch der kann seine Objekt-Pools nicht als beliebig großes Array (mit O(1)-Komplexität) verwalten (das ist das was ich mache) sondern muss die in mehreren Stücken (die Slabs) über den einen virtuellen Adressraum verteilen. Mich würde in diesem Zusammenhang mal interessieren wie das free von dem übergebenen Pointer auf die Objekt-Größe schließen kann um es dann auch in den richtigen Verwaltungsstrukturen als frei zu markieren.

sondern eine Lösung ist 64bit Architektur

Aber auch bei 64Bit sind die einzelnen Stack nicht unabhängig von einander und können sich gegenseitig blockieren (wenn auch auf einem größeren Niveau). Mein Angriff von http://forum.lowlevel.eu/index.php?topic=2224.msg25456#msg25456 funktioniert auch bei 64 Bit.

Die andere Lösung wären Stacks die nicht zusammenhängend sind. Ich habe sowas mal im Zusammenhang mit Linux gelesen, weiß aber nicht mehr wo das war oder wie das funktionieren soll.

Hm, da wird wohl versucht eine Murks-Krücke mit einer weiteren Murks-Krücke zu stützen. Ich bin entsetzt, obwohl eigentlich ist man ja so eine Vorgehensweise gewohnt.


Grüße
Erik

[FlashBurn]

Du warst es doch der hier mehrfach für neue Wege plädiert hat.

Ich sag ja auch gar nichts gegen neue Wege oder deine Architektur, es ist halt das Problem, dass deine Architektur noch nicht in Hardware existiert, das ich (oder wer auch immer) sie nicht haben kann und das ein OS welches für Segmente geschrieben (und optimiert) wurde sehr schlecht auf ne FlatMemory Architektur portierbar sein dürfte.

umgedreht erscheint mir das ziemlich selten (jedenfalls kann ich mich nur vereinzelt daran erinnern gut auf Segmentierung passende Antworten bekommen zu haben).

Das könnte daran liegen das es nicht so einfach zu verstehen ist Ich habe jedenfalls immernoch Probleme damit.

aber wenigstens etwas Toleranz wäre nicht schlecht.

Ach ich denke Toleranz ist nicht das Problem. Es ist halt nur doof wenn einer sagt, ich habe hier folgendes Problem ... und du dann antwortest, auf meiner Architektur mit meinen Segmenten würde ich das so und so lösen. Ist zwar schön zu wissen, aber geholfen hat es nichts

Für sowas wäre es am besten wenn du extra Threads aufmachst (Problem wäre wahrscheinlich das sich kaum Leute finden lassen die dann mit diskutieren können/wollen) oder die Diskussion so allgemein gehalten wird das es für beides gilt.

Hast du es eigentlich schonmal versucht deine Architektur in anderen Foren vorzustellen und die Feedback/Meinungen einzuholen (nichts gegen die Leute hier, aber es gibt Foren, wo ich mal behaupte das sich mehr und fähigere Leute rumtreiben)?

Aber auch der kann seine Objekt-Pools nicht als beliebig großes Array (mit O(1)-Komplexität) verwalten (das ist das was ich mache) sondern muss die in mehreren Stücken (die Slabs) über den einen virtuellen Adressraum verteilen.

Das ist z.B. glaub ich ein Punkt wo sich mein OS von anderen unterscheidet. Denn bei mir macht das nicht der User sondern der Kernel. Du rufst nur den Kernel auf das du neuen Speicher brauchst und wieviel und bekommst (sofern genug virtueller Speicher frei ist) nen Pointer auf solch einen Bereich zurück.
Bei mir besteht der SlabAllocator im Endeffekt nur aus erstes Element der Liste entfernen und Element an den Anfang der Liste packen.
Was bei mir nicht O(1) ist, ist unter Umständen das Suchen nach der Liste (unter Linux geht das).

Mich würde in diesem Zusammenhang mal interessieren wie das free von dem übergebenen Pointer auf die Objekt-Größe schließen kann um es dann auch in den richtigen Verwaltungsstrukturen als frei zu markieren.

Dafür gibt es mehrere Möglichkeiten, einmal hat man BoundaryTags (also vor dem Pointer steht wie groß der Bereich ist und eventuell mehr) und einmal speicherst du die Info welcher Slab-Struktur verwendet wird in der Struktur für die physische Page (unter Linux wird das so gemacht, aber das verbraucht mir zu viel Speicher).

Um mal die Möglichkeit von Linux zu diskutieren. Die haben ja ne page_t Struktur, wo die so einige Infos speicher, z.B. wie oft ne Page gemappt ist, sowas ähnliches habe ich ja auch (ist ein großes Array) und wenn ich wollte könnte ich dieses Array bzw. die Elemente darin ja um 4Byte größer machen damit ich darin nen Pointer auf ne Slab-Struktur speichern könnte.
Dazu hätte ich dann mal 2 Fragen. Ich sehe es halt so das der Speicherverbrauch eigentlich zu hoch dafür ist (die paar Pages die in meinem Kernel dann gemappt werden, max 1GB) oder wie seht ihr das?
Das nächste ist, was könnte man in so einem Pointer/Wert noch speichern, damit es sich doch lohnen würde das zu nutzen?

Problem was ich sehe, ist das es nur Infos sein dürfen die ich im Kernel brauchen könnte. Denn extra nen Syscall zu machen um die Info aus diesem Pointer zu bekommen, kostet mehr Performance als sie bringen würde und ist ein Sicherheits-Problem.

Mein Angriff von http://forum.lowlevel.eu/index.php?topic=2224.msg25456#msg25456 funktioniert auch bei 64 Bit.

Ich habe mir jetzt nicht alles durchgelesen, aber es läuft ja darauf hinaus, das ne Guard-Page von 4KB unzureichend erscheint, da man mit nem Index von nem Array leicht über diese Grenze hinauskommt.
Ich sehe es eigentlich so, na und! Ist ein Fehler des Programms und entweder es schmiert ab (weil keine Zugriffsrechte) oder es wird was überschrieben und schmiert dann ab oder es kann fremder Code ausgeführt werden. Bei letzterer Variante ist halt das Programm schuld, sicher sollte man als OS versuchen so gut es geht sich auch vor solchen Problemen zu schützen, aber ich weiß nicht ob das Verhältnis von Aufwand Nutzen da so toll ist.

[erik.vikinger]

Hallo,

und das ein OS welches für Segmente geschrieben (und optimiert) wurde sehr schlecht auf ne FlatMemory Architektur portierbar sein dürfte.

Ein OS für Segmentierung ist überhaupt nicht auf Flat-Memory portierbar.

Das könnte daran liegen das es nicht so einfach zu verstehen ist

Naja, es gibt einfach nicht viele Leute die sich damit überhaupt schon mal (wenn auch nur gedanklich) beschäftigt haben.
Aber wenn ich mal so weit bin wird sich das sicher ändern.

Es ist halt nur doof wenn einer sagt, ich habe hier folgendes Problem ... und du dann antwortest, auf meiner Architektur mit meinen Segmenten würde ich das so und so lösen. Ist zwar schön zu wissen, aber geholfen hat es nichts

Vor allem weil meine Antworten ab und an mal nach dem Prinzip "Ich hab Segmente, ich hab Dein Problem prinzipiell nicht, ätsch bätsch!" sind. Ich bin aber wirklich der Meinung das mir die Segmente mehr Probleme lösen als schaffen, aber ob das auch in der Realität so ist muss ich noch beweisen. Ich gebe aber auch manchmal Antworten die sehr gut (auf Flat-Memory) passen.

Hast du es eigentlich schonmal versucht deine Architektur in anderen Foren vorzustellen und die Feedback/Meinungen einzuholen (nichts gegen die Leute hier, aber es gibt Foren, wo ich mal behaupte das sich mehr und fähigere Leute rumtreiben)?

Nein, bis jetzt noch nicht. Hast Du da ein paar Vorschläge, was die Leute hier von meinen Plänen halten weiß ich nun ziemlich genau aber an neuem Feedback wäre ich schon sehr interessiert.
Mein Problem ist das wenn ich das Wort "Segmentierung" benutze dann bekomme ich entweder Schulterzucken als Antwort oder manche Leute (die alt genug sind) erinnern sich an den x86-Real-Mode und erklären das Segmentierung voll Sch.... ist. Mit wirklicher dynamischer Segmentierung (wie sie auch der 386 im PM bietet, zumindest in brauchbaren Ansätzen) haben sich einfach nie wirklich Leute beschäftigt.

Denn bei mir macht das nicht der User sondern der Kernel. Du rufst nur den Kernel auf das du neuen Speicher brauchst und wieviel und bekommst (sofern genug virtueller Speicher frei ist) nen Pointer auf solch einen Bereich zurück.

Du machst den Heap für den User-Mode im Kernel? Und dann noch Page-basiert? Gibt es dann jedes mal 4032 Bytes Verlust wenn ich ein Objekt mit 64 Bytes allozieren will?

Mich würde in diesem Zusammenhang mal interessieren wie das free von dem übergebenen Pointer auf die Objekt-Größe schließen kann um es dann auch in den richtigen Verwaltungsstrukturen als frei zu markieren.

Dafür gibt es mehrere Möglichkeiten, einmal hat man BoundaryTags (also vor dem Pointer steht wie groß der Bereich ist und eventuell mehr)

Das klingt nicht sehr vertrauenerweckend, das kann doch die Applikation ganz schnell mal kaputt machen und dann ist die Hölle los.

und einmal speicherst du die Info welcher Slab-Struktur verwendet wird in der Struktur für die physische Page (unter Linux wird das so gemacht, aber das verbraucht mir zu viel Speicher).

Das ist aber IMHO nichts für den User-Mode-Heap, für den Kernel selber sieht das aber schon recht interessant aus. Es geht mir aber auch um den SlabAllocator für den User-Mode-Heap und da scheint es nicht viel besseres als suchen zu geben weil man dem Pointer die Größe des Objekts nicht einfach so ansieht (und wieder ein Vorteil meiner Segmente, über den Selector kann ich genau sagen in welchem Segment das Objekt liegt und dann kurz nachschauen welche Objektgröße darin untergebracht ist).

Mein Angriff von http://forum.lowlevel.eu/index.php?topic=2224.msg25456#msg25456 funktioniert auch bei 64 Bit.

Ich habe mir jetzt nicht alles durchgelesen, aber es läuft ja darauf hinaus, das ne Guard-Page von 4KB unzureichend erscheint, da man mit nem Index von nem Array leicht über diese Grenze hinauskommt.
Ich sehe es eigentlich so, na und! Ist ein Fehler des Programms und entweder es schmiert ab (weil keine Zugriffsrechte) oder es wird was überschrieben und schmiert dann ab oder es kann fremder Code ausgeführt werden. Bei letzterer Variante ist halt das Programm schuld

Die Schuld für solche Probleme auf das Programm zu schieben ist IMHO der falsche Weg. Wir leben in einer Zeit wo Browser (und auch etliche andere Programme) Plug-Ins haben, die wie eine Shared-Library in den Adressraum des Browsers eingeblendet werden und dann dort alles tun können. Das viele dieser Plug-Ins auch noch Closed-Source sind macht die Situation erst recht nicht einfacher. Ein paar mehr Restriktionen damit sich eventuelle Lücken nicht zu leicht ausnutzen lassen wären schon nicht verkehrt, denn absolut fehlerfreie Software ist absolut unmöglich.

sicher sollte man als OS versuchen so gut es geht sich auch vor solchen Problemen zu schützen, aber ich weiß nicht ob das Verhältnis von Aufwand Nutzen da so toll ist.

Ich will ja nicht schon wieder die Segmente erwähnen aber mit denen ist dieses Problem recht einfach zu lösen.


Grüße
Erik

[FlashBurn]

Hast Du da ein paar Vorschläge

Naja, das Standardboard schlecht hin was osdev betrifft (behaupte ich mal) http://forum.osdev.org/index.php. Ob die mit deiner Idee klarkommen, weiß ich aber nicht.

Du machst den Heap für den User-Mode im Kernel? Und dann noch Page-basiert? Gibt es dann jedes mal 4032 Bytes Verlust wenn ich ein Objekt mit 64 Bytes allozieren will?

Genau deswegen wäre es toll wenn mir mal jemand erklärt was der Heap ist und was er macht. Denn was du mit Heap meinst, ist doch einfach nur malloc() und malloc() ruft entweder sbrk() oder mmap() auf um neuen Speicher zu bekommen.
Und genau letzteres meine ich! Was und wie malloc() dann den Speicher organisiert weiß ich nicht bzw. lege ich nicht fest.
Für mich ist der Heap einfach nur ein Speicherbereich der von malloc() genutzt wird und Page-basiert ist. Bei mir ist dieser Speicherbereich nur nicht zwingend zusammenhängend.

Das klingt nicht sehr vertrauenerweckend, das kann doch die Applikation ganz schnell mal kaputt machen und dann ist die Hölle los.

Sorry, aber jetzt kommt bei mir wieder Unverständnis! Ihr (du und svenska) sagt, dass ein "Verbraucher" seine Ressourcen so wieder zurück gibt wie er sie bekommen hat (also nicht 3 IDs miteinmal), aber hier sagst du jetzt dass das ja doof ist und das Programm amok laufen kann.
Ist bei nem SlabAllocator nicht anders, da musst du auch darauf vertrauen das die Adresse die freigegeben werden soll auch die richtige ist.
Alles andere wäre aber auch entweder Speicherverschwenderisch und/oder langsam.

Das ist aber IMHO nichts für den User-Mode-Heap, für den Kernel selber sieht das aber schon recht interessant aus.

Das weiß ich ja, aber ich finde es halt auch nicht so toll, wenn man für max 1GB (von 4 möglichen) Speicher verbraucht das aber für den Rest nicht nutzen kann.
Deswegen, nochmals die Frage was man in so einem Pointer/Wert noch speichern könnte, was für den Kernel vllt ganz interessant sein könnte?

Ich will ja nicht schon wieder die Segmente erwähnen aber mit denen ist dieses Problem recht einfach zu lösen.

Wenn man den Stack wirklich nur für lokale Variablen nutzen würde und nicht die Adressen von diesen Variablen nutzen/brauchen würde, dann könnte man ganz einfach auch unter PM im 32bit Modus Segmente für den Stack nutzen. Damit wäre das Problem auch gegessen und der Compiler müsste es nicht mal wissen.

[erik.vikinger]

Hallo,

Naja, das Standardboard schlecht hin was osdev betrifft (behaupte ich mal) http://forum.osdev.org/index.php. Ob die mit deiner Idee klarkommen, weiß ich aber nicht.

Da bin ich mir nicht sicher ob dafür mein Englisch reicht. Aber wenn meine OpCode-Spec fertig ist sollte ich vielleicht wirklich noch mal ein bisschen mehr Feedback einholen.

Genau deswegen wäre es toll wenn mir mal jemand erklärt was der Heap ist und was er macht.

Sorry, aber so wie Du über SlabAllocator & Co geschrieben hast dachte ich eigentlich Du wüsstest das bereits. Der Heap ist der Mechanismus der dem User-Code Speicher zur Verfügung stellt, der entscheidende Punkt ist das der User-Code beliebig große Speicherstückchen anfordern darf und der Heap-Mechanismus dafür sorgen muss das da trotzdem möglichst wenig Verschnitt entsteht. Darüber hinaus ist es Aufgabe des Heap-Mechanismus ein einheitliches API (malloc/free) zur Verfügung zu stellen und die konkreten OS-Funktionen dahinter zu verstecken (wegabstrahieren).

Denn was du mit Heap meinst, ist doch einfach nur malloc() und malloc() ruft entweder sbrk() oder mmap() auf um neuen Speicher zu bekommen.

Exakt.

Was und wie malloc() dann den Speicher organisiert weiß ich nicht bzw. lege ich nicht fest.

Doch, gerade Du als OS-Entwickler musst festlegen wie die Heap-Implementierung von der zu Deinem OS gehörenden libc arbeiten soll. Da hast Du im Prinzip 2 Möglichkeiten: entweder Du nimmst ne fertige libc und musst in Deinem OS genau die Syscalls anbieten die diese libc erwartet oder Du programmierst ne eigene libc und kannst dann die speziellen Fähigkeiten Deines OS nach belieben nutzen (solange die malloc/free-API erhalten bleibt). Ich denke die meisten hier sind den zweiten Weg gegangen und ich will das auch tun.

Für mich ist der Heap einfach nur ein Speicherbereich der von malloc() genutzt wird und Page-basiert ist.

Richtig, solange die Heap-Implementierung in der Lage ist den Speicher auch in anderen Größen als in Pages dem User-Code zur Verfügung zu stellen.

Bei mir ist dieser Speicherbereich nur nicht zwingend zusammenhängend.

Das muss er auch nicht, das ist ganz allein Deine freie Entscheidung.

Das klingt nicht sehr vertrauenerweckend, das kann doch die Applikation ganz schnell mal kaputt machen und dann ist die Hölle los.

Sorry, aber jetzt kommt bei mir wieder Unverständnis! Ihr (du und svenska) sagt, dass ein "Verbraucher" seine Ressourcen so wieder zurück gibt wie er sie bekommen hat (also nicht 3 IDs miteinmal), aber hier sagst du jetzt dass das ja doof ist und das Programm amok laufen kann.

Sorry, aber da hab ich mich wohl undeutlich ausgedrückt. Wenn die Verwaltungsstrukturen direkt neben den verwalteten Speicherblöcken liegen dann kann der User-Code diese Verwaltungsinformationen ganz leicht mal (aus versehen) überschreiben. Ich persönlich halte diese Vorgehensweise für ein erhebliches Risiko, gerade in Zeiten von allgegenwärtigen Buffer-Overflows. Ich weiß das viele Heap-Implementierungen das mit den Verwaltungsinformationen genau so machen und das dort nicht viel schlimmes passiert liegt sicher auch daran das dann oft einfache Prüfsummen u.ä. eingesetzt werden um Manipulationen zu erkennen. Trotzdem bin ich der Meinung das man die Verwaltungsinformationen von den Nutzdaten trennen sollte.

Ist bei nem SlabAllocator nicht anders, da musst du auch darauf vertrauen das die Adresse die freigegeben werden soll auch die richtige ist.

Also Vertrauen hab ich in sowas nicht all zu viel, dafür sind schon viel zu viele "fehlerfreie" Applikationen zum Problemfall geworden. Ich bevorzuge es wenn free den übergeben Pointer zu 100% auf Gültigkeit prüfen kann. So hab ich das jetzt auch in meiner User-Mode-Heap-Implementierung umgesetzt und auch das doppelte freigeben ist kein Problem mehr. Im Kernel würde ich das mit der Pointer-Prüfbarkeit wieder anders sehen, das ist ein geschlossenes System wo nur Du selber Fehler machen kannst und dort kann man z.B. für jeden Objekt-Typ/Größe ein eigenes free implementieren (im Kernel musst Du Dich nicht ans normale malloc/free-API halten).

Das weiß ich ja, aber ich finde es halt auch nicht so toll, wenn man für max 1GB (von 4 möglichen) Speicher verbraucht das aber für den Rest nicht nutzen kann.

Für den User-Space könntest Du dort den Page-Mapping-Counter (für Pages die in mehreren Adressräumen gemappt sind) unterbringen, im Kernel wirst Du doch hoffentlich kein Shared-Memory machen.

Wenn man den Stack wirklich nur für lokale Variablen nutzen würde und nicht die Adressen von diesen Variablen nutzen/brauchen würde, dann könnte man ganz einfach auch unter PM im 32bit Modus Segmente für den Stack nutzen. Damit wäre das Problem auch gegessen und der Compiler müsste es nicht mal wissen.

Das Problem ist das Du eben doch von Stack-Variablen eine Adresse generieren können musst. Im Prinzip sind die Modifikationen an einem Compiler recht überschaubar um ihm FAR-Pointer bei zu bringen. Als erstes muss der Compiler Pointer nicht auf Integer o.ä. abbilden sondern als einen eigenständigen Basis-Datentyp betrachten (das ist beim LLVM gegeben aber beim gcc nicht). Dann muss der Compiler in der Lage sein für bestimmte Datentypen mehrere Register als Einheit zu betrachten (also Segment-Register für den Selector + normales Register für das Offset) aber auch das sollte jeder Compiler können der z.B. auf einer 32Bit-CPU mit 64Bit-Integern umgehen kann. Die kritischen Stellen sind das Benutzen von Pointern (also bei jedem Speicherzugriff das richtige Segment-Register auswählen) und das Erzeugen von Pointern (also auch jedes mal das richtige Segment-Register als Quelle für den Selector benutzen). Ich denke das ich das beim LLVM alles hinbekommen werde aber wie schwierig es wirklich wird kann ich erst sagen wenn ich das auch tatsächlich geschafft hab.


Grüße
Erik

[Svenska]

Hallo,

Schonmal was von nem O(1) Scheduler gehört, der macht ja im Endeffekt auch nichts anderes als sortieren und suchen. Du musst die Menge der Elemente nur weit genug einschränken und schon geht das

Der sortiert nicht (er nimmt vorne weg und hängt hinten an) und er sucht nicht (er nimmt immer das erste Element). Definiere "sortieren" und "suchen". Wenn du n natürlich auf 1 beschränkst, weil es nur ein Element gibt, dann hat ein O(n)-Algorithmus eine O(1)-Laufzeit. Deswegen ist es aber trotzdem ein O(n)-Algorithmus.

Vergleiche mal die Laufzeit von Bubblesort und Quicksort für n Elemente (1k < n < 100k) und entscheide dann, ob dir solche Lösungen gefallen oder du nicht lieber doch den Stack allgemein größer baust. RAM ist heutzutage billig und in ausreichender Menge verfügbar.

Aber was ist mit meiner Idee QuickSort halt in Schritten anzuwenden?

Die ist Unsinn.

Wenn dein Quicksort feststellt, dass der Stackspace voll ist, dann müsstest du in jedem Fall einen weiteren Aufruf machen, um den Bubblesort auszuführen, und genau das geht zu dem Zeitpunkt nicht mehr. Mal abgesehen davon ist der Aufwand es nicht wert und bei Quicksort verhält sich die Rekursionstiefe auch logarithmisch zur Anzahl der Elemente.

Zumal es ja darum ging das du ab einer bestimmten Anzahl von Threads die Stacks nicht mehr vergrößern kannst und da hilft dann auch mehr RAM nicht mehr, sondern eine Lösung ist 64bit Architektur.

Dann musst du die Anzahl der Threads beschränken (macht sich im Hinblick auf Scheduler und andere Dinge im System eh besser), asynchrones I/O machen (ein Hauptgrund für Workerthreads) oder den Stack im Voraus hinreichend groß machen. Die Stackanforderungen zwischen "ls" und einer MySQL-Datenbank werden sich schon hinreichend stark unterscheiden, dass man einen kleinen Stack (z.B. 256 KB) für alles macht und Prozessen, die damit nicht klarkommen, gleich 4 MB gibt...

Und wenn eine Aufgabe schon theoretisch nur in O(n^2) lösbar ist, so trifft dies auf jede noch so geniale Implementation zu (oder schlechter).

Wimre dann hatte ich in theoretischer Informatik mal, das man bei genau solchen Problemen sich einfach "bessere" Bedingungen (z.B. die Menge der Elemente einschränken o.ä.) schafft damit man die Probleme halt schneller lösen kann.

Damit löst du aber die Aufgabe nicht mehr. Wenn du ein konkretes Problem hast, kannst du die Aufgabenstellung nicht immer "mal eben so" einfach ändern, nur damit man es eleganter lösen kann. Und wenn du sortieren musst, dann hängt die Sortierdauer nunmal (a) von der Anzahl der zu sortierenden Elemente und (b) vom Sortierzustand ab. Für "Anzahl=const" ist das sicherlich in O(1) machbar, aber das geht eben nicht überall.

Außerdem muss ich beim Navi diese Funktion auch einschalten - ich habe die Möglichkeit, ein Wunschverhalten zu erzwingen.

Natürlich, niemand will Dir das Recht auf einen guten Stau wegnehmen (außer die Grünen vielleicht).

Bewusst in einen Stau reinfahren hatte ich auch schon. Das kommt nämlich dann zustande, wenn (bei kurzem Stau) die Umleitungsstrecke ewig viel Umweg ist und länger dauert als der Stauaufenthalt oder wenn die Ausweichstrecken ebenfalls überlastet sind. In letzterem Fall ist das oft schlimmer als der Stau selbst, weil die Strecken nicht für Massentransit gebaut sind. Es gibt schon Gründe, unter bestimmten Umständen einen Ratschlag zu ignorieren und trotzdem besser zu fahren... allerdings nicht immer.

Was bei mir nicht O(1) ist, ist unter Umständen das Suchen nach der Liste (unter Linux geht das).

Aua. Ich möchte auf deinem OS einen Benchmark machen und dir zeigen, was O(1) eigentlich bedeutet. Das Erstellen von einem Thread dauert exakt genausolange wie das Erzeugen von einer Million Threads? Ein malloc(1) dauert exakt genausolange wie ein malloc(1024*1024*1024) und ist unabhängig vom derzeitigen Zustand des physischen Speichers? Dein Mapping von physischem Speicher zu virtuellem Adressraum geschieht unabhängig von der Größe der Blöcke, unabhängig von der Fragmentierung aller Adressräume und unabhängig vom Füllstand des physischen Speichers? Ein free() dauert genausolange wie jedes andere free(), egal wo der Pointer hinzeigt?

Man kann für irgendeinen Teil ein O(1) haben, aber für das Gesamtsystem ist das wesentlich schwieriger. Mal abgesehen davon ist O(1) auch nicht immer erstrebenswert, es gibt Algorithmen mit O(1), die nicht verwendet werden, da ein O(e^n)-Algorithmus absolut gesehen schneller ist, solange man vernünftige Größen verwendet.

Um mal die Möglichkeit von Linux zu diskutieren. Die haben ja ne page_t Struktur, wo die so einige Infos speicher, z.B. wie oft ne Page gemappt ist, sowas ähnliches habe ich ja auch (ist ein großes Array) und wenn ich wollte könnte ich dieses Array bzw. die Elemente darin ja um 4Byte größer machen damit ich darin nen Pointer auf ne Slab-Struktur speichern könnte.

Ein Array ist bei bekanntem Index O(1), bei unbekanntem Index (=Suche) O(n), maximal O(log n).

Ist ein Fehler des Programms und entweder es schmiert ab (weil keine Zugriffsrechte) oder es wird was überschrieben und schmiert dann ab oder es kann fremder Code ausgeführt werden. Bei letzterer Variante ist halt das Programm schuld, sicher sollte man als OS versuchen so gut es geht sich auch vor solchen Problemen zu schützen, aber ich weiß nicht ob das Verhältnis von Aufwand Nutzen da so toll ist.

In der heutigen Zeit sollte man für Sicherheit durchaus viel Aufwand treiben... Spammer und Botnetze sind eine Folge dieses Schulterzuckens.

Gruß,
Svenska

[FlashBurn]

Der Heap ist der Mechanismus der dem User-Code Speicher zur Verfügung stellt, der entscheidende Punkt ist das der User-Code beliebig große Speicherstückchen anfordern darf und der Heap-Mechanismus dafür sorgen muss das da trotzdem möglichst wenig Verschnitt entsteht. Darüber hinaus ist es Aufgabe des Heap-Mechanismus ein einheitliches API (malloc/free) zur Verfügung zu stellen und die konkreten OS-Funktionen dahinter zu verstecken (wegabstrahieren).

Also können wir uns darauf einigen das der Heap == malloc()/free() ist!?

Mein Prof hat mich heute auch wieder "geärgert". Denn ich sehe es immernoch soch das malloc()/free() nichts mit dem OS zu tun zu haben. Die stehen in irgendeiner Library drin und das OS hat keine Kontrolle darüber. Genauso kann man malloc()/free() oder die Library einfach austauschen ohne dass das OS was an der Speicherverwaltung ändert.

Was mich halt dann immernoch irretiert, ist wenn Leute sagen das die UserSpace Speicherverwaltung auch komplett vom UserSpace gemacht wird (eigentlich meinen die den Heap, aber dann sollen sie es auch sagen!) und das ist halt nicht so. Der Heap kann sich bei mir halt nicht aussuchen wo neuer Speicher hingemappt wird, sondern er hat das zu nehmen was er vom OS bekommt.

Doch, gerade Du als OS-Entwickler musst festlegen wie die Heap-Implementierung von der zu Deinem OS gehörenden libc arbeiten soll.

Siehe oben. Was ist wenn ein Programm aber ne andere libc verwendet. Alles was im UserSpace stattfindet hat mit dem OS nichts mehr zu tun (in dem Sinne das du es bestimmen kannst, mal von Apple abgesehen ).

Trotzdem bin ich der Meinung das man die Verwaltungsinformationen von den Nutzdaten trennen sollte.

Ich sage mal das du dadurch mehr Verschnitt haben wirst und wahrscheinlich sogar langsamer sein wirst (wie reden von FlatMemory ).

Für den User-Space könntest Du dort den Page-Mapping-Counter (für Pages die in mehreren Adressräumen gemappt sind) unterbringen, im Kernel wirst Du doch hoffentlich kein Shared-Memory machen.

Doch im Kernel habe ich auch SharedMemory und ich will der Struktur (die in einem Array organisiert ist) ja noch ein Element von 4Byte Größe hinzufügen, aber nicht nur weil es den SlabAllocator im Kernel schneller macht (und Speicher spart).
Damit der Speicher den ich sparen würde sich auch rentiert, müsste ich mind. 209715 Slabs in meinem Kernel haben und ich denke das sollte nicht so einfach passieren.

Der sortiert nicht (er nimmt vorne weg und hängt hinten an) und er sucht nicht (er nimmt immer das erste Element). Definiere "sortieren" und "suchen".

Ich füge neue Threads sortiert ein, also sortiere ich und ich suche immer den Thread mit der größten Priorität, also suche ich!
Das selbe mit dem geposteten Allocator, der sucht und sortiert auch, er macht halt nur ein paar Annahmen, naund!

Wenn dein Quicksort feststellt, dass der Stackspace voll ist, dann müsstest du in jedem Fall einen weiteren Aufruf machen

Ich habe gesagt, dass man das vorher entscheiden muss! Nicht erst mittendrin.

Dann musst du die Anzahl der Threads beschränken (macht sich im Hinblick auf Scheduler und andere Dinge im System eh besser),

Das hieße aber das ich bei vielen Sachen gar nicht die Performance bekomme die ich haben könnte und das die Anwendung nicht skaliert und das geht heutzutag gar nicht!

Damit löst du aber die Aufgabe nicht mehr.

Das stimmt ja so nicht. Wenn du in Physik (Schule) die Aufgabe bekommst, irgendetwas zu berechnen, machst du auch viele Annahmen, damit du die ganze Rechnung vereinfachen kannst.
Genauso macht man das bei vielen Problemen in der Informatik (frag mich bitte nicht nach einem Bsp.).

was O(1) eigentlich bedeutet

Die Anzahl der Schritte ist immer gleich.

Ein malloc(1) dauert exakt genausolange wie ein malloc(1024*1024*1024) und ist unabhängig vom derzeitigen Zustand des physischen Speichers?

Was das malloc() betrifft ist dem so. Ich kann bei so einer Betrachtung nicht noch das OS mit einbeziehen. Denn es kann ja sein das ich gar nicht weiß wie das OS es macht oder auf welchen OS mein Code läuft. Trotzdem kann malloc() O(1) sein.

[quote="svenska"
Ein Array ist bei bekanntem Index O(1), bei unbekanntem Index (=Suche) O(n), maximal O(log n).
[/quote]
Der Index dieses speziellen Arrays ist bekannt (ist einfach die Nummer der physischen Page).

[erik.vikinger]

Hallo,

In der heutigen Zeit sollte man für Sicherheit durchaus viel Aufwand treiben... Spammer und Botnetze sind eine Folge dieses Schulterzuckens.

Full ACK!

Also können wir uns darauf einigen das der Heap == malloc()/free() ist!?

Ja, im wesentlichen schon.

Denn ich sehe es immernoch soch das malloc()/free() nichts mit dem OS zu tun zu haben.

Die User-Mode-Heap-Verwaltung ist existenziell abhängig von der Verwaltung des virtuellen Adressraums die das OS zur Verfügung stellt. Also die libc (oder eben die Heap-Library) muss immer zum OS passen.

Die stehen in irgendeiner Library drin und das OS hat keine Kontrolle darüber.

Grundsätzlich hast Du recht, das OS kann die User-Mode-Heap-Verwaltung nicht direkt beeinflussen.

Genauso kann man malloc()/free() oder die Library einfach austauschen ohne dass das OS was an der Speicherverwaltung ändert.

Nur so lange die neue Library auch wieder zum OS passt. Es ist ja gerade die Aufgabe der libc dem User-Code ein paar Basis-Funktionen zur Verfügung zu stellen und eben die OS-Funktionen die das dann tatsächlich bewerkstelligen zu verstecken(wegabstrahieren), dazu ist es natürlich erforderlich das die libc zum OS passt also das OS auch so benutzen kann wie das OS eben funktioniert. Deine libc wird auf tyndur garantiert nicht laufen es sei denn Dein OS ist mit tyndur auf Syscall-Ebene exakt 100% kompatibel.

Was mich halt dann immernoch irretiert, ist wenn Leute sagen das die UserSpace Speicherverwaltung auch komplett vom UserSpace gemacht wird (eigentlich meinen die den Heap, aber dann sollen sie es auch sagen!) und das ist halt nicht so.

Doch das ist so, die User-Space-Heap-Verwaltung wird komplett im User-Space gemacht, das OS stellt nur den virtuellen Speicher zur Verfügung. Das Straßenbauamt kontrolliert ja auch nicht Deine fahrweise, es stellt nur die Straßen zur Verfügung von denen Du abhängig bist (wenn wir jetzt mal von einem nicht geländefähigem Auto ausgehen) und Deine fahrweise bestimmst Du selber (eben im Rahmen dessen was die Straßen hergeben).
Das OS macht zwar eventuell ein paar Einschränkungen weil es den virtuellen Speicher auf eine bestimmte Art verwaltet/anbietet aber so lange die libc (die ja eben zum OS passen muss) damit gut umgehen kann ist aus Sicht des User-Codes der Heap immer der selbe und völlig unabhängig vom OS.
Man kann aber auch in ein Programm eine zusätzliche Speicherverwaltung für spezielle Dinge parallel zum Heap implementieren, aber diese Speicherverwaltung ist dann auch wieder existenziell vom OS abhängig (also nicht wirklich protierbar).

Der Heap kann sich bei mir halt nicht aussuchen wo neuer Speicher hingemappt wird, sondern er hat das zu nehmen was er vom OS bekommt.

Das ist eine Designentscheidung die Du als OS-Entwickler getroffen hast, wenn die Heap-Verwaltung die Du als libc-Entwickler schreibst damit gut umgehen kann ist das auch völlig in Ordnung.
Ich persönlich würde es aber bevorzugen wenn der User-Mode-Code (also die Heap-Verwaltung) selber bestimmen kann wie sein virtueller Adressraum aufgebaut ist (in gewissen Grenzen natürlich), ich stelle mir vor (ohne es zu wissen) dass das die Heap-Verwaltung einfacher macht.

Was ist wenn ein Programm aber ne andere libc verwendet.

Dann sollte es eine libc sein die ebenfalls auf Deinem OS funktioniert ansonsten funktioniert das Programm einfach nicht (wahrscheinlich kannst Du eine fremde/unpassende libc nicht mal für Dein OS kompilieren weil in Deinen OS-spezifischen Headerfiles ja andere Syscalls deklariert sind).

Trotzdem bin ich der Meinung das man die Verwaltungsinformationen von den Nutzdaten trennen sollte.

Ich sage mal das du dadurch mehr Verschnitt haben wirst und wahrscheinlich sogar langsamer sein wirst (wie reden von FlatMemory ).

Ja, natürlich erzeugt das etwas mehr Verschnitt bzw. in diesem Fall konstanten Overhead pro Objekt, das ist auch bei mir so, denn ich wollte eigentlich die freien Objekte mit dem eigenen Speicher dieser Objekte verwalten und da gäbe es eben Probleme wenn ein Objekt doppelt dealloziert werden soll (in meinem Kernel werde ich das aber so machen weil ich da ja nicht mit fehlerhaften User-Code rechnen muss). Signifikant langsamer dürfte das aber IMHO nicht werden (nur ein ganz klein Wenig weil ein paar mehr Speicherzugriffe pro malloc/free erforderlich sind).

Doch im Kernel habe ich auch SharedMemory

Hm, na wenn das mal gut geht.

und ich will der Struktur (die in einem Array organisiert ist) ja noch ein Element von 4Byte Größe hinzufügen, aber nicht nur weil es den SlabAllocator im Kernel schneller macht (und Speicher spart).

Ist den ein schnellerer SlabAllocator kein erstrebenswertes Ziel? Ich persönlich finde schon und in meinem OS-Kernel lasse ich mir das auch gerne etwas Speicher kosten.

Wenn dein Quicksort feststellt, dass der Stackspace voll ist, dann müsstest du in jedem Fall einen weiteren Aufruf machen

Ich habe gesagt, dass man das vorher entscheiden muss! Nicht erst mittendrin.

Und wie willst Du vorher bestimmen wie tief QuickSort rekursieren muss? Das einzigste Kriterium was Du hast ist die Größe der zu sortierenden Daten aber damit verschenkst Du eventuell sehr viel wenn die Daten schon einigermaßen gut sortiert sind und kaum Rekursion nötig wäre.

Das stimmt ja so nicht. Wenn du in Physik (Schule) die Aufgabe bekommst, irgendetwas zu berechnen, machst du auch viele Annahmen, damit du die ganze Rechnung vereinfachen kannst.
Genauso macht man das bei vielen Problemen in der Informatik (frag mich bitte nicht nach einem Bsp.).

Dann frage ich Dich nach einem Beispiel!
Wenn Du bestimmte Annahmen im Vorfeld machst dann must Du auch garantieren das diese zur Laufzeit noch gültig sind. Kannst Du das in jedem Fall?


Grüße
Rik

[FlashBurn]

In der heutigen Zeit sollte man für Sicherheit durchaus viel Aufwand treiben... Spammer und Botnetze sind eine Folge dieses Schulterzuckens.

Sorry, aber das ist für mich eine typisch deutsche herangehensweise (wie die es in die IT geschafft hat, ist mir ein Rätsel ).
Denn was hier gemacht wird ist Symptom Bekämpfung und nicht die Ursachen beseitigen!

Warum sollte sich denn ein Programmierer um solche Sachen wie nen Bufferoverflow kümmern, wenn das OS es doch macht und es so auch noch performanter ist? Ich will nicht die Bequemlichkeit der Programmierer unterstützen.

Doch das ist so, die User-Space-Heap-Verwaltung wird komplett im User-Space gemacht, das OS stellt nur den virtuellen Speicher zur Verfügung.

Aber welchen Teil des virtuellen Speichers der Heap belegt, das wird halt nicht (unbedingt) im UserSpace gemacht!
Ich rede da von solchen Sachen, das man es ja auch so machen könnte das der ganze virtuelle Adressraum auch selbst vom UserSpace verwaltet wird, sprich der Code entscheidet wo ne Library hingemappt wird oder nen Stack oder halt der Heap und genau das seh ich halt nicht so (und ist sei ALR - oder wie das heißt - auch nicht mehr so und ihr wollt ja Sicherheit).

ich stelle mir vor (ohne es zu wissen) dass das die Heap-Verwaltung einfacher macht.

Wieso macht es die Heap-Verwaltung einfacher? Du musst jedes Mal auch den Fall einplanen das du den virtuellen Bereich den du haben willst nicht bekommst und wenn du den Fall eh einplanen musst, dann mach es doch gleich nur so das du den Bereich nimmst den du vom OS bekommst.

Dann sollte es eine libc sein die ebenfalls auf Deinem OS funktioniert ansonsten funktioniert das Programm einfach nicht

Das sollte eigentlich klar sein. Ich meine sowas wie ne libc von GNU und ne libc von LLVM und ne dietlibc usw. Alle können andere Algos implementieren, aber laufen auf deinem OS.

Signifikant langsamer dürfte das aber IMHO nicht werden (nur ein ganz klein Wenig weil ein paar mehr Speicherzugriffe pro malloc/free erforderlich sind).

Anders gefragt, was für eine Datenstruktur willst du denn einsetzen, dass es nicht signifikant langsamer wird (schreib aber bitte ob das nur mit deinen Segmenten funktioniert)?

Hm, na wenn das mal gut geht.

Gegenfrage, was soll denn schief gehen?

Ist den ein schnellerer SlabAllocator kein erstrebenswertes Ziel?

Du weißt doch noch die magischen 8MB

Aber ich habe gerade mal nachgerechnet, bei 4Byte pro Wert, macht das zusätzliche 1KB pro 1MB RAM pro Wert, ich denke das kann man verschmerzen

Jetzt mal was zu diesem Thema. Ich habe im Moment eine Struktur die so aussieht:

Code: [Auswählen]

struct vmmSharedPageEntry_t {
struct spinlock_t lock;
uint32t refCount;
struct list_t *tasks;
};

Ich führe also nen refCount und ich trage die Prozesse ein, die diese Page nutzen. Das Lock ist halt zum Prozess eintragen da.
Meine Frage wäre jetzt, muss/sollte ich wirklich Buch führen wo (im Sinne von in welchem Prozess) eine physische Page überall gemappt ist?
Weil wenn nicht dann könnte ich das Lock und die Liste rausnehmen und beschleunige meinen SlabAllocator etwas

Und wie willst Du vorher bestimmen wie tief QuickSort rekursieren muss? Das einzigste Kriterium was Du hast ist die Größe der zu sortierenden Daten aber damit verschenkst Du eventuell sehr viel wenn die Daten schon einigermaßen gut sortiert sind und kaum Rekursion nötig wäre.

Ich würde abwegen, was ist langsamer/schlechter, wenn ich irgendwann feststelle das mein Stack nicht mehr reicht und ich nen iterativen Sortier-Algo einsetzen muss oder das ich genau den von dir genannten Fall in kauf nehmen und dafür das Problem mit dem Stack gelöst habe und der worst-case wesentlich schneller ist.
Die Rekursionstiefe, würde ich anhand der Datenmenge festmachen. Was würde ich denn verschenken?

Dann frage ich Dich nach einem Beispiel!

Hättest du dich nicht bei dem "du" mit einschließen können

Wenn Du bestimmte Annahmen im Vorfeld machst dann must Du auch garantieren das diese zur Laufzeit noch gültig sind. Kannst Du das in jedem Fall?

Da ich das nicht mathematisch beweisen kann, sage ich mal nein.

Als Bsp. würde ich jetzt malloc() nehmen. Wenn du alle Größen die auftreten können/werden sortieren willst wirst du wohl schonmal ne Weile brauche, machst du jetzt aber die Annahme das auch Blöcke mit den Größen der 2er Potenzen reichen, kannst du schon viel schneller und einfacher sortien, nämlich in O(1).
Du hast damit zwar unter Umständen einen tierischen Verschnitt, aber was solls

[Svenska]

Hallo,

In der heutigen Zeit sollte man für Sicherheit durchaus viel Aufwand treiben... Spammer und Botnetze sind eine Folge dieses Schulterzuckens.

Sorry, aber das ist für mich eine typisch deutsche herangehensweise (wie die es in die IT geschafft hat, ist mir ein Rätsel ).
Denn was hier gemacht wird ist Symptom Bekämpfung und nicht die Ursachen beseitigen!

Warum sollte sich denn ein Programmierer um solche Sachen wie nen Bufferoverflow kümmern, wenn das OS es doch macht und es so auch noch performanter ist? Ich will nicht die Bequemlichkeit der Programmierer unterstützen.

Das OS kann also noch performanter Bufferoverflows verursachen? Prima...

Programmierer sind faul und bequem (andere Interpretation: unter enormem Zeitdruck, enormem Featuredruck und nur wenig Qualitätssicherung). Die Folgen sind Bufferoverflows in Betriebssystemen (inzwischen nicht mehr so häufig, solche Lücken haben enormen Marktwert), Bufferoverflows in Anwendungen (Flash, Acrobat Reader und alle Webbrowser sind derzeit bevorzugter Angriffsvektor) und Sicherheitsprobleme/falsche Annahmen in den Standardkonfigurationen (Botnetze auf Plasteroutern sind richtig prima).

Wozu Passwörter übers Netz mit MD5 hashen und auch noch verschlüsselt auf der Festplatte abspeichern?

Das sollte eigentlich klar sein. Ich meine sowas wie ne libc von GNU und ne libc von LLVM und ne dietlibc usw. Alle können andere Algos implementieren, aber laufen auf deinem OS.

Alle sind auf dein OS angepasst. Im Falle von glibc/dietlibc/newlib benutzen die Bibliotheken genau die Services, die laut POSIX-Standard vom Kernel bereitgestellt werden müssen, eventuell noch zusätzliche. Darum laufen diese auch nicht auf jedem OS...

Und wie willst Du vorher bestimmen wie tief QuickSort rekursieren muss? Das einzigste Kriterium was Du hast ist die Größe der zu sortierenden Daten aber damit verschenkst Du eventuell sehr viel wenn die Daten schon einigermaßen gut sortiert sind und kaum Rekursion nötig wäre.

Ich würde abwegen, was ist langsamer/schlechter, wenn ich irgendwann feststelle das mein Stack nicht mehr reicht und ich nen iterativen Sortier-Algo einsetzen muss oder das ich genau den von dir genannten Fall in kauf nehmen und dafür das Problem mit dem Stack gelöst habe und der worst-case wesentlich schneller ist.

Vergleiche bitte nochmals die Geschwindigkeitsunterschiede zwischen einem Bubblesort und einem Quicksort.

Die Rekursionstiefe, würde ich anhand der Datenmenge festmachen. Was würde ich denn verschenken?

Falsche Grundannahme, denn die Rekursionstiefe wird neben der Datenmenge auch entscheidend vom Sortierzustand bestimmt. Aber ich finde es interessant, dass du von hocheffizienten Algorithmen redest und einen ebensolchen für RAM einschränkst.

Wenn Du bestimmte Annahmen im Vorfeld machst dann must Du auch garantieren das diese zur Laufzeit noch gültig sind. Kannst Du das in jedem Fall?

Da ich das nicht mathematisch beweisen kann, sage ich mal nein.

Dann darfst du diese Annahmen nicht treffen.

Als Bsp. würde ich jetzt malloc() nehmen. Wenn du alle Größen die auftreten können/werden sortieren willst wirst du wohl schonmal ne Weile brauche, machst du jetzt aber die Annahme das auch Blöcke mit den Größen der 2er Potenzen reichen, kannst du schon viel schneller und einfacher sortien, nämlich in O(1).

Das glaube ich dir nicht. O(1) ist eine sehr heftige Einschränkung. Es wird trotzdem O(n), n=Anzahl der Blockgrößen, 1<n<20, sein. Dort spielt die Sortierzeit keine Rolle.

Mein Prof hat mich heute auch wieder "geärgert". Denn ich sehe es immernoch soch das malloc()/free() nichts mit dem OS zu tun zu haben. Die stehen in irgendeiner Library drin und das OS hat keine Kontrolle darüber. Genauso kann man malloc()/free() oder die Library einfach austauschen ohne dass das OS was an der Speicherverwaltung ändert.

Sie haben aber gefälligst direkt an das OS angepasst zu sein. Scheißegal, ob sie vom Kernel oder von der libc bereitgestellt werden: Sie sind extrem OS-spezifisch. Stellst du sie in der libc bereit, darfst du auch gern die Algorithmen ändern, aber es bleibt OS-spezifischer Code.

Der sortiert nicht (er nimmt vorne weg und hängt hinten an) und er sucht nicht (er nimmt immer das erste Element). Definiere "sortieren" und "suchen".

Ich füge neue Threads sortiert ein, also sortiere ich und ich suche immer den Thread mit der größten Priorität, also suche ich!
Das selbe mit dem geposteten Allocator, der sucht und sortiert auch, er macht halt nur ein paar Annahmen, naund!

Sortiert einfügen ist kein O(1), es sei denn, du hast für jede Priorität eine eigene Liste und fügst dort nicht ein, sondern hängst an. Wie du das suchen in O(1) machst, weiß ich nicht. Das ist O(n), n Anzahl der Prioritäten, also z.B. 1<n<10, damit relativ vernachlässigbar. Aber nicht O(1).

Wenn dein Quicksort feststellt, dass der Stackspace voll ist, dann müsstest du in jedem Fall einen weiteren Aufruf machen

Ich habe gesagt, dass man das vorher entscheiden muss! Nicht erst mittendrin.

Also konkret kein allgemeines Quicksort, sondern ein allgemeines Bubblesort und Quicksort nur unter bestimmten Randbedingungen (d.h. "genug" Stackspace).

Dann musst du die Anzahl der Threads beschränken (macht sich im Hinblick auf Scheduler und andere Dinge im System eh besser),

Das hieße aber das ich bei vielen Sachen gar nicht die Performance bekomme die ich haben könnte und das die Anwendung nicht skaliert und das geht heutzutag gar nicht!

Sowas reicht nicht:

Code: [Auswählen]

if (num_cores > 1) { worker_threads = num_cores*2; }
else { worker_threads = 4; }

Du kannst natürlich einen 486er mit 8MB RAM auch mit 16384 Threads nur für den httpd vollmüllen, ob der das mag, sei jetzt mal dahingestellt... Auf dem System dürften 2-3 Threads wesentlich effizienter sein, da das System weniger arbeiten muss und vor allem mehr RAM verfügbar ist, da weniger Threadverwaltung nötig ist.

Was du da erzählst, ist unreal. "Mehr Threads = Mehr Performance" ist schlichtweg falsch.

Damit löst du aber die Aufgabe nicht mehr.

Das stimmt ja so nicht. Wenn du in Physik (Schule) die Aufgabe bekommst, irgendetwas zu berechnen, machst du auch viele Annahmen, damit du die ganze Rechnung vereinfachen kannst.

Damit löse ich aber nicht die Aufgabe, sondern eine angepasste/vereinfachte Aufgabe. Und ich weiß, dass mein Ergebnis nur begrenzt gebrauchbar ist.

Genauso macht man das bei vielen Problemen in der Informatik (frag mich bitte nicht nach einem Bsp.).

Äh, doch?

Ein malloc(1) dauert exakt genausolange wie ein malloc(1024*1024*1024) und ist unabhängig vom derzeitigen Zustand des physischen Speichers?

Was das malloc() betrifft ist dem so. Ich kann bei so einer Betrachtung nicht noch das OS mit einbeziehen. Denn es kann ja sein das ich gar nicht weiß wie das OS es macht oder auf welchen OS mein Code läuft. Trotzdem kann malloc() O(1) sein.

Unzulässige Vereinfachung: Dein malloc() fragt beim VMM nach und es hängt von dem - also genau dem OS - ab, ob du nun konstante Laufzeit hast oder nicht. Du kannst gern sagen, dass ein Teil deiner malloc()-Implementation (und zwar genau der systemunabhängige Teil) von der Komplexität O(1) ist, aber für das gesamte malloc() von Aufruf bis Return kannst du nicht sprechen.

Gruß,
Svenska

[FlashBurn]

Vergleiche bitte nochmals die Geschwindigkeitsunterschiede zwischen einem Bubblesort und einem Quicksort.

Ich kann dir hier irgendwie nicht folgen. Das nen BubbleSort langsam ist und nen QuickSort schell, weiß ich, aber was du genau von mir willst ist mir nicht klar.

Ich sage nur, das man ein großes zu sortierendes Array (als Bsp.), welches aufgrund der Größe nicht sicher mit QuickSort sortiert werden kann, in mehrere Teile eingeteilt wird und die jeweils mit QuickSort (am besten noch jeder Teil in einem Thread) sortiert werden und wenn man dann das ganze Array sortiert sollte doch auch QuickSort ohne Probleme laufen (da die Teilstücke ja schon sortiert sind). Ich kann mich hier natürlich auch irren.

Das glaube ich dir nicht. O(1) ist eine sehr heftige Einschränkung. Es wird trotzdem O(n), n=Anzahl der Blockgrößen, 1<n<20, sein. Dort spielt die Sortierzeit keine Rolle.

Ich habe dir doch schon einen solchen Algo aufgeschrieben genannt. Indem du einfach das höchste gesetze Bit nimmst (und damit weißt in welche 2er Potenz die Größe fällt) und du dann in einem Array das erste Element aus einer Liste entfernst. Das ist O(1) denn die Schritte sind bei jeder Größe gleich (das höchste Bit bekommst du unter x86 mit bsr).

Sie haben aber gefälligst direkt an das OS angepasst zu sein. Scheißegal, ob sie vom Kernel oder von der libc bereitgestellt werden: Sie sind extrem OS-spezifisch. Stellst du sie in der libc bereit, darfst du auch gern die Algorithmen ändern, aber es bleibt OS-spezifischer Code.

Das sehe ich eben nicht so. Ansonsten müsstest du ja für jedes OS nen neuen Allocator schreiben, du kannst aber einfach einen Allocator nehmen (FlatMemory!) und den Algo verwenden!

Sortiert einfügen ist kein O(1), es sei denn, du hast für jede Priorität eine eigene Liste und fügst dort nicht ein, sondern hängst an.

Ja ich habe für jede Priorität eine Liste (das ist eben das was den Algo O(1) macht) und ob ich nun an eine Liste anfüge oder einfüge ist doch eigentlich das selbe.

Was du da erzählst, ist unreal. "Mehr Threads = Mehr Performance" ist schlichtweg falsch.

Es geht darum das du die Anzahl der Threads beschänken willst auch wenn sie mehr Performance bringen können.

Wie du das suchen in O(1) machst, weiß ich nicht.

Das selbe wie mit den 2er Potenzen. Ich habe ne Bitmap und in der suche ich das höchste gesetzte Bit, fertig!

Unzulässige Vereinfachung: Dein malloc() fragt beim VMM nach und es hängt von dem - also genau dem OS - ab, ob du nun konstante Laufzeit hast oder nicht. Du kannst gern sagen, dass ein Teil deiner malloc()-Implementation (und zwar genau der systemunabhängige Teil) von der Komplexität O(1) ist, aber für das gesamte malloc() von Aufruf bis Return kannst du nicht sprechen.

Wenn wir schon so die Haare spalten (zumal es um den malloc() Algo und nicht um den VMM Algo ging) dann kannst du auf einem modernen Mikroprozessor mit Cache und Out-Of-Order Ausführung nie O(1) garantieren, da nämlich der Eintrag nicht im Cache stehen kann und in die nächst höhere Cachestufe gewechselt wird und dann irgendwann in den RAM.
Auch kannst du ja nicht wissen ob eine Page nicht ausgelagert ist und dann müsste die auch erst nachgeladen werden (ist wie den VMM aufrufen) usw.

[Svenska]

Ich sage nur, das man ein großes zu sortierendes Array (als Bsp.), welches aufgrund der Größe nicht sicher mit QuickSort sortiert werden kann, in mehrere Teile eingeteilt wird und die jeweils mit QuickSort (am besten noch jeder Teil in einem Thread) sortiert werden und wenn man dann das ganze Array sortiert sollte doch auch QuickSort ohne Probleme laufen (da die Teilstücke ja schon sortiert sind). Ich kann mich hier natürlich auch irren.

Wie gesagt, ich halte das für nicht zielführend. Dann gib lieber im Voraus "genug Stack". Im Übrigen kostet ein Thread ebenfalls ein bisschen was an Speicher für Verwaltungsstrukturen und eine Sortierroutine mit stückweisem Sortieren und Multithreading macht den Code größer. Ich denke mal bei dem Speicheraufwand, den du da treiben würdest, kannst du es einfach dem Stack zuschlagen.

Außerdem, und dabei bleibe ich, sind die Anforderungen an ein System immer auch von den Fähigkeiten des Systems bestimmt. Das heißt, dass du ein System mit einstelligem Arbeitsspeicher sicherlich nicht so triezen wirst, wie ein System mit vierstelligem... und dass du den Standard-Stack somit auch abhängig vom vorhandenem RAM machen kannst. Mal abgesehen davon... der Stack für die Sortierung wächst mit der Datenmenge; auch die musst du erstmal in den Speicher stopfen. Ich will irgendwie nicht wissen, wie groß das Array sein muss, damit Quicksort 1 MB an Rekursions-Stack braucht...

Ich habe dir doch schon einen solchen Algo aufgeschrieben genannt. Indem du einfach das höchste gesetze Bit nimmst (und damit weißt in welche 2er Potenz die Größe fällt) und du dann in einem Array das erste Element aus einer Liste entfernst.

OK.

Sie haben aber gefälligst direkt an das OS angepasst zu sein. Scheißegal, ob sie vom Kernel oder von der libc bereitgestellt werden: Sie sind extrem OS-spezifisch. Stellst du sie in der libc bereit, darfst du auch gern die Algorithmen ändern, aber es bleibt OS-spezifischer Code.

Das sehe ich eben nicht so. Ansonsten müsstest du ja für jedes OS nen neuen Allocator schreiben, du kannst aber einfach einen Allocator nehmen (FlatMemory!) und den Algo verwenden!

Korrekt, solange dein beliebiger Allocator auf eine bekannte API des Kernels zurückgreift. Du kannst mir nicht erzählen, dass dein beliebiges malloc() in einer libc auf jedem x-beliebigen Betriebssystem läuft - auch mit Einschränkung auf FlatMemory nicht.

Eine identische Implementation würde ja sonst unverändert (und das ist der Punkt!) unter Windows NT, Windows 3.1 (erw.Mod.), DOS (mit Extender), Linux, Minix-386 und deinem OS laufen. Das geht nicht, weil die darunterliegende API eben nicht identisch ist.

Wenn natürlich dein Kernel eine Standard-POSIX-API zum VMM anbietet, wird jede POSIX-kompatible libc darauf ein malloc() aufsetzen können. Das ist prinzipiell vom Algorithmus unabhängig, denn es kommt auf die Interaktion mit dem OS an.

Was du da erzählst, ist unreal. "Mehr Threads = Mehr Performance" ist schlichtweg falsch.

Es geht darum das du die Anzahl der Threads beschänken willst auch wenn sie mehr Performance bringen können.

Kennst du den break-even-Punkt der Threadanzahl? Ist verschieden, als Faustregel gilt für CPU-bound-Prozesse die Prozessoranzahl (evtl. plus geringe Sicherheit), für I/O-bound-Prozesse etwa das doppelte; einen "immer-optimal"-Fall gibt es nicht. Also lege ich Limits im Voraus fest, ehe ich mir mit einer massiven Threaderstellung einer Anwendung einen DoS ins Haus hole.

Wenn ein Programm der Meinung ist, dass es 10 Millionen Threads für mein 10-Megapixel-Bild braucht, dann möchte ich das vorher explizit erlauben. Eleganter ist es, wenn das Programm dieses Limit vorher erfragen kann ("Dieses Programm kann mit mehr Threads mehr Leistung erzeugen.")

Wenn wir schon so die Haare spalten (zumal es um den malloc() Algo und nicht um den VMM Algo ging) dann kannst du auf einem modernen Mikroprozessor mit Cache und Out-Of-Order Ausführung nie O(1) garantieren, da nämlich der Eintrag nicht im Cache stehen kann und in die nächst höhere Cachestufe gewechselt wird und dann irgendwann in den RAM.

Du meinst hier harte Echtzeitanforderung, die geht mit modernen Prozessoren und Betriebssystemen wirklich nicht. Wenn du das Problem wirklich auf den malloc()-Algorithmus beschränkst und die darunterliegenden Ebenen vernachlässigst, hast du recht.

In meiner Welt, und offensichtlich auch in eriks, sind malloc() und VMM aber sehr eng miteinander verzahnt, sodaß eine getrennte Betrachtung nur wenig bringt. Für mich sollte ein naher malloc-Verwandter bereits eine Funktion des VMM sein, die man in der libc nur noch weitergeben muss. Damit können Kernelthreads (mal abgesehen vom VMM) es auch benutzen, ohne auf eine libc-Implementation, welche eventuell Kernelthreads erfordert, angewiesen zu sein. Sonst hast du nämlich wieder eine zyklische Abhängigkeit...

Auch kannst du ja nicht wissen ob eine Page nicht ausgelagert ist und dann müsste die auch erst nachgeladen werden (ist wie den VMM aufrufen) usw.

Richtig. Das kann ich allerdings im Voraus ändern, indem ich die Pages vorher benutze und davon ausgehe, dass genug RAM da ist.

Gruß,
Svenska