[Sistemi operativi] Tabella di paginazione di tipo hash

[Neptune]

Salve a tutti,
vorrei porvi più che altro una domanda teorica perchè per come è spiegata sui vari libri non riesco a comprenderla.

Sul libro dice che "ogni elmento della tabella hash contiene una lista concatenata di eleementi che la funzione hash fa corrispondere alla stessa locazione". E questo non riesco a capirlo.

Cioè, la tabella hash è una tabella in cui OGNI SINGOLO CAMPO è una linked list? e che significa che ogni elemento corrisponde alla stessa locazione? Cioè ogni pagina è un elmeneto e viene descritta come linked list? Quindi tu scorri la tabella, individui la pagina che ti serve e poi scorri la lista per trovare la locazione esatta?

Sapreste chiarirmi questo dubbio?

[MItaly]

Originariamente inviato da Neptune
Cioè, la tabella hash è una tabella in cui OGNI SINGOLO CAMPO è una linked list?

All'atto pratico sì.

e che significa che ogni elemento corrisponde alla stessa locazione?

La funzione di hash mappa tutti i possibili valori delle chiavi degli elementi che deve contenere in indici nella tabella in questione. In un mondo ideale, la tabella di hash sarebbe di dimensioni infinite, per ogni chiave la funzione di hash computerebbe un valore univoco, e quindi in ogni "posto" della tabella ci si farebbe stare un solo elemento.

Tuttavia le tabelle di hash nella realtà hanno dimensioni limitate, e le funzioni di hash possono produrre valori uguali per chiavi diverse. Per questo si fa in modo che in ogni "casella" della tabella di hash, invece di starci un elemento, ci sta una linked list di elementi, che contiene tutti gli elementi dal medesimo hash.
Quando si deve cercare qualcosa in una tabella di hash, si computa l'hash della chiave, si va alla relativa "casella" nella tabella di hash e si scorre la linked list finché non si trova l'elemento cercato (confrontando la chiave cercata con quella degli elementi presenti nella linked list in questione).

In questa maniera, la complessità dell'operazione tende a quella dell'array nei casi migliori (tutti elementi con hash diversi), dato che per localizzare la "casella" della tabella basta computare la funzione di hash e saltare al relativo indirizzo di memoria (O(1)), e, nel caso peggiore in assoluto (tutti gli elementi hanno lo stesso hash), raggiunge la complessità della linked list (O(N)), caso comunque raro se la tabella è adeguatamente commisurata al numero di elementi che dovrà contenere.

Questo in generale sulle hash table, sul loro impiego specifico per gestire le pagine di memoria non ti so dire.

[Neptune]

Originariamente inviato da MItaly
All'atto pratico sì.

La funzione di hash mappa tutti i possibili valori delle chiavi degli elementi che deve contenere in indici nella tabella in questione. In un mondo ideale, la tabella di hash sarebbe di dimensioni infinite, per ogni chiave la funzione di hash computerebbe un valore univoco, e quindi in ogni "posto" della tabella ci si farebbe stare un solo elemento.

Tuttavia le tabelle di hash nella realtà hanno dimensioni limitate, e le funzioni di hash possono produrre valori uguali per chiavi diverse. Per questo si fa in modo che in ogni "casella" della tabella di hash, invece di starci un elemento, ci sta una linked list di elementi, che contiene tutti gli elementi dal medesimo hash.
Quando si deve cercare qualcosa in una tabella di hash, si computa l'hash della chiave, si va alla relativa "casella" nella tabella di hash e si scorre la linked list finché non si trova l'elemento cercato (confrontando la chiave cercata con quella degli elementi presenti nella linked list in questione).

In questa maniera, la complessità dell'operazione tende a quella dell'array nei casi migliori (tutti elementi con hash diversi), dato che per localizzare la "casella" della tabella basta computare la funzione di hash e saltare al relativo indirizzo di memoria (O(1)), e, nel caso peggiore in assoluto (tutti gli elementi hanno lo stesso hash), raggiunge la complessità della linked list (O(N)), caso comunque raro se la tabella è adeguatamente commisurata al numero di elementi che dovrà contenere.

Questo in generale sulle hash table, sul loro impiego specifico per gestire le pagine di memoria non ti so dire.

Quindi un "hash" sarebbe una specie di indice di riga, ma può esserci che per quella riga ci siano più elementi, ovvero "più colonne" (se vogliamo rappresentare tutto come una tabella) e quindi scorriamo nella linked list per trovare l'elemento che realmente stavamo cercando facendo un confronto tra gli indici "di pagina logica" a cui poi assocerà la pagina fisica?

E questo metodo dovrebbe essere più veloce di una "normale tabella di allocazione dei pocessi" ? (anche se in realtà non saprei definire come viene in realtà memorizzata una tabella non di tipo hash)

[MItaly]

Originariamente inviato da Neptune
Quindi un "hash" sarebbe una specie di indice di riga, ma può esserci che per quella riga ci siano più elementi, ovvero "più colonne" (se vogliamo rappresentare tutto come una tabella) e quindi scorriamo nella linked list per trovare l'elemento che realmente stavamo cercando facendo un confronto tra gli indici "di pagina logica" a cui poi assocerà la pagina fisica?

Esattamente.

E questo metodo dovrebbe essere più veloce di una "normale tabella di allocazione dei pocessi" ? (anche se in realtà non saprei definire come viene in realtà memorizzata una tabella non di tipo hash)

Bisognerebbe capire cos'è una "normale tabella".

Se è un normale array, ci sono i costi di ridimensionamento (a meno che non lo si renda di dimensione fissa e finita lì) e la ricerca non è immediata, a meno che non si tenga l'array ordinato (costi aggiuntivi), nel qual caso si può usare una ricerca binaria, oppure si usi un array di dimensione fissa e massima, e accedi agli elementi usando direttamente il numero di pagina logica.

Il problema è che, se su macchine a 32 bit questo è fattibile, su macchine a 64 bit la questione diventa più complicata: supponiamo di avere una macchina che può indirizzare 4 GiB di memoria fisica, divise in pagine da 4 KiB; abbiamo quindi 1048576 pagine. Servono quindi 1048576 ingressi di tabella; per un semplice mapping pagina logica->pagina fisica basterebbero interi a 20 bit, con cui però è scomodo lavorare, per cui diciamo che usiamo normali interi a 32 bit, in modo da avere anche 12 bit per memorizzare gli attributi delle pagine logiche.
Ora, ci serve una tabella da 1048576 ingressi ciascuno di 4 byte, ossia 4 MB di memoria, una cosa fattibilissima con un normale array.

Ma pensiamo ora ad una macchina a 64 bit, in cui è possibile indirizzare 2^64 byte di memoria fisica: se anche usassimo pagine da 4 MiB, si tratterebbe comunque di 2^64/2^22=2^42 voci di tabella, che, anche usando interi a 48 bit, necessiterebbero, per il modello ad array "normale", di 3*2^42 byte, ossia di 24 TiB di spazio per la sola tabella di mapping logico-fisico.

Una soluzione quindi possono essere le tabelle multilivello: una tabella "master" da 2^21 ingressi, uno per ciascun blocco di 2^21 byte; ogni ingresso contiene un puntatore ad un'altra tabella da 2^21 ingressi, ognuno dei quali è relativo ad una pagina da 4 MiB. Naturalmente le tabelle "secondarie" vengono allocate solo se necessario.

Un'altra soluzione invece è appunto la tabella di hash, basta dimensionarla all'inizio in maniera adeguata alla memoria fisica da gestire (un tot più grande del necessario se si prediligono le prestazioni, un po' più piccola se si può accettare un numero di collisioni più alto a patto di un ingombro inferiore in memoria).

Nota: se stai preparando un esame su questa roba, controlla anche altrove quello che sto dicendo, dato che non ho mai studiato seriamente informatica, mi baso giusto su una lettura "di piacere" dal Tanenbaum e sul buon senso.

[YuYevon]

Nella gestione della memoria di un sistema operativo, le hash table vengono utilizzate per la gestione di tabelle delle pagine "invertite". Il beneficio sta nel fatto che mentre con le tabelle delle pagine "tradizionali" si hanno tante entry quante sono le pagine virtuali possibili (e su sistemi a 64 bit queste diventano 2^64/dimensione_pagina), con le tabelle invertite ci sono invece tante entry quante sono le pagine fisiche, quindi se (per citare Tanenbaum) in un sistema a 64 bit abbiamo 256 MB di ram con la dimensioni delle pagine pari a 4KB (c'è da chiedersi quanto sia sensato avere 256 MB di RAM su un sistema a 64 bit ma vabbè), una tabella delle pagine invertite richiede solo circa 256.000.000 / 4000 elementi, cioè circa 64000, mentre con le tabelle normali sarebbero 2^52 (cioè 2^64 / 2^12).

Si prende il numero di pagina virtuale dall'indirizzo virtuale, si calcola l'hash con un'apposita funzione e si accede all'elemento della tabella hash corrispondente: questo contiene un puntatore alla lista linkata che ha tanti elementi quante sono i numeri di pagina che hanno quello stesso valore della funzione hash, e per ognuna di esse è riportato il numero di pagina fisica corrispondente. Si scorre la lista fino a quando non si trova l'elemento con esattamente lo stesso numero di pagina richiesto e si compone l'indirizzo fisico prendendo il numero di frame corrispondente (l'offset è lo stesso dell'indirizzo virtuale). Se la pagina non viene trovata, si genera un page fault come nel caso della tabella "normale".

Per quanto riguarda le funzioni hash, in genere si tende a renderle "universali", cioè tali che i valori generati siano equiprobabili in tutto il range dei valori possibili, inoltre la concatenazione non è l'unico modo per gestire la collisione ma in genere per le hash table nella gestione della memoria dei sistemi operativi si tende a preferire la "semplicità" all'efficacia, per non aggiungere overhead di computazione.

[MItaly]

[OT]La tua firma... [/OT]

[YuYevon]

Originariamente inviato da MItaly
[OT]La tua firma... [/OT]

[ottì]acume--; ti riferisci a getslack vero? [/ottì]

[Neptune]

Originariamente inviato da YuYevon
Per quanto riguarda le funzioni hash, in genere si tende a renderle "universali", cioè tali che i valori generati siano equiprobabili in tutto il range dei valori possibili, inoltre la concatenazione non è l'unico modo per gestire la collisione ma in genere per le hash table nella gestione della memoria dei sistemi operativi si tende a preferire la "semplicità" all'efficacia, per non aggiungere overhead di computazione.

Riguardo a questo mi hai creato un'altro dubbio che non avevo.

Inanzi tutto questo "hash" dovrebbe essere un id? e viene generato con un determinato "algoritmo" fatto appostiamente per ordinare al meglio gli elementi?

E se si aggiungono altri elementi in seguito "vengono concatenati" ad un pre-esistente indirizzo hash? questo è che si intende per "concatenazione e gestione della collisione" ?

Comunque si è un esame di sistemi operativi ma è un argomento marginale, è giusto una cosa mia per capirne un pò meglio il funzionamento, dubito che su un paragrafetto che ne parla il libro poi debba farne un tema di 3 pagine

[YuYevon]

Originariamente inviato da Neptune
Inanzi tutto questo "hash" dovrebbe essere un id? e viene generato con un determinato "algoritmo" fatto appostiamente per ordinare al meglio gli elementi?

Una funzione hash è una funzione che, presa in input una chiave (che può essere un numero o magari una stringa che viene convertita in numero), restituisce un certo valore numerico (chiamato valore hash, codice hash, hash e basta o in altri modi). Ad ogni chiave è associato un solo valore, ma un certo valore può corrispondere a più chiavi diverse (ed è per questo che poi ci sono le collisioni). Una buona funzione hash deve essere "uniforme", cioè deve fare in modo di distribuire le varie chiavi su tutto il range dei valori possibili; per intenderci, una pessima funzione hash sarebbe quella che per ogni chiave genera sempre lo stesso valore, perché se così fosse tutti gli elementi colliderebbero e di fatto si avrebbe un'unica enorme lista con tutti gli elementi possibili (rendendo di fatto inutile e anzi controproducente il ricorso alla tabella hash, perché ricorrendo direttamente alla lista concatenata almeno non si perderebbe il tempo ogni volta per il calcolo dell'hash ma solo per la ricerca nella lista).

Se una funzione hash può avere in input 500 chiavi diverse e i valori che assume sono 100, allora l'ideale sarebbe che, su ogni valore, siano mappate 500/100=5 chiavi. Questa sarebbe la funzione ideale, nella pratica si cerca di realizzare qualcosa che tenda a questo grado di uniformità.

Originariamente inviato da Neptune
E se si aggiungono altri elementi in seguito "vengono concatenati" ad un pre-esistente indirizzo hash? questo è che si intende per "concatenazione e gestione della collisione" ?

Se il valore hash calcolato per questi elementi è stato generato già per altri elementi, allora si ha la collisione e un modo per gestire il problema è appunto la concatenazione, creando una lista. Poi ce ne sono altri come l'indirizzamento aperto, ma per quello che ne so nella gestione della memoria dei SO si ricorre sempre alla concatenazione.

[Neptune]

Originariamente inviato da YuYevon
[b]Una funzione hash è una funzione che, presa in input una chiave (che può essere un numero o magari una stringa che viene convertita in numero), restituisce un certo valore numerico[b] (chiamato valore hash, codice hash, hash e basta o in altri modi). Ad ogni chiave è associato un solo valore, ma un certo valore può corrispondere a più chiavi diverse (ed è per questo che poi ci sono le collisioni). Una buona funzione hash deve essere "uniforme", cioè deve fare in modo di distribuire le varie chiavi su tutto il range dei valori possibili; per intenderci, una pessima funzione hash sarebbe quella che per ogni chiave genera sempre lo stesso valore, perché se così fosse tutti gli elementi colliderebbero e di fatto si avrebbe un'unica enorme lista con tutti gli elementi possibili (rendendo di fatto inutile e anzi controproducente il ricorso alla tabella hash, perché ricorrendo direttamente alla lista concatenata almeno non si perderebbe il tempo ogni volta per il calcolo dell'hash ma solo per la ricerca nella lista).

Se una funzione hash può avere in input 500 chiavi diverse e i valori che assume sono 100, allora l'ideale sarebbe che, su ogni valore, siano mappate 500/100=5 chiavi. Questa sarebbe la funzione ideale, nella pratica si cerca di realizzare qualcosa che tenda a questo grado di uniformità.



Se il valore hash calcolato per questi elementi è stato generato già per altri elementi, allora si ha la collisione e un modo per gestire il problema è appunto la concatenazione, creando una lista. Poi ce ne sono altri come l'indirizzamento aperto, ma per quello che ne so nella gestione della memoria dei SO si ricorre sempre alla concatenazione.

Daccordo e questa funzione hash crea quindi una chiave che sia "facile da trovare" no? è questo lo scopo? creando un determinato algoritmo (basato su cosa? su che dati lavora che può ricreare più volte la stessa chiave?) che a seconda dei dati in input crea questa hash. Ma come fa a ricreare "eroneamente" chiavi hash uguali?