Neue "malloc" und "free" Funktionen schreiben [geschlossen]

Da dies für eine Interviewfrage ist, wird es wahrscheinlich keine "richtige" Antwort geben, und sie sind mehr an Ihrem Gedankenprozess interessiert und an Ihrem allgemeinen Wissen rund um das Thema.

Sie sollten darum bitten, die Anforderungen zu klären oder je nach Situation eine Reihe von Antworten zu geben. Hier sind einige Punkte zu beachten:

• Ist es wichtig, Speicherfragmentierung zu vermeiden? Eine feste Zuweisungsgröße kann helfen.
• Benötigen Sie Geschwindigkeitsgarantien für die Zuteilung? Verwenden Sie den Index der verwendeten / freien Blöcke.
• Müssen Sie die durchgeführten Zuordnungen einfach verfolgen? Fügen Sie der malloc / free library Protokollstrukturen hinzu.
• Müssen Sie Speicher- / Überlauf-Speicher schützen oder erkennen? Extra-Padding und periodische Padding-Checks.

Diese Seiten beantworten Ihre Frage.

Ссылка - dieselbe Frage Ссылка

Einfach gesagt,

Ihre Funktion malloc sollte in der Lage sein, Speicher vom Betriebssystem abzurufen und dem Client (z. B. Ihrem C-Programm) zu übergeben, der die dynamische Zuweisung von Speicher anfordert. Um dies zu implementieren, hat die malloc-Bibliothek normalerweise viele Datenstrukturen (abhängig von der Implementierung). Zum Beispiel kann die malloc -Implementierung wählen, freie Speicherblöcke unter Verwendung einer verknüpften Liste zu verfolgen. Ein effizienterer Weg wäre eine Liste verknüpfter Listen, die jeweils Blöcke eines bestimmten Größenbereichs enthalten.

Ich habe zufällig an der TCMalloc -Bibliothek gearbeitet, die Ihnen dabei helfen könnte, dies klarer zu verstehen

Speicherzuweisung durch Freelists

Nehmen wir an, Klasse 0 ist eine verkettete Liste von freien Blöcken der Größe 4k, Klasse 1 ist eine verkettete Liste von freien Blöcken der Größe 8k und so weiter.

Wenn ein Aufruf von malloc ausgeführt wird (z. B. in der Größe 10k), durchläuft Ihre malloc-Implementierung die Freelist , um den kleinsten freien Block zu ermitteln, der die Anforderung erfüllen würde (In diesem Fall a 4k Block wäre nicht ausreichend, also holt man einen 8k Block, entfernt ihn von der Freelist und gibt ihn an Ihr Programm zurück.

Ähnlich, wenn ein Aufruf von free gemacht wird, sollte Ihre Implementierung (unter anderem) den Block aus dem Programm zurückfordern und ihn an der entsprechenden Stelle einer der Freelisten .     

Es hängt von den Anforderungen ab, zum Beispiel, dass Sie eingebettete Software erstellen wollen, wo es manchmal nicht erlaubt ist, malloc / free während der Laufzeit oder aus Leistungsgründen zu machen. Sie könnten dann stattdessen Ihre eigene Version von malloc / free erstellen, die keinen Speicher freigibt / freigibt, sondern stattdessen nur Blöcke aus einem im Voraus zugewiesenen Heap abruft.

Wenn Sie über das Aufrufen von malloc() und free() Aufrufen sprechen, können Sie das mit etwas wie diesem tun:

Wenn Sie jedoch davon sprechen, Ihren eigenen Speicherzuordner zu erstellen, dann sollten Sie sich eine der Implementierungen von Heap Allocator von Kernighan und Ritchie in ihrem Buch "The C Programming Language 2nd Edition" ansehen. Es basiert im Wesentlichen auf der Verwendung der Systemfunktion sbrk() , um die Größe des Datensegments für den Prozess zu erhöhen.

Ich denke, sie könnten / sollten die Frage anders formulieren: "Wie wird der Heapspeicher von malloc verwaltet und ist er frei?".

Dann können Sie sich das Problem auf eine etwas andere Art und Weise vorstellen - angesichts einer linearen Liste von Werten, wie Sie Teile der Liste aufteilen und verfolgen, wie Sie Teile dieser Liste zurückgeben, wie geht es Ihnen Fragmentierung der Liste usw. verwalten.

Kurz gesagt, obwohl die Adresse des nächsten freien Blocks in dem Heap neben dem Block gespeichert ist, der zugeordnet ist, ist die Information darüber, wo das nächste freie Speicherstück gespeichert ist, für den Benutzer unsichtbar, ist aber immer noch Teil desselben Heapspeichers . Dies ist der Grund, warum ein überlaufender mallocated Speicher den Heap komplett korrumpieren kann und dazu führen kann, dass malloc und free abstürzen.

Normalerweise benutzt der Interviewer die Frage, um Ihnen die Freiheit zu geben, Ihr Wissen zu demonstrieren. Sie können mit der Grundfunktionalität beginnen und dann, wenn Sie wissen, dass Ihre Zwiebeln daran arbeiten, wie verschiedene O / S es handhaben, was die verschiedenen Algorithmen sind usw. Was Sie auch beschreiben würden, ist wahrscheinlich nicht die letzten zwanzig Jahre von R & amp; zu dem Thema!