2.1 Miejsce podręcznej pamięci buforowej w systemie plików Linuksa

Rys. 2.1 Miejsce podręcznej pamięci buforowej w systemie plików

W warstwowym modelu systemu plików Linuksa podręczna pamięć buforowa znajduje się w pomiędzy warstwą poszczególnych systemów plików a sterownikami urządzeń blokowych. Wszystkie żądania odczytu i zapisu bloków do urządzeń fizycznych przechodzą przez podręczną pamięć buforową, która dla każdego czytanego i zapisywanego bloku urządzenia tworzy bufor w pamięci fizycznej komputera.

2.2 Dynamiczny system pamięci buforowej

2.3 Algorytm obsługi żądania dostępu do bloku dyskowego

2.3.1 Algorytm obsługi żądania odczytu bloku

Rys. 2.2 Schemat algorytmu obsługi żądania odczytu bloku

Gdy proces żąda odczytu jakiegoś bloku urządzenia (wywołując jakąś funkcję systemową odczytu pliku) to najpierw sprawdzana jest podręczna pamięć buforowa, czy nie zawiera kopii tego bloku. Jeśli bufor tego bloku jest w pamięci i jest on aktualny, to nie następuje żadna operacja odczytu bloku urządzenia, a zamiast tego dane z bufora są kopiowane do przestrzeni adresowej użytkownika. Dopiero w przypadku, gdy takiego buforu nie ma, albo jest, ale nie jest aktualny (jego dane nie zgadzają się z tymi na urządzeniu), wywoływana jest operacja we/wy dla tego urządzenia.

2.3.2 Algorytm obsługi żądania zapisu bloku

Gdy zaś proces żąda zapisu jakiegoś bloku urządzenia (wywołując jakąś funkcję systemową zapisu pliku) to najpierw również sprawdzana jest podręczna pamięć buforowa, czy nie zawiera kopii tego bloku. Jeśli bufor tego bloku jest w pamięci, to nie następuje żadna operacja odczytu bloku urządzenia, a zamiast tego dane są zapisywane do tego buforu i przeznaczony zostaje on do późniejszego zapisu. Dopiero w przypadku, gdy takiego buforu nie ma, wywoływana jest operacja odczytu tego bloku z urządzenia, tworzony jest dla niego bufor, dane zostają zapisane do buforu i zostaje on przeznaczony do późniejszego zapisu.

2.4 Organizacja buforów w pamięci

By efektywnie zarządzać pamięcią buforową bufory są zorganizowane w odpowiednie struktury danych pozwalające na szybkie ich odnajdywanie i wykonywanie odpowiednich czynności (np. przeznaczenie wybranych buforów do zapisu). Należą do nich: tablica z haszowaniem, listy LRU i listy wolnych buforów.

2.4.1 Format przechowywania bloku:

Każdy blok urządzenia przechowywany jest w postaci buforu składającego się z dwóch części:

Rys 2.4 Schemat odwzorowania bloku urządzenia w pamięci buforowej

Nagłówki bufora (struktura buffer_head) znajdują się w taflowej pamięci podręcznej (tzw. SLAB cache), a blok z danymi (tablica typu char) na specjalnie rezerwowanych stronach pamięci.

Nagłówek bufora zawiera dane o samym buforze (m.in. numer urządzenia i bloku, rozmiar bloku), jak i informacje pomocnicze służące do organizacji i zarządzania buforami (m.in. dowiązania do różnych list, stan buforu, czas kiedy ma być zapisany). Wykaz i omówienie jego wszystkich pól zawarte są w dalszej części opracowania.

2.4.2 Identyfikacja buforu

Każdy blok jest identyfikowany przez numer bloku i numer urządzenia. Ta reprezentacja bloku w pamięci buforowej jest jednoznaczna, gdyż w danej chwili istnieje w pamięci tylko jeden bufor identyfikowany daną parą tych wartości.

2.4.3 Tablice z haszowaniem

By szybko odnaleźć przydzielony bufor dla określonego bloku używa się w tym celu tablicy hash_table[] z rozwiązywaniem kolizji metodą łańcuchową, tzn. elementy, dla których obliczone są te same indeksy w tablicy, połączone są w listę dwukierunkową. Do wyznaczenia indeksu takiej listy używa się funkcji haszującej (podana niżej przy szczegółach implementacji), która używa numeru urządzenia i numeru bloku. Po obliczeniu wartości funkcji haszującej dla poszukiwanego buforu, należy jeszcze przejrzeć po kolej listę znajdującą się pod obliczonym indeksem, w celu jego znalezienia. Rozmiar tej tablicy jest obliczany przy inicjalizacji pamięci buforowej, podczas startu systemu w procesie init() na podstawie ilości stron pamięci fizycznej.

W tablicy tej znajdują się tylko te nagłówki buforów, które obsługują przydzielone bufory.

Rys. 2.5 Fragment przykładowej tablicy hash_table[]

2.4.4 Listy LRU

Są to dwukierunkowe listy cykliczne nagłówków używanych buforów.

• oddzielne listy LRU dla poszczególnych typów buforów
  Bufory są umieszczany na różnych listach w zależności od ich stanów.
• bufory przechowywane według czasu ich użycia
  Bufor jest wstawiany na koniec listy, a usuwany z jej początku. W związku z tym są one uporządkowane na liście rosnąco według czasu ich użycia.

W obecnej wersji jądra są cztery takie listy - każda zawiera inny typ buforów:

Typ	Zawartość
BUF_CLEAN	bufory aktualne
BUF_LOCKED	bufory zablokowane (skierowane do zapisu)
BUF_DIRTY	bufory zmodyfikowane, jeszcze nie skierowane do zapisu
BUF_PROTECTED	chronione - ciągle obecne bufory Ramdisku

* Zmiana w wersji 2.4.7 *

W stosunku do poprzedniej wersji jądra (2.2.x) zwiększono liczbę list LRU - dodano nowy typ listy LRU - BUF_PROTECTED.

Początki wszystkich list są umieszczone w globalnej tablicy list LRU lru_list[] indeksowanej typami list.

Rys. 2.6 Przykładowa tablica list LRU lru_list[]

Listy LRU realizują algorytm LRU.

2.4.5 Algorytm LRU (Least Recently Used - najdawniej używane)

Jego szczegóły oraz analizę można znaleźć w książce Silberschatza "Podstawy systemów operacyjnych". Dla krótkiego przypomnienia jest to algorytm zastępowania buforów w pamięci, który do oszacowania najbliższej przyszłości używa niedawnej przeszłości. Przy braku wolnych buforów zastępowane są najdawniej użyte. Potrzebuje on jakiegoś sposobu segregowania czasowego bloków przy odwoływaniu się do nich.

W Linuksie segregowanie czasowe jest zaimplementowane przez kolejkowanie buforów na listach LRU.

Co ciekawe w praktyce korzysta się z algorytmu LRU tylko przy zapisywaniu buforów zmodyfikowanych (z listy BUF_DIRTY). Zatem tak naprawdę pozostałe listy nie są potrzebne (poza tym, że segregują bufory według ich typów).

2.4.6 Listy wolnych buforów

Są to dwukierunkowe listy cykliczne zawierające, jak wskazuje nazwa, nagłówki wolnych buforów.

Każda pojedyncza lista zawiera tylko wolne bufory jednej określonej wielkości bloku. W obecnej wersji jądra dopuszczalnych jest tylko 7 różnych wielkości bloków:

Początki wszystkich 7 list są umieszczone w globalnej tablicy list wolnych buforów free_list[] indeksowanej kolejnymi pozycjami wielkości bloków. Do przeliczania rozmiaru bloku na indeks w tablicy wolnych buforów służy specjalne makro.

Rys 2.7 Fragment przykładowej tablicy list wolnych buforów free_list[]

W momencie przydzielania nowego buforu o danym rozmiarze jest on usuwany z odpowiedniej listy buforów wolnych i wstawiany do tablicy z haszowaniem i odpowiedniej listu LRU.

2.4.7 Lista nieużywanych buforów

Przechowuje bufory, które nie są już wykorzystywane. Stanowią one rezerwę, która jest wykorzystywana w przypadku braku odpowiednich buforów na liście wolnych buforów. Gdy liczba buforów nieużywanych przekroczy ustalony limit, to pamięć przez nie zajmowana jest zwalniana.

2.4.8 Umiejscowienie buforu w omówionych strukturach danych

W danej chwili bufor znajduje się:

• albo na liście wolnych buforów - jeśli nie jest przydzielony do żadnego bloku urządzenia
• albo w tablicy z haszowaniem i na którejś z list LRU - jeśli jest przydzielony
• albo na liście nieużywanych buforów.

Gdy bufor jest zwalniany, usuwany jest z tablicy z haszowaniem i listy LRU i dołączany do odpowiedniej listy wolnych buforów.

2.5 Mechanizm aktualizacji stanu pamięci buforowej

W celu zapewnienia, że bufor zmodyfikowany zostanie zapisany, jak i odśmiecania pamięci buforowej ze starych buforów w razie zapotrzebowania na nowe bufory w Linuksie używa się:

Bdflush

Jest to demon zrealizowany jako wątek jądra, uruchamiany przy inicjalizacji systemu w procesie init (init/main.c).
Zajmuje się on kompleksową obsługą listy zmodyfikowanych buforów. W nieskończonej pętli zapisuje określoną parametrem liczbę buforów zmodyfikowanych, jeśli dodatkowo po tym zabiegu, stosunek liczby zmodyfikowanych buforów do ich całkowitej liczby, jest zbyt duży, to ponownie "wyrzuca" do urządzenia następną porcję buforów, a w przeciwnym przypadku przełącza się w stan uśpienia. Może być dodatkowo obudzony w razie niedoboru wolnych buforów, albo potrzeby zmniejszenia pamięci buforowej.

Jego parametry mogą być modyfikowane podczas działania.

Update

Ten demon pracuje jako drugi wątek jądra związany z zarządzaniem pamięcią buforową. Podobnie jak bdlfush, uruchamiany jest przy starcie systemu. W nieskończonej pętli, co pewien okres czasu (podany jako parametr dla funkcji bflush), budzi się i synchronizuje stare bufory (dokładniej: zapisuje bloki specjalne, i-węzły oraz zmodyfikowane bufory, dla których minął czas opóźnienia).

refill_freelist(int size)

Jest to funkcja do pozyskiwania wolnych buforów.

• najpierw próbuje przydzielić nową stronę na bufory
• w razie niepowodzenia wykorzystuje bdflush by odzyskać trochę wolnych buforów z używanych buforów

refile_buffer(struct buffer_head *bh)

Przenosi bufor do właściwej listy LRU.

2.6 Wykorzystanie mechanizmu pamięci buforowej

Get block - getblk(kdev_t dev, int block, int size)

Podstawowa funkcja realizująca mechanizm podręcznej pamięci buforowej. Zwraca ona bufor dla określonego parametrami bloku urządzenia. To ona próbuje najpierw zlokalizować bufor żądanego bloku w pamięci. Gdy to się nie udaje, to przydziela nowy bufor o odpowiednim rozmiarze z listy wolnych buforów, wstawia go do tablicy z haszowaniem i odpowiedniej listy LRU. W przypadku braku odpowiedniego wolnego buforu próbuje go pozyskać (za pomocą refill_freelist()).

Block read - bread((kdev_t dev, int block, int size)

Funkcja zwraca bufor zawierający żądany blok. Używa do tego celu pamięci buforowej - jeśli znajdzie w niej odpowiadający blokowi aktualny bufor, to go zwraca, w przeciwnym przypadku odczytuje blok do bufora (obecnego w pamięci bądź nowoprzydzielonego) za pomocą funkcji ll_rw_block() (Low Level Read/Write Block - z pliku drivers/block/ll_rw_blk.c).

Uwaga: w poprzedniej wersji jądra Linuksa istniała funkcja breada() (Block Read Ahead), czytająca kilka kolejnych bloków z wyprzedzeniem. Obecnie jej już nie ma, ale sam mechanizm pozostał. Jest on nadal dostępny m.in. w funkcji obsługi żądania operacji blokowej dla urządzenia: ll_rw_block() z parametrem READA. Poza tym mechanizm ten realizują funkcje odczytu plików w konkretnych systemach plików.

Block release - brelse(struct buffer_head *bh)

Funkcja zwalnia blok: przydzielony mu bufor musi by zapisany na urządzeniu i zwolniony.

3. Wybrane szczegóły implementacyjne

3.1 Nagłówek buforu

3.1.1 Definicja struktury buffer_head z pliku nagłówkowego include/linux/fs.h

struct buffer_head {
	/* Pierwsza linia pamięci cache: */
	struct buffer_head *b_next;	/* dowiązanie na liście w tablicy z haszowaniem */
	unsigned long b_blocknr;	/* numer bloku */
	unsigned short b_size;		/* rozmiar bloku */
	unsigned short b_list;		/* typ listy LRU, na której znajduje się ten bufor */
	kdev_t b_dev;			/* numer urządzenia (B_FREE = bufor wolny) */

	atomic_t b_count;		/* liczba korzystających z buforu */
	kdev_t b_rdev;			/* numer rzeczywistego urządzenie */
	unsigned long b_state;		/* mapa bitowa stanu buforu */
	unsigned long b_flushtime;	/* czas kiedy zmodyfikowany bufor powinien zostać zapisany */

	struct buffer_head *b_next_free;/* dowiązania na dwukierunkowych listach */ 
	struct buffer_head *b_prev_free;/* LRU/wolnych buforów */
	struct buffer_head *b_this_page;/* cykliczna lista buforów na jednej stronie */
	struct buffer_head *b_reqnext;	/* kolejka żądań operacji blokowych */

	struct buffer_head **b_pprev;	/* dwukierunkowa lista w tablicy z haszowaniem */
	char *b_data;			/* wskaźnik do bloku danych */
	struct page *b_page;		/* strona, na którą zmapowany jest ten nagłówek */
	void (*b_end_io)(struct buffer_head *bh, int uptodate); /* obsługa zakończenia operacji we/wy  */
 	void *b_private;		/* zarezerwowane dla funkcji b_end_io */

	unsigned long b_rsector;	/* rzeczywista lokacja buforu na dysku (numer sektora) */
	wait_queue_head_t b_wait;    	/* kolejka oczekujących na dostęp do buforu gdy jest zablokowany */

	struct inode *b_inode;		/* struktura i-węzła, do której należy blok buforu */
	struct list_head     b_inode_buffers;	/* dwukierunkowa lista zmodyfikowanyh buforów dla danego i-węzła */
};

Uwaga:
Struktura nagłówka buforu jest tak zorganizowana, by najczęściej używane pola znajdowały się w jednej linii pamięci cache (16 bajtów). Ma to na celu zwiększenie szybkości (szczególnie odczuwalne na procesorach 32-bitowych).

• pierwsze 16 bajtów: do przeszukiwania na listach tablicy z haszowaniem
• drugie 16 bajtów: do przeszukiwania list LRU

* Zmiana w wersji 2.4.7 *

3.1.2 Dokładniejszy opis ważniejszych pól struktury buffer_head

Typ listy LRU

Bity stanu buforu

Określają m.in. do której listy LRU ma trafić bufor.

Nazwa bitu	Znaczenie
BH_Uptodate	1 jeśli bufor odpowiada blokowi na dysku
BH_Dirty	1 jeśli bufor jest zmodyfikowany i musi być zapisany
BH_Lock	1 jeśli bufor jest zablokowany (np. przeznaczony do zapisu)
BH_Req	0 jeśli bufor został unieważniony
BH_Mapped	1 jeśli jest odwzorowany na dysk (tzn. ma odpowiadający mu fizyczny blok)
BH_New	1 jeśli bufor jest nowy i jeszcze nie zapisany
BH_Protected	1 jeśli bufor jest chroniony
BH_PrivateStart	pierwszy wolny bit do prywatnych oznaczeń dla innych celów

* Zmiana w wersji 2.4.7 *

b_flushtime

Podawane jako parametr dla demona bdflush w unii jego parametrów (fs/buffer.c):

union bdflush_param {
  struct {
    ...
    int age_buffer;  /* Czas dla zwykłego buforu, który musi upłynąć zanim zostanie zapisany */
    ...
  } b_un;
  unsigned int data[N_PARAM];
} bdf_prm;

Zadeklarowany przedział dopuszczalnych wartości: [0.01 s - 60 s]

* Zmiana w wersji 2.4.7 *

Funkcja obsługi końca operacji wejścia/wyjścia

Wywoływana jest po zakończeniu asynchronicznej transmisji dyskowej w celu aktualizacji nagłówków buforów dla odczytanych/zapisanych bloków.

3.2 Ustalone parametry ilościowe dotyczące pamięci buforowej

• Liczba buforów rezerwowych (do obsługi asynchronicznych żądań we/wy w celu uniknięcia sytuacji blokady z braku wolnych nagłówków buforów): NR_RESERVED = (10*MAX_BUF_PER_PAGE)

  gdzie:
  MAX_BUF_PER_PAGE = (PAGE_CACHE_SIZE / 512)

• Maksymalna liczba nieużywanych buforów: MAX_UNUSED_BUFFERS = NR_RESERVED+20

3.3 Funkcja haszująca

hashfn(dev, block) = (((dev SHL (bh_hash_shift - 6)) XOR (dev SHL (bh_hash_shift - 9))) XOR ((block SHL (bh_hash_shift - 6)) XOR (block SHR 13) XOR (block SHL (bh_hash_shift - 12))))

dev - numer urządzenia
blok - numer bloku
bh_hash_shift - przesunięcie bitowe obliczane przy inicjalizacji pamięci buforowej
a SHL b - przesunięcie bitów w liczbie a o b pozycji w lewo
a SHR b - przesunięcie bitów w liczbie a o b pozycji w prawo

a odczytanie właściwej pozycji tablicy z haszowaniem odbywa się następująco:

hash(dev, block) = hash_table[(hashfn(HASHDEV(dev), block) AND bh_hash_mask)]

gdzie:
bh_hash_mask jest o 1 jeden mniejsza od rozmiaru tablicy z haszowaniem (obliczanego przy inicjalizacji pamięci buforowej)

* Zmiana w wersji 2.4.7 *

W jądrze 2.2.x funkcja haszująca miała postać:

hashfn(dev, blok) = (((unsigned)(HASHDEV(dev) XOR block)) AND bh_hash_mask)

a odczytanie właściwej pozycji tablicy z haszowaniem odbywało się bezpośrednio:

hash(dev, block) = hash_table[hashfn(dev, block)]

3.4 Inicjalizacja pamięci buforowej

• Tablica z haszowaniem i listy wolnych buforów są tworzone przy starcie systemu w procesie init (init/main.c) za pomocą funkcji: buffer_init() z pliku fs/buffer.c

  Rozmiar hash_table[]

• obecnie wykorzystywana jest tylko część dostępnej ilości stron pamięci fizycznej (wstępnie liczb stron dostępnych jest dzielona przez 2^14 i mnożona przez rozmiar adresu nagłówka buforu)
• rozmiar tablicy hash_table[] jest obliczany następująco:
  

  nr_hash = (ROZMIAR_STRONY * 2^order) / sizeof(struct buffer_head *)

  gdzie:
  order - wykładnik największej potęgi 2 mniejszej od liczby stron pamięci

• pamięć dla tablicy hash_table[] jest rezerwowana przy wykorzystaniu funkcji __get_free_pages()

4. Podsumowanie zmian w jądrze 2.4.7

• Usunięcie określenia wartości opóźnienia zapisu dla bloków specjalnych (w stosunku do 2.2.x)
• Nowa, efektywniejsza funkcja haszująca (w porównaniu z 2.2.x)
• Zwiększenie liczby list LRU (do 4) (w porównaniu z 2.2.x)
• Usunięcie funkcji breada()
• Przyspieszone operacje na listach haszującej, LRU i wolnych buforów, użycie pamięci podręcznej SLAB dla nagłówków buforów
• Usunięcie znacznika czasu odwołania do buforu dla algorytmu LRU z nagłówka buforu (w stosunku do 2.0.x)

5. Zalety i wady pamięci buforowej:

5.1 Zalety:

6. Bibliografia

1. "Podstawy systemów operacyjnych" - A. Silberschatz, J. L. Peterson, P. B. Galvin, WNT 1993
2. "Linux Kernel - Jądro systemu" - M. Beck i inni, MIKOM 1999
3. Pliki źródłowe Linuksa (jądro 2.4.7):
   • include/linux/fs.h - struktury danych, różne deklaracje
   • fs/buffer.c - funkcje obsługi podręcznej pamięci buforowej
   • drivers/block/ll_rw_blk.c - funkcje odczytu i zapisu bloków
   • init/main.c - treść procesu init
4. Opracowania studentów Wydziału Matematyki, Informatyki i Mechaniki UW:
   • Linux: Algorytmy + Struktury danych (2000/2001)
   • Linux Podręcznik (1999/2000)
   • Projekt Lab-Linux (1997/1998)
   • Projekt Linux (1996/1999)