Können sich konkurrierende atomare Operationen gegenseitig verhungern?

Question

Stellen Sie sich ein Programm mit zwei Threads vor. Sie laufen den folgenden Code (CAS bezieht sich auf Compare and Swap):

// Visible to both threads 
static int test; 

// Run by thread A 
void foo() 
{ 
    // Check if value is 'test' and swap in 0xdeadbeef 
    while(!CAS(&test, test, 0xdeadbeef)) {} 
} 

// Run by thread B 
void bar() 
{ 
    while(1) { 
     // Perpetually atomically write rand() into the test variable 
     atomic_write(&test, rand()); 
    } 
} 

Ist es möglich, für Thread B ständig auf Thread A des CAS verursachen, so zum Scheitern verurteilt, dass 0xDEADBEEF nie auf ‚Test‘ geschrieben? Oder bedeutet natürlicher Planungs-Jitter, dass dies in der Praxis nie passiert? Was ist, wenn etwas in der While-Schleife von Thread A getan wurde?

Answer 1

Als theoretische Angelegenheit, ja. Wenn Sie es irgendwie schaffen könnten, die beiden Threads im Lockstep zu starten, so würde das

Dann würde CAS niemals wahr zurückgeben.

In der Praxis wird dies nie passieren, wenn Threads ein CPU/Core-teilen, und es ist unwahrscheinlich geschehen, wenn Threads auf verschiedenen CPUs oder Cores ausgeführt werden. In der Praxis ist es unglaublich unwahrscheinlich für mehr als ein paar Zyklen zu passieren, und astronomisch unwahrscheinlich für mehr als ein Scheduler Quantum passieren.

Und das ist, wenn dieser Code

void foo() 
{ 
    // Check if value is 'test' and swap in 0xdeadbeef 
    while(!CAS(&test, test, 0xdeadbeef)) {} 
} 

tut, was es zu tun wird, was den aktuellen Wert von test, zu holen ist und vergleichen Sie es mit test zu sehen, ob sie sich geändert hat. In der realen Welt würden Iterationen von CAS durch Code getrennt, der tatsächlich funktioniert hat. Das Schlüsselwort volatile wäre erforderlich, um sicherzustellen, dass der Compiler den Test vor dem Aufruf von CAS abgerufen hat, anstatt anzunehmen, dass eine Kopie, die es noch in einem Register hätte, immer noch gültig wäre.

Oder der Wert, den Sie gegen würde testen wäre nicht der aktuellen Wert von Test sein, sondern eher eine Art zuletzt bekannt Wert. Mit anderen Worten, dieses Codebeispiel ist ein Test der Theorie, aber Sie würden CAS in der Praxis nicht so verwenden, also selbst wenn Sie dies zum Scheitern bringen könnten, sagt es Ihnen nicht unbedingt, wie es gehen könnte scheitern, wenn sie in realen Algorithmen verwendet werden.

Answer 2

Starvation kann sicher in solchen Fällen geschehen. Zitiert the wikipedia page,

Es wird auch, dass der weithin verfügbare Atom-bedingte Primitiven, CAS und LL/SC gezeigt worden ist, kann nicht Hunger freien Implementierungen von vielen gemeinsamen Daten Strukturen ohne Speicherkosten bieten wachsen linear in der Anzahl der Threads. Wartefreie Algorithmen sind daher selten, sowohl in der Forschung als auch in der Praxis .

(Siehe den Link von der betreffenden Seite für den mathematischen Beweis).