Rimpiazzo della pagina

Preveniamo la "over allocation" (allocazione eccessiva) della memoria andando a modificare la routine del page-fault in modo da includere un rimpiazzo della pagina.

La pagina uscente deve essere riscritta in backing store (memoria di massa); si può però utilizzare un bit di modifica in modo da ridurre i tempi.

Il tempo per l'operazione di swap si divide in tempo di swap out e tempo di swap in; se la pagina che esce, è una pagina non modificata rispetto a quando è entrata, sul disco è presente la stessa pagina presente in memoria, quindi è inutile salvarla nuovamente.

Quindi, posso tenere traccia delle pagine modificate grazie ad un dirty modify bit che mi dice se la pagina è stata modificata, andando a salvare solo le pagine modificate.

1. Trovare la locazione della pagina sul disco

2. Trovare un frame libero, se presente;

   1. se è presente un frame libero, utilizzarlo

   2. Se non c'è un frame libero, usare un algoritmo di rimpiazzo di pagine per selezionare un frame vittima

      1. scrivere il frame vittima sul disco solo se dirty (modificato).

3. Portare la pagina desiderata nel frame appena liberato (o libero già da prima), aggiornare la pagina e la tabella dei frames.

4. Riprendere il processo riavviando l'istruzione che ha causato la trap.

Per ottenere le migliori prestazioni possibili dovrei essere in grado di sapere a priori quali saranno le pagine che mi serviranno, in modo da caricarle nel momento giusto senza rallentamenti.

Se ad esempio so che una pagina mi servirà tra non molto tempo, di certo non la sposto sul disco per caricarne una nuova, ma ne sceglierò un'altra che non mi servirà per un po' di tempo.

Nel momento in cui aumenta il numero di frames a disposizione del processo, il numero di page fault si riduce. Questo è ragionevole, siccome minore è lo spazio a disposizione del processo (dove poter caricare le proprie pagine) più aumenta la probabilità di page fault (ovvero che qualche pagina non sia già presente in memoria).

Se aumento lo spazio a disposizione in RAM fisica il numero di page fault si riduce; il SO tende ad "accontentare" i processi che verificano troppi page fault, in modo da concedergli più frames.

Un algoritmo FIFO prende e sceglie come vittima la pagina caricata in memoria da più tempo. Per il semplice motivo che la pagina è in memoria da molto tempo, essa viene scelta per essere spostata sul disco.

Non esiste alcuna garanzia che questa pagina fosse la pagina giusta da togliere, infatti questa pagina potrebbe essere una pagina molto importante del programma, dove potrebbe, ad esempio, risiedere lo stack.

Questo sistema non è assolutamente adatto.

L'altro grande problema di questo algoritmo è il seguente:

se fornisco ad un processo, invece di 3, 4 frames, il tasso di page fault, invece di diminuire (come dovrebbe), aumenta! Questa anomalia viene detta anomalia di Belady, ed in pratica è dovuta all'utiizzo dell'algoritmo fifo, ed in pratica si verifica un picco di page fault, ovvero con l'aumento di frames, aumentano anche i page fault; inevitabilmente con un aumento ulteriore dei frames questo picco si risolve.

Questa anomalia da particolarmente fastidio, perchè impedisce al SO di reagire ad un tasso di page fault elevato.

Per ridurre il più possibile il tasso di page fault dovremmo utilizzare un algoritmo ottimale, ovvero togliere dalla RAM la pagina che non servirà per più tempo, ma ovviamente non possiamo sapere qual è questa pagina.

Ovviamente questo tipo di algoritmo è solo "immaginario".

LRU - pagina meno utilizzata recentemente: non sapendo cosa potrà succedere nel futuro, l'algoritmo tenta di utilizzare ciò che è successo nel passato:

l'algoritmo deduce dal fatto che una pagina non viene utilizzata da tanto tempo per scegliere la vittima da spostare sul disco.

Questo algoritmo sembra simile a quello FIFO, ma c'è una sostanziale differenza: questo algoritmo sposta la pagina meno utilizzata recentemente (quella che non uso da più tempo), mentre il FIFO spostava la pagina presente in RAM da più tempo.

Il meccanismo di scelta della vittima, è hardware, e non software.

Il problema è che anche in questo caso, l'algoritmo LRU è troppo complicato da implementare.

Se infatti volessi scegliere la vittima con precisione sarei costretto, in hardware, di tenere traccia di tutti gli accessi in modo da avere una classifica ordinata dalla pagina utilizzata da più tempo a meno tempo, aggiornando la classifica ogni volta che effettuo un accesso in memoria.

Quello che accade nella realtà non è una scelta completamente casuale (della vittima), ma utilizzare degli algorittmi LRU approssimati.

Per realizzare questo tipo di algoritmo, vengono utilizzati i bit di riferimento;

Questi sono dei bit che sistematicamente, quando scatta il timer di sistema, vengono azzerati. Ogni volta che i bit di riferimento vengono azzerati, la prossima volta che entrerà in funzione il SO, troverà dei bit di riferimento alti SOLO per le pagine che sono state utilizzate.

In questo modo è possibile capire quali pagine, nell'ultimo intervallo di tempo, sono state utilizzate maggiormente.

Su questo meccanismo si basa l'algoritmo che la maggior parte dei SO utilizzano, detto algoritmo della seconda chance, o algoritmo dell'orologio:

In pratica c'è un"indicatore" che ci dice quale pagina deve essere spostata sul disco; nel momento in cui si verifica un page fault avviene il seguente meccanismo:

1. Se il bit di riferimento della pagina è basso (0), la pagina viene scelta per essere spostata sul disco.

2. Se il bit di riferimento della pagina è alto (1):

   1. il bit di riferimento viene posto a zero, lasciando la pagina in RAM

   2. Se al prossimo passaggio la pagina viene trovata con il bit di riferimento basso (0) viene spostata sul disco.

Questo algoritmo è detto "della seconda possibilità" perchè nel momento in cui per una pagina è giunto il momento di essere spostata sul disco, ma è stata utilizzata di recente, le si da una seconda possibilità azzerando il bit di riferimento.

Se alla seconda passata il bit verrà trovato basso, la pagina verrà spostata definitivamente.

una versione migliorata di questo algoritmo potrebbe essere quella dove la vittima viene scelta non solo rispetto a quanto è stata usata ultimamente (bit di riferimento == 0), ma anche se essa è una pagina che non è stata modificata, in modo da non dover nemmeno effettuare lo swap out, e quindi rimuovendola semplicemente dalla memoria.

🏁 05-26 00:22

Potrebbe accadere che la pagina appena spostata sul disco possa riservirmi immediatamente dopo.

Si può pensare ad una posizione "intermedia", che funzioni come un "cestino" dove le pagine "eliminate" vengono poste temporaneamente primad di essere definitivamente spostate su disco.

Questa soluzione richiede una maggiore quantità di memoria, ma offre prestazioni migliori.

Qual è il numero di frames che va assegnato ad ogni processo?

Ogni processo ha bisogno di un numero minimo di frames. Ad esempio, il vecchio IBM 370 ha la possibilità , con un'unica istruzione chiamata SS MOVE, di generare 6 possibili page fault!

• Istruzione è di 6 bytes, potrebbe essere a cavallo di 2 pagine

• 2 pagine per il campo di partenza

• 2 pagine per il campo di destinazione

Se, ad un sistema del genere, vengono concessi meno di 6 frames c'è il rischio che l'istruzione generi sempre dei page fault, senza mai riuscire ad essere eseguita.

Questo è il motivo per cui ogni processo ha bisogno di un numero minimo di frames.

Il numero massimo dipende sempre dalla memoria disponibile, ma ci sono delle guidelines:

• Allocazione fissa: ovvero sempre lo stesso numero di frames per ogni processo

• Allocazione a priorità

Divido il numero di frames a disposizione per il numero di processi, dando un numero uguale di frames per ogni processo.

L'evidente problema di questo metodo è che alcuni processi avranno uno spazio indirizzi molto piccolo, ed altri con uno spazio indirizzi molto grande.

Simile all'allocazione fissa, dove divido in frames la memoria disponibile; in questo caso, però, i vari frames vengono mappati sui processi a seconda della dimensione del processo: i processi **più grandi **riceveranno un maggior numero di frames.

• Rimpiazzo globale: il processo seleziona un frame di rimpiazzo dall'insieme di tutti i frames; un processo può ricevere un frame da un altro.

  • Il tempo di esecuzione del processo può essere molto vario

  • Ha un throughput maggiore, quindi più comune

• Rimpiazzo locale: ogni processo seleziona solo dal proprio insieme di frames allocati.

  • La performance per-processo è più affidabile

  • Possibilmente la memoria viene "poco utilizzata".

Se c'è un processo avente troppo pochi frames a disposizione, la probabilità di page fault che si verificheranno per quel processo sarà molto alta.

Di conseguenza possiamo definire il trashing come un processo impegnato a scambiare pagine tra RAM e disco.

Questo fenomeno va ad intaccare anche gli altri processi, proprio perchè effettuando continuamente degli scambi di pagine da RAM a disco, terà sempre occupato il disco.

Questa situazione porta ad una bassa percentuale di CPU utilizzata, che il sistem potrebbe vedere come fattore positivo, e lanciare un altro processo. Questo è disastroso, proprio perchè ci sarà ancora più scarsità di frames per accontentare il processo che sta andando in trashing.

Questo fenomeno è particolarmente "pericoloso" nei sistemi batch, ovvero quei sistemi dove l'interazione unamana è quasi inesistente, ed il sistema si occupa di tutto.

I sistemi batch, decidono di lanciare processi nel momento in cui la CPU è sottoutilizzata, e per questo motivo questi sono i sistemi più soggetti a questo fenomeno.

Sistemi come Mac OS o Windows non soffrono di questo problema, per via del fatto che è l'utente a scegliere il programma (e quindi processi) da lanciare.

Solitamente si verifica perchè un processo utilizza troppe pagine.

Il trucco risiede nel riuscire ad assegnare al processo un numero di frame che lo "accontenti" durante la durata di tutta la sua vita. Dobbiamo quindi cercare di capire quale sarà il numero minimo di frames che gli serve affinchè non inizi a generare page faults.

Il concetto è iniziare a dare ad un processo un certo numero di pagine, nel momento in cui esso viene avviato, in modo ch non abbia dei page fault immediatamente.

Spesso la pagina è a dimensione fissa per un certo processore; solitamente le pagine sono di grandezza pari alle potenze di 2.

Nel tempo (storicamente) con l'aumento della dimensione della memoria fisica (RAM) è andata aumentando anche la dimensione delle pagine.

Il TLB contiene pochi entry, più la pagina è grande, più il TLB (giustamente) riuscirà a coprire una porzione maggiore della memoria.

Se un programma ha una struttura che gli permette di occupare spazio in memoria in locazioni più o meno consegutive, il numero di page fault diminuisce; questo succede perchè abbiamo una maggiore probabilità di trovare dati che ci interessano in una singola pagina.

Un programma scritto male inevitabilmente sarà costretto ad effettuare un numero di page fault elevatissimo; Bisogna quindi accedere alla memoria ad indirizzi vicini tra loro.

E' necessario, a volte, bloccare delle pagine in memoria.

Questo perchè potrebbero contenere un buffer dal quale sta arrivando della data da unità I/O, quindi quelle pagine devono essere bloccate in RAM.

Per quanto riguarda la sicurezza, supponiamo di avere un programma che gestisce informazioni mantenute criptate; se il frame dove vengono mantenute in chiaro queste informazioni viene assegnato ad un altro processo senza che venga azzerato (come normalmente dovrebbe accadere), quel processo può leggere i dati in chiaro. I programmi che gestiscono informazioni assolutamente private, sono costretti a bloccare le pagine segnalando al SO di non spostare le pagine.

FINE CAPITOLO 10

🏁 05-26 01:00

Un File è uno spazio indirizzi logico continuo; in un file sono presenti dei dati che possono essere sotto forma numerica, carattere (usando la stessa codifica binaria per le variabili usate nella CPU).

Infatti è molto diverso scrivere "3.14" come caratteri e scrivere "3.14" come floating point.

In un file potrebbe essere presente un programma, nei vari formati:

• Sorgente

• Oggetto

• Eseguibile

In generale un file è un oggetto astratto i cui contenuti sono definiti dal creatore; solo il creatore del file, infatti, è a conoscenza di quello che è presente all'internod del file.

associati ad un file possono essere presenti una serie di informazioni:

• Nome in chiaro del file, che è l'unica informazione del file mantenuta in human readable, ovvero il nome del file, leggibile da un umano, che internamente è molto più astratto.

• Identificatore è diverso per ogni file che lo identifica univocamente.

• Tipo alcuni sistemi antichi prevedevano una serie di tipi di file predefiniti. Ai nostri giorni i SO continuano a vedere i file come una sequenza di byte, successivamente a seconda dell'estensione il SO capisce che tipo di file si ritrova a dover gestire. Una volta capito che tipo di file si tratta, il SO lo manda al gestore adatto (ad esempio .txt si apre un editor di testo).

• Posizione - locazione ci dice dove il file è locato nel disco, in modo da permettere al SO di accedere alla locazione di memoria dove il file è situato.

• Grandezza, ovvero la grandezza corrente del file.

• Informazioni di protezione, ovvero delle informazioni che consentono di evitare che il file venga manipolato, modificato da utenti che non sono autorizzati.

• Tempo data ed identificazione utente

Tutte queste informazioni sono presenti nel contenuto della struttura di directory; esiste una directory che non è altro un contenitore contenente tutte queste informazioni.

La posizione di queste informazioni varia da SO a SO, ma in ogni caso esse devono essere presenti.

Quando leggiamo: Grandezza: 100 bytes (115 KB sul disco) cosa vuol dire?

Fondamentalmente lo spazio sul disco viene allocato a blocchi, che nella loro grandezza minima sono di 512bytes. Questo significa che c'è un minimo di frammentazione interna, e quindi viene assegnato più spazio di quello necessario.

Sui files si ragiona in termini di dato astratto, nel senso che sono state definite le operazioni indipendentemente da come esse vengono implementate.

• Create

• Write - Alla posizione del puntatore write

• Read - Alla posizione del puntatore read

• Riposizionare tra il file

• Delete

• Truncate

• Open(Fi)

• Close(Fi)

La lettura e scrittura avvengono sempre a partire dalla posizione corrente all'interno del file; il SO gestisce una posizione corrente all'interno del file, che è la posizione alla quale avverrà la prossima lettura o scrittura.

Questo ci permette, quando leggiamo/scriviamo sequenzialmente, di dire che la prossima volta che si andrà a leggere/scrivere, non sarà da capo, ma nel punto immediatamente successivo.

Il puntatore all'interno del file, viene gestito automaticamente dal SO.

Questo metodo funziona bene nel momento in cui la lettura/scrittura è sequenziale, ma cosa succede quando voglio accedere al file in una posizione random?

Il read e write continua a funzionare allo stesso modo, ma si riposiziona all'interno del file, spostando semplicemente il puntatore.

Quindi, l'operazione di seek (ricerca) significa spostare il puntatore in una certa posizione all'interno del file.

E' un'operazione che consente, dato un nome simbolico del file, di individuare il file, e predisporre il tutto per l'accesso.

Questo vuol dire che da quel momento il file viene reso noto all'interno del processo che lo ha richiesto, e ci sarà quindi un puntatore che verrà avanzato ad ogni lettura e scrittura.

Elimina il procedimento che elimina il file dalle tabelle del processo, e se ci sono dei buffer, trasferisce il tutto.

Questa operazione ci assicura che tutto ciò che è presente in un buffer non ancora trasferito verso il disco, venga iniziato ad essere spostato sul disco (l'operazione non è immediata).

Il SO utilizza una tabella dei file aperti per tenere traccia dei files aperti (meglio di così non si poteva).

Questa tabella consente di accedere al puntatore all'interno del file che corrisponde alla posizione corrente all'interno del file, utilizzando delle operazioni di lettura/scrittura.

Supponiamo di aver aggiunto ad un file word un'immagine. Se proviamo ad eliminare l'immagine dal disco, il SO ci consente l'operazione, ma il file non viene realmente eliminato finchè il processo non sarà terminato.

Se ci sono effettive aperture, il SO rimuove il file dalla tabella dei file aperti, solo nel momento in cui non ci sono più aperture.

Questa è un'aggiunta relativamente recente, infatti i primi sistemi UNIX non permettevano il Locking dei file.

Non bisogna pensare al fatto che un file venga aperto da più processi come una cosa negativa; che succede quando un processo vuole scrivere su un file aperto anched altri processi?

Abbiamo il solito problema in un contesto leggermente diverso: se più processi tentano di scrivere contemporaneamente sullo stesso file, abbiamo un gran problema; se diversi processi, che hanno diversi puntatori nel file, scrivono sullo stesso file, scrivono in due punti diversi, cosa che non genererebbe particolari problemi.

Se voglio assicurarmi che un solo processo alla volta scriva sullo stesso file, devo richiedere un lock su quel dato file:

Questo significa dire a sistema operativo che quel dato processo sta lavorando su quel dato file, e nessun altro processo deve accedervi mentre quel processo vi scrive.

In alcuni casi è possibile anche avere un lock shared, ovvero bloccare solo una sezione del file, e quindi permettere ad altri processi di lavorare sulle restanti porzioni del file.

I lock possono essere di due tipi:

• Mandatorio (obbligatorio) ovvero l'accesso è negato assolutamente.

• Opzionale in questo caso viene semplicemente "consigliato" al processo di non accedervi, ma la decisione spetta solo al processo.

Nella maggioranza dei casi, i files non hanno una struttura, nel senso che sono semplicemente una sequenza di word o byte che vengono interpretati dal programma che gestisce quel tipo di file (estensione).

In altri casi i files potrebbero avere una struttura complessa, gestibile da caratteri di controllo in modo da costruire un file più complesso.

L'accesso sequenziale ad un file, significa avere un puntatore che punta alla posizione corrente, le letture/scritture avvengono da quella posizione in poi;

Qualora volessi tornare all'inizio del file, invece di effettuare una seek() (ricerca), è possibile effettuare un rewind che mi consente di spostarmi all'inizio del file in modo sequenziale (senza salti).

Accesso sequenziale

read next
write next
reset

Accesso diretto

read n
write n
position to n
    read next
    write next
rewrite n

Nell'accesso diretto, bisogna posizionarsi in una posizione precisa con un'operazione di seek() e poi (opzionalmente) effettuare una lettura/scrittura sequenziale

La directory contiene informazioni relative a files, e storicamente la struttura delle directory era fatta in questo modo:

C'era un'unica struttura di directory in cui erano presenti tutti i files.

Nella realtà, già dall'MS-DOS la struttura del file system è ad albero, che permette di avere files aventi lo stesso nome, purchè in directory diverse, oltre a poter separare i documenti dei vari utenti ecc.

Fondamentalmente un disco può essere visto come un unico volume, oppure in maniera partizionata.

Il partizionamento è particolarmente utilizzato dai produttori, anche per motivi di recovery, dove su un'unica unità fisica sono creati più volumi logici. Associata ad un disco, viene associata una tabella delle partizioni che individua la posizione di inzio e fine, di unità che logicamente sono separate.

Il sistema vede queste partizioni come tante unità logiche separate, ma in realtà sono tutte sullo steso disco.

Storicamente il vantaggio delle partizioni risiede in una migliore protezione e migliore backup: Possiamo ad esempio creare una partizione in cui saranno presenti solo programmi di sistema, renderla solo lettura, in modo che non possa essere alterata o distrutta.

Inoltre, per effettuare un backup, è difficile effettuare il backup per files utenti tra un unico enorme disco; conviene maggiormente creare una partizione di files utente, in modo da effettuare il backup dell'intera partizione.

FINE LEZIONE 12