Należy zaimplementować (w przestrzeni użytkownika) bibliotekę symulującą pamięć wirtualną ze stronicowaniem wraz z kilkoma algorytmami wymiany stron, będącymi również bibliotekami.
Należy zaimplementować bibliotekę symulującą działanie pamięci wirtualnej ze stronicowaniem. Symulowana pamięć ma się znajdować w zaalokowanej przez bibliotekę pamięci komputera, ale programy mają uzyskiwać do niej dostęp za pomocą opisanych poniżej funkcji z biblioteki, a nie bezpośrednio. Strony, które nie mieszczą się w pamięci mają być przechowywane w jednym pliku dyskowym (symulowanym dysku), tworzonym podczas inicjacji biblioteki i usuwanym przy jej zamykaniu. Strony mają być wczytywane i zapisywane za pomocą asynchronicznego wejścia-wyjścia.
Nasza symulowana pamięć to ciągły obszar bajtów adresowany od 0 do (page_size * addr_space_size) - 1 (wartości te podaje się przy inicjacji). Obszar ten jest złożony z ramek o wielkości 4-512 bajtów.
Aby dostać się do zawartości pamięci program wywołuje funkcję odczytującą albo zapisującą jeden bajt pamięci pod podanym adresem. Gdy strona zawierająca żądany adres znajduje się w symulowanej pamięci operacje te po prostu zwracają wartość. Gdy strony tej nie ma w pamięci (została wcześniej zapisana na symulowany dysk), należy ją wczytać.
Wybór strony, którą zwolnimy zależy od wybranej strategii stronicowania. Należy pamiętać o optymalizowaniu ilości odczytów i zapisów z dysku twardego. Wszystkie operacje wejścia-wyjścia muszą być wykonywane za pomocą mechanizmów asynchronicznego wejścia-wyjścia. Liczba jednocześnie wykonywanych operacji wejścia-wyjścia jest ograniczona.
Należy przygotować plik page.h, w którym trzeba umieścić deklarację struktury page:
typedef struct page {
...
} page
reprezentującej stronę w pamięci. Strukturę należy uzupełnić odpowiednimi polami.
Bibliotekę inicjuje się za pomocą funkcji:
typedef void (*pagesim_callback)(int op, int arg1, int arg2) int page_sim_init( unsigned page_size, unsigned mem_size, unsigned addr_space_size, unsigned max_concurrent_operations, pagesim_callback callback)
gdzie:
page_size to rozmiar strony w bajtach,
mem_size to rozmiar symulowanej pamięci operacyjnej, w ramkach,
addr_space_size to rozmiar symulowanej przestrzeni adresowej, w stronach
max_concurrent_operations to największa dopuszczalna liczba operacji wejścia-wyjścia wykonywanych jednocześnie,
callback to adres funkcji wywoływanej przez operacje dostępu do pamięci, opisana poniżej; gdy wartością tego parametru jest NULL operacje nie wywołują żadnej funkcji.
W przypadku błędu funkcja ustawia odpowiednio wartość errno oraz zwraca -1. Po poprawnej inicjacji biblioteki zwracane jest 0. Inicjacja biblioteki może się udać tylko raz. Po poprawnej inicjacji wynik działania kolejnych wywołań jest nieokreślony.
Należy umożliwić prowadzenie do 64 współbieżnych operacji asynchronicznego wejścia-wyjścia.
Działanie biblioteki kończy się za pomocą wywołania: void int page_sim_end() które powoduje zwolnienie wszystkich zasobów używanych przez bibliotekę. Po wywołaniu tej funkcji wywoływanie przez proces innych operacji z biblioteki powoduje zwrócenie wartości -1 i ustawienie wartości zmiennej errno na odpowiedni kod błędu.
Po zainicjowaniu biblioteki dostępne są funkcje:
int page_sim_get(unsigned a, uint8_t *v) int page_sim_set(unsigned a, uint8_t v)
a to adres, v to wskaźnik do wartości bądź wartość.
Operacje te odpowiednio odczytują i zapisują jeden bajt spod podanego adresu. Wynikiem operacji jest 0 gdy się ona powiedzie lub jeden ze zdefiniowanych przez autora biblioteki kodów błędów w przypadku niepowodzenia.
Należy zaimplementować następujące biblioteki strategi wymiany stron:
Wszystkie zaimplementowane biblioteki powinny posiadać taki sam interfejs określony w pliku nagłówkowym strategy.h. Interfejs musi zawierać co najmniej funkcję
page* select_page(...),
gdzie page to typ reprezentujący stronę w pamięci. Funkcja ta dla zadanej jako argument listy ramek znajdujących się w pamięci wybiera tę, która najlepiej spełnia warunki kwalifikujące do jej usunięcia, lub NULL jeśli nie ma takiej ramki. Lista argumentów tej funkcji może być dowolna ale jednakowa dla wszystkich strategii.
Skompilowana biblioteka wymiany stron powinna powinna być linkowana przy kompilacji, należy więc zadbać o przygotowanie odpowiedniego pliku Makefile. Plik Makefile powinien zawierać reguły:
Do śledzenia postępów operacji wymiany strony służy podana przy inicjowaniu biblioteki funkcja użytkownika. Przyjmuje ona trzy parametry - operację i ewentualnie jej argument(y). Operacja ta ma być wywoływana przez funkcje page_sim_get i page_sim_set w następujących sytuacjach:
Ponieważ funkcja użytkownika nie musi pozwalać na jednoczesne wywołania z wielu wątków, trzeba zapewnić synchronizację jej wywołań.
Operacje page_sim_get/set mogą być wywoływane jednocześnie przez wiele wątków, należy więc użyć odpowiednich (dowolnie wybranych) mechanizmów synchronizacji.
Zachowanie biblioteki w przypadku wywołania przez program funkcji systemowej fork (oraz clone, vfork) jest nieokreślone.
Działanie biblioteki w różnych procesach jest niezależne - w szczególności zawartość pamięci jest zupełnie oddzielna, a na dysku można stworzyć oddzielne pliki dla każdej inicjacji biblioteki.
Rozwiązanie zadania proszę przesyłać skryptem submitze swojego konta na komputerze students w terminie do 17 stycznia 2011 roku na adres solab@mimuw.edu.pl. Katalog z rozwiązaniem ma mieć następującą strukturę.
W głównym katalogu archiwum ma się znajdować plik Readme.txt zawierający opis rozwiązania, w tym użytych metod komunikacji i synchronizacji.
W katalogu src/ umieszczonym w głównym katalogu mają być pliki ze źródłami biblioteki oraz plik Makefile.
W katalogu src/ muszą się znajdować pliki:
Wszystkie pytania co do treści należy kierować do Tomasza Jurkiewicza na adres tj219438@mimuw.edu.pl po uprzednim sprawdzeniu pliku z pytaniami i odpowiedziami.