Dynamiczne przydzielanie pamięci
metodą stref nieprzesuwalnych
Daniel Oz
minkowski
Metoda stref nieprzesuwalnych:
a) pierwsze dopasowanie (first fit)
b) najgorszego dopasowania (worst fit)
c) najlepszego dopasowania (best fit)
Wstęp

Opis dynamicznego podziału na strefy

Kryterium wyboru strefy do przydzielenia

Algorytm przydzielania

Algorytm zwalniania

Zalety

Wady
Dynamiczny podział na strefy

Informacje o strefach znajdują się w tablicy

Przechowywane informacje to:

Rozmiar

Umiejscowienie

Status (dostępna/niedostępna)
Implementacja tablicy stref
wg  SO Madnick, Donovan

2 tablice statyczne

1. przechowuje informacje o strefach
zajętych

2. przechowuje informacje o strefach
wolnych

Sugerowane ulepszenie  lista dynamiczna
zamiast tablicy statycznej
Kryterium przydziału strefy

Pierwsze dopasowanie - First fit

Pierwszy wolny obszar wg adresu pamięci

Najlepsze dopasowanie - Best fit

Tablicę wolnych stref sortujemy pod względem
rozmiaru rosnąco. Wybieramy obszar którego
rozmiar najmniej różni się od rozmiaru żądania.

Najgorsze dopasowanie - Worst fit

Tablicę wolnych stref sortujemy pod względem
rozmiaru malejąco. Wybieramy największy
obszar i rezerwujemy początek wolnej strefy.
Przydział ciągłego obszaru
pamięci 
pierwsze dopasowanie
blok
kierunek
przeszukiwania
pamięć
Pierwsze dopasowanie

Metoda faworyzuje zajmowanie pamięci o
niższych adresach

Pozostaje obszar wolny o wysokim adresie,
który będzie wykorzystany, gdy przyjdzie
żądanie dużego obszaru pamięci
Przydział ciągłego obszaru
pamięci 
najlepsze dopasowanie
blok
kierunek
przeszukiwania
pamięć
Najlepsze dopasowanie

Może zajść szczęśliwa sytuacja, że istnieje
wolny obszar dokładnie o żądanym
rozmiarze i na pewno on zostanie wybrany

Przeważnie jednak tak się nie dzieje i trzeba
utworzyć mały wycinek

Ten wycinek jest tak mały, że przeważnie do
niczego się nie nadaje (fragmentacja)
Przydział ciągłego obszaru
pamięci 
najgorsze dopasowanie
blok
kierunek
przeszukiwania
pamięć
Najgorsze dopasowanie

Najwolniejsze  trzeba przeszukać wszystkie
dziury (lub odpowiednio segregować tablicę
wolnych miejsc)

Pozwala rozwiązać częściowo problem
fragmentacji wewnętrznej
Algorytm przydzielania
Algorytm zwalniania
Zalety

Podział strefowy zezwala na wiele wątków
wykonywanych  jednocześnie

Nie wymaga kosztownego sprzętu

Stosowane algorytmy są proste i łatwe do
zaimplementowania
Wady

Fragmentacja pamięci

Nawet gdy pamięć nie jest
rozczłonkowana, pojedynczy wolny
obszar może być zbyt mały, żeby
pomieścić strefę

Można uruchomić program o kodzie
mniejszym lub równym rozmiarowi
pamięci
Cel projektu

Która metoda jest najefektywniejsza w jakich
warunkach?

Kryteria:

czas oczekiwania procesu na przydzielenie
pamięci

procent używanej pamięci

Zmienne niezależne:

Zapotrzebowanie na pamięć

Zapotrzebowanie na czas procesora
Literatura

 Systemy operacyjne Madnick Donovan

 Zarządzanie pamięcią operacyjną 
wykłady dr Dariusz Wawrzyniak (AE we
Wrocławiu)