So veranlassen Sie den Kernel, fragmentierten Speicher zu komprimieren

Ich renne Fedora 26.

Dies ist für eine sehr seltsame Aufgabe, die mein Algorithmusprofessor gegeben hat. Die Aufgabe lautet:

Speicherfragmentierung in C:
Entwerfen, Implementieren und Ausführen eines C-Programms, das Folgendes ausführt: Es weist Speicher für eine Folge von 3mArrays mit einer Größe von jeweils 800.000 Elementen zu; Anschließend werden alle geradzahligen Arrays explizit freigegeben und eine Folge von mArrays mit einer Größe von jeweils 900.000 Elementen zugewiesen . Messen Sie die Zeit, die Ihr Programm für die Zuordnung der ersten und der zweiten Sequenz benötigt. Entladen Sie mfast den gesamten Hauptspeicher, der Ihrem Programm zur Verfügung steht. "

Das übergeordnete Ziel ist es, den Speicher zu fragmentieren und dann etwas mehr als das anzufordern, was als zusammenhängender Block verfügbar ist, wodurch das Betriebssystem gezwungen wird, den Speicher zu komprimieren oder zu defragmentieren.

Im Unterricht fragte ich, wie wir dies tun sollten, da das Gedächtnis visualisiert und nicht wirklich zusammenhängend ist, worauf er antwortete: "Nun, Sie müssen [virtuelles Gedächtnis] ausschalten." Einige andere Schüler fragten in der Klasse, wie wir wissen sollten, wann wir diese "Garbage Collection" erreicht haben, und er sagte: "Der Zeitpunkt für die zweite Zuweisung sollte länger sein als der erste, da die Garbage Collection viel Zeit in Anspruch nimmt."

After searching around a bit, the closest thing I could find to disabling virtual memory was to disable swap memory with swapoff -a. I disabled my desktop environment and compiled and ran my program from the native terminal (to avoid possible interference from other processes, especially a heavy one like the Desktop Environment). I did this and ran my program with increasing m until I reached a point where the timing for the second allocation was greater than the first.

Ich habe das Programm mit zunehmender mGeschwindigkeit ausgeführt und schließlich einen Punkt gefunden, an dem die Zeit für die zweite Zuweisung länger war als die Zeit für die erste Zuweisung. Unterwegs traf ich jedoch einen Punkt, an dem der Prozess vor der zweiten Zuweisung beendet wurde. Ich überprüfte dmesgund sah, dass es von oom-killer getötet wurde . Ich habe mehrere Artikel über oom-killer gefunden und gelesen und festgestellt, dass Sie die Speicherzuweisung durch den Kernel deaktivieren können.

Ich tat dies und führte mein Programm erneut aus, nur dieses Mal konnte ich kein msolches finden, so dass das Timing des zweiten höher war als das des ersten. Schließlich würde malloc mit immer größerem m (obwohl viel kleiner als bei aktivierter Gesamtzuordnung) fehlschlagen und mein Programm würde enden.

Ich habe drei Fragen, von denen die erste nicht wirklich so wichtig ist:

1. Ist Garbage Collection der richtige Begriff dafür? Mein Professor sagt sehr unerbittlich, dass dies eine Speicherbereinigung ist, aber ich ging davon aus, dass die Speicherbereinigung von Programmiersprachen durchgeführt wurde und dass dies als defragmentierter angesehen wird.

2. Ist eine Komprimierung auf einem Linux-System möglich, wie er es möchte?

3. Warum konnte ich einen Punkt erreichen, an dem die Zeit für die zweite Zuweisung höher war als die erste, als ich den Swap deaktivierte, aber die Gesamtzuordnung des Speichers aktiviert hatte? Hat die Verdichtung tatsächlich stattgefunden? Wenn ja, warum konnte ich keinen Punkt erreichen, an dem die Komprimierung stattfand, nachdem ich die Gesamtzuordnung des Speichers deaktiviert hatte?

Ein großes Lob an Ihre bisherige Forschung, dies ist in der Tat eine interessante Reihe von Fragen.

Hier ist allgemein ein wichtiger Aspekt zu berücksichtigen: Die Speicherzuweisung liegt teilweise in der Verantwortung des Betriebssystems und teilweise in der Verantwortung jedes laufenden Prozesses (Ignorieren alter Systeme ohne Speicherschutz und virtuelle Adressräume). Das Betriebssystem sorgt dafür, dass jeder Prozess seinen eigenen Adressraum erhält und den Prozessen bei Bedarf physischen Speicher zugewiesen wird. Jeder Prozess kümmert sich (bis zu einem gewissen Grad) darum, seinen Adressraum aufzuteilen und sicherzustellen, dass er ordnungsgemäß verwendet wird. Beachten Sie, dass die Verantwortung eines Prozesses für Programmierer weitgehend unsichtbar ist, da sich die Laufzeitumgebung um die meisten Dinge kümmert.

Nun, um Ihre Fragen zu beantworten ...

1. In meinen Augen ist die Speicherbereinigung nur einen Schritt von dem entfernt, was Sie hier tun. Ich stelle mir vor, Sie schreiben in C mit malloc()und free(). Die Garbage Collection , die von der Programmiersprache und der Laufzeitumgebung unterstützt wird, kümmert sich um den letzten Teil: Sie identifiziert Speicherblöcke, die zuvor zugewiesen wurden, aber nicht mehr verwendet werden (und vor allem nie wieder verwendet werden können), und gibt sie zurück an den Allokator. Die Frage verknüpft in JdeBP ‚s Kommentar bietet einige Hintergrundinformationen , aber ich finde es vor allem interessant , weil es zeigt , dass verschiedene Menschen auf Garbage Collection sehr unterschiedliche Meinungen haben, und auch , was als Garbage Collection.

   In dem Kontext, an dem wir interessiert sind, würde ich die „Speicherkomprimierung“ verwenden, um über den diskutierten Prozess zu sprechen.

2. Aus Sicht der User-Space-Programmierung ist das, was Ihr Professor verlangt, in C unter Linux aus einem einfachen Grund nicht möglich: Was uns hier wichtig ist, ist nicht die Fragmentierung des physischen Speichers, sondern die Fragmentierung des Adressraums. Wenn Sie Ihre vielen 800.000-Byte-Blöcke zuweisen, erhalten Sie genauso viele Zeiger auf jeden Block. Unter Linux hat das Betriebssystem selbst zu diesem Zeitpunkt nicht viel getan, und Sie haben nicht unbedingt physischen Speicher, der jede Zuordnung unterstützt (abgesehen davon, dass bei kleineren Zuordnungen das Betriebssystem überhaupt nicht beteiligt wäre, nur Ihre Allokator der C-Bibliothek, aber die Zuordnungen hier sind groß genug, dass die C-Bibliothek sie verwenden wirdmmap, die vom Kernel verwaltet wird). Wenn Sie die ungeradzahligen Blöcke freigeben, erhalten Sie diese Adressraumblöcke zurück, aber Sie können die Zeiger, die Sie auf die anderen Blöcke haben, nicht ändern. Wenn Sie die Zeiger ausdrucken, werden Sie feststellen, dass der Unterschied zwischen ihnen nicht viel größer ist als die Zuordnungsanforderung (802.816 Byte auf meinem System). Zwischen zwei Zeigern ist kein Platz für einen 900.000-Byte-Block. Da Ihr Programm tatsächliche Zeiger auf jeden Block hat und keinen abstrakteren Wert (in anderen Kontexten ein Handle), kann die Laufzeitumgebung nichts dagegen tun und daher ihren Speicher nicht komprimieren, um freie Blöcke zusammenzuführen.

   Wenn Sie eine Programmiersprache verwenden, in der Zeiger kein vom Programmierer sichtbares Konzept sind, ist unter Linux eine Speicherkomprimierung möglich. Eine andere Möglichkeit wäre die Verwendung einer Speicherzuweisungs-API, bei der die zurückgegebenen Werte keine Zeiger sind. Siehe zum Beispiel die Handle-basierten Heap-Zuweisungsfunktionen unter Windows (wobei Zeiger nur gültig sind, wenn ein Handle gesperrt ist).

3. Die Übung Ihres Professors misst effektiv die Leistung von mmap, einschließlich des Free-Block-Walking-Algorithmus. Sie weisen zuerst 3 × m Blöcke zu, geben dann die Hälfte davon frei und beginnen dann erneut, m Blöcke zuzuweisen . Durch das Freigeben all dieser Blöcke wird eine große Menge freier Blöcke auf dem Allokator des Kernels abgelegt, den er verfolgen muss (und die Zeit, die die freeAufrufe benötigen, zeigt, dass derzeit keine Optimierung durchgeführt wird). Wenn Sie die Zuweisungszeiten jedes einzelnen Blocks verfolgen, werden Sie feststellen, dass die erste Zuweisung von 900.000 viel, viel kostetlänger als die anderen (drei Größenordnungen auf meinem System), die zweite ist viel schneller, dauert aber immer noch viel länger (zwei Größenordnungen), und die dritte Zuordnung ist wieder auf dem typischen Leistungsniveau. Es ist also etwas los, aber die zurückgegebenen Zeiger zeigen, dass es keine Speicherkomprimierung war, zumindest keine zugewiesene Blockkomprimierung (was, wie oben erläutert, unmöglich ist) - vermutlich entspricht die Zeit der Zeitverarbeitung der Datenstrukturen, die der Kernel verwendet Behalten Sie dabei den verfügbaren Adressraum im Auge (ich überprüfe dies und werde es später aktualisieren). Diese langwierigen Zuweisungen können zunehmen, um die von Ihnen gemessenen Gesamtzuweisungssequenzen in den Schatten zu stellen. In diesem Fall dauern die 900.000 Zuweisungen insgesamt länger als die 800.000 Zuweisungen.

   Der Grund für die Überbeanspruchung des angezeigten Verhaltens besteht darin, dass die Übung von der reinen Manipulation des Adressraums zur tatsächlichen Zuweisung von Speicher geändert wird und somit die Größe Ihres Spielplatzes verringert wird. Wenn Sie zu viel Commit ausführen können, ist der Kernel nur durch den Adressraum Ihres Prozesses begrenzt, sodass Sie weit mehr Blöcke zuweisen und viel mehr Druck auf den Allokator ausüben können. Wenn Sie Overcommit deaktivieren, wird der Kernel durch den verfügbaren Speicher begrenzt, wodurch der Wert, den Sie für mauf Ebenen haben können , auf denen der Allokator nicht genug beansprucht wird, damit die Zuweisungszeiten explodieren.