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

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…)

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.

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.

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.