PatentDe  


Dokumentenidentifikation DE69718543T2 02.10.2003
EP-Veröffentlichungsnummer 0798656
Titel Ebenenkompression mit Löchern in Dateiensystemen
Anmelder Sun Microsystems, Inc., Mountain View, Calif., US
Erfinder Madany, Peter W., Fremont, California 94555, US;
Wong, Thomas K., Pleasanton, California 94566, US;
Nelson, Michael, Danville, California 94526, US
Vertreter HOFFMANN · EITLE, 81925 München
DE-Aktenzeichen 69718543
Vertragsstaaten DE, FR, GB, IT, SE
Sprache des Dokument EN
EP-Anmeldetag 14.03.1997
EP-Aktenzeichen 973017395
EP-Offenlegungsdatum 01.10.1997
EP date of grant 22.01.2003
Veröffentlichungstag im Patentblatt 02.10.2003
IPC-Hauptklasse G06F 17/30

Beschreibung[de]
GEBIET DER ERFINDUNG

Die vorliegende Erfindung betrifft das Gebiet der Datenkompression in einem Berechnungssystem. Insbesondere betrifft die vorliegende Erfindung die Online- Datenkompression auf Dateisystemebene unter Verwendung des Konzepts von Dateien mit "Löchern".

HINTERGRUND DER ERFINDUNG

Viele Computeranwendungen benötigen mehr Online- Datenspeicherplatz, als auf ihren Computerplattenlaufwerken verfügbar ist. Die einfachste Lösung für dieses Problem besteht in der Anschaffung und Installierung zusätzlicher Plattenlaufwerke. Jedoch ist diese Lösung sowohl kostspielig als auch unbequem. Zum Reduzieren der Anforderungen an die Datenspeicherung müssen die Anwender die Redundanz bei der Darstellung ihrer Daten reduzieren, d. h. ihre Daten komprimieren oder kompaktieren. Das Speichern von Daten in einem komprimierten Format impliziert, dass es zwei Formate für dieselben Daten gibt: eines ist das bevorzugte Format für die Manipulation der Daten, und das andere ist das ökonomischere Format zum Speichern der Daten. Die Datenkompression betrifft demnach zwei Prozesse: einen Prozess zum Komprimieren der Daten, wenn sie auf ein Speichermedium geschrieben werden, und einen Prozess zum Expandieren (manchmal als "Dekomprimieren" oder "Entkomprimieren" bezeichnet) der Daten, wenn sie von dem Speichermedium gelesen werden.

Die Kompressions- und Expansionsprozesse können in Software, Firmware oder Hardware ausgeführt werden. Die Datenkompression, sofern in Software ausgeführt, erhöht die Software-Komplexität des Systems. Sie erhöht auch direkt die Verarbeitungslast des Systems, da zusätzliche Prozessorzyklen für das Komprimieren und Expandieren erforderlich sind. Jedoch wird es mit der Verfügbarkeit von immer zunehmend leistungsfähigeren Prozessoren ökonomischer, Daten allgemein in Software zu komprimieren, und insbesondere als Teil der Dateisystemdienste, bereitgestellt durch das Computerbetriebssystem.

Dateisystemdienste sind für das Managen des Speichermediumraums verantwortlich. Sie bilden einen logischen Rahmen für die Anwender des Computersystems für den Zugang zu Daten, die in dem Speichermedium gespeichert sind. Der logische Rahmen umfasst üblicher Weise eine Hierarchie von Verzeichnisstrukturen zum Zuweisen einer Ansammlung von Dateien, die Anwender-benamte Programme oder Daten enthalten. Die Anwendung von Verzeichnissen und Dateien überwindet (aus dem Blickwinkel des Anwenders, das Anlegen zum Auffinden der tatsächlichen physikalischen Stellen der gespeichert Information in dem Speichermedium. Es sind viele unterschiedliche Typen von Dateisystemen bekannt. Insbesondere sind popoläre Dateisystemebereiche UNIX Dateisysteme und das WINDOWS NT Dateisystem. Das UNIX Dateisystem ist beschrieben in "Der Entwurf und die Implementierung des 4.3BSD UNIX Betriebssystems", S. Leffler, M. McKusick, M. Karels und J. Quarterman, Kapitel 7, Addison- Wesley, 1989. Das WINDOWS NT Dateisystem ist beschrieben in "Inside the Windows NT File System", H. Custer, Microsoft Press, 1994.

Datenkompressionssoftware kann entweder auf der Sektorebene oder auf der Dateisystemebene implementiert sein. Sektorebenen-Kompressionsschemata komprimieren den gesamten Platteninhalt einschließlich der Dateisystem-Metadaten. Sie arbeiten zwischen einem Dateisystem und einem Plattentreiber, unter Komprimierung von Daten, wie sie zu der Platte geschrieben werden, und sie expandieren automatisch die Daten bei einem Lesen von der Platte. Beispiele für Produkte, die sowohl auf der Datei- als auch Sektorebenekompression basieren, sind "Stacker", verfügbar von Sty Electronics, und "DoubleSpace" und "DriveSpace", verfügbar von Microsoft Corporation. Das Buch "PC Interne Systemprogrammierung", Michael Tischer, Abacus/Data Becker, Sth Edition, 1995, beschreibt ebenso das "DoubleSpace" Produkt.

Der Vorteil der Sektorebenen-Kompressionssoftware besteht darin, dass sie unabhängig von dem Dateisystem ist, das die Anwender verwenden. Der Nachteil besteht darin, dass existierende Anwenderdaten zunächst zu einer anderen Speichereinrichtung zu sichern sind, und dann in die Speichereinrichtung wieder gespeichert werden, wo komprimierte Daten gespeichert werden. Dieses Sichern und Neuspeichern existierender Daten ist ein zeitaufwendiger und fehleranfälliger Prozess.

Die Dateisystemebenen-Komprimierung bewirkt das Komprimieren von Dateien auf einer Pro-Dateibasis. Sie kann in anwendertransparenter Weise als Teil der grundlegenden Dateisystemdienste ausgeführt werden. Das Dateisystem detektiert, ob eine Datei detektiert werden soll, und es stößt dann den Komprimierungsprozess an, wenn die Datei geschrieben wird, sowie den Expansionsprozess, wenn die Dichteinrichtung gelesen wird. Dateisystemebenen- Komprimierung kann auch auf alle Dateien angewandt werden oder sie kann explizit durch Anwender auf einer Pro- Dateibasis, Pro-Verzeichnisbasis oder Pro-Dateitypbasis, initiiert werden. Die Veröffentlichung "Online Datenkomprimierung in einem Logstrukturierten Dateisystem" von M. Burrows, C. Jerian, B. Lampson und T. Mann, Proceedings of the Sth International Conference an Architectural Support for Proramming Languages and Operating Systems, 1992, beschreibt allgemein die Dateisystemebenen- Komprimierung.

Dieses Papier beschreibt eine log-strukturierte Dateisystem(LFS)-Technik für eine Dateisystemebenen- Komprimierung. Bei dieser Technik werden sämtliche neuen Daten an dem Ende einer sequentiell geschriebenen log-Einheit geschrieben, und die log-Einheit wird einfach bei einem Schreiben zur Platte komprimiert. Die log-Einheit wird in Segmenten fester Größe gespeichert. Das Komprimieren wird durch Zuweisen von Raum auf zwei Weisen unterstützt: entweder als physikalischer Raum, der Plattenblöcke repräsentiert, oder als logischer Raum zum Darstellen des Raums, der für nicht komprimierte Daten erforderlich ist. Ein Segment wird als voll betrachtet, wenn entweder ihr logischer oder physikalischer Raum erschöpft ist. Eine logische Blockabbildung wird während der Lese- und Schreibprozesse angewandt, zum Verfolgen der logischen Adressen und der physikalischen Adressen.

Eine typische Dateisystem-Implementierung, hiernach als Dateisystem in Bezug genommen, konvertiert die Anwenderabstraktion einer Datei als Feld von Bytes zu der Struktur, die durch das unterliegende physikalische Medium eingeprägt ist. Typischerweise sind Magnetplatten in Sektoren fester Größe organisiert. Obgleich der Anwender den Wunsch haben kann, ein einziges Byte in eine Datei zu schreiben, kann die Platte lediglich mehrere Sektoren lesen oder schreiben. Demnach muss zum Modifizieren eines einzigen Bytes in einer Datei das Dateisystem zunächst in dem Sektor lesen, der das zu modifizierende Byte enthält, und dann das beeinflusste Byte ersetzen, und schließlich den Sektor zurück zu der Platte schreiben. Der Betrieb zum Umsetzen eines wahlfreien Zugriffs eines Anwenders zu einem Feld von Bytes bei Lese- und Schreibvorgängen für Plattensektoren ist als "Block I/O" (Blockeingabe/Ausgabe) bekannt.

Zum wirksamen Unterstützen von Block I/O, unterteilt ein Dateisystem typischerweise das Feld der Bytes in einer vorgegebenen Datei in eine Gruppe logischer Blöcke mit fester Größe. Beispielsweise dann, wenn die Größe eines Dateisystem- Logikblocks 8192 Byte ist, würde der logische Block 0 Bytes von 0 bis 8191 der Datei enthalten, und der logische Block 1 würde Bytes 8192 bis 16383 der Datei enthalten, etc..

Die Daten in jedem logischen Block werden in einem physikalischen Block auf der Platte gespeichert. Ein physikalischer Block ist die Stelle auf der Platte, zu der das Dateisystem einen logischen Block abbildet. Ein physikalischer Block wird aus einem oder mehreren fortlaufenden Sektoren aufgebaut. Bei einer Platte mit 512 Byte-Sektoren würde ein logischer Block mit 8192 Byte auf der Platte durch einen physikalischen Block mit 8192 Byte dargestellt werden, der 16 fortlaufende Sektoren enthalten würde.

Demnach hat eine Datei mit N logischen Blöcken eine Tabelle mit N Abbildungen von einem logischen zu einem physikalischen Block. Das erste Element der Abbildungstabelle für eine Datei enthält die physikalische Blockadresse für den logischen Block 0, das nächste Element enthält die physikalische Adresse für den logischen Block 1, etc..

Obgleich die meisten Anwendungen Daten zu einer Datei in sequentieller Weise schreiben, schreiben einige Anwendungen Daten zufällig mit irgendeinem Versatz in die Datei. Beispielsweise kann eine Anwendung eine neue Datei erzeugen, und dann mehrere Bytes schreiben, ausgehend von einem Versatz M in der Datei. In diesem Fall sind die Bytes mit Versatz 0 und Versatz M-1 der Datei niemals geschrieben, sie bilden jedoch einen logischen Teil der Datei und werden allgemein so behandelt, als ob sie alle die Werte 0 hätten.

Da es verschwenderisch ist, einen physikalischen Block für einen entsprechenden Block zu speichern, der niemals geschrieben wurde (d. h., voll mit Nullwerten), besteht eine allgemeine Technik, die in einigen Dateisystemen eingesetzt wird, im Vermeiden der tatsächlichen Zuweisung für derartige Blöcke. Das Dateisystem zeigt eine spezielle physikalische Blockadresse, üblicherweise 0, die die Adresse eines speziellen, jedoch nicht existierenden physikalischen Blocks darstellt, der voll von Nullwerten ist. Der spezielle physikalische Block wird als ein "Loch" bezeichnet.

Im obigen Beispiel wird das Dateisystem die logischen Blöcke in den Bereich der Bytes von 0 bis M-1, mit der Ausnahme des logischen Blocks mit dem Versatz M, zu der speziellen Blockadresse abbilden, zum Anzeigen, dass diese Blöcke nicht zugewiesen sind. Eine Datei, die zumindest ein Loch enthält, wird als "löchrige" Datei bezeichnet.

Im wesentlichen kann eine "löchrige" Datei als eine Datei betrachtet werden, die mit einem grundlegenden Kompressionsalgorithmus komprimiert wurde, der lediglich physikalische Blöcke wegkomprimiert, die voll mit Nullwerten sind. Demnach ist die Kompression extrem beschränkt. Weiterhin ist eine "löchrige" Datei vollständig für die Anwender transparent. Demnach kann gesagt werden, dass Dateisysteme, die "löchrige" Dateien unterstützen, eine sehr eingeschränkte Form der Dateisystemebenen-Komprimierung unterstützen. "Löchrige" Dateien werden durch viele kommerzielle Implementierungen des UNIX Systems unterstützt, beispielsweise dem SunSoft Solaris Betriebssystem. Obgleich die meisten UNIX Betriebssysteme "löchrige" Dateien unterstützen, unterstützen sie nicht eine allgemeinere Form der Dateiebenenkomprimierung.

Zum transparenten Unterstützen einer Komprimierung auf der Dateisystemebene muss ein Dateisystem die folgenden Kompressionsattribute unterhalten: (1) ob eine Datei komprimiert ist oder nicht komprimiert ist, (2a) ob eine Datei als eine Einheit komprimiert ist, die Speicherlänge der komprimierten Datei, oder (2b) ob eine Datei in Einheiten gleicher Länge unterteilt ist und die Komprimierung bei jeder Einheit erfolgt, die Speicherlänge jeder Kompressionseinheit.

Die meisten existierenden Dateisysteme sind nicht mit diesem Typ der Unterstützung für eine Dateikomprimierung entworfen. Demnach enthalten ihre platteneigenen Dateisystemformate üblicher Weise nicht den Raum zum Speichern von Komprimierungsattributen. Typischerweise muss dann, wenn ein existierendes Dateisystem zum Unterstützen der Komprimierung zu verbessern ist, auch das platteneigene Dateisystemformat geändert werden. Das Ändern des platteneigenen Dateisystemformats eines Dateisystems erfordert üblicher Weise das Umsetzen existierender Anwenderdaten von dem alten platteneigenen Dateisystemformat zu dem neuen Format, was ein zeitaufwendiger, kostspieliger und fehleranfälliger Prozess ist.

Demnach wäre es wünschenswert, die Dateisystemebenen- Komprimierung auf existierende Dateisysteme zu erweitern, ohne der Anforderung zum Umsetzen existierender Daten. Es wäre auch wünschenswert, dass sowohl komprimierte als auch expandierte Dateien miteinander existieren, wodurch das Komprimieren allmählich eingeführt werden kann. Es wäre auch wünschenswert, die Fähigkeit zu haben, mehrere Komprimierungsalgorithmen in einem derartigen Dateisystem zu verwenden.

ZUSAMMENFASSUNG DER ERFINDUNG

Eine Ausführungsform der vorliegenden Erfindung betrifft ein Verfahren und Gerät zum Komprimieren von Daten in einem Dateisystem unter Verwendung des Konzepts von "Löchern". Eine Abbildungstabelle in dem Dateisystem bewirkt das Abbilden logischer Blöcke einer Datei zu den tatsächlichen physikalischen Blöcken auf der Platte, wo die Daten gespeichert sind. Eine nicht komprimierte Datei belegt dieselbe Zahl der physikalischen Blöcke auf der Platte wie die Zahl der logischen Blöcke. Blöcke sind typischerweise in Einheiten eines Clusters angeordnet, und die Datei kann Cluster für Cluster komprimiert werden. In einigen Ausführungsformen werden die Löcher zum Anzeigen nicht nur der Tatsache verwendet, dass ein Cluster komprimiert wurde, sondern auch zum Anzeigen des zum Komprimieren dieses Clusters verwendeten Komprimierungs-Algorithmus. Mit dieser Anordnung können unterschiedliche Cluster in einer Datei unter Verwendung unterschiedlicher Kompressions-Algorithmen komprimiert werden. Sobald für eine Datei die Anforderung zum Schreiben zu dem Speicher vorliegt, wird eine Einheit der Daten komprimiert, mit dem Ergebnis, dass die Datei weniger physikalische Blöcke belegt, als sie logische Blöcke aufweist. Die Datei kann dann zu dem Speicher geschrieben werden, und die Abbildungstabelle wird aktualisiert.

Die Abbildungstabelle wird zum Anzeigen aktualisiert, dass für eine vorgegebene Einheit komprimierter Daten weniger physikalische Blöcke erforderlich sind. Demnach werden bestimmte logische Blöcke, die zu diese Einheit der Daten gehören, nicht zu physikalischen Blöcken abgebildet, sondern sie werden zu einem Loch abgebildet. Ein Loch kann anzeigen, dass diese Einheit der Daten komprimiert wurde, und es kann auch anzeigen, dass zum Komprimieren dieser Einheit der Daten ein bestimmter Komprimierungs-Algorithmus verwendet wurde.

In einigen Fällen kann es erforderlich sein, zunächst einen Cluster von der Platte zu lesen, bevor er geschrieben wird. Beispielsweise dann, wenn eine Einheit von Daten in der Mitte eines Clusters beginnt oder endet, muss zum Beibehalten der Integrität der Kompressionseinheit zum Vermeiden des Überschreibens von nicht zu ändernden Daten der gesamte Cluster zunächst von der Platte gelesen werden. Beispielsweise dann, wenn eine Einheit von Daten in einem Computerspeicher zu der Platte zu schreiben ist und die Einheit von Daten halbwegs in dem Cluster beginnt, sollte der gesamte Cluster nicht zu der Platte geschrieben werden, da die erste Hälfte des Clusters überschrieben würde. Der gesamte Cluster sollte zunächst von der Platte gelesen werden, um die erste Hälfte des Clusters beizubehalten, die unverändert bleibt. Werden die Daten gelesen und bezeichnet ein Loch, dass der Cluster komprimiert wurde, so müssen zunächst die Daten expandiert werden. Sobald der Cluster in einem Puffer gelesen wurde, wird der zu ändernde Abschnitt überschrieben. Der Cluster wird dann komprimiert zu der Platte geschrieben. Cluster, in denen die Einheit der Daten weder beginnt noch endet, müssen nicht zunächst von der Platte gelesen werden, sondern sie können direkt geschrieben werden.

Bei einem Aspekt der Erfindung können unterschiedliche Cluster in einer Datei unterschiedliche Typen von Löchern enthalten. Dies ermöglicht das Anwenden unterschiedlicher Komprimierungs-Algorithmen in einer gegebenen Datei. Weiterhin können Dateien in einem Dateisystem unter Verwendung unterschiedlicher Typen von Löchern komprimiert werden. Dies ermöglicht die Anwendung vielfacher Komprimierungs-Algorithmen in dem Dateisystem auf einer Pro- Dateibasis.

Vielfältige Ausführungsformen der vorliegenden Erfindung erweitern demnach das Konzept der Dateien mit "Löchern" auf das Unterstützen einer Dateisystemebenen-Komprimierung. Demnach können sowohl komprimierte als auch expandierte Dateien miteinander existieren, wodurch sich für die Anwender der Vorteil einer Dateisystemebenen-Komprimierung ohne der Anforderung ergibt, dass Daten in einer existierenden Speichereinrichtung alle auf einmal konvertiert werden müssen, und ebenso wenig müssen sie das platteneigene Dateisystemformat ändern.

KURZE BESCHREIBUNG DER ZEICHNUNG

Die Erfindung, zusammen mit weiteren Vorteilen hiervon, lässt sich am besten unter Bezug auf die folgende Beschreibung im Zusammenhang mit der beiliegenden Zeichnung verstehen; es zeigen:

Fig. 1 symbolisch ein Beispiel einer Dateisystemstruktur;

Fig. 2 symbolisch die Abbildung von logischen Blöcken in einer Datei zu physikalischen Blöcken in dem Speicher oder auf der Platte;

Fig. 3 eine Abbildungstabelle für eine logische Datei gemäß einem Aspekt der Erfindung;

Fig. 4a Cluster von logischen Blöcken in einer Datei, die komprimiert sind;

Fig. 4b eine Ausführungsform einer Abbildungstabelle für die komprimierte Datei nach Fig. 4a;

Fig. 5a ein Flussdiagramm zum Darstellen eines Schreibbetriebs in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung;

Fig. 5b ein Flussdiagramm zum Darstellen eines Betriebs zum Berechnen der Schreibgröße, verwendet bei einer Ausführungsform des Schreibbetriebs nach Fig. 5a;

Fig. 5c ein Flussdiagramm zum Darstellen eines Schreibclusterbetriebs, verwendet bei einer Ausführungsform des Schreibbetriebs nach Fig. 5a;

Fig. 5d ein Flussdiagramm zum Darstellen eines Betriebs zum Berechnen und Festlegen einer Dateigröße, verwendet bei einer Ausführungsform des Schreibbetriebs nach Fig. 5a;

Fig. 5e ein Flussdiagramm zum Darstellen eines Komprimierungs- und Schreibclusterbetriebs, verwendet bei einer Ausführungsform des Schreibclusterbetriebs nach Fig. 5c;

Fig. 6a ein Flussdiagramm zum Darstellen eines Lesebetriebs zum Darstellen einer Ausführungsform der vorliegenden Erfindung;

Fig. 6b ein Flussdiagramm zum Darstellen eines Betriebs zum Berechnen einer Lesegröße, verwendet bei einer Ausführungsform des Lesebetriebs nach Fig. 6a;

Fig. 6c ein Flussdiagramm zum Darstellen eines Leseclusterbetriebs, verwendet bei einer Ausführungsform des Lesebetriebs nach Fig. 6a;

Fig. 7 ein Flussdiagramm zum Darstellen eines Lese- und Erweiterungsbetriebs in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung, die sich sowohl für Schreib- als auch Lesebetriebsschritte verwenden lässt;

Fig. 8a ein Flussdiagramm zum Darstellen eines Betriebs zum Festlegen einer Dateigröße in Übereinstimmung mit einer Ausführungsform der vorliegenden Erfindung;

Fig. 8b ein Flussdiagramm zum Darstellen eines Betriebs zum Kürzen einer Datei, verwendet bei einer Ausführungsform des Betriebs zum Festlegen der Dateigröße gemäß Fig. 8a;

Fig. 8c ein Flussdiagramm zum Darstellen eines Betriebs zum Verlängern einer Datei, verwendet bei einer Ausführungsform des Betriebs und Festlegen der Dateigröße nach Fig. 8a; und

Fig. 9 ein typisches Computersystem mit der Eignung für die Implementierung der vorliegenden Erfindung.

DETAILLIERTE BESCHREIBUNG DER ERFINDUNG

Fig. 1 zeigt allgemein eine Struktur für ein Dateisystem 200. Das Dateisystem hat eine Hierarchie von Verzeichnisstrukturen 201, eine Dateitabelle 301 und eine Abbildungstabelle 305. Es gibt eine Abbildungstabelle 305 für jeden Eintrag in der Dateitabelle 301. In dem Verzeichnis 201 gibt es Einträge von Dateinamen in dem Dateisystem und entsprechende Dateinummern, die das Indizieren von Dateien zu einem Eintrag in der Dateitabelle erlauben. Jeder Eintrag 302 in der Dateitabelle 301 identifiziert eine Datei des Dateisystems, und ist allgemein als Inode bekannt. Insbesondere sind ein Dateiname 203 und seine entsprechende Dateinummer 205 gezeigt. Die Zeigerdateinummer 205 zeigt auf eine bestimmte Inode 302 in der Dateitabelle 301. Diese Inode 302, oder Zeile der Dateitabelle 301, enthält Information über die gegebene Datei. Inodes sind beschrieben in "Der Entwurf und die Implementierung des 4.3BSD der UNIX Betriebssystems", Kapitel 7, auf das oben Bezug genommen ist. Die enthaltene Information kann zahlreiche Dateiattribute 303 betreffen, beispielsweise den Typ der Datei und die Dateizugriffsteuerung, und insbesondere die Größe 307 der Datei, sowie die Gesamtzahl der physikalischen Blöcke 309, die durch diese Datei auf der Platte belegt sind. Es ist ebenso ein Abbildungstabellenzeiger 304 gezeigt, der zu einer Abbildungstabelle für diese Datei zeigt. Es ist zu erkennen, dass andere Strukturen für ein Dateisystem möglich sind, und dass sich viele Dateisysteme für die Anwendung im Zusammenhang mit der vorliegenden Erfindung eignen.

Die Abbildungstabelle 305 enthält Information dahingehend, wie die Logikblöcke in einer Datei zu physikalischen Blöcken auf der Platte abgebildet sind. Es ist zu erkennen, dass diese physikalischen Blöcke auf einer Festplatte, einer Floppy Disk, einer Optikplatte oder dergleichen vorliegen können. Es ist auch möglich, dass diese physikalischen Blöcke im physikalischen Speicher des Computers oder einer ähnlichen Speichereinrichtung enthalten sind. Der erste Eintrag 306 in der Dateitabelle 305 bewirkt ein Abbilden zu der physikalischen Blocknummer 308 für die logische Blocknummer 0 der Datei. Der nächste Eintrag enthält die Abbildung für die logische Blocknummer 1, etc.. Die Größe der Datei 307 bestimmt die Zahl der Einträge in der Abbildungstabelle 305. Die physikalische Blocknummer identifiziert den Ort auf der Platte, wo der logische Block zu speichern ist. Die Abbildungstabelle kann unter Verwendung eines Felds, einer Liste oder einer ähnlichen Datenstruktur implementiert sein, oder sie kann in Hardware implementiert sein. Wird ein Feld angewandt, so kann der Index des Felds zum Repräsentieren der logischen Blocknummer dienen. Es ist bevorzugt, die Abbildungstabelle als ein Feld zu implementieren.

Die Fig. 2 zeigt bei 400 symbolisch, wie die logischen Blöcke der Datei auf die physikalischen Blöcke auf der Festplatte abgebildet werden können, als Beispiel. Gezeigt ist eine logische Datei 401, die typischerweise in dem Speicher eines Computers enthalten wäre, und so, wie sie bearbeitet wird. Ebenso ist eine Festplatte 420 gezeigt. Eine Festplatte ist typischerweise in physikalische Blöcke unterteilt, es ist jedoch nicht immer wahr, dass die logischen Blöcke der Datei in fortlaufend physikalischen Blöcken auf einer Festplatte gespeichert sind. Beispielsweise sind die logischen Blöcke der logischen Datei so gezeigt, dass sie zu nicht fortlaufenden physikalischen Blöcken auf der Festplatte 420 abgebildet sind. Demnach werden dann, wenn die logische Datei 401 zu der Festplatte geschrieben wird, die logischen Blöcke zu den nicht fortlaufenden physikalischen Blöcken geschrieben. In diesem Beispiel wird der logische Block Null 402 zu dem physikalischen Block Drei 428 geschrieben. Der logische Block Eins 404 wird zu dem physikalischen Block Eins 424 geschrieben, der logische Block Zwei 406 wird zu dem physikalischen Block K 432 geschrieben, und der logische Block N 408 wird zu dem physikalischen Block Vier 430 geschrieben. Wie gezeigt, besteht die logische Datei 401 aus null bis N Blöcken, jedoch kann eine Datei ein Block über die Länge sein, oder irgendeine Zahl von Blöcken in einer Länge. Ähnlich zeigt die Festplatte 420 physikalische Blöcke Null bis K, jedoch ist zu erkennen, dass logische Blöcke zu irgendwelchen der physikalischen Blöcke auf der Festplatte geschrieben werden können. Demnach lässt sich erkennen, wie die Abbildungstabelle 305 nach Fig. 1 verwendet wird, um anzuzeigen, zu welchen physikalischen Blöcken die logischen Blöcke geschrieben werden. Obgleich eine Festplatte 420 als ein Beispiel verwendet wird, kann diese Ressource 420 irgendein Speichermedium in Zuordnung zu einem Computer sein.

Wie oben diskutiert, kann es möglich sein, dass ein logischer Block in der einer Datei sehr wenig Daten enthält oder er kann tatsächlich vollständig leer sein, d. h., der logische Block ist voll von Nullwerten. Beispielsweise dann, wenn der logische Block Eins 404 vollständig von Nullwerten gefüllt ist, würde der Nullblock in seiner Gesamtheit zu dem physikalischen Block Eins 424 geschrieben werden. Wie oben erwähnt, ist dies nicht wünschenswert, da ein physikalischer Block vollständig gefüllt mit Nullwerten eine Verschwendung von Speicherraum darstellt.

Die Fig. 3 demonstriert, wie das "Loch" Konzept zum Vermeiden des Schreibens eines vollständig mit Nullwerten gefüllten physikalischen Blocks verwendet wird. Bei 500 in Fig. 3 ist ein Beispiel dieser Technik gezeigt. Es ist eine logische Datei 401 und ihre entsprechende Abbildungstabelle 305 gezeigt. In diesem Beispiel zeigt die logische Datei 401 vier logische Blöcke, Block Null, Block Eins, Block Zwei und Block N. In diesem Beispiel enthalten der logische Block Null 402 und der logische Block N 408 jeweils Nicht-Null-Daten. Jedoch enthalten die logischen Blöcke 1 und 2 beide nichts als Nullwerte. Unter erneutem Bezug auf die Fig. 2 lässt sich erkennen, dass der Logikblock Null zu dem physikalischen Block Drei geschrieben wird und dass der logische Block N zu dem physikalischen Block Vier geschrieben wird. Die Abbildungstabelle 305 zeigt demnach den Logikblock Null bei 502 abgebildet zu dem physikalischen Block Drei bei 504. Und ähnlich ist der Logikblock N bei 506 als abgebildet zu dem physikalischen Block Vier bei 508 gezeigt. Da jedoch die logischen Blöcke Eins und Zwei voll von Nullwerten sind, werden sie nicht zu den entsprechenden physikalischen Blöcken geschrieben. Anstelle hiervon zeigt die Abbildungstabelle, wie die logischen Blöcke Eins bei 510 und der Logikblock Zwei bei 514 zu den Löchern 512 und 516 abgebildet sind. Wie hier gezeigt, ist ein Loch 512 oder 516 durch die Zahl Null dargestellt. In diesem Fall repräsentiert Null eine spezielle Adresse, d. h. nicht eine tatsächliche physikalische Blockadresse, zu der Daten geschrieben werden, sondern eine einzige Adresse, die anzeigt, dass die entsprechenden logischen Blöcke tatsächlich voll mit Nullwerten sind. Es ist zu erkennen, dass sich andere Techniken anwenden lassen, um das Vorliegen eines Lochs anzuzeigen, anders als das Verwenden der Zahl Null. Beispielsweise kann ein Loch durch das Vorliegen einer unzulässigen Speicheradresse wie einer negativen Zahl angezeigt sein.

Zusätzlich wird im Rahmen der vorliegenden Erfindung in Betracht gezogen, dass eine unzulässige Speicheradresse oder dergleichen für die Unterscheidung verwendet werden kann, dass ein Loch durch einen Komprimierungs-Algorithmus erzeugt wird, gegenüber einem Loch, das vorab in einer Datei existiert, die nicht komprimiert wurde. Beispielsweise würde eine physikalische Blockadresse, dargestellt durch eine Null, anzeigen, dass ein Loch in einer expandierten Datei existiert, während eine physikalische Blockadresse mit einer unterschiedlichen unzulässigen Speicheradresse oder dergleichen anzeigen würde, dass ein Block oder Cluster von einer Datei komprimiert wurde.

Die Fig. 4a und 4b zeigen symbolisch eine Ausführungsform der vorliegenden Erfindung, bei der das Komprimierung einer Datei in einem Dateisystem ausgeführt wird, das nicht typischerweise eine Komprimierung unterstützt, durch Anwendung des Konzepts der Löcher. Die Fig. 4a zeigt bei 600 eine Logikdatei 610, die eine Datenkomprimierung durchläuft. In der Logikdatei 610 sind logische Blöcke Null bis Sieben gezeigt, die alle Daten enthalten. In diesem Beispiel ist ein Cluster in dem Dateisystem als vier Logikblöcke umfassend definiert. Demnach ist ein erster Cluster 630 gezeigt, der logische Blöcke Null bis Drei enthält, und ein zweiter Cluster 634, der logische Blöcke Vier bis Sieben enthält. In diesem Beispiel erfolgt das Komprimieren auf einer Cluster für Cluster Basis. Es ist zu erkennen, dass sich das Komprimieren auf einen Cluster mit irgendeiner geeigneten Größe anwenden lässt. Beispielsweise ist eine Clustergröße mit dem Vierfachen oder Achtfachen einer logischen Blockgröße möglich, mit einer Clustergröße von Minimum dem Vierfachen der logischen Blockgröße als bevorzugt. Jedoch sollte ein Cluster größer sein als die logische Blockgröße und ein ganzzahliges Vielfaches der logischen Blockgröße.

In diesem Beispiel wird der erste Cluster 630 in einen komprimierten Cluster 640 komprimiert, indem die Daten um die Hälfte so reduziert sind, dass die Daten lediglich in logischen Blöcken Null und Eins des komprimierten Clusters 640 vorliegen. Die logischen Blöcke Zwei und Drei des komprimierten Clusters 640 wären dann vollständig mit Nullwerten gefüllt. Ähnlich wird der Cluster 634 in einen komprimierten Cluster 644 komprimiert. Bei diesem Beispiel sind die Daten lediglich zu 75% ihrer Originalgröße komprimiert, und demnach enthalten die Logikblöcke Vier, fünf und Sechs Daten, während der Logikblock Sieben vollständig aus Nullwerten besteht. Die komprimierte Darstellung dieser logischen Datei ist bei 650 gezeigt. Die logischen Blöcke Null, Eins, Vier, Fünf und Sechs enthalten sämtlich Daten, während die logischen Blöcke Zwei, Drei und Sieben sämtlich Nullwerte sind.

Die entsprechende Abbildungstabelle 305 für die komprimierte Datei 650 ist in Fig. 4b gezeigt. Es ist zu erwähnen, dass die logischen Blöcke, die gültige Daten enthalten, zu tatsächlichen physikalischen Blockadressen abgebildet werden. Beispielsweise wird der logische Block Null 616 zu der Adresse des physikalischen Blocks Zwei 618 abgebildet. Da die logischen Blöcke Zwei, Drei und Sieben sämtlich aus Nullwerten bestehen, werden sie zu Löchern abgebildet. Beispielsweise werde die logischen Blöcke Zwei 620 und Drei 624 beide zu der speziellen negativen Adresse Zwei abgebildet, gezeigt bei 622 und 626. Die Zahl negativ Zwei, gezeigt bei 622 und 626, bezeichnet, dass der bestimmte Cluster komprimiert wurde. Demnach kann dann, wenn dieser Cluster von der Platte gelesen wird, diese negative Zwei detektiert werden, und der Cluster kann expandiert werden. In diesem Beispiel wurde der logische Block Sieben 628 zu der speziellen Adresse negativ Eins 631 abgebildet. Auf diese Weise kann diese spezielle Adresse nicht nur anzeigen, dass dieser Cluster komprimiert wurde, sondern ebenso, dass ein bestimmter Komprimierungs-Algorithmus zum Komprimieren des Clusters verwendet wurde. Beispielsweise kann die spezielle Adresse negativ Zwei bei 622 anzeigen, dass der erste Cluster unter Verwendung eines Algorithmus komprimiert wurde, während die spezielle Adresse negativ Eins bei 631 anzeigen kann, dass der zweite Cluster unter Verwendung eines unterschiedlichen Algorithmus komprimiert wurde. Auf diese Weise ist es möglich, Cluster einer Datei unter Verwendung unterschiedlicher Komprimierungs-Algorithmen zu komprimieren. Es wäre möglich, unterschiedliche Dateien unter Verwendung unterschiedlicher Komprimierungs-Algorithmen zu komprimieren.

Nun ist unter Bezugnahme auf die Fig. 5a ein Flussdiagramm 700 zum Darstellen des Schreibbetriebs für eine Ausführungsform der vorliegenden Erfindung gezeigt. Typischerweise akkumuliert ein Dateisystem Daten solange, bis der Umfang modifizierter Daten die Größe einer Komprimierungseinheit erreicht oder übersteigt. Der Schreibbetrieb wird dann die Daten komprimieren, den Rest der Cluster mit Nullwerten füllen, irgendwelche physikalischen Blöcke, die lediglich Nullwerte enthalten, mit Löchern ersetzen, und den Cluster zu der Platte schreiben. Der Schreibbetrieb beginnt mit dem Empfang der Eingabeparameter. Vier Variablen werden zu dem Schreibbetrieb eingegeben: der Eingabepuffer, die anfängliche Eingangspuffergröße, ein Dateiversatz und ein Dateiöffnungsdiscriptor. Der variable Eingangspuffer (Input Buffer) ist eine Adresse, die einen Datenpuffer anzeigt, der die zu der Platte zu schreibenden Daten enthält. Die anfängliche Eingangspuffergröße Initial Input Buffer Size) bezeichnet die Größe des Eingangspuffers in Bytes. Der Dateiversatz ist der Versatz der Datei, bei dem die Daten geschrieben werden. Der Dateiöffnungsdescriptor (Open File Descriptor) ermöglicht dem Schreibbetrieb den Zugang zu der Abbildungstabelle für die Datei, die geschrieben wird, und stellt die Dateigröße bereit. Die Dateigröße bezeichnet die Größe der geschriebenen Datei in Bytes. Eine weitere Variable ist von den Dateisystemmeterdaten verfügbar. Es ist die Variable Clustergröße, die die Größe eines Clusters in Bytes darstellt.

Nach dem Empfang der Schreibbetriebanforderung werden in dem Schritt 701 drei Variablen berechnet. Sie umfassen die Startclusternummer, die Endclusternummer und den Clusterversatz. Die Startclusternummer ist der Quotient aus dem Dateiversatz geteilt durch die Clustergröße. Die Endclusternummer ist der Quotient von: Dateiversatz plus Eingangspuffergröße minus eins, sämtlich geteilt durch die Clustergröße. Der Clusterversatz ist der Rest des Dateiversatz geteilt durch die Clustergröße. Die Variable Clusterversatz bezeichnet die Startstelle indem Cluster, wo die Daten geschrieben werden. All diese Variablen werden berechnet, und die Logik schreitet zu dem Schritt 703 voran, wo die vier Variablen initialisiert werden. Sie umfassen die Clusternummer, den Eingangspufferversatz, die Nummer der Bytes für das Schreiben und die anfängliche Eingangspuffergröße. Die Clusternummer bezeichnet den zu schreibenden Cluster, und sie wird gleich zu der Startclusternummer gesetzt. Der Eingangspufferversatz bezeichnet den Punkt in dem Eingangspuffer, von dem die Daten geschrieben werden, und er wird zu Null initialisiert. Weiterhin wird die Zahl der geschriebenen Bytes zu Null gesetzt, und die Eingangspuffergröße wird gleich zu der anfänglichen Eingangspuffergröße gesetzt. Der Eingangspufferversatz ist der Versatz in dem Eingangspuffer, von dem die Daten zu der Platte geschrieben werden.

In dem Schritt 705 wird eine Variable Schreibgröße (Write Size) berechnet. Diese Variable bezeichnet die Zahl der in einer Iteration dieses Betriebs zu schreibende Bytes, und die Schreibgröße muss einer als oder gleich zu der Größe eines Clusters sein. Dieser Schritt wird detaillierter nachfolgend unter Bezug auf die Fig. 5b erläutert. Nach dem Bestimmen der Schreibgröße wird ein (erster) Cluster zu der Platte in dem Schritt 707 geschrieben. Dieser Clusterschreibschritt wird detaillierter nachfolgend unter Bezug auf die Fig. 5c erläutert. Nach dem Schreiben des ersten Clusters wird die Clusternummervariable um Eins in dem Schritt 709 inkrementiert. Dann wird in dem Schritt 710 die variable Zahl der geschriebenen Bytes um die Schreibgröße inkrementiert, um die Zahl der Bytes zu bezeichnen, die gerade zu der Platte geschrieben sind. In diesem Punkt erfolgt eine Bestimmung dahingehend, ob der letzte Cluster für den Eingangspuffer geschrieben wurde. Dies erfolgt durch Vergleichen der Clusternummer zu der Endclusternummer in dem Schritt 711. Ist die Clusternummer größer als die Endclusternummer, so ist der Schreibbetrieb abgeschlossen, und die Steuerung geht zu dem Schritt 719 über. Ist dies nicht der Fall, so ist der Schreibbetrieb nicht abgeschlossen, und die Steuerung geht zu dem Schritt 713 über.

In dem Schritt 713 wird die Eingangspuffergröße um die Schreibgröße (Write Size) dekrementiert, um die Zahl der Bytes anzuzeigen, die immer noch zu der Platte geschrieben werden müssen. In dem Schritt 715 wird die Variable Eingangspufferversatz (Input Buffer Offset) um die Schreibgröße imkrementiert. In dem Schritt 717 wird die Variable Clusterversatz (Cluster Offset) gleich zu Null gesetzt, da irgendein Teilcluster geschrieben wurde, und die verbleibenden Cluster werden von ihrem Beginn ausgehend geschrieben. Von dem Schritt 717 verzweigt die Steuerung zurückzu dem Schritt 705, und der Betrieb wird zu einer anderen Iteration fortgesetzt, wie oben beschrieben. In dem Schritt 719 wird die Variable Dateigröße berechnet und festgelegt, zum Bezeichnen des neuen Endes der Datei für die Datei auf der Platte. Dieser Schritt wird nachfolgend detaillierter unter Bezug auf die Fig. 5d beschrieben. In dem Schritt 720 endet der Schreibbetrieb, und die variable Zahl der geschriebenen Bytes wird zu der aufrufenden Einheit zurückgegeben.

Die Fig. 5b zeigt eine Prozedur 705 zum Berechnen der Schreibgröße für die Zahl der zu schreibenden Bytes. Für den ersten und letzten geschriebenen Cluster kann die Schreibgröße nicht dieselbe sein wie die Clustergröße, da ein Schreibvorgang in einem Cluster beginnen oder enden kann. Für Zwischencluster ist die Schreibgröße gleich der Clustergröße. In dem Schritt 731 wird die Schreibgröße gleich der Clustergröße minus dem Clusterversatz gesetzt. Die Schreibgröße muss kleiner als oder gleich der Größe eines Clusters sein. Bei der ersten Iteration der Schreibprozedur kann die Schreibgröße kleiner als eine Clustergröße sein, wenn es einen Clusterversatz gibt; d. h., wenn die zu einer Platte zu schreibenden Daten in der Mitte des Clusters beginnen. Nachfolgenden Iterationen durch die Schreibprozedur ist die Schreibgröße gleich zu der Größe des Clusters, da der Clusterversatz in dem Schritt 717 zu Null gesetzt wurde. In dem Schritt 733 erfolgt ein Test, ob die Schreibgröße größer als die Eingangspuffergröße ist. Ist die Schreibgröße nicht größer als die Eingangspuffergröße, so zeigt dies an, dass die in dem Eingangspuffer verbleibenden zu schreibenden Daten größer als ein Cluster sind, und die Schreibgröße verbleibt bei der Größe eines Clusters, und die Prozess 705 ist abgeschlossen.

Ist jedoch die Schreibgröße größer als die Eingangspuffergröße, so zeigt dies an, dass das Ende des Eingangspuffers erreicht ist, und dass die zum Schreiben verbleibenden Daten weniger als als die Größe eines Clusters. In diesem Fall wird in einem Schritt 735 Schreibgröße gleich zu den verbleibenden Daten gesetzt, d. h., der Eingangspuffergröße. Es ist zu erwähnen, dass sich die Eingangspuffergröße mit dem Ausführen der Iterationen durch den Schreibbetrieb ändert, da die Variable Eingangspuffergröße um die Schreibgröße in dem Schritt 713 dekrementiert wird. Nach dem Schritt 735 ist der Schritt 705 zum Berechnen der Schreibgröße beendet.

Die Fig. 5c zeigt ein Flussdiagramm 707, das eine Prozedur zum Schreiben eines Clusters beschreibt. In dem Schritt 801 wird die gesamte Block-Abbildungsinformation für die Clusternummer wiedergewonnen. Beispielsweise kann die Variable Dateiöffnungsdiscriptor für den Zugriff auf die Abbildungstabelle für die geschriebene Datei verwendet werden, die die gesamte Abbildungsinformation für all die Cluster enthält. Beispielsweise ist in den Fig. 4a und 4b gezeigt, wie die Abbildungsinformation für einen ersten Cluster 640 in der Abbildungstabelle 305 enthalten ist.

Der Schritt 805 dient zum Testen, ob ein vollständiger Cluster geschrieben wird. Wird ein vollständiger Cluster von dem Eingangspuffer zu der Ausgangsdatei geschrieben, dann kann der Cluster direkt geschrieben werden. Dieser Test kann ausgeführt werden, indem ein Vergleich von Schreibgröße zu Clustergröße erfolgt, und ist dies Schreibgröße nicht gleich der Clustergröße, so zeigt dies an, dass ein vollständiger Cluster nicht geschrieben wird. Wird ein vollständiger Cluster geschrieben, so wird in dem Schritt 815 dieser Cluster komprimiert und von dem Eingangspuffer zu der offenen Datei geschrieben. Dieser Cluster von dem Eingangspuffer unter Verwendung der in dem Eingangspuffer bei der Stelle Eingangspufferversatz gespeicherten Daten komprimiert und zu der Platte geschrieben. Dieser Schritt 815 wird nachfolgend vollständiger unter Bezug auf die Fig. 5e erläutert.

Wird ein vollständiger Cluster nicht geschrieben, so muss dann, dieser Cluster zunächst von der Datei gelesen werden, bevor er geschrieben wird, wie in den Schritten 807 bis 811 gezeigt. Die Schritte 807 bis 813, die verwendet werden, wenn ein vollständiger Cluster nicht geschrieben wird, beschreiben eine Situation, in der entweder der Eingangspuffer bei einer Zwischenstelle in einem Cluster beginnt oder bei einer Zwischenstelle in einem Cluster endet. Beginnt der Eingangspuffer bei dem Beginn eines Clusters und endet er bei dem Ende eines Clusters, so sind diese Schritte nicht erforderlich. Die folgenden Variablen werden in den Schritten 807 bis 813 verwendet: Clusternummer ist der Cluster, bei dem die Daten wiedergewonnen werden, Lesepuffer ist ein temporärer Datenpuffer, der die wieder zu gewinnenden Daten enthält, Clusterversatz ist der Versatz in dem Lesepuffer, zu dem die Daten von dem Eingangspuffer kopiert werden, Eingangspuffer enthält die zu schreibenden Daten, und Eingangspufferversatz ist eine Stelle in dem Eingangspuffer, von der die Daten zu der Platte geschrieben werden.

In dem Schritt 807 wird der Lesepuffer rückgesetzt, durch Festlegen sämtlicher Bytes in dem Lesepuffer zu Null. In dem Schritt 809 wird der in Zuordnung zu der Clusternummer vorliegende Cluster von der Datei gelesen und expandiert, wenn erforderlich, und in dem Lesepuffer gespeichert. Dieser Schritt 809 wird nachfolgend vollständiger unter Bezug auf die Fig. 7 erläutert. In dem Schritt 811 werden Daten von dem Eingangspuffer zu dem Lesepuffer kopiert. Dieser Schritt kann durch Kopieren der Schreibgrößenbytes von Daten von der Stelle bei dem Eingangspufferversatz in dem Eingangspuffer zu der Stelle bei dem Clusterversatz des Lesepuffers ausgeführt werden. In dem Schritt 813 wird der Cluster in dem Lesepuffer komprimiert und zu der Datei auf der Platte geschrieben. Dieser Schritt wird nachfolgend vollständiger unter Bezug auf die Fig. 5e erläutert. Nach dem Abschließen der Schritte 815 und 813 ist diese Schreibclusterprozedur für den Schritt 707 bei Schritt 817 abgeschlossen.

Die Fig. 5d zeigt bei 719 eine Prozedur zum Berechnen der Dateigrößen-Variable. Diese Prozedur prüft, ob die Größe einer Datei erhöht ist, und wenn dies gilt, erfolgt das Angleichen der Dateigrößen-Variable. Die Variable Filegröße bezeichnet die Größe der Datei in Bytes. In dem Schritt 751 wird die Variable Abschluss Dateiversatz zu dem Dateiversatz plus der anfänglichen Eingangspuffergröße gesetzt. Da die Variable Dateiversatz den Versatz ausgehend von dem Beginn der Datei auf der Platte bezeichnet und die variable anfängliche Eingangspuffergröße die Gesamtgröße der zu schreibenden Daten ist, bezeichnet die Variable Dateiendeversatz nun das neue Ende der Datei, wenn sich die Länge der Datei erhöht hat. In dem Schritt 753 erfolgt ein Test, ob der Dateiendeversatz größer als die Dateigröße ist.

Ist der Dateiendeversatz nicht größer als die Dateigröße, so bezeichnet dies, dass sich die Länge der Datei nicht erhöht hat, und die Variable Dateigröße wird nicht geändert, und diese Prozedur ist bei 757 abgeschlossen. Ist jedoch der Dateiendeversatz größer als die Dateigröße, so wird dann in dem Schritt 755 die Variable Dateigröße rückgesetzt, so dass sie gleich der Variable Dateiendeversatz ist. Nach diesem Schritt endet die Prozedur bei dem Schritt 757.

Die Fig. 5e zeigt eine Prozedur zum Komprimieren und Schreiben eines Clusters zu der Platte. Die Fig. 5e repräsentiert entweder den Schritt 813 oder 185 der Fig. 5c. Diese Figur beginnt bei dem Schritt 948 durch entweder das Empfangen des Eingangspuffers oder des Lesepuffers. In dem Fall des Schritts 813 wird ein Cluster komprimiert und geschrieben, unter Verwendung der in dem Lesepuffer gespeicherten Daten, während in dem Fall des Schritts 815 ein Cluster unter Verwendung der Daten komprimiert und geschrieben wird, die in dem Eingangspuffer bei der Stelle Eingangspufferversatz gespeichert sind. Sobald ein Puffer empfangen wird, wird ein gewünschter Komprimierungs- Algorithmus für die Anwendung in dem Schritt 950 bezeichnet. Dieser Komprimierungs-Algorithmus wird zum Komprimieren der Daten in diesem Cluster verwendet. Die Wahl eines Komprimierungs-Algorithmus ist eine Entscheidung, die durch den Anwender, das Betriebssystem, das Dateisystem, oder irgendwie anders erfolgt. Die Wahl eines Komprimierungs- Algorithmus ist unabhängig von dieser Prozedur, und es ist zu erkennen, dass es, wie oben erläutert, möglich ist, einen unterschiedlichen Komprimierungs-Algorithmus für die Anwendung bei der Komprimierung jedes Clusters zu wählen.

In dem Schritt 952 werden die Daten in dem Empfangspuffer unter Verwendung des ausgewählten Komprimierungs-Algorithmus komprimiert, und diese komprimierten Daten werden in einen Kompressionspuffer geschrieben. In dem Schritt 954 wird bestimmt, ob die Kompression nützlich ist. In anderen Worten ausgedrückt, impliziert die Tatsache, dass weniger physikalische Blöcke zum Speichern der komprimierten Daten als der expandierten Daten erforderlich sind, dies, dass der Komprimierungs-Algorithmus wirksam ist, da er die physikalische Speichergröße der Daten reduziert hat. Andererseits kann es sein, dass der Komprimierungs- Algorithmus fähig ist, geringfügig die Größe der Daten zu reduzieren, jedoch nicht genug, um diese um die Einheit eines physikalischen Blocks zu reduzieren, oder irgendeiner anderen gewünschten Dateneinheit. In diesem Fall ist dieselbe Zahl der physikalischen Blöcke zum Speichern der komprimierten Daten wie der expandierten Daten erforderlich. Demnach wäre die Kompression nicht nützlich, und sie wird nicht verwendet.

Ist die Kompression nicht nützlich, so geht die Steuerung zu dem Schritt 975; wird bestimmt, dass die Kompression nützlich ist, so geht die Steuerung zu dem Schritt 956. In dem Schritt 975 wird die erforderliche Zahl der physikalischen Blöcke zum Speichern der Daten in dem Cluster zugewiesen. In dem Schritt 977 werden die expandierten Daten von dem Empfangspuffer zu den zugewiesenen physikalischen Blöcken auf der Platte geschrieben. In dem Schritt 979 wird die Abbildungstabelle aktualisiert, zum Abbilden der logischen Blöcke zu den neu beschriebenen physikalischen Blöcken. In dem Schritt 966 wird die Inode aktualisiert. Diese Aktualisierung kann das Aktualisieren der Größe der Datei, der Blöcke in der Datei oder andere Größen, umfassen. In dem Schritt 968 wird die aktualisierte Inode-Information zu der Platte geschrieben, für ein Zuweisen zu der Datei. In dem Schritt 970 werden die ursprünglich für diesen Cluster zugewiesenen physikalischen Blöcke freigegeben, da die neuen physikalischen Blöcke gerade geschrieben wurden. Nach dem Schritt 970 ist diese Prozedur für den Schritt 813 und 815 gemäß Fig. 5c bei 972 abgeschlossen.

Nun erfolgt ein Bezug auf den Fall, wo die Komprimierung nützlich ist, und in dem Schritt 956 wird die Zahl der physikalischen Blöcke, die zum Speichern der komprimierten Daten erforderlich ist, bestimmt. Beispielsweise dann, wenn der gewählte Komprimierungs-Algorithmus für das Reduzieren der Größe der expandierten Daten um 75% erfolgreich war, wären theoretisch lediglich 75% der zuvor verwendeten physikalischen Blöcke für die expandierten Daten zum Speichern der komprimierten Daten erforderlich. In dem Schritt 958 wird diese bestimmte Zahl der physikalischen Blöcke zugewiesen. In dem Schritt 960 werden die komprimierten Daten von dem Kompressionspuffer zu den zugewiesenen physikalischen Blöcken auf der Platte geschrieben. In dem Schritt 962 wird die Abbildungstabelle aktualisiert, zum Zeiger auf die neu beschriebenen physikalischen Blöcke. Dieser Schritt 962 ist analog dem Schritt 979.

In dem Schritt 964 wird der verwendete Komprimierungs- Algorithmus für die verbleibenden logischen Blöcke in der Abbildungstabelle zugewiesen, die dem durch die Clusternummer identifizierten Cluster zugewiesen ist. In anderen Worten ausgedrückt, muss aufgrund der Tatsache, dass der Komprimierungs-Algorithmus für das Reduzieren der Zahl der erforderlichen physikalischen Blöcke erforderlich war, eine bestimmte Zahl der logischen Blöcke nicht auf die tatsächlichen physikalischen Blöcke abgebildet werden, sondern sie kann auf ein Loch abgebildet werden. Wie oben erläutert, kann dieses Loch eine spezielle Adresse auf der Platte sein, sie kann eine illegale Plattenadresse sein, oder dergleichen. Als Beispiel können diese physikalischen Blöcke auf eine spezielle Adresse Null abgebildet werden, oder sie können auf eine illegale Adresse wie eine negative Eins oder eine negative Zwei abgebildet werden. Diese spezielle Adresse ist nicht nur zum Identifizieren der Tatsache nützlich, dass ein Komprimierungs-Algorithmus für diesen Cluster verwendet wurde, sondern ebenso zum Identifizieren des bestimmten verwendeten Komprimierungs-Algorithmus. Es ist zu erkennen, dass ein unterschiedlicher Komprimierungs-Algorithmus für jeden komprimierten Cluster verwendet werden kann, und eine eindeutige spezielle Adresse kann zum Identifizieren dieses Komprimierungs-Algorithmus verwendet werden. Nach dem Schritt 964 geht die Steuerung zu dem Schritt 966, und der Ablauf wird in der Prozedur, wie oben erläutert, fortgesetzt.

Nun ist unter Bezug auf die Fig. 6a, 6b und 6c ein Flussdiagramm 1000 gezeigt, zum Darstellen eines Lesebetriebs für eine Ausführungsform der vorliegenden Erfindung. Liest ein Anwender eine komprimierte Datei, so gewinnt das Dateisystem bei einem Dateiversatz die gespeicherte Kompressionseinheit wieder, die die Bytes bei dem Versatz enthält, expandiert die Daten und gibt sie an den Anwender zurück. Der Lesebetrieb beginnt mit dem Empfang der Eingabeparameter bei 1002. Vier Variable werden für den Lesebetrieb eingegeben: der Ausgabepuffer, die anfängliche Ausgangspuffergröße, der Dateiversatz und der Dateiöffnungsdescriptor. Der variable Ausgangspuffer ist eine Adresse, die einen Datenpuffer bezeichnet, der die von der Platte zu lesenden Daten enthält. Die anfängliche Ausgabepuffergröße bezeichnet die Größe des Ausgangspuffers in Bytes. Der Dateiversatz ist der Versatz in der Datei, bei dem die Daten gelesen werden. Der Dateiöffnungsdescriptor ermöglicht dem Lesebetrieb den Zugriff auf die Abbildungstabelle für die gelesene Datei und stellt die Dateigröße bereit. Eine weitere Variable ist von den Dateisystemmetadaten verfügbar, die Variable Clustergröße, und sie repräsentiert die Größe eines Clusters in Byte.

Ebenso wird die variable Zahl der gelesenen Bytes zu Null initialisiert.

In dem Schritt 1004 wird der Dateiversatz mit der Dateigröße verglichen. Ist der Dateiversatz größer oder gleich der Dateigröße, so zeigt dies an, dass ein Versuch zum Lesen hinter das Ende der Datei existiert, und die Leseprozedur endet bei dem Schritt 1030. Andererseits geht dann, wenn der Dateiversatz größer oder kleiner als die Dateigröße ist, dann die Steuerung zu dem Schritt 1006 über. In dem Schritt 1006 wird die Ausgangspuffergröße zunächst zu der anfänglichen Ausgangspuffergröße gesetzt. Die Ausgangspuffergröße kann ferner dann angeglichen werden, wenn bestimmt wird, dass der Lesebetrieb Daten hinter dem Ende der Datei anfordert. Ist die Ausgangspuffergröße größer als die Dateigröße minus Dateiversatz, so bedeutet dies, dass die Anforderung hinter das Ende der Datei vorliegt. Ist das so, so wird die Ausgangspuffergröße zu der Dateigröße minus Dateiversatz gesetzt.

In dem Schritt 1008 werden drei Variablen berechnet, insbesondere Startclusternummer, Endclusternummer und Clusterversatz. Die variable Startclusternummer ist der Quotient aus Dateiversatz geteilt durch Clustergröße. Die Endclusternummer ist der Quotient: Dateiversatz plus Ausgangspuffergröße minus einst, sämtlich geteilt durch die Clustergröße. Der Clusterversatz ist der Rest aus dem Dateiversatz geteilt durch die Clustergröße. Die Variable Clusterversatz bezeichnet den Ort in dem Cluster, von dem aus die Daten gelesen werden. Sobald diese Variablen berechnet sind, werden drei Variablen in dem Schritt 1010 initialisiert. Die Clusternummer bezeichnet den zu lesenden Cluster, und sie wird gleich zu der Startclusternummer gesetzt. Der Ausgangpufferversatz bezeichnet den Punkt in dem Ausgangspuffer zum Speichern der von der Platte zu lesenden Daten, und er wird zu Null initialisiert. Der Ausgangspuffer ist der Versatz in dem Ausgangspuffer zum Speichern der Daten, die von der Platte gelsen werden.

In dem Sehritt 1012 wird die Variable Lesegröße berechnet. Diese Variable bezeichnet die Zahl der in einer Iteration dieses Betriebs zu lesenden Byte, und die Lesegröße muss kleiner als oder gleich der Größe eines Clusters sein. Dieser Schritt wird detaillierter nachfolgend unter Bezug auf die Fig. 6b erläutert. In dem Schritt 1014 wird ein Cluster von der Platte gelesen. Dieser Schritt wird nachfolgend detaillierter unter Bezug auf die Fig. 6c erläutert. In dem Schritt 1016 wird die Clusternummer um Eins inkrementiert. In dem Schritt 1018 wird die Variablennummer für gelesene Bytes um die Lesegröße inkrementiert, zum Anzeigen der Zahl der Bytes, die gerade von der Platte gelesen wurden. Als nächstes erfolgt in dem Schritt 1020 ein Test, ob der letzte Cluster für den Ausgangspuffer gelesen wurde. Ist die Clusternummer größer als die Endclusternummer, so ist der Lesebetrieb abgeschlossen, und die Steuerung geht zu dem Schritt 1030. Ist dies nicht der Fall, so ist der Lesebetrieb nicht abgeschlossen, und die Steuerung bewegt sich zu dem Schritt 1022.

In dem Schritt 1022 wird die Ausgangspuffergröße um die Lesegröße dekrementiert, zum Anzeigen der von der Platte gelesenen Zahl von Bytes. In dem Schritt 1024 wird die Variable Ausgangspufferversatz um die Lesegröße inkrementiert. In dem Schritt 1026 wird die Variable Clusterversatz gleich zu Null gesetzt. Von dem Schritt 1026 verzweigt die Steuerung zurück zu dem Schritt 1012, und der Betrieb wird mit einer anderen Iteration fortgesetzt, wie oben diskutiert. In dem Schritt 1030 endet der Lesebetrieb, und die variable Nummer der gelesenen Bytes wird zu der aufrufenden Einheit zurückgegeben.

Die Fig. 6b zeigt eine Prozedur zum Implementieren des Schritts 1012 nach Fig. 6a zum Berechnen der Lesegröße, der Zahl der zu lesenden Bytes. In dem Schritt 1031 wird die Lesegröße gleich zu der Clustergröße minus dem Clusterversatz gesetzt. Die Lesegröße muss kleiner als oder gleich der Größe eines Clusters sein. In der ersten Iteration der Leseprozedur kann die Lesegröße kleiner als eine Clustergröße sein, wenn es einen Clusterversatz gibt. D. h., dann, wenn die von einer Platte zu lesenden Daten in der Mitte des Clusters beginnen. Bei nachfolgenden Iterationen durch die Leseprozedur ist die Lesegröße gleich der Größe eines Clusters, da der Clusterversatz in dem Schritt 1026 zu Null gesetzt wurde. In dem Schritt 1033 erfolgt ein Test, ob die Lesegröße größer als die Ausgangspuffergröße ist. Ist die Lesegröße nicht größer als die Ausgangspuffergröße, so bezeichnet dies, dass die auf der Platte verbleibenden und in den Ausgangspuffer zu lesenden Daten größer oder gleich einem Cluster sind, und die Lesegröße verbleibt bei der Größe eines Clusters, und die Prozess 1012 ist abgeschlossen.

Ist jedoch die Lesegröße größer als die Ausgangspuffergröße, so bezeichnet dies, dass das Ende des Ausgangspuffers erreicht wurde, und dass die verbleibenden zu lesenden Daten kleiner als die Größe eines Clusters sind. In diesem Fall wird in dem Schritt 1035 die Lesegröße gleich den verbleibenden zu lesenden Daten gesetzt, insbesondere der Ausgangspuffergröße. Es ist zu erwähnen, dass sich die Ausgangspuffergröße bei Durchführen von Iterationen durch den Lesebetrieb ändert, da die Variable Ausgangspuffergröße durch den Leseschritt im Schritt 1022 dekrementiert wird. Nach dem Schritt 1035 ist der Schritt 1012 zum Berechnen der Lesegröße abgeschlossen.

Die Fig. 6c zeigt eine Prozedur zum Ausführen des Leseclusterbetriebs, d. h. dem Schritt 1014 nach Fig. 6a. Dieser Betrieb beginnt bei dem Schritt 1051. In dem Schritt 1051 werden Daten in Zuordnung von der Clusternummer von der Platte gelesen und expandiert und in dem Lesepuffer gespeichert. Dieser Schritt 1051 wird nachfolgend vollständig unter Bezug auf die Fig. 7 erläutert. In dem Schritt 1053 wird ein Cluster der Daten von dem Lesepuffer in den Ausgangspuffer kopiert. Dieser Schritt kann durch Kopieren von Daten in den Lesepuffer ausgehend von dem Clusterversatz für die Zahl von Lesegrößebytes zu dem Ausgangspuffer bei dem Versatz-Ausgangspufferversatz ausgeführt werden. Bei dem Schritt 1055 ist dieser Schritt 1014 abgeschlosen.

Die Fig. 7 zeigt bei 900 eine Prozedur zum Lesen von Daten von einer Platte, sowie zum Expandieren, wenn es erforderlich ist, und zum Zurücklassen dieser Daten in dem Lesepuffer. Diese Prozedur 900 entspricht dem Schritt 809 der Fig. 5c und dem Schritt 1051 der Fig. 6c. Der Schritt 901 bestimmt, ob irgendwelche physikalischen Blocknummern des Clusters einen Komprimierungs-Algorithmus identifizieren. Wie oben erläutert, lässt sich ein Komprimierungs-Algorithmus durch das Vorliegen eines Lochs in der Abbildungstabelle identifizieren. Beispielsweise würde anstelle einer gültigen physikalischen Blocknummer eine spezielle Adresse, eine illegale Adresse oder dergleichen in der Abbildungstabelle auftreten, zum Anzeigen, dass ein Loch vorliegt, und dass ein Cluster komprimiert wurde.

Wird ein Kompressions-Algorithmus identifiziert, so geht die Steuerung zu dem Schritt 905 über, und anderenfalls geht die Steuerung zu dem Schritt 903 über. In dem Schritt 905 werden sämtliche physikalischen Blöcke mit einer positiven Blocknummer (oder diejenigen, die nicht als Löcher bezeichnet sind) von der Platte gelesen und in dem Kompressionspuffer gespeichert. In diesem Beispiel kann eine spezielle Adresse wie Null oder eine negative Zahl zum Anzeigen eines Lochs verwendet werden, so dass demnach irgendwelche positiven Blocknummern anzeigen, dass ein gültiger physikalischer Block mit Daten bei dieser Stelle existiert. Es ist zu erkennen, dass gültige physikalische Blöcke mit Daten nicht notwendiger Weise einer positiven physikalischen Blocknummer zugewiesen sein müssen, sondern sie können irgendeiner physikalischen Blocknummer zugewiesen sein, die nicht zum Anzeigen eines Lochs vorgegeben ist. In dem Schritt 907 werden die Daten in dem Kompressionspuffer unter Verwendung des bezeichneten Kompressions-Algorithmus expandiert, und sie werden dann in den Lesepuffer geschrieben. Nach dem Schritt 907 endet die Prozedur.

Wird ein Kompressions-Algorithmus in dem Schritt 901 nicht identifiziert, so werden in dem Schritt 903 sämtliche physikalische Blöcke mit einer positiven Blocknummer einfach direkt in den Lesepuffer ohne Durchlaufen einer Expansion gelesen. In diesem Schritt werden ebenso positive Blocknummern zum Bezeichnen der Tatsache verwendet, dass ein gültiger physikalischer Block von Daten existiert, während eine Blocknummer von Null anzeigen würde, dass ein Loch existiert. Nach dem Schritt 903 ist die Prozedur abgeschlossen.

Der eingestellte Dateigrößenbetrieb wird durch das Dateisystem entweder zum Verringern der Größe einer Datei auf der Platte oder zum Erhöhen der Größe einer Datei auf der Platte verwendet. Er kann ebenso zum Wiederbeanspruchen von Raum bei dem Ende einer Datei verwendet werden. Beispielsweise kann dann, wenn ein Anwender eine Datei in dem Speicher des Computers editiert, und die Größe der Datei verringert, dann, wenn diese Datei anschließend zu der Platte geschrieben wird, der Dateigrößeneinstellbetrieb anstelle des zuvor diskutierten Schreibbetriebs verwendet werden. Der Dateigrößeneinstellbetrieb kann auch zum Erhöhen der Dateigröße verwendet werden. Das Ergebnis des Dateigrößeneinstellbetriebs ist, dass die Größe der Datei von der alten Dateigröße zu der neuen Dateigröße geändert wird, die für den Betrieb eingegeben wird. Die neue Dateigröße kann größer als, kleiner als oder gleich der alten Dateigröße sein. Stimmen die alte Dateigröße und die neue Dateigröße überein, so werden keine Schritte ausgeführt. Andernfalls wird die Datei entweder verlängert oder gekürzt.

Die Fig. 8a zeigt bei 1100 ein Flussdiagramm zum Ausführen des Dateigrößeneinstellbetriebs. Der Dateigrößeneinstellbetrieb beginnt mit dem Empfang, als Eingabe, des Parameters neue Dateigröße, der in Byte die gewünschte Größe der neuen Datei anzeigt. In dem Schritt 1102 wird die neue Dateigröße mit der momentanen Dateigröße verglichen. Stimmen beide überein, so terminiert der Dateigrößeneinstellbetrieb. Stimmen sie nicht überein, so wird die neue Dateigröße gegen die Dateigröße in dem Schritt 1103 verglichen. Ist die neue Dateigröße größer als die Dateigröße, so bezeichnet dies, dass die Datei verlängert werden muss, und es wird der Verlängerungsschritt 1107 ausgeführt. Dieser Schritt wird nachfolgend detaillierter unter Bezug auf die Fig. 8c erläutert. Ist die neue Dateigröße kleiner als Dateigröße (File Size), so bezeichnet dies, dass die Datei im Hinblick auf die Größe zu verringern ist, und der Verkürzungsschritt 1105 wird ausgeführt. Dieser Schritt wird nachfolgend detaillierter unter Bezug auf die Fig. 8b erläutert. In dem Schritt 1109 wird die variable Dateigröße zu der neuen Dateigröße rückgesetzt. In dem Schritt 1111 wird die Inode-Information für die Datei aktualisiert, und diese Inode wird dann zu der Platte geschrieben. Nach dem Schritt 1111 terminiert der Dateigrößeneinstellbetrieb.

Die Fig. 8b zeigt ein Flussdiagramm zum Ausführen des Dateikürzungsschritts 1105 von der Fig. 8a. Das Ziel des Abkürzungsschritts ist das Setzen zu Null der Bytes nach dem Zeiger Neu Dateigröße zu der Ende des Clusters. Dann werden alle Cluster nach dem Cluster mit der Versatz-Neue Dateigröße freigegeben. In dem Schritt 1151 werden die Variablen Schreibgröße und Schreibversatz bezeichnet. Die Variable Schreibgröße repräsentiert einen Zeiger, der die Stelle in der Datei anzeigt, von der die Bytes zu Null zu setzen sind. Die Variable Schreibversatz wird zu der neuen Dateigröße gesetzt. Die Variable Schreibgröße repräsentiert die Zahl der verbleibenden Bytes, bei Dateiversatz-Neue Dateigröße bis zu dem Ende des Clusters, die zu Null zu setzen sind. Die temporäre Variable Temporäre Schreibgröße wird gleich zu der Clustergröße minus dem Rest der neuen Dateigröße geteilt durch die Clustergröße gesetzt. Als nächstes wird dann, wenn die neue Dateigröße Null gleicht oder wenn die temporäre Schreibgröße der Clustergröße gleicht, dann die Schreibgröße zu Null gesetzt. Andernfalls wird die Schreibgröße zu der temporären Schreibgröße gesetzt.

Gleicht die Schreibgröße Null, so sind keine Bytes zu Null zu setzen, und die Cluster lassen sich freigeben. In dem Schritt 1153 geht dann, wenn Schreibgröße gleich Null ist, die Steuerung zu dem Schritt 1159 über, und ist dies nicht der Fall, so geht die Steuerung zu dem Schritt 1155 über. In dem Schritt 1155 wird der Schreibpuffer rückgesetzt. Der Schreibpuffer hat die Größe gleich der Clustergröße. In dem Schritt 1157 werden Schreibgröße-Zahl von Bytes von dem Schreibpuffer zu der Datei ausgehend von dem Schreibversatz geschrieben. Aufgrund der Tatsache, dass dies ein Schreibbetrieb ist, kann der Schritt 1157 unter Verwendung des Schreibbetriebs implementiert werden, der bei 700 in den Fig. 56a bis 5e gezeigt ist. Vier Variablen werden zu diesem Schreibbetrieb übergeben. Wie oben beschrieben, erfordert das Flussdiagramm 700 vier Eingangsgrößen, insbesondere eine Eingabepuffer, eine Eingabepuffergröße, einen Dateiversatz und einen Dateiöffnungsdescriptor. In dem Schritt 1157 entspricht der Schreibpuffer den Eingangspuffer, die Schreibgröße entspricht der Eingangspuffergröße, der Schreibversatz entspricht dem Dateiversatz, und der Dateiöffnungsdescriptor, der die momentane Datei bezeichnet, die zu dem obigen Dateigrößeneinstellbetrieb eingegeben wird, wird zu dem Schreibbetrieb übergeben.

Die Schritte 1159 bis 1167 repräsentieren die Schritte, durch die die verbleibenden Cluster nach dem Cluster mit der neuen Dateigröße freigegeben werden. In dem Schritt 1159 werden die Variable Startclusternummer und Endclusternummer berechnet. Diese Variablen lassen sich so, wie oben erläutert, berechnen, beispielsweise wie in dem Schritt 701 nach Fig. 5a. Ist jedoch die Schreibgröße gleich Null, so sollte auch die Clusternummer um Eins dekrementiert werden. In dem Schritt 1161 wird die Clusternummer um Eins inkrementiert. In dem Schritt 1163 wird die Clusternummer mit der Endclusternummer verglichen. Ist die Clusternummer größer als die Endclusternummer, so ist der Schritt 1105 abgeschlossen ist dies nicht der Fall, so bezeichnet dies, dass ein Cluster freizugeben ist. In dem Schritt 1165 wird die Blockabbildungsinformation für diesen Cluster wiedergewonnen. Dieser Prozess kann so, wie oben erläutert, ausgeführt werden, beispielsweise wie in dem Schritt 801 nach Fig. 5c. Ebenso werden die ursprünglichen Blöcke in diesem Cluster freigegeben. In dem Schritt 1167 wird die Abbildungstabelle aktualisiert, und sämtliche Blöcke in diesem momentanen Cluster werden gleich zu Null gesetzt. Im wesentlichen werden diejenigen Blöcke, die nun Null sind, als Löcher markiert. Nach dem Schritt 1167 wird die Schleife zu dem Schritt 1161 fortgesetzt, die Clusternummer wird zum Bezeichnen des nächsten Clusters um Eins inkrementiert, und der Betrieb wird so, wie oben beschrieben, fortgesetzt.

Die Fig. 8c zeigt den Schritt 1107 von der Fig. 8a, und dies ist der Dateiverlängerungsschritt. Das Ziel dieses Dateiverlängerungsschritts, ist das zu Null setzen sämtlicher Bytes nach der alten Dateigröße zu dem Ende des Clusters. Dann werden die Blöcke in jedem der Cluster nach dem Cluster mit dem Versatz der alten Dateigröße als Löcher markiert. In dem Schritt 1131 werden die Variablen Schreibgröße und Schreibversatz berechnet. Die Variable Schreibversatz repräsentiert einen Zeiger, der eine Stelle nach der Datei bezeichnet, von der aus die Bytes zu Null zu setzen sind. Die Variable Schreibversatz ist gleich der neuen Dateigröße. Die Variable Schreibversatz repräsentiert die Zahl der verbleibenden Bytes bei dem Dateiversatz-Neue Dateigröße bis zu dem Ende des Clusters, die zu Null zu setzen sind. Die Variable Schreibversatz wird gleich zu der alten Dateigröße plus Eins gesetzt. Als nächstes wird die temporäre Variable Temporäre Schreibgröße gleich zu der Clustergröße minus dem Rest der neuen Dateigröße geteilt durch die Clustergröße gesetzt. Als nächstes wird dann, wenn die alte Dateigröße gleich Null ist oder wenn die temporäre Schreibgröße gleich der Clustergröße ist, dann die Schreibgröße zu Null gesetzt. Andernfalls wird die Schreibgröße gleich zu der temporären Schreibgröße gesetzt.

Gleicht die Schreibgröße Null, so sind keine Bytes zu Null zu setzen, und die Cluster lassen sich als Löcher markieren. Ist in dem Schritt 1133 die Schreibgröße gleich Null, so geht die Steuerung zu dem Schritt 1139 über, und ist dies nicht der Fall, so geht die Steuerung zu dem Schritt 1135 über. In dem Schritt 1135 wird der Schreibpuffer rückgesetzt. Der Schreibpuffer hat eine Größe gleich der Clustergröße. In dem Schritt 1137 wird eine Zahl von Schreibgrößen Byte von dem Schreibpuffer zu der Datei geschrieben, startend bei dem Schreibversatz. Da dies ein Schreibbetrieb ist, lässt sich der Schritt 1137 unter Verwendung des Schreibbetriebs implementieren, der bei 700 in den Fig. 5a bis 5e gezeigt ist. Vier Variablen werden zu diesem Schreibbetrieb übergeben. Wie oben beschrieben, erfordert das Flussdiagramm 700 vier Eingabegrößen, insbesondere einen Eingabepuffer, eine Eingabepuffergröße, einen Dateiversatz und einen Dateiöffnungsdescriptor. In dem Schritt 1137 entspricht Schreibpuffer dem Eingangspuffer, Schreibgröße entspricht der Eingangspuffergröße, Schreibversatz entspricht dem Dateiversatz, und der Dateiöffnungsdescriptor, der die momentane Datei identifiziert, die gemäß dem oben festgelegten Dateigrößenbetrieb eingegeben wird, wird ebenso zu dem Schreibbetrieb übergeben. Nach dem Abschließen des Schreibbetriebs geht die Steuerung zu dem Schritt 1139 über.

Die Schritte 1139 bis 1147 führen die Funktion zum Markieren sämtlicher Blöcke in den Clustern ndach dem Cluster mit der Variable Alte Dateigröße zu Löchern aus. In dem Schritt 1139 werden die Variablen Startclusternummer und Endclusternummer berechnet. Diese Variablen lassen sie wie oben für den Schritt 701 gemäß Fig. 5a berechnen. Ist jedoch die Schreibgröße gleich Null, so sollte die Clusternummer um Eins dekrementiert werden. In dem Schritt 1141 wird die Clusternummer um Eins inkrementiert. In dem Schritt 1143 wird die Clusternummer mit der Endclusternummer verglichen. Ist die Clusternummer größer als die Endclusternummer, dann ist der Schritt 1107 abgeschlossen. Ist dies nicht der Fall, so müssen mehr Cluster als Löcher markiert werden. In dem Schritt 1145 werden sämtliche Blocknummern für diesen Cluster zu Null gesetzt, was bedeutet, dass diese Blöcke Löcher sind. In dem Schritt 1147 wird die Abbildungstabelle aktualisiert, zum Reflektieren der Tatsache, dass diese Blöcke als Löcher markiert sind. Nach dem Schritt 1147 wird die Schleife zu dem Schritt 1141 fortgesetzt, die Clusternummer wird um Eins zum Anzeigen des nächsten Clusters inkrementiert, und der Betrieb wird fortgesetzt.

Die vorliegende Erfindung, wie oben beschrieben, setzt zahlreiche Prozessschritte im Zusammenhang mit in Computersystemen gespeicherten Daten ein. Diese Schritte sind diejenigen, die eine physikalische Manipulation von physikalischen Einheiten erfordern. Üblicherweise nehmen diese, obgleich nicht erforderlich, Größen die Form elektrischer oder magnetischer Signale ein, mit der Fähigkeit für eine Speicherung, einer Übertragung, einer Kombination, eines Vergleichs oder einer andersartigen Manipulation. Es ist manchmal günstig, prinzipiell aus Gründen einer gemeinsamen Anwendung, auf diese Signal als Bits, Werte, Elemente, Variable, Zeichen, Datenstrukturen oder dergleichen Bezug zu nehmen. Es ist jedoch zu erwähnen, dass all diese und ähnliche Begriffe mit den geeigneten physikalischen Größen in Zusammenhang zu bringen sind, und lediglich bequeme Markierungen angewandt auf diese Größen darstellen.

Ferner erfolgt ein Bezug auf die ausgeführten Manipulationen oft im Hinblick auf Begriffe wie Identifizieren, Ablauf oder Vergleich. All die Betriebsschritte, die hier beschrieben sind und die einen Teil der vorliegenden Erfindung bilden, sind Maschinenbetriebsschritte. Nützliche Maschinen zum Ausführen der Betriebsschritte der vorliegenden Erfindung umfassen digitale Universalrechner oder andere ähnliche Einrichtungen. In sämtlichen Fällen ist eine Unterscheidung zu beachten, zwischen dem Verfahren der Betriebsschritte während dem Betrieb eines Computers und dem Verfahren zum Berechnen selbst. Die vorliegende Erfindung betrifft die Verfahrensschritte für den Betrieb eines Computers bei Verarbeitung elektrischer oder anderer elektrischer Signale zum Erzeugen anderer gewünschter physikalischer Signale.

Die vorliegende Erfindung betrifft auch ein Gerät zum Ausführen dieser Betriebsschritte. Dieses Gerät kann speziell für die erforderlichen Zwecke konstruiert sein, oder es kann ein Universalrechner sein, selektiv aktiviert oder rekonfiguriert durch ein in einem Computer gespeichertes Computerprogramm. Der hier dargestellte Prozess ist nicht inhärent auf irgendeinem bestimmten Computer oder ein anderes Gerät bezogen. Insbesondere können zahlreiche Universalmaschinen mit Programmen verwendet werden, die in Übereinstimmung mit den hier gegebenen technischen Lehren geschrieben sind, oder es kann bequemer sein, ein spezialisierteres Gerät zum Ausführen der erforderlichen Verfahrensschritte zu konstruieren. Die erforderliche Struktur für eine Vielzahl dieser Maschinen ergibt sich anhand der oben gegebenen Beschreibung.

Zusätzlich betrifft die vorliegende Erfindung ferner ein computer-lesbares Medium, das Programmanweisungen zum Ausführen zahlreicher computer-implementierter Betriebsschritte umfasst. Das Medium und die Programmbefehle können diejenigen sein, die speziell für die Zwecke der vorliegenden Erfindung entworfen und konstruiert sind, oder sie können von der Art sein, die für die im technischen Gebiet der Computer-Software Vertrauten allgemein bekannt und verfügbar sind. Beispiele für ein computer-lesbares Medium umfassen, ohne hierauf beschränkt zu sein, Magnetmedien wie Festplatten, Floppy Disks und Magnetband; optische Medien wie CD-ROM Platten; magneto-optische Medien wie Floppy/optische Platten; und Hardware-Einrichtungen, die speziell zum Speichern und Ausführen der Programmbefehle konfiguriert sind, beispielsweise Nurlesespeicher-Einrichtungen (ROM) oder Speicher mit wahlfreiem Zugriff (RAM). Beispiele der Programmbefehle umfassen Maschinencode, beispielsweise erzeugt durch einen Compiler, und Dateien mit Code auf höherer Ebene, die sich durch den Computer unter Verwendung eines Interpretierers ausführen lassen.

Die Fig. 9 stellt ein typisches Computersystem in Übereinstimmung mit der vorliegenden Erfindung dar. Das Computersystem 100 enthält eine Zentralverarbeitungseinheit 102 (CPU), gekoppelt mit Speichereinrichtungen umfassend einen Nurlesespeicher 104 (ROM) und einen Speicher mit wahlfreiem Zugriff 106 (RAM). Wie im Stand der Technik bekannt, wirkt der ROM 104 zum Transferieren von Daten und Befehlen in einer Richtung zu der CPU, und der RAM 106 wird typischerweise zum Transferieren von Daten und Befehlen in bidirektionaler Weise verwendet. Eine Massenspeichereinrichtung 108 ist ebenso bidirektional mit der CPU 102 verbunden, und sie stellt zusätzliche Datenspeicherkapazität bereit. Die Massenspeichereinrichtung 108 kann zum Speichern von Programmen, Daten und dergleichen verwendet werden, und sie kann die Form eines magnetischen oder Papierbandlesegeräts oder irgendeiner allgemein bekannten Einrichtung annehmen. Es ist zu erkennen, dass die in der Massenspeichereinrichtung 108 gehaltene Information in geeigneten Fällen in Standardweise als Teil des RAM 105 als virtueller Speicher enthalten sein kann. Eine spezifische Massenspeichereinrichtung, beispielsweise ein CD-RAM 114, kann ebenso unidirektional Daten zu der CPU führen.

Die CPU 102 ist auch mit einer oder mehreren Eingabe/Ausgabe- Einrichtungen 110 gekoppelt, die, ohne hierauf beschränkt zu sein, Einrichtungen umfassen kann, wie Videomonitore, Trackballs, Mauseinheiten, Tastaturen, Mikrophone, berührungsempfindliche Anzeigen, Transducer-Kartenlesegeräte, magnetische oder Papierband-Lesegeräte, Tabletts, Stifte, Sprach- und Handschrift-Erkennungseinheiten oder andere allgemein bekannte Eingabeeinrichtungen, beispielsweise selbstverständlich andere Computer. Schließlich kann die CPU 102 optional mit einem Computer oder eine Telekommunikationsnetz gekoppelt sein, unter Verwendung einer Netzverbindung, wie allgemein bei 112 gezeigt. Mit einer derartigen Netzverbindung wird in Betracht gezogen, dass die CPU Information von dem Netz empfangen kann, oder Information zu dem Netz im Verlauf des Ausführens der obenbeschriebenen Verfahrensschritte ausgeben könnte. Die oben beschriebenen Einrichtungen und Materialien sind für die mit Computer- Hardware und Software vertrauten Fachleute allgemein bekannt.

Obgleich die vorangehende Erfindung detailliert für Zwecke der Klarheit des Verständnisses beschrieben wurde, ist erkenntlich, dass bestimmte Änderungen und Modifikationen in dem Schutzbereich der angefügten Patentansprüche praktisch umgesetzt werden können. Beispielsweise kann eine komprimierte Datei zu irgendeinem einem Computer zugewiesenen Speichermedium geschrieben werden. Weiterhin müssen Daten nicht in Einheiten von Clustern komprimiert werden, sondern sie können auf einer Dateibasis komprimiert werden, oder sie können auf der Basis einer Einheit kleiner als ein Cluster wie einem Block oder einer anderen Einheit komprimiert werden. Ferner kann das Vorliegen eines "Lochs" in der Abbildungstabelle durch irgendeine Notation bezeichnet werden, die anzeigt, dass ein voller physikalischer Block nicht zugewiesen wird. Ein gültiger physikalischer Block kann durch irgendeine Zahl bzw. Nummer repräsentiert werden, die in irgendeiner Weise einen Abschnitt des Speichers auf dem Speichermedium anzeigt. Ferner ist bei der beschriebenen Ausführungsform das Verteilsystem so strukturiert, dass die Clustergröße für jede Datei dieselbe ist. Jedoch ist zu erkennen, dass sich die vorliegende Erfindung auch im Zusammenhang mit Dateisystemen verwenden lässt, die unterschiedlichen Dateien das Verwenden unterschiedlicher Clustergrößen ermöglicht. Demnach sind die beschriebenen Ausführungsformen als illustrativ und nicht einschränkend heranzuziehen, und die Erfindung sollte nicht auf die hier gegebenen Details eingeschränkt sein, sondern sie sollte durch die folgenden Ansprüche und deren vollständigen Äquivalente definiert sein.


Anspruch[de]

1. Computer-implementiertes Verfahren zum Speichern von Daten (700) in einem Dateisystem (200) mit einer Abbildungstabelle (305), ausgebildet zum Abbilden logischer Speicherblöcke (401) in physikalische Speicherblöcke (420), wobei das Verfahren folgende Schritte enthält:

Anfordern, dass ein Segment von Daten in einen physikalischen Speicher geschrieben wird, wobei das Segment der Daten ausgewählten logischen Speicherblöcken zugewiesen ist;

Komprimieren (815, 813) des Segments der Daten in komprimierte Daten derart, dass die komprimierten Daten weniger Blöcke des Speichers als das Segment der Daten belegt;

Schreiben (707) der komprimierten Daten in den physikalischen Speicher, wobei die komprimierten Daten zumindest in einen physikalischen Speicherblock geschrieben werden; und

Aktualisieren (997, 962) der Aktualisierungstabelle (305) derart, dass jeder physikalische Speicherblock, der den komprimierten Daten zugewiesen ist, abgebildet wird, durch einen Abbildungstabelleneintrag, entsprechend einem der ausgewählten logischen Speicherblöcke, und dass jeder der ausgewählten logischen Speicherblöcke, der nicht irgendeinem der physikalischen Speicherblöcke zugewiesen ist, auf einen Lochidentifizierer abgebildet wird, der nicht irgendeinem physikalischen Speicherblock entspricht.

2. Verfahren nach Anspruch 1, wobei der Lochidentifizierer den Komprimierungs-Algorithmus identifiziert, der zum Komprimieren des Segments der Daten verwendet wird.

3. Verfahren nach Anspruch 1 oder 2, wobei:

das Segment der Daten eine Vielzahl von Cluster enthalten kann, und das Dateisystem zum Verarbeiten von Clustern ausgebildet ist, wobei jeder Cluster einer Vielzahl von Blöcken des logischen Speichers entspricht; und

die Komprimierungs- und Schreibschritte in einem Cluster durch eine Cluster-Vorgehensweise ausgeführt werden.

4. Verfahren nach Anspruch 3, wobei:

für die Anwendung eine Vielzahl von Lochidentifizierern zur Verfügung steht; und

der für in Zuordnung zu einem bestimmten Cluster ausgewählte Lochidentifizierer den Komprimierungs- Algorithmus identifiziert, der zum Komprimieren der Daten in diesem Cluster verwendet wird.

5. Verfahren nach Anspruch 4, wobei unterschiedliche Komprimierungs-Algorithmen zum Komprimieren unterschiedlicher Cluster in dem Segment der Daten verwendet werden.

6. Verfahren nach Anspruch 1, wobei das Dateisystem zum Verarbeiten von Clustern ausgebildet ist, und wobei jeder Cluster einer Vielzahl logischer Speicherblöcke entspricht, und wobei die ausgewählten Speicherblöcke eine Vielzahl von Clustern überspannen können, und das Verfahren ferner folgende Schritte enthält:

Bestimmen (805), ob das Segment der Daten bei einer Zwischenstelle in einem ersten der Vielzahl der Cluster beginnt, wobei dann, wenn bestimmt wird, dass das Segment der Daten bei einer Zwischenstelle beginnt, das Verfahren ferner den Schritt zum Ausführen eines Teilcluster-Schreibbetriebs unter Verwendung des ersten Clusters als momentaner Cluster enthält, wobei der Teilcluster-Schreibbetrieb die folgenden Teilschritte enthält:

a) Lesen von Daten (809) in Zuordnung zu dem momentanen Cluster von dem physikalischen Speicher in einen Lesepuffer derart, dass die momentanen Clusterdaten in dem Lesepuffer in einem expandierten Format gespeichert werden,

b) Kopieren (811) eines Abschnitts des Segments der Daten in Zuordnung zu dem momentanen Cluster in den Lesepuffer nach dem Abschluss des Leseschritts,

c) Komprimieren der in dem Lesepuffer gespeicherten Daten (952) nach dem Kopierschritt,

d) Schreiben (960) der komprimierten Daten in den physikalischen Speicher, und

e) Aktualisieren der Abbildungstabelle (962) derart, dass jeder physikalische Speicherblock in Zuordnung zu den komprimierten Daten durch einen Abbildungstabelleneintrag abgebildet wird, gemäß dem einen der ausgewählten logischen Speicherblöcke, der dem momentanen Cluster zugewiesen ist, und dass jeder der ausgewählten logischen Speicherblöcke, zugewiesen zu dem momentanen Cluster, der nicht irgendeinem der physikalischen Speicherblöcke zugewiesen ist, zu einem Lochidentifizierer abgebildet wird, der nicht irgendeinem physikalischen Speicherblock entspricht.

7. Verfahren nach Anspruch 6, ferner enthaltend den Schritt zum Bestimmen, ob der momentane Cluster in einem komprimierten Format gespeichert ist, und Expandieren der momentanen Clusterdaten für ein Speichern in dem Lesepuffer, wenn bestimmt wird, dass der momentane Cluster in einem komprimierten Format gespeichert ist.

8. Verfahren nach Anspruch 6 oder 7, wobei der Lochidentifizierer den Komprimierungs-Algorithmus identifiziert, der zum Komprimieren der Daten verwendet wird, die dem momentanen Cluster zugewiesen sind.

9. Verfahren nach Anspruch 7 oder 8, wobei:

eine Vielzahl von Lochidentifizierern für die Anwendung zur Verfügung stehen; und

der Lochidentifizierer, der für die Anwendung in Zuordnung zu einem bestimmten Cluster ausgewählt wird, den Komprimierungs-Algorithmus identifiziert, der zum Komprimieren der Daten in diesem Cluster verwendet wird.

10. Verfahren nach einem der Ansprüche 6 bis 9, wobei unterschiedliche Komprimierungs-Algorithmen zum Komprimieren unterschiedlicher Cluster in dem Segment der Daten verwendet werden.

11. Verfahren nach einem der Ansprüche 6 bis 10, ferner enthaltend die Schritte:

Bestimmen, ob das Segment der Daten bei einer Zwischenstelle in einem zweiten der Vielzahl der Cluster endet, wobei dann, wenn bestimmt wird, dass das Segment der Daten bei einer Zwischenstelle endet, das Verfahren ferner den Schritt zum Ausführen des Teilcluster- Schreibbetriebs unter Verwendung des zweiten Clusters als momentanen Cluster enthält.

12. Verfahren nach einem der Ansprüche 6 bis 11, ferner enthaltend die Schritte:

Bestimmen, ob einer der Vielzahl der Cluster ein Vollcluster ist, wobei ein Vollcluster einer ist, bei dem das Segment der geschriebenen Daten weder bei einer Zwischenstelle in dem Cluster beginnt noch dort endet, wobei dann, wenn bestimmt wird, dass einer der Vielzahl der Cluster ein Vollcluster ist, das Verfahren ferner die Schritte enthält:

f) Komprimieren der Daten (952) in Zuordnung zu dem Vollcluster,

g) Schreiben der komprimierten Daten (916) in dem physikalischen Speicher,

h) Aktualisieren der Abbildungstabelle (962) derart, dass jeder physikalische Speicherblock in Zuordnung zu den komprimierten Daten zu einem zugewiesenen logischen Speicherblock abgebildet wird, der dem Vollcluster zugewiesen ist, und dass jeder logische Speicherblock, der dem Vollcluster zugewiesen ist, der nicht irgendeinem der physikalischen Speicherblöcke zugewiesen wird, auf einen Lochidentifizierer abgebildet wird, der nicht irgendeinem physikalischen Speicherblock in Zuordnung zu den komprimierten Daten entspricht.

13. Computer-implementiertes Verfahren zum Wiedergewinnen von Daten (1000) in einem Dateisystem (200) mit einer Abbildungstabelle (305), ausgebildet zum Abbilden logischer Speicherblöcke auf physikalische Speicherblöcke, wobei das Verfahren folgende Schritte enthält:

Anfordern, dass ein Segment von Daten von dem physikalischen Speicher gelesen wird (1014), wobei das Segment der Daten ausgewählten logischen Speicherblöcken zugewiesen ist; und

Bestimmen (901), unter Bezugnahme auf die Abbildungstabelle, ob irgendeiner der ausgewählten logischen Speicherblöcke auf einen Lochidentifizierer abgebildet wird, der identifiziert, dass das Segment der Daten in komprimierter Form in den physikalischen Speicher gespeichert wird, wobei dann, wenn bestimmt wird, dass das Segment der Daten in komprimierter Form gespeichert wird, die folgenden Teilschritte ausgeführt werden:

a) Lesen (905), von dem physikalischen Speicher in einen Kompressionspuffer, sämtlicher physikalischer Speicherblöcke, die den ausgewählten logischen Speicherblöcken des Segments der Daten zugewiesen sind, und

b) Expandieren (907) der physikalischen Speicherblöcke, gespeichert in dem Kompressionspuffer, derart, dass das Segment der Daten dann in expandierter Form in den Kompressionspuffer gespeichert wird.

14. Verfahren nach Anspruch 13, wobei der Lochidentifizierer den Komprimierungs-Algorithmus identifiziert, der zum Komprimieren des Segments der Daten verwendet wird.

15. Verfahren nach Anspruch 13 oder 14, wobei:

das Segment der Daten eine Vielzahl von Clustern enthalten kann, und das File-System zum Verarbeiten von Clustern ausgebildet ist, wobei jeder Cluster einer Vielzahl von Blöcken des logischen Speichers entspricht; und

die Lese- und Expandierschritte in einer Cluster für- Cluster-Weise ausgeführt werden.

16. Verfahren nach Anspruch 15, wobei:

für die Anwendung eine Vielzahl von Lochidentifizierern zur Verfügung steht, und die logischen Speicherblöcke in der Abbildungstabelle gemäß dem einen bestimmen Cluster zumindest zu einem Lochidentifizierer abgebildet werden, der den Kompressions-Algorithmus anzeigt, der zum Komprimieren von Daten in diesem bestimmten Cluster verwendet wird.

17. Verfahren nach Anspruch 15 oder 15, wobei unterschiedliche Kompressions-Algorithmen zum Komprimieren unterschiedlicher Daten in dem Segment der Daten verwendet werden.

18. Verfahren nach einem der Ansprüche 13 bis 17, wobei dann, wenn bestimmt wird, dass das Segment der Daten nicht in komprimierter Form gespeichert wird, ein Lesen (903) von dem physikalischen Speicher in den Lesepuffer erfolgt, und zwar sämtlicher physikalischer Speicherblöcke, die den ausgewählten logischen Speicherblöcken des Segments der Daten zugewiesen sind, so dass das Segment der Daten dann in einem expandierten Format in dem Lesepuffer gespeichert wird.

19. Computergerät (100) für die Anwendung bei der Kompression und Expansion eines Datensegments in einem Dateisystem, wobei das Datensegment einer ausgewählten Vielzahl logischer Speicherblöcke zugewiesen ist, wobei das Computergerät enthält:

eine Zentralverarbeitungseinheit (102);

einen Speicher mit wahlfreiem Zugriff (106) in Kommunikation mit der Zentralverarbeitungseinheit;

eine Massenspeichereinrichtung (108) in Kommunikation mit der Zentralverarbeitungseinheit;

eine Abbildungstabelle (305), ausgebildet zum Abbilden der ausgewählten logischen Speicherblöcke des Datensegments zu zugewiesenen physikalischen Speicherblöcken der Massenspeichereinrichtung derart, dass dann, wenn das Datensegment in einer komprimierten Form in der Massenspeichereinrichtung gespeichert wird, das komprimierte Datensegment weniger physikalische Speicherblöcke belegt als das expandierte Datensegment, und derart, dass jeder physikalische Speicherblock, der den komprimierten Daten zugewiesen ist, eine Abbildung durch einen Abbildungstabelleneintrag erfährt, gemäß dem einen der ausgewählten logischen Speicherblöcke, und dass jeder der ausgewählten logischen Speicherblöcke, der nicht irgendeinem der physikalischen Speicherblöcke zugewiesen wird, auf einen Lochidentifizierer abgebildet wird, der nicht irgendeinem physikalischen Speicherblock entspricht.

20. Gerät nach Anspruch 19, wobei der Lochidentifizierer den Kompressions-Algorithmus identifiziert, der zum Komprimieren des Segments der Daten verwendet wird.

21. Gerät nach Anspruch 19, wobei:

das Segment der Daten eine Vielzahl von Clustern enthält, wobei jeder Cluster einer Vielzahl von Blöcken des logischen Speichers entspricht;

eine Vielzahl der Lochidentifizierer für die Anwendung verfügbar ist; und

der für die Anwendung in Zuordnung zu einem bestimmten Cluster ausgewählte Lochidentifizierer den zum Komprimieren der Daten in diesem Cluster verwendeten Kompressions-Algorithmus identifiziert.

22. Gerät nach Anspruch 21, wobei unterschiedliche Kompressions-Algorithmen zum Komprimieren unterschiedlicher Cluster in dem Segment der Daten verwendet werden.

23. Computerprogrammprodukt mit einem computer-anwendbaren Medium mit einem hierauf ausgeführten computer-lesbaren Code zum Komprimieren und Expandieren von Daten in einem Dateisystem eines Computers, wobei das Dateisystem (200) eine Abbildungstabelle (305) enthält, ausgebildet zum Abbilden logischer Speicherblöcke in physikalische Speicherblöcke, wobei das Computerprogrammprodukt den folgenden computer-lesbaren Programmcode zum Bewirken von Aktionen in dem Computer enthält:

Programmcode zum Anfordern, dass ein Segment von Daten zu einem physikalischen Speicher geschrieben wird, wobei das Segment der Daten ausgewählten logischen Speicherblöcken zugewiesen ist;

Programmcode zum Komprimieren des Segments der Daten in komprimierte Daten derart, dass die komprimierten Daten weniger Blöcke des Speichers als das Segment der Daten bewegen;

Programmcode zum Schreiben der komprimierten Daten in den physikalischen Speicher, wobei die komprimierten Daten zumindest in einen physikalischen Speicherblock geschrieben werden; und

Programmcode zum Aktualisieren der Abbildungstabelle derart, dass jeder physikalische Speicherblock in Zuordnung zu den komprimierten Daten durch einen Abbildungstabelleneintrag zu einem entsprechenden der ausgewählten logischen Speicherblöcke abgebildet wird und jeder der ausgewählten logischen Speicherblöcke, der nicht irgendeinem der physikalischen Speicherblöcke zugeordnet ist, zu einem Lochidentifizierer abgebildet wird, der nicht irgendeinem physikalischen Speicherblock entspricht.

24. Computerprogrammprodukt nach Anspruch 23, wobei der Lochidentifizierer den zum Komprimieren des Segments der Daten verwendeten Komprimierungs-Algorithmus identifiziert.

25. Computerprogrammprodukt nach Anspruch 23 oder 24, wobei:

das Segment der Daten eine Vielzahl von Clustern enthalten kann und das Dateisystem zum Verarbeiten der Cluster ausgebildet ist, wobei jeder Cluster einer Vielzahl von Blöcken des logischen Speichers entspricht; und

das Komprimieren und Schreiben des Segments der Daten in einer Cluster für-Cluster-Weise ausgeführt wird.

26. Computerprogrammprodukt nach Anspruch 25, wobei:

für die Anwendung eine Vielzahl von Lochidentifizierern zur Verfügung stehen; und

der für die Anwendung in Zuordnung zu einem bestimmten Cluster ausgewählte Lochidentifizierer den zum Komprimieren der Daten in diesem Cluster verwendeten Kompressions-Algorithmus identifiziert.

27. Computerprogrammprodukt nach Anspruch 26, wobei unterschiedliche Kompressions-Algorithmen zum Komprimieren unterschiedlicher Cluster in dem Segment der Daten verwendet werden.

28. Computer-implementiertes Verfahren zum Übertragen des Computerlesbaren Programmcodes nach einem der Ansprüche 23 bis 27, wobei das Verfahren folgenden Schritte enthält:

Speichern des Programmcodes auf einem Computeranwendbaren Medium;

Empfangen einer Anforderung für die Übertragung des Programmcodes; und

Übertragen des Programmcodes über ein Netzwerk zu einer Fernstelle.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com