Sprytne zarządzanie pamięcią ze stałymi operacjami czasowymi?

18

Rozważmy segment pamięci (którego rozmiar może się zwiększać lub zmniejszać, jak plik, w razie potrzeby), na którym można wykonać dwie podstawowe operacje alokacji pamięci obejmujące bloki o stałym rozmiarze:

  • przydział jednego bloku
  • uwolnienie wcześniej przydzielonego bloku, który nie jest już używany.

Ponadto, jako wymaganie, system zarządzania pamięcią nie może poruszać się po aktualnie przydzielonych blokach: ich indeks / adres musi pozostać niezmieniony.

Najbardziej naiwny algorytm zarządzania pamięcią zwiększyłby licznik globalny (o wartości początkowej 0) i użyłby swojej nowej wartości jako adresu do następnej alokacji. Jednak nigdy nie pozwoli to skrócić segmentu, gdy pozostanie tylko kilka przydzielonych bloków.

Lepsze podejście: zachowaj licznik, ale zachowaj listę zwolnionych bloków (które można wykonać w stałym czasie) i używaj jej jako źródła nowych alokacji, o ile nie jest pusta.

Co następne? Czy można zrobić coś sprytnego, wciąż z ograniczeniami ciągłego przydzielania i zwalniania czasu, które utrzymywałyby możliwie najmniejszy segment pamięci?

(Celem może być śledzenie aktualnie nieprzydzielonego bloku o najmniejszym adresie, ale wydaje się, że nie jest to możliwe w stałym czasie…)

Stéphane Gimenez
źródło
czy sprawdzanie listy nie byłoby już ciągłe, ponieważ lista mogłaby się powiększać lub zmniejszać z powodu wcześniej dokonanych przydziałów / przydziałów?
Sim
@Sim, zakładałem, że jest to lista połączona, a wraz z nią operacjami będzie , ponieważ zawsze pracujesz tylko z głową. O(N.)
sick
Myślę, że twoje „lepsze podejście” wykorzysta już optymalną ilość pamięci, tzn. Nigdy nie przydzieli dodatkowej pamięci, jeśli jest wolny blok. Jak twoim zdaniem poprawiłoby się „sprytne” podejście? Czy masz na myśli, że powinien on przydzielić blisko początku, aby była większa szansa na zmniejszenie segmentu po zwolnieniu?
svick
@Sim: Przykro mi, może powinienem był użyć terminu stos (ale myślałem, że może to być mylące), „deallocate” to push, a „alokacja” to pop, lub w przypadku niepowodzenia po prostu wracam do przyrostu licznika. Oba są stałym czasem.
Stéphane Gimenez
Czy masz ograniczenia czasu rzeczywistego, czy też jesteś w porządku z amortyzowanym stałym czasem? Odpowiedzi będą prawdopodobnie zupełnie inne.
Gilles „SO- przestań być zły”

Odpowiedzi:

11

W przypadku bloków o stałym rozmiarze opisana jest bezpłatna lista . Jest to bardzo popularna technika z następującym zwrotem: lista wolnych bloków jest przechowywana w samych wolnych blokach. W kodzie C wyglądałoby to tak:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Działa to dobrze, o ile wszystkie przydzielone bloki mają ten sam rozmiar, a ten rozmiar jest wielokrotnością wielkości wskaźnika, dzięki czemu wyrównanie zostaje zachowane. Alokacja i dezalokacja są czasem stałym (to znaczy tak samo stałym, jak dostęp do pamięci i elementarne dodatki - w nowoczesnym komputerze dostęp do pamięci może wiązać się z brakami pamięci podręcznej, a nawet z pamięcią wirtualną, stąd dostęp do dysku, więc „stały czas” może być dość duży). Nie ma narzutu pamięci (żadnych dodatkowych wskaźników na blok itp.; Przydzielone bloki są ciągłe). Ponadto wskaźnik alokacji osiąga dany punkt tylko wtedy, gdy kiedyś trzeba było alokować wiele bloków: ponieważ alokacja woli korzystać z wolnej listy, wskaźnik alokacji jest zwiększany tylko wtedy, gdy przestrzeń pod bieżącym wskaźnikiem jest pełna. W tym sensie, technika.

Malejącywskaźnik alokacji po wydaniu może być bardziej złożony, ponieważ wolne bloki można niezawodnie zidentyfikować tylko postępując zgodnie z bezpłatną listą, która przechodzi przez nie w nieprzewidywalnej kolejności. Jeśli zmniejszenie wielkości dużego segmentu, gdy jest to możliwe, jest dla Ciebie ważne, możesz zastosować alternatywną technikę, z większym narzutem: między dowolnymi dwoma przydzielonymi blokami umieszczasz „dziurę”. Otwory są połączone razem z podwójnie połączoną listą, w kolejności pamięci. Potrzebujesz formatu danych dla otworu, abyś mógł zlokalizować adres początkowy otworu, wiedząc, gdzie się on kończy, a także rozmiar otworu, jeśli wiesz, gdzie otwór zaczyna się w pamięci. Następnie, po zwolnieniu bloku, tworzysz otwór, który łączysz z następnym i poprzednim otworem, odbudowując (wciąż w stałym czasie) uporządkowaną listę wszystkich otworów. Narzut wynosi wtedy około dwóch słów wielkości wskaźnika na przydzielony blok; ale przy tej cenie można niezawodnie wykryć wystąpienie „ostatniej dziury”, tj. okazji do zmniejszenia dużego segmentu.

Istnieje wiele możliwych wariantów. Dobrym materiałem wprowadzającym jest Dynamic Storage Allocation: A Survey and Critical Review autorstwa Wilson i in.

Thomas Pornin
źródło
4
Jak znaleźć dziury najbliżej miejsca zwolnienia w stałym czasie?
Raphael
1
W drugiej metodzie, którą opisuję, otwór to nagłówek (para wskaźników, lista otworów) wraz z miejscem na zero, jeden lub więcej bloków danych. Pomiędzy dwoma dowolnymi przydzielonymi blokami zawsze znajduje się otwór, nawet jeśli jest to mikro-otwór składający się tylko z nagłówka otworu. Tak więc zlokalizowanie najbliższych otworów jest łatwe: znajdują się tuż przed i zaraz po szczelinie. Oczywiście mikrootwory nie są częścią bezpłatnej listy (listy dziur kwalifikujących się do alokacji). Innym sposobem na to jest to, że dodajesz nagłówek do każdego bloku i każdego (nie-mikro) otworu (alokacja pod 16-bitową Ms-Dos działała w ten sposób).
Thomas Pornin
4

Ta odpowiedź dotyczy ogólnych technik zarządzania pamięcią. Nie zauważyłem, że pytanie dotyczy przypadku, w którym wszystkie bloki mają ten sam rozmiar (i są wyrównane).


Podstawowe strategie, które powinieneś znać, to: pierwsze dopasowanie, następne dopasowanie, najlepsze dopasowanie i system znajomych . Raz napisałem krótkie podsumowanie kursu, którego nauczałem, mam nadzieję, że będzie czytelne. Wskazuję na dość wyczerpującą ankietę .

W praktyce zobaczysz różne modyfikacje tych podstawowych strategii. Ale żaden z nich nie jest naprawdę stały! Nie sądzę, że jest to możliwe w najgorszym przypadku, gdy używa się ograniczonej ilości pamięci.

rgrig
źródło
Co ciekawe, muszę to szczegółowo przeczytać. Wydaje się jednak, że systemy te zajmują się w szczególności niestałymi przydziałami wielkości, co nie stanowi problemu.
Stéphane Gimenez
Dobrze. Przepraszam, przeczytałem zdecydowanie za szybko twoje pytanie.
rgrig
O(lgn)
s / najmniejszy wolny blok / wolny blok pod najmniejszym adresem /
rgrig
2

Możesz rzucić okiem na analizę zamortyzowaną, aw szczególności tablice dynamiczne. Nawet jeśli operacje nie są tak naprawdę wykonywane na bieżąco na każdym kroku, na dłuższą metę wygląda na to, że tak jest.

gallais
źródło
2
I w jaki sposób tablice dynamiczne pomogą w alokacji pamięci?
sick
Czy (de) przydzielisz fragmenty ciągłych komórek przy użyciu tego samego rodzaju algorytmu? Cały Twój plik byłby połączoną listą coraz większych fragmentów.
Gallais