Gestione della memoria fisica

L'allocazione a blocchi di pagine contigue si basa sul seguente meccanismo.

La memoria è suddivisa in grandi blocchi di pagine contigue, la cui dimensione è una potenza di detta ordine del blocco. Per ogni ordine esiste una lista che collega tutti i blocchi di quell'ordine. Le richieste di allocazione indicano l'ordine del blocco che desiderano.

Se un blocco richiesto è disponibile questo viene allocato, altrimenti è diviso in . I due nuovi blocchi sono detti buddies l'uno dell'altro, e questa relazione è conservata dalle strutture dati utilizzate per l'allocazione.

Quando un blocco viene liberato il suo buddy viene analizzato e, se è libero, i due vengono riunificati, ricreando un blocco più grande.

Fino a quando la quantità di RAM libera è sufficientemente grande Linux alloca la memoria senza svolgere particolari controlli. La memoria destinata ai processi viene rilasciata quando un processo termina, e la memoria destinata alle disk cache cresce sempre perché non esiste un criterio per stabilire se un dato su un disco non verrà più utilizzato.

Quando la quantità di memoria scende sotto un livello critico interviene PFRA (Page Frame Reclaiming Algorithm), il cui obiettivo è riportare il numero di pagine libere ad un livello di dimensione al minimo maxFree.

Il meccanismo utilizzato da PFRA per scegliere quali pagine liberare si basa su LRU, cioè sulla scelta delle pagine non utilizzate da più tempo.

Definiamo freePages come il numero di pagine di memoria fisiche libere in un certo istante, requiredPages come il numero di pagine che vengono richieste per una certa attività da parte di un processo, minFree come il numero minimo di pagine libere sotto il quale non si vorrebbe scendere, e maxFree come il numero di pagine libere al quale PFRA tenta di riportare freePages.

Il PFRA può essere invocato direttamente da parte di un processo che richiede requiredPages di memoria se .

È inoltre invocato periodicamente tramite kswapd, una funzione attivata periodicamente dal SO che invoca PFRA se .

Il PFRA determina il numero di pagine da liberare con l'algoritmo:

Esistono due liste globali, dette Least Recently Used List (LRU List) che collegano tutte le pagine appartenenti ai processi:

• Active list: contiene tutte le pagine che sono state accedute recentemente e non possono essere scaricate.
• Inactive list: contiene le pagine inattive da molto tempo che sono quindi candidate per essere scaricate.

Entrambe le liste tengono le pagine in ordine di invecchiamento, tramite spostamento delle pagine da una lista all'altra per tenere conto degli accessi a memoria.

Dato che l'x64 non tiene traccia del numero di accessi alla memoria, Linux realizza un'approssimazione basata sul bit di accesso A presente nella PTE della pagina, che viene posto a da x64 ogni volta che la pagina viene acceduta, e viene azzerato periodicamente dal sistema operativo.

Ad ogni pagina viene inoltre associato un flag ref, oltre al bit di accesso A settato dall'hardware. Questo serve a raddoppiare il numero di accessi necessari per spostare una pagina da una lista all'altra.

Definiamo un'algoritmo semplificato per vedere come si spostano le due pagine:

Per le pagine nell'active list, se azzera , e se sposta P in testa alla active list, altrimenti pone a . Viceversa se , se lo pone a , e se sposta P in testa alla inactive list con .

Per le pagine nell'inactive list (escluse le pagine precedentemente spostate), se azzera , e se sposta P in coda alla active list con , altrimenti pone a . Viceversa se , se lo pone a , e se sposta P in coda alla inactive list.

Per quanto riguarda lo scaricamento prima si scaricano le pagine appartenenti alla page cache non più utilizzate da nessun processo, in ordine di NPF. Successivamente si parte dalla coda della lista inactive, tenendo conto della eventuale condivisione delle pagine. Una pagina virtuale è ritenuta scaricabile solo se tutte le pagine condivise sono nella inactive list in posizioni successive.

È necessario che sia disponibile una Swap Area sul disco, e pertanto esiste lo Swap File, una sequenza di Page slots, ognuna di dimensioni pari ad una pagina, identificata da un numero (SWPN).

Ogni swap area è identificata da un descrittore, che contiene un contatore per ogni page slot (swap_map_counter), che indica il numero di pagine virtuali condivise dalla pagina fisica copiata nel Page Slot.

Per ogni pagina da scaricare swap_out si determina, in base al dirty bit della pagina se salvarla su disco. Se questa è mappata su file e shared si salva su file, se invece è anonima si salva nella swap area.

Una pagina fisica condivisa è dirty se il suo descrittore è marcato D a seguito di un TLB flush, oppure una delle pagine virtuali condivise sulla stessa pagina fisica è contenuta nel TLB ed è marcata dirty.

Quando una pagina viene ricaricata con lo swap_in in Linux non cancella la pagina dalla swap area, che rappresenta una backing store per quella pagina. L'informazione è mantenuta nella swap cache, cioè l'insieme delle pagine che sono state rilette dalla swap area e non sono state modificate, assieme ad alcune strutture ausiliarie che permettono di gestirla come se tali pagine fossero mappate sulla swap area.

Consideriamo le pagine anonime e private: quando si esegue uno swap_in la pagina viene copiata in memoria fisica, la copia nella swap area non viene eliminata, la pagina letta in memoria è marcata in sola lettura. Nella swap cache index viene inserito un descrittore che contiene i riferimenti alla pagina fisica e al page slot. Se la pagina fisica viene solo letta, quando la pagina viene nuovamente scaricata non viene riscritta su disco, ma se viene scritta, si verifica un page fault e la pagina diventa private non appartiene più alla swap area.

Per quanto riguarda le liste LRU il comportamento è come segue:

• La NPV che è stata letta o scritta, cioè quella che ha causato lo swap_in, viene inserita in testa alla active con .
• Eventuali altre NPV condivise all'interno della stessa pagina vengono poste in coda alla inactive con .

In sistemi molto carichi il PFRA può non riuscire a risolvere la situazione. In tal caso come estrema ratio deve invocare il OOMK, che seleziona un processo e lo elimina.

La scelta del processo da eliminare è fatta in base ai seguenti criteri:

• Molte pagine occupate.
• Poco lavoro svolto.
• Priorità bassa.
• Senza privilegi di root.
• Non gestisca componenti hardware.