Zjawiskiem związanym z podziałem i przydziałem pamięci jest fragmentacja. Pod pojęciem fragmentacji kryją się dwa osobne zjawiska określane jako fragmentacja zewnętrzna i fragmentacja wewnętrzna. Fragmentacja wewnętrzna dotyczy niewykorzystania pamięci wewnątrz przydzielonego bloku i najczęściej jest skutkiem operowania przez system większymi jednostkami, niż dokładność specyfikacji potrzeb ze strony aplikacji lub jądra systemu. Ten rodzaj fragmentacji jest charakterystyczny dla systemów z podziałem stałym.
Fragmentacja zewnętrzna oznacza podział na osobne części. Problem fragmentacji zewnętrznej ujawnia się najczęściej w zarządzaniu wolną przestrzenią. W niektórych podejściach do zarządzania pamięcią (np. w stronicowaniu) można też go odnieść do obszarów pamięci przydzielonych procesom. Pofragmentowanie wolnej przestrzeni bierze się stąd, że przydzielane są kolejne fragmenty pamięci, a następnie część z nich jest zwalniana, a część pozostaje zajęta.
W przedstawionym obrazie pamięci wolna przestrzeń jest podzielona na 4 fragmenty, z których żaden nie jest wystarczająco duży, żeby pomieścić w ciągłym obszarze pamięci blok danych na potrzeby procesu. Gdyby jednak udało się scalić wolne fragmenty w jeden duży obszar, wystarczyłoby miejsca na więcej niż 2 takie bloki.
Możliwość scalenia zależy od sposobu wiązania adresów. Sensowna realizacja scalenia wolnych fragmentów wymaga ustalania adresów fizycznych w czasie wykonania przy wsparciu jednostki zarządzania pamięcią.
Fragmentacja wewnętrzna wynika najczęściej z ograniczeń na rozmiar przydzielanej jednostki. Nie jest to jednak jedyny przypadek. W przedstawionym przykładzie przydział dokładnie tylu bajtów, ile wynosi zapotrzebowanie, powoduje, że koszt utrzymania bardzo małego obszaru wolnego jest niewspółmiernie duży, np.:
Dlatego wolny obszar przydzielany jest w całości, ale nie jest w pełni wykorzystany. Powstaje wiec fragmentacja wewnętrzna, wynikająca z decyzji zarządcy, a nie z konfiguracji systemu.
W podejściu z podziałem stałym nie można oczekiwać przydziału ciągłego obszaru pamięci o rozmiarze większym, niż to wynika z podziału, dokonanego na etapie konfiguracji systemu. Konsekwencją podziału stałego przestrzeni procesów użytkownika jest konieczność ograniczenia rozmiaru procesu do rozmiaru partycji. Z drugiej strony, mniejszym procesom również przydzielane są obszary pamięci, wynikające z takiego podziału, co oznacza marnowanie pamięci w związku z fragmentacją wewnętrzną.
W najprostszym przypadku partycje mają ten sam rozmiar. Realizacja żądania polega zatem na znalezieniu jakiejkolwiek wolnej partycji. W przedstawionym przykładzie realizacji żądań przydziału pamięci dla dwóch procesów obie wolne partycje zostają zajęte w całości, pomimo że potrzeby procesów są mniejsze.
Istotnym problemem może być przypadek zażądania przydziału obszaru większego, niż udostępniony przez system w wyniku podziału. W przypadku przydziału pamięci na dane (np. w jądrze) ograniczenia, wynikające z podziału stałego, można przewidzieć wcześniej i dostosować odpowiednio struktury danych. W przypadku programu można zastosować technikę, zwaną nakładkowaniem. Nakładkowanie polega na podziale kodu (nie danych) na części niezależne od siebie i wymianie w miarę potrzeb jednej części — nakładki (ang. overlay) — na inną.
W programie wydziela się część stałą, która zawsze znajduje się w pamięci oraz nakładki, które wiąże się z tzw. sekcją nakładkowania. Na każdą sekcję wydzielona jest pewna część pamięci. Nakładki w ramach tej samej sekcji podlegają wymianie — jedna nakładka usuwa inną. W programie może być kilka takich sekcji.
Z nakładkami wiążą się pewne ograniczenia. Stan nakładki usuwanej z pamięci nie jest nigdzie zapisywany, w związku z tym nie może ona ulegać zmianie — może zawierać tylko kod, ewentualnie stałe. Ograniczone są też możliwości przekazywania danych i sterowania pomiędzy nakładkami w tej samej sekcji, zatem nie można się odwołać z jednej nakładki do drugiej w tej samej sekcji. Przekazywanie danych i sterowania odbywa się najczęściej za pośrednictwem części stałej, czyli w tej części (ewentualnie w nakładce w innej sekcji) znajdują się wywołania podprogramów zlokalizowanych w nakładkach. Podział na nakładki wymaga dokładnej znajomości kodu i przepływu sterowania. Ponieważ nakładkowanie stosowane jest w przypadku dużych programów, podział na nakładki jest złożonym zadaniem. Może też być źródłem dodatkowych, trudno wykrywalnych błędów.
Nakładkowanie nie wymaga wsparcia ze strony jądra systemu operacyjnego, co najwyżej ze strony pewnych narzędzi do tworzenia kodu. Ze względu na uciążliwość technika ta stosowana jest jednak tylko w przypadku istotnych ograniczeń na rozmiar pamięci fizycznej w stosunkowo prostych architekturach. Zalecanym rozwiązaniem, wymagającym jednak wsparcia zarówno na poziomie architektury, jak i na poziomie systemu operacyjnego, jest pamięć wirtualna, która zostanie omówiona w następnym module.
Odpowiedzią na zróżnicowane pod względem wielkości żądania może być podział na partycje o różnych rozmiarach. Realizacja żądania wymaga znalezienie partycji, odpowiednio dobrze dopasowanej do wielkości zapotrzebowania. Może jednak powstać problem decyzyjny w przypadku, gdy najlepiej dopasowane partycje są zajęte, a wolne są partycje większe. Optymalizując przepustowość można przydzielić partycję większą (kosztem fragmentacji wewnętrznej), a optymalizując wykorzystanie pamięci należałoby wstrzymać przydział do momentu zwolnienia najlepiej dopasowanej partycji.
Istotą podziału dynamicznego jest operowanie stosunkowo niewielkimi jednostkami i przydzielanie bloków, stanowiących ciąg kolejnych jednostek w stosownej do zapotrzebowania liczbie. Przydzielany jest zatem ciągły obszar pamięci z dokładnością do rozmiaru jednostki. Jednostka może obejmować 1 bajt, ale częściej operuje się nieco większymi jednostkami, np. 16 bajtów (tzw. paragraf). W przypadku większych jednostek możliwa jest niewielka fragmentacja wewnętrzna.
W przypadku podziału dynamicznego po przydzieleniu odpowiedniego bloku reszta obszaru pozostaje wolna i jest do dyspozycji na potrzeby kolejnych żądań.
Wolne obszary mogą mieć różne rozmiary i trudno z góry ustalić, gdzie znajduje się odpowiedni obszar. Wyróżnia się 4 strategie poszukiwania odpowiedniego obszaru, tzw. dziury.
Pierwszy wolny blok jest zbyt mały, więc przydzielany jest następny wolny blok. Jest on jednak większy niż zapotrzebowanie, dlatego po przydzieleniu pozostanie jeszcze trochę wolnego miejsca. Jest to metoda szybka, biorąc pod uwagę średni czas wyszukiwania. Warto zwrócić uwagę, że blok dałoby się dopasować również w pozostałe wolne obszary, ale zgodnie z kierunkiem przeszukiwania nie były one w ogóle analizowane.
Poszukiwany jest taki obszar wolny, żeby po przydziale pozostało po nim jak najmniej wolnego miejsca. Wymaga to przeszukania wszystkich dziur (dlatego metoda jest stosunkowo powolna), chyba że znajdzie się obszar dokładnie odpowiadający zapotrzebowaniu lub pozostały do przeszukania obszar jest mniejszy niż zapotrzebowanie.
Znalezienie największego wolnego obszaru wymaga również przeszukania wszystkich wolnych dziur, chyba że znajdzie się dziurę większą niż połowa zakresu pamięci, jaki pozostał jeszcze do przeszukania lub obszar pozostały do przeszukania jest niewiększy niż dotychczas znaleziona największa dziura.,/p>
Metoda nie jest zbyt często stosowana, jednak jej idea jest taka, żeby pozostawiać stosunkowo duże wolne obszary, gdyż zarządzanie małymi obszarami jest często nieefektywne (o czym wspomniano przy omawianiu fragmentacji wewnętrznej).
Metoda bloków bliźniaczych (ang. buddy) polega na sukcesywnym dzieleniu dostępnego obszaru pamięci na połowy i przydziale najlepiej dopasowanego bloku, którego rozmiar jest potęgą przy podstawie 2. Jest przy tym ustalony minimalny rozmiar przydzielanego bloku (wykładnik L ).
Jest to metoda pośrednia pomiędzy przydziałem stałym a dynamicznym. Rozmiar partycji nie jest ustalony odgórnie, ale możliwość dopasowania go do żądanej wielkości jest ograniczona. Najmniej korzystny przypadek ma miejsce, gdy wielkość żądanego obszaru jest trochę większa niż potęga dwójki, gdyż prawie połowa przydzielonego bloku pozostaje niewykorzystana (fragmentacja wewnętrzna).
Takie podejście ułatwia jednak zarządzanie, gdyż przyspiesza wyszukiwanie odpowiedniego bloku. Wolne bloki o danym rozmiarze identyfikowane są poprzez listę, której czoło znajduje się w tablicy. Indeks tablicy odpowiada wykładnikowi potęgi dwójki, określającej rozmiar bloku.
Metoda bloków bliźniaczych stosowana jest w systemie Linux, przede wszystkim na wewnętrzne potrzeby jądra. Również podczas przydziału stron pamięci dla procesów zarządca stara się je grupować i w przypadku większych żądań przydzielać ciąg stron o kolejnych numerach, stanowiących bliźniaczy blok.
Przykład pokazuje realizację ciągu żądań przydziału pamięci w metodzie bloków bliźniaczych. Do dyspozycji jest obszar 1 MB (=1024 KB). W odpowiedzi na żądanie przydziału 100 KB następuje podział bloku 1 MB na 2 bloki po 512 KB, z których jeden jest dalej dzielony na 2 bloki po 256 KB, a jeden z tych bloków z kolei dzielony jest znowu na 2 bloki po 128 KB. Dalszy podział nie ma już sensu, gdyż 64 KB to za mało w stosunku do zapotrzebowania. Żądanie przydziału 240 KB będzie zaspokojone niemal natychmiast, ponieważ dokonany wcześniej podział wyodrębnił już jeden blok o rozmiarze 256 KB, a jego połowa byłaby zbyt małym obszarem. Kolejne żądanie — przydziału 64 KB — wymaga przepołowienie wydzielonego już bloku 128 KB. Następne żądanie — 250 KB, wymaga bloku 256 KB, który może powstać przez podział bloku 512 KB. Warto zwrócić uwagę, że gdyby ostanie żądanie dotyczyło bloku o rozmiarze trochę większym, np. 260 KB, przydzielony musiałby być cały blok 512 KB.