Cap.4 Memorizzazione di record ed organizzazione dei file Flashcards
Cos’è un Buffer?
è una zona di memoria usata per compensare differenze di velocità nel trasferimento o nella trasmissione di dati, oppure per velocizzare l’esecuzione di alcune operazioni
Mentre viene letto o scritto un buffer, la CPU può elaborare i dati nell’altro buffer.
Ciò è possibile perché esiste un processore indipendente per l’I/O di disco (controller) che, una volta avviato, può procedere nel trasferire un blocco di dati tra la memoria e il disco indipendentemente dall’operazione della CPU, e in parallelo con essa.
Cos’è la tecnica della doppia bufferizzazione?
Essa consente una lettura o scrittura continua di dati su blocchi di disco consecutivi, che elimina il tempo di posizionamento e il ritardo di rotazione per i trasferimenti
di tutti i blocchi escluso il primo. Inoltre, i dati sono tenuti pronti per essere elaborati, riducendo così il tempo di attesa nei programmi
Un modo semplice per spiegare come funziona il buffering multiplo è fare un esempio reale. È una bella giornata di sole e hai deciso di tirare fuori la piscina per bambini, solo che non riesci a trovare il tuo tubo da giardino. Dovrai riempire la piscina di secchi. Quindi riempi un secchio (o tampone) dal rubinetto, chiudi il rubinetto, vai in piscina, versi l’acqua, torna al rubinetto per ripetere l’esercizio. Questo è analogo al buffering singolo. Il rubinetto deve essere chiuso mentre “processi” il secchio d’acqua.
Ora considera come lo faresti se avessi due secchi. Riempirai il primo secchio e poi scambierai il secondo sotto il rubinetto in esecuzione. Hai quindi il tempo necessario per riempire il secondo secchio per svuotare il primo nella piscina per bambini. Quando torni puoi semplicemente scambiare i secchi in modo che il primo si riempia di nuovo, durante il quale puoi svuotare il secondo nella piscina. Questo può essere ripetuto fino a quando la piscina è piena. È chiaro che questa tecnica riempirà la piscina molto più velocemente in quanto vi è molto meno tempo trascorso ad aspettare, senza fare nulla, mentre i secchi si riempiono. Questo è analogo al doppio buffering. Il rubinetto può essere sempre attivo e non deve attendere che l’elaborazione sia terminata.
Hashing
Un tipo di organizzazione primaria di file è basato sull’hash, che fornisce un accesso rapido ai record sotto certe condizioni di ricerca. La condizione di
ricerca deve essere una condizione di uguaglianza su un campo singolo, detto campo hash del file, che è anche un campo chiave (chiave hash). L’idea è
quella di fornire una funzione hash (di randomizzazione), che è applicata al valore del campo hash di un record e fornisce l’indirizzo del blocco di disco
in cui è memorizzato il record.
Hash interno per i file, l’hash è implementato con una tabella hash costruita usando un vettore di record di dimensioni
M, e che il campo di valori possibili per l’indice del vettore vada da 0 a M-1, si ha pertanto M slot i cui indirizzi corrispondono agli indici del vettore. Si
sceglierà una funzione hash che trasforma il valore del campo hash in un intero compreso tra 0 e M-1.
L’hash per file su disco è detto hash esterno. Lo spazio di indirizzi obiettivo è fatto di bucket, che è un blocco di disco o un cluster di blocchi contigui. La
funzione hash mappa una chiave in un numero relativo per il bucket. Una tabella contenuta nell’header del file converte il numero del bucket nel
corrispondente indirizzo di blocco di disco. Con i bucket il problema delle collisioni è meno grave perché possono essere inviati nello stesso bucket
senza causare problemi. Ma se il bucket è pieno, viene utilizzata una variazione del concatenamento in cui in ogni bucket si mantiene un puntatore a
una lista concatenata di record di overflow per il bucke
Quali sono le risoluzioni delle collisioni?
Il processo di ricerca di un’altra posizione è detto risoluzione delle collisioni:
▪ Indirizzamento aperto: procedendo dalla posizione occupata specificata dall’indirizzo hash, il programma verifica in ordine le posizioni successive fino a che non si trova una posizione inutilizzata (vuota).
▪ Concatenamento: per questo metodo si estende il vettore con un certo numero di posizioni di overflow (locazioni vuote). Inoltre, a ogni locazione di record viene aggiunto un campo puntatore. Una collisione viene risolta ponendo il nuovo record in una locazione di overflow inutilizzata e imponendo il valore dell’indirizzo di tale locazione al puntatore presente nella locazione di indirizzo hash occupata. Si mantiene perciò una lista concatenata di record di overflow per ogni indirizzo hash.
▪ Hash multiplo: il programma applica una seconda funzione hash se la prima ha come risultato una collisione. Se risulta un’altra collisione, il programma usa l’indirizzamento aperto o applica una terza funzione hash e poi, se necessario, usa l’indirizzamento aperto.
Cos’è l’hashing statico? Quali sono i vantaggi/svantaggi?
L’hashing statico è un metodo di hashing dei dati che utilizza una chiave o un indice predeterminato per mappare i dati nelle posizioni di memoria.
A ciascun dato viene assegnato un indirizzo univoco nella tabella hash, determinato dal valore della chiave.
Il valore della chiave viene utilizzato per accedere ai dati dalla tabella hash, rendendo facile e veloce l’individuazione di un dato specifico
VANTAGGI:
tempi di ricerca più rapidi, migliore utilizzo della memoria e maggiore coerenza dei dati.
SVANTAGGI:
non è adatto a insiemi di dati in continua evoluzione, poiché la tabella hash statica non è progettata per accogliere nuovi elementi di dati. Inoltre, l’hashing statico può essere difficile da implementare in alcuni scenari, ad esempio quando è necessario memorizzare una grande quantità di dati.
Cos’è l’hashing estendibile? Quali sono i vantaggi/svantaggi?
L’hash estendibile, memorizza una struttura d’accessi insieme al file, simile all’indicizzazione. La differenza è che la struttura d’accesso è basata sui valori che risultano dopo l’applicazione della funzione hash al campo di ricerca.
Nell’indicizzazione, invece, la struttura d’accesso è basata sui valori del campo di ricerca stesso. Più precisamente, nell’hash estendibile, si mantiene una specie di directory, un vettore di 2^d indirizzi di bucket, dove d è detta profondità globale (global depth) della directory.
Il valore intero corrispondente ai primi d bit (i più significativi) di un valore hash è usato come un indice per il vettore per determinare un elemento della directory, e l’indirizzo in corrispondenza a quell’elemento determina il bucket in cui sono memorizzati i record corrispondenti.
Una profondità locale (local depth) d’, memorizzata con ogni bucket, specifica il numero di bit su cui è basato il contenuto del bucket
L’hashing dinamico è un metodo di archiviazione dei dati che consente di recuperare i dati in modo rapido ed efficiente.
L’hashing dinamico è una forma avanzata di hashing che consente di modificare frequentemente la memorizzazione dei dati senza dover modificare la struttura sottostante.
VANTAGGI:
maggiore scalabilità e flessibilità, può essere utilizzato per migliorare le prestazioni dei sistemi di recupero e archiviazione dei dati. Consentendo modifiche frequenti nella memorizzazione dei dati, l’hashing dinamico può ridurre il tempo necessario per la ricerca e l’aggiornamento dei dati. Inoltre, l’hashing dinamico può contribuire a ridurre lo spazio necessario per l’archiviazione dei dati, in quanto non richiede l’archiviazione dell’intero set di dati in memoria.
SVANTAGGI:
Uno svantaggio è che la directory deve essere ispezionata prima di accedere ai bucket veri e propri, il che ha come risultati due accessi ai blocchi anziché uno solo, com’è invece nell’hash statico
Cos’è l’hash lineare? E come funziona?
L’hash lineare non richiede strutture d’accesso addizionali. In questi schemi hash il risultato dell’applicazione di una funzione hash è un intero non negativo, e perciò può essere rappresentato come un numero binario. La struttura d’accesso è costruita sulla rappresentazione binaria del risultato della funzione hash, che è una stringa di bit. Tale rappresentazione sarà detta valore hash di un record.
I record sono distribuiti fra i bucket sulla base dei valori dei bit iniziali (leading bits) presenti nei loro valori hash
Si supponga che il file abbia inizialmente M bucket numerati 0, 1, …, M-1 e usi la funzione mod hash h(K)=K mod M, questa funzione hash è detta funzione hash iniziale hi.
L’overflow a seguito di collisioni è ancora necessario e può essere gestito mantenendo singole catene di overflow per ogni bucket. Però, quando una collisione porta a un record di overflow in ogni bucket del file, il primo bucket nel file (bucket 0) viene sdoppiato in due bucket: il bucket originario 0 e un nuovo bucket M alla fine del file. I record originariamente nel bucket 0 sono distribuiti tra i due bucket sulla base di una diversa funzione hash hi+1(K)=K mod 2M
Non c’è alcuna directory, è necessario solo un valore n, inizialmente posto a 0 e incrementato di 1 ogni volta che si verifica uno sdoppiamento, per determinare quali bucket sono stati sdoppiati.
Per recuperare un record con valore di chiave hash K, dapprima si applica la funzione hi a K, se hi(K) < n, allora si applica la funzione hi+1 a K perché il bucket è già stato sdoppiato. Inizialmente è n=0, a indicare che la funzione hi si applica a tutti i bucket, n cresce linearmente quando i bucket vengono sdoppiati. Quando n=M dopo essere stato incrementato, ciò significa che tutti i bucket originari sono stati sdoppiati e la funzione hash hi+1 si applica a tutti i record nel file.
A questo punto, n è riportato a 0, e ogni nuova collisione che causa overflow porta all’uso di una nuova funzione hash hi+2(K) = K mod 4M
Cos’è la tecnologia RAID?
Un miglioramento nella tecnologia della memoria secondaria è rappresentato dallo sviluppo della tecnologia RAID, acronimo di Redundant Array of Inexpensive (o Indipendent) Disks.
Lo scopo principale della tecnologia RAID è quello di uguagliare i tassi molto diversi di miglioramento delle prestazioni dei dischi rispetto a quelli della memoria principale e dei microprocessori.
Una soluzione naturale consiste in un grande vettore di piccoli dischi indipendenti che si comporta come un singolo disco logico di maggiori prestazioni.
Viene usato un concetto detto data striping (suddivisione dei dati), che utilizza il parallelismo per incrementare le prestazioni del disco.
Il data striping distribuisce i dati in modo trasparente fra più dischi, così che essi si comportino come un unico disco, grande e veloce.
La suddivisione migliora le prestazioni di I/O complessive consentendo che I/O multipli vengano serviti in parallelo, fornendo così alti tassi di trasferimento.
La suddivisione dei dati realizza anche un bilanciamento del carico fra i dischi.
Quali sono i miglioramenti dell’affidabilità nella tecnologia RAID? E le tecniche?
Avendo più dischi, la frequenza di guasto è maggiore, quindi un’ovvia soluzione è quella di servirsi di una certa ridondanza dei dati in modo tale che i guasti ai dischi possano essere tollerati.
Gli svantaggi sono le operazioni di I/O aggiuntive per la scrittura, calcoli supplementari per mantenere la ridondanza e per effettuare il ripristino dagli errori, e capacità di disco aggiuntiva per memorizzare informazioni ridondanti
Una tecnica per introdurre ridondanza è detta mirroring o shadowing, dove i dati sono scritti con ridondanza in due dischi fisici identici, che sono trattati come un solo disco logico.
Quando i dati vengono letti, essi possono essere recuperati dal disco con minori ritardi di accodamento, di posizionamento e di rotazione.
Se un disco si guasta, l’altro disco viene usato finché il primo non è stato riparato.
Un’altra soluzione al problema dell’affidabilità è quella di memorizzare informazioni supplementari che non sono normalmente necessarie ma che possono essere usate per ricostruire le informazioni perse in caso di guasto del disco
Quali sono i miglioramenti delle prestazioni nella tecnologia RAID?
I vettori di dischi si servono della tecnica del data striping per ottenere tassi di trasferimento migliori.
il data striping a livello di bit (bit-level data striping) consiste nello spezzare un byte di dati e nello scrivere il bit j nel j-esimo disco.
((Con byte di 8 bit, otto dischi fisici possono essere considerati come un solo disco logico con un aumento di otto volte del tasso di trasferimento dati. Ogni disco partecipa a ciascuna richiesta di I/O e l’ammontare totale di dati letti per ogni richiesta è di otto volte i dati letti dal singolo disco.))
Lo striping a livello di bit può essere generalizzato a un numero di dischi che sia o un multiplo o un fattore di otto.
La granularità dell’interleaving dei dati può essere maggiore di un singolo bit, ad esempio, i blocchi di un file possono essere suddivisi su dischi diversi, dando origine allo striping a livello di blocco (block-level striping)
Con lo striping a livello di blocco, richieste indipendenti multiple che accedono a blocchi singoli (piccole richieste) possono essere servite in parallelo da dischi separati, diminuendo così il tempo di accodamento delle richieste di I/O. Le richieste che accedono a più blocchi (grandi richieste) possono essere parallele, riducendo così il loro tempo di risposta. In generale, più elevato è il numero di dischi in un vettore, più ne beneficiano le prestazioni potenziali. Però, supponendo che i guasti siano indipendenti, il vettore di dischi di 100 dischi ha nell’insieme un’affidabilità che è 1/100 di quella di un disco singolo. Perciò la ridondanza tramite codici a correzione d’errore e il mirroring di disco è necessaria per fornire affidabilità insieme con alte prestazioni.
Quali sono i problemi da considerare nelle ridondanze nei raid?
L’introduzione di ridondanze deve considerare due problemi:
la scelta di una tecnica per calcolare l’informazione ridondante
e
la scelta di un metodo per distribuire l’informazione ridondante sul vettore di dischi.
Si affronta il primo problema tramite l’uso di codici a correzione d’errore che utilizzano bit di parità, o codici specializzati.
Con lo schema di parità si può considerare che un disco ridondante contenga la somma di tutti i dati presenti negli altri dischi.
Quando un disco si guasta le informazioni mancanti possono essere ricostruite tramite un processo simile a una sottrazione.
Per il secondo problema, i due approcci più importanti consistono nel memorizzare le informazioni ridondanti su un piccolo numero di dischi o nel distribuirle uniformemente su tutti i dischi. Quest’ultimo ha come risultato un miglior bilanciamento del carico.
I diversi livelli di RAID scelgono una combinazione di queste opzioni per implementare la
ridondanza, e perciò per migliorare l’affidabilità
