È la mia implementazione spin lock corretta e ottimale?

StackOverflow https://stackoverflow.com/questions/1383363

Domanda

Io sto usando un blocco di selezione per proteggere una sezione molto piccola critica. Contention accade molto raramente così un blocco di selezione è più appropriato di un mutex regolare.

Il mio codice attuale è la seguente, e non si assume x86 e GCC: 

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

Quindi mi chiedo:

  • E 'questo codice corretto? Ha garantire il corretto la mutua esclusione?
  • Funziona su tutti i sistemi operativi x86?
  • Funziona su x86_64 troppo? Su tutti i sistemi operativi?
  • E 'ottimale?
    • Ho visto implementazioni spin lock utilizzando confrontare-e-swap, ma non sono sicuro che è meglio.
    • In base alla documentazione di GCC builtins atomiche ( http: //gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html ) c'è anche __sync_lock_release. Io non sono un esperto di barriere di memoria, quindi non sono sicuro se va bene per me di utilizzare questo invece di __sync_synchronize.
    • Sto ottimizzazione per il caso in cui non c'è conflitto.

Non mi interessa a tutti su contesa. Ci possono essere 1, forse 2 altri thread che cercano di bloccare il blocco di selezione una volta ogni pochi giorni .

È stato utile?

Soluzione

Quindi mi chiedo: 

* Is it correct?

Nel contesto citato, direi di sì. 

* Is it optimal?

Questa è una domanda caricato. Reinventando la ruota si sono anche reinventare un sacco di problemi che sono stati risolti da altre implementazioni

  • mi aspetto un ciclo dei rifiuti in caso di fallimento in cui non si sta cercando di accedere alla parola di blocco.

  • L'utilizzo di una barriera completa nella sblocco ha solo bisogno di avere la semantica di rilascio (è per questo che usereste __sync_lock_release, in modo che si otterrebbe st1.rel su Itanium, invece di MF, o di un lwsync su PowerPC, ...). Se davvero a cuore solo x86 o x86_64 i tipi di barriere utilizzati qui o no non importa tanto (ma se si dove fare il salto di Itanium di Intel per una porta HP-IPF allora non vorrebbe questo).

  • non si ha l'istruzione di pausa () che che normalmente si mette prima che il ciclo dei rifiuti.

  • quando c'è contesa che si desidera qualcosa , semop, o anche un sonno muto in preda alla disperazione. Se si ha realmente bisogno le prestazioni che questo si acquista quindi il suggerimento futex è probabilmente una buona. Se avete bisogno di prestazioni questa acquista abbastanza cattivo per mantenere di questo codice si hanno un sacco di ricerca da fare.

Si noti che non vi era un commento che dice che la barriera di rilascio non è stata richiesta. Questo non è vero nemmeno su sistemi x86 perché la barriera di rilascio serve anche come istruzione al compilatore di non mischiare altri accessi alla memoria intorno al "barriera". Molto simile a quello che si otterrebbe se si è utilizzato asm ( "" ::: "memoria"). 

* on compare and swap

Il 86 lo sync_lock_test_and_set sarà mappare ad un'istruzione xchg che ha un prefisso di blocco implicita. Sicuramente il codice generato più compatto (esp. Se si utilizza un byte per la "parola di blocco" invece di un int), ma non per questo meno corretto che se si è utilizzato BLOCCO cmpxchg. Uso di confronto e swap può essere utilizzato per algorthims più elaborate (come mettere un non-zero puntatore ai metadati per la prima "cameriere" nel lockword in caso di fallimento).

Altri suggerimenti

guarda bene a me. Btw, qui è la libro di testo implementazione che è più efficiente anche nel caso sostenuto. 

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

In risposta alle tue domande:

  1. Looks ok per me
  2. Supponendo che il sistema operativo supporta GCC (e GCC ha le funzioni implementate); questo dovrebbe funzionare su tutti i sistemi operativi x86. La documentazione GCC suggerisce che un avvertimento sarà prodotto se non sono supportati su una determinata piattaforma.
  3. Non c'è niente x86-64 specifico qui, quindi non vedo perché no. Questo può essere esteso a qualsiasi un'architettura che supporta GCC, tuttavia ci forse più modi ottimali di raggiungere questo su architetture non x86.
  4. potrebbe essere leggermente meglio con l'utilizzo __sync_lock_release() nel caso unlock(); come questo sarà diminuire il blocco e aggiungere una barriera di memoria in una sola operazione. Tuttavia, supponendo che la tua affermazione che non ci sarà raramente contesa; si guarda bene a me.

Se siete su una versione recente di Linux, si può essere in grado di utilizzare un futex - un "mutex veloce userspace":

  

Un blocco futex-based correttamente programmato non utilizzerà chiamate di sistema, tranne quando il blocco è conteso

Nel caso incontrastato, che si sta cercando di ottimizzare per il tuo spinlock, il futex si comporterà esattamente come uno spinlock, senza la necessità di una chiamata di sistema del kernel. Se il blocco è contestata, l'attesa si svolge nel kernel senza busy-attesa.

Mi chiedo se la seguente implementazione CAS è quella corretta in x86_64. E 'quasi due volte più veloce sul mio i7 X920 portatile (Fedora 13 x86_64, GCC 4.4.5). 

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

Non posso commentare sulla correttezza, ma il titolo della tua domanda sollevato una bandiera rossa, prima ancora di leggere il corpo domanda. primitive di sincronizzazione sono diabolicamente difficili da garantire la correttezza ... se possibile, è meglio utilizzare un ben progettato biblioteca / mantenuto, forse pthreads o spinta: :. filo

Un miglioramento è suggerire sta utilizzando Tatas (test-e-test -e-set). Usando operazioni CAS sono considerate piuttosto costoso per il processore, quindi è preferibile evitare, se possibile. Un'altra cosa, assicurarsi che non si soffre di inversione di priorità (cosa succede se un thread con una priorità alta tenta di acquisire il blocco, mentre un thread con bassa priorità tenta di liberare la serratura? In Windows, ad esempio questo problema in ultima analisi, da parte risolto da lo scheduler con una spinta di priorità, ma è possibile in modo esplicito rinunciare intervallo di tempo del tuo thread nel caso in cui non si è riuscito ad acquisire il blocco in voi ultimi 20 tentativi (per esempio ..)

La procedura di sblocco non ha bisogno della barriera di memoria; l'assegnazione ad esclusione è atomico finché DWORD allineato a x86.

Nel caso specifico di X 86 (32/64) non credo che avete bisogno di un recinto di memoria a tutti nel codice di sblocco. 86 non fa alcun riordino, eccetto che memorizza vengono prima messi in un buffer negozio e così li diventare visibile può essere ritardato per altri thread. E un filo che fa un negozio e quindi legge dal medesimo variabile leggerà dal buffer negozio se non è ancora stato lavato a memoria. Quindi tutto ciò che serve è una dichiarazione asm per prevenire reorderings compilatore. Si corre il rischio di un thread che detiene il blocco leggermente più lungo del necessario dal punto di vista di altri thread, ma se non si cura di contesa che non dovrebbe importare. In realtà, pthread_spin_unlock viene implementato come quello sul mio sistema (Linux x86_64).

Il mio sistema implementa anche pthread_spin_lock utilizzando lock decl lockvar; jne spinloop; invece di utilizzare xchg (che è ciò che __sync_lock_test_and_set usi), ma non so se ci sia effettivamente una differenza di prestazioni.

Ci sono alcune ipotesi sbagliate.

In primo luogo, SpinLock ha senso solo se ressource è bloccata su un altro CPU. Se ressource è bloccata sulla stessa CPU (che è sempre il caso dei sistemi monoprocessore), è necessario per rilassarsi di pianificazione al fine di sblocco ressource. Si codice corrente lavorerà su sistemi monoprocessore a causa di pianificazione passa compiti automaticamente, ma è uno spreco di ressource.

Il sistema multi-processore, stessa cosa può happends, ma compito possono migrare da una CPU all'altra. In breve, l'uso di spin lock è corretta se si garantiamo che le attività verrà eseguito su un'altra CPU.

In secondo luogo, il bloccaggio di un mutex è veloce (veloce come spinlock) quando si è sbloccato. Mutex bloccaggio (e sbloccare) è lento (molto lento) solo se mutex è già bloccato.

Quindi, nel tuo caso, suggerisco di usare i mutex.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top