|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.SO-Mod4-3-Lez4 History
Hide minor edits - Show changes to output
Changed lines 42-43 from:
to:
Il '''working set''' è l'insieme delle pagine di lavoro, e la sua finestra scorre sulla stringa di riferimento delle pagine. Changed lines 45-56 from:
!!!!Sostituzione della pagina (1) to:
!!!!Prevenzione del thrashing (4)
Per garantire di non entrare mai in situazione di thrashing, bisogna fare in modo che la sommatoria dei frame allocati ai vari processi caricati nel sistema sia sempre minore dei frame totali. In caso contrario, viene selezionato un processo vittima p'_v_' che viene scaricato.
Il limite di questa strategia è che dovrei conoscere a priori la stringa di riferimento delle pagine su cui calcolare l'ampiezza del WS, ma questo già sappiamo che non è spesso possibile. Si può però approssimare la dimensione della finestra del working set, ad esempio utilizzando la tecnica di ''page-fault frequency'' che vediamo subito ora.
!!!!Prevenzione del thrashing (5)
Con la '''page-fault frequency''' (frequenza delle mancanze di pagina) aggiusto dinamicamente il numero di frame assegnato ai processi in base alla situazione attuale, ovvero alla frequenza con cui ho page fault.
Si fissa così un limite superiore e uno inferiore nel tasso di mancanze di pagina. Se un processo supera quello superiore, gli vengono dati altri frame. Se invece arriva al limite inferiore significa che sto concedendo al processo un numero di frame troppo elevato (aumentando di conseguenza la dimensione del WS); non lascerò scendere ulteriormente il tasso di mancanza, o altri processi potrebbero cominciare a risentirne, quindi gli tolgo frame.
!!Pag 6
!!!!Prevenzione del thrashing (6) Deleted lines 58-110:
!!!!Sostituzione della pagina (2)
...
!!Pag 6
!!!!Sostituzione della pagina (3)
L'introduzione del ''bit di modifica'' migliora l'efficienza della sostituzione della pagina perché lo scaricamento avviene solo quando serve.
!!!!Politiche di sostituzione della pagina
...
!!Pag 7
!!!!Politiche di sostituzione: FIFO
La politica ''First In / First Out'' guarda al passato, supponendo che ciò che è appena stato utilizzato ha più possibilità di essere scelto ancora nel futuro.
!!!!Politiche di sostituzione: SO
La politica di ''Sostituzione Ottima'' fa risparmiare un sacco di scambi di pagina, ma presuppone la conoscenza della stringa di riferimento, cosa che non accade quasi mai.
!!Pag 8
!!!!Politiche di sostituzione: LRU (1)
...
!!!!Politiche di sostituzione: LRU (2)
Il ''Least Recently Used'' si può realizzare con
* orologi o contatori ("la pagina col contatore più vecchio del mio processo va via)
* stack
!!Pag 9
!!!!Politiche di sostituzione: RB (1)
...
!!!!Politiche di sostituzione: RB (2)
...
!!Pag 10
!!!!Politiche di sostituzione: SC (1)
La politica ''Second Chance'' marca la pagina da rimuovere, ma non la toglie subito. Se anche al turno successivo viene segnalata come vittima designata, stavolta viene tolta davvero.
!!!!Politiche di sostituzione: RB (2)
...
!!Pag 11
!!!!Politiche di sostituzione: LFU
...
!!!!Politiche di sostituzione: MFU
...
!!Pag 12
!!!!Politiche di selezione delle pagine da caricare
In pratica viene selezionata oltre alla pagina richiesta una serie di altre pagine la cui scelta dipende da due modalità di previsione:
* pagina richiesta + N pagine successive adiacenti (sperando che vengano poi effettivamente utilizzate)
* N pagine della stringa di riferimento predetta a partire da un'analisi attenta della situazione che tiene in considerazione vari criteri
Added lines 1-102:
(:title Sistemi Operativi - Appunti caotici:)
[[Torna alla pagina di Sistemi Operativi->SistemiOperativi]]
----
%titolo%''':: Appunti caotici ::'''
%center%%sottotitolo%Lezione 4
%center%%sottotitolo%Thrashing
!!Pag 1
!!!!Sommario
...
!!Pag 2
!!!!Il fenomeno del thrashing
Se un processo ha troppo pochi frame allocati, i page fault occorrono così frequentemente che viene trascorso più tempo nella paginazione che nell'esecuzione del processo, il che ovviamente è una situazione non desiderabile.
Il fenomeno del '''thrashing''' o ''paginazione spazzatura'' avviene quando abbiamo una paginazione così frequente da essere di fatto inutile. Dal momento che ne deriva una grave perdita di prestazioni, la scelta del numero delle pagine deve sempre essere fatta con molta attenzione.
!!!!Cause
* multiprogrammazione: più sono i processi caricati in memoria centrale, più è piccolo il numero di pagine assegnate, più sono frequenti i page fault, più il sistema è rallentato
* l'algoritmo di schedulazione a lungo termine introduce nuovi prrocessi per incrementare lo sfruttamento del processore.
Dal grafico sulla slide si vede chiaramente che superata una certa soglia di livello di multiprogrammazione l'utilizzo della CPU si abbatte drasticamente. E' da quel punto in poi che ho il thrashing. Va detto anche che sarebbe preferibile evitare di arrivare nella parte del grafico con crescita non lineare, dal momento che l'incremento delle prestazioni in questo intervallo è talmente basso che non ne vale nemmeno la pena.
!!Pag 3
!!!!Evitare il thrashing
* '''politica di schedulazione che impedisca il thrashing''', limitando il caricamento di nuovi processi quando il numero di frame allocati ai processi diminuisce eccessivamente
* '''politica di allocazione dei frame che impedisca il thrashing''', restringendo l'insieme dei frame eligibili per lo scaricamento in caso di mancanza di frame liberi (allocazione locale) e in modo tale che il processo continui ad avere un numero minimo di frame disponibili. Il vantaggio di questa soluzione è che non vado a toccare il numero di pagine degli altri processi, evitando che qualcuno particolarmente ingordo dia fastidio agli altri.
!!!!Prevenzione del thrashing (1)
Dato che il programma può cambiare la dinamica degli accessi alla memoria centrale nel tempo, è possibile realizzare un modello di località di esecuzione del processo su cui fare opportune valutazioni. Ad esempio si possono osservare zone di memoria con pochi accessi (probabilmente contenenti dati) ed altre molto più utilizzate (probabilmente zone di codice).
Questa dinamicità è dovuta al fatto che quando scriviamo il programma lo facciamo generalmente in modo leggibile e manutenibilie, strutturando codice e dati applicando dei criteri di buona programmazione (ad esempio scrivendo il programma con una parte principale che esegue varie procedure scritte applicando le stesse figure strutturali come cicli, condizioni, ecc). Uno di questi principi è che quando siamo in una procedura vi rimaniamo finché non è terminata, quindi verranno eseguite delle istruzioni che si trovano in porzioni ben precise e confinate nella memoria centrale. Nei linguaggi strutturati di alto livello sono il compilatore ed il linker a fornire una forte località al codice, ma possiamo ottenere lo stesso risultato anche con linguaggi a livello più basso. Ad esempio strutturando per bene le routine in assembler otterrei comunque un buon livello di localizzazione, evitando di ottenere strutture cosiddette "spaghetti-like", col programma sbriciolato su più porzioni di memoria in modo molto poco efficiente.\\
E' possibile garantire una buona località anche sullo stack e nello heap, in quest'ultimo caso rispettando il principio che sto accedendo a una struttura dati rimarrò nella zona appena allocata per un certo periodo di tempo.
!!Pag 4
!!!!Prevenzione del thrashing (2)
...
!!!!Prevenzione del thrashing (3)
...
!!Pag 5
!!!!Sostituzione della pagina (1)
...
!!!!Sostituzione della pagina (2)
...
!!Pag 6
!!!!Sostituzione della pagina (3)
L'introduzione del ''bit di modifica'' migliora l'efficienza della sostituzione della pagina perché lo scaricamento avviene solo quando serve.
!!!!Politiche di sostituzione della pagina
...
!!Pag 7
!!!!Politiche di sostituzione: FIFO
La politica ''First In / First Out'' guarda al passato, supponendo che ciò che è appena stato utilizzato ha più possibilità di essere scelto ancora nel futuro.
!!!!Politiche di sostituzione: SO
La politica di ''Sostituzione Ottima'' fa risparmiare un sacco di scambi di pagina, ma presuppone la conoscenza della stringa di riferimento, cosa che non accade quasi mai.
!!Pag 8
!!!!Politiche di sostituzione: LRU (1)
...
!!!!Politiche di sostituzione: LRU (2)
Il ''Least Recently Used'' si può realizzare con
* orologi o contatori ("la pagina col contatore più vecchio del mio processo va via)
* stack
!!Pag 9
!!!!Politiche di sostituzione: RB (1)
...
!!!!Politiche di sostituzione: RB (2)
...
!!Pag 10
!!!!Politiche di sostituzione: SC (1)
La politica ''Second Chance'' marca la pagina da rimuovere, ma non la toglie subito. Se anche al turno successivo viene segnalata come vittima designata, stavolta viene tolta davvero.
!!!!Politiche di sostituzione: RB (2)
...
!!Pag 11
!!!!Politiche di sostituzione: LFU
...
!!!!Politiche di sostituzione: MFU
...
!!Pag 12
!!!!Politiche di selezione delle pagine da caricare
In pratica viene selezionata oltre alla pagina richiesta una serie di altre pagine la cui scelta dipende da due modalità di previsione:
* pagina richiesta + N pagine successive adiacenti (sperando che vengano poi effettivamente utilizzate)
* N pagine della stringa di riferimento predetta a partire da un'analisi attenta della situazione che tiene in considerazione vari criteri
----
[[Torna alla pagina di Sistemi Operativi->SistemiOperativi]]
|
|
