POLITECHNIKA POZNAC
SKA
Laboratorium z systemów operacyjnych czasu rzeczywistego
Projekt: 4. Zarządzanie pamięcią operacyjną metodą stref nieprzesuwalnych z zadaniami
oczekującymi na przydział pamięci z uwzględnieniem strategii:
I) pierwszego dopasowania
II) najlepszego dopasowania
III) najgorszego dopasowania
Rok akad. Data: 10 IV 2008
2007/2008
Wydział Elektryczny Oddanie sprawozdania
Daniel
Studia dzienne
Oz
minkowski
Automatyka i
Robotyka
Grupa A3/2 Ocena:
1. Założenia projektu
Temat: Zarządzanie pamięcią operacyjną metodą stref nieprzesuwalnych z zadaniami
oczekującymi na przydział pamięci z uwzględnieniem strategii:
I) pierwszego dopasowania
II) najlepszego dopasowania
III) najgorszego dopasowania
Algorytm programu:
Język programowania : C++, środowisko: Borland C++ Builder Personal.
2. Opis projektu
Ë% Zarys problemu
Zadaniem programu jest symulacja układu przydzielającego pamięć procesom
uporządkowanym w liście procesów oczekujących. Program wykorzystuje metodę
dynamicznego przydzielania stref nieprzesuwalnych w trzech jej odmianach nazywanych:  first
fit - pierwsze dopasowanie,  best fit - najlepsze dopasowanie,  worst fit - najgorsze
dopasowanie.
Ë% Opis metody
Metoda zarządzania pamięcią za pomocą dynamicznego przydzielania stref nieprzesuwalnych
jest metodą prymitywną, ale umożliwiającą wielowątkowość. Jedynymi jej zaletami są łatwość
implementacji oraz wyżej wspomniana możliwość umieszczenia wielu programów jednocześnie
w pamięci operacyjnej.
Strefa to pamięć przydzielona jednemu procesowi stanowiąca dla niego jego przestrzeń
adresową. Proces nie powinien mieć dostępu do pamięci spoza swojej wyznaczonej strefy, aby
nie powodować konfliktów ze współbieżnymi procesami.
Poprzez dynamiczne przydzielanie stref rozumie siÄ™ przydzielanie ich w czasie wykonania, gdy
nadejdzie żądanie przydzielenia pamięci dla nowo uruchamianego procesu.
Nieprzesuwalność stref oznacza, że gdy raz przydzielimy dany obszar nie możemy już go
przesuwać, co uniemożliwia defragmentację wolnego obszaru pamięci. Jest to oczywiście wada
tej metody.
Aby móc zarządzać zasobami trzeba mieć możliwość przechowywać informacje o strefach
zajętych i wolnych. W książce  Systemy operacyjne zaproponowano implementację tej metody
przy wykorzystaniu dwóch tablic (lub lepiej list dynamicznych): jednej dla stref przydzielonych,
drugiej dla stref wolnych. W tablicy musi znalez
ć się informacja o adresie i rozmiarze strefy.
Pisząc program wykorzystałem inną organizację danych: informacje przechowywane są w
jednej tablicy, a do każdego rekordu dodawany jest stan danej strefy  wolne/zajęte oraz (na
potrzeby symulacji i synchronizacji w czasie, numer cyklu procesora w którym dany proces
zakończy się wykonywać).
Każdy model pamięci jest symulowany poprzez kolejkę procesów oczekujących, tabelę
opisującą rozmieszczenie stref oraz graficzną reprezentację pamięci. Dla wygody umieściłem
wszystkie wskaz
niki do elementów okna reprezentujących modele w tablicy wskaz
ników do
odpowiedniego typu.
W każdym cyklu procesora istnieje możliwość przydzielenia pamięci dla procesu oczekującego
w kolejce  jeden proces na jeden cykl oraz zwolnienia zasobów wykorzystywanych przez
wszystkie procesy, które zakończyły wykonywanie w danym cyklu.
W programie wykorzystane sÄ… trzy metody:
- pierwszego dopasowania  proces jest lokowany w pierwszej znalezionej strefa, która jest
większa niż żądany obszar
- najlepszego dopasowania  proces jest umieszczany w najmniejszej strefie większej niż
żądany obszar
- najgorszego dopasowania  proces jest umieszczany w największej wolnej strefie w pamięci
Algorytm przydzielania pamięci jest niemal identyczny dla wszystkich metod  program
przegląda tabelę stref w poszukiwaniu takiej, która zdolna jest pomieścić nadchodzący proces.
To co odróżnia od siebie algorytmy to kryteria sortowania tabeli stref: przy  first fit sortowana
jest ona według adresu stref rosnąco, przy  best fit według rozmiaru strefy rosnąco (małe
strefy najpierw), przy  worst fit według rozmiaru malejąco. W trakcie realizacji projektu
nasunął mi się wniosek, że  worst fit ma zaletę, której nie wymieniano w materiałach
dydaktycznych, a mianowicie  jeśli pierwsza w tabeli (największa) strefa nie jest zdolna
pomieścić żądania to znaczy, że żadna strefa nie będzie do tego zdolna. Jest to zaleta, której nie
mają pozostałe dwie metody.
Algorytm przydzielania pamięci:
Algorytm zwalniania pamięci:
3. Struktura danych użytych w programie:
Przyciski:
TButton *Zadaj; //kliknięcie powoduje dodanie do kolejki procesu o wprowadzonych parametrach
TButton *ZwiekszLicznik; //ręczne zwiększanie licznika cykli procesora
TButton *LosujNowyProces;
TCheckBox *Auto;
Wprowadzanie danych:
TEdit *Czasms; //jak często ma być zwiększany licznik (czas przepełnienia timera XTAL)
TEdit *CzasTrwania; //okno wprowadzania danych
TEdit *Ilosc; //Ile nowych procesów ma być wylosowanych po naciśnięciu przycisku  Losuj...
TEdit *Licznik;
TEdit *RozmiarZadania; //Okno wprowadzania danych
Lista akcji jakie można wykonać:
TActionList *ActionList;
TAction *AZwiekszLicznik; //zwiększenie licznika cykli procesora
TAction *AZadaj; //funkcja obsługująca przydzielanie pamięci we wszystkich 3 modelach
TAction *AZwolnij; //zwalniają zasoby zajmowane przez kończący się proces, również scala wolne strefy
TAction *APorzadkujWgAdresu; //porzÄ…dkuj pierwszÄ… tabelÄ™ stref wg kryterium adresu (bÄ…belkowe)
TAction *APorzadkujWgRozmiaruRosnaco; // porzÄ…dkuj drugÄ… tabelÄ™ stref wg kryterium rozmiaru (bÄ…belkowe)
TAction *APorzadkujWgRozmiaruMalejaco; // porzÄ…dkuj trzeciÄ… tabelÄ™ stref wg kryterium rozmiaru (bÄ…belkowe)
TAction *APrzedstawGraficznie; //odśwież widok paska reprezentującego pamięć
TAction *APrzesunPusteNaKoniec; //przesuwa puste pola na koniec tabeli stref i zmniejsza liczbÄ™ kolumn
Tabele (de facto listy dynamiczne) przechowujÄ…ce dane o strefach:
TStringGrid *TabelaStref1;
TStringGrid *TabelaStref2;
TStringGrid *TabelaStref3;
Graficzna reprezentacja pamięci:
TPaintBox *Pamiec1;
TPaintBox *Pamiec2;
TPaintBox *Pamiec3;
Tabela (de facto listy dynamiczne) przechowujÄ…ce dane o oczekujÄ…cych procesach:
TStringGrid *Kolejka1;
TStringGrid *Kolejka3;
TStringGrid *Kolejka2;
Timer, którego przepełnienie powoduje zwiększenie licznika:
TTimer *XTAL;
4. Instrukcja użytkownika
Aby przeprowadzić szybką symulację zachowania się pamięci zarządzanych
trzema różnymi odmianami metody dynamicznego przydzielania stref
nieprzesuwalnych należy:
Wpisać liczbę nowych procesów w polu znajdującym się na przycisku
 Losuj ... Nowych Procesów , które mają być dodane do kolejki (domyślnie
50), a następnie kliknąć w/w przycisk. Istnieje możliwość ręcznego
wprowadzania procesów poprzez podanie parametrów procesu w oknach
 Rozmiar żądania oraz  Czas trwania , a następnie kliknięcie przycisku
 Wprowadz
ręcznie .
Na formatce w prawej górnej części znajduje się pole  Licznik , które
informuje o liczbie taktów procesora, które minęły od początku symulacji.
Można ręcznie przechodzić do następnego taktu poprzez klikanie przycisku
 Zwiększ licznik lub zaznaczyć pole  Automatycznie co ... ms podając
wcześniej żądaną liczbę milisekund (domyślnie 1000ms, czyli 1s).
Z chwilą obsłużenia żądania znajdującego się na pierwszym miejscu w kolejce
będzie można zaobserwować gdzie przydzielono strefę we wszystkich trzech
modelach.
Automatyczne zwiększanie licznika procesora zakończy się dopiero po
odznaczeniu pola  Automatycznie co ... ms .
W każdej chwili można wskazać kursorem strefę w graficznej reprezentacji
pamięci, aby uzyskać o niej wszystkie informacje. Pojawią się one w prawym
górnym rogu.
5. Wnioski
Moim celem było stworzenie symulacji zdolnej do zbadania, który algorytm
przydzielania jest najlepszy. Nie udało mi się do końca osiągnąć tego celu, ale
drobne modyfikacje programu pozwalajÄ… na Å‚atwe dodanie opcji zbierania
danych statystycznych o procesach, takich jak długość oczekiwania na
przydzielenie pamięci czy procent wykorzystanej pamięci. Ciekawym
pomysłem byłoby dodanie opcji losującej nowe procesy, które miałyby
parametry opisane rozkładem normalnym/Poissona/równomiernym. Wyniki
można byłoby wtedy zapisywać do pliku celem póz
niejszej obróbki np. w
arkuszu kalkulacyjnym.
Oprócz tego zauważyłem rzadko, jeśli w ogóle, wymienianą cechę metody
 worst fit , mianowicie: jeśli uporządkujemy tabelę stref wg rozmiaru
malejąco, oznacza to, że pierwsza strefa jest największa. To pociąga za sobą
oczywisty wniosek, że jeśli pierwsza strefa nie jest w stanie obsłużyć
przychodzącego żądania oznacza, to, że żadna z nich nie może. Powoduje to,
że wystarczy sprawdzić tylko jedną strefę zamiast przeszukiwania całej tablicy.
6. Literatura
1. E. Madnick, J. Donovan,  Systemy operacyjne , Państ. Wydaw. Naukowe,
1983.
2.  Zarządzanie pamięcią operacyjną  wykłady dr Dariusz Wawrzyniak
3. G. W. Evans II, G. F. Wallace, G.L. Sutherland,  Symulacja na maszynach
cyfrowych , Wydawnictwa Naukowo- Techniczne, Warszawa 1973.