-
Die Erfindung betrifft das technische
Gebiet der Speicherverwaltung und spezieller das Gebiet der Speicherdefragmentierung.
Die Erfindung ist besonders zum Einsatz bei tragbaren Datenträgern geeignet.
Solche tragbare Datenträger
können
beispielsweise Chipkarten (smart cards) in unterschiedlichen Bauformen
oder Chipmodule sein. Die Erfindung kann jedoch auch zur Defragmentierung
eines nicht-flüchtigen
beschreibbaren Halbleiterspeichers bei anderen ressourcenbeschränkten Systemen
eingesetzt werden.
-
Tragbare Datenträger weisen in gegenwärtig üblichen
Ausgestaltungen einen Mikrocontroller mit einem Prozessorkern und
mehreren unterschiedlichen Speicherfeldern auf. In der Regel ist
zumindest eines dieser Speicherfelder als nicht-flüchtiger
beschreibbarer Halbleiterspeicher, zum Beispiel als EEPROM oder
als Flash-Speicher, ausgebildet. Dieses Speicherfeld kann beispielsweise
zur Aufnahme eines Dateisystems gemäß der Norm ISO/IEC 7816-4 oder
zum Speichern von Objekten und Datenfeldern (arrays) in einer Java
CardTM-Laufzeitumgebung dienen.
-
Kapitel 5.7 des Buches "Handbuch der Chipkarten" von Wolfgang Rankl
und Wolfgang Effing, 3. Auflage, Hanser-Verlag 1999, Seiten 242–248, gibt einen Überblick über die
Dateiverwaltung bei Chipkarten. Im Abschnitt "Freispeicherverwaltung" auf Seite 246 wird
als Kompromiß zwischen
Funktionalität,
Programmgröße und Zuverlässigkeit
ein Speicherverwaltungssystem vorgeschlagen, welches das Löschen von
Dateien erlaubt, aber keine Verschiebung (Relokation) bestehender
Dateien vorsieht. Der durch das Löschen einer Datei freigewordene
Speicher steht nur bis zur Größe der gelöschten Datei wieder
für eine
neue Datei zur Verfügung.
Ist die neue Datei kleiner als die gelöschte Datei, so entsteht Speicherverschnitt,
der für
die Dateiverwaltung endgültig
verloren ist.
-
Im Zuge der ständig zunehmenden Leistungsfähigkeit
von Chipkarten und anderen ressourcenbeschränkten Systemen stellt jedoch
eine Einschränkung
wie die gerade genannte einen erheblichen Wettbewerbsnachteil dar.
Es besteht daher Bedarf an tragbaren Datenträgern, die ein leistungsfähiges Speicherverwaltungssystem
aufweisen. Dies umfaßt
insbesondere die Fähigkeit
zur Speicherdefragmentierung. Bei der Defragmentierung werden belegte
Speicherbereiche verschoben, um "Löcher" im Speicher, also
einzelne freie Speicherbereiche zwischen den belegten Speicherbereichen,
zusammenzufassen. Dies vergrößert den
größten zusammenhängenden
freien Speicherbereich, der dann zur Anlage entsprechend großer neuer
Dateien verwendet werden kann.
-
Techniken zur Defragmentierung von Speicherbereichen
sind zur Verwendung bei üblichen Computern,
beispielsweise PCs, gut bekannt. Der Einsatz solcher Techniken bei
tragbaren Datenträgern
ist jedoch mit Schwierigkeiten verbunden, weil bei tragbaren Datenträgern jederzeit
mit einem plötzlichen
Ausfall der Versorgungsspannung gerechnet werden muß, beispielsweise
aufgrund einer ungewollten Fehlbedienung oder sogar eines gezielten Manipulationsversuchs.
Auch bei einem solchen plötzlichen
Spannungsausfall oder einer sonstigen Störung muß die Datenintegrität – unabhängig vom Zeitpunkt
der Störung – absolut
gewährleistet
sein. Dies gilt insbesondere deshalb, weil tragbare Datenträger häufig für sicherheitskritische
Anwendungen oder im Zusammenhang mit Finanztransaktionen eingesetzt
werden.
-
EP 1 046 996 A1 zeigt ein Verfahren zur Speicherdefragmentierung
bei Chipkarten, bei dem Daten in Paketen (chunks) einer fest vorgegebenen Größe von einem
Quellbereich in einen unterbrechungssicheren Zwischenpuffer und
von dort in einen Zielbereich kopiert werden. Die Paketgröße entspricht
der Seitengröße eines
EEPROM der Chipkarte und kann beispielsweise 32 Byte oder 64 Byte
betragen. Der Zwischenpuffer wird eingesetzt, um – in Verbindung
mit zwei alternierend verwendeten Verwaltungsdatensätzen – die Datenintegrität bei unerwarteten
Unterbrechungen des Verfahrensablaufs sicherzustellen. Dieses Verfahren
ist jedoch in der Praxis relativ langsam, da erstens die Verwendung
des im EEPROM befindlichen Zwischenpuffers zusätzliche Schreibvorgänge bedingt
und da zweitens viele weitere Verwaltungsdaten in das EEPROM geschrieben
werden müssen.
-
Die Erfindung hat demgemäß die Aufgabe, die
genannten Probleme ganz oder zum Teil zu lösen. Insbesondere soll durch
die Erfindung eine Technik zur Speicherdefragmentierung für tragbare Datenträger und
andere ressourcenbeschränkte Systeme
bereitgestellt werden, die einerseits die Datenintegrität auch bei
unvorhergesehenen Unterbrechungen gewährleistet und andererseits
zumindest unter praxistypischen Anwendungsbedingungen eine hohe
Leistung aufweist.
-
Erfindungsgemäß wird diese Aufgabe ganz oder
zum Teil gelöst
durch ein Verfahren zur Speicherdefragmentierung mit den Merkmalen
des Anspruchs 1, ein Computerprogrammprodukt gemäß Anspruch 10 und einen tragbaren
Datenträger
gemäß Anspruch
11. Die abhängigen
Ansprüche
definieren bevorzugte Ausgestaltungen der Erfindung. Die Aufzählungsreihenfolge
der Verfahrensschritte in den Ansprüchen soll nicht als Einschränkung des Schutzbereichs
aufgefaßt
werden; es sind vielmehr Ausgestaltungen der Erfindung vorgesehen,
bei denen diese Verfahrensschritte ganz oder teilweise in anderer
Reihenfolge oder ganz oder teilweise parallel oder ganz oder teilweise
ineinander verzahnt (interleaved) ausgeführt werden.
-
Eine der Erfindung zugrundeliegende Überlegung
ist es, die Blockgröße, mit
der die Daten vom Quellbereich in den Zielbereich verschoben werden, variabel
zu gestalten. Es ist vorgesehen, diese Blockgröße bei jedem Verschiebevorgang
so festzulegen, daß die
Blockgröße höchstens
so groß wie
der Versatz zwischen dem Quellbereich und dem Zielbereich – und vorzugsweise
genau so groß wie
dieser Versatz – ist.
Auf diese Weise kann auch bei sich überlappenden Quell- und Zielbereichen
zuverlässig vermieden
werden, daß Daten
im Quellbereich, die nach einer plötzlichen Verfahrensunterbrechung möglicherweise
noch benötigt
werden, durch einen in den Zielbereich eingeschriebenen Datenblock überschrieben
werden. Die Erfindung schafft damit die technischen Grundlagen,
um einen unterbrechungssicheren Zwischenpuffer und die dadurch bedingten, zeitaufwendigen
Schreibvorgänge überflüssig zu
machen.
-
Das erfindungsgemäße Kopierverfahren ist unter
praxistypischen Einsatzbedingungen äußerst effizient, da meist eine
beträchtliche
Blockgröße gewählt werden
kann und daher nur wenige Schreibvorgänge im Verwaltungsdatenbereich
erforderlich sind. Dieser Effekt wird noch verstärkt, wenn im Laufe des Defragmentierungsvorgangs
mehrere "Löcher" zusammenfallen und
damit der Versatz zwischen den Quell- und Zielbereichen immer weiter
zunimmt. Wenn dagegen der Versatz zwischen dem Quell- und dem Zielbereich – also die
Größe des zu
schließenden "Loches" – sehr klein ist, leidet die
Effizienz des hier vorgeschlagenen Verfahrens. Dieser Fall kommt jedoch
in der Praxis nur selten vor. Ferner kann gerade bei großen Blockgrößen bei
einem Wiederanlaufvorgang nach einer Spannungsunterbrechung relativ viel
zusätzliche
Kopierarbeit anfallen. Auch dieser theoretisch denkbare Fall stellt
jedoch für
die Praxis keinen ins Gewicht fallenden Nachteil dar.
-
Die Erfindung ist zur Verwaltung
eines nicht-flüchtigen
beschreibbaren Speichers von tragbaren Datenträgern und sonstigen ressourcenbeschränkten Systemen
(z.B. sogenannten eingebetteten Systemen) geeignet, insbesondere
dann, wenn hohe Anforderungen an die Betriebssicherheit und Datenintegrität auch bei
ungünstigen
Einsatzbedingungen gestellt werden. Besonders eignet sich die Erfindung
zur Defragmentierung eines Dateisystems, z.B. eines Dateisystems
gemäß ISO/IEC
7816-4, oder sonstiger Datenstrukturen im nicht-flüchtigen beschreibbaren
Speicher. Die Datenstrukturen können
insbesondere dynamisch verwaltete Objekte und Datenfelder (arrays)
sein, die im Rahmen einer Speicherbereinigung (garbage collection)
einer Defragmentierung unterzogen werden. Eine derartige Speicherbereinigung
ist z.B. gemäß Version
2.2 der Java CardTM-Spezifikation optional
vorgesehen.
-
Erfindungsgemäß wird die erfolgreiche Übertragung
jedes Datenblocks vom Quellbereich in den Zielbereich in einem Verwaltungsdatenbereich
unterbrechungssicher vermerkt. Dies kann beispielsweise dadurch
erfolgen, daß der
Verwaltungsdatenbereich zwei Blockzähler aufweist, die nach der
erfolgreichen Übertragung
jedes Datenblocks weitergeschaltet werden. Hierbei ist unter dem
Begriff "weiterschalten" je nach Ausgestaltung
des Verfahrens entweder eine Inkrementierung oder eine Dekrementierung
zu verstehen. Der Verwaltungsdatenbereich ist vorzugsweise im nicht-flüchtigen
beschreibbaren Speicher angelegt. In bevorzugten Ausführungsformen
werden im Verwaltungsdatenbereich weitere für den Defragmentierungsvorgang
wichtige Daten abgelegt, beispielsweise Daten über die Größe und Position des Quellbereichs
und/oder des Zielbereichs.
-
Zur Effizienzsteigerung ist vorzugsweise
vorgesehen, jeden Datenblock unmittelbar – also zumindest ohne Zwischenschaltung
eines unterbrechungsgesicherten Zwischenpuffers – vom Quellbereich in den Zielbereich
zu kopieren. Die Datenintegrität
nach einer z.B. durch einen Spannungsausfall hervorgerufenen Verfahrensunterbrechung
wird vorzugsweise dadurch sichergestellt, daß nach dem folgenden Neustart
die Datenübertragung
vom Quellbereich in den Zielbereich bei dem in der Verarbeitungsreihenfolge
ersten Datenblock fortgesetzt wird, dessen erfolgreiche Übertragung
noch nicht in dem Verwaltungsdatenbereich vermerkt worden ist.
-
In unterschiedlichen Ausgestaltungen
kann die Speicherdefragmentierung automatisch oder durch expliziten
Aufruf einer entsprechenden Betriebssystemfunktion angestoßen werden.
Die Speicherdefragmentierung kann einen einzigen oder mehrere Verschiebevorgänge aufweisen,
bei denen vorzugsweise jeweils ein "Speicherloch" geschlossen wird.
-
Vorzugsweise ist der nicht-flüchtige beschreibbare
Speicher ein Halbleiterspeicher, der als EEPROM (electrically eraseable
programmable read only memory) oder als FLASH-Speicher oder als FRAM
(ferroelectric random access memory) oder in einer anderen Technologie
ausgestaltet sein kann. Die Dauer eines Schreibzugriffs auf diesen
Speicher ist in der Regel deutlich höher als die Dauer eines Lesezugriffs
und/oder als die Dauer eines Schreibzugriffs auf einen flüchtigen
Halbleiterspeicher des Datenträgers.
-
Das erfindungsgemäße Computerprogrammprodukt
weist Programmbefehle auf, um das erfindungsgemäße Verfahren zu implementieren.
Ein derartiges Computerprogrammprodukt kann ein körperliches
Medium sein, beispielsweise ein Halbleiterspeicher oder eine Diskette
oder eine CD-ROM, auf dem ein Programm zur Ausführung eines erfindungsgemäßen Verfahrens
gespeichert ist. Das Computerprogrammprodukt kann jedoch auch ein
nicht-körperliches
Medium sein, beispielsweise ein über
ein Computernetzwerk übermitteltes
Signal. Das Computerprogrammprodukt kann insbeson dere zur Verwendung
im Zusammenhang mit der Herstellung und/oder Initialisierung und/oder
Personalisierung von Chipkarten oder sonstigen Datenträgern oder sonstigen
ressourcenbeschränkten
Systemen vorgesehen sein.
-
In bevorzugten Ausgestaltungen sind
das Computerprogrammprodukt und/oder der tragbare Datenträger mit
Merkmalen weitergebildet, die den hier beschriebenen und/oder den
in den abhängigen Verfahrensansprüchen genannten
Merkmalen entsprechen.
-
Weitere Merkmale, Vorteile und Aufgaben der
Erfindung gehen aus der folgenden genauen Beschreibung eines Ausführungsbeispiels
der Erfindung und mehrerer Ausführungsalternativen
hervor. Es wird auf die Zeichnungen verwiesen, in denen zeigen:
-
1 eine
schematische Darstellung eines Datenträgers in einem Ausführungsbeispiel
der Erfindung,
-
2 eine
Darstellung mehrerer Bereiche des nicht-flüchtigen beschreibbaren Speichers
bei dem Datenträger
von 1, und
-
3A und 3B ein beispielhaftes Flußdiagramm
eines von dem Datenträger
von 1 ausgeführten Defragmentierungsverfahrens.
-
Der in 1 dargestellte
Datenträger 10 weist
auf einem einzigen Halbleiterchip einen Prozessorkern 12,
mehrere in unterschiedlichen Technologien ausgestaltete Speicherfelder
und eine Schnittstellenschaltung 14 zur kontaktlosen oder
kontaktgebundenen Kommunikation auf. Im vorliegenden Ausführungsbeispiel
sind als Speicherfelder ein beschreibbares RAM 16, ein maskenprogrammiertes ROM 18 und
ein elektrisch lösch-
und programmierbares EEPROM 20 vorgesehen. Schreibzugriffe
auf das EEPROM 20 sind relativ aufwendig und benötigen z.B.
die dreißigfache
Zeit eines Lesezugriffs auf das EEPROM 20 oder eines Schreibzugriffs
auf das RAM 16.
-
Im ROM 18 – und zum
Teil auch im EEPROM 20 – ist ein Betriebssystem 22 enthalten,
das eine Vielzahl von Funktionen und Diensten bereitstellt. Unter
anderem verwaltet das Betriebssystem 22 ein Dateisystem 24,
das im vorliegenden Beispiel gemäß der Norm
ISO/IEC 7816-4 ausgestaltet ist. Die Dateien des Dateisystems 24 sind
in einem im EEPROM 20 angelegten, dynamisch verwalteten
Dateibereich 26 gespeichert. Ein ebenfalls im EEPROM 20 befindlicher
Verzeichnisdatenbereich 28 enthält Verzeichnisinformationen,
die den Inhalt des Dateibereichs 26 betreffen. Ferner ist
im EEPROM 20 ein Verwaltungsdatenbereich 30 vorgesehen,
auf dessen Funktion unten noch genauer eingegangen werden wird.
-
2 zeigt
eine beispielhafte Belegung des Dateibereichs 26 mit drei
belegten Speicherbereichen UM1, UM2, UM3, die je einer Datei im
Dateisystem 24 (1)
entsprechen. Zwischen den belegten Speicherbereichen UM1, UM2, UM3
befinden sich freie Speicherbereiche FM1, FM2, die beispielsweise durch
das Löschen
von Dateien entstanden sind.
-
Der Verzeichnisdatenbereich 28 weist
für jeden
belegten Speicherbereich UM1, UM2, UM3 einen Verzeichnisdatensatz
MM1, MM2, MM3 auf, welcher zumindest die Startadresse des Speicherbereichs
UM1, UM2, UM3 enthält.
Weitere Informationen über
den jeweiligen Speicherbereich UM1, UM2, UM3 – beispielsweise dessen Größe und Organisation
sowie der Dateiname – können in
unterschiedlichen Ausführungsformen
im Verzeichnisdatensatz MM1, MM2, MM3 und/oder im Speicherbereich
UMl, UM2, UM3 enthalten sein. Die in 2 links
vom Dateibereich 26 gezeigte Zahlenspalte stellt symbolisch Speicheradressen – ausgedrückt z.B.
in Bytes oder Speicherseiten – relativ
zum Beginn des Dateibereichs 26 dar.
-
Das Betriebssystem 22 (1) bietet ein leistungsfähiges Speicherverwaltungssystem,
das Funktionen zum Anlegen und Löschen
von Dateien aufweist. Ein wesentlicher Aspekt des Speicherverwaltungssystems
im vorliegenden Ausführungsbeispiel
ist es, daß der
durch das Löschen
von Dateien freigegebene Speicherplatz wieder uneingeschränkt für neue Dateien
zur Verfügung
gestellt wird. Bei der beispielhaften Speicherbelegung nach 2 ist dies nicht unmittelbar
gewährleistet,
weil eine neu anzulegende Datei, die einen zusammenhängenden
Abschnitt im Dateibereich26 benötigt,
höchstens
so groß wie
der größte einzelne
freie Speicherbereich – hier
FM1 – werden
könnte,
obwohl insgesamt mehr freier Speicher zur Verfügung steht. Das Betriebssystem 22 ist
deshalb dazu eingerichtet, im Zuge der dynamischen Speicherverwaltung
eine Defragmentierung des Dateibereichs 26 durchzuführen.
-
Allgemein werden bei der Defragmentierung belegte
Speicherbereiche UM1, UM2,... im Dateibereich 26 verschoben,
um freie Speicherbereiche FM1, FM2,..., die über den Dateibereich 26 verstreut sind,
zu vereinigen und somit die Größe des zusammenhängenden
freien Speichers im Dateibereich 26, der zum Anlegen neuer
Dateien benötigt
wird, zu steigern.
-
Der Defragmentierungsvorgang kann
in unterschiedlichen Ausführungsvarianten
durch unterschiedliche Mechanismen ausgelöst werden. So kann z.B. im
Zusammenhang mit jedem Löschen
einer Datei stets ein Defragmentierungsvorgang ausgeführt werden.
Es kann auch vorgesehen sein, die Defragmentierung erst in Reaktion
auf das Eintreten einer vorbestimmten Situation zu starten, z.B.
beim Überschreiten
eines vorgegebenen Fragmentierungsgrades oder bei der Bearbeitung
einer Anforderung zum Anlegen einer neuen Datei, für die kein
hinreichend großer
zusammenhängender
Speicherbereich mehr verfügbar
ist. Schließlich
kann auch vorgesehen sein, den Defragmentierungsvorgang nur in Reaktion
auf einen Aufruf eines entsprechenden Betriebssystemdienstes zu
beginnen. Die letztgenannte Ausgestaltung hat den Vorteil, daß der Ausführungszeitpunkt
der relativ zeitaufwendigen Defragmentierung vom Programmierer geeignet
festgelegt werden kann.
-
3A und 3B zeigen das im vorliegenden
Ausführungsbeispiel
eingesetzte Defragmentierungsverfahren. Die folgende Erläuterung
geht von der beispielhaften Speicherbelegung gemäß 2 aus, bei der der zweite belegte Speicherbereich
UM2 in unmittelbaren Anschluß an
den ersten belegten Speicherbereich UM1 verschoben werden soll.
Dadurch vergrößert sich
der ursprüngliche
zweite freie Speicherbereich FM2 um die Größe des ursprünglichen
ersten freien Speicherbereichs FM1. Im Hinblick auf diesen Verschiebevorgang
bildet der zweite belegte Speicherbereich UM2 an seiner anfänglichen Position
an den Adressen 9-16 einen Quellbereich 32, und
die gewünschte
Endposition an den Adressen 6-13 bildet einen Zielbereich 34.
-
Die ersten vier Schritte 50–56 des
Defragmentierungsverfahrens gemäß
-
3A betreffen
die Initialisierung von Einträgen
in dem in 1 und 2 gezeigten Verwaltungsdatenbereich 30.
Zunächst
wird, in Schritt 50, ein Kennungswert F in den Verwaltungsdatenbereich 30 eingetragen,
welcher den laufenden Defragmentierungsvorgang anzeigt. Bei jedem
Neustart des Datenträgers 10 – z.B. infolge
eines plötzlichen
Spannungsausfalls – wird
der Kennungswert F im Verwaltungsdatenbereich 30 überprüft. Wenn
dort eine noch nicht abgeschlossene Defragmentierung vermerkt ist,
muß diese
im Zusammenhang mit dem Neustart korrekt fortgesetzt werden, um
die Datenintegrität des
Dateibereichs 26 zu gewährleisten.
-
In Schritt 52 werden einige Defragmentierungsparameter,
nämlich
ein Zielzeiger DP, eine Blockgröße BS, ein
Quellzeiger SP und eine Gesamtlänge
LEN, in den Verwaltungsdatenbereich 30 eingetragen.
-
Der Zielzeiger DP ist die Startadresse
des Zielbereichs 34, also bei der beispielhaften Speicherbelegung
von 2 die Startadresse
des ersten freien Speicherbereichs FM1. An die durch den Zielzeiger
DP angegebene Adresse werden beim folgenden Verschiebevorgang die
ersten Daten geschrieben.
-
Der Quellzeiger SP ist die Startadresse
des Quellbereichs 32, hier also die erste Adresse des auf das "Speicherloch" folgenden belegten
Speicherbereichs UM2.
-
Die Blockgröße BS bestimmt die maximale Menge
von Daten, welche in einem Teilschritt der Defragmentierung verschoben
werden. Im vorliegenden Ausführungsbeispiel
ist die Blockgröße BS gleich dem
Versatz zwischen dem Quellbereich 32 und dem Zielbereich 34,
also gleich der Differenz zwischen dem Quellzeiger SP und dem Zielzeiger
DP. 2 zeigt die Lage
eines ersten,zweiten und dritten Datenblocks 36, 38, 40 im
Quellbereich 32. Die im Zuge der Defragmentierung ausgeführte Datenübertragung
erfolgt blockweise; die drei Blöcke 36, 38, 40 werden
also einzeln vom Quellbereich 32 in den Zielbereich 34 kopiert.
-
Die Gesamtlänge LEN gibt die Größe des Quell-
und des Zielbereichs 32, 34 und damit die Menge
der insgesamt – meist
in mehreren einzelnen Blöcken 36, 38, 40 – zu übertragenden
Daten an.
-
In Schritt 54 werden die bisher genannten Einträge im Verwaltungsdatenbereich 30 durch
einen Fehlererkennungscode EDC abgesichert. Sobald der Fehlererkennungscode
EDC erfolgreich geschrieben worden ist, wird der durch die Defragmentierungsparameter
angegebene Verschiebevorgang vollständig ausgeführt, und zwar auch dann, wenn
eine Unterbrechung wegen eines Spannungsausfalls und eines anschließenden Neustarts
erfolgt.
-
In Schritt 56 werden zwei Blocknummernzähler BN1
und BN2 im Verwaltungsdatenbereich 30 auf einen Anfangswert
initialisiert. Die Blocknummernzähler
BN1, BN2 geben im vorliegenden Ausführungsbeispiel die Anzahl der
bereits vollständig und
erfolgreich vom Quellbereich 32 in den Zielbereich 34 übertragenen
Datenblöcke 36, 38, 40 an.
Im Initialisierungsschritt 56 wird daher der Wert "0" in beide Blocknummernzähler BN1,
BN2 eingetragen. Durch die Verwendung von zwei Blocknummernzählern BN1,
BN2 kann der Verfahrensfortschritt unterbrechungssicher vermerkt
werden, weil im Falle eines Spannungsausfalls während des Beschreibens des
ersten Blocknummernzählers
BN1 jeweils noch der vorher gültige – und erforderlichenfalls
nach wie vor verwendbare – Zählerstand
aus dem zweiten Blocknummernzähler
BN2 ermittelbar ist.
-
Die Verfahrensschritte 58–66 definieren
eine Programmschleife. In jedem Schleifendurchlauf wird genau ein
Block 36, 38, 40 vom Quellbereich 32 an die
entsprechende Position im Zielbereich 34 übertragen.
Es werden zunächst,
in Schritt 58, eine Quelladresse und eine Zieladresse des ersten
Bytes des im jeweiligen Schleifendurchlauf aktuellen Blocks 36, 38, 40 berechnet.
Beim ersten zu übertragenden Block 36 entsprechen
diese Adressen den im Verwaltungsdatenbereich 30 gespeicherten
Angaben zum Quellzeiger SP und Zielzeiger DP. Bei den weiteren Schleifendurchläufen ergeben
sich die Quelladresse und Zieladresse dann in Abhängigkeit
von der in BN1 und BN2 gespeicherten Anzahl der bereits erfolgreich
kopierten Datenblöcke,
die im folgenden als Blocknummer BN bezeichnet werden soll, durch
die Formeln: Quelladresse = Quellzeiger SP + (Blocknummer BN·Blockgröße BS) Zieladresse
= Zielzeiger DP + (Blocknummer BN·Blockgröße BS)
-
Die so ermittelten Quell- und Zieladressen können im
flüchtigen
RAM 16 oder in einem Register der Prozessorkerns 12 gehalten
werden, weil sie nach einem Spannungsausfall sowieso aufgrund der Daten
im Verwaltungsdatenbereich 30 neu bestimmt werden würden.
-
In Schritt 60 wird ein an der jeweils
gerade berechneten Quelladresse beginnender Block 36, 38, 40 an
den mit der Zieladresse beginnenden Speicherbereich verschoben.
Die Anzahl der zu kopierenden Bytes wird einerseits durch die maximale Blockgröße BS und
andererseits durch das Ende des Quellbereichs 32 begrenzt.
Bei der in 2 gezeigten
Speicherbelegung wird also bei den ersten beiden Schleifendurchläufen – entsprechend
den ersten beiden Blöcken 36, 38 – jeweils
die durch die Blockgröße BS definierte
Byteanzahl kopiert. Beim dritten Schleifendurchlauf – also dem
den dritten Block 40 betreffenden Kopiervorgang – ist das
Produkt der Blockgröße BS und
der Nummer BN+1 des aktuell kopierten Blocks 40 größer als
die Gesamtlänge
LEN des Quellbereichs 32. In diesem Fall werden nur die bis
zur Gesamtlänge
LEN verbleibenden Bytes kopiert; deren Anzahl beträgt: Byteanzahl
= Gesamtlänge
LEN – (Blocknummer
BN·Blockgröße BS)
-
Schritt 60 kann durch eine Programmschleife implementiert
werden, die bei jedem Durchlauf ein Byte von der Quell- zur Zieladresse
kopiert und dann die Quell- und die Zieladresse inkrementiert. Diese Programmschleife
wird für
jedes im aktuellen Block 34, 36, 38 zu
kopierende Byte einmal durchlaufen. In einer Ausführungsvariante
kann die Programmschleife auch zwei Abbruchbedingungen, nämlich erstens
die Überschreitung
der Blockgröße BS und zweitens
das Erreichen des Endes des Quellbereichs 32 aufweisen.
Im vorliegenden Ausführungsbeispiel erfolgt
der Kopiervorgang vom Quellbereich 32 in den Zielbereich 34 unmittelbar,
also ohne Zwischenspeicherung oder allenfalls mit einer nicht gegen
Unterbrechungen gesicherten Zwischenspeicherung im RAM 16 oder
in einem Register des Prozessorkerns 12.
-
Wie bereits erwähnt, wird im vorliegenden Ausführungsbeispiel
bei der Initialisierung in Schritt 52 die Blockgröße BS gleich
dem Versatz zwischen dem Quellbereich 32 und dem Zielbereich 34 gesetzt. Dies
entspricht der maximalen Datenmenge, die bei einem Schleifendurchlauf
in Schritt 60 vom Quellbereich 32 in den Zielbereich 34 kopiert
werden kann, ohne daß sich
die in den Zielbereich 34 eingeschriebenen Daten mit dem
ursprünglichen
Datenblock 36; 38, 40 des Quellbereichs 32 überlappen.
Auf diese Weise wird sichergestellt, daß das Übertragen eines Datenblocks 36, 38, 40 vom
Quellbereich 32 in den Zielbereich 34 den ursprünglichen
Datenblock 36, 38, 40 im Quellbereich 32 unverändert beläßt. Der
ursprüngliche
Datenblock 36, 38, 40 steht daher auch nach
einer möglichen
Unterbrechung des Kopiervorgangs in Schritt 60 unverändert für einen
weiteren Kopierversuch zur Verfügung.
-
Der erfolgreiche Abschluß der Kopierschritts 60
wird nun im Verwaltungsdatenbereich 30 vermerkt, indem
zunächst
in Schritt 62 der erste Blocknummernzähler BN1 und dann in Schritt
64 der zweite Blocknummernzähler
BN2 erhöht
werden. So werden z.B. beim ersten Durchlauf der durch die Schritte 58–66 gebildeten
Schleife nach der erfolgreichen Verschiebung des ersten Blocks 36 die
beiden Blocknummernzähler
BN1 und BN2 jeweils auf den Wert "1" gesetzt.
Der ursprüngliche
Datenblock 36, 38, 40 im Quellbereich 32 wird
nun nicht mehr benötigt;
er kann vielmehr beim nächsten
Schleifendurchlauf überschrieben
werden. Ein solcher weiterer Schleifendurchlauf erfolgt, wenn in
Abfrage 66 festgestellt wird, daß noch ein Datenblock 36, 38, 40 zu
kopieren ist. Dies ist solange der Fall, wie das Produkt aus der Blockgröße BS und
der inkrementierten Blocknummer kleiner als die Gesamtlänge LEN
des Quellbereichs 32 ist.
-
Wenn der letzte Block 40 erfolgreich
kopiert worden ist, wird die Programmausführung mit dem in 3B gezeigten Schritt 68
der Aktualisierung des Verzeichnisdatenbereichs 28 fortgesetzt.
Im vorliegenden Fall wird in den Verzeichnisdatensatz MM2 des verschobenen
Speicherbereichs UM2 die neue Startadresse dieses Speicherbereichs – hier also
der Wert des Zielzeigers DP – eingetragen.
Nun kann in Schritt 70 das Ende der Defragmentierung im Kennungswert
F vermerkt werden. Wenn ab diesem Zeitpunkt eine Spannungsunterbrechung
auftritt, wird bei der in Zusammenhang mit dem folgenden Neustart vorgenommenen Überprüfung des
Kennungswertes F festgestellt, daß keine Fortsetzung eines laufenden Defragmentierungsvorgangs
erforderlich ist.
-
Insgesamt wurde durch den bislang
beschriebenen Verfahrensablauf der ursprüngliche zweite belegte Speicherbereich
UM2 von den Adressen 9-16 an die Adressen 6-13 verschoben.
Dadurch wurde ein zusammenhängender
freier Speicherbereich an den Adressen 14-18 geschaffen.
Wenn dieser Platz ausreicht, wird das Defragmentierungsverfahren
in Schritt 72 beendet. Andernfalls kann durch einen wiederholten
Verschiebevorgang, der erneut bei Schritt 50 beginnt, der ursprüngliche
dritte belegte Speicherbereich UM3 von den Adressen 19-20 an die
Adressen 14-15 verschoben werden. Dadurch würde ab der
Adresse 16 ein noch größerer zusammenhängender
freier Speicherbereich entstehen. In einer Ausführungsalternative kann auch
vorgesehen sein, den Defragmentierungsvorgang immer für den zweiten
und alle folgenden belegten Speicherbereiche UM2, UM3,... im Dateibereich 26 auszuführen.
-
Wie bereits erwähnt, wird bei jedem Neustart des
Datenträgers 10 der
Kennungswert F ausgewertet. Wird dabei ein noch nicht abgeschlossener
Defragmentierungsvorgang festgestellt, so wird dieser bei dem ersten
Datenblock 36, 38, 40 fortgesetzt, dessen
erfolgreiche Übertragung
vom Quellbereich 32 in den Zielbereich 34 noch
nicht in den Blocknummernzählern
BN1, BN2 vermerkt worden ist. Das in 3A und 3B gezeigte Verfahren wird
dazu bei Schritt 58 fortgesetzt. Möglicherweise werden in diesem
Zusammenhang Daten eines Datenblocks 36, 38, 40,
die bereits teilweise vom Quellbereich 32 in den Zielbereich 34 kopiert
worden sind, nochmals übertragen.
Die zusätzliche
Arbeit beläuft
sich im schlechtesten Fall auf das Kopieren eines vollen Datenblocks 36, 38, 40.
Dennoch ist es in der Regel wünschenswert,
die Blockgröße BS möglichst
groß zu
wählen,
weil dadurch bei der regulären
Defragmentierung weniger Schreiboperationen in die Blocknummernzähler BN1,
BN2 des Verwaltungsdatenbereichs 30 anfallen.
-
Es versteht sich, daß das hier
geschilderte Verfahren nicht nur zur Defragmentierung von Dateisystemen
verwendet werden kann, sondern allgemein zur Defragmentierung aller
Arten von dynamisch verwalteten Speicherbereichen. Hierunter sind insbesondere
Speicherbereiche für
Objekte und Datenfelder (arrays) bei Datenträgern und anderen ressourcenbeschränkten Systemen
zu verstehen, welche eine Java CardTM-Laufzeitumgebung
aufweisen.