Appunti Sistemi operativi

(OS FA CREAZIONE E AGGIORNAMENTO DELLA PAGE TABLE

CPU: FA LA LETTURA DELLA PAGE TABLE)

Prestazioni della Paginazione su richiesta:

Probabilità assenza pagina (p).

Page fault con sostituzione: Quando serve una pagina fisica libera in cui caricare la pagina dal disco,

algoritmo+ meccanismo di sostituzione.

Meccanismo di sostituzione

Pagina pulita: precedentemente copiata da disco

e la copia non ha avuto modifiche, sono

identificate da un “bit di modifica (M)” M=1

allora modificata.

Algoritmi di sostituzione, per scegliere la

vittima minimizzando la frequenza di page

fault:

Algoritmo FIFO (non buono): prima pagina che

entra prima che esce , si imbatte nell’anomalia

di Belady: avere più pagine fisiche di memoria

può causare più page fault.

Algoritmo Ottimale (solo concettuale): si

sostituisce la pagina che non si userà per il periodo di tempo più lungo, è

impossibile sapere i futuri riferimenti.

Algoritmo LRU (Least Recently Used): campo numerico che viene

incrementato ad ogni accesso alla pagina, l’algoritmo sostituisce la

pagina con il valore più basso. (IDEALE)

Approssimazione LRU: utilizza un bit di riferimento (invece che il

contatore, perché troppo lavoro per CPU), itera un puntatore sulle liste

della pagine.

Se pagina candidata ha bit Rif =1, allora la pagina non viene sostituita

ma si pone il bit riferimento a 0.

Se pagina candidata ha bit Rif=0, allora viene sostituita

Ad ogni esecuzione l’algoritmo riprende da dove si era fermato.

Thrasing (pc si impalla): processo non riceve sufficiente numero di

pagine fisiche, il sistema passa più tempo a gestire i page fault che ad

eseguire i programmi.

Origine problema: usare un principio di località, i processi tendono ad accedere ad un sottoinsieme di pagine

della loro memoria (working set), per evitare thrasing almeno il working set deve risiedere in memoria.

Working set size(WSS): numero totale delle pagine a cui il processore fa riferimento in periodo Δ

D=ΣWSS : richiesta totale di memoria da parte dei processi.

M =dimensione RAM, 

Thrasing se D>M. SOLUZIONE Eliminare/ridurre processi.

Gestione memoria in Linux: le versioni moderne non si avvalgano della segmentazione.

Virtual Memory Areas: raggruppa le aree uguali e le gestisce come un singolo gruppo

Allocazione memoria:

User-level: è riservato ai processi utente, area heap alterna

blocchi(chunk) liberi e allocati di dimensione variabile, op:

es q=malloc( 32) (best-fit, ritorna valore NULL se



allocazione fallisce) oppure free(q). Se heap pieno

estensione con sbrk(). Tiene traccia dei chunk come una

linked list. (puntatori memorizzato all’interno dei blocchi

liberi). Prima pagina virtuale del processo ha sempre i

permessi di accesso disattivati (puntatore=NULL), se non

viene inizializzato ha un comportamento che dipende

dall’indirizzo che “pesca”, può essere valido o meno, e

quindi può prendere un “valore spazzattura”, oppure causare

“segmentation fault”

User/kernel split: è dedicato al sistema operativo Kernel non utilizza

una tabella delle pagine separata. Il kernel riusa parte dello spazio

virtuale del processo interrotto.

Problemi di sicurezza, CPU fanno esecuzione speculativa tentando

di indovinare le prossime istruzioni ed eseguirle in anticipo

lasciando tracce nella cache. Soluzione: dedicare al kernel una page

table separata (rallenta performance).

Master kernel page table: gestisce spazio virtuale

riservato al kernel, associazione lineare tra indirizzi

virtuali e fisici

Buddy System: permetti di allocare per multipli di 2^k

pagine contigue

Architettura Sistema I/O: è spesso collo di bottiglia delle

prestazioni e causa perdite dei dati, ha degli indicatori di

prestazione: latenza, numero richieste servite, percentuale

di utilizzo dei dispositivi, no starvation. Le periferiche

sono: Human readable (interagiscono con utente),

machine readable (interazione con dispositivi locali),

comunicazione (interazione con dispositvi remoti). Il sistema di I/O del SO fornisce un astrazione dei

dispositivi ai programmi utente.

Parte indipendete dai dispostivi (programma usa stesse primitive per accedere ai dischi).

Parte dipendente vi sono i device drivers che sono specifici per ogni dispositivo e rappresentano la maggior

parte del SO (maggiori cause di malfunzionamenti)

Disco: dispositivo più critico.

Parametri prestazionali: tempo di seek: tempo di ricerca per posizionare la testina sulla traccia desiderata.

Ritardo di rotazione: tempo necessario affinche l’inzio del dato ruoti presso la testina.

Tempo di trasferimento: il periodo necessario per trasferire i dati una volta che la testina è posizionata

correttamente sopra il settore richiesto.

Politiche di I/O Buffering:

Write-through: dati scritti immediatamente sia su buffer sia su disco

Write-back: dati non scritti subito ma svuotati (flush) periodicamente.(migliori prestazioni ma problema con

i guasti)

Page cache: tutta la memoria RAM residua non usata dai processi viene dedicata alla page cache, ci sono i

parametri di tempo massimo per flush/percentuale di memoria sporca.

Politiche Scheduling del disco:

Secondo il richiedente: FIFO, basse prestazioni molti movimenti superflui, PRIORITA’: come FIFO però con

code diverse per ogni priorità, possibile starvation. LIFO

Secondo l’elemento richiesto: SSTF (Shortest Service Time First) seleziona richiesta con minimo seek time

(starvation).

SCAN (Ascensore): soddisfa le richieste di tutta una sola direzione e successivamente si inverte. (starvation

ridotta)

C-SCAN: una direzione, quando viene soddisfatta i braccetti del

disco portano la testina alla parte opposta.

Linus Elevator (C-SCAN modificato per Linux):I/O sorting e

merging. Starvation tipo: writes-starving-reads cioè scritture molto

superiori alle letture. Scritture sono bufferizzate, letture non sono

bufferizzate. Novità: Deadline alle code.

Anticipatory scheduling: introduce un meccanismo di attesa dopo

una lettura, per migliorare le prestazioni delle letture successive.

RAID (Redundant Array of Independent Disks): un insieme di

dischi (blocchi fisici divisi “strip”), visto dalle applicazioni come

un’unica unità logica, una stripe è un insieme di strip su posizioni

omologhe

RAID 0: non ridondante, se disco guasto sua porzione dati viene

persa, dischi lavorano in parallelo, dischi fisici=quantità dati logici.

Problema: strip piccolofile sparpagliato su più dischi

RAID 1: mirroring, copia su disco, offre elevata affidabilità ma dimezza la capacità effettiva di storage.

RAID 3: ridondanza con bit di parità, dischi richiesti n+1,

RAID 2: ridondanza con codici di Hamming, rileva in più di un disco (considerato eccessivo), dischi

richiesti: n+m, tempo servizio : log(dischi da proteggere).

RAID 4: striping su blocchi di dati, ridondanza dei dati con bit di parità per blocco, disco di parità è un collo

di bottiglia. Dischi richiesti N+1. Problema: aggiornare il bit di parità.

RAID 5: ridondanza dei dati con bit di parità per blocco distribuiti su più dischi, n+1cd.

RAID 6: doppia parità distribuita, offre la massima affidabilità ma le prestazioni in scrittura(peggiore). N+2

Dischi richiesti.

SSD: fatto di celle di transistor ad accesso random e riprogrammabili, la vita dipende dal numero di

operazioni, fenomeno di write amplificationscritture su blocchi interi, gli accessi casuali causano usura e

peggiorano le prestazioni.

File System: gestione e organizzazione dei file, fornisce alle applicazioni un’interfaccia unica per la gestione

dei file. Un file è la prima astrazione realizzata dal FS, la directory è la seconda (trattate come “file speciali”,

contengono puntatori a file). Le directory permettono di condividere lo stesso file (link).

Link:

Hard-Link: usano indirizzo fisico del file, un file ha due puntatori

Soft-Link: ho due file(uno fittizio).

Rimozione Link:

Reference Counting: il file è conservato finché esiste un almeno un riferimento (esiste un conteggio di

riferimenti).

BackPointers: richiede doppio collegamento tra directory e file.

Accesso ai File:

Sequenziale: FS ha puntatore all’ultima posizione acceduta, dopo un’operazione il puntatore avanza.

Diretto: processo seleziona (seek) una posizione arbitraria da accedere.

File Control Block (FCB): è un contenitore di metadati(contiene info sui file, non contiene il nome), la

directory entry punta ad esso. Gli FCB più usato sono mantenuti in RAM (caching).

Organizzazione fisica: il disco è un vettore

lineare di blocchi (per OS). Blocco: gruppo di

settori. Il disco può essere suddiviso in partizioni,

ognuna con un proprio file system. La tabella

delle partizioni contiene le coordinate di ogni

partizione. MBR (Master Boot Record) contiene

il bootloader.

Metodi di Allocazione(modi in cui i blocchi sono

assegnati):

Allocazione Contigua: file occupa insieme di blocchi contigui, favorisce accesso sequenziale e per accedere

al file è sufficiente sapere la posizione di inizio e la lunghezza. Frammentazione esterna, file non possono

crescere facilmente.

Allocazione Concatenata: lista concatenata di blocchi, niente frammentazione, facilità nella scelta per

allocare. Problema se un link viene danneggiato, maggior consumo. Es. FAT, la FAT table concentra i

puntatori in un’unica area sul disco.

Allocazione Indicizzata: tutti i puntatori salvati in un blocco indice. Svantaggio, la tabella indice ha una

dimensione fissa. Linux risolve il problema con “inode” permette adottare puntatori diretti e indiritte, così

da aumentare il numero di puntatori, ed l’index node contiene il FCB e puntatori. Per la gestione dello spazio

libero viene usato il BitMap (1bit x ogni blocco).

Cancellazione di File: l’FS cancella solo i metadati dei file, i blocchi sono marcati come disponibili (così da

sovrascriverli)

Ext2: file system standard per sistemi Unix, dimensione

dei blocchi configurabile, attributi dei file ereditabili

dalle directory, supporto a file immutabili, gestione dei

file con dimensione max di 4TB.

Organizzazione:

l file system ext2 suddivide il disco in gruppi di

blocchi, raggruppando blocchi appartenenti alla stessa

traccia o a tracce adiacenti per favorire la località degli

accessi e migliorare le prestazioni, gli inode tendono ad

essere allocati nel gruppo della directory che contiene il file, mentre le directory sono distribuite

uniformemente tra i vari gruppi

Struttura del block group:

Superblock: contiene informazioni sulla partizione.

Inode table: contiene gli inode dei file appartenenti al gruppo.

Data