Rysunek: Przerwanie braku strony (źródło: Silberschatz, Galvin, Podstawy systemów operacyjnych)
p = współczynnik błędów braku strony, 0 ≤ p ≤ 1.0
p = 0 => nie ma błędów braku strony
p = 1 => każde odwołanie powoduje błąd braku strony
| efektywny czas dostępu = | (1-p) * czas dostępu do pamięci + p * czas obsługi błędu braku strony |
| czas obsługi błędu braku strony = | czas obsługi przerwania + [czas wysłania strony na dysk] + czas sprowadzenia strony z dysku + czas wznowienia obliczeń |
Bit modyfikacji umożliwia zmniejszenie liczby transmisji dyskowych - tylko modyfikowane strony trzeba zapisywać z powrotem na dysk.
Algorytm powinien minimalizować liczbę błędów braku strony.
Ciąg odwołań: ciąg numerów stron, np.
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Algorytm FIFO
3 ramki pamięci => 9 przerwań braku strony
4 ramki pamięci => 10 przerwań braku strony
Anomalia FIFO (Belady'ego); FIFO NIE jest algorytmem stosowym
Algorytm optymalny: usuń stronę, do której najdłużej nie
będzie odwołania
(algorytm stosowy: M(m,r) zawiera się w M(m+1,r))
3 ramki pamięci => 7 przerwań braku strony
4 ramki pamięci => 6 przerwań braku strony
Nierealizowalny w praktyce, stosowany do porównań
Algorytm LRU (ang. Least Recently Used,
najdłużej nieużywany najpierw)
3 ramki pamięci => 10 przerwań braku strony
4 ramki pamięci => 8 przerwań braku strony
Implementacja z licznikiem: z każdą pozycją w tablicy stron jest związany licznik, podczas każdego odwołania zawartość zegara kopiuje się do licznika.
Implementacja ze stosem: numery stron przechowuje się na stosie, po każdym odwołaniu do strony przesuwa się jej numer na wierzchołek stosu.
Algorytmy przybliżające LRU:
Bit odwołania: z każdą stroną związuje się bit odwołania (inicjalnie = 0); w chwili odwołania do strony ustawia się bit na 1; usuwa się stronę z bitem 0; którą?
Algorytm drugiej szansy: przegląda się strony zgodnie z porządkiem FIFO, cyklicznie; gdy bit=0, to stronę można wymienić; gdy bit=1, to zeruje się bit, a stronie daje "drugą szansę" (czas sprowadzenia strony do pamięci := czas bieżący).
Algorytm zegarowy: jak w 2, ale cykliczna lista stron.
Algorytm LFU (ang. Least Frequently Used, najmniej używana najpierw)
Algorytm MFU (ang. Most Frequently Used, najwięcej używana najpierw)
Przydział ramek:
Minimalna liczba ramek zależy od architektury komputera.
Przydział równy: każdy proces dostaje tyle samo.
Przydział proporcjonalny: każdy proces dostaje proporcjonalnie do swojego rozmiaru.
Przydział priorytetowy: proces o wyższym priorytecie może wybrać stronę do usunięcia spośród swoich stron lub stron procesów o niższym priorytecie.
Algorytmy lokalne (wybór strony do usunięcia spośród własnych stron) i globalne (wybór strony do usunięcia sporód wszystkich stron).
Proces jest zajęty głównie przesyłaniem stron z dysku do pamięci i z pamięci na dysk.
Brak wystarczającej liczby stron jest powodem wysokiego współczynnika błędów braku strony:
Wykres zależności wykorzystania procesora od poziomu wieloprogramowości.
Rysunek: Migotanie (źródło: Silberschatz, Galvin, Podstawy systemów operacyjnych)
Zasada lokalności odwołań: w każdej fazie wykonania program korzysta jedynie z drobnej części całego zbioru stron (lokalność czasowa, przestrzenna).
T = parametr => ustalona liczba odwołań do stron.
Jeśli T = nieskończoność, to zbiór roboczy obejmuje wszystkie strony.
Zasada pola roboczego a równoważenie obciążenia
Jeśli są jeszcze wolne ramki => można zainicjować nowy proces.
Jeśli Suma WSi > liczba dostępnych ramek => migotanie => wstrzymanie jednego z procesów.
Jak aproksymować zawartość pola roboczego:
zegar + bit odwołania
Przykład: T = 10 000
zegar generuje przerwanie co 5 000 jednostek czasu,
na każdą stronę przeznacza się w pamięci dwa bity,
z nadejściem przerwania kopiuje się wszystkie bity odwołania, a następnie zeruje,
jeśli jeden z bitów w pamięci = 1, to strona należy do WS.
Sprowadzanie wstępne; OBL (ang. One Block Lookahed)
Wybór rozmiaru strony: fragmentacja, rozmiar tablicy stron, narzut na wejście-wyjście, lokalność
Struktura programu: przykład dostępu do macierzy kwadratowej wierszami vs kolumnami
Restrukturyzacja programu: zwiększenie lokalności odwołań
Blokowanie stron na czas operacji wejścia-wyjścia (przypinanie stron w pamięci)
Zrealizowany po raz pierwszy w systemie Solaris 2.4. Jest dostępna bogata literatura na jego temat:
W Linuksie kod alokatora płytowego znajduje się w plikach źródłowych mm/slab.c i include/linux/slab.h.
Alokator płytowy obsługuje przydział pamięci na potrzeby jądra. Jądro potrzebuje wielu różnych tymczasowych obiektów, takich jak np. struktury dentry, mm_struct, inode, files_struct. Obiekty tymczasowe jądra mogą mieć rozmiary zarówno bardzo małe, jak i bardzo duże, ponadto są często alokowane i często zwalniane, a więc trzeba wykonywać te operacje efektywnie.
Jakie korzyści daje alokator płytowy w porównaniu z tradycyjnymi metodami alokacji pamięci?
Buforując obiekty określonego typu można, w sprzyjających okolicznościach, uniknąć konieczności wywoływania dla nich konstruktora i destruktora.
Zwykle najczęściej używane pola obiektu są umieszczone na początku. Ponadto tradycyjne alokatory przydzielają na obiekt obszar o rozmiarze będącym wielokrotnością potęgi 2, a ponadto wyrównują położenie obiektu w pamięci. Ma to negatywny wpływ na wykorzystanie pamięci podręcznej procesora, w której odwzorowanie adresu do pozycji w pamięci podręcznej odbywa się wg wzoru:
pozycja w pamięci podręcznej = adres % rozmiar pamięci podręcznej
Alokator płytowy niweluje ten problem.
Jeśli alokacja obszaru w pamięci wymaga przeszukiwania list czy struktur rozproszonych w pamięci, to ma to negatywny wpływ na zawartość TLB (alokator zostawia wówczas w TLB duży ślad, ang. footprint).
Tak wygląda struktura pamięci podręcznej alokatora płytowego:
Głównym zadaniem alokatora płytowego w Linuksie jest zmniejszenie liczby odwołań do systemu bliźniaków. Alokator płytowy utrzymuje wiele różnych pamięci podręcznych (ang. cache). Dla często używanych obiektów (takich jak np. files_struct) utrzymuje dedykowaną pamięć podręczną, a dla pozostałych obiektów pewną liczbę ogólnych pamięci podręcznych, po jednej dla obszarów o rozmiarze będącym kolejną potęgą dwójki. W pliku /proc/slabinfo można obejrzeć listę dostępnych pamięci podręcznych alokatora płytowego, liczbę wolnych i liczbę zaalokowanych obiektów w każdej pamięci podręcznej.
Oto dedykowane pamięci podręczne:
/* System wide caches */
extern kmem_cache_t *vm_area_cachep;
extern kmem_cache_t *names_cachep;
extern kmem_cache_t *files_cachep;
extern kmem_cache_t *filp_cachep;
extern kmem_cache_t *fs_cachep;
extern kmem_cache_t *sighand_cachep;
extern kmem_cache_t *bio_cachep;
A to ogólne pamięci podręczne:
/* Size description struct for general caches. */
struct cache_sizes {
size_t cs_size;
kmem_cache_t *cs_cachep;
kmem_cache_t *cs_dmacachep;
};
extern struct cache_sizes malloc_sizes[];
Możliwe rozmiary to 32, 64, 96, 128, ..., 65 536, ..., 33 554 432.
A to przykładowa zawartość /proc/slabinfo. W kolejnych kolumnach znajdują się:
| cache-name | nazwa pamięci podręcznej |
| num-active-obj | liczba obiektów w użyciu |
| total-objs | łączna liczba dostępnych obiektów (także nieużywanych) |
| obj-size | rozmiar obiektu |
| num-active-slabs | liczba płyt zawierających aktywne obiekty |
| total-slabs | łączna liczba płyt |
| num-pages-per-slabs | liczba stron na jedną płytę |
kmem_cache 61 68 112 2 2 1
tcp_open_request 0 40 96 0 1 1
blkdev_requests 128 160 96 4 4 1
dnotify cache 0 0 20 0 0 1
sigqueue 0 29 132 0 1 1
cdev_cache 1881 1888 64 32 32 1
bdev_cache 3 59 64 1 1 1
mnt_cache 11 59 64 1 1 1
inode_cache 83974 83979 512 11997 11997 1
dentry_cache 87337 87360 128 2912 2912 1
dquot 0 0 128 0 0 1
filp 683 690 128 23 23 1
names_cache 0 10 4096 0 10 1
buffer_head 24662 24680 96 617 617 1
mm_struct 38 48 160 2 2 1
vm_area_struct 1899 1920 96 48 48 1
fs_cache 37 59 64 1 1 1
files_cache 37 45 416 5 5 1
signal_act 39 45 1312 13 15 1
size-131072(DMA) 0 0 131072 0 0 32
size-131072 0 0 131072 0 0 32
size-4096(DMA) 0 0 4096 0 0 1
size-4096 24 48 4096 24 48 1
size-128(DMA) 0 0 128 0 0 1
size-128 967 1020 128 34 34 1
size-32(DMA) 0 0 32 0 0 1
size-32 9504 9605 32 85 85 1
Pamięć jest fizycznie alokowana i inicjowana całymi płytami (ang. slab). Każda płyta składa się z jednej lub większej liczby ramek, zawierających zarówno zaalokowane, jak i wolne obiekty.
Alokator płytowy używa trzech struktur danych:
Układ tych struktur w pamięci zależy od rozmiaru obiektów przechowywanych w pamięci podręcznej. W przypadku małych obiektów deskryptory płyty i obiektu są umieszczone NA płycie:
W przypadku dużych obiektów deskryptory płyty i obiektu są umieszczone POZA płytą:
W obrębie jednej pamięci podręcznej trzymane są dowiązania do płyt z obiektami tego samego rozmiaru. Płyty są umieszczone na trzech listach:
Alokator w pierwszej kolejności przydziela obiekty z płyt częściowo zapełnionych, następnie z płyt pustych. Na potrzeby kolejnych żądań alokuje nowe płyty (odwołując się do systemu bliźniaków).
Płyta to ciągły obszar pamięci, do którego można wrzucić pewną liczbę obiektów o konkretnym rozmiarze. Deskryptory płyty mogą być przechowywane wewnątrz płyty (tak dzieje się w przypadku małych obiektów, mniejszych niż 1/8 strony) bądź na zewnątrz (w przypadku dużych obiektów).
struct slab {
struct list_head list;
unsigned long colouroff;
void *s_mem;
unsigned int inuse;
kmem_bufctl_t free;
};
list: lista, do której należy ta płyta
colouroff: kolor tej płyty
s_mem: adres pierwszego obiektu na płycie
inuse: liczba aktywnych obiektów na płycie
free: pole używane do łączenia wolnych obiektów w listę
typedef unsigned int kmem_bufctl_t;
Deskryptor obiektu służy do łączenia obiektów wolnych w listę. Jest on potrzebny tylko dla wolnego obiektu, musi jednak być rozłączny z samym obiektem, gdyż nie chcemy niszczyć poprawnie skonstruowanego obiektu.
Deskryptory obiektów, tak jak deskryptory płyt mogą być przechowywane na dwa sposoby: wewnątrz płyty (dla małych obiektów) bądź na zewnątrz (dla dużych obiektów).
Deskryptor obiektu może być prostą liczbą całkowitą, gdyż do ustalenia pamięci podręcznej i płyty, do której należy obiekt wystarczy dowiązanie do deskryptora ramki zawierającej obiekt.
Wszystkie dowiązania do wolnych obiektów są trzymane w tablicy elementów typu kmem_bufctl_t, która ma tyle pozycji, ile jest obiektów na płycie. Tablica jest trzymana tuż ZA deskryptorem płyty i nie ma do niej bezpośredniego wskaźnika. Jest natomiast dostępna pomocnicza funkcja:
static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
{
return (kmem_bufctl_t *) (slabp + 1);
}
Dostęp do i-tego elementu tablicy odbywa się więc następująco:
slab_bufctl(slabp)[i]
Indeks następnego wolnego obiektu na płycie jest przechowywany w slabp->free.
Inicjowanie płyty polega na wypełnieniu tablicy kmem_bufctl_t kolejnymi indeksami obiektów, zaczynając od 1 i kończąc na znaczniku BUFCTL_END. Do slab_t->free wstawia się 0. Ogólnie, dla wolnego obiektu o indeksie n indeksem następnego wolnego obiektu jest kmem_bufctl_t[n].
Adres pierwszego obiektu jest pamiętany w slabp->s_mem. Jeśli do tego adresu dodamy slabp->free (indeks pierwszego wolnego obiektu) pomnożone przez cachep->objsize (rozmiar obiektu), to otrzymamy adres pierwszego wolnego obiektu na płycie.
Do inicjowania ogólnych pamięci podręcznych służy funkcja:
void __init kmem_cache_init(void)
Do tworzenia dedykowanych pamięci podręcznych służy funkcja:
/**
* kmem_cache_create - Create a cache.
* @name: A string which is used in /proc/slabinfo to identify this cache.
* @size: The size of objects to be created in this cache.
* @align: The required alignment for the objects.
* @flags: SLAB flags
* @ctor: A constructor for the objects.
* @dtor: A destructor for the objects.
*/
struct kmem_cache *
kmem_cache_create (const char *name, size_t size,
size_t align, unsigned long flags,
void (*ctor)(void*, struct kmem_cache *, unsigned long),
void (*dtor)(void*, struct kmem_cache *, unsigned long))
Jeśli podczas tworzenia pamięci podręcznej jest ustawiona flaga SLAB_HWCACHE_ALIGN, to rozmiar obiektu jest wyrównywany do L1_CACHE_BYTES (dla większości architektur równe 32), dzięki czemu obiekty będą wyrównane w sprzętowej pamięci podręcznej. Powoduje to powstanie odstępów między obiektami na płycie.
Funkcja kmalloc służy do przydziału pamięci na potrzeby jądra.
Funkcja najpierw próbuje zaalokować obiekt w częściowo wypełnionej płycie, potem w wolnej płycie. Jeśli zakończy się to niepowodzeniem, to próbuje zaalokować nowe ramki z systemu bliźniaków.
Funkcja kfree służy do zwalniania pamięci przedzielonej na potrzeby jądra. Zwalnianie pustych płyt odbywa się podczas usuwania pamięci podręcznej. To z niej ostatecznie zostanie wywołana funkcja znana nam z systemu bliźniaków funkcja.
Jedna linia sprzętowej pamięci podręcznej odwzorowuje wiele różnych bloków pamięci RAM. Obiekty o tym samym rozmiarze powinno się przechowywać z tym samym przesunięciem względem pamięci podręcznej alokatora. Obiekty mające to samo przesunięcie względem różnych płyt będą z dużym prawdopodobieństwem odwzorowane do tej samej linii sprzętowej pamięci podręcznej. Alokator płytowy stara się zredukować to niekorzystne zjawisko poprzez mechanizm kolorowania płyt: różnym płytom są przypisywane różne kolory, które określają przesunięcie obiektów w ramach płyty.
Obiekty na różnych płytach będą umieszczane z różnym przesunięciem, zależnie od ilości wolnej pamięci. Przesunięcie jest mierzone w jednostkach będących wielokrotnością BYTES_PER_WORD, chyba, że jest ustawiona flaga SLAB_HWCACHE_ALIGN, gdyż wówczas jest wielokrotnością L1_CACHE_BYTES.
Podczas tworzenia pamięci podręcznej liczy się liczbę obiektów, które można umieścić na płycie oraz liczbę niewykorzystanych bajtów. Na ich podstawie wylicza się:
colour: liczbę dostępnych kolorów (przesunięć na różnych płytach),
colour_off: kolejne przesunięcie
Alokator płytowy wykorzystuje do kolorowania płyty niewykorzystane bajty wewnątrz płyty (zmienna left_over w funkcji kmem_cache_create). Płyty o różnych kolorach przechowują pierwszy obiekt płyty na różnych miejscach w pamięci, uwzględniając wymagane wyrównanie obiektu w pamięci oraz kolor płyty. Pierwszy kolor jest oznaczany jako 0, a ostatni (którego wartość znajduje się w polu colour deskryptora pamięci podręcznej) jako left_over/offset. Kolorowanie powoduje przesunięcie części wolnego obszaru płyty z końca na początek.
Różne kolory są po równo rozdzielane pomiędzy płyty określonego typu obiektu. Każda nowo tworzona płyta ma kolor różny od poprzedniej, aż do osiągnięcia maksymalnej liczby dostępnych kolorów.
| Janina Mincer-Daszkiewicz |