POLITECHNIKA POZNACSKA
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
Ozminkowski
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 wskazniki do elementów okna reprezentujących modele w tablicy wskaznikó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ózniejszej 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.
Wyszukiwarka
Podobne podstrony:
DU202poz2072 Szczegółowy zakres i forma dokumentacji projektowej50 w sprawie geodezyjnej ewidencji sieci uzbrojenia terenu oraz zespołów uzgadniania dokumentacji prsw dokumentacja projekt rfiddokumentacja projektowa3 Dokumentacja projektowa I8Y2 (3)Projekt1 Nowy dokument tekstowyprojekt 16 zadanie 3 dokumentacjaProjekt Nr 32 Dokumentacjawięcej podobnych podstron