Les opérations atomiques concurrentes peuvent-elles s'affaiblir les unes les autres?

Question

Imaginez un programme avec deux threads. Ils sont en cours d'exécution le code suivant (CAS fait référence à 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()); 
    } 
} 

Est-il possible pour le fil B pour provoquer perpétuellement CAS de fil A à l'échec de telle sorte que 0xdeadbeef est jamais écrit « test »? Ou est-ce que la gigue d'ordonnancement naturel signifie que dans la pratique cela n'arrive jamais? Que faire si un travail a été fait à l'intérieur de la boucle while du thread A?

Answer 1

En théorie, oui. Si vous pouviez gérer d'une façon ou d'une autre pour obtenir les deux threads fonctionnant comme ceci:

Alors CAS ne reviendrait jamais vrai.

En pratique, cela n'arrivera jamais lorsque des threads partagent un CPU/Core, et il est peu probable que cela se produise lorsque des threads sont exécutés sur des processeurs ou des cœurs différents. En pratique, c'est incroyablement improbable pour plus de quelques cycles, et astronomiquement peu probable pour plus d'un quantum de planificateur.

Et c'est si ce code

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

fait ce qu'il semble faire, ce qui est de récupérer la valeur actuelle de test, et le comparer à test pour voir si elle a changé. Dans le monde réel, les itérations de CAS seraient séparées par un code qui a réellement fonctionné. Le mot-clé volatile serait nécessaire pour s'assurer que le compilateur récupérait le test avant d'appeler CAS plutôt que de supposer qu'une copie qu'il pourrait encore avoir dans un registre serait toujours valide.

Ou la valeur que vous testerez contre ne serait pas la valeur actuelle de test, mais plutôt une sorte de dernière connue valeur. En d'autres termes, cet exemple de code est un test de la théorie, mais vous n'utiliseriez pas CAS comme ça en pratique, donc même si vous pouviez faire échouer cela, cela ne vous dit pas nécessairement comment il pourrait échouer lorsqu'il est utilisé dans des algorithmes du monde réel.

Answer 2

La famine peut sûrement arriver dans de tels cas. Citant the wikipedia page,

Il a également été démontré que les conditionnelles atomiques largement disponibles primitives, CAS et LL/SC, ne peuvent pas fournir sans famine mises en œuvre de nombreuses données communes structures sans coûts de mémoire de plus en plus linéairement dans le nombre de threads . Algorithmes sans attente sont donc rares, à la fois dans la recherche et en pratique.

(Voir le lien de la page en question pour la preuve mathématique).