Gli spinlock sono una buona scelta per un allocatore di memoria?

Question

Ho suggerito ai manutentori del runtime del linguaggio di programmazione D alcune volte che l'allocatore di memoria/garbage collector dovrebbe utilizzare spinlock invece delle normali sezioni critiche del sistema operativo. Questo non ha davvero preso piede. Qui ci sono le ragioni per cui credo spinlocks sarebbe meglio:

1. Almeno in benchmark sintetici che ho fatto, è molte volte più veloce di sezioni critiche del sistema operativo quando c'è contesa per il blocco allocatore di memoria/GC. Modifica: Empiricamente, l'uso di spinlock non aveva nemmeno un sovraccarico misurabile in un ambiente single-core, probabilmente perché i lock devono essere mantenuti per un così breve periodo di tempo in un allocatore di memoria.
2. allocazioni di memoria e simili operazioni richiedono solitamente una piccola frazione di un timeslice, e anche una piccola frazione del tempo un interruttore contesto prende, rendendo stupido context switch nel caso di contesa.
3. Un garbage collection nell'implementazione in questione arresta il mondo comunque. Non ci sarà alcuna rotazione durante una raccolta.

Esistono buoni motivi non da utilizzare spinlocks in un'implementazione collettore allocatore di memoria/spazzatura?

Answer 1

In Windows in ogni caso, gli oggetti sezione critica hanno già la possibilità di fare questo (http://msdn.microsoft.com/en-us/library/ms682530.aspx):

Un thread utilizza l'InitializeCriticalSectionAndSpinCount o la funzione SetCriticalSectionSpinCount per specificare un conteggio di rotazione per l'oggetto sezione critica. Rotazione significa che quando un thread tenta di acquisire una sezione critica che è bloccata, il thread entra in un ciclo, controlla se il blocco è stato rilasciato e se il blocco non viene rilasciato, il thread va in sospensione. Nei sistemi a processore singolo, il conteggio degli spin viene ignorato e il conteggio degli spin delle sezioni critiche è impostato su 0 (zero). Nei sistemi multiprocessore, se la sezione critica non è disponibile, il thread chiamante fa girare dwSpinCount volte prima di eseguire un'operazione di attesa su un semaforo associato alla sezione critica. Se la sezione critica diventa libera durante l'operazione di spin, il thread chiamante evita l'operazione di attesa.

Speriamo che altre piattaforme seguiranno l'esempio se non lo fanno già.

Answer 2

Gli spinlock sono assolutamente inutili su sistemi con una sola CPU/core o, più in generale, in situtations con contesa elevata (quando ci sono molti thread in attesa sul blocco).

Answer 3

1. Ovviamente il comportamento nel caso peggiore di uno spinlock è terribile (lo scheduler del sistema operativo appena vede 30 thread di CPU-bound, quindi cerca di dare loro tutto un po 'tempo di CPU, 29 dei quali girare come matti mentre il thread che tiene chiusa la serratura), quindi dovresti evitarli se puoi. Un sacco di persone più intelligenti di me sostengono che gli spinlock hanno no casi di utilizzo dello spazio utente a causa di questo.

2. I mutex di sistema devono girare un po 'prima di mettere il thread in stop (o addirittura effettuare qualsiasi tipo di chiamata di sistema), in modo che a volte possano funzionare esattamente come gli spinlock anche quando c'è qualche contesa.

3. un allocatore può spesso praticamente eliminare il conflitto di blocchi utilizzando solo la serratura per allocare pagine fili. Ogni thread è quindi responsabile della partizione delle proprie pagine. Finisci per acquisire il blocco solo una volta ogni allocazione N e puoi configurare N in base alle tue esigenze.

Ritengo che 2 e 3 siano argomenti forti che non possono essere contrastati in modo efficace dai benchmark sintetici. Dovresti mostrare che le prestazioni di un programma reale ne soffrono.

Answer 4

Ci sono buone ragioni per non utilizzare gli spinlock in un'implementazione di allocatore di memoria/garbage collector?

Quando alcuni fili sono compute-bound (CPU-bound) e altri fili sono memoria allocatore-bound, quindi utilizzando spinlocks prende cicli di CPU che potrebbero essere utilizzati dal thread di elaborazione-bound e/o usati da fili che appartengono ad altri processi.

Answer 5

Non sono sicuro se sono d'accordo, dato che le allocazioni di memoria POSSONO impiegare molto tempo (l'unico modo in cui non lo fa se si prealloca tutta la memoria e poi lo si riemette) .. Hai davvero bisogno di provare le stesse allocazioni e deallocazioni dimensioni dell'heap mult gig con milioni di voci, con molte applicazioni colpiscono la sezione critica di allocazione (note applicazioni e non thread) e con il cestino cestinare/scambiare dalla memoria insufficiente. È anche possibile ottenere problemi di scambio del disco durante l'allocazione e fare un blocco di selezione in attesa di una richiesta di disco non è certamente appropriato.

E come CyberShadow menzionato sulla CPU a thread singolo si finisce per andare a un normale blocco con un sovraccarico. Ora una lingua può essere eseguita su molti CPUS incorporati che sono tutti a thread singolo.

Anche se si riesce a scappare con uno scambio interbloccato, è meglio (dato che è senza serratura, ma blocca ancora la CPU e solleva LOCK # per la memoria multi core) ma la maggior parte dei lock lo usa comunque (ma è necessario fare di più) . Tuttavia, la struttura di un heap normalmente significa che uno scambio interbloccato non è sufficiente e si finisce per creare una sezione critica. Si noti che è possibile in una scuola materna Mark Sweep (generazionale) con un GC per fare assegnazioni come confronto interbloccato e aggiunta del puntatore. Lo faccio per il GC OS Cosmos C# e rende per le allocazioni di velocità dello stack.

Answer 6

Uno degli insetti perfus nel garbage collector del Glasgow Haskell Compiler è così fastidioso che ha un nome, "last core slowdown". Questa è una diretta conseguenza del loro uso inappropriato di spinlock nel loro GC ed è aggravata su Linux a causa del suo scheduler, ma, in effetti, l'effetto può essere osservato ogni volta che altri programmi sono in competizione per il tempo della CPU.

L'effetto è evidente sul secondo grafico here e può essere visto non solo nell'ultimo core here, dove il programma Haskell vede il degrado delle prestazioni oltre i soli 5 core.