Am Mittwoch, 3. Januar 2007 09:14 schrieb Klaus Klein: > Max Trense wrote: > > Genau. Das auf jeden Fall. Allerdings ist der Read-Ahead-Algorithmus > > wesentlich wichtiger als die Größe des Read-Ahead-Buffers. Allerdings hat > > man als reiner Bediener auf den Algorithmus wenig Einfluss :-( > > Meines Wissens ist Read-Ahead eine Funktion welche anstatt nur des > adressierten Sektors gleich mehrere darauf folgende Sektoren mit liest > und hier die Wahrscheinlichkeit, dass sowieso die nächsten Blocks auch > gebraucht werden, nutzt um den Lesezugriff zu erhöhen, da diese dann > schon im Cache stehen. Mir ist nicht bekannt das es hier einen > Algorithmus gibt, weder was der tun sollte. (ist sowieso > LowLevel-Zugriff auf die Platte und somit ohne Optimierungsmöglichkeit > hinsichtlich irgendwelcher File Systeme)
Da musst Du aber unterscheiden zwischen dem Read-Ahead, das der Plattencontroller macht und der Read-Ahead-Data-Prediction, die die meisten Betriebssysteme durchführen. Der Plattencontroller liest immer exakt soviel wie er in einem Durchlauf schafft, auch wenn das mehr ist als angefordert war. Das bringt bei nicht fragmentierten Daten einen leichten Performancegewinn. Die Prediction, die die meisten Betriebsysteme in ihren I/O-Routinen verwenden kann auch mit fragmentierten Daten umgehen und liest Daten eben tatsächlich bevor sie angefragt werden. > >>> Ein Problem ist aber auch hier der Overhead. Der fällt im > >>> Vergleich zur Performancesteigerung zwar recht gering aus, aber es gibt > >>> eben auch Fälle, in denen es nicht möglich ist, mehrere Blöcke parallel > >>> zu lesen. Eben dieser Fall ist bei Swap gegeben: Arbeitsspeicher wird > >>> in der Regel nicht in zusammenhängenden Clustern benötigt, sondern > >>> meistens nur einzelne Pages. Und das entspricht dem Laden eines > >>> einzelnen Blocks von der Festplatte. > >> > >> Kurze Frage: Warum müssen Pages, gerade bei multithreaded Anwendungen > >> oder MultiKern/Prozessoren, immer 'sequenziell' geswapped (Autsch, ganz > >> übles Neudeutsch) werden? > > > > Das werden Sie nicht. Das Betriebssystem (hier natürlich vor allem die > > Speicherverwaltung) wird eine bestimmte Menge an Speicherseiten > > auslagern, wenn der Systemspeicher knapp wird. Welche das sind, das > > bestimmt ein spezieller Paging-Algorithmus. Der lässt sich im > > Linux-Kernel zum Beispiel auch auswählen (Allerdings ist der > > voreingestellte Algo wohl definitiv der Beste). Diese Speicherseiten sind > > in der Regel weder zusammenhängend, noch stehen sie in irgendeiner > > Relation zueinander. Und genau da beginnt natürlich auch das große > > Problem. Während des Einlagerns von Speicherseiten wird wieder zufällig > > auf eine Speicherseite zugegriffen. Welche Speicherseite das sein wird, > > lässt sich nicht vorhersagen und damit auch nicht optimieren. Es gab vor > > einigen Jahren mal einen Ansatz, Page-Faults (Also die Ereignisse, die > > zum Einlagern einer Speicherseite führen) in Gruppen zusammenzufassen und > > über Heuristiken vorhersagbar zu machen. Allerdings steht der Aufwand für > > diese Methodik wohl in keinem Verhältnis zur erreichten > > Performance-Steigerung. > > So war das mit sequenziell nicht gemeint. Wusste nicht, das sequenziell mehrere Bedeutungen hat ;-) > Vielmehr, wird den seitens des Kernel bzw. der Speicherverwaltung > erwartet das die Pages in der Reihenfolge von der Platte gelesen bzw. > von dort geliefert werden wie sie angefordert wurden (FiFo) oder ist > dies auch, wie z.B. IP-Pakete, auch in einer abweichenden Reihenfolge > geschehen und das Speichermanagement sortiert das dann aus? Das wird nicht passieren. Wie ich schon gesagt habe (ist vielleicht nicht so deutlich rübergekommen) wartet die Speicherverwaltung nicht, bis mehrere Page-Faults auftreten. Daher wird von der I/O-Schnittstelle auch immer nur _ein_Block gleichzeitig gelesen. Und das lässt sich auf keinen Fall parallelisieren. > Beispiel: > Anforderung : #12, #265, #2, #177, #5674 > Rücklieferung : #12, #2, #177, #265, #5674 > > Dies wäre dann eigentlich, im Gegensatz zu Deiner ursprünglichen > Abhandung, ein klassischer Fall für eine Parallelisierung. ;-) Genau dieser Fall tritt aber nicht auf, da immer nur ein Page-Fault gleichzeitig bearbeitet wird. > >> Ich denke schon das hier mächtig > >> 'parallelisiert' werden kann. Zudem ist die Wahrscheinlichkeit, das die > >> Blöcke welche gelesen oder geschrieben werden müssen auf > >> unterschiedlichen Platten liegen, beim Stripping (über zwei oder mehrere > >> Platten) nun mal nahe 50:50 (bei zwei) oder grösser (bei mehreren > >> Platten). Somit sollte eigentlich genau hier das Thema mit der > >> Verteilung des Overheads (Kopfbewegung) greifen. > > > > Das sieht natürlich erstmal so aus. Allerdings musst Du auch bedenken, > > dass für diese Optimierung mehr als ein Block in einem gewissen > > Zeitabschnitt gelesen werden muss. > > Gerade nicht. Davon ausgehend dass das swapping dann gebraucht wird wenn > es Angefordert wird und eben zufällig, bzw. nicht vorhersehbar, ist, > macht es erstmal keinen Sinn auf etwas zu warten. Da Festplatten > durchaus schon eine gewisse Intelligenz mitbringen (Lese.- und > Schreiboperationen werden optimiert) wird hier u.U. schon beim > lesen/schreiben parallelisiert ohne das das Speichermanagement davon > etwas mitbekommt. Bei den Zugriffen auf eine Platte bleiben jedoch die > Kopfbewegungen der grösste Faktor und somit kann währen eine Platte noch > positioniert die zweite Platte schon den nächsten (bei einer > Wahrscheinlichkeit von 50:50) Sektor anfahren und somit im Vergleich zu > einem Zugriff auf einer Platte einen Zeitvorteil herausholen. > > HDD : |----Seek----------|-Read-|----Seek----------|-Read-| > > im Vergleich zu zwei Platten > > HDD1 : |----Seek----------|-Read-| > HDD2 : |----Seek----------|-Read-| Beim Swapping wartet der Speichermanager mit der Bearbeitung des nächsten Page-Faults, bis der aktuelle beseitigt ist. Es kann ja sein, dass die Beseitigung des aktuellen Page-Faults eine Speicherseite auslagert, die der Prozess, der den nächsten Page-Fault auslösen wird braucht. Man kann zwar Heuristiken verwenden, um vorherzusagen, welche Speicherseiten wahrscheinlich in der nächsten Zeit nicht benötigt werden, aber es bestünde trotzdem die Chance für eine solche Race-Condition. > > Im Falle von Page-Faults kann aber eben das nicht > > vorhergesagt werden. Man würde also eine Weile warten und mehrere > > Page-Faults sammeln, damit man sie dann gemeinsam bearbeiten kann. Da > > aber nicht vorhergesagt werden kann, ob in den nächsten n Zeiteinheiten > > weitere (und wenn ja, wieviele) Page-Faults auftreten, muss man auf jeden > > Fall bis zu einem bestimmten Timeout warten. Ist innerhalb dieses > > Timeouts mindestens ein weiterer Page-Fault aufgetreten, könnte diese > > Methode tatsächlich etwas schneller sein, als das herkömmliche Lesen > > einer Speicherseite. Ist jedoch kein weiterer Page-Fault aufgetreten, > > kommt zu der Zeit, die der Rechner benötigt, um eine Seite einzulagern > > natürlich noch die Zeit des Timeouts hinzu. Leider ist der letzte Fall > > der deutlich häufigere (vgl. Stallings, William: Betriebssysteme). > > Ein weiterer Einflussfaktor ist die Reaktionszeit von Prozessen. > > Natürlich kann ein Prozess, der einen Page-Fault ausgelöst hat, nicht > > fortgesetzt werden, bis der Page-Fault korrigiert ist. Dadurch würden im > > schlimmsten Fall mehrere Prozesse hängen, bis der Timeout abgelaufen ist. > > Das warten auf Page-Faults macht nur dann einen Sinn wenn ich damit > Zugriffszeiten auf der HDD optimieren kann. Da Page-Faults aber > 'anscheinend' nicht zusammenhängend auftreten (wäre mal interessant sich > die Zusammenhänge zwischen Applikation, Speichermanagement und swapping > mal anzuschauen) ergibt für mich eine Warten (mittels TomeOut) erstmal > keinen Sinn da anschliessend noch nicht mal feststeht das damit Zugriffe > optiemiert werden können und sich somit meist nur Wartezeiten addieren. Genau deshalb tut man das ja auch nicht :-) > >>> Da dieser Vorgang nicht parallelisierbar ist, gibt es natürlich > >>> auch keine Performance-Steigerung. > >> > >> Nochmal. Warum nicht? > > > > Weil auf die Daten in zufälliger Reihenfolge nacheinander zugegriffen > > wird. Das heißt, man kann nicht anhand des aktuell abgefragten Datums auf > > die zukünftig abgefragten Daten schließen. > > Also ein voneinander unabhängiger, in sich abgeschlossener Zugriff in > zufälliger Reihenfolge. Wenn das _nicht_ parallelisierbar ist, hab ich > wahrscheinlich das Konzept von parallel nicht verstanden. ;-) Eben nicht in sich abgeschlossen. Die Einlagerung von Speicher hat ja auch immer eine vorhergehende Auslagerung zur Folge (hmm, die Kausalität stimmt trotzdem ;-) ). Und eben diese Auslagerung könnte ja den Prozess betreffen, der als nächstes eine Einlagerung vorsieht. > BTW, erinnert mich irgendwie an UDP! Was hast Du nur mit Netzwerken ;-) > >> BTW. die Grösse einer Page ist nicht zufällig ein Vielfaches von 512 > >> Byte und somit ein ideales Vielfaches der Blockgrösse, was dann wieder > >> ideal zum Read-Ahead passt? > > > > Die Größe einer Page hängt vor allem vom verwendeten Paging-Algorithmus > > ab. Diese Größe muss allerdings nicht mal für alle verwendeten Pages fest > > sein. Der Buddy-Algorithmus verwendet zum Beispiel statt der Pages > > sogenannte Buddies, die für jede Invokation der Buddy-Funktion halbiert > > werden, bis ein Buddy von optimaler Größer erreicht ist. > > Ich kann jedoch nicht glauben das hier Speicher in Grössenordnugnen > kleiner 512 Byte 'geswapped' wird. und 512 Byte sind nun mal ein Sektor > und somit kleinste Einheit auf der Platte. ;-) Nein, das wird auch nicht passieren. Meines Wissens ist es gar nicht möglich weniger Speicher als 512 Byte zu allozieren, daher kann auch ein Buddy nicht kleiner werden. Das Konzept geht eher darauf zurück, das man den gesamten Speicher nimmt, und in einer Baumstruktur anordnet, um dann unterschiedlich große Buddies zu bekommen, so dass im optimalen Fall bei unterschiedlichen Allokationen weniger Speicher verschwendet wird. > >>> Einen ähnlichen Fall gibt es bei sehr > >>> kleinen Dateien. Natürlich könnte man nun die Blockgröße des > >>> Dateisystems auf einen kleineren Wert konfigurieren. Das bringt > >>> allerdings wegen der Seektime der Festplatte nicht besonders viel. > >> > >> Bei der Änderung der Blockgrösse wird man bei einer nicht fragmentierten > >> Datei wohl keinen Unterschied messen, zumindest nicht wenn die Datei > >> nicht über die Zylindergrenze der Platte hinausreicht und somit ohne > >> Kopfbewegung gelesen wird. (und so ein Zylinder ist schon mächtig gross. > >> ;-) ) > > > > Was wiederum auch nur für das sequentielle Lesen von Daten von der > > Festplatte stimmt. > > Mitnichten. Dein Beispiel bezog sich auf die Änderung der Blockgrösse im > Zusammenhang mit dem lesen von 'sehr kleinen' Dateien. > Davon Ausgehend das eine 'sehr kleine', nicht fragmentierte, Datei > innerhalb eines Zylinders auf der Platte liegt und somit ohne > Kopfbewegung (und mit Read-Ahead) gelesen werden kann wird eine > Modifikation der Blockgrösse wohl keine nennenswerte Auswirkung haben. > Egal ob die Datei nun sequenziell oder Random-Access gelesen wird. Es geht auf niedriger Ebene aber eben nicht um Dateien. Wenn ich wenige Daten habe, die gelesen werden müssen, diese aber über das komplette physikalische Medium verstreut sind, dann bringt es mir nichts, dass jede dieser Dateien (die zusammengenommen die Daten darstellen, die ich von der Platte lesen möchte) für sich alleine sehr klein und nicht fragmentiert ist. > > Bei mehreren kleinen Dateien, die über die Partition verteilt sind > > (das ist genau das Szenario des ausgelagerten Speichers; hier liegen > > mehrere Speicherseiten an unterschiedlichen Stellen im Swap) ist > > natürlich im schlimmsten Fall (übrigens streng genommen auch im > > durchschnittlichen Fall) für jeden einzelnen Lesevorgang eine > > Neupositionierung nötig. > > Exakt. Und diese sollten sich eigenlich mit mehreren Platten besser > Optimieren lassen als mit einer einzelnen. ;-) Das gilt aber wieder nur unter der Annahme, dass diese Daten auch parallel angefragt werden. > > Ausserdem lässt sich Swap nicht sinnvoll defragmentieren, da sich der > > Inhalt regelmäßig ändert. > > Max, ich glaube hier bringst Du diverse Sachen durcheinander. > Defragmentieren hat erstmal nichts mit dem Inhalt zu tun!! > Ich glaube auch nicht das eine Swap-Partition überhaupt im irgendeinem > Zusammenhang mit Fragmentierung steht. Bei einer Swap-Datei auf z.B. > einer FAT-Partition (Live-CD) gibts das dann schon, aber eben nur im > Zusammenhang mit der Datei und dem Filesystem, aber nicht mit dem Inhalt!! Jede strukturierte Information kann fragmentiert oder defragmentiert werden. Das Problem ist nur, dass sich die Struktur eines Swapspeichers in regelmäßigen Abständen ändert. Den Rest beantworte ich, wenn ich mehr Zeit habe ;-) Max -- ---------------------------------------------------------------------------- PUG - Penguin User Group Wiesbaden - http://www.pug.org
