X86 CMPXCHG è atomico?

La documentazione di Intel a

http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf

dice

“Questa istruzione può essere utilizzata con un prefisso LOCK per consentire l’esecuzione dell’istruzione atomicamente.”

La mia domanda è

  1. CMPXCHG può funzionare con l’indirizzo di memoria? Dal documento sembra non esserlo, ma qualcuno può confermare che funziona solo con VALUE effettivi nei registri, non nell’indirizzo di memoria?

  2. Se CMPXCHG non è atomico e un livello linguistico di alto livello CAS deve essere implementato tramite LOCK CMPXCHG (con prefisso LOCK), qual è lo scopo di introdurre una simile istruzione?

Stai confondendo i blocchi di alto livello con la funzione CPU di basso livello che si chiamava LOCK .

I blocchi di alto livello che gli algoritmi lock-free cercano di evitare possono proteggere frammenti di codice arbitrari la cui esecuzione può richiedere tempo arbitrario e quindi, questi blocchi dovranno mettere i thread in stato di attesa fino a quando il blocco è disponibile che è un’operazione costosa, ad esempio implica mantenere una fila di thread in attesa.

Questa è una cosa completamente diversa dalla funzione di prefisso CPU LOCK che protegge una sola istruzione e quindi potrebbe contenere altri thread per la durata di quella singola istruzione. Poiché questo è implementato dalla CPU stessa, non richiede sforzi software aggiuntivi.

Pertanto la sfida nello sviluppo di algoritmi lock-free non è la rimozione della sincronizzazione completamente, ma si riduce a ridurre la sezione critica del codice a una singola operazione atomica che verrà fornita dalla CPU stessa.

Sembra parte di quello che stai veramente chiedendo è:

Perché il prefisso di lock non è implicito per cmpxchg con un operando di memoria, come per xchg ?

La semplice risposta (che altri hanno dato) è semplicemente che Intel l’ha progettata in questo modo. Ma questo porta alla domanda:

Perché Intel l’ha fatto? Esiste un caso d’uso per cmpxchg senza lock ?

Su un sistema a singola CPU, cmpxchg è atomico rispetto ad altri thread o qualsiasi altro codice in esecuzione sullo stesso core della CPU . (Ma non per gli osservatori “di sistema” come un dispositivo I / O mappato in memoria, o un dispositivo che fa letture DMA di memoria normale, quindi lock cmpxchg era rilevante anche sui progetti CPU uniprocessore).

Gli interruttori di contesto possono essere eseguiti solo su interrupt e gli interrupt si verificano prima o dopo un’istruzione, non nel mezzo. Qualsiasi codice in esecuzione sulla stessa CPU vedrà il cmpxchg come completamente eseguito o non del tutto .


Ad esempio, il kernel di Linux è normalmente compilato con il supporto SMP, quindi usa lock cmpxchg per CAS atomico. Ma quando viene avviato su un sistema a processore singolo, patcherà il prefisso di lock a un nop ovunque il codice sia stato allineato, poiché nop cmpxchg è molto più veloce di lock cmpxchg . Per maggiori informazioni, vedi questo articolo di LWN sul sistema “SMP alternative” di Linux . Può anche eseguire il patchback per lock prefissi prima di colbind a caldo una seconda CPU.

Per saperne di più sull’atomicità delle singole istruzioni sui sistemi uniprocessore in questa risposta , e nella risposta @ + risposta di supercat su Can num++ essere atomico per int num . Vedi la mia risposta lì per un sacco di dettagli su come l’atomicità funziona davvero / è implementata per le istruzioni read-modify-write come lock cmpxchg .


(Questo stesso ragionamento si applica anche a cmpxchg8b / cmpxchg16b e xadd , che di solito viene utilizzato solo per operazioni di synchonization / atomic, per non rendere il codice a thread singolo eseguito più velocemente Ovviamente la memoria di destinazione add [mem], reg è utile al di fuori del lock add [mem], reg case.)

Il prefisso LOCK serve per bloccare l’accesso alla memoria per il comando corrente, in modo che altri comandi che si trovano nella pipeline della CPU possano accedere alla memoria in questo momento. Utilizzando il prefisso LOCK, l’esecuzione del comando non verrà interrotta da un altro comando nella pipeline della CPU a causa dell’accesso alla memoria di altri comandi che vengono eseguiti contemporaneamente. Il manuale INTEL dice:

Il prefisso LOCK può essere anteposto solo al seguente nelle struction e solo a quelle forms delle istruzioni in cui l’operando di destinazione è un operando di memoria: ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC , NEG, NOT, OR, SBB, SUB, XOR, XADD e XCHG. Se il prefisso LOCK viene utilizzato con una di queste istruzioni e l’operando di origine è un operando di memoria, può essere generata un’eccezione opcode non definita (#UD).