Verfahren zur Umsetzung von logischen in reale Blockadressen in Flashspeichern

Die Erfindung beschreibt ein Verfahren zur Verwaltung von Speicherblöcken in einem nichtflüchtigen Speichersystem mit einzeln löschbaren, mit realen Speicherblocknummern adressierbaren Speicherblöcken, die durch eine Adressumsetzung mittels Zuordnertabellen von einer logischen Blocknummer in jeweils eine der realen Speicherblocknummern adressierbar sin.

Flash- Speicher werden in vielen Computersystemen eingesetzt, insbesondere auch in wechselbaren Speicherkarten für digitale Kameras und tragbare Computer. Flash- Speicher sind in Speicherblöcken mit jeweils vielen Sektoren organisiert. Wesentliche Eigenschaften dieser Speicher sind, dass nur eine beschränkte Anzahl von Schreib- und Löschoperationen möglich ist und dass das Löschen nur in Speicherblöcken möglich ist, die mehrere Sektoren enthalten. Dabei beanspruchen die Schreib- und Löschvorgänge sehr viel mehr Zeit (bis zum Faktor 50) als das Lesen. Die Umsetzung von logischen Speicheradressen in reale Speicheradressen ist in Flashspeichersystemen bekannt, etwa aus der DE 102 27 256 für die gleichmäßige Abnutzung von realen Speicherblöcken oder aus der DE 103 41 616, um defekte reale Speicherblöcke zu verwalten. Die Speichersysteme bekommen immer mehr Speicherkapazität, damit werden die Speicherblockadressen länger und die Umsetzungstabellen von logischen in reale Speicherblockadressen immer größer.

Kleine Speicherblockgrößen, etwa von 4 KByte, sind günstig, um bei Dateisystemen mit vielen kleinen Dateien den Verlust durch nicht genutzten Platz in den Speicherblöcken nicht zu groß werden zu lassen. Vielfach werden nun größere Speicherblöcke von 32 KByte bis 256 KByte gebildet, um die Umsetzungstabellen entsprechend kleiner zu halten. Dabei ist es wichtig, die Adresszeiger in den Tabellen auf 16 Bit zu begrenzen, um die Adressumsetzung schnell und effizient durchführen zu können.

Es ist Aufgabe der Erfindung unterschiedlich große Speichersysteme mit einheitlichen Tabellenstrukturen bei unterschiedlichen realen Speicherblockgrößen effizient zu verwalten.

Gelöst wird diese Aufgabe dadurch, dass die logische Blocknummer über eine erste Tabelle einer physischen Speicherblocknummer zugeordnet und über eine zweite Tabelle die physische Speicherblocknummer einer realen Speicherblocknummer zugeordnet wird, wobei mit einer physischen Speicherblocknummer ein oder mehrere reale Speicherblöcke adressiert werden.

Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen angegeben.

Die zweite Tabelle ordnet einer physischen Speicherblocknummer ein oder mehrere reale Speicherblöcke zu, wobei die Größe der realen Speicherblöcke durch die

Strukturierung der eingesetzten Speicherchips vorgegeben ist. So werden Chips mit Blockgrößen von 4 KByte oder mit Blockgrößen von 32 KByte, 64 KByte, 128 KByte oder noch größeren realen Blöcken eingesetzt.

Es ist ein Vorteil des Verfahrens, dass die erste Adressumsetzung von logischen Speicherblocknummern in physische Speicherblocknummern unabhängig von der

Größe der realen Speicherblöcke durchgeführt wird. Das Verfahren ist somit bei vielen unterschiedlich großen Speichersystemen einsetzbar. Die Verwaltung von defekten realen Speicherblöcken wird nur mittels der zweiten Adressumsetztabelle durchgeführt, indem in der zweiten Tabelle die Nummern von defekten Speicherblöcken durch die Nummern von funktionsfähigen Speicherblöcken ersetzt werden. Die Nummern von defekten Speicherblöcken werden dann in ungenutzten Bereichen der zweiten Tabelle geiührt.

Die Bildung der physischen Speicherblöcke in der ersten Adressumsetzungstabelle hat den Vorteil, dass große Speicherblöcke aus mehreren realen Speicherblöcken gebildet werden, auf die eine Speicheroperation gemeinsam angewendet wird, unabhängig davon, wo die realen Speicherblöcke in den Speicherchips lokalisiert sind. Dies erhöht die Geschwindigkeit bei der Abarbeitung der Speicheroperationen.

Die Geschwindigkeit der Abarbeitung der Speicheroperationen wird weiter erhöht, wenn die realen Speicherblöcke in verschiedenen Speicherchips liegen. Dann werden die Speicheroperationen, wie „schreiben" oder „löschen" parallel in den Speicherchips durchgeführt (interleaving). Bei einigen Typen von Speicherchips ist eine große Zahl von Speicherblöcken in so genannten Bänken zusammengefasst, die parallel

Speicheroperationen durchfuhren können. Wenn nun die physischen Speicherblocks jeweils nur aus realen Speicherblöcken bestehen, die in verschiedenen Bänken und in Verschiedenen Speicherchips liegen, wird die parallele Abarbeitung von Speicheroperationen auf allen realen Speicherblöcken durchgeführt und eine maximale Verarbeitungsgeschwindigkeit erreicht.

Die Tabellen zur Adressumsetzung werden in für die Verwaltung reservierten nichtflüchtigen realen Speicherblöcken gehalten. Sie stehen damit auch nach einem Stromausfall zur Verfügung. Zur schnellen Bearbeitung der Speicheroperationen werden Kopien von aktuell benötigen Teilen der Adressumsetzungstabellen zusätzlich in einem internen schnellen RAM-Speicher gehalten (caching). Die Nummern der für die Verwaltung des Speichersystems reservierten Speicherblöcke werden nicht mit in die erste Tabelle zur Adressumsetzung aufgenommen. Sie sind damit von außen nicht über logische Sektornummern adressierbar. Ein kleiner Prozentsatz von Speicherblöcken, etwa 3%, werden für den Ersatz defekt gewordener Speicherblöcke reserviert. Auch die Nummern dieser realen Speicherblöcke werden nicht mit in die erste Tabelle zur Adressumsetzung aufgenommen. Sie sind damit von außen nicht über logische Sektornummern adressierbar.

Eine vorteilhafte Ausführung der Erfindung ist beispielhaft in den Figuren beschrieben. Fig. 1 zeigt ein Blockdiagramm eines Speichersystems mit 12 Speicherchips. Fig. 2 zeigt den Aufbau der beiden Adressumsetzungstabellen. Fig. 3 zeigt zwei Beispiele der Übersetzung von logischen Adressen in reale Adressen.

In Fig. 1 ist ein Blockdiagramm für ein Speichersystem aus zwölf Speicherchips CO bis CI l mit jeweils einer Speicherkapazität von 128 Megabyte dargestellt. Das Speichersystem besitzt damit eine Größe von 1,5 Gigabyte. Speicheroperationen wie „lesen" und „schreiben" können mit logischen Sektoren von jeweils 512 Byte Größe

- A -

durchgeführt werden. Acht reale Speichersektoren von 512 Byte Größe sind zu realen Blöcken von 4 KByte zusammengefasst, die gemeinsam löschbar sind. Die zwölf Speicherchips CO bis CIl besitzen jeweils 262144 reale Sektoren, von denen jeweils vier eine Page bilden. Zwei Pages bilden jeweils einen realen Speicherblock, die in jeweils vier Bänken BAO bis B A3 angeordnet sind. Jeweils vier Speicherchips sind logisch zu einem Superchip SCO bis SC3 zusammengefasst. Ein physischer Speicherblock PB umfasst nun sechzehn reale Speicherblöcke aus den vier Chips eines Superchips aus jeweils vier unabhängigen Bänken mit zusammen 64 KByte. In dem hier gezeigten Fall ist der physische Block PB in dem Superchip SCO mit den Chips CO bis C3 mit jeweils einem realen Speicherblock in jedem der vier mal vier Bänke BAO bis BA3 gebildet. Alle realen Speicherblöcke des physischen Blocks PB können damit eine Speicheroperation parallel abarbeiten.

In den Fig. 2A und 2B sind zwei Beispiele von Adressumsetzungen angegeben. In Fig. 2A soll eine Speicheroperation auf den logischen Sektor LSN mit der Nummer 127 durchgeführt werden. Dazu wird die logische Sektornummer in die Bestandteile Sektornummer in einer Page PN, Tupelindex TI und logische Blocknummer LBN aufgeteilt. Da sechzehn Blöcke mit jeweils acht Sektoren zu einem physischen Sektor zusammengefasst sind, ergibt sich eine physische Sektornummer zwischen 0 und 127. Die realen Sektornummern in einer Page sind nicht unbedingt fortlaufend, sondern können je nach Größe der Page Lücken aufweisen. Hier ist angenommen, dass eine Page vier reale Sektoren besitzt und jeweils zwei Pages zu einem Realblock zusammengefasst sind. Da aufeinander folgende Pages in aufeinander folgenden Bänken angeordnet sind, entstehen in einem Realblock entsprechend der Anzahl der Bänke und der Chips Lücken in der Nummerierung der realen Sektoren. In diesem

Beispiel wird daher zur Bildung der realen Sektornummer das Bit6 B6 als oberstes Bit der realen Sektornummer angesehen. In diesem Fall ist die logische Blocknummer LBN gleich 0, der Tupelindex TI = 15 und die Pagenummer PN = 3. Die physische Sektornummer PSN wird zu 127. Das Bit B6 wird als fünftes Bit der Realen Sektornummer RSN genutzt. Damit wird die Reale Sektornummer RSN gleich 31. Die logische Blocknummer LBN indiziert die erste Tabelle LTP aus Fig. 3 und liefert die Superchipnummer SC = 0 und die physische Blocknummer PBN = 0.

Auf die gleiche Weise ist in Fig. 2B die logische Sektornummer 1011769 aufgespaltet. Hier wird die Pagenummer PN = 1, der Tupelindex TI = 10 und die logische Blocknummer LBN = 7904. Die physische Sektornummer hat den Wert 125. Das Bit B6 wird als fünftes Bit der Realen Sektornummer RSN genutzt. Damit wird die Reale Sektornummer RSN gleich 25.

Die logische Blocknummer LBN indiziert die erste Tabelle LTP aus Fig. 3 und liefert die Superchipnummer SC = 1 und die physische Blocknummer PBN = 0.

In Fig.3 ist die Struktur der beiden Tabellen LTP und PTR gezeigt. In der ersten Tabelle zur Adressumsetzung LTP wird die logische Blocknummer LBN in die Adresse eines physischen Blocks umgesetzt, die aus den Bestandteilen Superchipnummer SCN und physische Blocknummer PBN besteht. In dem hier dargestellten Beispiel sind drei Superchips mit den Nummern 0 bis 2 vorhanden. Die Superchipnummer ist somit 2 Bit breit. Eine physische Blocknummer besteht aus dreizehn Bit und kann damit Werte von 0 bis 8191 annehmen. Um Platz für 32 Verwaltungsblöcke und jeweils 256 Reserveblöcke zu lassen, reichen die Werte nur bis 7903 bzw. bis 7935. Wie in Fig. 2 dargestellt, ist die logische Blocknummer LBN in diesem Beispiel 16 Bit breit und kann Werte zwischen 0 und 24319 annehmen, entsprechend der Summe der physischen Blöcke der drei Superchips SCO bis SC2. Die Zeiger aus der ersten Tabelle LTP dienen als Index in die zweite Tabelle PTR. Sie zeigen jeweils auf ein Tupel von sechzehn realen Blöcken, die in vier mal vier Bänken BAO bis BA3 angeordnet sind. Ein Tupel ist in vier Chips eines Superchips angeordnet. Somit ergibt sich eine Tabelle mit 16 Spalten, in der jeweils die realen Blocknummern einer Bank angegeben sind. Es können Werte zwischen 0 und 7903 bzw. 7935 angegeben sein, solange keine Ersatzblöcke eingetragen wurden. So ist z.B. in der zweiten Zeile an letzter Position ein Ersatzblock EB eingetragen, der dann eine größere Blocknummer besitzt. Die Blocknummern können nur Werte modulo der Banknummer besitzen. Durch Verwaltungsoperationen können die Blocknummern aber beliebig innerhalb der Bänke vertauscht sein. Die Zeilen der Tabelle PTR, die nicht durch eine physische Blocknummer adressierbar sind, sind ungenutzt, hier durch jeweils ein U gekennzeichnet.

Die durch die beiden Beispiele aus Fig. 2 zu adressierenden realen Speicherblöcke sind in der Tabelle durch Schraffur kenntlich gemacht. Die logischen Sektornummer LSN =

127 adressiert über SCN = O und PBN = 0 hier den Block 3 in der ersten Zeile der Tabelle PTR mit dem Tupelindex TI = 15 und gehört zu Chip 0*4+3 = 3. Die logischen Sektornummer LSN = 1011769 adressiert über SCN = 1 und PBN = 0 hier den Block 2 mit dem Tupelindex TI = 10 und gehört zu Chip 1 *4+2 = 6.

Bezugszeichenliste

BAn Banknummer

Cn Chipnummer

EB Ersatzblock

LBN logische Blocknummer

LSN logische Sektornummer

LTP erste Tabelle (logtophys)

PBn physische Blocknummer

PTR zweite Tabelle (phystoreal)

RBN reale Blocknurnmer

RSN reale Sektornummer

PN Pagenummer

PSN physische Sektornummer

SCn Superchipnummer

SN Sektornummer

TI Tupelindex

U Ungenutzte physische Blöcke