14. Zarządzanie pamięcią

W poprzednich rozdziałach rzadko zerkaliśmy za kulisy, żeby zobaczyć, jak naprawdę jest wykonywany program i jak są przechowywane zmienne różnych typów. Było to spowodowane tym, że w książce tej koncentrowaliśmy się na strukturach danych, a nie na wewnętrznych szczegółach działania komputera.
Takie odwołanie było jednak nie do uniknięcia przynajmniej w jednym wypadku, a mianowicie przy omawianiu rekursji w rozdziale 7. Stosowanie rekursji wyjaśnialiśmy na podstawie zmian zachodzących na stosie programu, pokazując w ten sposób, jak naprawdę działa komputer. Poruszyliśmy również tę problematykę przy omawianiu dynamicznego przydzielania pamięci. Trudno byłoby zrozumieć zagadnienie dynamicznego przydziału pamięci bez dobrej znajomości struktury pamięci komputera i świadomości tego, że bez użycia funkcji malloc() czy calloc() wskaźniki mogłyby wskazywać na nie przydzielone miejsca w pamięci. Trzeba również wiedzieć, że aby uniknąć wyczerpania zasobów pamięci komputera, należy używać funkcji f ree (). Jeśli chodzi o zarządzanie pamięcią, to w języku C odpowiedzialność spoczywa na programiście, a cała pamięć może się wypełnić nieosiągalnymi blokami, które nie zostały zwolnione za pomocą funkcji f ree (), jeśli programista okaże się nierozważny. Najefektywniejszą i najelegantszą strukturę programu może unicestwić przydzielanie zbyt wielkiej ilości pamięci.
Kopiec jest obszarem w pamięci głównej, z którego na żądanie programu są dynamicznie przydzielane bloki pamięci. (Kopiec ten nie ma nic wspólnego ze specjalną drzewiastą strukturą również zwaną kopcem i omówioną w podrozdziale 8.9). W językach takich jak Fortran czy Cobol kompilator może z góry określić, ile pamięci potrzeba do wykonania programu. W językach dopuszczających dynamiczne przydzielanie pamięci rozmiar potrzebnej pamięci nie zawsze można wyznaczyć przed uruchomieniem programu. Dlatego właśnie jest używany kopiec. Jeśli program w języku C żąda pamięci, wywołując funkcję malloc (), to pewna liczba bajtów określona za pomocą sizeof () albo w inny sposób, zostaje zarezerwowana w kopcu, po czym zostaje zwrócony adres pierwszego bajtu tego bloku pamięci.
Jak już napomknęliśmy, w języku C za zarządzanie, pamięcią jest odpowiedzialny programista. Inną strategią w zarządzaniu pamięcią jest przerzucenie odpowiedzialności

488

za przydzielanie i zwalnianie pamięci z programisty na system operacyjny lub raczej jego część zwaną zarządcą pamięci (ang. metnory manager}. Zarządca pamięci zajmuje się pulą wolnych bloków pamięci, przydziela bloki pamięci programom użytkownika i oczyszcza pamięć, zwracając niepotrzebne już bloki do puli(Zarządca pamięci realizuje także inne funkcje, jak planowanie dostępu do danych dzielonych, przemieszczanie kodu i danych między pamięcią główną a pomocniczą oraz sparowanie od siebie poszczególnych procesów.). Co istotne, funkcje te są wykonywane automatycznie, bez interwencji użytkownika. Użytkownik może uświadomić sobie, że procesy te zachodzą, kiedy musi czekać na zakończenie operacji czyszczenia pamięci, ale to zarządca decyduje, kiedy powinna ona zostać wykonana.
Automatyczne odzyskiwanie pamięci to luksus, który nie stanowi części środowiska każdego języka programowania. Pojawiło się ono wraz z językiem Lisp i większość badań nad odzyskiwaniem pamięci dotyczyła środowiska Lispu, ale prowadzi się je także w połączeniu z językami Smalltalk, Prolog, C++, Modula-3 i innymi. Automatyczne czyszczenie pamięci uwalnia programistę od zajmowania się przydzielaniem i zwalnianiem pamięci.
Jednym z problemów, które dobrze zaprojektowany zarządca pamięci musi umieć rozwiązać, jest konfiguracja dostępnej pamięci. Zwracając pamięć za pomocą funkcji f ree (), programista nie ma żadnej kontroli nad tą konfiguracją. Zwłaszcza po wielu operacjach przydziału i zwolnienia pamięci kopiec jest podzielony na małe kawałki wolnej pamięci przeplecione z partiami pamięci będącej w użyciu. Kiedy zatem przychodzi żądanie przydziału n bajtów pamięci, nie można go zrealizować, bo w kopcu nie ma dostatecznie dużego ciągłego obszaru, chociaż łączna ilość wolnej pamięci może znacznie przekraczać n. Zjawisko to jest nazywane fragmentacją zewnętrzną. Zmiana konfiguracji pamięci, a w szczególności umieszczenie wolnej pamięci w jednej części kopca, a już przydzielonej pamięci w drugiej jego części, rozwiązuje ten problem. Kolejnym problemem jest fragmentacją wewnętrzna, występująca wtedy, kiedy przydzielane fragmenty pamięci są większe niż żądane. Jest to nieodłączna wada niektórych metod zarządzania pamięcią. W niniejszym rozdziale omawiamy kilka spośród wielu sposobów odzyskiwania pamięci.

14.1. Metody dopasowywania sekwencyjnego

Prosta metoda organizacji pamięci mogłaby polegać na przechowywaniu listy wszystkich bloków pamięci, uaktualnianej po realizacji żądania przydziału albo zwolnienia bloku. Bloki na takiej liście mogą być uporządkowane na różne sposoby: ze względu na rozmiary lub na adresy bloków. Kiedy przychodzi żądanie przydzielenia bloku, trzeba podjąć decyzję, który blok przydzielić i jak potraktować fragment bloku przekraczający żądany rozmiar.
Z uwagi na efektywność listy bloków są dwukierunkowe, a dowiązania znajdują się w blokach. W każdym wolnym bloku część pamięci jest wykorzystana do przechowywania dwóch dowiązań. Oprócz tego zarówno wolne, jak i zajęte bloki zawierają po dwa pola określające ich stan (wolne/zajęte) i rozmiar.












489

W metodach dopasowywania sekwencyjnego wszystkie wolne bloki pamięci są ze sobą połączone, a ich listę przeszukuje się w celu znalezienia bloku o rozmiarze większym bądź równym żądanemu. Prosta strategia traktowania zwolnionych bloków pamięci polega na sklejeniu ich z sąsiadującymi blokami i odnotowaniu tego faktu przez odpowiednie poprawienie dowiązań na liście.
Ze względu na sposób przeszukiwania listy metody te można podzielić na kilka kategorii. Metoda "pierwszy-pasujący" (ang. first-fii) powoduje przydzielenie pierwszego bloku pamięci wystarczająco dużego, aby móc spełnić żądanie. Metoda "naj-lepiej-pasujący" (ang. best-fit) powoduje przydzielenie bloku najbliższego rozmiarem żądanemu. W metodzie "najgorzej-pasujący" (ang. worst-fit) znajduje się największy blok na liście, dzięki czemu po zwróceniu jego fragmentu o rozmiarze równym żądanemu pozostała część jest na tyle duża, że można ją będzie wykorzystać przy realizacji następnych żądań. W metodzie "następny-pasujący" (ang. next-fif) przydziela się następny (po bieżącym) wolny blok o dostatecznym rozmiarze.
Na rysunku 14.1a jest przedstawiona konfiguracja pamięci po realizacji kilku żądań przydziału i zwolnień bloków pamięci, a na rysunku 14.1b jest pokazane, które bloki zostałyby przydzielone przy zastosowaniu poszczególnych metod sekwencyjnego dopasowywania do realizacji żądania 8 KB pamięci.1

Rys. 14.1. Przydzielanie pamięci z użyciem metod sekwencyjnego dopasowywania

Najefektywniejsza jest metoda "pierwszy-pasujący". Metoda "następny-pasujący" jest z nią porównywalna pod względem szybkości, ale prowadzi do znacznie silniejszej fragmentacji zewnętrznej, ponieważ przegląda się tu listę bloków, poczynając od pozycji bieżącej, i dociera do końca listy znacznie wcześniej niż przy użyciu metody "pierwszy-pasujący". Metoda "najlepiej-pasujący" jest jednak jeszcze gorsza z tego punktu widzenia, ponieważ prowadzi do wyszukania bloku najbliższego


490

rozmiarem żądanemu. Części bloków pozostające po przydzieleniu fragmentów wymaganego rozmiaru są małe i praktycznie bezużyteczne. W metodzie "najgorzej--pasujący" próbuje się zapobiec temu rodzajowi fragmentacji unikając, a przynajmniej opóźniając tworzenie się małych bloków.
Kolejność ustawienia bloków na liście decyduje o tym, ile trwa kończące się sukcesem lub niepowodzeniem poszukiwanie wolnego bloku. Na przykład dla metod "najlepiej-pasujący" i "najgorzej-pasujący" najwłaściwsze jest ułożenie bloków pod względem rozmiarów. Dla pozostałych metod odpowiednie jest uporządkowanie według adresów.

14.2. Metody niesekwencyjne

Metody sekwencyjnego dopasowywania ze względu na swoją sekwencyjną naturę mogą stawać się nieefektywne, jeśli pamięci jest dużo. W przypadku dużej ilości pamięci warto byłoby stosować niesekwencyjne sposoby wyszukiwania. Jedna ze strategii polega na podziale kopca na ustaloną liczbę list, z których każda zawiera bloki tego samego rozmiaru [5]. Większe bloki są dzielone na mniejsze w celu spełnienia żądań przydziału pamięci, a przy okazji mogą być tworzone nowe listy. Ponieważ liczba takich list bywa duża, można z nich utworzyć drzewo.
Inne rozwiązanie opiera się na obserwacji, że liczba rozmiarów bloków, których przydzielenia żąda program, jest ograniczona, chociaż żądania poszczególnych programów mogą różnić się między sobą. Lista bloków różnych rozmiarów może więc pozostać krótka, jeśli stwierdzimy, które rozmiary są najpopularniejsze. Prowadzi to do metody adaptacyjnego dokładnego dopasowywania (ang. adaptive exact-fit}, w której dynamicznie tworzy się i uaktualnia listy bloków pamięci dokładnie realizujących żądania [4].
W metodzie tej są przechowywane listy bloków określonego rozmiaru, zwróconych do puli pamięci podczas ostatnich T operacji przydziału. Zwolniony właśnie przez program blok b jest dodawany do listy bloków tego samego rozmiaru co b. Kiedy przychodzi żądanie przydzielenia bloku rozmiaru b, w celu jego spełnienia jeden z bloków jest odłączany od tej listy. W przeciwnym razie rozpoczyna się bardziej czasochłonne poszukiwanie bloku w kopcu przy użyciu jednej z metod sekwencyjnego dopasowywania.
Jeśli podczas ostatnich T operacji przydziału nie nadeszło żądanie przydzielenia żadnego bloku z danej listy, to cała lista jest likwidowana. Dzięki temu nie przechowuje się list bloków rzadko używanych rozmiarów, a zbiór list bloków pozostaje niewielki, co pozwala na jego sekwencyjne przeszukiwanie. Ponieważ nie jest to sekwencyjne przeszukiwanie całej pamięci, metody dokładnego dopasowywania nie zalicza się do metod dopasowywania sekwencyjnego.
Na rysunku 14.2 widać przykład listy rozmiarów i kopca utworzonych metodą adaptacyjnego dokładnego dopasowywania. Pamięć uległa fragmentacji, ale jeśli napływa żądanie przydzielenia bloku rozmiaru 7, można je zrealizować natychmiast,





491

Rys. 14.2. Przykład konfiguracji listy rozmiarów i kopca, utworzonych metodą adaptacyjnego dokładnego dopasowywania
ponieważ na liście rozmiarów jest element odpowiadający rozmiarowi 7, nie trzeba więc przeszukiwać całego kopca. Prosty algorytm przydzielania bloków wygląda następująco:
t = 0;

allocate (reąsize)
t++;
if lista blobloków rozmiaru reąsize figuruje na liście rozmiarów size_list
lastref (bl) = t; /* moment ostatniego odwołania */
/* do listy bl */
b = blocks (łoi) ; /* pierwszy element listy b1 */
if b był jedynym blokiem na liście b1
usuń b1 z size_list;
else b = szukaj_w_kopcu_bloku_rozmiaru (reqsize) ;
usuń z size_list wszystkie listy bloków b1, dla których
t - lastref (b1) < T;
return b;

Procedura zwalniania bloków jest jeszcze prostsza.
Algorytm ten uwidacznia problem fragmentacji pamięci. Aby można było z tym problemem skutecznie sobie radzić, trzeba algorytm rozbudować. Jednym z rozwiązań jest napisanie procedury upakowania kopca (łączenia osobnych obszarów pamięci w jeden spójny blok) po pewnej liczbie operacji przydziału i zwolnienia pamięci. Inny sposób mógłby polegać na kasowaniu listy rozmiarów i tworzeniu jej na nowo po jakimś z góry określonym czasie. Autorzy tej metody twierdzą, że przy jej testowaniu problem fragmentacji "nie wystąpił", ale mogło to być związane z konfiguracją ich testów. Problem na pewno pojawia się w algorytmach sekwencyjnego dopasowywania, a także w kolejnej niesekwencyjnej metodzie omawianej w następnym podrozdziale.

492

14.2.1. Systemy par

W niesekwencyjnych metodach zarządzania pamięcią, zwanych metodami systemów par (metodami "bliźniaków", ang. buddy systems], nie operuje się po prostu na pojedynczych blokach, ale dzieli pamięć na pary bloków, które skleja się, jeśli tylko jest to możliwe. W systemie par nigdy nie zdarza się, żeby obydwa bloki tworzące parę były wolne. Wolny blok może albo mieć towarzysza wykorzystywanego właśnie przez program, albo wcale go nie mieć.
Klasyczną wersję stanowi binarny system par [10]. Zakłada się w nim, że pamięć składa się z 2'" komórek dla pewnej liczby naturalnej m, o adresach O, ..., 2^(m)-1, oraz że komórki te można ustawiać w bloki o rozmiarach będących potęgami dwójki. Potrzebna jest także tablica avail[], która dla każdego i = 0, ..., m w komórce avail[i] zawiera początek dwukierunkowej listy bloków tego samego rozmiaru 2^i.
Nazwa tej metody bierze się stąd, że każdy blok pamięci (z wyjątkiem całości pamięci) jest stowarzyszony z drugim blokiem tego samego rozmiaru, który wraz z nim bierze udział w przydzielaniu i zwalnianiu obszarów pamięci. Adres towarzysza bloku rozmiaru 2^i wyznacza się, biorąc dopełnienie (i+1)-ego bitu w adresie tego bloku. Jest to ściśle związane z tym, że rozmiary bloków mogą być wyłącznie potęgami dwójki. W szczególności adresy wszystkich bloków rozmiaru 2^i mają zera na ostatnich i pozycjach z prawej strony, a różnią się jedynie pozostałymi bitami. Jeśli na przykład pamięć składa się tylko z ośmiu komórek, to możliwymi adresami bloków rozmiaru l są {000, 001, 010, 011, 100, 101, 110, 111}, adresami bloków rozmiaru 2 są {000, 010, 100, 110}, rozmiaru 4 - {000, 100}, a rozmiaru 8 - {000}. Łatwo spostrzec, że w drugim zbiorze adresów ostatnim bitem jest O, a adresy odnoszą się do bloków rozmiaru 2^i. Adresy z trzeciego zbioru mają na końcu dwa zera, a odnoszą się do bloków rozmiaru 22. W drugim zbiorze występują dwie pary złożone z bloku i jego towarzysza: {(000, 010), (100, 110)}, a w trzecim jest tylko jedna taka para, mianowicie {(000, 100)}. Adresy bloku rozmiaru 2' i jego towarzysza z pary różnią się zatem tylko (i+1)-ym bitem.
Jeśli pojawia się żądanie przydzielenia bloku pamięci rozmiaru s, to system par musi zwrócić blok rozmiaru większego bądź równego s. Ponieważ jest na to zwykle wielu kandydatów, sięga się do listy bloków w tablicy avail[] takiej, że rozmiar tych bloków, 2^k>=s, jest najmniejszy. Listę tę można znaleźć na pozycji avail[k]. Jeśli lista jest pusta, to sprawdza się następną listę bloków na pozycji k+1, potem k+2 itd. Poszukiwanie trwa aż do znalezienia niepustej listy (albo osiągnięcia końca tablicy avail[]), od której następnie odłącza się blok.

rozmiar pamięci - 2^m dla pewnego m; avail[i] = -1 dla i = 0, . . . ,m-1 ;
avail[m] = adres kopca;
reserve(req_size)
rounded_size = [lg(req_size)];









493

avail_size = mm (rounded_size, . . .,m) takie, że avail[avail_size] > -1 ;
if takie avail_size nie istnieje
bloku nie można przydzielić;
else błock = avail[avail_size];
odłącz blok od listy avail[avail_size];
while (rounded_size < avail_size) /* dopóki wolny blok jest */
avail_size--; /* za duży - rozbijaj go */
błock = lewa polowa bloku błock;
wstaw towarzysza bloku błock na listę avail[avail_size] ;
return błock;

Rys. 14.3. Struktura bloku w binarnym systemie par

Każdy wolny blok w systemie par powinien zawierać cztery pola określające jego stan, rozmiar i dwóch sąsiadów na liście. Z kolei w blokach zajętych potrzebne jest tylko pole stanu. Na rysunku 14.3 z lewej strony widać strukturę wolnego bloku w systemie par. Blok jest wolny, bo jego pole stanu zawiera wartość 0. Rozmiarem bloku jest 25. Poprzednik nie jest określony, więc to ten właśnie blok jest wskazywany przez avail[5]. Rozmiar jego następnika to również 25. Z prawej strony rysunku 14.3 widać blok zajęty, który w polu stanu ma wartość 1.
Na rysunku 14.4 jest przedstawiony przykład przydzielenia trzech bloków pamięci, przy założeniu, że użytkowana pamięć składa się z 27=128 komórek. Początkowo cała pamięć jest wolna (rys. 14.4a). Następnie nadchodzi żądanie przydzielenia bloku rozmiaru 18. Wartością rounded_size jest [~lg(18)l = 5, ale avail_size = 7, pamięć rozbija się więc na parę bloków, każdy rozmiaru 2fi, a drugi z nich oznacza się jako wolny, zapisując to w jego polu stanu i włączając go do listy avail[6] (rys. 14.4b). Wartość avail_size jest w dalszym ciągu większa niż rounded_size, jest więc wykonywana kolejna iteracja pętli while w funkcji reserve(). Pierwszy blok jest rozbijany na dwa mniejsze, a drugi z nich zostaje włączony do listy avail[5] (rys. 14.4c). Pierwszy z mniejszych bloków zostaje oznaczony jako zajęty i zwrócony wywołującemu funkcję reserve () do wykorzystania. Zauważmy, że chociaż naprawdę potrzebna jest tylko część zwracanego bloku, to jako zajęty oznacza się cały przydzielony blok.

496

Rys. 14.4. Przydzielenie trzech bloków pamięci w binarnym systemie par

495

Następne żądanie dotyczy bloku rozmiaru 14; teraz rounded_size=[lg(14)]=4, avail_size = 5 i sięgamy po blok wskazywany przez avail[5] (rys. 14.4d). Jest on za duży, ponieważ rounded_sizeBloki pamięci nie tylko się przydziela, lecz także i zwalnia, a wtedy trzeba je zwrócić do puli wolnych bloków. Zanim się je tam dołączy, sprawdza się stan towarzysza z pary danego bloku. Jeśli jest on wolny, to obydwa bloki łączy się w jeden, dwukrotnie większy. Jeśli towarzysz z pary nowo otrzymanego bloku również jest wolny, to znowu łączy się oba bloki w jeden większy. Proces ten trwa dopóty, dopóki nie skleimy całej pamięci w jeden blok albo dopóki blok stanowiący parę dla bieżącego nie okaże się zajęty. W wyniku takiego sklejania otrzymujemy bloki wolnej pamięci tak duże, jak to tylko możliwe. Algorytm włączania bloku do puli wolnych bloków wygląda następująco:

include(błock)
block_size - rozmiar bloku błock;
buddy = adres bloku błock z zanegowanym bitem block_size+1;
while block_size != m /* blok błock ma parę */
i stanem bloku buddy jest 0 /* blok buddy jest wolny */
usuń blok buddy z listy avail[block_size];
błock = błock plus buddy; /* połącz bloki błock i buddy w jeden */
zapisz 0 jako stan bloku błock;
block_size++;
buddy = adres nowego bloku błock z zanegowanym bitem block_size+l ;
dołącz blok błock do listy avail[block_sizej;

Cały proces jest zilustrowany na rysunku 14.5. Zajęty wcześniej blok zostaje teraz zwolniony (rys. 14.5a), a ponieważ blok tworzący z nim parę jest wolny, obydwa zostają połączone w jeden dwukrotnie od nich większy blok, który włączamy do listy avail[5] (rys. 14.5b). Zwolnienie kolejnego bloku pozwala zarządcy pamięci na połączenie go z jego towarzyszem, a następnie sklejenie tak otrzymanego bloku z drugim, tworzącym z nim parę (rys. 14.5c). Zwróćmy uwagę, że nie wykorzystana część pierwszego bloku z lewej strony (zaznaczona ciemniejszym kolorem) nie uczestniczyła w procesie sklejania i nadal jest traktowana jako zajęta. Również dwa ostatnie bloki z prawej strony na rysunku 14.5a, chociaż sąsiednie, nie zostały połączone, ponieważ nie tworzą pary. Bloki stanowiące parę w binarnym systemie par muszą być tego samego rozmiaru.
Binarny system par, chociaż stosunkowo szybki w działaniu, może być bardzo nieefektywny, jeśli chodzi o wykorzystanie pamięci. Dwa pierwsze bloki z lewej strony na rysunku 14.5a zajmują w sumie 48 pozycji, z których w użyciu jest zaledwie




496

32, ponieważ użytkownik naprawdę potrzebował 18+ 14 komórek pamięci. Oznacza to, że jedna trzecia tych dwóch bloków się marnuje. Może być nawet jeszcze gorzej, jeśli rozmiar żądanych bloków zawsze nieco przekracza potęgę dwójki. W takim
X
wypadku nie wykorzystuje się około 50% pamięci. Źródłem tego problemu fragmen-tacji wewnętrznej jest konieczność zaokrąglania rozmiarów wszystkich żądanych bloków do najbliższej większej potęgi dwójki.

Rys. 14.5. Zwolnienie bloku (a) powodujące sklejenie bloku z jego towarzyszem z pary; (b) zwolnienie kolejnego bloku prowadzi do dwóch sklejeń

Może tu też wystąpić problem fragmentacji zewnętrznej: odmowa realizacji żądania pomimo istnienia wystarczającej do jego spełnienia ilości wolnej pamięci. Na przykład przy konfiguracji pamięci jak na rysunku 14.4g żądanie przydzielenia bloku rozmiaru 50 zostanie odrzucone, ponieważ nie ma wolnego bloku rozmiaru 64 ani większego. Podobnie zostałoby potraktowane żądanie przydzielenia 33 komórek i to z tego samego powodu, chociaż istnieje wolny ciągły obszar rozmiaru 33. Jedna z jego komórek należy jednak do innego bloku, przez co staje się niedostępna.
Wszystkie te problemy wypływają z faktu, że w binarnym systemie par stosuje się prosty podział bloków na dwie równe części, nie dostosowując w dostatecznym stopniu pamięci do realizacji napływających żądań. Ciąg możliwych rozmiarów blo-

497

ków w tym systemie to 1,2, 4, 8, 16, ..., 2^m. W celu ulepszenia binarnego systemu par zapiszmy ten ciąg za pomocą wzoru rekurencyjnego

s#i={1, jeśli i = 0; s#(i-1)+s#(i-1), w przeciwnym razie

który można uważać za szczególny przypadek ogólniejszego równania
s#i={c#1, jeśli i = 0; ... c#k, jeśli i = k-1; s#(i-1)+s#(i-2), w przeciwnym razie

Jeśli k=1, to powyższe równanie daje nam binarny system par. Jeśli k=2, to otrzymujemy doskonale nam znany wzór na ciąg Fibonacciego:

s#i={1, jeśli i = 0,1; s#(i-1)+s#(i-2), w przeciwnym razie

Prowadzi to do systemu par Fibonacciego, zaproponowanego przez Daniela S. Hirs-chberga. Jako wartości s#0 i s#1 wybrał on liczby 3 i 5. Jeśli k>2, to mamy do czynienia z uogólnionymi systemami Fibonacciego [8].
Problem związany z systemem par Fibonacciego leży w tym, że znalezienie bloku stanowiącego parę dla danego bloku nie zawsze jest proste. W binarnym systemie par informacja zawarta w polu określającym rozmiar bloku wystarcza nam do obliczenia adresu jego towarzysza. Jeśli znajduje się tam liczba k, to adres ten znajdujemy, biorąc dopełnienie (k+ l)-ego bitu w adresie bloku. Metoda ta działa poprawnie niezależnie od tego, czy ten towarzysz leży z lewej czy z prawej strony bloku. Jej prostotę zawdzięczamy temu, że rozmiarami bloków są wyłącznie potęgi dwójki oraz temu, że rozmiary obydwu bloków w parze są takie same.
W systemie Fibonacciego nie da się zastosować tego podejścia, żeby bowiem połączyć zwalniany blok z jego towarzyszem trzeba jeszcze wiedzieć, z której jego strony towarzysz ten się znajduje. Nic więc dziwnego, że znajdowanie pary dla danego bloku bywa dość kosztowne, jeśli idzie o czas i pamięć. Hirschberg używał w tym celu tablicy, która mogła mieć prawie tysiąc elementów, jeśli największym dopuszczalnym rozmiarem bufora było 17717. Jego metodę można uprościć, umieszczając w każdym bloku odpowiednie znaczniki, ale binarny znacznik Lewy/Prawy może okazać się niewystarczający. Jeśli blok b#1, oznaczony jako Lewy skleimy ze stanowiącym dla niego parę blokiem b#2, to powstaje pytanie: jak znaleźć parę dla otrzymanego w ten sposób bloku b#3? Istnieje eleganckie rozwiązanie, w którym używa się nie jednego, ale dwóch binarnych znaczników: bitu pary i bitu pamięci [7]. Jeśli blok b#1 zostaje rozbity na bloki b#left i b#right, to wykonujemy przypisania bit_pary(b#left) = O, bit_pary(b#right) = 1, bit_pamięci(b#left) = bit_pary(b#1) i wreszcie bit_pamięci(b#right) = = bit_pamięci(b#1) (zob. rys. 14.6a). Dwa ostatnie przypisania służą do zachowania pewnej informacji o poprzednikach: bit_pamięci(b#left) informuje, czy blok przed rozbiciem był lewym czy prawym składnikiem pary, natomiast bit_pamięci(b#right) niesie tę samą informację o jednym z jego poprzedników. Proces sklejania jest dokładnym odwróceniem rozbijania (zob. rys. 14.6b).












98

Rys. 14.6. (a) Rozbicie bloku rozmiaru Fib(k) na parę bloków z użyciem bitu pary i bitu pamięci; (b) sklejenie dwóch bloków stanowiących parę na podstawie informacji zapisanej w bitach pary i pamięci

Algorytmy przydzielania i zwalniania bloków są pod wieloma względami podobne do algorytmów dla binarnego systemu par. Algorytm przydzielania bloków wygląda następująco:

avail[i] = -1 dla i = 0, . . . , m-1 ;
avail[m] = adres kopca;

reserveFib(req_size)
avail_size = numer pierwszej liczby Fibonacciego
większej niż req_size i takiej, że avail[avail_size] > -1 ;
if takie avail_size nie istnieje
bloku nie można przydzielić;
else błock = avail[avail_size];
odłącz blok od listy avail[avail_size];

499

while F/6(avail_size-1) > req_size /* dopóki wolny blok jest */
/* za duży - rozbijaj go; */
if req_size <= F/b (avail_size-2) /* jeśli można, wybierz */
/* mniejszy blok z pary */
wstaw większą część bloku błock na listę
avail[avail_size-1];
błock = mniejsza część bloku błock;
else wstaw większą część bloku błock na listę avail[avail_size-2];
błock = większa część bloku błock;
avail_size = numer liczby Fibonacciego będącej
rozmiarem bloku błock;
ustaw znaczniki bloku błock;
ustaw znaczniki towarzysza bloku błock;
return błock;

Innym rozszerzeniem binarnego systemu par jest ważony system par [12]. Jego celem, tak jak w wypadku systemów Fibonacciego, jest zmniejszenie stopnia frag-mentacji wewnętrznej przez dopuszczenie większej liczby różnych rozmiarów bloków niż w systemie binarnym. Rozmiary bloków w ważonym systemie par działającym na 2^m jednostkach pamięci są postaci 2^k dla 0<=k<=m oraz 3*2^k dla 0<=k<=m - 2, czyli 1, 2, 3, 4, 6, 8, 12, 16, 24, 32,..., jest ich więc prawie dwa razy więcej niż w metodzie binarnej. Jeśli trzeba, bloki rozmiaru 2^k rozbija się na bloki 3*2^(k-2) i 2^(k-2), a bloki rozmiaru 3 * 2^k na bloki
3*2^(k+1) i 2^(k). Zauważmy, że pary dla bloku rozmiaru 2* nie można wyznaczyć jednoznacznie, ponieważ może on mieć albo prawego towarzysza rozmiaru 2^(k+1) lub 3*2^k, albo lewego towarzysza rozmiaru 2^(k+1). W celu rozróżnienia tych trzech przypadków do każdego bloku dodaje się dwubitowy znacznik rodzaju. Symulacje wykazują jednak, że ważony system par jest trzykrotnie wolniejszy i prowadzi do silniejszej fragmentacji zewnętrznej niż binarny system par. Jak wspomnieliśmy, wymaga on użycia dwóch dodatkowych bitów na blok, a algorytm jest bardziej skomplikowany niż dla binarnego systemu par, wymaga bowiem rozważenia większej liczby przypadków przy sklejaniu bloków.
Systemem pośrednim między systemem binarnym a ważonym jest dualny system par [11]. Operuje się tu dwoma oddzielnymi obszarami pamięci, jednym zawierającym bloki rozmiarów 1, 2, 4, 8, 16, ..., 2^i, ..., i drugim z blokami rozmiarów 3, 6, 12, 24, 48, ..., 3 * 2^i, .... W ten sposób metodę binarną stosuje się w dwóch obszarach. Fragmentacja wewnętrzna w metodzie dualnej lokuje się mniej więcej w połowie drogi między wartościami dla metody binarnej i ważonej. Fragmentacja zewnętrzna w dualnym systemie par jest niemal taka sama jak w binarnym systemie par.
Na zakończenie tych rozważań zauważmy, że często fragmentacja wewnętrzna jest odwrotnie proporcjonalna do zewnętrznej, ponieważ fragmentacji wewnętrznej unika się, jeśli przydzielane bloki są możliwie najbliższe rozmiarem blokom żądanym. Oznacza to jednak tworzenie się przy okazji małych bloków - resztek, trudnych

500

do wykorzystania. Te małe bloki można posklejać w jeden duży za pomocą metod sekwencyjnego dopasowywania, ale sklejanie niezbyt dobrze współgra z podejściem opartym na systemach par. Istnieje wprawdzie metoda, stanowiąca rozwinięcie ważonego systemu par, w której próbuje się dokonywać takiego sklejania, ale złożoność tego algorytmu stawia pod znakiem zapytania jego użyteczność [6].

14.3. Odśmiecanie

W poprzednich podrozdziałach głównym kryterium oceny algorytmów było to, w jakim stopniu prowadzą do fragmentacji wolnej pamięci. Zjawisko to spowodowane jest faktem, że poszczególne żądania zgłaszane w trakcie działania programu różnią się rozmiarami bloków. W wielu sytuacjach rozmiary te są jednak stałe, a algorytmy dynamicznego przydzielania pamięci nie muszą dotyczyć fragmentacji i można się w nich skoncentrować na innych zagadnieniach, jak upakowywanie pamięci lub zawsze aktualny problem kompromisu między szybkością działania a zużyciem pamięci. Algorytmy takie, zwane algorytmami czyszczenia (odśmiecania) pamięci, służą do usuwania bezużytecznych danych z pamięci składającej się z bloków ustalonego rozmiaru, chociaż często rozszerza sieje tak, by mogły zapewnić obsługę bloków o różnych rozmiarach.
Jakaś metoda czyszczenia pamięci wchodzi zwykle w skład środowiska języków przetwarzających listy, w szczególności Lispu. Kiedy pozostaje już niewiele wolnej pamięci, jest automatycznie wywoływana procedura odśmiecająca; działanie programu zostaje na ten czas wstrzymane, a kontynuowane jest dopiero po zakończeniu odśmiecania. Ponieważ programy odśmiecające były tworzone głównie z myślą o językach przetwarzających listy, wypada powiedzieć kilka słów o tym, jak w językach tych jest wykorzystywana pamięć.
Świat języka Lisp jest dość jednorodny: jego zmienne odnoszą się albo do atomów (liczb lub znaków), albo do list. Każdy element listy zawiera dwa wskaźniki, poprzednik i następnik, czyli w terminologii Lispu car i cdr. Operacje języka Lisp przetwarzają takie listy, w wyniku czego często otrzymuje się bardzo rozbudowane struktury wiązane, jak drzewa binarne lub grafy (dozwolone są cykle). Wskaźniki do wszystkich struktur wiązanych wykorzystywanych aktualnie przez program są przechowywane w zbiorze początków, zawierającym wszystkie wskaźniki początkowe. Zadaniem algorytmu odśmiecania jest określenie, które fragmenty pamięci są dostępne z któregokolwiek z tych wskaźników, które natomiast nie są bieżąco używane i mogą wrócić do puli wolnej pamięci.
Metody odśmiecania zawierają zazwyczaj dwie fazy, które mogą być zaimple-mentowane jako oddzielne przebiegi albo stanowić jedną całość:
1. Faza zaznaczania - mająca na celu wyznaczenie wszystkich aktualnie używanych bloków.
2. Faza odzyskiwania - kiedy wszystkie nie zaznaczone bloki wracają do puli pamięci; w fazie tej można także dokonywać upakowywania pamięci.
501
14.3.1. Metoda ,,zaznacz-i-usuń"

Klasyczną metodą odśmiecania jest metoda "zaznacz-i-usuń" (ang. mark-and-sweep), przebiegająca w dwóch odrębnych fazach. Najpierw zaznacza się wszystkie będące właśnie w użyciu komórki pamięci, przebiegając w tym celu wszystkie struktury wiązane, a następnie porządkuje się pamięć, zbierając nie używane komórki i umieszczając je w puli pamięci.

Zaznaczanie

Prosta procedura zaznaczania bardzo przypomina przechodzenie drzewa metodą pre-order. Jeśli węzeł nie jest zaznaczony, to zaznacza się go i, jeżeli nie jest atomem, kontynuuje się zaznaczanie dla jego poprzednika i następnika:

marking(node)
if węzeł node nie jest zaznaczony
zaznacz węzeł node ;
if węzel node nie jest atomem
marking (poprzednik węzła node) ;
marking (następnik węzła node) ;

Procedurę tę wywołuje się dla każdego elementu zbioru początków. Problem związany z tym zwięzłym i eleganckim algorytmem polega na tym, że może on powodować przepełnienie stosu programu, a zagrożenie to jest całkiem realne, jeśli weźmiemy pod uwagę fakt, że zaznaczane listy mogą być bardzo długie. Lepiej zatem użyć stosu w jawnej postaci, dzięki czemu nie trzeba umieszczać na stosie programu danych niezbędnych do właściwego wznowienia działania procedury po powrocie z wywołania rekurencyjnego. Oto przykładowy zapis takiego algorytmu:

MarkingWithStack (node)
clear(S);
push(node, S) ;
while (!empty(S))
node =pop(S) ;
while węzeł node nie jest zaznaczony i nie jest atomem
zaznacz węzeł node ;
push (następnik węzła node) ;
node = poprzednik węzła node ;
if węzeł node nie jest zaznaczony i nie jest atomem
zaznacz węzeł node ;

Problemu przepełnienia i tak się jednak nie uniknie. Jeśli stos S jest zaimplemen-towany jako tablica, to może ona okazać się zbyt mała. Jeśli stos implementuje się jako listę, to jej użycie może być niemożliwe, bo na stos potrzebna jest pamięć, której właśnie brakuje i do której odzyskania ten stos miał się przyczynić. Istnieje kilka sposobów wyjścia z tego impasu: można używać stosu ograniczonego rozmiaru


502

i w razie jego przepełnienia wykonywać specjalne operacje lub można też spróbować wcale nie korzystać ze stosu.
Praktyczny algorytm, nie wymagający używania osobnego stosu, zaproponowali Schorr i Waite. Podstawowy pomysł polega na wbudowaniu, w pewnym sensie, stosu w przetwarzaną listę. Metodę tę należy zaliczyć do tej samej kategorii co przechodzenie drzewa bez użycia stosu, omówione w podrozdziale 8.4.3. W metodzie Schor-ra i Waite'a niektóre dowiązania są w trakcie przechodzenia listy tymczasowo odwracane w celu "zapamiętania" drogi powrotnej, a ich pierwotne wartości są odtwarzane po zaznaczeniu wszystkich komórek dostępnych z miejsca, w którym nastąpiło odwrócenie. Po napotkaniu węzła zaznaczonego lub atomu algorytm wraca do poprzedniego węzła. Powrót do węzła następuje albo poprzez pole poprzednika, albo następnika. W tym pierwszym przypadku trzeba jeszcze zbadać ścieżkę wiodącą do następnika, a w algorytmie trzeba użyć znacznika do rozróżnienia, czy sprawdzone już zostały obie ścieżki - do poprzednika i do następnika, czy też tylko ta do poprzednika. Do tego celu służy dodatkowy bit, który nazwiemy tag. Jeśli sięgamy do poprzednika jakiegoś węzła, to wartością jego bitu tag pozostaje zero, więc po powrocie do tego węzła udamy się dalej ścieżką do następnika, zmieniając przy tym bit tag na jeden, a przy powrocie znowu na zero. Schematyczny zapis algorytmu wygląda następująco:

InvertLink (p1, p2 , p3)
tmp = p3 ;
p3 =pl;
p1 = p2 ;
p2 = tmp;

SWmarking (curr)
prev = NULL;
while (1)
zaznacz węzeł curr ;
if poprzednik węzła curr jest zaznaczony lub jest atomem
if poprzednik węzła curr jest nie zaznaczonym atomem
zaznacz poprzednik węzła curr ;
while następnik węzła curr jest zaznaczony lub jest atomem
if następnik węzła curr jest nie zaznaczonym atomem
zaznacz następnik węzła curr;
while prev nie jest równy NULL i tag(prev) == 1 /* powrót */
tag(prev) = 0;
InvertLink(curr, prev, następnik węzła prev) ;
if prev nie jest równy NULL
InvertLink(curr, prev, poprzednik węzła prev) ;
else koniec;
tag (curr) = 1;
503

InvertLink(prev, curr, następnik węzła curr) ;
else IiwertLink (prev, curr, poprzednik węzła curr) ;

Na rysunku 14.7 jest przedstawiony przykład. Każda część tego rysunku ilustruje zmiany na liście po dokonaniu opisanych operacji. Zwróćmy uwagę, że w węzłach będących atomami bit tag jest niepotrzebny. Każdy węzeł nie będący atomem składa się z czterech pól: bitu służącego do zaznaczania, węzła, bitu tag oraz dowiązań do poprzednika i następnika. Początkową wartością obu pól zawierających znaczniki jest zero. W rzeczywistości jest potrzebny jeszcze jeden bit, nie pokazany na rysunku, a mianowicie znacznik informujący, czy węzeł jest czy też nie jest atomem.
Poniżej zamieszczamy opis każdego przebiegu pętli while wraz z numerem rysunku przedstawiającego strukturę listy po tym przebiegu.

Przebieg 1: Wykonujemy InvertLink(prev, curr, poprzednik curr) (rys. 14.7b).

Przebieg 2: Znowu wykonujemy InvertLink (prev, curr, poprzednik curr) (rys. 14.7c).

Przebieg 3: Jeszcze raz wykonujemy InvertLink(prev, curr, poprzednik curr) (rys. 14.7d).

Przebieg 4: Zaznaczamy następnik węzła curr i wykonujemy Iiwert-Link(curr, prev, poprzednik prev) (rys. 14.7e), znowu wykonujemy InvertLink(curr, prev, poprzednik prev) (rys. 14.7f), zmieniamy bit tag węzła curr na 1 i wykonujemy Invert-Link(prev, curr, następnik curr} (rys. 14.7g).

Przebieg 5: Zaznaczamy następnik węzła curr, zmieniamy bit tag węzła prev na O i wykonujemy InvertLink(curr, prev, następnik prev) (rys. 14.7h), wykonujemy InvertLink(curr, prev, poprzednik prev) (rys. 14.7i), zmieniamy bit tag węzła curr na 1 i wykonujemy InvertLink(prev, curr, następnik curr) (rys. 14.7j).

Przebieg 6: Zmieniamy bit tag węzła prev na 1 i wykonujemy Invert-Link(curr, prev, następnik prev) (rys. 14.7k). Wartością prev staje się NULL i algorytm się kończy.

Zauważmy, że cykle na listach nie sprawiają algorytmowi żadnego kłopotu. Procedura SWmarking () jest wolniejsza niż MarkingWithStack (), ponieważ wymaga dwukrotnego odwiedzania każdej komórki, manipulowania wskaźnikami i dodatkowego bitu. Rezygnacja ze stosu nie wydaje się więc najlepszym rozwiązaniem. Inne sposoby opierają się na użyciu stosu ustalonego rozmiaru w połączeniu z pewną formą obsługi przepełnienia. Schorr i Waite proponują rozwiązanie polegające na przejściu do ich metody odwracania dowiązań, jeśli stos o ustalonym rozmiarze się przepełnia. Inne metody polegają na zawężeniu informacji umieszczanej na stosie. Na przykład procedura MarkingWithStack () niepotrzebnie odkłada na stos węzły, których pole następnika jest puste, a więc których przetwarzanie można przerwać po zakończeniu badania ścieżki do poprzednika.
504

Rys. 14.7. Przykład działania algorytmu Schorra i Waite'a do zaznaczania komórek pamięci będących w użyciu
405

Rys. 14.7. Przykład działania algorytmu Schorra i Waite'a do zaznaczania komórek pamięci będących w użyciu (cd.)

506

W metodzie, której autorem jest Wegbreit, nie jest potrzebny dodatkowy znacznik, a na stosie zamiast wskaźników umieszcza się po jednym bicie na każdy węzeł na badanej ścieżce, którego poprzednik ani następnik nie są atomami. Badana ścieżka to ta od aktualnie rozpatrywanego węzła do wskaźnika początkowego. Jednak podobnie jak w algorytmie Schorra-Waite'a, stosuje się tu odwracanie dowiązań. Ulepszeniem tej metody jest algorytm Fastmark [22]. Tak jak u Weigbreita, zachowuje on na stosie informację o węzłach zawierających dowiązania do innych, nie będących atomami. Na stosie znajdują się teraz jednak wskaźniki do węzłów, a nie bity, odwracanie dowiązań nie jest więc konieczne.

Fastmark(node)
if węzeł node nie jest atomem
zaznacz węzeł node ;
while (1)
if zarówno poprzednik, jak i następnik węzła node są zaznaczone lub są atoniami
if empty(S)
koniec;
else node =pop(S) ;
else if tylko następnik węzła node nie jest zaznaczony ani nie jest atomem zaznacz następnik węzła node ;
node = następnik węzła node ;
else if tylko poprzednik węzła node nie jest zaznaczony ani nie jest atomem zaznacz poprzednik węzła node ;
node = poprzednik węzła node ;
else if zarówno poprzednik, jak i następnik węzła node nie są zaznaczone ani nie są atomami
zaznacz poprzednik i następnik węzła node ;
push(następnik węzła node) ;
node = poprzednik węzła node ;

Zachęcamy czytelnika do wykonania tego algorytmu na liście z rysunku 14.7a. Nie rozwiązuje on jednak całkowicie dokuczliwego problemu przepełnienia stosu. Chociaż mówi się, że algorytm Fastmark potrzebuje w większości sytuacji około 30 miejsc na stosie, mogą trafić się złośliwe przypadki, wymagające stosu zdolnego pomieścić tysiące pozycji. Jeśli zatem algorytm ten ma być niezawodny, trzeba go zmodyfikować. Podstawową ideą tak otrzymanego algorytmu sprawdzającego stos jest usuwanie ze stosu węzłów już zaznaczonych lub takich, których ścieżki do poprzednika lub następnika zostały zbadane. Nawet jednak temu ulepszonemu algorytmowi zdarza się czasami wyczerpać całą pamięć, a wtedy "poddaje się i zgłasza błąd przepełnienia stosu" [22]. Metoda Schorra i Waite'a, symulująca stos za pomocą odwracania listy, jest zatem bardziej godna zaufania, chociaż wolniejsza.
507

Odzyskiwanie pamięci

Po zaznaczeniu wszystkich komórek będących aktualnie w użyciu procedura odzyskująca wolną pamięć zwracają do puli, przebiegając sekwencyjnie wszystkie komórki pamięci od największych adresów w dół i wstawiając wszystkie nie zaznaczone pozycje na listę wolnej pamięci. Po zakończeniu tego procesu wszystkie adresy na tej liście będą ułożone w porządku rosnącym. W trakcie przeglądania pamięci na wszystkich bitach służących do zaznaczania, komórek wpisuje się wartość O, więc na końcu znaczniki te będą wyzerowane zarówno w używanych, jak i w nie używanych komórkach. Oto zapis tego prostego algorytmu:

sweep()
dla każdej pozycji 1 w pamięci od ostatniej do pierwszej
if znacznik na pozycji l jest równy 1
wstaw pozycję l na początek listy wolnej pamięci ;
zmień znacznik na pozycji l na 0 ;

Algorytm sweep () przebiega całą pamięć. Jeśli dodamy do tego przebieg potrzebny na zaznaczanie i późniejszą obsługę listy wolnej pamięci, zawierającej komórki rzadko porozrzucane po pamięci, widzimy, że trzeba tu jeszcze co nieco ulepszyć.

Upakowywanie

Po zakończeniu procesu odzyskiwania wolne komórki będą rozproszone między tymi, których program właśnie używa. Trzeba więc dokonać upakowania. Jeśli wolne komórki leżą w spójnym obszarze, to lista wolnych miejsc w ogóle nie jest potrzebna. Również jeśli odśmiecanie dotyczy bloków różnych rozmiarów, bardzo wygodne jest ustawienie wszystkich wolnych komórek w jednym ciągu. Upakowywanie jest także potrzebne przy odśmiecaniu pamięci wirtualnej. Dzięki niemu realizacji żądań przydziału pamięci można dokonywać za pomocą minimalnej liczby odwołań. Inną sytuacją, w której opłaca się wykonywać Upakowywanie, jest jednoczesne korzystanie ze stosu programu i z kopca. W ten właśnie sposób jest na przykład zaimplementowany język C. Kopiec i stos znajdują się na przeciwległych krańcach pamięci, a rosnąc zbliżają się do siebie. Jeśli zajęte fragmenty kopca będą leżały z dala od stosu, na ten ostatni będzie więcej miejsca.
Prosty algorytm dwóch wskaźników służący do wykonania upakowania pamięci opiera się na metodzie podobnej do fazy rozrzucania w algorytmie sortowania szybkiego: dwa wskaźniki przebiegają pamięć, zaczynając od przeciwnych jej końców. Kiedy pierwszy wskaźnik trafia na zaznaczoną komórkę, a drugi na nie zaznaczoną, zawartość zaznaczonej komórki zostaje przeniesiona do nie zaznaczonej, a jej nowe położenie jest zapisywane pod starym adresem. Proces ten trwa dopóty, dopóki wskaźniki się nie miną. Następnie przegląda się zagęszczony w ten sposób obszar złożony z przeniesionych komórek w celu uaktualnienia wskaźników do poprzedników i następników. Jeśli wskaźniki skopiowanych komórek odwołują się do pozycji leżących poza obszarem zagęszczonym, sięga się pod stary adres, żeby odczytać nowy. Oto algorytm:



508

compact ( )
lo = adres początku pamięci;
hi = adres końca pamięci;
while (lowhile komórka *lo jest zaznaczona
lo++;
while komórka *hi nie jest zaznaczona
hi--;
zlikwiduj zaznaczenie komórki *hi ;
*lo = *hi;
poprzednik *hi-- = lo++; /* zostaw nowy adres */
lo = adres początku pamięci ;
while (lo < hi ) /* przejrzyj tylko obszar zagęszczony */
if *lo nie jest atomem i poprzednik *lo > hi
poprzednik *lo = następnik poprzednika *lo;
if *lo nie jest atomem i następnik *lo > hi
następnik *lo = następnik następnika *lo;
lo++;

Rysunek 14.8 ilustruje ten proces w sytuacji, kiedy przed komórką A są dwa wolne miejsca, na które można przenieść komórki B i C. Na rysunku 14.8a widać zawartość pamięci przed upakowaniem. Na rysunku 14.8b komórki B i C zostały przeniesione na wolne miejsca, a dowiązania do następnika na ich poprzednich pozycjach wskazują nowe adresy. Na rysunku 14.8c widać zagęszczoną część pamięci po sprawdzeniu dowiązań do poprzedników i do następników wszystkich komórek oraz uaktualnieniu ich, jeśli odnosiły się do pozycji spoza obszaru zagęszczonego.

Rys. 14.8. Przykład upakowywania pamięci
1509

Ten stosunkowo prosty algorytm nie jest zbyt efektywny: potrzebuje jednego przebiegu przez całą pamięć w celu zaznaczenia komórek, jednego przebiegu na przeniesienie zaznaczonych komórek do spójnego obszaru i jednego przebiegu przez ten obszar w celu uaktualnienia wskaźników - w sumie dwa i pół przebiegu przez pamięć. Jednym ze sposobów zmniejszenia liczby przebiegów jest połączenie faz zaznaczania i czyszczenia pamięci, co stanowi podstawę nowych kategorii metod.

14.3.2. Metody kopiowania

Algorytmy oparte na kopiowaniu są niemal dosłownie "czystsze" niż omówione dotychczas metody, bo nie mają w ogóle do czynienia ze "śmieciami" w pamięci. Dotyczą one jedynie komórek dostępnych ze wskaźników początkowych i łączą je w całość; komórki nie przetworzone są wolne. Przykładem metody kopiowania jest algorytm "przerwij-i-skopiuj" (ang. stop-and-copy), dzielący pamięć na dwa obszary, z których tylko jeden - aktywny -jest używany do przydzielania pamięci [21]. Kiedy wskaźnik początku wolnego miejsca dotrze do końca tego obszaru, wszystkie jego używane komórki są kopiowane do drugiego obszaru, który staje się aktywny, a program wznawia działanie (zob. rys. 14.9).
Listy można kopiować metodą przechodzenia wszerz [18]. Gdyby listy były zwykłymi drzewami binarnymi bez innych dowiązań, algorytm byłby taki sam jak przechodzenie drzewa wszerz, omawiane w podrozdziale 8.4.1. Listy mogą jednak zawierać cykle, a elementy na jednej liście mogą zawierać wskaźniki do drugiej. W tym ostatnim przypadku algorytm ten tworzy wiele kopii tej samej komórki, a w poprzednim - wpada w nieskończoną pętlę. Problem ten można łatwo rozwiązać tak, jak w procedurze compact(), zachowując nowy adres w kopiowanej komórce, co pozwala na odwołanie do komórki po jej skopiowaniu. W algorytmie tym nie jest potrzebna faza zaznaczania ani użycie stosu. Przechodzenie wszerz pozwala również na połączenie kopiowania list i uaktualniania wskaźników. Algorytm ma do czynienia ze "śmieciami" jedynie pośrednio, nie sięga bowiem wcale do nie używanych komórek. Im bardziej zaśmiecona jest pamięć, tym szybsze jest działanie algorytmu.
Zwróćmy uwagę, że koszt odśmiecania tą metodą maleje wraz ze wzrostem rozmiaru pamięci (obydwu obszarów). W rzeczywistości nie tylko zmniejsza się liczba zamian obszarów rolami, ale również, co jest bardziej zaskakujące, skraca się czas przypadający na jedną zamianę. Na przykład program uruchomiony z 4 MB pamięci wymaga 34 zamian, z których każda zajmuje średnio 6,8 s, a ten sam program dysponujący 16 MB pamięci potrzebuje tylko trzech zamian, zajmujących po 2,7 s - różnica jest więc bardzo znacząca. Dodajmy, że jeśli pamięci jest naprawdę dużo (w tym przykładzie 64 MB), to odśmiecanie w ogóle nie jest potrzebne [13]. Oznacza to, że przeniesienie odpowiedzialności za zwalnianie pamięci z programisty (jak w C lub Pascalu) na procedurę odśmiecającą nie musi powodować spowolnienia programów. Jest to prawdą przy założeniu, że wolnej pamięci jest dużo.


510

Rys. 14.9. Sytuacja w pamięci przed skopiowaniem zawartości używanych komórek z obszaru do obszaru (a) i sytuacja zaraz po skopiowaniu (b). Wszystkie używane komórki zajmują spójny fragment pamięci

14.3.3. Odśmiecanie krokowe

Procedury odśmiecające w językach przetwarzających listy są wywoływane automatycznie, kiedy zasoby wolnej pamięci zaczynają się wyczerpywać. Jeśli przydarza się to w trakcie działania programu, zostaje ono wstrzymane, dopóki nie zostanie zakonczone odśmiecanie. Może ono zająć kilka sekund, co w systemach z podziałem czasu może wzrosnąć do minut. Sytuacja taka jest nie do zaakceptowania w systemach czasu rzeczywistego, w których kluczowe znaczenie ma szybkość reakcji programu. Dlatego często warto stosować procedury odśmiecania krokowego, których działanie przeplata się z wykonywaniem programu. Działanie programu zostaje wstrzymane tylko na krótką chwilę, co pozwala procedurze odśmiecającej na oczyszczenie jedynie części pamięci i pozostawienie reszty na później. Wiąże się z tym jednak pewien problem. Po częściowym przetworzeniu jakiejś listy przez procedurę czyszczącą program może tę listę zmienić; mówiąc inaczej: doprowadzić do mutacji listy. Z tego powodu program działający w połączeniu z procedurą krokowego odśmiecania nazywamy "mutatorem". Zmiany takie trzeba wziąć pod uwagę przy wznowieniu odśmiecania i ewentualnie ponownie przetworzyć niektóre komórki albo i całe listy. To dodatkowe obciążenie wskazuje, że odśmiecanie krokowe wymaga większego wysiłku niż zwykłe. W istocie, udowodniono, że w porównaniu ze zwykłymi procedurami odśmiecania procedury odśmiecania krokowego wymagają dwukrotnie większej mocy obliczeniowej [26].

511

Metody z kopiowaniem komórek

Algorytm krokowy oparty na metodzie "przerwij-i-skopiuj" zaprojektował Henry Baker [15]. Podobnie jak we wspomnianej metodzie, w algorytmie Bakera również używa się dwóch obszarów, zwanych źródłowym i docelowym, które są jednocześnie aktywne, aby zapewnić właściwą współpracę między mutatorem i procedurą odśmiecąjącą. Podstawowy pomysł polega na przydzielaniu pamięci w obszarze docelowym, zaczynając od jego końca i kopiowaniu przy każdym żądaniu tej samej liczby k komórek z obszaru źródłowego do docelowego. Dzięki temu procedura czyszcząca może realizować swoje zadanie, nie zakłócając zbytnio pracy mutatora. Po skopiowaniu wszystkich osiągalnych komórek do obszaru docelowego role obydwu obszarów się odwracają. Procedura odśmiecąjącą przechowuje dwa wskaźniki. Pierwszy z nich, zwany scan, wskazuje komórkę, której poprzednik i następnik wraz ze swoimi listami powinny być skopiowane do obszaru docelowego, jeśli nadal są w obszarze źródłowym. Ponieważ rozmiar tych list może być większy niż k, czasami nie daje się przetworzyć ich za jednym razem. Z obszaru źródłowego jest kopiowanych co najwyżej k komórek, do których docieramy metodą przechodzenia wszerz, a kopie są umieszczane na końcu kolejki. Dostęp do kolejki zapewnia drugi wskaźnik, bottom, zawierający adres początku wolnej pamięci w obszarze docelowym. Procedura odśmiecąjącą może przetworzyć następnik bieżącej komórki w tym samym kroku odśmiecania, ale może także zaczekać do następnego. Na rysunku 14.10 jest przedstawiony przykład. Jeśli nadchodzi żądanie przydzielenia komórki, której pole poprzednika wskazuje na P, a następnikiem ma być Q (jak w Lispowej konstrukcji cons(P, Q)), gdzie zarówno P, jak i Q leżą w obszarze docelowym, to komórkę przydziela się w górnej części obszaru docelowego i nadaje się odpowiednie wartości początkowe obydwu jej polom wskaźnikowym. Przy założeniu, że k = 2 z listy poprzednika komórki wskazywanej przez scan zostaną skopiowane dwie komórki, a poprzednik będzie przetwarzany po nadejściu kolejnego żądania. Podobnie jak w metodzie "przerwij-i-skopiuj", w algorytmie Bakera przechowuje się na pierwotnej pozycji w obszarze źródłowym nowy adres jej kopii w obszarze docelowym na wypadek, gdyby później przydzielone komórki odwoływały się do starego adresu.




512

Szczególną ostrożność trzeba zachować, kiedy wskaźnik do poprzednika i/lub następnika przydzielanej właśnie komórki dotyczy elementu obszaru źródłowego, już skopiowanego albo nie. Ponieważ komórki na końcu obszaru docelowego nie są przetwarzane komórek z obszaru źródłowego miałoby opłakane skutki po zamianie obszaru źródłowego na docelowy, gdyż te ostatnie komórki są teraz traktowane jako wolne i wypełnia się je nową zawartością. Mutator mógłby w jednym miejscu użyć wskaźnika do oryginału, a w innym - do kopii, co prowadziłoby do logicznych niespójności.

Rys. 14.10 Sytuacja w pamięci przed (a) i po (b) przydzieleniu komórki, której wskaźniki do poprzednika i następnika dotyczą komórek P i Q w obszarze docelowym, zgodnie z algorytmem Bakera

513

Przed mutatorem stawia się więc barierę odczytu, uniemożliwiającą korzystanie z odwołań do komórek obszaru źródłowego. W wypadku odwołania do obszaru źródłowego trzeba sprawdzić, czy komórka ta zawiera nowy adres - zawarty w jej polu następnika adres pozycji w obszarze docelowym. Jeśli odpowiedź jest twierdząca, to tego właśnie adresu używa się przy przydzielaniu nowej komórki. W przeciwnym razie komórkę, do której następuje odwołanie, trzeba skopiować, zanim nastąpi przydzielenie pamięci. Jeśli na przykład poprzednikiem przydzielanej komórki ma być P - skopiowana już wcześniej komórka w obszarze źródłowym, jak na rysunku 14.11a, to nowy adres P zostaje zapisany w polu przeznaczonym na wskaźnik do poprzednika (zob. rys. 14.11b). Jeśli wskaźnik do następnika w nowej komórce ma wskazywać na Q - dotychczas nie przetwarzaną komórkę z obszaru źródłowego, to komórka Q jest kopiowana do obszaru docelowego (wraz z jednym ze swych potomków, ponieważ k = 2), a dopiero potem wskaźnikowi do następnika nowej komórki nadaje się wartość adresu kopii Q.
W algorytmie Bakera jest możliwych wiele rozmaitych modyfikacji i ulepszeń. Aby na przykład uniknąć ciągłego sprawdzania warunków podczas przydzielania nowych komórek, do każdej komórki dodaje się pole służące do adresowania pośredniego. Jeśli komórka znajduje się w obszarze docelowym, wskaźnik w tym polu wskazuje na nią samą, w przeciwnym zaś razie - na jej kopię w obszarze docelowym [17]. Wprawdzie unika się wtedy sprawdzania, ale w zamian trzeba dbać o odpowiednie wartości wskaźników w każdej komórce. Innym sposobem rozwiązania tego problemu jest wykorzystanie istniejących udogodnień sprzętowych. Przykładowo, za pomocą blokady odczytu można uniemożliwić mutatorowi dostęp do komórek nie przetworzonych przez procedurę odśmiecającą: strony pamięci z kopca zawierające nie przetworzone komórki są zabezpieczone przed odczytem [20]. Próba sięgnięcia przez mutator do takiej strony jest przechwytywana i powoduje zgłoszenie przerwania, którego obsługa polega na przetworzeniu tej strony przez program odśmiecający, dzięki czemu mutator może wznowić działanie. Metoda ta jednak może zniwelować krokowy charakter pracy programu odśmiecającego, bo po zamianie obszarów rolami przerwania zgłaszane są często, a obsługa każdego z nich wymaga przetworzenia całej strony pamięci z kopca. Mogą być potrzebne pewne dodatkowe warunki, jak możliwość nieprzeglądania całej strony w ramach obsługi przerwania. Z drugiej strony, jeśli do kopca nie sięga się zbyt często, nie stanowi to większego problemu.
Interesującą modyfikacją algorytmu Bakera jest metoda oparta na obserwacji, że większość przydzielanych komórek jest potrzebna tylko przez bardzo krótką chwilę; tylko niewiele spośród nich jest używanych przez dłuższy czas. W metodzie tej - zwanej odśmiecaniem pokoleniowym - dzieli się wszystkie przydzielone komórki na co najmniej dwa pokolenia i skupia uwagę na pokoleniu najmłodszym, wytwarzającym najwięcej "śmieci". Komórek tych nie trzeba kopiować, co oszczędza procedurze odśmiecającej nieco pracy. Co więcej, ciągłe sprawdzanie i kopiowanie długowiecznych komórek jest niepotrzebną stratą czasu, przeglądanie tych komórek w poszukiwaniu śmieci odbywa się więc rzadko.

514

Rys. 14.11. Zmiany dokonywane za pomocą algorytmu Bakera, jeśli adresy P i Q dotyczą komórek w obszarze źródłowym. P jest komórką już skopiowaną, Q - nie

W klasycznej wersji programu odśmiecania pokoleniowego przestrzeń adresowa jest podzielona na pewną liczbę regionów,
r#1, ..., r#n, a nie tylko na obszar źródłowy i docelowy; każdy region zawiera komórki z tego samego pokolenia [24]. Większość wskaźników wskazuje na komórki z wcześniejszych pokoleń. Niektóre z nich mogą jednak być skierowane "w przyszłość" (np. jeśli użyto Lispowej konstrukcji rplacd).


515

W metodzie tej takich odwołań "w przód" dokonuje się w dwóch krokach, poprzez tablicę adresów pośrednich związaną z każdym regionem. Wskaźnik z regionu r{ nie wskazuje na komórkę c w regionie r#(i+j) ale na komórkę c' w tablicy odpowiadającej regionowi r#(i+j), a c' zawiera wskaźnik do c. Jeśli region r#i, zostaje przepełniony, to wszystkie jego osiągalne komórki kopiuje się do innego regionu r'#i, a następnie odwiedza się wszystkie regiony zawierające pokolenia komórek młodsze niż
r#i w celu uaktualnienia wskaźników odwołujących się do przeniesionych właśnie do nowego regionu komórek. Regionów zawierających pokolenia starsze niż r#i, odwiedzać nie trzeba. W tablicy adresów pośrednich regionu r#i zmieni się zapewne tylko kilka odnośników (zob. rys. 14.12). Problem uaktualniania tablic adresów pośrednich można rozwiązać, zapisując w takiej tablicy wraz z każdym wskaźnikiem jednoznaczny identyfikator regionu, do którego dany wskaźnik się odwołuje. Identyfikator uaktualnia się jednocześnie ze wskaźnikiem. Niektóre wskaźniki mogą stać się niepotrzebne, jak wskaźnik w tablicy dla regionu r#(i+1) na rysunku 14.12b, i można je będzie usunąć, kiedy będziemy likwidować sam region.

Rys. 14.12. Trzy regiony przed (a) i po (b) skopiowaniu osiągalnych komórek z regionu r/ do r', w ramach metody odśmiecania pokoleniowego Liebermana-Hewitta

516

Metody bez kopiowania komórek

W metodach krokowych opartych na kopiowaniu problem tkwi nie tyle w zawartości oryginalnej komórki i jej kopii, co w ich położeniach, czyli adresach w pamięci, które z konieczności są różne. Mutator nie może traktować tych adresów jednakowo, bo skończyłoby się to zawieszeniem programu. Z tego powodu niezbędne są pewne mechanizmy zapewniające logiczną spójność adresowania - temu właśnie celowi służy bariera odczytu. Możemy jednak całkowicie uniknąć kopiowania; w końcu w pierwszej omawianej metodzie odśmiecania, "zaznacz-i-usuń", nie tworzyło się żadnych kopii. Z uwagi na pracę w czasochłonnych i nieprzerywalnych przebiegach była ona wprawdzie zbyt kosztowna, a w systemach czasu rzeczywistego - po prostu nie do zaakceptowania, metoda ta na tyle jednak pociąga swoją prostotą, że można pokusić się o próbę jej adaptacji do reżimu pracy w czasie rzeczywistym. Jak się okazuje, próbę taką, i to z satysfakcjonującymi wynikami, podjął Taiichi Yuasa.
Algorytm Yuasy także składa się z dwóch faz: jednej na zaznaczanie osiągalnych (będących w użyciu) komórek i drugiej na oczyszczanie pamięci przez wstawienie na listę wolnej pamięci avail_list wszystkich wolnych (nie zaznaczonych) komórek. Faza zaznaczania, jest podobna do tej z metody "zaznacz-i-usuń", z tą różnicą, że przebiega krokowo: za każdym wywołaniem procedura zaznaczająca przetwarza tylko k#1, komórek, gdzie k#1 jest pewną niewielką stałą. Po zaznaczeniu k#1, komórek wznawia działanie mutator. Stała k#2, używana w fazie oczyszczania, określa, ile komórek zostanie przetworzonych przed przekazaniem sterowania do mutatora. Program odśmiecający pamięta, czy jest w trakcie zaznaczania czy oczyszczania. Procedura zaznaczająca albo czyszcząca jest zawsze wywoływana po zgłoszeniu żądania przydziału komórki pamięci przez procedurę tworzącą nowy wskaźnik początkowy i nadającą wartości początkowe jego polom poprzednika i następnika, jak w poniższym pseudokodzie:

CreateRootPtr (p, q, r) /* operacja cons w Lispie /*
if program odśmiecający jest w fazie zaznaczania
zaznacz co najwyżej k} komórek;
else if program odśmiecający jest w fazie oczyszczania
oczyść co najwyżej k2 komórek;
else if na liście avail_list jest mało wolnych komórek
wstaw wszystkie wskaźniki początkowe na stos
S programu odśmiecającego ;
p = pierwsza komórka na liście avail_list;
poprzednik p = q;
517

następnik p = r;
zaznacz p, jeśli jest w nie oczyszczonej części kopca;

Pamiętajmy, że mutator może pozmieniać niektóre grafy dostępne ze wskaźników początkowych, co jest szczególnie istotne, jeśli zdarza się w trakcie fazy zaznaczania, może bowiem spowodować, że pewne komórki pozostaną nie zaznaczone, pomimo że są osiągalne. Na rysunku 14.13 jest przedstawiony przykład. Po wstawieniu wszystkich wskaźników początkowych na stos S (rys. 14.13a) i przetworzeniu wskaźników r#3 oraz r#2, a w trakcie przetwarzania wskaźnika r#1 (rys. 14.13b), mutator wykonuje dwa przypisania: poprzednikiem r#3 staje się następnik r#1, a następnikiem r#1, zostaje r#2 (rys. 14.13c). Jeśli teraz wznowimy proces zaznaczania, nie ma on szans dotarcia do poprzednika r#3, czyli c#5, bo traktuje cały graf r#3 jako już przetworzony. Powoduje to dołączenie poprzednika r#3 do listy wolnej pamięci avail_list w fazie oczyszczania. Aby tego uniknąć, procedura zmieniająca wartość poprzednika lub następnika dowolnej komórki wstawia starą wartość uaktualnianego pola na stos programu odśmiecającego.



Rys. 14.13. Problem pojawiający się, jeśli w nie kopiującym krokowym algorytmie odśmiecającym Yuasy nie użyjemy stosu do zapamiętania komórek, które mogły zostać opuszczone w fazie zaznaczania

518

Oto przykład takiej procedury:

UpdateTail (p, q) /* operacja rplacd w Lispie /*
if program odśmiecający jest w fazie zaznaczania
zaznacz następnik p ; push (następnik p, S) ;
następnik p = q;

Rys. 14.14. Zmiany zachodzące w pamięci podczas fazy oczyszczania w metodzie Yuasy

519

W fazie zaznaczania, ze stosu S co najwyżej k#1, razy zdejmuje się element, a dla każdego zdjętego ze stosu wskaźnika p zaznacza się jego poprzednik i następnik.
Faza oczyszczania w pojedynczych krokach przebiega całą pamięć, wszystkie nie zaznaczone komórki wstawia na listę wolnej pamięci, a wszystkie zaznaczone zmienia na nie zaznaczone. Jeżeli mamy być konsekwentni, to świeżo przydzieloną komórkę pozostawiamy nie zaznaczoną, jeśli odpowiedni fragment pamięci został już oczyszczony. Gdybyśmy postąpili inaczej, to następny cykl zaznaczania mógłby spowodować bałagan. Na rysunku 14.14 jest przedstawiony przykład. Wskaźnik Sweeper, oznaczający zasięg strefy oczyszczonej, osiągnął już komórkę c#3, a mutator żąda teraz przydzielenia nowej komórki, wywołując CreateRootPtr(r#2, c#5, c#3), wobec czego pierwsza komórka listy wolnej pamięci jest z niej usuwana i staje się nowym wskaźnikiem początkowym (rys. 14.14b). Przydzielonej właśnie komórki nie zaznaczamy, ponieważ jej adres jest wcześniejszy niż wskazywany przez Sweeper.
Jeśli zwalniamy jakąś komórkę w obszarze już oczyszczonym, to staje się ona "śmieciem", ale do puli wolnej pamięci wraca dopiero po wznowieniu oczyszczania od początku pamięci. Na przykład po przypisaniu do wskaźnika r, następnika r, komórka c2 staje się nieosiągalna, ale na razie nie można odzyskać zajmowanej przez nią pamięci i dołączyć jej do listy wolnych pozycji (rys. 14.14c). To samo dzieje się z komórkami o adresach wyższych niż bieżąca wartość wskaźnika Sweeper, jak w wypadku komórki c6 po zamianie wartości następnika r#1 na następnik r#2 (rys. 14.14d). Te tak zwane "pływające śmiecie" zostaną usunięte w następnym przebiegu.

14.4. Uwagi końcowe

Oceniając efektywność algorytmów zarządzania pamięcią, a zwłaszcza algorytmów odśmiecania, musimy być ostrożni, żeby nie narazić się na zarzut Paula Wilsona wobec podręczników, w których kładzie się nadmierny nacisk na asymptotyczną złożoność algorytmów, pomijając kluczową sprawę "stałych współczynników, związanych z poszczególnymi kosztami" [28]. Jest to szczególnie widoczne w przypadku algorytmów nie działających krokowo, których koszt jest zazwyczaj proporcjonalny albo do rozmiaru n kopca ("zaznacz-i-usuń"), albo do liczby osiągalnych komórek m ("przerwij-i-skopiuj"). Sugeruje to przewagę tych ostatnich metod, zwłaszcza kiedy liczba osiągalnych komórek jest niewielka w stosunku do rozmiaru kopca. Jeśli jednak weźmiemy pod uwagę to, że koszt oczyszczania pamięci jest mały w porównaniu z kosztem kopiowania, różnica efektywności nie jest wcale taka oczywista. W praktyce, jak wykazano, wydajność metod "zaznacz-i-usuń" oraz "przerwij-i-skopiuj" jest bardzo zbliżona [30].
Przykład ten wskazuje, że na efektywność algorytmów zarządzania pamięcią wpływ mają głównie dwa elementy: zachowanie programu i właściwości sprzętu, na którym działa. Po wielu operacjach przydzielania programowi pamięci wartość m staje się bliska n\ przeglądanie jedynie osiągalnych komórek to prawie to samo co przeglądanie całego kopca (czy też jego regionu). Jest to szczególnie istotne w przy-

520

padku programów odśmiecania pokoleniowego, których efektywność opiera się na założeniu, że większość przydzielanych komórek jest używana przez bardzo krótki czas. Jeśli natomiast oczyszczanie nie jest dużo szybsze niż kopiowanie, przewaga jest po stronie metod z kopiowaniem komórek.
Złożoność asymptotyczna jest miarą zbyt nieprecyzyjną, a w publikacjach dotyczących zarządzania pamięcią jej wyznaczaniu nie poświęca się wiele uwagi. Znacznie ważniejsze są "stałe współczynniki, związane z poszczególnymi kosztami". Wprowadza się również subtelniejsze miary efektywności, nie wszystkie jednak dają się łatwo wyliczać, na przykład ilość pracy wkładana w odzyskanie jednej komórki, wskaźnik szybkości tworzenia obiektów, średni czas istnienia obiektu albo gęstość występowania w pamięci osiągalnych obiektów [24].
Algorytmy zarządzania pamięcią są zwykle blisko związane ze sprzętem, od którego może zależeć wybór konkretnej metody. Odśmiecanie można na przykład znacznie, przyspieszyć, używając sprzętu wyspecjalizowanego do tego celu. W maszynach opartych na Lispie bariera odczytu jest zaimplementowana sprzętowo i w formie mikrokodu, co faworyzuje bazujące na tej barierze programy odśmiecania krokowego. Bez wsparcia sprzętowego praca takich odśmiecaczy zajmuje około 50% czasu działania programu. W takiej sytuacji lepszy wybór stanowią algorytmy bez kopiowania komórek. Odrębny aspekt stanowią ograniczenia dotyczące reżimu pracy w czasie rzeczywistym. W systemach czasu rzeczywistego, gdzie szybkość reakcji komputera jest sprawą gardłową, dochodzi dodatkowy narzut związany z programem odśmieca-jącym. Może to być słabiej zauważalne niż w przypadku programów odśmiecających nie działających krokowo, bo nie ma żadnych widocznych okresów oczekiwania programu na zakończenia działania odśmiecacza. Dobór metod krokowych powinien jednak odpowiadać ograniczeniom czasu rzeczywistego.

14.5. Przykład: odśmiecanie "w miejscu"

Efektywność kopiujących algorytmów odśmiecania polega na tym, że nie wymagają one przetwarzania nie wykorzystywanych komórek. Nie przetworzone komórki są pod koniec fazy traktowane jako śmiecie. Wadą tych algorytmów jest jednak konieczność kopiowania osiągalnych komórek z jednego obszaru do drugiego. Program odśmieca-jący działający ,,w miejscu" próbuje zachować zalety algorytmów kopiujących, nie produkując kopii osiągalnych komórek [16].
W algorytmie są stale przechowane dwie listy dwukierunkowe, FreeList i NonFreeList. Pierwsza z nich początkowo zawiera wszystkie komórki kopca heap, a kiedy napływa żądanie skonstruowania listy lub nowego atomu, zabierana jest z niej potrzebna do tego celu komórka. Kiedy lista FreeList staje się pusta, jest wywoływana funkcja collect(). Funkcja ta najpierw przenosi wszystkie wskaźniki początkowe z NonFreeList na pośrednią listę ToBeMarkedList. Następnie przenosi ona po jednej komórce na raz zawartość ToBeMarkedList na inną pomocniczą listę, MarkedList, zapisując przy tym w przeznaczonym na zaznaczanie

521

polu mark każdej komórki wartość marked. Oprócz tego dla każdej komórki nie będącej atomem funkcja collect () dołącza do ToBeMarkedList wskaźniki do jej nie zaznaczonych poprzednika i następnika, czyli head i taił. W naszym przykładzie dołącza się je na początek ToBeMarkedList, struktury listowe będą więc przechodzone "w głąb". Żeby przechodzić je "wszerz" (jak w algorytmie Cheneya), trzeba by dołączać je na koniec ToBeMarkedList, co wymaga użycia drugiego wskaźnika - do końca listy. Zwróćmy uwagę, że chociaż komórka jest już przeniesiona na listę komórek zaznaczonych MarkedList, trzeba ją jeszcze zaznaczyć, żeby zabezpieczyć się przed wejściem w nieskończoną pętlę w strukturach cyklicznych i niepotrzebną pracą w połączonych między sobą strukturach acyklicznych.
Po opróżnieniu ToBeMarkedList wszystkie osiągalne komórki kopca heap są już przetworzone i zadanie funkcji collect () jest niemal zakończone. Przed powrotem z jej wywołania wszystkie komórki pozostające na liście NonFreeList stają się elementami FreeList, a wszystkie zaznaczone komórki umieszcza się na NonFreeList, zmieniając zawartość ich pola mark na !marked. Teraz już program () może wznowić działanie.
Trzeba mieć jasność, że program czyszczący pamięć jest częścią środowiska programu i działa w tle, niemal niezauważalnie dla użytkownika. Aby unaocznić działanie programu odśmiecającego, w naszym przykładzie są symulowane niektóre elementy otoczenia programu, mianowicie kopiec i tablica symboli.
Kopiec jest zrealizowany jako tablica struktur o dwóch polach znacznikowych (atom/nie-atom i zaznaczony/nie-zaznaczony) i dwóch wskaźnikowych, które w rzeczywistości zawierają liczby całkowite oznaczające pozycje w kopcu poprzedniej i następnej komórki (jeśli istnieją). Stosownie do tej implementacji, obydwie stałe listy, FreeList i NonFreeList, oraz obydwie tymczasowe, ToBeMarkedList i MarkedList, to po prostu zmienne całkowite oznaczające położenie w tablicy heap pierwszej komórki na danej liście (jeśli istnieje).
Tablica symboli jest zaimplementowana jako tablica roots wskaźników początkowych. Nie używa się jawnych nazw zmiennych, a jedynie indeksów komórek tablicy heap. Jeśli na przykład zawartością tablicy roots jest jest [324 0], to program () używa aktualnie tylko czterech zmiennych, od roots[0] do roots[3], a zmienne te wskazują odpowiednio na komórki 3, 2, 4 i 0 w kopcu heap. Liczby 0-3 można traktować jako dolne indeksy bardziej oczywistych nazw jak var(), var,, var2 i wzr3.
Procedura program () to tylko prosta symulacja programu użytkownika, ograniczająca się do zgłaszania żądań przydziału pamięci z kopca i jej zwalniania. Żądania te generowane są losowo i klasyfikowane ze względu na ich rodzaj: 30% dotyczy przydziału pamięci na atomy, 60% - na listy, 5% to zmiany poprzednika, a pozostałe 5% - zmiany następnika. Można dobrać inne proporcje, a rozkład przypisań dopasować do liczby przypisań już wykonanych, wprowadzając odpowiednie zmiany w procedurze program(). Rozmiar kopca heap i tablicy wskaźników również łatwo zmodyfikować.
Procedura program () generuje liczbę losową rn z przedziału od 0 do 99, określającą operację do wykonania. Następnie losowo wybiera się zmienne z tablicy roots. Jeśli na przykład wartością rn jest 11, roots to [3 2 4 0], a p jest równe 2, to komórka o numerze roots[p]=4 z kopca heap, wskazywana przez zmienną 2, zostaje atomem: w jej polu value zostaje umieszczona wartość val, a znacznik kind przyjmujer wartość atom. Jeśli p jest równe 4, oznacza to, że na pozycji 4 w tablicy roots trzeba utworzyć nową zmienną (zmienną 4 lub, jak kto woli, var4), a na pozycji roots[4] zapisujemy pierwszą wartość z FreeList.
Żeby można było zobaczyć, że nasz program cokolwiek robi, dołączyliśmy prostą funkcję PrintList (), wypisującą elementy danej listy.

Na rysunku 14.15 jest przedstawiony kod programu odśmiecającego, działającego w miejscu.

strony 522 do 525

#include
# includę

#define MaxHeap 10
#define MaxRoot 100
#def ine empty -1
#def ine atom 1u
#def ine marked 1u
#def ine OK 1
#def ine head 0
#define taił 1
ttdefine Head (p) heap[p]. info. links[head]
#define Taił (p) heap[p]. info. links[tail]
#define Value (p) heap[p]. info. value

struct CellRec {
unsigned int kind : 1 ;
unsigned int mark : 1;
int prev, next;
union {
int value; /* wartość w przypadku atomu, */
int links[2]; /* poprzednik i następnik w przeciwnym razie */ } info;
} heap[MaxHeap] ;

int roots[MaxRoot], RootCnt = 0;
int FreeList = empty, NonFreeList = empty;

PrintList(int list, char *name)
{ int i;

printf ( "%s " ,name) ;
for (i = list; i != empty; i = heap[i] .next)
printf ("(%d%d%d) ", i, Head(i) , Taił (i));
putchar('\n'); }

void
datach (int celi, int *list)
{
if (heap[cell].next != empty)
heap[heap[cell].next].prev = heap[cell].prev;
if (heapfcell] .prev != empty)
heap[heap[cell] .prev].next = heap[cell] .next;
if (celi == *list) /* początek listy */
*list = heap[cell].next;
}
void
insert (int celi, int *list)
{

heap[cell] .prev = empty;
heap[cell] .next = *list;
if (*list != empty)
heap[*list] .prev = celi;
*list = cell;
}

void
transfer(int celi, int *list1, int *list2)
{
detach(cell, list1);
insert(cell, Iist2);
}

void
collect()
{ register int p, hołd;
int ToBeMarkedList = empty, MarkedList = empty;

for (p = 0; p < RootCnt; p++)
transfer(roots[p], ŁNonFreeList, ŁToBeMarkedList);
for (p =ToBeMarkedList; p != empty; p = hołd) {
hołd = heap[p] .next; /* konieczne, ponieważ procedura transfer () */
transfer(p, &ToBeMarkedList, ŁMarkedList); /* zmienia pole next */
heapfp] .mark = marked;
if (heapfp] .kind != atom && heap[p] .mark != marked) {
transfer (Head(p) , &NonFreeList, ScToBeMarkedList) ;
transfer(Taił(p), &NonFreeList, &ToBeMarkedList);
}
}
for (p = MarkedList; p != empty; p = heap[p].next)
heap[p].mark = ! marked;
FreeList =NonFreeList;
NonFreeList = MarkedList;

AllocateAux(int p)
{
if (p==MaxRoot) {
printf ( "Brak miejsca na nowe zmienne\n" ) ;
return !OK;
}
if (FreeList == empty)
collect() ;
if (FreeList == empty) {
printf ( "Brak miejsca w kopcu na nowe komórki\n" ) ;
return !OK;
}

if (p ==RootCnt)
roots [RootCnt++] =p;
roots[p] = FreeList;
transfer(FreeList, &FreeList, &NonFreeList);
return OK;
}

void
AllocateAtom (int p, int val) /* odpowiednik lispowego set f */
{
if (AllocateAux(p) == OK) {
heap[roots[p]] .kind = atom;
Value (rootsfp]) = val ;
}
}

void
AllocateList (int p, int q, int r) /* lispowe cons */
{
if (AllocateAux(p) == OK) {
heap[roots[p]]. kind = ! atom;
Head(roots[p]) = roots[q];
Taił (roots[p]) = roots[r];
}
}

void
UpdateHead(int p, int q) /* lispowe rplaca */
{
Head(roots[p]) =roots[q];
}

void
UpdateTail (int p, int q) /* lispowe rplacd */
{
Taił (roots[p]) =roots[q];
}

void
program()
{ static int val =123;
intrn = rand() %100;
int p = rand() % (RootCnt+1) ; /* być może nowy wskaźnik początkowy */
int q = rand() % RootCnt;
int r = rand () % RootCnt ;
if (rn < 20)
AllocateAtom(p,val++);
else if (rn < 90)
AllocateList(p,q,r);
else if (rn < 95 && heap[roots[q]]. kind != atom)
UpdateHead(q, r) ;
else if (heap[roots[q]]. kind !=atom)
UpdateTail(q, r);
}

main() { int i;
for (i =MaxHeap-1; i >= 0; i--) {
insert(i, &FreeList);
heap[i] .mark = Imarked;
}
AllocateAtom(0,13); /* na początek: */
AllocateAtom(l, 14) ; /* tworzymy dwa atomy i jeden */
AllocateList (2,0,1); /* węzeł nie będący atomem */
for (i = 0; i < 10; i++)
program();
}

Rys. 14.15. Implementacja programu odśmiecającego, działającego w miejscu
526

14.6. Ćwiczenia
1. Co się dzieje z metodą "pierwszy-pasujący", jeśli zastosować ją do listy uporządkowanej według rozmiarów bloków?
2. W jaki sposób trudność związana ze sklejaniem bloków w metodach sekwencyjnego dopasowywania zależy od kolejności bloków na liście? Jak można rozwiązywać ewentualne problemy wynikające z takiej kolejności?
3. Metoda optymalnego dopasowania rozstrzyga, który blok przydzielić, po zbadaniu próbki bloków w celu znalezienia najbliższego rozmiarem żądanemu oraz pierwszego bloku przekraczającego żądany rozmiar [3]. Od czego zależy efektywność tej metody? Jak wypada ten algorytm w porównaniu z innymi metodami sekwencyjnego dopasowywania?
4. W jakich przypadkach lista rozmiarów w metodzie adaptacyjnego dokładnego dopasowywania może być pusta (oprócz sytuacji początkowej)? Jaki jest jej maksymalny rozmiar i kiedy może być osiągnięty?
5. Dlaczego w systemach par używa się dwukierunkowych, a nie jednokierunkowych list bloków?
6. Podaj algorytm zwracania bloków do puli pamięci w systemie par Fibonacciego.
7. Zastosuj procedurę MarkingWithStack() do lewostronnie i prawostronnie zdegenerowanych struktur listowych z rysunku 14.16. Ile wywołań pop() i push () wykonuje się w każdym przypadku? Czy wszystkie są potrzebne? Jak zoptymalizowałbyś kod w celu uniknięcia wykonywania zbędnych operacji?

Rys. 14.16. Struktury listowe zdegenerowane lewostronnie (a) i prawostronnie (b)

8. W wykorzystywanej do odśmiecania metodzie liczników odwołań każda komórka c zawiera pole z licznikiem, którego wartość określa, ile komórek odwołuje się do niej. Licznik jest zwiększany za każdym razem, kiedy jakaś komórka zaczyna wskazywać na c, a zmniejszany, kiedy odwołanie takie jest likwidowane. Program odśmiecający używa tego licznika podczas oczyszczania pamięci: jeśli wartością licznika jakiejś komórki jest zero, komórkę tę można zwolnić, bo żadna inna na nią nie wskazuje. Omów zalety i wady tej metody odśmiecania.
9. W algorytmie Bakera przeglądanie pamięci przez program odśmiecający powinno się zakończyć, zanim spotkają się wskaźniki bottom i top w obszarze docelowym i można będzie zamienić obszary rolami. Jaka wartość k to zapewni? Załóżmy, że n jest maksymalną żądaną przez program liczbą komórek, a 2m to liczba komórek w obszarach źródłowym i docelowym. Jaki efekt powoduje podwojenie wartości k, jeśli jest ona liczbą całkowitą i jeśli jest ułamkiem (jeśli na przykład wynosi ona 0,5, to na każde dwa żądania jest wykonywana jedna kopia)?


527

10. W modyfikacji algorytmu Bakera, uaktualniającej strony pamięci kopca po przechwyceniu próby dostępu do nich ze strony mutatora [20], pojawia się problem obiektów przekraczających granicę strony. Zaproponuj rozwiązanie tego problemu.

14.7. Zadania programistyczne

1. Zaimplementuj następującą metodę przydzielania pamięci, opracowaną przez A. W. Wulfa, C. B.Weinstocka i C. B. Johnssona, zwaną metodą szybkiego dopasowywania (ang. quick-fit method) [2]. W metodzie tej używa się tablicy avail o n +1 komórkach, gdzie n jest ustaloną doświadczalnie liczbą najczęściej żądanych rozmiarów bloków, a komórka i zawiera wskaźnik do listy bloków i-tego rozmiaru. Ostatnia (n+1) komórka jest przeznaczona dla bloków innych, rzadziej spotykanych rozmiarów. Może to również być wskaźnik do listy, ale ponieważ takich bloków może być dużo, należałoby zalecić inne rozwiązanie, na przykład drzewo poszukiwań binarnych. Napisz funkcje przydzielające i zwalniające bloki. Zwalniany blok sklejaj z jego sąsiadami. W celu przetestowania swojego programu generuj losowo rozmiary bloków do przydzielenia z pamięci symulowanej za pomocą tablicy o rozmiarze będącym potęgą dwójki.
2. W dualnym systemie par zarządzane są metodą binarną dwa obszary pamięci. Liczba takich obszarów może być jednak większa [11]. Napisz program operujący trzema obszarami o rozmiarach bloków postaci 2^i, 3 * 2^j i 5 * 2^k. Żądany rozmiar bloku s zaokrągla się w górę do najbliższej liczby dającej się zapisać którymś z tych sposobów. Na przykład 9 zostałoby zaokrąglone do 10, co jest rozmiarem bloku z trzeciego obszaru. Jeśli w tym obszarze żądania nie można zrealizować, to rozważa się następną dopuszczalną liczbę, którą jest 12 z drugiego obszaru. Jeśli również i tu brak wolnego bloku o takim lub większym rozmiarze, to jest sprawdzany obszar pierwszy. W razie zakończenia próby przydziału niepowodzeniem umieszczaj żądania na liście i realizuj je, kiedy tylko pojawia się wystarczająco duży blok. Uruchamiaj swój program, zmieniając trzy parametry: rozmiary przydzielanych bloków, liczbę napływających żądań i całkowity rozmiar pamięci.
3. Zaimplementuj prostą wersję programu odśmiecania pokoleniowego, wykorzystującego tylko dwa regiony [14]. Kopiec jest podzielony na dwie równe części.

Rys. 14.17. Kopiec o dwóch obszarach, odśmiecany metodą pokoleniową Appela

528

Rys. 14.18. "Kierat" Bakera
529

W górnej części przechowuje się komórki skopiowane z dolnej jako osiągalne ze wskaźników początkowych. Dolna część jest używana do przydzielania pamięci i zawiera jedynie nowsze komórki (zob. rys. 14.17a). Kiedy zostaje zapełniona, program odśmiecający oczyszczają, kopiując wszystkie osiągalne komórki do części górnej (rys. 14.17b), po czym można już przydzielać pamięć, zaczynając od początku dolnej części. Po kilku takich cyklach górna część również się przepełnia, a komórki kopiowane z dolnej części w rzeczywistości są także przepisywane do części dolnej (rys. 14.17c). W takiej sytuacji rozpoczynamy proces oczyszczania górnej części, kopiując wszystkie osiągalne komórki z części górnej do dolnej (rys. 14.17d), a następnie przenosząc wszystkie osiągalne komórki na początek części górnej (rys. 14.17e).
4. W podrozdziale 14.5 zaprezentowaliśmy program odśmiecający działający w miejscu, ale nie krokowo. Zmodyfikuj go tak, aby działał krokowo. Procedura program () zostanie zastąpiona przez mutator (), pozwalający procedurze collectorO na przetworzenie k komórek, dla pewnej ustalonej wartości k. Aby mutator () nie mógł zaburzyć integralności struktur, być może nie całkowicie przetworzonych przez procedurę collector (), powinien on przepisywać wszelkie nie zaznaczone komórki z FreeList na ToBeMarkedList.
Inną elegancką modyfikację tego algorytmu otrzymuje się, łącząc wszystkie cztery listy w listę cykliczną, tworzącą, nazwany tak przez Henry'ego Bakera [16], "kierat" (rys. 14.18a). Wskaźnik Free jest przesuwany zgodnie z ruchem wskazówek zegara, jeśli nadchodzi żądanie przydzielenia nowej komórki, a wskaźnik ToBeMarked przesuwa się k razy, kiedy pozwala na to mutator. Dla każdej nie będącej atomem komórki, przez którą przechodzi wskaźnik ToBeMarked, jej poprzednik i następnik są przenoszone przed wskaźnik ToBeMarked, jeśli nie są zaznaczone. Kiedy spotykają się wskaźniki ToBeMarked i EndNotFree, nie ma już komórek do zaznaczenia, a kiedy Free spotyka się z NotFree, nie ma już komórek na liście wolnej pamięci (rys. 14.18b). W tym wypadku wszystko, co znajduje się między NotFree a EndNotFree (poprzednio nazywaliśmy to NonFreeList), to "śmiecie", które może wykorzystać mutator. Wskaźniki NotFree i EndNotFree zamieniają się zatem rolami, jak gdyby lista NotFreeList zamieniła się na FreeList (rys. 14.18c). Wszystkie wskaźniki początkowe są przenoszone do części "kieratu" zawartej między wskaźnikami ToBeMarked a EndFree (tworząc zaczątek tego, co dawniej nazywaliśmy ToBeMarkedList), a mutator może wznowić działanie.

Bibliografia

Zarządzanie pamięcią

[1] Smith H.F.: Data structures: Form and function. San Diego, CA, Harcourt-Brace-Jovano-
vich 1987, Ch. 11. [2] Standish T.A.: Data structure techniaues. Reading, MA, Addison-Wesley 1980, Chs. 5, 6.


530

Metody sekwencyjnego dopasowywania

[3] Campbell J.A.: A notę on an optimal-fit method for dynamie allocation of storage. Computer Journal, 1971, 14, s. 7-9.
Metody niesekwencyjne
[4] Oldehoeft R.R., Allan S.J.: Adaptive exact-fit storage management. Communications of
the ACM, 1985, 28, s. 506-511. [5] Ross D.T.: The AED free storage package. Communications of the ACM, 1967, 10,
s. 481-492.

Systemy par

[6] Bromley A.G.: Memory fragmentation in buddy methods for dynamie storage allocation.
Acta Informatica, 1980, 14, s. 107-117. [7] Cranston B., Thomas R.: A simplified recombination scheme for the Fibonacci buddy
system. Communications of the ACM, 1975, 18, s. 331-332.
[8] Hinds J.A.: An algorithm for locating adjacent storage blocks in the buddy system. Communications ofthe ACM, 1975, 18, s. 221-222. [9] Hirschberg D.S.: A class of dynamie memory allocation algorithms. Communications of
the ACM, 1973, 16, s. 615-618. [10] Knowlton K.C.: A fast storage allocator. Communications of the ACM, 1965, 8, s. 623-
-625. [11] Page I.P., Hagins J.: Improving performance of buddy systems. IEEE Transactions on
Computers, 1986, C-35, s. 441-447.
[12] Shen K.K., Peterson J.L.: A weighted buddy method for dynamie storage allocation. Communications ofthe ACM, 1974, 27, s. 558-562.

Odśmiecanie

[13] Appel A.W.: Garbage collection can be faster than stack allocation. Information Processing Letters, 1987, 25, s. 275-279.
[14] Appel A.W.: Simple generational garbage collection and fast allocation. Software - Prac-
tice and Expeńence, 1989, 19, s. 171-183.
[15] Baker H.G.: List processing in real time on a serial computer. Communications of the
ACM, 1978, 21, s. 280-294. [16] Baker H.G.: The Treadmill: Real-time garbage collection without motion sicknss. ACM
SIGPLAN Notices, 1992, 27, No. 3, s. 66-70.
[17] Brooks R.A.: Trading data space for reduced time and code space in real-time collection
on stock hardware. SIGPLAN Symposium on Lisp and Functional Programming. Austin
1984, s. 108-113.
[18] Cheney C.J.: A nonrecursive list compacting algorithm. Communications of the ACM,
1970, 13, s. 677-678.
[19] Cohen J.: Garbage collection of linked data structures. Computing Surveys, 1981, 13,
s. 341-367.
531

[20] Ellis J.R., Li K., Appel A.W.: Real-time concurrent collection on stock multiprocessors.
SIGPLAN Notices, 1988, 23, No. 7, s. 11-20.
[21] Fenichel R.R., Yochelson J.C.: A Lisp garbage-collector for virtual-meemory computer
systems. Communications ofthe ACM, 1969, 12, s. 611-612.
[22] Kurokawa T.: A new fast and safe marking algorithm. Software - Practice and Experien-
ce, 1981, 11, s. 671-682.
[23] Layer D.K., Richardson C.: Lisp systems in the 1990s. Communications of the ACM,
1991,34, No. 9, s. 49-57.
[24] Lieberman H., Hewitt C.: A real-time garbage collector based on the lifetimes of objects.
Communications ofthe ACM, 1983, 26, s. 419-429.
[25] Schorr H., Waite W.M.: Ań efficient machine-independent procedurę for garbage collection in various list structures. Communications of the ACM, 1967, 10, s. 501-506.
26] Wadler P.L.: Analysis of algorithm for real-time garbage collection. Communications of
the ACM, 1976, 19, s. 491-500; 1977, 20, p. 120.
[27] Wegbreit B.: A space-ejficient list structure tracing algorithm. IEEE Transactions on
Computers, 1972, C-21, s. 1009-1010.
[28] Wilson P.R.: Uniprocessor garbage collection techniąues. In: Bekkers, Yves, Coheen,
Jacąuees (eds.): Memory management. Berlin, Springer 1992, s. 1-42.
[29] Yuasa T.: Real-time garbage collection on general-purpose machinę. Journal of Systems
and Software, 1990, 11, s. 181-198.
[30] Zorn B.: Comparing mark-and-sweep and stop-and-copy garbage collection. Proceedings
ofthe 1990 ACM Conference on Lisp and Functional Programming, Nice 1990, s. 87-98.