5.2.3 Scenariusze dostepu - algorytm getblk

Spis tresci

• Funkcja getblk() i funkcje pomocnicze:
  • refill_free_list(),
  • grow_buffers(),
  • create_buffers(),
  • get_unused_buffer_head(),
  • maybe_shrink_lav_buffers(),
  • shrink_specific_buffers(),
• Bibliografia.

Funkcja getblk()

DEFINICJA: struct buffer_head* getblk(kdev_t dev, int block, int size)
    WYNIK: wskaznik do naglowka bufora w przypadku sukcesu
           NUll wpp.

Algorytm dzialania funkcji getblk().

1. W odpowiedniej kolejce haszujacej szukamy bufora opisanego przez parametry funkcji getblk() tzn. ktorego pola b_dev, b_blocknr, b_size z naglowka bufora sa odpowiednio rowne dev, block, size.
2. Jesli znalezlismy poszukiwany bufor, to jesli nie jest brudny (bit BH_Dirty pola b_state naglowka bufora rowny jest 0) tzn. jego dane sa takie same jak dane zpisane w odpowiadajacym mu bloku fizycznego urzadzenia, to ustawiamy czas zapisu (pole b_flushtime naglowka bufora) na 0. Jesli dodatkowo bufor zawiera aktualne dane (bit BH_Uptodate pola b_state rowny 1) to wstawiamy go na koniec odpowiadajacej mu kolejki lru (najdluzej nieuzywanych buforow) za pomoca funkcji put_last_lru(). Oznaczamy bufor jako dotkniety tzn. ustawiamy bit BH_Touched pola b_state na 1. Nastepnie zwracamy znaleziony bufor konczac funkcje getblk().

   Uwaga. Wszystkie bufory znajdujace sie w kolejkach haszujacych zawieraja aktualne dane. Dlatego bufor znaleziony w kolejce haszujacej i nie bedacy brudnym zawsze zawiera aktualne dane. (Tak mi sie wydaje)

3. Jesli nie znalezlismy poszukiwanego bufora to musimy wziac wolny bufor odpowiedniego rozmiaru i przyporzadkowac go danemu blokowi, czyli:
   • dopoki kolejka buforow wolnych odpowiedniego rozmiaru jest pusta wywolujemy funkcje refill_freelist(). Funkcja ta dostarczy wolne bufory do danej kolejki,
   • sprawdzamy, czy nie pojawil sie bufor odpowiadajacy podanemu blokowi. Jesli tak, to wracamy do punktu 1. Moze sie to zdazyc, poniewaz w czasie wywolania funkcji refill_freelist() jest mozliwosc zasniecia podczas oczekiwania na pewne zdarzenia,
   • bierzemy bufor z kolejki wolnych buforow,
   • wypelniamy odpowiednie pola w naglowku bufora : licznik uzytkownikow (b_count) rowny 1, czas zapisu (b_flushtime) rowny 0, oznaczamy go jako "dotkniety", okreslamy blok, ktoremu bedzie odpowiadal ten bufor tzn. urzadzenie (b_dev) rowne podanemu (dev), numer bloku (b_blocknr) rowny podanemu (block),
   • wstawiamy bufor do odpowiedniej kolejki haszujacej i na koniec odpowiedniej kolejki lru (funkcja insert_into_queues()).
   • zwracamy otrzymany bufor konczac funkcje getblk().

Funkcja refill_freelist().

  DEFINICJA: void refill_freelist(int size)
 

1. Okreslamy zapotrzebowanie na pamiec potrzebna na utworzenie buforow podanego rozmiaru (zmienna needed). Liczba tworzonych buforow podczas jdnego wywolania funkcji refill_freelist() jest podana w bdf_prm.b_un.nrefill.
2. Jesli liczba wolnych stron pamieci (nr_free_pages) jest dwa razy wieksza niz okreslona w zmiennej min_free_pages minimalna liczba wolnych stron i nie utworzylismy jeszcze wystarczajacej liczby buforow (needed >0 ) to wywolujemy funkcje grow_buffers(). Funkcja ta probuje zwiekszyc liczbe buforow podanego rozmiaru Jesli funkcji grow_buffers() udalo sie stworzyc nowe bufory, to zmniejszamy zapotrzebowanie na pamiec (needed) i wracamy do punktu 2.
3. Sprawdzamy czy mamy juz dosyc wolnych buforow (needed <= 0) jesli tak, to konczymy funkcje refill_freelist().
4. Sprawdzamy, czy jest zbyt duzo buforow innych rozmiarow. Jesli tak, to usuwamy je, a na ich miejsce probujemy utworzyc bufory podanego rozmiaru. Jesli mamy ich wystarczajaco duzo, to konczymy funkcje refill_freelist. Wyszukiwaniem zbednych buforow i usuwaniem ich zajmuje sie funkcja maybe_shrink_lav_buffers(), zas tworzeniem nowych funkcja grow_buffers().
5. Teraz bedziemy probowac uzyskac wolne bufory likwidujac uzywane bufory podanego rozmiaru. Najpierw wyznaczamy kandydata dla kazdej niepustej kolejki lru (najdluzej nieuzywanych buforow). Pomijamy przy tym kolejki lru buforow brudnych i dzielonych. Kandydatem nie moze byc bufor, ktory jest brudny, dzielony, wlasnie uzywany, chroniony, niewlasciwego rozmiaru czy zalokowany. Elekcje wygrywa kandydat, ktory najdluzej nie byl uzywany (czas ostatniego uzycia jest wpisany w pole b_lru_time naglowka bufora). Usuwamy go z kolejki lru i haszujacej, nastepnie wstawiamy do kolejki buforow wolnych. Wybieramy nastepnego kandydata dla kolejki, z ktorej wybralismy zwyciezce. Sprawdzamy czy mamy juz dosyc wolnych buforow. Jesli tak, to konczymy funkcje, jesli nie to wracamy do elekcji.
6. Nie uzyskalismy dostatecznej liczby wolnych buforow, nawet korzystajac z listy lru. W takim przypadku probujemy zwiekszyc liczbe wolnych buforow, wywolujac funkcje grow_buffers() jesli tylko liczba wolnych stron pamieci jest o piec wieksza niz minimalna liczba wolnych stron ( min_free_pages). Jesli udalo sie, to wracamy do punktu piatego.
7. Ostatnim krokiem w zdobywaniu wolnych buforow jest wywolanie funkcji grow_buffers() z wiekszym priorytetem, niz do tej pory. Jesli i to zawodzi, to budzimy proces bdflush (zapisuje brudne bufory), a sami zasypiamy czekajac na zakonczenie jego dzialania.
8. Wracamy do punktu piatego.

Funkcja grow_buffers()

    DEFINICJA: int grow_buffers(int pri, int size)
        WYNIK: 1 w przypadku sukcesu
               0 wpp

1. Pobiera wolna strone pamieci, za pomoca funkcji get_free_page(), wywolujac ja z priorytetem podanym w parametrach (pri). Jesli to sie nie uda, to zwraca zero.
2. Wywolujemy funkcje create_buffers(), podajac w parametrach pobrana strone oraz rozmiar bufora. Funkcja ta stworzy nam bufory, ktorych dane beda umieszczane na podanej stronie.
3. Wstawiamy uzyskane bufory do kolejki buforow wolnych i zwracamy 1.

Funkcja create_buffers().

  DEFINICJA: struct buffer_head* create_buffers(unsigned long page, unsigned long size)
      WYNIK: wskaznik do naglowka bufora 
             NULL jesli nie udalo sie stworzyc bufory 

Funkcja get_unused_buffer_head()

  DEFINICJA: buffer_head* get_unused_buffer_head(void)
      WYNIK: wskaznik do naglowka bufora
             NULL jesli nie udalo sie pobrac naglowka bufora

Funkcja maybe_shrink_lav_buffers().

  DEFINICJA: int maybe_shrink_lav_buffers(int size)
      WYNIK: 1 w przypadku sukcesu
             0 wpp

Funkcja shrink_specific_buffers().

  DEFINICJA: int shrink_specific_buffers(unsigned int priority, int size)
      WYNIK: 1 w przypadku sukcesu
             0 wpp

1. Najpierw rozpatrujemy wolne bufory. Bierzemy bufor z kolejki wolnych. Jesli pozostale bufory, ktorych segment danych znajduje sie na tej samej stronie pamieci, sa nieuzywane, to zwalniamy ja i zwracamy jeden.
2. Teraz probujemy zwalniac bufory z kolejnych list lru. Pomijamy przy tym liste buforow dzielonych. Bierzemy kolejno bufory z listy lru zgodnie z kolejnoscia postarzania. Liczba buforow, ktore zbadamy zalezy od licznosci tej listy. Jesli dany bufor jest w stanie dotkniety (BH_Touched), to zmniejszamy wiek bufora, jesli nie, to postarzamy bufor. Wiek bufora jest zapisany w naglowku strony pamieci zawierajacej jego segment danych. Jesli bufor jest uzywany, chroniony lub zalokowany, to bierzemy nastepny. Jesli jest brudny, to zapisujemy go i bierzemy nastepny. Jesli bufor ma wiek rowny zero (wiek strony pamieci) i jesli pozostale bufory, ktorych dane znajduja sie na tej samej stronie, sa nieuzywane, to zwalniamy ja i zwracamy jeden. Jesli nie udalo sie zwolnic strony, to zwracamy zero.

   Uwaga Dzialanie tej funkcji opisalem dla wywolania przez funkcje maybe_shrink_lav_buffers(), czyli z priorytetem (pri) rownym 6.

   ---

   Bibliografia

   1. Pliki zrodlowe Linuxa:
      • fs/buffer.c

   ---

   Autor: Wojciech Poslowski

   ---