5.2.2 Struktura puli buforow
Do spisu tresci tematu 5
5.2.2 Struktura puli buforow.
Spis tresci
Opis struktur
Bibliografia
Pytania i odpowiedzi
Opis struktur
Struktury danych stosowane przy pamieci buforowej maja na celu:
zapewnienie szybkiego znalezienia bufora odwzorowanego w dany blok
(lub stwierdzenia jego braku) - sluza temu kolejki
mieszajace.
znalezienie bufora, do ktorego mozna wczytac nowy blok z dysku - sluzy
do tego lista buforow wolnych
organizacje przeplywu buforow miedzy powyzszymi listami - lista
lru
umozliwienie zwalniania stron pamieci zawierajacych bufory - listy
unused_list i reuse_list oraz tablica next_to_age
Kolejki mieszajace
Dowolny blok w systemie plikow (a takze ewentualny bufor zawierajacy
dane z niego) jest jednoznacznie identyfikowany przez numer urzadzenia,
na ktorym sie znajduje i numer bloku na tym urzadzeniu. I te dwie wartosci
sa argumentami funkcji mieszajacej (w rzeczywistosci makra), zdefiniowanej
nastepujaco:
_hashfn(nr_urzadzenia, nr_bloku)=(nr_urzadzenia XOR numer bloku) mod
nr_hash
Zatem mamy nr_hash kolejek mieszajacych przechowywanych w tablicy hash_table.
Zmienna nr_hash jest zalezna od rozmiaru pamieci i jest inicjowana w funkcji
buffer_init razem
z tablica hash_table. Przyjmuje wartosci od 997 do 65521. Kolejki mieszajace
sa listami prostymi dwukierunkowymi. Wykorzystywane sa w nich skladowe
b_prev i b_next naglowka buforu. Praktycznie
wszystkie odwolania do tablicy mieszajacej sa realizowane poprzez makro
hash(dev,block), zwracajace te liste, ktora moze zawierac dany bufor.
Lista buforow wolnych
Poniewaz Linux dopuszcza rozne rozmiary buforow (od 0.5 do 8 kB), mamy
osobna liste dla kazdego rozmiaru. Kazda z nich jest dwukierunkowa lista
cykliczna, wykorzystujaca skladowe b_next_free i b_prev_free naglowka
buforu. Zmienna free_list jest tablica indeksowana numerami rozmiarow
(szczegoly w pliku
buffer.c). Wszystkie bufory na tych listach nie zawieraja
danych (pole b_dev ustawione na B_FREE).
Listy lru
Aby moc wybrac uzywany bufor do usuniecia, wszystkie bufory z danymi
sa trzymane w tablicy lru_list, porzadkujacej bufory wzgledem czasu ostatniego
uzycia. Deklaracje:
static struct buffer_head * lru_list[NR_LIST]
#define BUF_CLEAN 0 /* Bufory nie nalezace do zadnej z kategorii nizej
*/
#define BUF_UNSHARED 1 /* Bufory, ktore przestaly byc dzielone */
#define BUF_LOCKED 2 /* Bufory przeznaczone do zapisu */
#define BUF_LOCKED1 3 /* Bufory z danymi specjalnymi*/
#define BUF_DIRTY 4 /* Bufory, ktore trzeba bedzie kiedys zapisac */
#define BUF_SHARED 5 /* Bufory dzielone */
#define NR_LIST 6 /* Liczba list w tablicy */
Mamy tutaj szesc rodzajow, na jakie podzielono bufory z danymi. Bufory
dzielone (lista 5) sa to bufory, ktore zostaly odwzorowane na przestrzen
adresowa jakiegos procesu (Linux robi to zamiast kopiowac ich zawartosc
do przestrzeni adresowej procesow). Powod, dla ktorego bufory BUF_UNSHARED
sa rozrozniane od BUF_CLEAN jest mi nie znany. Danymi specjalnymi (lista
3) sa na przyklad i-wezly.
Tablica lru_list pod kazdym z indeksow trzyma kolejke cykliczna buforow
danego rodzaju. Wskaznikami do bufora nastepnego i porzedniego w buforze
sa pola b_next_free i b_prev_free (te same co dla kolejki buforow wolnych,
zatem nie mozna byc w obu kolejkach na raz). Oprocz tego kazdy bufor w
skladowej b_list przechowuje indeks, pod ktorym znajduje sie jego lista
lru. A raczej pod ktorym indeksem sie powinien znajdowac. Bo zauwazmy,
ze lista BUF_LOCKED jest to lista buforow, ktorych zawartosc jest zapisywana
na dysk. Kiedy operacja zapisu sie skonczy, nalezalo by przeniesc bufor
do innej listy. Ale operacje zwiazane z zakonczeniem zapisu sa dokonywane
przez obsluge przerwania, a ta nie moze zmieniac struktur list (bo przerwanie
moze przyjsc w trakcie na przyklad obchodzenia tej listy). Zatem zmieniane
jest tylko pole b_list i kto inny (proces ktory to wykryje) zajmuje sie
przenoszeniem bufora do innej listy. Sluzy do tego funkcja refile_buffer.
Listy lru sa wykorzystywane przez funkcje refill_freelist.
Deklaracja typow
list w pliku include/linux/fs.h
Struktury zwiazane ze stronicowaniem
Jak juz stwierdzilem w opisie naglowka buforu nie jest to glowny temat
mojego zainteresowania, dlatego wspominam o tym tylko pobieznie.
Wiekszosc stron pamieci, nie wylaczajac stron zawierajacych bufory,
podlega algorytmowi starzenia (ang. aging), sluzacemu wybraniu "ofiary"
podlegajacej wywlaszczeniu, gdy potrzeba zwolnic miejsce w pamieci. Ale
strony z buforami wymagaja specyficznego traktowania - oczywiscie absurdem
bylby swapping ich na dysk, zamiast tego nalezy upewnic sie, ze wszystkie
bufory sa wolne i zwolnic pamiec. Starzeniem sie buforow zajmuje sie funkcja
age_buffer, korzystajaca
z tablicy next_to_age. Jest to tablica indeksowana numerami list lru i
zawiera wskazniki do buforow z kazdej z tych list. Kiedy wszystkie bufory
na stronie sie zestarzeja i zostanie podjeta decyzja o wywlaszczeniu, sa
one usuwane ze wszystkich struktur i przenoszone do kolejek unused_list
i reuse_list. Wykorzystywane sa wskazniki next_free i prev_free. W kolejce
unused_list sa bufory, ktore mozna juz utracic, a w reuse_list te, na ktorych
maja zostac jeszcze wykonane operacje zapisu (odczyt sie nie moze zdarzyc).
Pozniej sukcesywnie bufory z reuse_list sa przenoszone do unused_list,
az sie oprozni. Te listy mozna budowac dzieki temu, ze wszystkie bufory
na stronie sa polaczone w liste jednokierunkowa za pomoca wskaznikow b_this_page
z naglowka bufora.
Operacjami na unused_list i reuse_list zajmuja sie nastepujace funkcje
put_unused_buffer_head
- umieszczenie bufora na unused_list
get_unused_buffer_head
- zdjecie bufora z unused_list
get_more_buffer_heads
- ??? (miedzy innymi przydzielenie nowej strony na bufory)
recover_reusable_buffer_heads
- przenosi bufory z reuse_list do unused_list
free_async_buffers
- przenosi wszystkie bufory z danej strony do reuse_list
Bibliografia
Pliki zrodlowe:
include/linux/fs.h - deklaracje
struktury buffer_head i typow kolejek lru
fs/buffer.c - wszystkie opisane
tu funkcje
Pytania i odpowiedzi
Jakie rozwiazania programistyczne uwazam za najciekawsze?
Listy lru. Najpierw pracowicie (i nie
do konca skutecznie - patrz pole b_list) dzieli sie bufory na szesc list,
zeby potem i tak przegladac wszystkie tak "na wszelki wypadek",
na przyklad w funkcji sync_buffers
(tam to nawet sa dwa okrazenia po kazdej liscie).
Jakie ograniczenia systemowe zauwazylem?
Zadnych - pamiec na bufory jest przydzielana dynamicznie i system
jest w stanie wykorzystac tyle, ile sie mu przydzieli.
Autor:Tadeusz Kopec
Wyszukiwarka
Podobne podstrony:
Stan cywilny, wyk struktura ludnosci wg 5 strElementy struktury organizacyjnej i zarządzanie projektowaniem organizacjiElementy składowe i struktura robotów cz 1plan2010 12 struktura pmsElementy składowe i struktura robotów cz 2Klasyfikacja struktur organizacyjnychStruktura SejmuStruktury Sił Zbrojnych BiałorusiKomórki macierzyste tkanek zęba i możliwości odtwarzania struktur zęba2 STRUKTURAfinkcje i struktura rodzinyCHRAPEK,podstawy robotyki, elementy sk?owe i struktura robotówwięcej podobnych podstron