1. Zarządzanie pamięcią
1. Wsparcie sprzętowe na procesorach Intel 386
1. Mechanizm tłumaczenia adresów
2. Pamięci podręczne
2. Struktura pamięci fizycznej
1. Ramki i tablice ramek
2. Wolne ramki
3. Zwalnianie i zajmowanie ramek
3. Pliki wykonywalne
1. Obsługa różnych formatów plików wykonywalnych
2. Format ELF
3. Fork i Exec
4. Segmenty pamięci dzielonej
5. Pliki odwzorowane do pamięci
6. Wirtualna przestrzeń adresowa procesu
7. Przestrzeń adresowa procesu
8. Funkcja brk()
9. Katalogi i tablice stron
10. Stronicowanie na żądanie
1. Odwołanie do strony w pamięci
2. Odwołanie do strony poza pamięcią
3. Wymiana stron
1. Mechanizm postarzania stron
2. Demon kswapd
4. Podręczna pamięć buforowa stron
11. Zarządzanie plikami wymiany i urządzeniami wymiany
12. Pamięć dla jądra

Algorytm buddy - tablica free_area

Algorytm buddy - zajmowanie bloków

Algorytm buddy - zajmowanie i dzielenie bloków

Algorytm buddy - zajmowanie i dzielenie bloków cz.2

Algorytm buddy - zwalnianie i łączenie bloków

Algorytm buddy - zwalnianie i łączenie bloków cz.2

Tak wyglada obraz pamieci w pliku ELF.

• adres wirtualny
• adres liniowy
• segmenty jądra i użytkownika
• dostęp do segmentu użytkownika z jądra:
  • put_user() i get_user()
  • memcpy_tofs() i memcpy_fromfs()
• MMU

• dwupoziomowe przeliczanie adresu
• konwersja 3-poziomowego przeliczania linuxowego na 2-poziomowe przeliczanie dla Intela:
  • prosty trik:    rozmiar PMD = 1
  • pozycja w katalogu stron jako PMD
  • uwzględnienie tego przez operacje mające dostęp do katalogu stron

• 64a9d902(hex) - 0110 0100 1010 1001 1101 1001 0000 0010 (bin)

• index w kat. stron: 0110010010(bin) - 192 (hex) (pierwsze 10 bitów)
• index w tablicy stron: 1010011101(bin) - 29d (hex) (kolejne 10 bitów)
• przesunięcie: 100100000010(bin) - 902 (hex) (ostatnie 12 bitów)

• pozycja w katalogu stron - pgd_t
• dostęp do tej pozycji (makro pgd_val()):
  • pgd_alloc() -
  • pgd_free() -
  • pgd_bad() -
  • pgd_clear() -
  • pgd_none() -
  • pgd_page() -
  • pgd_present() -
  • pgd_offset() -
  • pgd_set() -
  • SET_PAGE_DIR() -

• pozycja w pośrednim katalogu stron - pmd_t
• dostęp do tej pozycji - pmd_val():
  • analogicznie jak do pgd_t oraz:
  • pmd_alloc() i pmd_alloc_kernel()
  • pmd_free() - pmd_free_kernel()
  • pmd_set() - nie zdefiniowany dla i386

• pozycja w tablicy stron - pte_t
• dostęp do tej pozycji (makro pte_val()):
• flagi i atrybuty
• zdefiniowane kombinacje atrybutów - pgprot_t

• Makra pgprot_t:
  • PAGE_NONE
  • PAGE_SHARED
  • PAGE_COPY
  • PAGE_READONLY
  • PAGE_KERNEL


• definiowanie atrybutów ochrony:
  • __P000 do __P111
  • __S000 do __S111
  • _PAGE_NORMAL()
• znaczenie tych atrybutów w architekturze Intela

• mk_pte()
• pte_alloc()
• pte_alloc_kernel()
• pte_free()
• pte_free_kernel()
• pte_clear()
• pte_dirty()
• pte_mkclean()
• pte_mkdirty()
• pte_exec()
• pte_execprotect()
• pte_mkexec()
• pte_mkread()
• pte_mkwrite()

• pte_read()
• pte_write()
• pte_rdprotect()
• pte_wprotect()
• pte_mkold()
• pte_mkyoung()
• pte_young()
• pte_none()
• pte_present()
• pte_page()
• pte_offset()
• pte_modufy()
• set_pte()

Wymagania pamięciowe stawiane systemowi:


• zwiększone wymagania ilościowe - np. wprowadzenie interfejsu graficznego.
• procesy współbieżne - ochrona  danych, większe zużycie pamięci.

Rozwiązania:


• Mechanizm stronicowania - łatwe przeliczanie adresów wirtualnych na fizyczne, skuteczna ochrona danych.
• Mechanizm wymiany - zwalnianie pamięci poprzez usuwanie całych procesów

Ograniczenie:


• Brak możliwości alokacji większego obszaru pamięci niż istniejąca pamięć fizyczna.

Rozwiązanie II


• Stronicowanie na żądanie - mechanizm wymiany stosowany dla poszczególnych stron pamięci procesu

void do_no_page(struct task_struct *task,
                struct vm_areastruct *vma,
                unsigned long adres,
                int write_acces)
   

Możliwe akcje podejmowane przez do_no_page():


• is_present -Strona znajduje się w pamięci (np. jest przydzielona innemu procesowi). Modyfikowane są deskryptory.



• swap_page -Strona znajduje się na urządzeniu wymiany, zostaje zainicjowana transmisja strony do pamięci RAM.



• anonymus_page -Strona nie została jeszcze fizycznie przydzielona. Przydzielana jest nowa strona.



• sig_bus -Nastąpiła próba odwołania się do strony, która nie jest reprezentowana w bieżącym drzewie deskryptorów. Wysyłany jest do procesu sygnał SIGBUS

Modyfikowane zmienne struktury task_struct:


• min_flt określa ile spośród błędów braku strony nie wymagało odwoływania się do dysku.



• maj_flt określa liczbę błędów braku strony wymagających transmisji dyskowej.

Modyfikowane zmienne struktury mm_struct:


• rrs informuje ile stron procesu znajduje się aktualnie w pamięci RAM.

• demon KSWAPD (Kernel Swap Deamon)

Demon budzi się co 1 sekundę i sprawdza stan wolnych zasobów.
Następnie albo próbuje zwolnić częsć zasobów, albo jesli jest
zadowalajaca ilosć to zasypia.
 
• jądro

Jesłi podczas gdy jakis proces poprosi o przydział pamięci, okaże się, że
ilosć wolnych ramek spadła poniżej dolnej wartosci progowej, to jądro
stara się obudzić demona, po to żeby on nad tym popracował :)

Trzy progi wartosci
oznaczające stan wolnych zasobów
(ilosć wolnych ramek pamięci)




• min (48)  wartosć progowa, poniżej jej system próbuje za wszelką cenę zwolnić pamięć, to własnie poniżej tej wartosci, demon kswapd jest budzony przez jądro.

• low  (96)   tu jestemy w tak zwanym stadium "srednim" system ani nie próbuje zwalniać zasobów za wszelką cenę, ani nie jest "zadowolony" z posiadanych wolnych zasobów. Posrednią wartosć wprowadzono w celu rozgraniczenia na dwa stany posrednie z różnym priorytetem zwalniania.

• high (144) górna wartosć progowa, jeli stan zasobów jest większy, to demon po obudzeniu stwierdza, że "wystarczy" i dalej zasypia.

• Priorytet zwalniania mówi demonowi ile ramek pamięci ma postarać się zwolnić zanim znów pójdzie spać

Demon KSWAPD




• metoda: LFU
 
• działanie: wybieramy rodzaj stron do usunięcia:
• prywatne strony procesu
• strony pamięci dzielonej
• strony będące obrazem plików

Demon KSWAPD cd.




• przykład dla stron procesu

 
• szukamy procesu
• ustalamy liczbę ramek do odebrania

 
• szukamy obszaru pamięci wirtualnej

 
• szukamy strony i próbujemy ją zwolnić

Demon KSWAPD cd.

• czy od czasu ostatniego sprawdzania nastapił zapis do strony (DIRTY)

 
• czy strona nie ma przypadkiem aktualnej kopii na dysku

• czy strona była odwiedzana (bit ACCESSED)
• jest to jedyna pozostałoć po tzw. "wieku strony" występującym w poprzednich wersjach systemu, aktualnie sprawdzanie wieku strony jest mechanizmem jednostopniowym (poprzednio dwu-stopniowym), patrzymy tylko czy od ostatniego sprawdzania, strona była "dotykana" jesli nie to wyrzucamy, jesli tak to tylko modyfikujemy w/w bit. W poprzedniej wersji systemu wiek storny był mehanizmem dwustopniowym, każda strona posiadała oprócz w/w bitu, również przyporządkowaną liczbę, która okrelała cile jej wiek. Mechanizm został uproszczony!

Demon KSWAPD cd.

• jeśli na danym poziomie zagnieżdżenia nie uda się znaleźć zasobu do usunięcia, to wracamy na poziom wyżej, i próbujemu "zaatakować" następny zasób, np.:

 

 

jeśli nie udało się zwolnić strony w danym obszarze wirtualnym, i nie ma już następnej, to wchodzimy na poziom o jeden wyższy i próbujemy z następnym obszarem wirtualnym i jego stronami, jeśli to był natomiast ostatni obszar wirtualny danego procesu, to próbujemy zaatakować następny "dobry" proces z tablicy procesów, itd.

Mechanizm wymiany stron
(podsumowanie)

• system stara się zachować pulę wolnych zasobów

 
• zwalniamy ze strategią LFU (najrzadziej używane najpierw)

 
• kontynuujemy szukanie następnych kandydatów od miejsca w którym ostatnio skończylimy (sprawiedliwość, ew. optymalizacja)

• uproszczono mechanizm starzenia się stron (wydajnosć!)

• uproszczono mechanizm budzenia i priorytetów działania demona

• potrzebna strona znajduje sie w pamięci buforowej stron:
  • zwraca stronę z bufora, bez ponownego jej wczytywania


• potrzebna strona nie znajduje się w pamięci buforowej stron:
  • alokowana jest pamięć na stronę
  • strona zostaje sprowadzona z systemu plików
  • jeśli to możliwe, inicjowany jest odczyt następnej strony z tego pliku

Budowa jądra Linuksa 2.2.12 - pamięć dzielona, urządzenia wymiany, wymiana, pamięć dla jądra.

Plan wystąpienia

• Pamięć dzielona w Linuksie
  • Realizacja pamięci dzielonej w modelu pamięci wirtualnej
• Pliki i urządzenia wymiany
  • Dołączenie urządzenia wymiany.
  • Odłączenie urządzenia wymiany.
  • Wybór urządzenia do zrzucenia strony
  • Zapis/odczyt z urządzenia
  • Przydział miejsca na stronę
  • Zwolnienie miejsca na stronę
• Przydział pamięci dla jądra
  • Schemat działania alokatora pamięci z buforowaniem obiektów
    • Cache
    • Tafle
    • Bufory
  • Implementacja w jądrze Linuksa.
    • Struktura kmem_cache_s
    • Struktura kmem_slab_t
    • Struktura kmem_bufctl_s
    • Przydział pamięci
    • Zwalnianie pamięci
    • Uwagi końcowe

Pamięć dzielona w Linuksie

Wstęp czyli zastosowania pamięci dzielonej w systemie Linux :

• w komunikacji międzyprocesowej IPC Systemu V
• stanowi najszybszy sposób wymiany informacji
• w jądrze systemu
• wykonywanie wielu instancji tego samego programu w oparciu o jeden, wspólny segment kodu
• współdzielenie niemodyfikowanych fragmentów segmentu danych przez kopie procesu
• udostępnianie procesom tzw. bibliotek dzielonych

Realizacja pamięci dzielonej w modelu pamięci wirtualnej :

• odmienna specyfika segmentów dzielonych
• inne atrybuty/flagi dla pozycji tablicy stron
• inny algorytm obsługi błędu braku strony
• inny algorytm wymiatania
wymusiła organizację pamięci w oparciu o obszary pamięci wirtualnej
• pola struktury opisującej obszar pamięci wirtualnej, bezpośrednio zaangażowane w zarządzanie segmentami pamięci dzielonej
• utrzymywanie cyklicznej listy dwukierunkowej obszarów, do których odwzorowany został ten sam segment pamięci dzielonej

          struct vm_area_struct* vm_next_share;
          struct vm_area_struct* vm_prev_share;
  

• referencja do deskryptora segmentu dzielonego zamapowanego do danego obszaru pamięci wirtualnej

          unsigned long vm_pte;
  

• ważniejsze pola struktury deskryptora segmentu pamięci dzielonej (struct shmid_ds) wykorzystywane przez mechanizmy zarządzania pamięcią
• tablica stron danego segmentu

          unsigned long* shm_pages
  

• głowa wyżej opisanej dwukierunkowej listy cyklicznej

          struct vm_area_struct* attaches
  

• funkcje na usługach pamięci dzielonej

sys_shmget()

tworzy nowy segment dzielony oraz tworzy strukturę shmid_ds, inicjuje ją i dodaje do globalnej tablicy deskryptorów pamięci dzielonej (shm_segs)
uwaga : na tym etapie nie przydziela się jeszcze stron

sys_shmctl()

m.in. usuwa segment

sys_shmat()

odwzorowuje segment dzielony do pamięci wirtualnej procesu

tworzy i odpowiednio inicjuje obszar pamięci

odmapowuje poprzednie odwzorowanie pod danym adresem

dodaje obszar do pamięci procesu za pomocą shm_map()

sys_shmdt()

działa przeciwnie do sys_shmat()

shm_nopage()

obsługa błędu braku strony - wartość pte właściwą dla rozpatrywanej strony pozyskuje nie z tablicy stron procesu lecz z tablicy shm_pages deskryptora segmentu dzielonego, do którego odwołanie zaskutkowało błedem braku strony

shm_swap()

cykliczne wymiatanie stron pamięci dzielonej realizowane przez kswapd - kandydatów do usunięcia do pamięci drugorzędnej znajduje przeglądając tablice stron w kolejnych deskryptorach segmentów dzielonych

Pliki i urządzenia wymiany

Zarządzanie plikami i urządzeniami wymiany.

System Linux obsługuje dwa rodzaje dyskowych urządzen wymiany:

• urządzenia plikowe - zorganizowane tak jak plik dyskowy, jedna strona w wielu blokach; wolniejszy dostep
• urządzenia blokowe - spójny blok na dysku; szybsza obsługa

Informacja o podłączonych urządzeniach przechowywana w tablicy swap_info o rozmiarze określonym przez stałą MAX_SWAPFILES.
Elementy tablicy są typu:

struct swap_info_struct
{
        unsigned int flags;
        kdev_t swap_device;
        struct dentry * swap_file;         /* i-węzeł urządzenia*/
        unsigned short * swap_map;         /* mapa bajtowa dowiązań*/
        unsigned char * swap_lockmap;      /* mapa bitowa */
        unsigned int lowest_bit;
        unsigned int highest_bit;
        unsigned int cluster_next;
        unsigned int cluster_nr;
        int prio;                          /* priorytet */
        int pages;                         /* ile wolnych stron */
        unsigned long max;
        int next;
}

Informacja o liście priorytetowej:

struct swap_list_t {
        int head;                          /* głowa listy */
        int next;                          /* następny do rozpatrzenia */
}

Dołączenie urządzenia wymiany.

Jako parametr nazwa pliku specjalnego (urządzenia), oraz flagi, które mogą określać priorytet urządzenia, jeśli nie określają - priorytet zmniejszający się z kolejnymi przyłączonymi urządzeniami jest nadawany automatycznie.

Funkcja znajduje miejsce w tablicy swap_info, sprawdza uprawnienia, rodzaj urządzenia, inicjalizuje mapy bitową i bajtową, zwiększa liczbę dostępnego miejsca na urządzeniach wymiany (nr_swap_pages) o liczbę stron dostępnych na tym urządzeniu, na koniec wstawia do listy priorytetowej.

Odłączenie urządzenia wymiany.

int sys_swapoff(const char * specialfile)

Funkcja usuwa urządzenie z listy, ustawia flagę, mowiącą, że nie można pisać. Stara się zwolnić strony zrzucone na to urządzenie, używając funkcji:
int try_to_unuse(unsigned int type)

Jeżeli się uda, zwalnia odpowiednie pole w tablicy swap_info i ustawia flagę, że urządzenie jest nieużywane. Jeżeli się nie uda, wstawia z powrotem do listy i wychodzi z błędem.

Wybór urządzenia do zrzucenia strony

Algorytm jest realizowany przez funkcje:

unsigned long get_swap_page(void)

Funkcja po prostu wybiera zgodnie z priorytetem: najpierw szuka miejsca na urządzeniu wskazywanym przez swap_list.next, jeśli nie znajdzie, to przeszukuje kolejno urządzenia o tym samym priorytecie, następnie zaczyna od początku listy. Kiedy drugi raz zaczyna szukać od początku (swap_list.head ) oznacza to, że nie ma wolnego miejsca i wychodzi z błędem.
Jeśli się powiedzie zwracana liczba ma w sobie zakodowany numer urządzenia i numer ramki na tym urządzeniu.
Wskaźnik swap_list.next jest ustawiany zgodnie z priorytetem.

Zapis/odczyt z urządzenia

• Funkcja rw_swap_page - wywołuje rw_swap_page_base(rw, entry, page, base)

rw

określa czy ma być wykonany odczyt czy zapis

entry

zakodowany numer urządzenia i ramki

page

opis strony

wait

operacja synchroniczna/asynchroniczna

Algorytm zapisu/odczytu

• Zdekoduj numer urządzenia i ramki ze zmiennej entry
• Sprawdz poprawność numeru urządzenia i ramki
• Zablokuj i zwiększ licznika dowiązań do ramki
• Zaznacz, że ramka ma być odblokowana i licznik dowiązań zmniejszony o 1 (operacja asynchroniczna)
• Wykonaj operację (funkcja brw_page)
• Czekaj na zakończenie (operacja synchroniczna)

Przydział miejsca na stronę

• Funkcja scan_swap_map
• Pakiety wielkości 32 ramek (stała SWAP_CLUSTER_MAX)
• Wyszukiwanie wolnej ramki w mapie bajtowej urządzenia
• Przydziel ramki

Przydział miejsca na stronę - przykład

Zwolnienie miejsca na stronę

• Funkcja swap_free(entry)
• Zdekoduj numer urządzenia i ramki (i sprawdź poprawność)
• Zmniejsz licznik dowiązań do ramki
• Jeżeli priorytet aktualnego urządzenia jest mniejszy niż priorytet urządzenia, z którego zwalniano stronę, to aktualne urządzenie staje się pierwszym z listy priorytetowej

Przydział pamięci dla jądra Linuksa w wersji 2.2.12.

• Problem: częste przydzielanie i zwalnianie podobnych obiektów
• Idea: wyeliminowanie inicjalizacji i niszczenia przydzielanych obiektów przez zapamiętywanie stanu początkowego skonstruowanego obiektu.
• Skutek: znaczne przyspieszenie przydziału, ze względu na większy koszt konstrukcji obiektu niż alokacji pamięci dla niego.

Cache

• przydział obiektu: jeśli jest obiekt w cache'u to weź go, wpp przydziel pamięć (fizyczną) i skonstruuj obiekt;
• zwolnienie obiektu: zwróć obiekt do cache'u (bez niszczenia go);
• odzyskanie pamięci (fizycznej): weź jakieś obiekty z cache'u, zniszcz je i zwolnij pamięć (fizyczną);

Tafle (ang. slab).

• częściowe posortowanie listy.
• fizycznie - jedna lub kilka stron pamięci logicznie podzielonych na bloki jednakowego rozmiaru plus struktura zarządzająca taflą oraz lista struktur zarządzających buforami.
• licznik zajętych bloków.
• organizacja tafli w zależności od wielkości buforów: mniejsze lub większe od 1/8 strony.

• trywialny algorytm zwalniania nieużywanej pamięci;
• szybkie, efektywne operacje przydziału i zwalniania pamięci;
• ograniczenie fragmentacji zewnętrznej;
• zminimalizowanie fragmentacji wewnętrznej;

Bufory.

• struktura logiczna reprezentująca obiekty - kawałki spójnej pamięci.
• maksymalny rozmiar standardowego obiektu - 131072

Struktura kmem_cache_s.

• Operacje na cache'u:
  • tworzenie/niszczenie:
  • interfejs od strony procesów (moduły): przydział/zwolnienie obiektu
  • interfejs od strony sprzętu (system): przydział/zwolnienie pamięci fizycznej
  
• Najważniejsze pola:
  • kmem_slab_t *c_freep - wskaźnik do pierwszej wolnej tafli;
  • void (*c_ctor)(void *, kmem_cache_t *, unsigned long) - konstruktor;
  • void (*c_dtor)(void *, kmem_cache_t *, unsigned long) - destruktor;
  • struct kmem_cache_s *c_nextp - wskaźnik do następnego cache'u;
  • kmem_slab_t *c_firstp, *c_lastp - wskaźniki do pierwszej i ostatniej tafli;

Struktura kmem_slab_s.

• dwa rodzaje organizacji tafli:
  • obiekty większe od 1/8 strony:

• obiekty mniejsze od 1/8 strony:

• najważniejsze pola:
  • struct kmem_bufctl_s *s_freep - lista wolnych buforów;
  • struct kmem_bufctl_s *s_index - wskaźnik do listy buforów;
  • unsigned long s_inuse - licznik zajętych buforów;
  • struct kmem_slab_s *s_nextp, *s_prevp - wskaźniki do następnej i poprzedniej tafli na liście (w cache'u);
  • void *s_mem - adres pierwszego buforu w tafli;

Struktura kmem_bufctl_s.

• łączenie buforów wewnątrz tafli
• identyfikacja tafli zawierającej dany bufor
• przechowywanie adresu skojarzonego buforu (obiektu)
• pola (union):
  • struct kmem_bufctl_s *buf_nextp - wskaźnik do następnego kmem_bufctl_s;
  • kmem_slab_t *buf_slabp - tafla buforu;
  • void *buf_objp - adres buforu;
• co struktura zawiera zależy od organizacji danego cache'u i stanu obiektów

Przydział pamięci dla jądra - kmalloc().

1. Wyszukaj cache z cache_sizes dla obiektów o rozmiarach minimalnych większych od żądanego rozmiaru.
2. Zablokuj przerwania.
3. Jeśli wszystkie tafle są zapełnione - idź do (i).
4. Jeśli żądanie dotyczy pamięci z dostępem bezpośrednim - idź do (j).
5. Jeśli w liście tafli nie ma wskaźnika do wolnego obiektu - idź do (h).
6. Odblokuj przerwania.
7. Zakończ się zwracając obliczony wskaźnik do wolnego obiektu.
8. Zaktualizuj wskaźnik do pierwszej tafli z wolnymi obiektami. Idź do (f).
9. Dodaj nową taflę z wolnymi obiektami i idź do (c) (jeśli się to nie powiedzie - wyjdź z błędem).
10. Zwróć taflę z obiektami w pamięci z dostępem bezpośrednim. Idź do (e).

Zwalnianie pamięci - kfree().

1. Jeśli adres zwalnianego wskaźnika jest błędny, to wyjdź z błędem.
2. Znajdź strukturę opisującą bufor (kmem_bufctl_s) z uwzględnieniem miejsca położenia w pamięci (na liście s_index lub bezpośrednio za buforem - sprawdzenie flagi w c_flags).
3. Sprawdź poprawność wywołania przez sprawdzenie flagi s_magic - jeśli jest niewłaściwa, to wyjdź z błędem.
4. Zwolnij pamięć pod wskazanym adresem i zaktualizuj struktury zarządzające pamięcią. Zakończ się sukcesem.

Uwagi końcowe.

• /proc/slabinfo
• odpluskwianie, statystyki
• efektywność
• artykuł Jeffa Bonwicka: www.nuclecu.unam.mx/~miguel/bonwick.ps