Eigene Implementierung für das Kopieren von Dateien

[Phoenixz]

Hallo CB-Community,

ich komme gleich auf den Punkt. Mir geht es um eine eigene Implementierung eines Kopiervorgangs für Dateien (Also nicht etwa die Verwendung der Windows-Kopierfunktion). Ich würde das ganze gerne auf Pseudocode Niveau halten, da es mir nur um die Theorie geht und die ist ja bekanntlich Sprachenunabhängig.

Also nun zu meiner Frage: Das Kopieren von Dateien kann man auf das „Grundproblem“ herunterbrechen, den Inhalt eines (Quell-)Streams in ein (Ziel-)Stream zu schreiben. Ein einfacher Lösungsansatz würde dabei wie folgt vorgehen:

Lese X Bytes aus dem Quellstream in ein Buffer, 
schreibe anschließend den Buffer in den Zielstream. 
Wiederhole diesen Vorgang solange noch Bytes im Quellstream zu lesen sind.

(Ok, das ist nicht gerade Pseudo Code, doch das sollte hoffentlich auch verständlich sein. Halt ganz normales paketweises kopieren).

Was mir jetzt aber aufgefallen ist, ist die Tatsache, dass man immer einen Wechsel hat zwischen Lesen und Schreiben.
Also habe ich mir heute überlegt ob es nicht effizienter wäre das Ganze auf zwei Threads zu verteilen. Der eine liest ständig in eine Queue (ggf. noch beschränken auf maximale Anzahl der Pakete) und der andere nimmt sich immer ein Paket aus der Queue raus und schreibt es in den Zielstream. Liegt Quelldatei und Zielverzeichnis (bzw. Zieldatei) auf der gleichen Festplätte würde das zwar nicht so viel bringen (da die Festplatte ja kein gleichzeitiges Lesen und Schreiben ermöglicht), aber wenn dies nicht der Fall ist (also die Dateien auf unterschiedlichen Festplatten liegen) müsste doch ein Geschwindigkeitsvorteil vorhanden sein.
Ich konnte leider keine Informationen zum Thema finden, „Wie implementiert man das Kopieren von Dateien richtig“ ^^. Sind also meine Gedankengänge korrekt und empfiehlt sich eine Multithreading-Lösung zum Kopieren?

Vielen Dank,
Daniel

 

[toeffi]

Und was ist deiner Lösung jetzt individuell?
Die Lösung mit den Threads ist nicht unbedingt schneller. Was ist wenn der Lesende Thread schneller ist als der Schreibende? Dann wartet der Lesenden auf den schreibenden und du hast keinen Geschwindigkeitsvorteil.
Ich denke, was das kopieren von Dateien angeht sind die Algorithmen mehr als optimiert, das Problem sind eher die Speichermedien.

 

[Phoenixz]

Ok, vielleicht kam das jetzt ein wenig falsch von mir rüber. Ich möchte das Rad von Kopieren nicht neu erfinden ^^. Ich gehe auch davon aus, dass die bestehenden Kopieralgorithmen mehr als Optimal sind. Doch wie sehen diese aus? Ich will nur wissen wie man es richtig macht bzw. wie es z.B. MS bei Windows macht. Den Windows-Kopiervorgang kann ich aber nicht benutzte (also über Windows-API), da der z.B. kein Pausieren unterstützt.

Was ist wenn der Lesende Thread schneller ist als der Schreibende? Dann wartet der Lesenden auf den schreibenden und du hast keinen Geschwindigkeitsvorteil.

Das ist ja nicht wirklich schlimm, wenn der Lesende auf den schreibenden wartet. Denn so gesehen wird dann ja trotzdem zu JEDEM Zeitpunkt geschrieben. Bei der naiven Lösung jedoch nicht! Da ist es immer Schreiben, Lesen, Schreiben, Lesen, …
Es ist ja sogar anzunehmen, dass der Lesende schneller als der schreibende ist (da eine Festplatte ja üblicherweise schneller lesen kann als schreiben). Aus dem Grund würde ich die Queue ja auch auf eine bestimmte Paketanzahl begrenzen. Ich will nur versuchen, dass IMMER geschrieben wird, ohne Pausen einzulegen. Und das scheint ja bei der Lösung der Fall zu sein.

 

[toeffi]

Nein. Du hast keine Performance Gewinn. Denn solange wie der Schreibende Thread nicht fertig ist, wartet dein Lesender, da du ihn auf eine bestimmte Paketanzahl begrenzen willst hast du den selben Effekt wie auch beim "normalen" kopieren. Du schreibst, und liest dann wieder aus der Queue. Ob du das nun im wechsel machst oder der Lesende Thread immer erst warten muss bis der schreibende die Queue geleert hat macht da keinen Unterschied.

 

[NullPointer]

Meine Vermutung wäre, daß (sofern Quell- und Zieldatei auf dem gleichen Datenträger liegen) vor allem daduch ein Performancegewinn möglich ist, daß man den Puffer im RAM so groß wie möglich macht - im Idealfall also zuerst die ganze Quelldatei einliest und dann an einem Stück ans Ziel schreibt. Dadurch erspart man der Festplatte das ständige Hin- und Herbewegen zwischen den beiden Dateien.

Liegen Quelle und Ziel auf verschiedenen Datenträgern, wäre dieses Vorgehen natürlich von Nachteil, da dann der Zieldatenträger solange nichts zu tun hat, wie die Quelle gelesen wird.

 

[Whiz-zarD]

Zudem ist es mit Schreiben und Lesen nicht getan.
Was machst du, wenn kein Speicher mehr frei ist? Dann kann es schnell beim Multi-Threading zu einem Deadlock kommen:
Der lesende Thread wartet, bis der schreibene Thread fertig ist aber der schreibene Thread kann nicht fertig werden, weil kein Speicher zur Verfügung steht.
Oder der Deadlock passiert andersrum, wenn der Arbeitsspeicher voll sein sollte und nichts mehr vom Medium gelesen werden kann.

Zusätzlich muss noch abgefragt werden, ob die gelesenden und geschriebenen Daten korrekt sind. Sonst kannst du das Problem haben, dass die Daten falsch gelesen oder geschrieben worden sind. z.B. das Lesen von einer defekten Festplatte/CD/DVD/... . Darum gibt es auch die CRC-Checksummen Überprüfung.

Also so einfach ist so ein Kopiervorgang auch wieder nicht.

 

[Phoenixz]

Hmmm… vielleicht reden wir auch aneinander vorbei, den für mich ist das immer noch nicht ersichtlich. Für mich hört sich das so an, als ob du mich missverstanden hast und denkst, das die Queue immer komplett gelehrt werden muss, bevor sie wieder gefüllt werden kann.

Also nochmal ein wenig detaillierter:
Wir haben einen Lesenden Thread. Der macht folgendes, des liest X Bytes (= ein Paket) und legt diese jedes Mal in eine Datenstruktur, in diesem Fall eine Queue rein. Wenn in der Queue Y Elemente drin sind wird der Thread schlafen geschickt. Sobald jedoch weniger als Y Elemente drin sind, wird sofort wieder ein Paket reingelegt.
Da anzunehmen ist, dass der lesende Thread schneller als der schreibende ist wird das Erscheinungsbild auftreten, dass abwechselnd in der Queue immer Y und Y-1 Elemente drin sein werden.
Wenn es keine Bytes mehr im Quellstream zu lesen gibt ist der Thread natürlich fertig und wird beendet.

Anschließend haben wir noch einen schreiben Thread der sich aus der Queue jeweils ein Paket rausnimmt und diesen in den Zielstream reinschreibt. Dieser Vorgang wird solange wiederholt, solange es Pakete in der Queue gibt.

Die Threads laufen unabhängig voneinander. Der Lesende wartet als streng genommen niemals auf den schreibenden sondern darauf, dass Y-1 Elemente in der Queue sind, um wieder ein Paket reinzulegen (Aber das hängt ja miteinander zusammen).

Rein Theoretisch würde da auch schon eine Queue mit 2 Paketen ausreichen, um zu erziehen, das der schreibende Thread immer was zu schreiben hat.

Also um das nochmal klarzustellen, wir haben nicht das Verhalten, <fülle Queue>, <leere Queue komplett>, <fülle Queue>, <leere Queue komplett>. Das wäre ja in der tat nichts bringen und ist ja wie ein großes Paket anzusehen.

Wenn ich dich jedoch falsch verstanden habe, könntest du deine Erklärung etwas ausführen?
Soweit trotzdem schon mal Dankeschön für die Hilfe!

@Whiz-zarD
Vielen Dank für den Hinweis. Natürlich sind dann anschließend noch einige Fehlerquellen abzudecken, doch in erster Linie muss erst mal der rudimentäre Kopiervorgang stehen um diese Dinge zu berücksichtigen .

 

[toeffi]

Multithread Programmierung bringt nur dann einen Vorteil solange die beteiligten Threads wirklich immer was zu tuen haben. Der Schlafen-Schicken-Aufwecken-Prozess ist glaube ich enorm Kontraproduktiv und die wirkliche Auslastung liegt zu 90% bei dem schreibenden Thread.

 

[Whiz-zarD]

Beide Threads asynchron laufen zu lassen, wäre sehr unsicher.
Denn ob der lesende Thread immer schneller als der speichernde Thread, ist nicht gesagt.
Da beide Threads gemeinsam in einer Datenstruktur schreiben, müssen sie synchronisiert werden, da der Speichernde Thread, die geschriebenen Daten aus der Queue löschen muss.
Ansonsten kannst du nur Daten kopieren, die kleiner sind, als der freie Arbeitsspeicher.
Wenn sie Asynchron laufen, kann es z.B. passieren, dass der speichernde Thread Daten löscht, die noch doch gar nicht gespeichert sind.

 

[Phoenixz]

Ja, das Nichtsequenzielle Programmierung wesentlich Fehleranfälliger ist, ist mir auch bewusst (Habe auch schon genug in dieser Richtung geproggt, insb. das Debuggen macht reichlich Spass ^^). Sicherlich muss da einiges an Gehirnschmalz reingesteckt werden, dass sichergestellt werden kann, dass nicht schief läft. Genau so ist mir auch bewusst, dass das ganze sicherlich Prozessorlästiger ist als die naive Lösung. Jedoch lasse ich lieber den Prozessor deutlich mehr arbeiten, wenn ich dadurch den Kopiervorgang beschleunigen kann. Also, unabhängig von Sicherheit und Prozessorauslastung, ist anzunehmen dass ein solcher Kopiervorgang schneller ist als ein naiver (bei unterschiedlichen Datenträgern)? Für mich hört sich das zumindest noch danach an.

 

[Whiz-zarD]

Der Vorgang kann aber auch nur schneller sein, wenn man wirklich den idealen Fall verwischt, also dass das Lesen immer schneller ist, als das Schreiben. Dieser Fall ist aber nicht immer gegeben. z.B. wenn man von einer CD liest und auf eine SSD schreibt. Dann ist der schreibende Thread schneller als der lesende und somit ist dein Algorithmus für die Katz.
Das sind optimierungen, die eigentlich keiner macht, weil ...
1. es nicht immer eine Optimierung bedeutet
2. asynchrones Multithreading, wo beide Threads in eine Datenstruktur schreiben, unsicher ist.

 

[Banthor]

Wie der Threadersteller schon am Anfang schrieb macht es überhaupt nur dann Sinn, wenn Quelle und Ziel auf unterschiedlichen physischen Geräten sind.

Und ein anderer schrieb Threads machen nur dann Sinn, wenn diese ausgelastet werden können. Das ist bei unterschiedlichen Geräten natürlich gegeben. Selbst wenn eine der der beiden Geräte sehr langsamer ist als das andere. Im Idealfall sind beide Geräte gleich schnell, dann kannst du mit einer fast halbierten Koperzeit rechnen.

Wichtig dabei ist, dass eine Threads bei IO-Operationen sich ohnehin die meiste Zeit im Wartezustand befinden, weil Massenspeicher i.d.R. ziemlich langsam sind.

Beispiel:
Man will 1000MB kopieren
Die Quelle liest mit 100MB/s
Das Ziel schreibt mit 50MB/s

Würde man sequentiell erste lesen und dann schreiben, würde der Kopierprozess 10Sek + 20Sek dauern - also insgesamt 30Sek.

Würde man mit Threads parallel lesen und schreiben, so würde das langsamere Gerät die Gesamtdauer vorgeben - der Kopierprozess würde also ca. 20Sek dauern (vllt. minimal mehr wegen Synchronisierung der Threads und initialem Anlauf)

Die Synchronisierung der Threads kann man bei IO-Operationen weitestgehend ignorieren. Wie gesagt, wartet die CPU bei IO ohnehin ewig lange und in dieser Zeit würde man parallel schon schreiben können. Je größer die Puffer (also bei dir die Pakete) sind, desto weniger Synchronisierung wird fällt an.

Am Besten ist es, wenn du es einfach mal programmierst und dann mal deine Ergebnisse hier zeigst

 

[Whiz-zarD]

Ach, und nochwas:

Jedoch lasse ich lieber den Prozessor deutlich mehr arbeiten, wenn ich dadurch den Kopiervorgang beschleunigen kann.

Schonmal was von UDMA gehört?
Um den Prozessor zu entlasten, hat man das UDMA-Verfahren eingeführt, weil das Versenden der Daten, über den CPU (PIO-Modus) zu rechenintensiv war.

 

[Phoenixz]

Der Vorgang kann aber auch nur schneller sein, wenn man wirklich den idealen Fall verwischt, also dass das Lesen immer schneller ist, als das Schreiben. Dieser Fall ist aber nicht immer gegeben. z.B. wenn man von einer CD liest und auf eine SSD schreibt. Dann ist der schreibende Thread schneller als der lesende und somit ist dein Algorithmus für die Katz.

Auch hier wäre der Alg. soweit ich das überblicken kann nicht für die Katz. Den auch hier erhält man einen Vorteil, weil während der eine Thread noch schreibt fängt der andere schonwieder an zu lesen und wartet nicht erst bis der schreibende fertig ist um erst dann anzufangen zu lesen. Generell sollte eigentlich ein Geschwindeltsvorteil immer dann vorhanden sein, wenn zwei unterschiedlichen Datenträgern verwendet werden, was gar nicht so selten der Fall ist. Jedoch kann ich dir trotzdem insoweit zustimmen das es sich halt nur um eine „Optimierung“ handelt, die nicht alle Fälle abdeckt.

Leider muss ich zugeben noch nie was von UDMA gehört zu haben. Das mit der Prozessorauslastung ist jedoch auch so eine Sache. Ich gehe nämlich nicht davon aus das bei einem Dual Core beide Prozessoren bei 90% landen werden sondern VIEL VIEL weniger.
Ich glaube das sinnvollste ist der Vorschlag von Banthor, nämlich das ganze einfach mal zu testen und dabei Prozessorauslastung und benötigte Zeit in relation stellen und daraus einen Schluss ziehen. (Natürlich für beide Fälle, Dateien befinden sich auf den gleichen Datenträgen und einaml auf unterschiedlichen Datenträgern). Jedoch wollte ich mir vorher einfach mal ein paar Meinungen anhören um mir eine bessere Meinung bilden zu können. In diesem Sinne finde ich es sogar besonders gut ein paar kritische Meinungen zu dem Alg. gehört zu haben, sodass mir auch besonders die Risiken und Probleme mit diesem Alg. klar wurden.

 

[Whiz-zarD]

Ich gehe nämlich nicht davon aus das bei einem Dual Core beide Prozessoren bei 90% landen werden sondern VIEL VIEL weniger.

Sei dir da mal nicht so sicher
Wenn du ein Dual Core CPU dein eigen nennst und noch eine IDE Festplatte (und passendes Mainboard) besitzt, dann schalte die Festplatte mal in den PIO-Modus und kopiere dann mal auf der Festplatte eine mehrere Gigabyte große Datei. Du wirst staunen, was da die CPU leisten muss. Der Rechner reagiert dann so extrem langsam, sodass selbst der Mauszeiger nicht mehr richtig reagiert. Auch dauert der Kopiervorgang deutlich länger. Auch beim dicksten CPU, den man kaufen kann.
Im PIO-Modus war es vorgesehen, dass alle Daten, die von A nach B laufen, den Umweg über den CPU machen. Im heutigen UDMA-Modus können die Speichermedien direkt miteinander kommunizieren und sorgen automatisch schon dafür, dass die Daten korrekt ankommen.
Somit wird der CPU kaum bis gar nicht beansprucht.

In deiner Überlegung würdest du aber quasi den PIO-Modus nachprogrammieren, weil hier der Prozessor bestimmt, welche Daten gelesen und welche geschrieben werden.

Will die I/O-Hardware Daten senden oder empfangen, trennt der DMA-Controller den Prozessor vom Bussystem. Der DMA-Controller führt dann die Anforderung mit hoher Geschwindigkeit aus. Danach wird die Verbindung zwischen Prozessor und Bussystem wieder hergestellt. Für den Speichertransfer benötigt der Prozessor bis zu 40 Takte je Byte. Der DMA-Controller führt den Zugriff innerhalb von vier Takten aus.

Bei deinen Algorithmus würde immer wieder die CPU an das Bussystem gekoppelt und dem DMA-Controller sagen, welches Byte nun als nächstes gelesen und gespeichert werden soll, anstatt den DMA Controller zu sagen "Transferiere 10 GB von A nach B"

Und das nächste, was dein Algorithmus beeinflusst, ist die Programmiersprache selbst.
Wenn du sowas programmieren willst, dann kommst du an C bzw. Assembler nicht drumherum. Alles andere wäre viel zu langsam.

 

[Phoenixz]

Klingt auf jeden Fall einleuchtend und plausibel! Doch wenn ich das jetzt richtig verstanden habe wäre dann ja die naive Methode auch „falsch“. Den auch da übertrage ich nicht die Datei von A nach B direkt, sondern ich lese aus dem Quellstream in einen Buffer und schreibe denn den Buffer wieder in den Zielstream. In diesem Sinne bestimmt dann doch auch wieder der Prozessor welche Daten gelesen und geschrieben werden. Die Frage ist dann nur wie leite ich dann einen solchen direkten Kopiervorgang ein?

Ohne mich genauer mit dem UDMA-Modus zu beschäftigen, klingt es jedoch so für mich, als sei es dort nicht möglich den Kopiervorgang zu pausieren, liege ich da richtig? Das wäre leider für meine Zwecke nicht "tragbar", da das ein Absolutes Hauptkriterium ist (würde mich aber trozdem interessieren, wie ich dann einen solchen Kopiervorgang einleite).

 

[Whiz-zarD]

Wozu denn auch pausieren, wenn der CPU damit nichts zu tun hat?
Ich kenn mich mit dem DMA-Zugriffsverfahren auch nicht besonders gut aus aber ich les grad was über die Prioritätsverwaltung von DMA und anscheinend ist es nicht möglich, ein Kopiervorgang zu pausieren. Es gibt aber wohl Möglichkeiten, einem Kopiervorgang eine geringere Priorität zu geben.

Und ja, die "naive"-Methode ist sehr CPU-Lastig.
Weil du quasi eine CPU->Speichermedium->RAM->CPU->RAM->Speichermedium Kette aufbaust. Also:
1. Hole Daten von Festplatte/CD/...
2. Speicher in den RAM
3. Hole Daten vom RAM
4. Speicher auf Festplatte/SSD/...
Was quasi die generelle Arbeitsweise des PIO-Modus entspricht.
Beim DMA sagt der CPU einfach zum DMA-Controller: "Speicher Daten von A nach B" (also z.B. "Speicher Daten von CD nach Festplatte") und der DMA-Controller übernimmt die Aufgabe, während die CPU höchstens die Statusinformationen abruft, um sie z.B. auf den Bildschirm abbilden zu lassen.

 

[Banthor]

UDMA/DMA

Meine Zeiten so hardwarenah in Assembler zu programmieren liegen mit dem Amiga 500/1200 nun schon sehr lange zurück. Auch dort gab es auch schon DMA-Modi. Wenn mein Wissen noch auf heutige Hardware zutrifft sage ich folgendes:

Prinzipiell ist es so, dass die CPU dem Festplattencontroller sagt "Kopiere Sektor X bis Sektor Y an Speicheradresse M". Dann legt der Festplattencontroller unabhängig von CPU los und kopiert die Daten dann 1:1 von der Festplatte in den Speicher. Wenn alles fertig ist bekommt die CPU ein Interrupt, um zu signalisieren, dass alles fertig ist. Es ist also nur so, dass UDMA nur die Rohdaten ohne Hilfe zwischen Festplatte und Hauptspeicher transferieren kann - und das schon ein Riesenfortschritt. Ich nehme auch an, dass heutige DMA Modi gleichzeitig noch die Daten automatisch dekodieren kann (Was beim Amiga z.B. noch immer die CPU vornehmen musste).

Es gibt aber also noch jede Menge für die CPU zu tun, was mich nun behaupten lässt, dass es nicht so ist (auch nicht mit UDMA), dass der Festplattencontroller eine Datei vollständig alleine ohne Hilfe der CPU Daten auf eine zweite (oder auch nur auf dieselbe) Festplatte kopieren kann. Es gibt einen ganz einfachen Grund warum das nicht sein kann:

Die Hardware und somit der UDMA-Modus hat keine Ahnung davon, wie das Dateisystem (NTFS, FAT, exFAT, ...) Daten auf der Festplatte organisiert.

Allein aus diesem Grund muss die CPU die Daten entsprechend umorgansieren, d.h. freie Sektoren lokalisieren, Dateiblöcke/header schreiben usw. Sind die Daten transformiert so sagt die CPU dem Festplattencontroller wieder "Kopiere diese Speicherblock wieder auf diese und diese Sektoren", was dann wieder sehr schnell und ohne Hilfe der CPU funktioniert.

Wäre es so, dass der UDMA-Modus direkt ohne CPU Daten von Festplatte A nach Festplatte B kopieren könnte, so müsste er alle existierende und noch nicht existierenden Dateisysteme beherrschen.

 

[roker002]

Es lohnt sich nur dann ein Stream Lesen/Schreiben wenn es Multi CPU unterstützt. Man muss halt die mehreren Threads erstellen und diese dann Pro CPU verteilen. wie es genau geht, konnte ich so schnell nicht finden. Sonst kannst du sicher nach Win Apis aus dem COM irgendwas heraussuchen.

 

[lararsc]

Ich denke dieser Artikel könnte dich sehr interessieren:
http://blogs.technet.com/b/markrussinovich/archive/2008/02/04/2826167.aspx