DE69414556T2 - Schnell loeschbare datei - Google Patents

Description

HINTERGRUND DER ERFINDUNG Gebiet der Erfindung
• Diese Erfindung betrifft ein verbessertes System zum Speichern und Wiedergewinnen von Informationen in Flash-Speichern und ganz besonders ein System, das in einen Flash- Speicher geschriebene Daten organisiert und verwaltet.
Beschreibung des Standes der Technik
• Wie dem Fachmann ersichtlich ist, sind bei elektrisch löschbaren und programmierbaren Festwertspeichern (EEPROMs) vom Flash-Typ Transistoren mit schwebendem bzw. veränderlichem Gatter im Stand der Technik beschrieben worden und derzeit wirtschaftlich erhältlich. Diese sogenannten Flash- Speicher sind nicht-flüchtige Speicher ähnlich in Funktionalität und Leistung zu EPROM-Speichern mit einer zusätzlichen Funktionalität, die einen systeminternen programmierbaren Vorgang gestattet, um Blöcke des Speichers zu löschen. In einem Flash-Speicher ist es in der Praxis nicht geeignet, einen zuvor beschriebenen Bereich eines Speichers ohne eine vorhergehende Blocklöschung des Bereiches wieder zu beschreiben. Während diese Erfindung im Zusammenhang mit einem Flash-Speicher beschrieben wird, versteht es der Fachmann, daß deren Lehre ebenso auf Datenspeichervorrichtungen mit den gleichen Schreib-, Lese- und Blocklöschungscharakteristiken vor Schreibcharakteristiken wie bei Flash- Speichern anwendbar ist.
• In einem typischen Computersystem ist das verarbeitende bzw. bearbeitende Systemprogramm für die Datenverwaltung der Datenspeichervorrichtungen, die Teil des Systems sind, verantwortlich. Um eine Kompatibilität mit dem verarbeitenden bzw. bearbeitenden Systemprogramm zu erreichen, besteht ein notwendiges und gewöhnlicherweise ausreichendes Attribut einer Datenspeichervorrichtung darin, daß sie Daten aus jedem Platz in dem Datenspeichermedium (aus-)lesen und darin (ein-)schreiben kann. Daher sind Flash-Speicher nicht mit typischen existierenden verarbeitenden bzw. bearbeitenden Systemprogrammen kompatibel, wenn Daten nicht in einen Bereich eines Flash-Speichers geschrieben werden können, in welchen Daten vorher geschrieben wurden, bis der Bereich erst gelöscht ist.
• Softwareprodukte sind im Stand der Technik vorgeschlagen worden, um einem Flash-Speicher zu gestatten, durch existierende computerverarbeitende Programme ohne Modifikation des verarbeitenden bzw. bearbeitenden Systemprogrammes verwaltet zu werden. Diese bekannten Programme betreiben allerdings den Flash-Speicher als eine "Einmal-Schreib-Oftmals-Lese-"Vorrichtung. Dieses bekannte Softwareprodukt kann zuvor beschriebene Speicherplätze nicht wiederherstellen. Wenn sämtliche Plätze gegebenenfalls beschrieben sind, kann der Speicher ohne ein spezifisches Benutzereingreifen nicht weiter verwendet werden.
• Die GB-A-2 251 323 offenbart einen Flash-Speicher, der blocklöschbar ist und der einen aktiven Block zum Speichern von ersten Daten sowie einen Reserveblock zum Speichern von zweiten Daten, die eine Kopie der ersten Daten sind, welche während eines Putzvorganges vor dem Löschen des aktiven Blockes hergestellt sind, beinhaltet. Die Reserblöcke sind Blöcke, die eine zeitweise Dateisicherung während des Putzvorganges vorsehen. Der Flash-Speicher beinhaltet eine Verzeichnistabelle zum Verzeichnen einer logischen Adresse einer Zuordnungseinheit zu einer physikalischen Adresse eines Bereiches (Zuordnungseinheit) in dem Speicher. Eine weitere Tabelle ist vorhanden, um Informationen bereitzustellen, ob ein Block ein aktiver Block oder ein Reserveblock ist und ob der Block frei oder in Benutzung ist. Ein Putzvorgang zieht einen Wiederzuordnungsvorgang nach sich. Dabei werden sämtliche gegenwärtig aktiven Dateien aus den Blöcken, die eventuell zu löschen sind, herausbewegt. Die Verzeichnistabelle ist eine verbundene Liste, wobei jede verbundene Listenkette in der Verzeichnistabelle eine historische Aufzeichnung der Schaffung und Entfernung von schmutzigen Bereichen darstellt.
ZUSAMMENFASSUNG DER ERFINDUNG
• Eine Aufgabe dieser Erfindung besteht in der Bereitstellung eines Verfahrens (d. h. einer Software, Firmware einer Hardware), um einen Zugang zu einem Flash-Speicher zu steuern und zu verwalten, so daß der Flash-Speicher für das computerverarbeitende System als eine Datenspeichervorrichtung erscheint, bei welcher es möglich ist, Daten aus jedem Flash-Speicherplatz (aus-) zu lesen oder darin (ein-) zu schreiben. Ein Verfahren, das einem Flash-Speicher gestattet, Direktzugriffsspeicher zu emulieren, und existierenden computerverarbeitenden Systemen gestattet, jede andere erforderliche Unterstützung in der gleichen Weise, die durch Standard-Direktzugriffsspeicher bereitgestellt und von dem Emulationsverfahren unabhängig sind, zur Verfügung zu stellen.
• Kurz gesagt beabsichtigt diese Erfindung die Bereitstellung eines Flash-Speichers, eines virtuellen Verzeichnissystems, das gestattet, Daten kontinuierlich in unbeschriebene physikalische Adreßplätze geschrieben zu werden. Das virtuelle Speicherverzeichnis verknüpft physikalische Platzadressen des Flash-Speichers, um den Platz der Daten in dem Speicher zu verfolgen.
• Die physikalischen Plätze des Flash-Speichers sind als ein Feld von Bytes organisiert. Jedem der Bytes in dem Feld ist eine Adreßnummer aufgrund derer das Byte physikalisch zugänglich ist, die hierin als der physikalische Adreßraum bezeichnet ist, zugeordnet. Jedes der Bytes in dem Feld weist eine zweite Adresse, genannt der virtuelle Adreßraum, auf. Eine Tabelle, genannt ein virtuelles Verzeichnis, konvertiert virtuelle Adressen in physikalische Adressen. Hier ist zu bemerken, daß der virtuelle Adreßraum nicht notwendigerweise die gleiche Größe wie der physikalische Adreßraum aufweist.
• Eine zusammenhängende, in der Länge festgelegte Gruppe von physikalischen Byteadressen bildet einen Block. Unter Voraussetzung einer Blockgröße von 512 Byte ist zum Beispiel ein Byte mit einer physikalischen Adresse von 256211 die Bytenummer 211 in Block 500 (256211 : 512 = 500 + 211). Ein oder mehrere physikalische zusammenhängende Bereiche (sogenannte Zonen) eines Flash-Speichers, die physikalisch gelöscht werden können, indem eine geeignete bekannte Flash- Speichertechnologie verwendet wird, umfaßt eine Einheit und jede Einheit beinhaltet eine integrale Anzahl von Blöcken.
• Das virtuelle Speicherverzeichnis ist eine Tabelle, in welcher der erste Eingang zum virtuellen Block 0, der zweite zum virtuellen Block 1 usw. gehört. In der Tabelle ist zu jeder virtuellen Blockadresse eine entsprechende physikalische Adresse zugeordnet. Beim (Aus-)Lesen aus dem Flash- Speichervorgang wird eine computererzeugte Adresse als eine virtuelle Blockadresse und ein Byteplatz im Block decodiert. Das virtuelle Speicherverzeichnis wird verwendet, um die virtuelle Blockadresse in eine physikalische Blockadresse umzuwandeln bzw. zu konvertieren; der Byteplatz ist der gleiche in dem virtuellen Adreßraum und dem physikalischen Adreßraum.
• Bei einem Schreibvorgang wird die computererzeugte Adresse wiederum als eine virtuelle Blockadresse und ein Byteplatz in dem Block interpretiert. Das virtuelle Speicherverzeichnis konvertiert diese in eine physikalische Speicherblockadresse. Wenn der Flash-Speicherblock, welcher der physikalischen Adresse entspricht, dann gegenwärtig beschrieben wird, ist es im allgemeinen nicht möglich, diese physikalische Adresse zu beschreiben. Ein unbeschriebener Block wird daher angepeilt bzw. aufgefunden und beschrieben. Das virtuelle Speicherverzeichnis wird geändert, so daß die unbeschriebene physikalische Blockadresse zu der ursprünglichen virtuellen Adresse verzeichnet wird und die ursprüngliche physikalische Adresse als unbenutzbar bezeichnet wird und unbenutzbar bleibt, bis ein Zonenlöschungsvorgang stattfindet, welcher die Einheit, die diesen Block beinhaltet, löscht. Es ist zu bemerken, daß ein Schreibvorgang annimmt, daß ein gesamter Block wieder beschrieben werden wird. Auf diese Weise finden Computersysteme gewöhnlich Daten in einem Speichermedium. Allerdings ist es ersichtlich, daß im allgemeinen jede gewünschte Anzahl von Bytes in den neuen Speicherplatz geschrieben werden könnte.
• Bei einer bevorzugten Ausführungsform der Erfindung wird jede Einheit einer logischen Einheitsadresse zugeordnet, die unverändert bleibt, wenn die Einheit in einen neuen physikalischen Adreßplatz in einem Flash-Speicher wieder beschrieben wird. Das virtuelle Verzeichnis beinhaltet Bezugnahmen auf die logischen Einheitsadressen eher als die physikalischen Einheitsadressen, so daß eine Datenbewegung während Einheitsübertragungen keine Auswirkung auf ein virtuelles Verzeichnis hat.
• Jede Einheit weist ein Benutzerverzeichnis von sämtlichen Blöcken innerhalb der Einheit auf; die virtuelle Adresse eines Blockes, wenn sie verzeichnet ist, und die besonderen Zeichen, um freie Blöcke zu bezeichnen und um nicht verwendbare Blöcke zu bezeichnen.
• Nicht verwendbare Blöcke des zuvor beschriebenen Flash- Speichers werden zurückgewonnen, indem Speichereinheiten, welche die nicht verwendbaren Blöcke beinhalten, zu einem reservierten, unbeschriebenen Raum in dem Flash-Speicher übertragen werden. Nur die verwendbaren Blöcke werden bei dem Übertragungsvorgang beschrieben, so daß die Plätze, an welchen sich die nicht verwendbaren Blöcke befinden, wenn wieder beschrieben, in dem reservierten Raum nicht wieder beschrieben werden und daher verwendbar sind. Nach erfolgter Wiederbeschreibung wird der ursprüngliche Speichereinheitsraum als eine Einheit blitzartig gelöscht und wird daher ein unbeschriebener reservierter Raum, auf den eine nachfolgende Übertragung erfolgen kann.
• Bei einer bevorzugten Ausführungsform der Erfindung wird auch das virtuelle Verzeichnis primär bzw. hauptsächlich in dem Flash-Speicher mit nur einem kleinen sekundären virtuellen Verzeichnis im Direktzugriffsspeicher gespeichert. Das virtuelle Verzeichnis in einem Flash-Speicher wird in Blöcken gespeichert und in bzw. auf Seiten organisiert, deren Größe gleich dem Produkt der Anzahl von Bytes in einem Block mal der Anzahl von physikalischen Blockadressen diese Anzahl von Bytes repräsentierend ist. Ein sekundärer Direktzugriffsspeicher beinhaltet die Seitenadressen. Beim Lesen von Daten für eine vorgegebene virtuelle Adresse wird die Seitenzahl durch Teilen einer Adresse durch die Seitengröße bestimmt. Das Ergebnis indiziert das sekundäre virtuelle Verzeichnis, um den richtigen primären virtuellen Verzeichnisblock zu finden. Der Rest wird verwendet, um die erforderliche physikalische Adresse für das virtuelle Verzeichnis, das in dem Flash-Speicher gespeichert ist, zu berechnen. Um das virtuelle Verzeichnis in dem Flash-Speicher zu ändern, wird das geänderte Verzeichnis in einen freien Block geschrieben und wird das sekundäre Verzeichnis in dem Direktzugriffsspeicher geändert, um die Änderung in dem primären Verzeichnisplatz zu reflektieren. Der ersetzte Block wird als gelöscht markiert.
KURZBESCHREIBUNG DER ZEICHNUNGEN
• Die vorhergehenden und anderen Aufgaben, Aspekte und Vorteile werden aus der nachfolgenden detaillierten Beschreibung einer bevorzugten Ausführungsform der Erfindung unter Bezugnahme auf die Zeichnungen besser verständlich, wobei:
• Fig. 1 ein Blockdiagramm ist, das zweckmäßige Komponenten eines Systems in Übereinstimmung mit einer Ausführungsform eines Systems gemäß der Lehre dieser Erfindung darstellt,
• Fig. 2 eine bildliche Darstellung eines Niveaus einer Flash-Speicherorganisation in Übereinstimmung mit der Lehre dieser Erfindung ist,
• Fig. 3 eine bildliche Darstellung ist, auf welche Weise eine Einheit formatiert wird,
• Fig. 4 eine bildliche Darstellung ist, welche zeigt, wie die computererzeugten Adressen in physikalische Adressen verzeichnet werden,
• Fig. 5 ein Flußdiagramm ist, welches einen Lesevorgang darstellt,
• Fig. 6 ein Flußdiagramm ist, welches einen Schreibvorgang darstellt,
• Fig. 7 ein Bilddiagramm ist, welches den Stand einer Einheit vor und nach einem Übertragungsvorgang darstellt,
• Fig. 8 ein Flußdiagramm eines Übertragungsvorganges ist,
• Fig. 9 ein Flußdiagramm ist, welches den Vorgang zeigt, bei dem ein überwiegender Teil des virtuellen-zu- physikalischen Verzeichnisses in einem Flash- Speicher gespeichert wird.
DETAILLIERTE BESCHREIBUNG EINER BEVORZUGTEN AUSFÜHRUNGSFORM
• Nun Bezug nehmend auf die Fig. 1 der Zeichnungen gibt in einem typischen System ein Prozessor 10 in Kombination mit dessen verarbeitender bzw. bearbeitender Systemsoftware eine Reihe von Lese- und Schreibbefehlen aus, um Daten auszulesen und in spezifische Adreßplätze in einem Direktzugriffsspeicher zu schreiben. Wie es durch den Fachmann ersichtlich ist, können in einer Direktzugriffsspeichervorrichtung, wie einem Disk-Speicher, Daten (ein-)geschrieben oder aus jedem Adreßplatz (aus-)gelesen werden. Der Prozessor 10 bei dem System der Fig. 1 schreibt Daten in einen und liest Daten aus einem Flash-Speicher 12 in Blöcken an spezifischen Adreßplätzen. Obschon Zonen des Flash- Speichers 12 gelöscht werden können, können gegenwärtig beschriebene Adreßplätze nicht wieder beschrieben werden, bis die gesamte Zone gelöscht ist. In Übereinstimmung mit der Lehre dieser Erfindung stellt eine Flash-Speichersteuereinrichtung 14 einen vollständig wiederbeschreibbaren virtuellen Adreßraum zur Verfügung, so daß der Flash-Speicher 12 einen Direktzugriffsspeicher, wie einen Disk-Speicher, emuliert, und stellt die prozessorverarbeitende Systemsoftware sämtliche weitere erforderliche verarbeitende Unterstützung (wie ein Dateisystem) in der gleichen Weise bereit, wie sie es für einen Standard-Direktzugriffsspeicher vorsieht, und in einer Weise, die unabhängig von dem Flash- Speicher 12 und dessen Steuereinrichtung 14 ist. Ein typisches System beinhaltet auch einen herkömmlichen Direktzugriffsspeicher 16. Es ist ersichtlich, daß die Funktionen der Steuereinrichtung 14 in einer Software, Firmware einer Hardware durchgeführt werden können und nicht notwendigerweise als eine physikalisch getrennte Einheit besteht, wie in der Zeichnung vorgeschlagen ist.
• Nun Bezug nehmend auf die Fig. 2 ist teilweise die Organisation des Flash-Speichers dargestellt. Der Flash-Speicher weist eine Anzahl von Zonen auf, die hier als Zone A, Zone B etc. bezeichnet sind. Jede Zone ist aus einer Anzahl von zusammenhängenden physikalischen Speicherplätzen zusammengesetzt, die bei Verwendung einer herkömmlichen, hinlänglich bekannten Flash-Speichertechnologie blockweise gelöscht bzw. blockgelöscht werden können. Die Zonen sind als Einheiten organisiert, von denen nur vier gezeigt sind, welche in der Zeichnung als EINHEIT #1, EINHEIT #6, EINHEIT N-1 und ÜBERTRAGUNGSEINHEIT bezeichnet sind. Jede Einheit ist aus wenigstens einer Zone einer Vielzahl von zusammenhängenen Zonen zusammengesetzt. Wie hier dargestellt ist, ist j ede Einheit aus zwei Zonen zusammengesetzt (d. h. EINHEIT #1 - Zone A und Zone B; EINHEIT #2 - Zone C und Zone D, ÜBERTRAGUNGSEINHEIT - Zone x2 und 2x).
• Jede Einheit ist aus einer integralen Anzahl von adressierbaren Blöcken zusammengesetzt und jeder Block wiederum ist aus einer zusammenhängenden, in der Länge festgelegten Gruppe von Bytes zusammengesetzt. Es ist immer eine Einheit in dem Speicher 12 vorhanden, der unbeschrieben ist (d. h. eine ÜBERTRAGUNGSEINHEIT), so daß aktive Blöcke in eine Einheit, die gelöscht werden muß, in diese unbeschriebene Einheit vor Löschen der Einheit geschrieben werden können.
• Nun auf die Fig. 3 Bezug nehmend beinhaltet jede Einheit eine integrale Anzahl von zusammenhängenden Datenblöcken 21, die wiederum aus zusammenhängenden Byteadressen zusammengesetzt sind, die als eine Blockzahl und eine Verschiebung bzw. Versetzung bzw. einen Offset innerhalb des Blockes adressiert werden können. Jeder Block in einer Einheit weist eine Einheit auf, die durch die Blockzahl und die Verschiebung mit der bzw. um die Einheit adressiert werden kann. Jede Einheit weist einen Einheitskopf bzw. ein oberes Einheitsende 23 und ein Verzeichnis 25 des Zuordnungsstatus jedes Blockes in der Einheit auf. Der Einheitskopf 23 um faßt eine Formatidentifizierungseinrichtung und die logische Einheitszahl der Einheit. Da sich Daten während einer Einheitsübertragung physikalisch bewegen müssen, bleibt die Einheitszahl vorzugsweise unverändert, selbst wenn sich der physikalische Platz der Einheit in dem Flash-Speicher 12 ändert. Zusätzlich kann der Kopf auch systemweite Informationen beinhalten. Das Blockzuordnungsverzeichnis 25 weist ein Wort für jeden Block auf, das dessen Status und dessen Verschiebung in der Einheit bezeichnet. Die Statusanzeigen sind: "Block frei und beschreibbar", "Block gelöscht und nicht beschreibbar", "Block ordnet zu und enthält Benutzerdaten" und eine virtuelle Adresse des Blockes (Rückversetzungszeiger).
• Wie zuvor erwähnt ist, wird jeder Einheit vorzugsweise eine logische Einheitszahl zugeordnet, die sich nicht ändert, selbst wenn sich der physikalische Platz in dem Speicher der Einheit ändert. Wie in der Fig. 4 dargestellt ist, sind die durch den Computer 10 erzeugten Adressen 29 aus einer Blockzahl und einer Blockverschiebung zusammengesetzt. Diese Adressen werden durch die Flash-Steuereinrichtung 14 als virtuelle Adressen interpretiert und ein virtuelles Verzeichnis wird verwendet, um eine Übereinstimmung zwischen dem virtuellen Adreßraum und dem physikalischen Adreßraum herzustellen. Die virtuellen Verzeichnisänderungen als Blöcke werden wieder beschrieben und der virtuelle Adreßraum ist daher dynamisch. Es ist ebenso zu bemerken, daß ein Block oder Blöcke in dem virtuellen Adreßraum jederzeit in den physikalischen Adreßraum umverzeichnet bzw. umgewandelt werden können und daß Blöcke in dem physikalischen Adreßraum unbeschrieben und daher frei sein können, beschrieben zu werden.
• Da sich die Daten während einer Einheitsübertragung in einen unbeschriebenen Einheitsraum physikalisch bewegen, werden die Daten logischen Einheitszahlen zugeordnet, die sich mit Änderungen in dem physikalischen Raum der Einheit in dem Speicher nicht ändern. Ein virtuelles Verzeichnis 31 verzeichnet Blockzahlen in der virtuellen Adresse in einer logischen Blockadresse bzw. bildet Blockzahlen in der virtuellen Adresse auf eine logische Blockadresse in dem ersten Schritt einer Zwei-Schritt-Adressenübersetzung bzw. Zwei-Schritt-Adressenübertragung ab. Die logische Einheitsadresse ist eine auf eine logische Einheitszahl bezogene Adresse, ähnlich einer physikalischen Adresse, die eine auf eine physikalische Einheitszahl bezogene Adresse ist. Die logische Einheitszahl sind die höherwertigen binären Zahlen der logischen Adresse und können von der logischen Adresse durch einen Bitverschiebungsvorgang abgeleitet werden. Die aus dem Verzeichnis 31 erhaltene logische Adresse 33 beinhaltet eine logische Einheitszahl längs mit der Verschiebung des Blockes in(-nerhalb) der Einheit.
• Eine logische Einheitstabelle 35 überträgt bzw. setzt die logische Einheitszahl in eine physikalische Einheitszahl für die logische Einheit um. Dieser Zwei-Schritt- Adressenübersetzungsvorgang bzw. Zwei-Schritt-Adressenübertragungsvorgang vermeidet die Notwendigkeit, Blockadressen in dem Verzeichnis zu ändern, wenn eine Einheit an einen neuen physikalischen Platz bewegt wird.
• In einem Lesevorgang wird die virtuelle Adresse 29, die aus einer Blockadresse zum Beispiel zusammengesetzt ist, anfänglich in einer logischen Einheitszahl und einer Blockverschiebung innerhalb der Einheit in dem adressierten Block verzeichnet. Das Verzeichnis 35 verzeichnet die Einheitszahl 33 in einer physikalischen Adresse 37 für die Einheit längs mit der Verschiebung des adressierten Blockes 37 innerhalb der Einheit und der adressierte Datenblock wird aus diesem physikalischen Raum gelesen. Hier ist vorausgesetzt, daß Daten auf einer Blockbasis gelesen und geschrieben werden, wie es typischerweise erfolgt ist. Natürlich können Daten auf einer Bytebasis bei Verwendung des gleichen Prinzips, wenn gewünscht, geschrieben und gelesen werden. Die Fig. 5 ist ein Flußdiagramm, das diesen Lesevorgang darstellt. Wie zuvor erklärt ist, wird die virtuelle Adresse 29 in einer logischen Adresse (Block 40) in dem ersten Schritt einer Zwei-Schritt-Adressenübersetzung bzw. Zwei-Schritt-Adressenübertragung verzeichnet bzw. in einer logischen Adresse (Block 40) abgebildet. In dem zweiten Schritt wird die logische Adresse in einer physikalischen Adresse in dem Flash-Speicher, Block 41, verzeichnet bzw. abgebildet. Daten werden an dieser physikalischen Adresse gelesen, Block 42, der den Vorgang abschließt.
• Bei einem Schreibvorgang wird die virtuelle Adresse 29 wiederum anfänglich in einer logischen Einheitszahl und einer Blockverschiebung innerhalb der Einheit verzeichnet. Der Algorithmus der Steuereinrichtung 14 untersucht das Blockzuordnungsverzeichnis 25 für diese Einheit. Wenn der zu dieser Adresse korrespondierende Block geschrieben worden ist, kann ein Schreibbefehl an der korrespondierenden physikalischen Adresse nicht ausgeführt werden. Der Steueralgorithmus scannt bzw. fragt das Blockzuordnungsverzeichnis 25 für jede Einheit ab, bis ein freier Block aufgefunden wird. Der Status des Blockes in dem Blockverzeichnis 25 an der ursprünglichen Einheitsadresse wird geändert, um in dem Block in dem Zuordnungsverzeichnis gelöscht zu werden, und der Status des freien Blockes wird geändert, um beschrieben zu werden. Das virtuelle Verzeichnis 31 wird aktualisiert, so daß die ursprüngliche virtuelle Adresse nun auf die neue logische Adresse hinweist, in welcher der Schreibvorgang stattfinden muß. Diese logische Adresse wird in einer physikalischen Adresse in der zuvor beschriebenen Weise verzeichnet bzw. abgebildet und der Block wird in diese Adresse geschrieben. Die Fig. 6 ist ein Flußdiagramm, das diesen Schreibvorgang darstellt. Bei einem Schreibvorgang wird die virtuelle Adresse 29 in einer logischen Einheitsadresse verzeichnet, Block 45, und wird die Einheitszuordnung für die Einheit untersucht, Block 46. Wenn in einem Entscheidungsblock 47 die Einheitsadresse frei ist, wird die Ein heitsadresse in einer physikalischen Adresse verzeichnet bzw. abgebildet, Block 48, und werden Daten in diese physikalische Adresse (ein-)geschrieben, Block 49, und endet der Vorgang. Wenn die logische Adresse nicht frei ist (Block 47), werden die Einheitstabellen gescannt bzw. abgefragt, um eine freie Adresse in den Einheitszuordnungstabellen aufzufinden, Block 50. Diese neue logische Adresse wird in einer physikalischen Adresse verzeichnet bzw. abgebildet, Block 51, und die Daten werden in diese physikalische Adresse (ein-)geschrieben, Block 52. Die Einheitszuordnungstabellen werden aktualisiert (Block 53), um anzuzeigen, daß der ursprüngliche Block gelöscht und nicht beschreibbar ist und daß der neue Block zugeordnet ist und Benutzerdaten enthält. Das virtuelle-zu-logische Adressenverzeichnis wird dann aktualisiert, um auf die neue physikalische Adresse der Daten, die mit der ursprünglichen virtuellen Adresse übereinstimmt, hinzuweisen, Blöcke 54 und 55.
• Um die Lese- und Schreibvorgänge ohne Beschränkung fortsetzen zu können, wird der physikalische Speicherraum periodisch zurückgewonnen bzw. regeneriert. Wie zuvor erklärt ist, wird wenigstens eine Einheit des Speichers immer reserviert, so daß sie gänzlich aus freien Blöcken besteht und als eine ÜBERTRAGUNGSEINHEIT dient.
• Nun auf die Fig. 7 Bezug nehmend wird eine aktive Einheit ausgewählt (hier EINHEIT #M) und werden sämtliche dieser gegenwärtig verzeichneten bzw. abgebildeten aktiven Blöcke gelesen und dann in die ÜBERTRAGUNGSEINHEIT geschrieben. Die ausgewählte Einheit #M wird dann blockweise gelöscht bzw. blockgelöscht und wird die ÜBERTRAGUNGSEINHEIT, während die Übertragungseinheit, in welche die aktiven Blöcke geschrieben worden sind, bei diesem Beispiel die Einheit #M wird. Die Fig. 7 zeigt den Status der Einheiten vor und nach einem Übertragungsvorgang bzw. Übersetzungsvorgang. Die Fig. 8 ist ein Flußdiagramm dieses Übertragungsvorgan ges bzw. Übersetzungsvorganges. Bei einem Übertragungsvorgang wird eine Einheit für die Übertragung bzw. Übersetzung ausgewählt, Block 60, und werden die aktiven Datenblöcke in der ausgewählten Einheit gelesen, Block 61. Diese aktiven Datenblöcke werden dann in die Übertragungseinheit an Positionen in der Übertragungseinheit entsprechend den Positionen, an welchen sie in der ursprünglichen Einheit angeordnet waren, geschrieben, Block 62. Die ausgewählte ursprüngliche Einheit wird dann blitzartig gelöscht, Block 63, und das logische-zu-physikalische Adressenverzeichnis wird geändert, so daß die ausgewählte Einheit die Übertragungseinheit wird und die Übertragungseinheit der Einheitszahl der ausgewählten Einheit zugeordnet wird, Block 64.
• Das so weit beschriebene System benötigt ein virtuelles Verzeichnis, dessen Inhalte frei aktualisiert sind, und ein solches Verzeichnis kann in einem herkömmlichen Direktzugriffsspeicher gespeichert werden. Allerdings unter der Voraussetzung zum Beispiel einer Blockgröße von 512 Byte, da das virtuelle Verzeichnis einen Eingang für jeden Block beinhaltet und jeder Eingang zum Beispiel 4 Byte lang ist (d. h. geeignet zum Adressieren bis zu 4 Gigabyte eines Speichers), würde ein Flash-Speicher von 80 MByte einen Speicher von 640 kByte erfordern, um die Verzeichnistabellen zu speichern. Um den zum Speichern des virtuellen Verzeichnisses erforderlichen Platz des Direktzugriffsspeichers zu beschränken, wird bei einer bevorzugten Ausführungsform der Erfindung ein Großteil der Verzeichnisdaten in dem Flash-Speicher 12 selbst gespeichert und wird ein sekundäres virtuelles Verzeichnis, das virtuelle Adressen aus dem Computer in dem primären virtuellen Verzeichnis verzeichnet bzw. abbildet, in einen Direktzugriffsspeicher, wie dem Speicher 16, gespeichert. Ein hier zu betrachtender wesentlicher Gesichtspunkt besteht darin, daß die sekundäre virtuelle Verzeichnisanordnung den Vorgang zum Lesen und Schreiben des virtuellen Verzeichnisses zu den früher beschriebenen Verfahren zum Lesen und Schreiben gewöhnlicher Daten identisch ist. Das virtuelle Verzeichnis selbst wird in einer zu den Benutzerdaten in der vorhergehenden Beschreibung äquivalenten Weise behandelt und das in dem Direktzugriffsspeicher gespeicherte virtuelle Verzeichnis (das heißt, daß das sekundäre virtuelle Verzeichnis) ist zu dem virtuellen Verzeichnis in der vorhergehenden Beschreibung äquivalent.
• Bei dieser Ausführungsform befindet sich das virtuelle Verzeichnis in dem Flash-Speicher 12 an negativen virtuellen Adressen; ein gewöhnlicher Raum beginnt bei einer virtuellen Adresse Null. Das virtuelle Verzeichnis verzeichnet bzw. bildet die selbst verwendete negative Adresse ab, so daß das sich in einen Flash-Speicher befindliche virtuelle Verzeichnis wie gewöhnliche Benutzerdaten gelesen und geschrieben werden kann und sich nur der Teil des virtuellen Verzeichnisses, das selbst verzeichnet bzw. abbildet (d. h. das sekundäre virtuelle Verzeichnis) in dem Direktzugriffsspeicher befindet.
• Bei einem vereinfachten Beispiel wird ein virtuelles Verzeichnis von 6000 Byte angenommen, die in zwölf virtuellen Verzeichnisblöcken, jeweils zu 512 Byte, gespeichert sind. Es wird eine Vier-Byte-Adresse angenommen, wobei jeder Verzeichnisblock 128 physikalische Adressen speichern kann. Jeder Block enthält daher die Adressen von 64 kByte eines virtuellen Flash-Speichers. Jeder Block von virtuellen Flash-Speicheradressen wird als eine Seite betrachtet und der Direktzugriffsspeicher speichert die Seitenadressen (bei diesem Beispiel nur 48 Byte), die in bzw. zu Adressenblöcken verzeichnet bzw. abgebildet sind. Beim Lesen von Daten aus einer vorgegebenen virtuellen Adresse wird die Adresse durch die Seitengröße (64 kByte) geteilt, um eine Seitenzahl in dem sekundären virtuellen Verzeichnis zu erhalten, welches in den bzw. zu dem Seitenblock des primären virtuellen Verzeichnisses, in welchem die Adresse gespeichert ist, verzeichnet bzw. abbildet. Mit dem virtuel len Speicherseitenblock kann das Verfahren zum Verzeichnen bzw. Abbilden in einer spezifischen physikalischen Adresse eines Flash-Speichers in der bereits beschriebenen Weise fortfahren. Nachdem die virtuelle Adresse durch die Seitengröße geteilt ist, kann zum Beispiel der Rest durch die virtuelle Speicherblockgröße (z. B. 512) geteilt werden, um einen Index zu dem aus dem Flash-Speicher gelesenen Adressenfeld zu erhalten.
• Beim Schreiben von Daten in einer vorgegebenen virtuellen Adresse wird die computererzeugte Adresse ebenso durch die Seitengröße geteilt, um einen Index zu dem sekundären virtuellen Verzeichnis in dem Direktzugriffsspeicher zu erhalten. Das sekundäre virtuelle Verzeichnis verzeichnet bzw. bildet in bzw. zu einem primären virtuellen Verzeichnis ab, in welchem der primäre virtuelle Verzeichnisblock (ein-)gelesen ist; und dies wird ausgenutzt, um in dem physikalischen Block, der adressiert worden ist, zu verzeichnen bzw. abzubilden, in welchem es (ein-)gelesen ist. Da dieser Block nicht wieder beschrieben werden kann, wird ein unbeschriebener Block identifiziert und in der zuvor beschriebenen Weise mit dem als gelöscht markierten ursprünglichen Datenblock beschrieben. Um das virtuelle Verzeichnis, das sich in dem Flash-Speicher befindet, zu aktualisieren, wird im wesentlichen der gleiche Vorgang durchgeführt. Der virtuelle Verzeichnisblock wird in seiner modifizierten Form, um den neuen physikalischen Platz der Adressendaten zu reflektieren, in einen unbeschriebenen Block in dem Flash- Speicher geschrieben und der alte Block wird als gelöscht markiert. Der sekundäre virtuelle Speicher in dem Direktzugriffsspeicher wird, wenn notwendig, geändert, um die Änderung in den primären virtuellen Speicherblockplätzen wiederzugeben bzw. zu reflektieren.
• Die Fig. 9 ist ein Flußdiagramm dieses Vorganges. Der erste Schritt bei diesem Verfahren besteht darin, eine virtuelle Adresse in eine Seitenzahl umzuwandeln bzw. zu konvertie ren, Block 70, und die Seitenzahl zu verwenden, um die Adresse in dem RAM 16 in dem Flash-Speicher 12 des einschlägigen bzw. relevanten Seitenblockes des virtuellen Verzeichnisses, die in dem Flash-Speicher gespeichert ist, aufzufinden bzw. zu lokalisieren, Block 21. Der Seitenblock des virtuellen Verzeichnisses an dieser Adresse wird aus dem Flash-Speicher gelesen (Block 72) und in der zuvor beschriebenen Weise verwendet, um eine zu der virtuellen Adresse korrespondierende physikalische Adresse für einen Datenlese- oder Datenschreibvorgang aufzufinden bzw. zu lokalisieren. Bei einem Datenschreibvorgang muß der Seitenblock des virtuellen Verzeichnisses aktualisiert werden, Block 73, und wird der aktualisierte Seitenblock des virtuellen Verzeichnisses in einen freien physikalischen Adreßplatz des Flash-Speichers geschrieben, Block 74. Die ursprüngliche Flash-Speicheradresse, an welcher der Seitenblock des virtuellen Verzeichnisses angeordnet war, wird als gelöscht markiert, Block 75, und der RAM-Speicher 16 wird aktualisiert, um auf die virtuelle-zu-physikalische Verzeichnisadresse für das aktualisierte Verzeichnis hinzuweisen, Block 76.
• Das virtuelle Verzeichnis kann nach Starten des Systems einfach wiederhergestellt werden. Das virtuelle Verzeichnis, das sich in dem Flash-Speicher befindet, ist nicht flüchtig und bedarf keiner Wiederherstellung. Das sekundäre virtuelle Verzeichnis, das sich in dem flüchtigen Direktzugriffsspeicher befindet, kann durch Scannen bzw. Abfragen des Blockverwendungsverzeichnisses, das sich an dem oberen Ende jeder Einheit befindet, beim Start wiederhergestellt werden. Die als in einer virtuellen Adresse verzeichnet bzw. abgebildet markierten Blöcke werden identifiziert und das sekundäre virtuelle Verzeichnis dementsprechend hergestellt.

Claims (6)

1. Speicherverwaltungsverfahren für einen Speicher (12), in welchen Daten nur in unbeschriebene physikalische Speicherplätze geschrieben werden können und in welchen eine Zone von benachbarten Speicherplätzen gleichzeitig gelöscht werden können, umfassend die Schritte:

Organisieren der Daten in dem Speicher (12) in eine Vielzahl von Einheiten, wobei jede der Einheiten wenigstens eine Zone einschließt,

Organisieren jeder Einheit in eine integrale Anzahl von adressierbaren Blöcken, wobei jeder Block eine Vielzahl von benachbarten physikalischen Speicherplätzen umfaßt, Errichten eines Blockzuordnungsverzeichnisses (25) für jede Einheit, welches den Zustand jedes Blockes in einer Einheit als entweder beschrieben oder unbeschrieben oder gelöscht anzeigt,

Errichten eines virtuellen Verzeichnisses (31), um virtuelle Blockadressen in physikalischen Blockadressen innerhalb einer Einheit zu verzeichnen,

Schreiben von Daten in den Speicher (12) an einer virtuellen Adresse (29):

(a) Verzeichnen der virtuellen Adresse (29) in einer physikalischen Blockadresse in einer Einheit,

(b) Untersuchen des Blockzuordnungsverzeichnisses (25) für die Einheit, in welche die virtuelle Adresse (29) in Unterabschnitt (a) verzeichnet worden ist, um zu bestimmen, ob der Zustand eines Blockes an einer physikalischen Blockadresse beschrieben oder unbeschrieben oder gelöscht ist,

(c) wenn sich der Block an der physikalischen Blockadresse in beschriebenem Zustand befindet:

(1) Untersuchen des Blockzuordnungsverzeichnisses (25) von wenigstens einer anderen der Einheiten, um eine unbeschriebene Blockadresse zu identifizieren,

(2) Schreiben der Daten in den Speicher (12) zu der unbeschriebenen Blockadresse,

(3) Ändern des Blockzuordnungsverzeichnisses (25) für einen Block in der Einheit, in welchem die virtuelle Adresse (29) in Schritt (a) verzeichnet worden ist, um sie als gelöschte physikalische Blockadresse anzuzeigen,

(4) Ändern des Blockzuordnungsverzeichnisses (25) für einen Block in der Einheit, in welche die Daten in Schritt (c) (2) geschrieben worden sind, um sie als geschriebene, zuvor unbeschriebene Blockadresse, an welcher die Daten geschrieben worden sind, anzuzeigen,

(5) Ändern des virtuellen Verzeichnisses (31), um virtuelle Adressen (29) in physikalische Adressen (37) in einer Einheit zu verzeichnen, derart, daß das virtuelle Verzeichnis (31) die virtuelle Adresse (29) in die physikalische Adresse (37) des zuvor unbeschriebenen Blockes, in welchen die Daten in Schritt (c) (2) geschrieben worden sind, zu verzeichnen, derart, daß die virtuelle Adresse nicht in der physikalischen Adresse (37) des geschriebenen Blockes des Schrittes (c) verzeichnet wird.

2. Speicherverwaltungsverfahren nach Anspruch 1, umfassend die Schritte:

Speichern eines ersten virtuellen Verzeichnisses in dem Speicher (12), das virtuelle Adressen (29) in physikalische Adressen (37) in einer Einheit abbildet,

Organisieren des in dem Speicher (12) gespeicherten ersten virtuellen Verzeichnisses in Segmente von seitenadressierbaren Blöcken,

Speichern eines zweiten virtuellen Verzeichnisses in einem Direktzugriffsspeicher (16), das Seitenadressen in physikalische Adressen der seitenadressierbaren Blöcke in dem Speicher (12) abbildet,

Ändern eines seitenadressierbaren Blockes in dem ersten virtuellen Verzeichnis, das in dem Speicher (12) gespeichert ist, durch Schreiben eines geänderten seitenadressierbaren Blockes in eine unbeschriebene physikalische Blockzuordnung, und

Aktualisieren des zweiten virtuellen Verzeichnisses, das in dem Direktzugriffsspeicher (16) gespeichert ist, derart, daß es die Seitenadresse des geänderten seitenadressierbaren Blockes in der unbeschriebenen physikalischen Blockzuordnung, in welche der geänderte seitenadressierbare Block geschrieben worden ist, verzeichnet.

3. Speicherverwaltungsverfahren nach Anspruch 2, umfassend die Schritte:

Einschreiben von Daten in den Speicher (12) an einer virtuellen Adresse (29) durch:

(a) Ableiten einer Seitenadresse aus einer virtuellen Adresse (29),

(b) Verzeichnen der Seitenadresse in einem seitenadressierbaren Block in dem Speicher (12),

(c) Lesen eines Segmentes des ersten virtuellen Verzeichnisses, das eine virtuelle Adresse (29) in einer physikalischen Adresse (37) verzeichnet,

(d) Verzeichnen der virtuellen Adresse (29) in einer physikalischen Adresse (37),

(e) wenn sich der Block an der physikalischen Blockadresse in einem geschriebenen oder gelöschten Zustand befindet:

(1) Schreiben der Daten in den Speicher (12) an einer unbeschriebenen Blockadresse,

(2) Ändern des ersten virtuellen Verzeichnissegmentes, derart, daß das erste virtuelle Verzeichnis die virtuelle Adresse (29) in der physikalischen Adres se (37) des unbeschriebenen Blockes, in welchem die Daten in Schritt (e) (1) geschrieben worden sind, verzeichnet,

(3) Schreiben des geänderten ersten virtuellen Verzeichnissegments aus Schritt (e) (2) in einen unbeschriebenen physikalischen Blockplatz in dem Speicher (12),

(4) Aktualisieren der in dem Direktzugriffsspeicher (16) gespeicherten zweiten Tabelle, derart, daß sie die Seitenadresse des geänderten ersten virtuellen Verzeichnissegmentes des unbeschriebenen physikalischen Blockplatzes verzeichnet.

4. Speicherverwaltungsverfahren nach einem der Ansprüche 1 bis 3, bei welchem das Verzeichnen der virtuellen Adresse (29) in einer physikalischen Adresse (37) eine Zwei-Schritt- Adressenübersetzung umfaßt:

Übersetzen der virtuellen Adresse (29) in eine logische Einheitsadresse (33) durch das virtuelle Verzeichnis (31), und

Übersetzen der logischen Adresse (33) in die physikalische Adresse (37) durch eine logische Einheitstabelle (35).

5. Speicherverwaltungsverfahren nach einem der Ansprüche 1 bis 4, umfassend:

Einlesen von Daten in den Speicher an einer virtuellen Adresse:

(a) Verzeichnen der virtuellen Adresse (29) in einer physikalischen Blockadresse in einer Einheit,

(b) Lesen der Daten aus dem Speicher (12) an der physikalischen Adresse (37).

6. Speicherverwaltungsverfahren nach einem der Ansprüche 1 bis 5, umfassend die weiteren Schritte:

Errichten einer Übertragungseinheit in dem Speicher (12), in welchem sämtliche Blöcke der Einheit unbeschrieben sind, wobei die Übertragungseinheit ein Übertragungseinheitsblockzuordnungsverzeichnis beinhaltet,

periodisches Identifizieren einer zu löschenden, zu der Übertragungseinheit unterschiedlichen ausgewählten Einheit, Lesen jedes geschriebenen Blockes in die ausgewählte Einheit,

Schreiben jedes geschriebenen Blockes in der ausgewählten Einheit in die Übertragungseinheit,

Aktualisieren des Übertragungseinheitszuordnungsverzeichnisses (25), um den Zustand der Blöcke, die in dem gerade vorhergehenden Schritt zum Schreiben geschrieben worden sind, als geschrieben anzuzeigen,

Löschen der ausgewählten Einheit,

Aktualisieren des virtuellen Verzeichnisses der virtuellen Adressen (29) in physikalische Adressen (37), um die Bewegung der geschriebene Blöcke zu reflektieren.