Pok-13-wyk-Slajd41
Środowisko czasu wykonania – system DPP(2)
Projektując i implementując system DPP należy wybrać metodę reprezentacji bloków i algorytm przydziału bloków.
Bloki można reprezentować za pomocą: mapy bitowej, listy bloków wolnych, znaczników początkowych oraz znaczników granicznych
Przy reprezentowaniu bloków za pomocą mapy bitowej obszar zarządzany przez system DPP jest podzielony na dwie części: mapę bitową i obszar przydzielanych bloków. Każdy bit mapy bitowej odwzorowuje zajętość odpowiadającego mu bloku.
W metodzie wykorzystującej listę bloków wolnych w każdym bloku wolnym pamiętany jest jego rozmiar i adres następnego wolnego bloku. Bloki są uporządkowane na liście według adresów fizycznych. W blokach zajętych nie przechowuje się żadnych dodatkowych danych.
W metodzie znaczników początkowych w każdym bloku – i wolnym i zajętym na początku przechowywany jest bit informacji o zajętości bloku oraz informacja o rozmiarze bloku. Ponieważ znaczniki początkowe nie pozwalają efektywnie określić adresu poprzedzającego bloku (tak jak w liście jednokierunkowej konieczne jest przeszukiwanie od początku) znacznik powiela się również na końcu każdego bloku – mamy wtedy do czynienia z metodą znaczników granicznych.
Bloki mogą być przydzielane ze sterty według różnych algorytmów. Najprostszym i najszybszym algorytmem przydziału jest lista bloków wolnych o jednakowych rozmiarach. Bardziej wyrafinowanym rozwiązaniem są różnorodne strategie dopasowania, z których najbardziej znane są te, które przeglądają stertę w poszukiwaniu pierwszego dostatecznie dużego bloku (First-Fit) albo najlepiej pasującego (Best-Fit).
Systemy bliźniąt (buddy systems) są bardziej elastyczną odmianą listy bloków wolnych o jednakowych rozmiarach. Dopuszczają one, w razie potrzeby, podział większego bloku na mniejsze. Dla wszystkich rozmiarów bloków pamiętane są oddzielne listy bloków wolnych. Stosowane są różne proporcje dzielenia bloków większych na mniejsze, najpopularniejsze są naturalne potęgi dwójki, ale są również systemy oparte o liczby Fibonacciego i systemy wagowe.
