Wear Leveling Algorithmen in Flashes


PandoraSuechtig

Still Fresh
Joined
Oct 7, 2008
Messages
456
Da uns Thrake den "Weihnachtsupdate vonCraigx" Thread zugemacht hat, da das Thema dort wirklich OT war, werden wir (ich, wejp, grond) uns brav im eigenen Thread zum Thema (Wie schon von Mae vorgeschlagen) weiter unterhalten :)

Für die meisten Pandora-Fans dürfte das Thema belanglos sein. Aber vielleicht hat der eine oder andere sogar Erfahrung damit und kann uns die Diskussion mit einigen Einsichten vereinfachen.

Die Diskussion fing damit an :
http://forum.gp2x.de/viewtopic.php?f=23&t=6424&start=73
Ab da sind wir in die Tiefen von Wear Leveling Algorithmen (WLA) in flashes abgetaucht...

Wir konnten vor allem eine Frage nicht klären: Sind die WLA in Flashes Filesystem sensitiv?? also funktionieren sie z.B. nur FAT effektiv?? Da jeder Hersteller seinen WLA als Betriebsgeheimnis hütet und jeder wohl seinen eigenen hat, wäre hier ein Insider sehr hilfreich? Wer hilft uns Inkognito weiter? :)

EDIT BY Thrake:
grond said:
PandoraSuechtig said:
grond said:
Um eine physikalische Adresse auf einen anderen Block zu mappen, muss es eine Tabelle geben, die Adresspaare beinhaltet, die einander zugeordnet sind.
Falsch. Eine einfache sequentielle Liste der physischen Adressen (die (logische Adresse/Blockgrösse[=2^n]) entspricht dem Index in dieser Tabelle) wär die banalste Lösung.
Das ist identisch mit dem, was ich meinte: die physikalische Adresse ist Funktion der logischen Adresse, die Abbildung ist eineindeutig und bijektiv, d.h., Adresspaare werden gebildet.
Nein, das eine ist eine Tabelle von Adresspaaren, das andere eine Liste von einzelnen Adressen (die Zuordnung erfolgt durch die Position in der Liste). Das erste lässt viel Interpretationsspielraum und erwähnt Adress"paare". Eine Lookuptable mit Adressen hätte ich noch als equivalent verstanden.
grond said:
PandoraSuechtig said:
grond said:
grond hat geschrieben:
Die tatsächliche Adresse eines Blocks setzt sich dann so zusammen: %xxxxxxxxxxyyyyyyyy. "x" bedeutet dabei ein Bit, das aus der Zuordnungstabelle gelesen wird, y ein Bit aus der unveränderten Eingangsadresse.
Blödsinn. Die Adresse des Blocks besteht aus den x, die y addressieren ein bestimmtes Byte im Block.
Das meinte ich. s/Block/Byte.
Dann wars nur ein Schreibfehler.
grond said:
PandoraSuechtig said:
grond said:
Dazu reicht es, den Adresseintrag für den gerade freigewordenen Block so zu verändern, dass er ganz ans Ende der Blockliste rutscht. Damit wird der Zeitabstand bis zu einem erneuten Beschreiben automatisch maximiert.
Zögert nur die Fragmentierung hinaus bis einmal 2^(n+m) Bytes (Fassungsvermögen des Mediums) auf das Medium geschrieben wurden. Also eine ziemlich mickrige Verzögerung...
Meine Ausführungen beruhen auf der Annahme, dass der Controller wissen kann, ob ein Block im FS belegt ist oder nicht. Ich weiß nicht, ob das so ist. Wenn es nicht so ist, müssten grundsätzlich Daten zwischen Quelle und Ziel ausgetauscht werden, wodurch die Anzahl der Schreibzugriffe erst einmal in der Gesamtbilanz verdoppelt würde. Dann bliebe höchstens, besonders aktive Blocks festzustellen und nach einer bestimmten Anzahl Schreibzugriffe mit einem anderen Block zu tauschen. Dazu würde wohl eine Art "history" am einfachsten sein.
History hat denselben Haken wie deine Idee der "FreeList": Irgendwo auf dem Flash muss sie gespeichert werden, und wenn sie bei jedem Schreibzugriff angepasst werden muss (angeblich der Fall durch doppelte Schreibzugriffe), hat sie nach 10000 Schreibzugriffen auf das Medium selber schon 10000 Schreibzugriffe erfahren und wird als erstes ausfallen... Dafür hatte ich schon vorher die Idee aufgeführt, dass man WriteCounts pro Flashblock führt (Jeweils als Teil des Blocks) und nur nach je z.B. 1024 Schreibzugriffen auf dieselbe Zelle ein Austausch (und somit eine Anpassung des Blockmappings) erfolgt (worst case: nach 10 Mio Schreibzugriffen [je 1024 gebündelt auf denselben Block] auf das Medium hätte das Mapping 10000 Zugriffe erfahren).
Unabhängig davon ob wir von einem Controller reden, der die freien Blöcke im FS beachtet oder seine eigenen freien Blöcke managed, in beiden Fällen wird nach einmal 2^(n+m) Bytes Schreiben die Fragmentierung anfangen. Denn die Liste der freien Blöcke wird jeweils um den letzten freigegebenen Block ergänzt und die Freigaben können zufällig erfolgen, also wird die Liste ab dem ersten Eintrag nach 2^(n+m) Bytes Schreibzugriffen ungeordnet sein. Es geht mir nicht darum, dass wenn das Medium fast voll ist, die Knappheit der freien Blöcke das Problem wäre (Falls wir von freien Blöcken im FS reden), sondern, dass die Liste der freien Blöcke nur ganz am Anfang garantiert nach der physikalischen Adresse der Blöcke sortiert ist.
grond said:
PandoraSuechtig said:
grond said:
Basiszeiger reichen, dessen Wert man von allen Adressen abzieht und der bei jeder Operation erhöht wird, so dass er immer auf den ersten freien Eintrag zeigt), man würde sich aber das Dekrementieren aller Einträge in der Zuordnungstabelle sparen, wenn ein Block auf den letzten Platz der freien Blöcke rutscht.
Nun wirds mir unverständlich, genau genommen ergibt es für mich keinen Sinn. Basiszeiger von allen Adressen abziehen, zugleich soll eine Veränderung dieses Basiszeiger aber keine Anpassung aller Einträge zur Folge haben???
Anfangszustand: {1, 2, 3}, Basiszeiger = 0
erste Verschiebung (erster physikalischer Block wird freigegeben): {4, 2, 3}, Basiszeiger = 1 (der erste physikalische Block rutscht logisch aufgrund der Erhöhung um Anzahl(Blöcke) = 3 nach hinten)
zweite Verschiebung (zweiter physikalischer Block wird freigegeben): {4, 5, 3}, Basiszeiger = 2

Will ich nun in den logischen Block 1 schreiben, muss ich alle Einträge minus den Basiszeiger rechnen und die Resultate mit der gewünschten logischen Adresse vergleichen. Da wir hier über Hardware reden, wäre das nahezu beliebig parallelisierbar. Allerdings für eine Blockgröße von 512 Bytes nicht praktisch realisierbar. Da müsste man schon mit größeren Blöcken arbeiten.
Hmmm. Ich sehe eine rollende Liste und einen Offsetzeiger, ist das alles um was es geht? Anstatt die Liste ständig zu shiften mit einem Offsetzeiger zu arbeiten? Wenn dies nur die Liste der freien Blöcke sein soll, funktioniert das nicht, denn sie kann sich in der Länge ändern. Wenn es die Liste aller Blöcke ist, dann ginge es darum bei jedem Schreibvorgang den nächsten "zum Ersetzen zu verwendenden" Block sofort ermitteln zu können? Dies würde ein Ersetzen bei jedem Schreibzugriff erfordern? Dann wird das Flash jedesmal mit 2 Schreibzugriffen belastet und diese Liste + Basiszeiger (Offset) muss mit jedem Schreibzugriff upgedatet werden? Wie oben schon beschrieben wären nach 10'000 Schreibzugriffen auf das Medium zumindest der Block der den Offset speichert schon am Belastungslimit. Die Idee mit der rollenden Liste (soweit ich das richtig verstehe) hätte natürlich den Vorzug der optimalen gleichmässigen Abnutzung aller Blöcke in der Liste, aber in der Praxis klappt das nicht weil der Block, der den Offset enthält jedes mal upgedatet werden würde. Dazu kommt der doppelte Schreibzugriff.

Tut mir leid Gond, ich will echt nicht böse sein, aber ich zweifle an deinem Vorschlag.

Soviel ich schon im Vorfeld sinniert habe über mögliche WL Algorithmen, die das Flash möglichst wenig abnutzen, habe ich immer eine Sache vermieden, da ich keine gute Antwort drauf weiss: Wie wird ein "möglichst wenig" benutzter Block ermittelt? Da das Führen einer Datenstruktur für ein schnelles oder optimales (der am wenigsten Benutzte Block) Auffinden immer in einem oder mehreren Blocks landen würde, die dann besonders belastet werden, denke ich, dass hier "suboptimal" ad hoc, wenn einer benötigt wird, sequentiell nach einem "ausreichend gutem" Kandidaten gesucht wird. Falls die Ersetzung eines Blocks wie weiter oben vorgeschlagen nur etwa jeden 1024. Schreibzugriff auf denselben ausgetauscht würde, könnte in einem Bereich z.B. ein Offset (und Statistiken??) gespeichert werden welches der letzte gefundene Block war und bei der nächsten sequentiellen Suche wird ab dem folgenden fortgefahren.
Mit der suboptimalen Lösung wären trotzdem sehr viele Schreibzugriffe möglich, bevor ein Abnutzungsproblem auftaucht. Nehmen wir an, wegen der Verteilung der Schreibzugriffe würde jeder 20. auf denselben Block fallen (das wär schon eine sehr schlechte Verteilung), dann wäre nach ca. 20000 Schreibzugriffen auf das Medium ein Ersetzen nötig. Nur dann würde eine kleine Performancebusse wegen der Suche nach einem freien Block und dem Ersetzen anfallen und die Blöcke mit den Statistiken würden 20000x10000 = 200Mio Schreibzugriffe auf das Medium aushalten.

Jetzt fallen mir noch einige Optimierungen ein:
  • Einige wenige Byte (Adressen) kann der Controller sicher in einem kleinen (flüchtigen) Puffer (Register?) halten: Wenn er bei jedem Lesevorgang den WriteCount des Blocks beachtet, kann er sich so bei jedem Lesen eine winzige Liste mit den am wenigsten beschriebenen Blöcken merken (je Eintrag: WC+Adresse). Dies ist generell, welchen WL-Algorithmus wir auch immer annehmen, von Nutzen.
  • Wenn beim Schreiben ein Block ersetzt werden soll, kann der auch in einen "TODO" Buffer. Sobald der IO pausiert, kann der Controller sich dann daran machen den/die TODOs im Buffer abzuarbeiten, also die Blöcke zu ersetzen. Wenn beim Schreiben mehr Blöcke anfallen, als dieser Puffer Platz hat, könnte ausnahmsweise (und nur dann) gleich während dem Schreiben die Ersetzung vollzogen werden oder der "am wenigsten brennende Fall" aus dem Puffer fallen? Das sollte den Geschwindigkeitseinbruch beim Schreiben minimieren.
  • Genauso kann auch die sequentielle Suche nach guten Kandidaten für Ersatzblöcke in der IO losen Zeit erfolgen.
Natürlich ist eine Liste der "least written" Blöcke, die anhander der Reads aufgebaut wird suboptimal und gelegentlich muss sequentiell gesucht werden. Sonst würde der Controller auf einem fast leeren Medium, auf dem nur ständig kleine Datenmengen geschrieben und wieder gelöscht werden, die noch nie benutzten Blöcke ja nie lesen und zum Ersetzen nutzen. Auch wenn er noch nichts nicht gelesen hat, aber gleich ein Ersetzen anfällt, muss eine Suche her.
 

PandoraSuechtig

Still Fresh
Joined
Oct 7, 2008
Messages
456
Meine Argumentationen basieren immer auf der Annahme, dass alle "persistenten" Daten auf dem Flash liegen, aber vielleicht gibts in den ganzen Sticks auch etwas "besseren" Speicher, der mehr Schreibzyklen aushält und die Optimierungen durch persistentes Halten von Histories, Freelists, LRU Listen, LOU Lists (least often used) ermöglicht?
Tja ein Insider wär hier Gold wert...
 

Joker

Still Fresh
Joined
Mar 10, 2003
Messages
2,423
PandoraSuechtig said:
Da uns Thrake den "Weihnachtsupdate vonCraigx" Thread zugemacht hat, da das Thema dort wirklich OT war, werden wir (ich, wejp, grond) uns brav im eigenen Thread zum Thema (Wie schon von Mae vorgeschlagen) weiter unterhalten :)

und dann auch bitte in den richtigen Bereich!

moved to Off-Tropic
 
A

Anonymous

Guest
PandoraSuechtig said:
Da jeder Hersteller seinen WLA als Betriebsgeheimnis hütet und jeder wohl seinen eigenen hat, wäre hier ein Insider sehr hilfreich?

Nö, die hüten das nicht als Geheimnis, wäre auch dumm, wenn sie das täten, denn dann könnte man das ja nach einer (nicht übermäßig komplizierten) Chipanalyse kopieren. Zufälligerweise bin ich außer Mikrochipentwickler auch Patentanwalt. Wenn man bei depatisnet.dpma.de bei der Einsteigerrecherche "wear-leveling" eingibt, bekommt man eine ganze Reihe von Patentschriften, die sich mit dem Thema befassen. Lesen werde ich die jetzt allerdings nicht... :)

Das ist identisch mit dem, was ich meinte: die physikalische Adresse ist Funktion der logischen Adresse, die Abbildung ist eineindeutig und bijektiv, d.h., Adresspaare werden gebildet.
Nein, das eine ist eine Tabelle von Adresspaaren, das andere eine Liste von einzelnen Adressen (die Zuordnung erfolgt durch die Position in der Liste). Das erste lässt viel Interpretationsspielraum und erwähnt Adress"paare". Eine Lookuptable mit Adressen hätte ich noch als equivalent verstanden.

Der Silicon-Compiler sieht das alles als äquivalent an, will sagen, es kommt dieselbe Schaltung dabei heraus.

PandoraSuechtig said:
History hat denselben Haken wie deine Idee der "FreeList": Irgendwo auf dem Flash muss sie gespeichert werden

Müssen muss sie nur, wenn der Algo auch gut[/] sein soll. Wenn es z.B. hauptsächlich darum geht, die Blöcke mit der FAT zu schützen, weil dort die absolut meisten Schreibzugriffe geschehen, würde der Controller auch nach einem Löschen der History bei der nächsten Inbetriebnahme schnell wieder "wissen", wo die FAT ist. Der Use-Count für die der FAT zugeordneten Blöcke wäre schnell wieder auf den Spitzenplätzen. Hier hätten wir dann einen Fall einer FAT-spezifischen Optimierung, ohne dass das Flash sich des Filesystems bewusst sein müsste...


und wenn sie bei jedem Schreibzugriff angepasst werden muss (angeblich der Fall durch doppelte Schreibzugriffe), hat sie nach 10000 Schreibzugriffen auf das Medium selber schon 10000 Schreibzugriffe erfahren und wird als erstes ausfallen...

Ja, das ist richtig. Ich habe mich auch schon gefragt, ob es "haltbarere" Flashblöcke gibt, die wegen einer größeren Oxiddicke nicht so leicht durchbrechen, aber nicht im gesamten Flash benutzt werden können, weil die Packungsdichte sinken und die Leistungsaufnahme steigen würde (größere Tunnelspannung). Denke ich aber eigentlich nicht, weil das die Kosten für den Prozess hochtreiben würde.


Dafür hatte ich schon vorher die Idee aufgeführt, dass man WriteCounts pro Flashblock führt (Jeweils als Teil des Blocks) und nur nach je z.B. 1024 Schreibzugriffen auf dieselbe Zelle ein Austausch (und somit eine Anpassung des Blockmappings) erfolgt

Ja, das Modulo wäre bei einer Zweierpotenz "gratis" und der Nachteil des immer doppelten Schreibens beim Blocktausch fiele weg. Im übrigen könnte jeder Block neben dem Write-Count auch gleich seine logische Adresse speichern. Sollte beim Adressieren kein unendliches Problem sein: Adresse wird angelegt, jeder Block prüft, ob die Adresse zufällig seine ist (braucht ein paar Gatter) und schreibt den Inhalt aus.


Unabhängig davon ob wir von einem Controller reden, der die freien Blöcke im FS beachtet oder seine eigenen freien Blöcke managed

Ich denke, dass es immer unwahrscheinlicher ist, dass der Controller das FS interpretiert. Was, wenn die FAT (mal wieder) beschädigt wird? Bringen sich dann FS-Checker und Controller gegenseitig um?


PandoraSuechtig said:
Hmmm. Ich sehe eine rollende Liste und einen Offsetzeiger, ist das alles um was es geht?

Nicht genug? :)


Wenn dies nur die Liste der freien Blöcke sein soll, funktioniert das nicht

Nein, das ist die Liste aller Blöcke, nur wird eine Änderung immer nur dann vorgenommen, wenn ein Block FS-frei wird (ich schlage hiermit offiziell die Begriffe "FS-frei" und "PH-frei" vor).


diese Liste + Basiszeiger (Offset) muss mit jedem Schreibzugriff upgedatet werden? Wie oben schon beschrieben wären nach 10'000 Schreibzugriffen auf das Medium zumindest der Block der den Offset speichert schon am Belastungslimit.

Nur, wenn die Liste in einem Block gespeichert wird. Der Eintrag für jeden Block kann aber in jedem Block gespeichert sein. Der Basiszeiger ist aber ein Problem. Könnte sich aber eventuell auch elegant lösen lassen. Wenn man in jedem Block ein Bit hat, das "verschoben" anzeigt und invertiert wird, wenn ein Verschiebungsvorgang vorgenommen wird, dann könnte man durch logische Verknüpfung jeweils zweier benachbarter Bits den Block finden, der als nächstes zu verschieben ist.


Wie wird ein "möglichst wenig" benutzter Block ermittelt?

Tja. Man kann die Schreibzugriffe "dithern", also ein (Pseudo-)Zufallselement ins Spiel bringen und hoffen, dass das schon gutgehen wird. Oder man rotiert deterministisch, wie ich oben angedeutet habe (mir selbst ist zugegebenermaßen nicht ganz klar, ob das gehen kann). Alles andere wird zu kompliziert, man müsste für eine optimale Lösung alle Write-Counts miteinander vergleichen.


[*] Einige wenige Byte (Adressen) kann der Controller sicher in einem kleinen (flüchtigen) Puffer (Register?) halten: Wenn er bei jedem Lesevorgang den WriteCount des Blocks beachtet, kann er sich so bei jedem Lesen eine winzige Liste mit den am wenigsten beschriebenen Blöcken merken (je Eintrag: WC+Adresse). Dies ist generell, welchen WL-Algorithmus wir auch immer annehmen, von Nutzen.

Denke nicht, dass das von großem Nutzen wäre. Die selten geschriebenen Blöcke werden tendenziell auch seltener gelesen (ich weiß, es gibt viele Beispiele, bei denen das nicht so ist, trotzdem dürfte es da eine Korrelation geben). Außerdem sind die Speichergrößen des Flashs inzwischen sehr groß gegenüber einer vertretbaren Puffergröße im Controller. Wir müssten schließlich mit SRAM oder Flip-Flops arbeiten, wenn wir dem Controller nicht noch gleich ein separates DRAM-Modul spendieren wollen :)


[*] Wenn beim Schreiben ein Block ersetzt werden soll, kann der auch in einen "TODO" Buffer. Sobald der IO pausiert, kann der Controller sich dann daran machen den/die TODOs im Buffer abzuarbeiten, also die Blöcke zu ersetzen. Wenn beim Schreiben mehr Blöcke anfallen, als dieser Puffer Platz hat, könnte ausnahmsweise (und nur dann) gleich während dem Schreiben die Ersetzung vollzogen werden oder der "am wenigsten brennende Fall" aus dem Puffer fallen? Das sollte den Geschwindigkeitseinbruch beim Schreiben minimieren.

Geschwindigkeitseinbruch bei einem Tausch alle 1024 Zugriffe? :)

Speicher gliedern sich intern immer in mehrere Abschnitte. Z.B. enthält ein Abschnitt alle physikalischen Adressen, für die Modulo 8 = 0, der nächste Modulo 8 = 1 usw. Wenn man nun schlauerweise immer mit einem Block aus einem anderen Abschnitt tauscht, müsste sich das wunderbar parallelisieren lassen.


Natürlich ist eine Liste der "least written" Blöcke, die anhander der Reads aufgebaut wird suboptimal und gelegentlich muss sequentiell gesucht werden.

Ja, wenn man wirklich versucht, die am wenigsten beschriebenen Blöcke zu ermitteln, dann müsste man wohl sequentiell suchen. Allerdings gibt es da das Problem, dass sich der Write-Count schneller ändern kann als die Suche ausgeführt werden kann.
 
A

Anonymous

Guest
grond said:
Wenn man bei depatisnet.dpma.de bei der Einsteigerrecherche "wear-leveling" eingibt, bekommt man eine ganze Reihe von Patentschriften, die sich mit dem Thema befassen. Lesen werde ich die jetzt allerdings nicht... :)

Hömm, jetzt habe ich doch aus Neugier die Einleitung einer Offenlegungsschrift gelesen, weil die deutschsprachig war. Wenn man das glauben kann, was da in der Einleitung über Flash und Wear-Leveling steht, gibt es eine große Enttäuschung für unseren Debattierclub: das Wear-Leveling funktioniert so, dass ein Block nach einer bestimmten Anzahl von Schreibzugriffen automatisch als "bad" markiert und nicht mehr verwendet wird. Für diesen Block wird dann eben ein Ersatz benutzt. Dafür reicht ein einfacher Zähler im Block und eine Zuordnungstabelle.
 

PandoraSuechtig

Still Fresh
Joined
Oct 7, 2008
Messages
456
grond said:
Nö, die hüten das nicht als Geheimnis, wäre auch dumm, wenn sie das täten, denn dann könnte man das ja nach einer (nicht übermäßig komplizierten) Chipanalyse kopieren.
Wurde schon in ein oder zwei c't Magazinen erwähnt, dass die Algorithmen von den Herstellern geheim gehalten werden. Ich kann mir gut vorstellen, dass die besseren Algorithmen nicht patentiert werden. Den Algorithmus, den du in einer Patentschrift gefunden hast, ist auch im Grunde kein Wear-Leveling (zumindest verdient es nicht den Namen). Das ist nur das Benutzen von Reserveblöcken. Ist ja auch in Festplatten heute alltäglich. Oder die c't irrt sich schlichtwegs. Oder aber sie reden von geheim aber benutzten hauptsächlich wirklich nur ein simples remappen auf Reserveblöcke sobald ein Block nach dem Schreiben als nicht mehr nutzbar eingestuft wird (nach jedem Schreiben ein Test-Read, dafür wird er aber bis zuletzt benutzt).
Wenn sogar die einfachen Flashes MINDESTENS 10000 Schreibzugriffe auf denselben Block überleben, dann könnte man vielleicht von gemittelt 20000 rechnen, bei sagen wir 8kb Blöcken (kennt jemand die typischen Blockgrössen??), brauchen 1024 Stück gerade mal 8 MB Reservespeicher. Dafür hätten wir aber 1024x20000, also beim worst case scenario 20Mio Schreibzugriffe auf denselben Block. Beste Kandidaten dürfte der Teil der FAT mit der "Tabelle der Free Blocks" liefern... Rechnen wir weiter mit einem 8 GB Stick, also 2^20 Blöcke braucht eine Blockadresse 20 Bit und das Adressieren der Reserveblöcke 10 Bit (plus 2 Bit für andere Infos macht für einen Remapping Eintrag 32bit), die Mapping-Table wäre also 2^10 Einträge x 32 Bit gesamt 4kb gross, passt in einen Block. Dieser sollte aber nur maximal 1024 Updates erfahren, kein Problem. In die ersten 4 kbyte noch einen Index, die Einträge sortieren und wir können problemlos bei jeder Adressnachfrage die Mappingtabelle konsultieren.
grond said:
Der Silicon-Compiler sieht das alles als äquivalent an, will sagen, es kommt dieselbe Schaltung dabei heraus.
Langsam leuchtet mir ein, dass wir ein etwas anderes Vokabular haben. Bin SW-Ing., du ein HW-Ing.
PandoraSuechtig said:
History hat denselben Haken wie deine Idee der "FreeList": Irgendwo auf dem Flash muss sie gespeichert werden
grond said:
Müssen muss sie nur, wenn der Algo auch gut[/] sein soll. ... Der Use-Count für die der FAT zugeordneten Blöcke wäre schnell wieder auf den Spitzenplätzen. Hier hätten wir dann einen Fall einer FAT-spezifischen Optimierung, ohne dass das Flash sich des Filesystems bewusst sein müsste...

"Gut" ist etwas unscharf. Im Sinne von "optimal verteilen" ja, im Sinne von "Flash-Schonend" Nein.
Das wäre keine FAT spezifische Optimierung, fast jedes FS hat stark beschriebenere Zonen, daher wäre es in dem Sinne auch eine "spezifische Optimierung" für jedes dieser FS. Aber da diese Aussagen oft vom Marketing kommen, wäre es gut möglich, dass sie es als "FAT" optimiert "verkaufen". Und was wäre der Use-Count? Wo würde er geführt werden und wie würde er benutzt? Du bringst manchmal solche Worte oder Gedanken ein, führst sie aber leider nicht ganz aus.
grond said:
Ja, das ist richtig. Ich habe mich auch schon gefragt, ob es "haltbarere" Flashblöcke gibt, die wegen einer größeren Oxiddicke nicht so leicht durchbrechen, aber nicht im gesamten Flash benutzt werden können, weil die Packungsdichte sinken und die Leistungsaufnahme steigen würde (größere Tunnelspannung). Denke ich aber eigentlich nicht, weil das die Kosten für den Prozess hochtreiben würde.
Darum wäre ein "optimal verteilender WLA" eher unwahrscheinlich, weil er solche Datenstrukturen halten müsste im Flash. Dein Vorschlag mit der rollenden Liste wäre so ein Kandidat. Andererseits hast du mehrfach die Parallelität in Flashes angesprochen und das leuchtet auch mir langsam ein. Das erlaubt ein ziemlich schnelles und effizientes Suchen nach Blöcken mit tiefen "WriteCounts" zum Ersetzen von Blöcken. Auch ein sehr ineffizienter Austausch dürfte die Grenze der Schreibzugriffe auf das ganze Medium bevor ein Datenverlust eintritt, locker in den mehrstelligen Millionenbereich katapultieren. s.o. das simple Beispiel mit "nur Reserveblöcken".
grond said:
Im übrigen könnte jeder Block neben dem Write-Count auch gleich seine logische Adresse speichern. Sollte beim Adressieren kein unendliches Problem sein: Adresse wird angelegt, jeder Block prüft, ob die Adresse zufällig seine ist (braucht ein paar Gatter) und schreibt den Inhalt aus.
"jeder Block prüft, ob die Adresse zufällig seine ist" ? Hier scheiden sich unsere Vorstellungen völlig. Nach meinem Verständnis müsste der Controller jeden Block auslesen und seine "logische" Adresse prüfen, was völlig ineffizient wäre. Während du von davon redest, dass "jeder Block ... prüft" ? Mir ist bekannt, dass Flash einige Parallelisierungen zulässt und dass gewisse "eq 0, (addresse)" sehr einfach ablaufen können. Aber da bin ich zuwenig tief in der HW um das zu beurteilen.
grond said:
Ich denke, dass es immer unwahrscheinlicher ist, dass der Controller das FS interpretiert. Was, wenn die FAT (mal wieder) beschädigt wird? Bringen sich dann FS-Checker und Controller gegenseitig um?
Sehr guter Einwand gegen die Interpretation des FS. Andererseits sehe ich gerade bei FAT wenig Risiken. Logisch falsche Daten führen schon zu einem Verlustrisiko. Alles was du da noch mit spezialisierten Tools speziell noch "rettest", hat einfach eine erhöhte Chance einen falschen Inhalt zurück zu liefern. FAT ist zu einfach gestrickt um so noch grössere Schäden zu riskieren.
grond said:
PandoraSuechtig said:
Hmmm. Ich sehe eine rollende Liste und einen Offsetzeiger, ist das alles um was es geht?
Nicht genug? :)
War einfach zu kompliziert erklärt.


grond said:
PandoraSuechtig said:
diese Liste + Basiszeiger (Offset) muss mit jedem Schreibzugriff upgedatet werden? Wie oben schon beschrieben wären nach 10'000 Schreibzugriffen auf das Medium zumindest der Block der den Offset speichert schon am Belastungslimit.
Nur, wenn die Liste in einem Block gespeichert wird. Der Eintrag für jeden Block kann aber in jedem Block gespeichert sein.
Redest du von einer Linked List?? Dann kannst du wahrlich nur ein paar Links anpassen um diese "Reihenfolge" anzupassen. Aber da der aktuell beschriebene zuerst aus der Liste ausgetragen werden muss, wäre eine Double-Linked-List besser. Dann wäre mit wenigen Zugriffen das Feld in der Liste gefunden, ausgetragen, neu eingetragen und die Liste angepasst. Das führt aber (falls Blöcke jeweils nur als ganzes geschrieben werden können) zu mindestens 8 Schreibzugriffen pro Schreibzugriff:
austragen: block der auf den zielblock verweist, nachfolgeblock der auf den zielblock zurückverweist (dies dreimal für alten position, neue position und block mit dem ersetzt wurde) und 2x für block und ersatzblock austauschen und wo ist das Mapping phy-log?
grond said:
Der Basiszeiger ist aber ein Problem. Könnte sich aber eventuell auch elegant lösen lassen. Wenn man in jedem Block ein Bit hat, das "verschoben" anzeigt und invertiert wird, wenn ein Verschiebungsvorgang vorgenommen wird, dann könnte man durch logische Verknüpfung jeweils zweier benachbarter Bits den Block finden, der als nächstes zu verschieben ist.
Wir traversieren also wieder alles? bzw. die ganzen "is moved" aller blöcke? Du scheinst hier ständig von einer Parallelität im Flash auszugehen, die ich nicht einschätzen kann.
grond said:
Alles andere wird zu kompliziert, man müsste für eine optimale Lösung alle Write-Counts miteinander vergleichen.
Parallel Seek für einige Schritte, davon den mit dem kleinsten Write-Count. Muss ja nicht optimal sein.
grond said:
Denke nicht, dass das von großem Nutzen wäre. Die selten geschriebenen Blöcke werden tendenziell auch seltener gelesen (ich weiß, es gibt viele Beispiele, bei denen das nicht so ist, trotzdem dürfte es da eine Korrelation geben). Außerdem sind die Speichergrößen des Flashs inzwischen sehr groß gegenüber einer vertretbaren Puffergröße im Controller. Wir müssten schließlich mit SRAM oder Flip-Flops arbeiten, wenn wir dem Controller nicht noch gleich ein separates DRAM-Modul spendieren wollen :)
Dachte hier nur an eine winzige Optimierung, bei jedem Read wird mit einer kleinen Liste der letzten "least written" verglichen. Da reichen je 4 Byte pro Eintrag und von mir aus 16 Einträge, wäre 64 Byte. Ist das so teuer/abwegig? Es soll nur eine "Hilfestellung" für Seeken sein. Hatte im Vorschlag geschrieben, dass damit das Seeken nicht gänzlich wegfallen kann.
grond said:
Geschwindigkeitseinbruch bei einem Tausch alle 1024 Zugriffe? :)
Nunja... Die Wortwahl... :oops:
grond said:
Ja, wenn man wirklich versucht, die am wenigsten beschriebenen Blöcke zu ermitteln, dann müsste man wohl sequentiell suchen. Allerdings gibt es da das Problem, dass sich der Write-Count schneller ändern kann als die Suche ausgeführt werden kann.
??? Inwiefern? Die sequentielle Suche soll nur über einen Bruchteil der Blöcke erfolgen und nur zwischen Schreib-/Lesezugriffen. Dazwischen erfolgen keine Änderungen. Es war keine Vollständige sequentielle Suche parallel zum Betrieb über den ganzen Speicher gemeint.

Wir würden immer entweder an das Problem Performance, Optimale Verteilung der Austäusche bzw. Writes, oder "Herstellungskosten" des Mediums stossen und daher wird die "ausbalancierte" Lösung irgendwo im suboptimal verteilenden Bereich liegen. Auch der Algorithmus dürfte etwas Zufall nutzen und so auch bei einigen "dümmsten Fällen" schneller ans Limit stossen.
So ähnlich funktioniert auch die Chipherstellung z.B. bei Intel. Kein Prozi in der Endproduktion wird zu 100% getestet und das Herstellungsverfahren ist nicht so "vorsichtig" mit grossen Reserven eingestellt, dass sicher 100% aller Prozis fehlerfrei produziert werden. Es ist günstiger bei allen knapper mit den Tests, und den Herstellungsfaktoren (z.B. Dicke der Schichten) zu fahren und dabei bei jeder CPU minim Geld zu sparen und mit wenigen Prozent Rückfallquote zu rechnen. Die Kosten für den Umtausch fallen geringer aus, als die gesparten Kosten. So kann auch ein WLA suboptimal funktionieren und etwas zufällig funktionieren, so dass im schlimmsten Fall wirklich mal ein winziger Anteil ausgetauscht werden muss, weil er schon nach kurzer Zeit einen defekten Block meldet.
 
A

Anonymous

Guest
PandoraSuechtig said:
Wurde schon in ein oder zwei c't Magazinen erwähnt, dass die Algorithmen von den Herstellern geheim gehalten werden. Ich kann mir gut vorstellen, dass die besseren Algorithmen nicht patentiert werden.

Möglich ist das, es wäre aber sehr dumm. Chipanalysen kann man für ca. 100.000€ bestellen und bekommt dafür wirklich phantastisches Material geliefert. Woher ich das weiß? Öhm, so vom Hörensagen...

Guck mal wirklich auf depatisnet nach Patentschriften. Du wirst staunen, wieviele gute Treffer es da offenbar gibt.

Den Algorithmus, den du in einer Patentschrift gefunden hast, ist auch im Grunde kein Wear-Leveling (zumindest verdient es nicht den Namen). Das ist nur das Benutzen von Reserveblöcken.

Optimales WL würde die Größe des Datenträgers mit der Zeit kontrolliert bis auf Null "runterfahren". Solange man mit seinen Daten hinkäme (ständiges Schreiben und Löschen kleiner Dateien) würde das nicht wirklich stören. Ab und zu mal ein neues FS anlegen und weitermachen, bis der letzte Block gestorben ist. Ich glaube nicht, dass es irgendein WL gibt, das das in der Realität könnte.

grond said:
Im übrigen könnte jeder Block neben dem Write-Count auch gleich seine logische Adresse speichern. Sollte beim Adressieren kein unendliches Problem sein: Adresse wird angelegt, jeder Block prüft, ob die Adresse zufällig seine ist (braucht ein paar Gatter) und schreibt den Inhalt aus.

"jeder Block prüft, ob die Adresse zufällig seine ist" ? Hier scheiden sich unsere Vorstellungen völlig. Nach meinem Verständnis müsste der Controller jeden Block auslesen und seine "logische" Adresse prüfen, was völlig ineffizient wäre.

Nö, wozu? Das Flash dürfte ja auch ein paar andere Logikelemente wie Transistoren für Leseverstärker und dergleichen erlauben. Da kann man dann auch an jedem Block einen simplen Vergleicher anbauen, der die lokal gespeicherte logische Adresse mit der auf den Adressleitungen angelegten Adresse vergleicht. Das braucht nur ein paar Transistoren.

Andererseits sehe ich gerade bei FAT wenig Risiken.

Naja, wir müssen jetzt ja nicht annehmen, dass irgendein Hersteller auf Dinge wie ext3 Rücksicht nähme, wenn sich aber herumspricht, dass das Flash von einem beliebigen Hersteller unrettbar kaputtgeht, wenn es in NTFS formatiert ist und ein Fehler auftritt, wäre das wohl doch geschäftsschädigend. Will sagen: das Medium muss auch mit komplexeren Dateisystemen robust sein.


Redest du von einer Linked List??

Nö, s.o.: in jedem Block kann ja die logische Adresse gespeichert werden (bzw. ist die logische Adresse dann der im Block gespeicherte Wert Modulo Speichergröße), der Block muss sich ja nur melden, wenn seine momentane Adresse angelegt wird.

Dachte hier nur an eine winzige Optimierung, bei jedem Read wird mit einer kleinen Liste der letzten "least written" verglichen. Da reichen je 4 Byte pro Eintrag und von mir aus 16 Einträge, wäre 64 Byte. Ist das so teuer/abwegig?

Das dürfte kein Problem sein. Aber wie groß wäre der Nutzen?

grond said:
Ja, wenn man wirklich versucht, die am wenigsten beschriebenen Blöcke zu ermitteln, dann müsste man wohl sequentiell suchen. Allerdings gibt es da das Problem, dass sich der Write-Count schneller ändern kann als die Suche ausgeführt werden kann.
??? Inwiefern? Die sequentielle Suche soll nur über einen Bruchteil der Blöcke erfolgen und nur zwischen Schreib-/Lesezugriffen.

Wenn andauernd geschrieben wird, kannst Du (außer mit viel flüchtigem Speicher im Controller zum "Mitschreiben") nicht mehr mithalten.

So ähnlich funktioniert auch die Chipherstellung z.B. bei Intel. Kein Prozi in der Endproduktion wird zu 100% getestet

Prozessoren sind speziell, aber sonst wird bei Chips schon möglichst alles getestet. Das Problem ist: sagen wir, es gibt n mögliche logische Kombinationen, die prinzipiell von der Hardware berechnet werden können. n ist eine nahezu unendlich große Zahl, weil es sehr viele interne logische Zustände gibt. Für einen Test kann man diese logischen Zustände setzen und sich das Ergebnis angucken. Man kann aber niemals alle möglichen Eingangswerte testen, also versucht man "gute" Testvektoren zu finden, deren Ergebnisse möglichst oft Abweichungen zeigen, wenn in der Schaltung etwas kaputt ist. Das entspricht ziemlich genau der Theorie hinter den Hashes: der Hash ist kürzer als die möglichen Eingangswerte, soll aber dennoch sich möglichst für unterschiedliche Eingangswerte immer unterscheiden, was letztlich nicht möglich ist, aber eventuell für typische Veränderungsmuster möglich ist.

und das Herstellungsverfahren ist nicht so "vorsichtig" mit grossen Reserven eingestellt, dass sicher 100% aller Prozis fehlerfrei produziert werden.

Normalerweise macht man sogenannte sechs-sigma-Vorgaben an den Hardwareentwickler. Das "sigma" bezieht sich auf die Standardabweichung. Sechs-sigma bedeutet, dass 3 Chips von einer Million nicht funktionieren dürfen. Das ist für CPUs eine zu harte Vorgabe, weshalb ja noch das "Binning" durchgeführt wird (CPUs werden nach ihren maximalen Taktraten sortiert).
 

PandoraSuechtig

Still Fresh
Joined
Oct 7, 2008
Messages
456
grond said:
Optimales WL würde die Größe des Datenträgers mit der Zeit kontrolliert bis auf Null "runterfahren". Solange man mit seinen Daten hinkäme (ständiges Schreiben und Löschen kleiner Dateien) würde das nicht wirklich stören. Ab und zu mal ein neues FS anlegen und weitermachen, bis der letzte Block gestorben ist. Ich glaube nicht, dass es irgendein WL gibt, das das in der Realität könnte.
Warum die Grösse kontrolliert auf Null...? Verstehe die Aussage nicht.
grond said:
Nö, wozu? Das Flash dürfte ja auch ein paar andere Logikelemente wie Transistoren für Leseverstärker und dergleichen erlauben. Da kann man dann auch an jedem Block einen simplen Vergleicher anbauen, der die lokal gespeicherte logische Adresse mit der auf den Adressleitungen angelegten Adresse vergleicht. Das braucht nur ein paar Transistoren.
Hardwarelogik... Wenn dies so einfach ist, kann das Adressmapping also inhärent ablaufen und braucht auch keine zusätzlichen Writes, da bei jedem Write eines Blockes seine logische Adresse mitgeschrieben wird. Das ermöglicht ganz neue Algorithmen...
grond said:
das Medium muss auch mit komplexeren Dateisystemen robust sein.
Dass die Dinger FS optimiert sind bezweifle ich schon seit dem Anfang. Erwarte eher Algorithmen die für jedes Zugriffsschema ausreichend gut ausfallen.
grond said:
Dachte hier nur an eine winzige Optimierung, bei jedem Read wird mit einer kleinen Liste der letzten "least written" verglichen. Da reichen je 4 Byte pro Eintrag und von mir aus 16 Einträge, wäre 64 Byte. Ist das so teuer/abwegig?
Das dürfte kein Problem sein. Aber wie groß wäre der Nutzen?
Wenn man alle Blöcke zugleich im Zugriff haben kann mit einfachen Operationen, dann wär doch auch ein paralleler Test auf den Wert des WriteCounters möglich um schnell die günstigen Blöcke zu finden? z.B. Alle deren Wordcounter AND "FFF0" == 0 ? (alle mit weniger als 16 Schreibzugriffen) und falls keiner gefunden dasselbe mit "FF00" (alle mit <256). Wär sowas möglich??
grond said:
Wenn andauernd geschrieben wird, kannst Du (außer mit viel flüchtigem Speicher im Controller zum "Mitschreiben") nicht mehr mithalten.
Zwischen den Schreibzugriffen meinte nicht "in Ruhepausen", sondern zwischen 2 Schreibzugriffen. Nun kann man entweder einen nötigen Umtausch protokollieren um ihn später auszuführen um das Schreiben nicht zu lange zu unterbrechen oder falls zu viele zum Austauschen anfallen das Schreiben pausieren oder jedesmal falls nötig sofort austauschen. Aber halt nicht parallel zum Schreiben/Lesen, sondern dazwischen (IO pausiert).
grond said:
Man kann aber niemals alle möglichen Eingangswerte testen, also versucht man "gute" Testvektoren zu finden, deren Ergebnisse möglichst oft Abweichungen zeigen, wenn in der Schaltung etwas kaputt ist. Das entspricht ziemlich genau der Theorie hinter den Hashes: der Hash ist kürzer als die möglichen Eingangswerte, soll aber dennoch sich möglichst für unterschiedliche Eingangswerte immer unterscheiden, was letztlich nicht möglich ist, aber eventuell für typische Veränderungsmuster möglich ist.
In der SW-Welt: Vollständige Pfadabdeckung, Blackbox-/Whiteboxtesten, Extremalwerte testen... Ist auch hier bekannt.
 
A

Anonymous

Guest
PandoraSuechtig said:
grond said:
Optimales WL würde die Größe des Datenträgers mit der Zeit kontrolliert bis auf Null "runterfahren". Solange man mit seinen Daten hinkäme (ständiges Schreiben und Löschen kleiner Dateien) würde das nicht wirklich stören. Ab und zu mal ein neues FS anlegen und weitermachen, bis der letzte Block gestorben ist. Ich glaube nicht, dass es irgendein WL gibt, das das in der Realität könnte.
Warum die Grösse kontrolliert auf Null...? Verstehe die Aussage nicht.

Was ich meine, ist das: es würden zu jedem Zeitpunkt alle heilen Blöcke benutzt, aber naturgemäß immer mal welche kaputtgehen. Die Zahl der heilen Blöcke geht daher mit der Zeit gegen Null, eben weil Flash nicht unendlich viele Schreibzyklen aushält. Funktioniert das WL optimal, dann könnte man einen 1G Flashspeicher jahrhundertelang nutzen mit dem einzigen Nachteil, dass halt irgendwann nur noch ein Block übrig ist. Geht der kaputt, ist der Speicher erst endgültig kaputt. Das wird aber kein realexistierender Speicher ermöglichen. Bei dem in der einen Patentschrift erläuterten WL wäre der Flash ja vermutlich kaputt, wenn alle Ersatzblöcke aufgebraucht sind.

grond said:
Dachte hier nur an eine winzige Optimierung, bei jedem Read wird mit einer kleinen Liste der letzten "least written" verglichen. Da reichen je 4 Byte pro Eintrag und von mir aus 16 Einträge, wäre 64 Byte. Ist das so teuer/abwegig?
Das dürfte kein Problem sein. Aber wie groß wäre der Nutzen?
Wenn man alle Blöcke zugleich im Zugriff haben kann mit einfachen Operationen, dann wär doch auch ein paralleler Test auf den Wert des WriteCounters möglich um schnell die günstigen Blöcke zu finden? z.B. Alle deren Wordcounter AND "FFF0" == 0 ? (alle mit weniger als 16 Schreibzugriffen) und falls keiner gefunden dasselbe mit "FF00" (alle mit <256). Wär sowas möglich??

Ja, das würde mit 16 Gattern pro Block, also ziemlich wenig Aufwand, gehen (wobei Du wohl die Tests "0x000f & WC == 0" und "0x00ff & WC == 0" meinst). Nur steigt die Granularität der Suche, weil Du nur "kleiner-gleich-Vergleiche" mit Zweierpotenzen machen könntest. Willst Du hingegen einen echten Vergleich mit einem wählbaren Wert machen, brauchst Du einen (sehr schnellen) Subtrahierer. Das wäre wiederum zuviel Overhead für einen Block. Eine Minimumsuche wäre parallelisiert komplett unmöglich (also "der Block mit dem kleinsten UC bitte melden!").

grond said:
Wenn andauernd geschrieben wird, kannst Du (außer mit viel flüchtigem Speicher im Controller zum "Mitschreiben") nicht mehr mithalten.
Zwischen den Schreibzugriffen meinte nicht "in Ruhepausen", sondern zwischen 2 Schreibzugriffen. Nun kann man entweder einen nötigen Umtausch protokollieren um ihn später auszuführen um das Schreiben nicht zu lange zu unterbrechen oder falls zu viele zum Austauschen anfallen das Schreiben pausieren oder jedesmal falls nötig sofort austauschen. Aber halt nicht parallel zum Schreiben/Lesen, sondern dazwischen (IO pausiert).

Da bekommst Du ein Problem mit Deiner Marketingabteilung, weil Du Dein Flash wegen schlechter Zeiten bei den gängigen Schreib/Lesetests nicht mehr an den Mann bringen kannst.
 

PandoraSuechtig

Still Fresh
Joined
Oct 7, 2008
Messages
456
"0x000f & WC == 0" ? Nein, ich meinte "0xFFF0 & WC == 0". Test ob höherwertige gesetzt (&) und falls nicht (== 0), können nur die ersten Bits gesetzt sein, also Werte <= 0x00F (15).
Es muss kein Minimum gefunden werden oder gar explizit gegen einen Wert verglichen werden. Es genügt gegen die Maske zu prüfen und solange in jeder Iteration z.B. 4 Bit mehr zu maskieren bis endlich eine Ergebnismenge vorhanden ist. Daraus braucht man nur jeweils ein Ergebnis (einen Block) für das Ersetzen. Wie immer das bei Flash dann funktionieren sollte (z.B. "der erste, der sich dann meldet").
Nun kommt noch ein weiteres Problem : Bei dieser Suche würde (da sich die ganze Geschichte deterministisch verhält) kurz nacheinander aufgerufen immer derselbe Block als erster in dieser Ergebnismenge herauskommen? Nennen wir ihn Block A, er ist dem logischen Sektor a zugewiesen. Dann hätten wir noch einen Block B (log. b) und C (log. c), b und c werden häufig beschrieben. Zuerst muss B(b) ausgetauscht werden -> Er kriegt A zugewiesen (A und B werden also getauscht)
-- a(B) b(A) c(C)
Nun braucht c Ersatz, das Ergebnis liefert in Ergebnisreihe wieder als erstes A, also wird C und A getauscht:
-- a(B) b(C) c(A)
A wurde also weitergereicht und b hat wieder einen häufiger beschriebenen Block abgekriegt und wird später wieder schneller einen Ersatz benötigen? Das System weiss nicht, dass A schon einem logischen Sektor mit vielen Zugriffen zugewiesen war, diese Info wird im System nicht gemanaged. Je nach Algorithmus ist sie von Belang und könnte mitgespeichert werden. Wenn wir aber einen z.B. nach "mod 2^x == 0" Verfahren wechselnden WL-A. wählen, ist es diesem egal, da "C" gerade erst die Schwelle erreicht hat und b somit erst wieder nach "2^x" wieder die nächste Schwelle fürs Ersetzen treffen wird. Auch der Block A (nun bei c) wird oft beschrieben werden und daher bald einen hohen WriteCount erreichen und in der "Ergebnisliste" sowieso nicht mehr erscheinen.
grond said:
Da bekommst Du ein Problem mit Deiner Marketingabteilung, weil Du Dein Flash wegen schlechter Zeiten bei den gängigen Schreib/Lesetests nicht mehr an den Mann bringen kannst.
Wenn der Stick von einem testenden c't Redakteur dauernd auf demselben Sektor beschrieben wird, ist dieser irgendwann in der Notlage das Schreiben zu unterbrechen um den Block zu ersetzen oder er riskiert den Ausfall. Ist halt die Zwickmühle.
 

PandoraSuechtig

Still Fresh
Joined
Oct 7, 2008
Messages
456
Wenn wir so wieter diskutieren kommt am Ende vielleicht ein neuer WL-Alg. dabei raus?? Patent? wissenschaftliche Arbeit?... :)
 
A

Anonymous

Guest
PandoraSuechtig said:
"0x000f & WC == 0" ? Nein, ich meinte "0xFFF0 & WC == 0". Test ob höherwertige gesetzt (&) und falls nicht (== 0), können nur die ersten Bits gesetzt sein, also Werte <= 0x00F (15).

Ja, hast recht, keine Ahnung, warum ich so falsch gedacht habe.

Es muss kein Minimum gefunden werden oder gar explizit gegen einen Wert verglichen werden. Es genügt gegen die Maske zu prüfen und solange in jeder Iteration z.B. 4 Bit mehr zu maskieren bis endlich eine Ergebnismenge vorhanden ist.

Wie gesagt, Du suchst dann in Zweierpotenzschritten, bekommst also irgendwann plötzlich eine große Menge Blöcke, die nicht unterscheidbar zur Verfügung stehen. Das könnte ein Problem sein.

Nun kommt noch ein weiteres Problem : Bei dieser Suche würde (da sich die ganze Geschichte deterministisch verhält) kurz nacheinander aufgerufen immer derselbe Block als erster in dieser Ergebnismenge herauskommen?

Das würde nicht die Anzahl der Schreibzyklen insgesamt verringern (jeder Block hält halt eine bestimmte Anzahl Schreibzugriffe aus), aber es geht ja auch darum, die Kapazität möglichst lange gleich groß zu halten. Also ist es tatsächlich ein Problem (vorher dachte ich, das wäre egal).
 
A

Anonymous

Guest
PandoraSuechtig said:
Wenn wir so wieter diskutieren kommt am Ende vielleicht ein neuer WL-Alg. dabei raus?? Patent?

Da wir öffentlich diskutieren, wird es mit einem Patent schon einmal nichts werden. Vermutlich reden wir eh vollkommenen Quatsch... :lol:
 

SebuSoft

Still Fresh
Joined
Feb 6, 2009
Messages
185
Hallo Leute ;-)
Bin neu hier im Board (auch wenn schon etwas länger Heimlicher Verehrer der p&|a :oops: ) aber bei dem Thema muss ich mich auch einfach mal einklinken :)

Nicht das ich darin jetzt übermäßig erfahrung hätte oder so aber finde ich halt interessant :oops:

Habe vielleicht auch das ein oder andere nur flüchtig überlesen da es sich zu wiederholen schien, aber denke habe alles Erfasst und möchte auch meine 2Cent dazu steuern ;-)

Hoffe nur mein Schreibstil (Extrem Lange Sätze ohne Punkt und Komma :wacko: ) Schreckt nicht zu sehr ab :D

@grond: Jip das wollte ich auch schon vorschlagen als ich angefangen habe eure Diskusion zu lesen. Einfach die Blöcke nicht direkt anzusteuern sondern über ein Bus-System wo jeder Block seine Eigene Adresse kennt und mit den Daten Antwortet falls sie mit der gesuchten Adresse übereinstimmt :)

Das könnte man sogar noch so erweitern das der Controller intern mehr Adressen verwaltet als er nach aussen hin angibt so das Ersatz Blöcke erstmal mit nach Aussen hin nicht vorhandenen Adressen belegt werden.

Ein großer Vorteil dieses Bus-Systems ist es auch das sich die Adresse ja auch nur max. so oft ändert wie der Block neu beschrieben wird dabei also keine Probleme Auftauchen wie sie PandoraSuechtig bei der Zuordnungs-Tabelle sieht wobei man sonst auch dort dafür Sorgen könnte das jede Speicher Stelle einzeln angesprochen wird und dann nur so oft beschrieben wird wie der Block den sie representiert auch wenn bei der möglichkeit das finden eines Blockes erschwert wird.

Was das Auswechseln angeht muss ich allerdings sagen würde ich folgendes Vorschlagen: Sobald ein Block eine Bestimmte Anzahl von Überschreibungen hinter sich hat (sagen wir für möglichst einfache vergleiche z.B. vielfache von 1024) wird er mit dem bis zu dem Zeitpunkt am wenigsten benutzten Block ausgetauscht. Es gibt halt immer wieder Daten die einmal geschrieben und dann nur noch gelesen werden solche Blöcke hätten dann immer einen Count von 1 während andere dann vielleicht schon bei 9216 oder was weiß ich sind... (Auch wenn es bei meiner Methode nie zu soeinem Fall kommen würde) Da kann man denke ich ruhig in Kauf nehmen das beim wechseln beide einen Schreib vorgang verlieren da der Block der 1x beschrieben wurde mit großer Wahrscheinlichkeit auch länger nicht mehr neu beschrieben wird als der der dauernt neu beschrieben wurde! Dennoch würde ich aufgrund von Dateien deren "Staknation" dazwischen liegt und der Möglichkeit das auch Dateien die lange nie geändert würden mal gelöscht werden eher einen kleineren Wert als 9216 vorschlagen :-D Deswegen bei jedem vielfachen von 1024 ich halte es zumindest für extrem unwahrscheinlich das die Worst-Case Situation eintritt und ein paar Blöcke über den gesamten Adressraum gejagt werden also kurz nach dem sie getauscht haben plötzlich doch die Adresse die so wenig beschrieben wurde neu benutzt wird und danach dann wieder :-D

Hierbei sollte ein reger Austausch zwischen den Meistgeänderten und am wenigsten geänderten Dateien entstehen während das Mittel maß wohl seine Adesse lange behält aber alles in allem alle Blöcke ungefähr gleich stark belastet werden! Und da der Austausch nur alle 1024 Schreibzugriffe auf einen Block von ja min. 10.000 getauscht wird jeder Block wohl über die gesamt Lebensdauer des Systems 10-20 getauscht und die 10-20 Schreibzugriffe kann man denke ich verzeihen ;-)
 
Top