Programy alokacji Malloc

Question

Tak, prowadzę kurs systemów komputerowych. Miałem kilka pytań na temat różnych systemów alokacji w celu wdrożenia malloc. W przypadku jawnych list, jeśli implementuję malloc przy użyciu stosu typu LIFO, jaki jest dokładnie cel posiadania wskaźników do poprzednio zwolnionej pamięci? Na przykład, dlaczego potrzebujesz podwójnie powiązanych list? Czy pojedynczo połączone listy nie działają równie dobrze?

Malloc lecture. Znalazłem ten link online, możesz zobaczyć slajd 7, aby zobaczyć, o czym mówię.

Przyglądając się schematowi rozdzielonych list, te listy są jednokierunkowe, prawda? A także, czym właściwie jest mechanizm koalescencji? Na przykład, jeśli 4 słowa zostaną zwolnione, czy najpierw spróbujesz dołączyć do niego, gdy wolna przestrzeń wokół ciebie zostanie wstawiona z powrotem na odpowiednią segregowaną listę połączoną? A może po prostu wstawisz blok 4 słów w sekcji "4 słowa" odpowiedniej segregowanej listy połączonej?

Dziękuję.

Answer 1

Ponieważ zwolniony blok zawsze ma miejsce na dwa wskaźniki, dlaczego nie powinien podwójnie łączyć listy? Upraszcza kod koalescencyjny, więc nie musi utrzymywać wskaźnika na końcu podczas przeglądania listy. Pozwala także na przechodzenie listy w dowolnym kierunku w przypadku, gdy istnieje podpowiedź, dla której koniec listy może być bliższy rozpoczęciu wyszukiwania. Jeden niejasny system, który kiedyś widziałem, trzymał wskaźnik w "środku", gdzie nastąpiła ostatnia aktywność.

Podczas zwalniania bloku. Istnieją tylko cztery możliwe przypadki:

• Wolna blok sąsiaduje po darmowa bloku.
• Bezpłatny blok przylega do przed darmowy blok.
• Wolny blok znajduje się pomiędzy i obok wolnych bloków przed i po nim.
• Bezpłatny blok nie sąsiaduje z żadnym wolnym blokiem.

Celami koalescencyjny sąsiadujących wolnych bloków są:

• zmniejszyć długość połączonej listy
• dokładnie odzwierciedlać wielkość wolnego bloku bez obciążania podzielnika patrzeć w przyszłość, aby zobaczyć jeśli dwa bloki sąsiadują z sobą:

Sortowanie wolnego bloku na freelistę o określonej długości często przynosi korzyści, ale w większości praktycznych wdrożeń koalescencja jest priorytetem, tak aby alloc() wniosek o blok o innym rozmiarze nie jest niewłaściwie odrzucany, gdy istnieje wiele różnej wielkości wolnych bloków.