Nachrichten

81

OS-Design / Re:Optimale Baumstrukturen fuer malloc/free

« am: 03. September 2011, 14:15 »

dann nimm doch einfach die Adresse als zusätzliches Sortierkriterium. Wenn Du einen Speicherbereich mit einer bestimmten Größe suchst ist Dir doch sicher egal welcher es genau ist (solange die Größe passt) so das es keine Rolle spielt welchen Du als erstes im Baum findest und diesen einfach nimmst.

Wie sollte denn dann das Kriterium dafür aussehen? Dann müsste ich mir ja eine Funktion überlegen, die mir aus den Werten eindeutige Schlüssel generiert, oder?
Mir fällt da auf die Schnelle kein Algorithmus ein.

Ich vermute mal der Baum mit der Größe als Kriterium dient Dir fürs Allozieren von Speicher und der könnte sicher etwas kleiner und damit schneller sein wenn dort nur die freien Blöcke drin sind.

Richtig, so woll es auch aussehen. Ich möchte den Baum so klein wie möglich halten.

82

OS-Design / Re:Optimale Baumstrukturen fuer malloc/free

« am: 03. September 2011, 13:18 »

Also mit identischen Knoten meinte ich Knoten, die die gleiche Speichergröße verwalten.
Bei mir liegt vor jedem Speicherblock ein Header, der den Speicherbereich beschreibt. Der Baum wird anhand der Größen und der Adresse sortiert (zwei Bäume).
Für die SPeichergröße kann es somit "identische Knoten" geben.
Bei einem selbst balancierendem Baum kann es sein, dass ein identischer Knoten auf der Rechten Baumhälfte liegt. Dadurch kann ich den ganzen Weg nicht vereinfacht abarbeiten.
Kann mir zumindest künstlich solch einen Baum aufbauen.
Das ist derzeit mein Problem.

83

OS-Design / Optimale Baumstrukturen fuer malloc/free

« am: 02. September 2011, 23:11 »

Nabend zusammen,

ich arbeite gerade an einem neuen kmalloc, da ich bei meinem derzeitigen Kernel festgestellt habe, dass der Kernel dabei sehr viel zeit vertreiben muss.

Nun wollte ich einen balancierenden Baum verwenden allerdings habe ich dabei das Problem, dass ich bei identischen Knoten nicht fuer einen sortierten Baum garantieren kann, wodurch mir ja die ganzen Vorteile verloren gehen.
Dann hatte ich die Idee, dass die freien Speicherbereiche mit identischer Groesse in einem einzigen Knoten abgelegt werden.

Wie habt ihr das Problem geloest?
Ausserdem ueberlege ich mir die ganze Zeit, welche Baeume am besten fuer die Speicherverwaltung am besten sind.
Habe leider nichts aufschlussreiches gefunden (AVL oder RB).
Habt ihr damit Erfahrungen?

Gruesse,
rizor

84

Lowlevel-Coding / Re:Makefile dynamisch mit Leben füllen

« am: 23. August 2011, 19:23 »

selbst dann ist src leer.
Wenn ich das script normal aufrufe, dann funktioniert es...

85

Lowlevel-Coding / Makefile dynamisch mit Leben füllen

« am: 23. August 2011, 18:27 »

Hi zusammen,

mir gefällt mein derzeitiges Build-System nicht mehr, da der Wartungsaufwand einfach zu groß ist.
Habe jetzt alles auf eine Makefile runtergebrochen und das soll erst beim Aufruf die nötigen Informationen bekommen.

Habe mir dafür ein Skript geschrieben, das mir die Source-Files, etc. ermittelt und dann per echo weitergibt.
Die Skripte laufen auch fehlerfrei.
Leider ignoriert mein Makefile die Ausgaben.

Der Aufruf sieht wie folgt aus:

Code: [Auswählen]

SRC=`sh script.sh -source`
Der Aufruf ermittelt die passenden Source-Files, aber die ignoriert das Makefile.
Woran liegt das?

Grüße,
rizor

86

OS-Design / Re:neues OS-Konzept

« am: 22. August 2011, 22:17 »

Herzlich willkommen,

Ich habe bei deinem Konzept mal eine Frage: Was ist ein intelligentes OS?
Was hast du denn mit Smartweb und deinem OS vor?

Es duerfte vermutlich schwer sein hier jemanden zu finden, der das Ganze mit dir aufbaut, da jeder sein eigenes Projekt hat oder am Community-OS bastelt.
Vllt waere es besser, wenn du dich einem der Projekte anschliesst.

Wir unterstuetzen dich natuerlich tatkraeftig bei deiner Entwicklung, wenn du Probleme haben solltest.

Gruss,
rizor

87

OS-Design / Re:Locking innerhalb des Kernels

« am: 12. August 2011, 14:16 »

Ich habe eben ein Paper über Hazard Pointer gelesen und die sollen sehr viel performanter sein als Spinlocks sein.  Das kann ich mir nur schwer vorstellen, da man je immer doppelt nachschauen muss, oder?  Ein Vorteil ist halt der Garbage Collector, der sich um gelöscht Objekte kümmert. Aber kann es sein, dass man die Verwaltung der Pointer trotzdem durch Locking sichern muss? Mir fällt zumindest keine andere Möglichkeit ein.  Sicher sind die auf jeden Fall. da du ja immer weißt, wer gerade Zugriff auf ein Objekt hat.

88

OS-Design / Re:Locking innerhalb des Kernels

« am: 12. August 2011, 12:42 »

Ich meine folgendes, Thread A holt sich den Pointer und setzt atomar den Counter auf ALT+1 (das ist jetzt kein Reference-Counter) und wenn das erfolgreich war, weiß er das der Counter in Ordnung ist. Das Problem daran ist jetzt, dass das Auslesen und das spätere CMPXCHG nicht zusammenhängend atomar sein können.
Denn Thread B hat sich den Pointer auch geholt und er hat das Objekt freigegeben und irgendwie kommt ein neues Objekt an die gleiche Adresse wie das alte Objekt (was bei nem SlabAllocator mehr als wahrscheinlich ist) und der Counter hat jetzt leider den Wert den Thread A erwartet und was passiert nun? Thread A kommt an die Reihe und macht nen CMPXCHG und da der Counter dummerweise den erwarteten Wert hat, denkt Thread A es bekommt das alte Objekt, dabei ist es ein neues Objekt.

Das war das ABA-Problem, glaube ich.

Dann habe ich dich richtig verstanden. Das funktioniert dann nur mit einem Lock. Den Algorithmus kannst du halt nicht lockless schreiben.
Man koennte es unter Umstaenden lockless machen, indem man eines der Cache-Protokolle emuliert. Dadurch wuerde aber der Overhead steigen. Da ist ein einfacher Lock vermutlich performanter.

89

OS-Design / Re:Locking innerhalb des Kernels

« am: 12. August 2011, 11:54 »

Ich glaube das war so, das jeder Pointer, durch nen "Counter" (weil der immer nur um eins erhöht wird) "geschützt" wird und das Problem war, das wenn die Zeit zw. 2 Zugriffen eines Threads zu lange ist, dass dann das Objekt freigegeben werden kann und durch nen anderen Thread wieder alloziert wird und dann der Counter zufällig den selben Wert hat wie der Thread der nun nach längerer Zeit wieder darauf zugreift, aber das Objekt ist jetzt nicht mehr das gleiche.

Ich bin mir nicht sicher, ob ich dein Szenario richtig verstehe, aber das Problem kannst du doch umgehen, dass du gewaehrleisten kannst, dass die Ueberpruefung der Werte und das Setzen atomar stattfindet. Da muesste man dann unter Umstaenden einen Lock aufbauen, der den Counter schuetzt.

90

OS-Design / Re:Locking innerhalb des Kernels

« am: 09. August 2011, 19:28 »

Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Irgendwo brauchst du halt eine oberste Ebene, die nicht weggeht. Im Zweifelsfall eine statische Variable als Lock.

Die Idee finde ich aber auch nicht so gut, da ich dadurch eine Serialisierung drin habe, die an sich unnötig ist.

Wieso kriegst du da eine unnötige Serialisierung? Und wie oft kommt es überhaupt vor, dass du die Wurzel löschst?

Wenn ich immer über eine Wurzel einsteigen müsste, damit ich meine Strukturen finde, hätte ich eine unnötige Serialisierung.
Das möchte ich vermeiden (außer beim VFS). Wobei ich mir da auch noch nicht wirklich sicher bin. Unter Umständen ist da viel mit Caching machbar um sogar das weitestgehend zu vermeiden.

Die Idee mit dem atomran Flag finde ich gut. Das ist wahrscheinlich das beste.
Mein Problem war/ist, das ich unter Umständen mehrere CPUs habe, die auf eine Struktur zugreifen wollen. Wenn nun einer die Struktur wegräumt (bei Threads/Prozessen wahrscheinlich sogar besser erklärt), möchte der Rest trotzdem noch ran.
Ein Szenario: Ich habe mehrere Threads eines Prozesses, die alle echt parallel auf mehreren CPUs laufen.
Nun macht ein Thread was illegales oder beendet den Prozess, Der Kernel räumt die Strukturen weg und beendet natürlich die Threads auf den anderen CPUs. Was passiert nun, wenn einer der Threads sich durch einen Syscall oder so im Kernel befindet, der gerade die IRQs deaktiviert hat und auch auf die Prozessstruktur zugreifen möchte? Momentan wartet der einfach auf den Lock, egal ob er jemals dran kommt oder nicht. Das war mein Problem. Das sollte durch die atomaren Flags vermeidbar sein oder durch den Reference-Counter.

91

OS-Design / Re:Locking innerhalb des Kernels

« am: 08. August 2011, 20:52 »

Die Idee mit dem Counter finde ich echt nicht schlecht.
Werde mal schauen, wie ich das implementieren kann.
Der SLAB-Allocator war jetzt nur ein Beispiel (unter Umständen nicht das beste).
Aber es gibt ja auch dynamische Strukturen, wie z.B. Prozess-/Thread-Strukturen,die koordiniert abgearbeitet werden müssen. Ich versuche ein halbwegs generisches Konzept zu finden, damit ich das dann nicht immer wieder neu machen muss.

92

OS-Design / Re:Locking innerhalb des Kernels

« am: 08. August 2011, 17:30 »

Das hat nichts mit den Bäumen zu tun. Das Thema wurde parallel aufgeworfen.
Bei einem Baum ist mir die Wurzel klar. Sowas habe ich bei SLABs natürlich nicht.
Da habe ich keine Verwaltung von Caches.
Ein Cache wird angefordert und einfach an den jeweiligen Thread oder das Subsystem weitergegeben. Beim Allozieren eines Objekts wird der Cache mit übergeben. Dadurch habe ich einen kontrollierten Einstieg und es gibt keine Serialisierung bei unterschiedlichen Anfragen. Das ist halt mein Hauptproblem. So habe ich recht viele Datenstrukturen implementiert, damit der Parallelisierungsgrad so hoch wie möglich ist.

93

OS-Design / Re:OS für's Mobile

« am: 08. August 2011, 17:27 »

Also für Handys hab ich noch kein OS geschrieben.
Aber für embedded schon. Also je nachdem wie tief deine Fragen gehen, versuche ich dir gerne zu helfen.
Als Einstieg für Os-Dev für Handieswürde ich dir erst einmal das Embedded-OsDev empfehlen.

94

OS-Design / Re:Locking innerhalb des Kernels

« am: 07. August 2011, 19:29 »

Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Irgendwo brauchst du halt eine oberste Ebene, die nicht weggeht. Im Zweifelsfall eine statische Variable als Lock.

Die Idee finde ich aber auch nicht so gut, da ich dadurch eine Serialisierung drin habe, die an sich unnötig ist.
Vermutlich ist die performanteste Idee wirklich eine Semaphore, die Informationen nach außen trägt.

95

OS-Design / Re:Locking innerhalb des Kernels

« am: 07. August 2011, 14:14 »

Stimmt, das funktioniert einwandfrei bei den unteren Elementen eines Baums.
Was ist nun, wenn du den gesamten Baum löschen möchtest?
Dann löschst du die Wurzel, die gleichzitig der Einstiegspunkt für alle Threads/CPUs ist. Wie verhinderst du da den Deadlock?

Es ist klar, dass die CPU der Lock-Besitzer unterbrochen werden kann.
Aber das mache ich ja erst, sobald ich den Lock möchte.

96

OS-Design / Re:Locking innerhalb des Kernels

« am: 07. August 2011, 12:34 »

So ähnlich mache ich es auch mit dem Locking, außer, dass ich die Liste wieder freig eben, wenn ich gerade eine Page analysiere. Dadurch versuche ich halt den Paralleliserungsgrad des Slabs zu erhöhen.
Das ist ja alles kein Thema.
Was passiert, wenn du den Cache jetzt löschst, aber eine andere PU in dem moment auf den Cache zugreifen möchte?

97

OS-Design / Re:Locking innerhalb des Kernels

« am: 07. August 2011, 11:39 »

Aber wie willst du garantieren, dass keine andere CPU auf einen der Locks wartet?
Das funktioniert in meinen Augen nicht mit Locks alleine, aber leider habe ich keine speicherschonende, performante Idee.

98

OS-Design / Re:Locking innerhalb des Kernels

« am: 07. August 2011, 10:40 »

Geht in die Richtung.
Ein Beispiel: Ich habe einen SLAB-Allocator und da soll nun entweder aufgeräumt werden, also freier Speicher freigegeben werden, oder der Cache selber soll zerstört werden.
Für den Cache selber brauche ich alle Locks, das ist klar. Somit gibt es dann nur auf der Struktur des Caches selber das Problem, dass es CPUs geben kann, die den Lock haben wollen. Nun zerstöre ich den Cache und die anderen CPUs stehen im Deadlock.

Ich möchte nicht immer die ganzen Strukturen locken, das ist mir nicht performant genug.

Das Locking an sich ist ja kein Thema, aber wie signalisiere ich den anderen CPUs, dass genau dieser Knoten gelöscht wird und die wartenden CPUs nicht unkontrolliert arbeiten?

Die Hazard-Pointer werde ich mir mal anschauen.
Ich hatte die Idee mit Semaphoren zu arbeiten und imer einen Status mitzugeben, der dem Thrread signalisiert ob er den Lock hat oder warum er geweckt wurde, obwohl er keine Exclusiv-Rechte hat.
Ist aber immer ein großer Speicheroverhead

99

OS-Design / Locking innerhalb des Kernels

« am: 07. August 2011, 00:03 »

Nabend zusammen,

ich bin gerade dabei eine optimale Locking-Strategie fuer meinen Kernel zu entwickeln, da er ein preemptive Kernel werden soll. Das Locking der einzelnen Elemente und Subsysteme des Kernels ist kein Problem... solange die Strukturen existieren.
Nun habe ich aber Strukturen, die auch immer wieder zerstoert werden. Falls ich nun eine CPU habe, die auf einen Lock wartet, der in dem Moment zerstoert wird. Daraus resultieren zwei Probleme... Entweder die wartende CPU bekommt irgendwann den vermuteten Lock, weil der Speicher durch eine andere CPU fuer was anderes verwendet wird... dann kommt es ja zu einem unkontrollierten verhalten, oder die wartende CPU bleibt in einem Deadlock.

Ich bin momentan dabei, dass ich mir ein Konzept ueberlege, dass auch in solchen Situationen kontrolliert arbeitet. Ich hatte die Idee mit einem Flag, das angibt ob die Struktur noch passt oder eben auch nicht. EIne andere Moeglichkeit waere eine Semaphore, die bei der Zerstoerung einer Struktur aufgeloest wird und die blockierten CPUs frei gibt und ihnen den Grund fuer den Rueckruf mitteilt. Ist unter Umstaenden auch nicht die beste Idee.
Wie habt ihr das denn geloest?

Gruss,
rizor

100

Lowlevel-Coding / Re:MiniOS protecdet Mode

« am: 31. July 2011, 22:47 »

Hallo,

du könntest GitHub, Sourceforge oder einfache Filehoster verwenden, damit du deinen Kernel ins Netz bekommst.
Bei GitHub und Sourceforge bekommst du dann gleichzeitig eine Versionierung geschenkt.

Die Seiten beschreiben auch echt gut wie das funktioniert.

Gruß,
rizor