Come sincronizzare l'accesso a molti oggetti

Question

Ho un pool di thread con alcuni thread (ad esempio un numero di core) che funzionano su molti oggetti, ad esempio migliaia di oggetti. Normalmente darei a ciascun oggetto un mutex per proteggere l'accesso ai suoi interni, bloccarlo quando lavoro, quindi rilasciarlo. Quando due thread tentano di accedere allo stesso oggetto, uno dei thread deve attendere.

Ora voglio salvare alcune risorse ed essere scalabile, poiché potrebbero esserci migliaia di oggetti e ancora solo una mano piena di thread. Sto pensando a un design di classe in cui il thread ha una sorta di oggetto mutex o lock e assegna il blocco all'oggetto quando è necessario accedere all'oggetto. Ciò farebbe risparmiare risorse, poiché ho solo tanti oggetti di blocco quanti thread ho.

Ora arriva la parte di programmazione, in cui voglio trasferire questo disegno in codice, ma non so da dove iniziare. Sto programmando in C++ e voglio usare le classi Boost laddove possibile, ma le classi autoprodotte che gestiscono questi requisiti speciali sono ok. Come potrei implementarlo?

La mia prima idea era di avere un boost :: oggetto mutex per thread, e ogni oggetto ha un boost :: shared_ptr che inizialmente è unset (o NULL). Ora quando voglio accedere all'oggetto, lo blocco creando un oggetto scoped_lock e assegnandolo a shared_ptr. Quando shared_ptr è già impostato, attendo sul blocco corrente. Questa idea sembra un mucchio pieno di condizioni di gara, quindi l'ho quasi abbandonato. C'è un altro modo per realizzare questo design? Un modo completamente diverso?

Modifica: La descrizione precedente è un po 'astratta, quindi aggiungo un esempio specifico. Immagina un mondo virtuale con molti oggetti (pensa> 100.000). Gli utenti che si spostano nel mondo potrebbero spostarsi attraverso il mondo e modificare gli oggetti (ad esempio, sparare frecce ai mostri). Quando si utilizza solo un thread, sto bene con una coda di lavoro in cui le modifiche agli oggetti vengono accodate. Voglio un design più scalabile, però. Se sono disponibili 128 processori principali, voglio utilizzare tutti i 128, quindi utilizzare quel numero di thread, ciascuno con code di lavoro. Una soluzione sarebbe utilizzare la separazione spaziale, ad es. usa un lucchetto per un'area. Ciò potrebbe ridurre il numero di blocchi utilizzati, ma sono più interessato se esiste un design che consente di risparmiare il maggior numero di blocchi possibile.

Answer 1

È possibile utilizzare un pool di mutex anziché allocare un mutex per risorsa o un mutex per thread. Quando vengono richiesti i mutex, prima controlla l'oggetto in questione. Se ha già un mutex taggato su di esso, blocca su quel mutex. Altrimenti, assegna un mutex a quell'oggetto e segnalalo, togliendo il mutex dal pool. Una volta che il mutex è non segnalato, svuota lo slot e riporta il mutex al pool.

Answer 2

Se seguo correttamente ....

struct table_entry { 
    void * pObject;  // substitute with your object 
    sem_t sem;   // init to empty 
    int  nPenders; // init to zero 
}; 

struct table_entry * table; 

object_lock (void * pObject) { 
    goto label;     // yes it is an evil goto 

    do { 
     pEntry->nPenders++; 
     unlock (mutex); 
     sem_wait (sem); 
label: 
     lock (mutex); 
     found = search (table, pObject, &pEntry); 
    } while (found); 

    add_object_to_table (table, pObject); 
    unlock (mutex); 
} 

object_unlock (void * pObject) { 
    lock (mutex); 
    pEntry = remove (table, pObject); // assuming it is in the table 
    if (nPenders != 0) { 
     nPenders--; 
     sem_post (pEntry->sem); 
    } 
    unlock (mutex); 
} 

È possibile che questo dovrebbe funzionare, ma ha alcuni svantaggi potenziali, come ...

1. Un possibile collo di bottiglia nella ricerca.
2. Fame da fame. Non vi è alcuna garanzia che un dato thread uscirà dal ciclo do-while in object_lock().

Tuttavia, a seconda della configurazione, questi potenziali svantaggi potrebbero non avere importanza.

Spero che questo aiuti.

Answer 3

Dubito che ci sia un modo pulito per realizzare il tuo progetto. Il problema che l'assegnazione del mutex all'oggetto sembra che modificherà il contenuto dell'oggetto - quindi è necessario un mutex per proteggere l'oggetto da diversi thread che provano ad assegnarvi i mutex contemporaneamente, quindi per mantenere il primo assegnamento di mutex sicuro, avresti bisogno di un altro mutex per proteggere il primo.

Personalmente, penso che quello che stai cercando di curare probabilmente non è un problema in primo luogo. Prima di passare molto tempo a provare a sistemarlo, farei un po 'di test per vedere cosa (se non altro) perdi semplicemente includendo un Mutex in ogni oggetto e finendo con esso. Dubito che dovrai andare oltre.

Se è necessario fare più di questo, penso di avere un pool di oggetti sicuro per i thread e ogni volta che un thread vuole operare su un oggetto, deve ottenere la proprietà da quel pool. La chiamata per ottenere la proprietà dovrebbe rilasciare qualsiasi oggetto attualmente posseduto dal thread richiedente (per evitare deadlock), e quindi dargli la proprietà dell'oggetto richiesto (blocco se l'oggetto è attualmente di proprietà di un altro thread). Il gestore del pool di oggetti probabilmente opererebbe in un thread da solo, serializzando automaticamente tutti gli accessi alla gestione del pool, così il codice di gestione del pool potrebbe evitare di dover bloccare l'accesso alle variabili dicendogli chi possiede attualmente quale oggetto e così via.

Answer 4

Personalmente, ecco cosa vorrei fare. Hai un numero di oggetti, tutti probabilmente hanno una chiave di qualche tipo, dì nomi. In modo da prendere il seguente elenco di nomi di persone:

Bill Clinton 
Bill Cosby 
John Doe 
Abraham Lincoln 
Jon Stewart 

Così ora si potrebbe creare una serie di elenchi: uno per ogni lettera dell'alfabeto, dire. Bill e Bill sarebbero andati in una lista, John, Jon Abraham tutto da soli.

Ogni elenco dovrebbe essere assegnato a un thread specifico - l'accesso dovrebbe passare attraverso quel thread (si dovranno eseguire operazioni di marshalling su un oggetto su quel thread - un grande uso di funtori). Allora avete solo due posti per bloccare:

thread() { 
     loop { 
     scoped_lock lock(list.mutex); 
     list.objectAccess(); 
     } 
} 

list_add() { 
     scoped_lock lock(list.mutex); 
     list.add(..); 
} 

Mantenere le serrature al minimo, e se si sta ancora facendo un sacco di bloccaggio, è possibile ottimizzare il numero di iterazioni di eseguire sugli oggetti negli elenchi da 1 a 5, per ridurre al minimo la quantità di tempo trascorso all'acquisto di serrature. Se il tuo set di dati cresce o è digitato per numero, puoi fare qualsiasi quantità di dati separati per mantenere il blocco al minimo.

Answer 5

Mi sembra che tu abbia bisogno di una coda di lavoro. Se il blocco della coda di lavoro è diventato un collo di bottiglia, è possibile cambiarlo in modo che ogni thread abbia una propria coda di lavoro, quindi una sorta di scheduler darebbe all'oggetto in entrata il thread con il minimo lavoro da fare. Il livello successivo è il furto del lavoro in cui i thread che hanno esaurito il lavoro esaminano le code di lavoro di altri thread. (Vedi la libreria di thread building di Intel)

Answer 6

Senza saperlo, quello che cercavi è Software Memoria transazionale (STM).

I sistemi STM gestiscono internamente i blocchi necessari per garantire le proprietà ACI (Atomico, Coerente, Isolato). Questa è un'attività di ricerca. Puoi trovare molte librerie STM; in particolare sto lavorando su Boost.STM (la libreria non è ancora disponibile per il beta test e la documentazione non è realmente aggiornata, ma puoi giocare con). Ci sono anche alcuni compilatori che stanno introducendo TM in (come compilatori Intel, IBM e SUN). È possibile ottenere la bozza di specifica da here

L'idea è di identificare le regioni critiche come segue

transaction { 
    // transactional block 
} 

e lasciare che il sistema di STM per gestire con le serrature necessari per quanto assicura le proprietà ACI.

L'approccio Boost.STM lasciare che si scrive le cose come

int inc_and_ret(stm::object<int>& i) { 
    BOOST_STM_TRANSACTION { 
    return ++i; 
    } BOOST_STM_END_TRANSACTION 
} 

È possibile vedere la coppia BOOST_STM_TRANSACTION/BOOST_STM_END_TRANSACTION come un modo per determinare un blocco implicita ambito.

Il costo di questa pseudo trasparenza è di 4 byte di metadati per ogni oggetto stm ::.

Anche se questo è lontano dal tuo progetto iniziale, penso davvero che cosa c'era dietro il tuo obiettivo e la progettazione iniziale.

Answer 7

Qui abbiamo un interesse per un modello simile. Una soluzione che abbiamo considerato è quella di avere un blocco globale (o condiviso) ma utilizzato nel seguente modo:

• Un flag che può essere atomicamente impostato sull'oggetto. Se imposti il ​​flag, allora possiedi l'oggetto.
• Esegui l'azione, quindi ripristina la variabile e segnala (trasmetti) una variabile di condizione.
• Se l'acquisizione non è riuscita, attendere la variabile di condizione. Quando viene trasmesso, controlla il suo stato per vedere se è disponibile.

Sembra tuttavia che sia necessario bloccare il mutex ogni volta che si modifica il valore di questa variabile. Quindi c'è un sacco di blocco e sblocco, ma non è necessario mantenere il blocco per un lungo periodo.

Con un blocco "condiviso" si ha un blocco che si applica a più elementi. Dovresti usare una sorta di funzione "hash" per determinare quale mutex/variabile di condizione si applica a questa particolare voce.

Answer 8

Rispondi alla seguente domanda sotto il post di @ JohnDibling.

hai implementato questa soluzione? Ho un problema simile e vorrei sapere come hai risolto il rilascio del mutex in piscina. Voglio dire, come fai a sapere, quando rilasci il mutex, che può essere tranquillamente rimesso in coda se non sai se un altro thread lo trattiene?

da @LeonardoBernardini

---

Attualmente sto cercando di risolvere lo stesso tipo di problema. Il mio approccio è creare la propria struttura mutex (chiamarla counterMutex) con un campo contatore e il campo mutex risorsa reale. Quindi, ogni volta che provi a bloccare il counterMutex, prima incrementi il ​​contatore e poi blocchi il mutex sottostante. Quando hai finito, decrementi il ​​coutner e sblocchi il mutex, dopodiché controlla il contatore per vedere se è zero, il che significa che nessun altro thread sta tentando di acquisire il lock. Se è così, rimetti il ​​counterMutex in piscina. C'è una condizione di competizione durante la manipolazione del contatore? potresti chiedere La risposta è no. Ricorda che hai un mutex globale per garantire che solo una discussione possa accedere a coutnerMutex contemporaneamente.