Buforowanie

Do działania podręcznej pamięci buforowej konieczna jest implementacja pewnej puli buforów umożliwiająca szybkie odszukanie bufora reprezentującego dany blok dyskowy. Pula buforów musi zapewniać jednoznaczne odwzorowanie buforów w bloki dyskowe - każdy blok dyskowy znajduje się w pamięci w co najwyżej jednej kopii. Potrzebne są pewne algorytmy kontrolujące przepływ buforów pomiędzy strukturami danych puli buforów i organizację współpracy z pamięcią systemową.

Funkcjami wysokiego poziomu których wywołanie powoduje użycie mechanizmu buforowania są read i write. Funkcje te w rzeczywistości powodują wywołanie funkcji specyficznych dla konkretnego systemu plików określonych w tablicy rozdzieczej file operations. Dla pewnych systemów plików funkcje opisane poniżej zastępowane są przez podobne, ale bardziej przystosowane, np.: ext2_bread zamiast bread; dla innych systemów standardowe funkcje mechanizmu buforowania są wywoływane po dokonaniu specyficznych czynności, np.: fat_bread używa bread. Gdyby zawsze stosowano wywoływanie tu opisanych funkcji, to kod byłby bardziej czytelny, ale narzut związany z wywołaniem funkcji (szczególnie gdy funkcja specyficzna dla systemu plików nie robi wiele ponad wywołanie funkcji ogólnej) powoduje, że efektywniej jest zakodować daną funkcję ponownie. Dla wszystkich systemów plików implementacje funkcji read lub write powodują jednak wykonanie tego samego algorytmu bread.

Każdy bufor składa się z dwóch części: nagłówka bufora i zawartości pewnego bloku dyskowego. W nagłówku znajdują się pola informujące o odwzorowaniu danych z bufora w pewien blok dyskowy i pola określające aktualny stan bufora. Ponadto istnieją pola używane do zarządzania buforami, czyli utrzymywania pewnych struktur puli buforów i organizacji przepływu buforów w tych strukturach. Dane dyskowe zawarte w buforze mogą mieć różne rozmiary w zależności od wielkości bloku dyskowego. Istnieje 5 standardowych rozmiarów bufora.

Bufory zorganizowane są w trzech podstawowych strukturach:

Z zastosowania pól używanych do konstrukcji tych struktur wynika, że dowolny bufor znajduje się albo na liście wolnych, albo w tablicy mieszającej i jednocześnie na liście LRU. Po uruchomieniu systemu wykonywana jest funkcja inicjująca powyższe struktury. Wszystkie dostępne bufory umieszczane są na liście wolnych i alokowana jest pamięć na tablicę mieszającą, natomiast lista LRU jest początkowo pusta

Ponadto istnieją pewne dodatkowe struktury pomocnicze, jak lista nagłówków buforów, z której pobiera się nagłówek podczas tworzenia nowego bufora, oraz listy służące do stronicowania pamięci zawierającej bufory. Wszystkie bufory leżące na jednej stronie pamięci połączone są w listę, co jest przydatne w czasie usuwania tej strony z pamięci głównej.

Można zauważyć, że przyjęta w Linuxie struktura puli buforów jest różna od spotykanej w innych Unixach; struktura opisywana w książce Bacha składa się tylko z dwóch list, bez pośredniczącej kolejki buforów wolnych.

Funkcja bread jest wywoływana gdy zostanie zgłoszone zapotrzebowanie na pewien blok dyskowy. Jako parametry przekazywany jest numer systemu plików i numer bloku w tym systemie, oraz rozmiar bufora. Funkcja próbuje odszukać blok danych w tablicy mieszającej za pomocą algorytmu getblk, który zwraca bufor (jednocześnie go zajmując) wypełniony aktualnymi danymi w przypadku znalezienia, a w przeciwnym razie pusty. Jeśli zwrócony blok zawiera aktualne dane to jest zwracany dalej do funkcji wywołującej algorytm bread. Gdy bufor jest pusty - nie znaleziono bloku w puli buforów - wykonywana jest niskopoziomowa funkcja inicjująca czytanie z dysku. Proces śpi w oczekiwaniu na zakończenie operacji odczytu. Następnie dokonywane jest sprawdzenie, czy odczytane dane są poprawne, co zabezpiecza przed błędami niskopoziomowych operacji dyskowych. Zwracany jest bufor z poprawnymi danymi, a w przypadku błędu następuje zwolnienie bufora i zwracana jest wartość NULL.

Funkcja breada ma podobne działanie, ale dokonuje również odczytu z wyprzedzeniem. Sprawdzana jest odleglość bieżącej pozycji od konca pliku, i inicjowany jest odczyt następnych bloków z plików. Funkcja ta, podobnie jak bread, czeka na odczytanie żądanego bloku, ale na zakończenie odczytu pozostałych bloków już nie.

Tu można znalezc dokladniejszy opis funkcji bread i breada.

Zapisywanie bloków dyskowych odbywa się w dwóch etapach. Po pierwsze - gdy proces wywoła write, to wykonywany jest algorytm analogiczny do getblk, jednak z pewny m wyjątkiem: w przypadku braku bufora w kolejkach mieszających odczyt niskopoziomowy następuje tylko wtedy zapisywany fragment nie obejmuje całego bloku. Następnie bufor jest modyfikowany i oznaczany jako brudny.

Rzeczywiste zapisanie bloku na dysk ma miejsce w przypadku konieczności opróżnienia buforów potrzebnych dla innych operacji, lub na skutek okresowego działania demona bdflush.

Zadaniem algorytmu getblk jest odszukanie i dostarczenie żądanego bufora z tablicy mieszającej. Jeśli nie ma bufora w tablicy mieszającej zwracany jest nowy, pusty bufor. Bufor taki pobierany jest z kolejki buforów wolnych, która jest uzupełniana zgodnie ze strategią odzyskiwania buforów. Zwracany bufor jest już zablokowany. W liście LRU dany bufor zgodnie ze strategią przesuwany jest na koniec.

Funkcja brelse służy do zwolnienia zablokowanego uprzednio bufora po wykonaniu na nim pewnych operacji przez proces.Jej działanie jest proste.

Warto tutaj rozpatrzyć pewne możliwe scenariusze mogące zachodzić dla algorytmu getblk:

W Unixie, gdzie struktura puli buforów oparta jest na dwóch listach, możliwych scenariuszy jest więcej i ich opis jest bardziej skomplikowany. Przyjęty w Linuxie schemat oparty na trzech strukturach danych znacznie upraszcza konstrukcję puli buforó w (np. zapisywanie buforów na dysk zostało oddzielone od przydzielania nowych buforów), jednak zarządzanie taką pulą wymaga nieco większego nakładu pracy.

Gdy algorytm getblk nie znajduje bufora w tablicy mieszającej, zwraca nowo przydzielony bufor pobrany z kolejki buforów wolnych. Może się jednak zdarzyć, że kolejka buforów wolnych jest pusta, wtedy konieczne jest jej uzupełnienie. Operacja ta odbywa się w kilku fazach, gdyż odzyskiwane bufory mogą pochodzić z kilku źródeł. Dla zwiększenia efektywności każde wywołanie funkcji refill_free_list powoduje odzyskanie ustalonej, większej ilości buforów.

Pierwszym źródłem nowych buforów jest wolna pamięć w systemie. Wywoływana jest funkcja, która przydziela pamięć na nowe bufory. Drugim źródłem są listy LRU, z których odzyskuje się najdłużej nieużywane bufory. Ponadto z list LRU można odzyskiwać bufory oznaczone do zapisu opóźnionego.

Różne sposoby odzyskiwania buforów przeplatają się w różnych fazach algorytmu. Jeśli w systemie jest dużo wolnej pamięci to najpierw wywoływana jest funkcja grow_buffers. Następna próba utworzenia polega na odzyskiwaniu buforów z list LRU. Wybierany jest jeden kandydat z każdej listy (nie uwzględniając buforów oznaczonych do opóŸnionego zapisu), i dopiero wśród tych kandydatów dokonuje się ostatecznej selekcji. Jeśli w tym momencie nie uzyskamy potrzebnej ilości buforów, ponownie wywołujemy grow_buffers z większym priorytetem. Dopiero gdy ta metoda nie skutkuje uruchamiany jest demon zapisujący bdflush. Ostatnią szansą jest ponowne wywołanie grow_buffers z jeszcze większym priorytetem.

Taka strategia szereguje kolejne fazy prób odzyskiwania buforów w zależności od wpływu danej fazy na system i kosztu jej wykonania. Na przykład gdy jest dużo wolnej pamięci to nie ma potrzeby likwidować starych buforów, ale gdy pamięci jest mało to warto zużyć trochę czasu na uruchomienie demona bdflush.

Demon bdflush działa też niezależnie od omawianej funkcji i okresowo zapisuje dane na dysk. Jest to dodatkowe źródło wolnych buforów.

Podstawowe zalety buforowania to zwiększenie wydajności systemu i ujednolicenie interfejsu funkcji dostępu do dysku. Ale ważne jest też np. ukrywanie przed użytkownikiem faktu, że operacji dyskowe są operacjami blokowymi; pozwala na wykonywanie przez procesy operacji bajtowych. Jądro nie musi znać znaczenia danych dyskowych - mogą to być np. i-węzły.

Niestety występują też znaczące wady. Podstawowym problemem związanym z opóźnionym zapisem jest nieznajomość momentu, w którym dane zostają w rzeczywistości zapisywane na dysku. W przypadku awarii systemu dane te zostają utracone. Dodatkowym problemem jest podwójne kopiowanie - z dysku do pamięci jądra i ponownie do pamięci procesu. W Linuxie probuje się temu zaradzić stosując bufory dzielone.

Skomentowane źródła funkcji systemu buforowania:

Szczegółowe opisy algorytmów:

Pozostala literatura: