Sezioni critiche con processori multicore

Question

Con un processore single-core, in cui tutti i thread vengono eseguiti da una singola CPU, l'idea di implementare una sezione critica utilizzando un'operazione di test-and-set atomico su alcuni mutex (o semaforo o ecc) in memoria sembra abbastanza semplice; Poiché il tuo processore sta eseguendo un test-and-set da un punto del tuo programma, non può necessariamente farlo da un altro punto del tuo programma mascherato come un altro thread.

Ma cosa succede quando si dispone di più di un processore fisico? Sembra che la semplice atomicità a livello di istruzione non sia sufficiente, b/c con due processori che eseguono potenzialmente le operazioni di test-and-set contemporaneamente, ciò di cui si ha realmente bisogno per mantenere l'atomicità è l'accesso alla posizione di memoria condivisa del mutex. (E se la posizione della memoria condivisa è caricata nella cache, c'è anche l'intera consistenza della cache da trattare ..)

Questo sembra comportare molto più sovraccarico del caso single core, quindi ecco la carne di la domanda: quanto peggio è? È peggio? Viviamo semplicemente con esso? O aggirarlo applicando una politica che tutti i thread all'interno di un gruppo di processi devono vivere sullo stesso nucleo fisico?

Answer 1

I sistemi multi core/SMP non sono solo diverse CPU incollate insieme. C'è un supporto esplicito per fare le cose in parallelo. Tutte le primitive di sincronizzazione sono implementate con l'aiuto dell'hardware lungo le linee di atomic CAS. L'istruzione blocca il bus condiviso dalle CPU e dal controller di memoria (e dai dispositivi che eseguono DMA) e aggiorna la memoria, o semplicemente aggiorna la memoria basandosi su cache snooping. Ciò a sua volta causa l'algoritmo cache coherency per forzare tutte le parti coinvolte a svuotare le loro cache.

Disclaimer - questa è una descrizione molto semplice, ci sono cose più interessanti qui come cache virtuali o fisiche, politiche di writeback della cache, modelli di memoria, recinzioni ecc.

Se vuoi sapere di più su come Il sistema operativo potrebbe utilizzare queste funzionalità hardware: ecco l'argomento an excellent book sull'argomento.

Answer 2

Avresti bisogno di un test-and-set che costringa il processore a notificare tutti gli altri core dell'operazione in modo che siano consapevoli. Sì, questo introduce un overhead e devi conviverci. È un motivo per progettare applicazioni multithread in modo tale da non attendere troppo spesso le primitive di sincronizzazione.

Answer 3

Bene, a seconda del tipo di computer che si dispone in giro per casa, effettuare le seguenti operazioni: Scrivere una semplice applicazione multithread. Esegui questa applicazione su un singolo core (Pentium 4 o Core Solo) e poi eseguilo su un processore multicore (Core 2 Duo o simile) e scopri quanto è grande la velocità.

Concesso questi sono confronti ingiusti poiché Pentium 4 e Core Solo sono molto più lenti a prescindere dal core di un Core 2 Duo. Forse confrontare tra un Core 2 Duo e un Core 2 Quad con un'applicazione che può utilizzare 4 o più thread.

Si alza un numero di punti validi. I processori Muliple introducono un sacco di mal di testa e sovraccarico. Tuttavia, dobbiamo solo convivere con loro, perché l'aumento di velocità del parallelismo può superarli di gran lunga, se le sezioni critiche sono sufficientemente lunghe.

Per quanto riguarda il suggerimento finale sull'avere tutti i thread sullo stesso core fisico, ciò sconfigge completamente il punto di un computer multi-core!

Answer 4

Oppure aggirarlo applicando una politica che tutti i thread all'interno di un gruppo di processi devono vivere sullo stesso nucleo fisico?

Questo annullerebbe l'intero punto del multithreading. Quando si utilizza un blocco, un semaforo o altre tecniche di sincronizzazione, si sta facendo affidamento sul sistema operativo per assicurarsi che queste operazioni siano interbloccate, indipendentemente dal numero di core che si stanno utilizzando.

Il tempo di passare a un thread diverso dopo che è stato rilasciato un blocco è determinato principalmente dal costo di un interruttore di contesto. This SO thread si occupa del sovraccarico di commutazione del contesto, quindi potresti volerlo controllare.

Ci sono alcune altre discussioni interessanti anche:

• What are the differences between various threading synchronization options in C#?
• Threading best practices

si dovrebbe leggere questo articolo di MSDN anche: Understanding the Impact of Low-Lock Techniques in Multithreaded Apps.

Answer 5

Il fornitore di cpus multi-core deve fare in modo che i diversi core si coordinino durante l'esecuzione di istruzioni che garantiscono l'accesso alla memoria atomica.

Sui chip intel, ad esempio, si dispone dell'istruzione "cmpxchg". Confronta il valore memorizzato in una posizione di memoria con un valore previsto e lo scambia per il nuovo valore se i due corrispondono. Se lo precedi con l'istruzione 'lock', è garantito che sia atomico rispetto a tutti i core.

Answer 6

Gli accessi di memoria sono gestiti dal controller di memoria che dovrebbe occuparsi di problemi multi-core, ovvero non dovrebbe consentire l'accesso simultaneo agli stessi indirizzi (probabilmente gestito dalla pagina di memoria o dalla linea di memoria). Quindi puoi usare un flag per indicare se un altro processore sta aggiornando il contenuto della memoria di qualche blocco (questo per evitare un tipo di lettura sporca in cui una parte del record viene aggiornata, ma non tutto).

Una soluzione più elegante consiste nell'utilizzare un blocco semaforo HW se il processore ha tale caratteristica. Un semaforo HW è una coda semplice che potrebbe essere di dimensione no_of_cores -1. Ecco come funziona il processore 6487/8 di TI. È possibile interrogare direttamente il semaforo (e eseguire il ciclo fino a quando non viene rilasciato) oppure eseguire una query indiretta che genererà un'interruzione una volta che il core avrà ottenuto la risorsa. Le richieste vengono accodate e pubblicate nell'ordine in cui sono state create. Una query del semaforo è un'operazione atomica.

La coerenza della cache è un altro problema e in alcuni casi potrebbe essere necessario eseguire writeback e aggiornamenti della cache. Ma questa è una cosa specifica per l'implementazione della cache. Con 6487/8 avevamo bisogno di farlo su poche operazioni.