[membox] Mutua esclusione efficiente per la hash table

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

Salve a tutti,
sto lavorando al progetto membox (qui il kit con la descrizione) e vorrei confrontarmi con qualcuno sul sistema che è opportuno usare per la mutua esclusione della hashtable dove si memorizzano i file.

Per fare un breve riassunto, bisogna realizzare un server che con più thread accede contemporaneamente in una hash table inserendo/eliminando/modificando i suoi elementi. Per cui ovviamente l'accesso alla hash table deve essere in mutua esclusione; però in una lezione di laboratorio il Torquati disse esplicitamente che mettere solo un mutex per proteggere l'accesso a tutta la hash table non è una soluzione accettabile (= ti boccia), perché è troppo inefficiente (blocchi tutta la hashtable quando invece basterebbe bloccare solo l'elemento sui cui agisce quel thread, in modo da lasciare liberi gli altri di leggere/scrivere altrove). D'altra parte disse che non è accettabile nemmeno dichiarare un mutex per ogni elemento memorizzato nella hash table: in questo modo ci sarebbe il massimo del parallelismo, ma gli elementi possono essere anche migliaia e quindi supererebbero il numero massimo di mutex dichiarabili, con il rischio che la memoria del programma esploda. Insomma ci ha fatto capire che bisogna trovare una via di mezzo tra bloccare tutti gli elementi e bloccarne uno alla volta.

Io al momento ho ignorato il problema e provvisoriamente ho un mutex unico, ma molto presto dovrò metterci mano. Voi come avete risolto? Da quello che ho capito bisogna trovare un modo per decidere una specie di partizione degli elementi della tabella hash, e poi affidare ogni parte ad un mutex diverso. Ma in che modo di può essere sicuri di stabilire una partizione che non abbia sovrapposizioni?

Ad esempio può essere una accettabile l'idea di decidere un numero X e poi partizionare gli elementi in base al resto della divisione per X, cioè se elemento.chiave mod X = 0 fa parte del gruppo 0, se elemento.chiave mod X = 1 fa parte del gruppo 1, ecc, con un mutex per ogni gruppo) oppure c'è il rischio che ci siano comunque sovrapposizioni? Il punto è che l'implementazione della hash table è fornita dal prof e non so come lavori al suo interno.
Rispondi

Torna a “[SOL] Sistemi operativi e laboratorio”