{"id":5272,"date":"2017-06-09T18:51:47","date_gmt":"2017-06-09T18:51:47","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/aba-a-is-not-the-same-as-a\/"},"modified":"2023-06-26T12:11:22","modified_gmt":"2023-06-26T12:11:22","slug":"aba-a-is-not-the-same-as-a","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/aba-a-is-not-the-same-as-a\/","title":{"rendered":"ABA – A is not the same as A"},"content":{"rendered":"

A common problem in concurrency is the so-called ABA problem. That means you read a value twice and each time it returns the same value A. Therefore you conclude that nothing changed in between. But you forgot the B.<\/p>\n

<\/p>\n

Let me first use a simple scenario to introduce the problem.<\/p>\n

<\/span>An analogy<\/span><\/h2>\n

The scenario consists of you sitting in a car and waiting that the traffic light becomes green. Green stands in our case for B, and red for A. What’s happening?<\/p>\n

    \n
  1. You look at the traffic light and it is red (A).<\/li>\n
  2. Because you are bored, you begin to check the news on your smartphone and forget the time.<\/li>\n
  3. You look once more at the traffic light. Damn, is still red (A).<\/li>\n<\/ol>\n

    Of course, the traffic light became green (B) between your two checks. Therefore, what seems to be one red phase was two.<\/p>\n

    What does this mean for threads (processes)? Now once more formal.<\/p>\n

      \n
    1. Thread 1 reads a variable var with value A.
      <\/span><\/li>\n
    2. Thread 1 is preempted, and thread 2 runs.<\/li>\n
    3. Thread 2 changes the variable var from A to B to A.<\/li>\n
    4. Thread 1 starts to execute and checks the value of variable var; because the value of variable var is the same, thread 1 continues with its work,<\/li>\n<\/ol>\n

      Often, that is a no-brainer. You can simply ignore it.<\/p>\n<\/p>\n

      <\/span>No-brainer<\/span><\/h2>\n

      Have a look at it here. The function fetch_mult<\/span> (1) multiplies a std::atomic<T>& shared<\/span> by mult<\/span>.<\/p>\n

      \n
      \/\/ fetch_mult.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <iostream><\/span>\r\n\r\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\r\nT fetch_mult(std::<\/span>atomic<<\/span>T>&<\/span> shared, T mult){                          \/\/ 1<\/span>\r\n  T oldValue =<\/span> shared.load();                                          \/\/ 2<\/span>\r\n  while<\/span> (!<\/span>shared.compare_exchange_strong(oldValue, oldValue *<\/span> mult));  \/\/ 3<\/span>\r\n  return<\/span> oldValue;\r\n}\r\n\r\nint<\/span> main(){\r\n  std::<\/span>atomic<<\/span>int<\/span>><\/span> myInt{5<\/span>};\r\n  std::<\/span>cout <<<\/span> myInt <<<\/span> std::<\/span>endl;          \r\n  fetch_mult(myInt,5<\/span>);\r\n  std::<\/span>cout <<<\/span> myInt <<<\/span> std::<\/span>endl;         \r\n}\r\n<\/pre>\n<\/div>\n
      The key observation is that there is a small time window between the reading of the old value T oldValue = shared.load<\/span> (2) and the comparison with the new value (3). Therefore, another thread can kick in and change the oldValue<\/span> from oldValue<\/span> to anotherValue<\/span> to oldValue<\/span> back. The anotherValue<\/span> is the B in ABA.<\/p>\n
      Often it makes no difference if the first read value is in the second read operation the original value. But in a lock-free concurrent data structure, ABA may have a great impact.<\/p>\n
      <\/span>A lock-free data structure<\/span><\/h2>\n
      I will not present here in detail a lock-free data structure. I will use a lock-free stack implemented as a singly linked list. The stack supports only two operations. <\/p>\n
        \n
      1. Pops the top object and returns a pointer to it.<\/span><\/li>\n
      2. Pushes the object specified to stack.<\/span><\/li>\n<\/ol>\n
        Let me describe in pseudo-code the pop operation to get an idea of the ABA problem. The pop operation performs, in essence, the following steps in a loop until the operation was successful.<\/p>\n
          \n
        1. Get the head node: head<\/strong><\/li>\n
        2. Get the subsequent node: headNext<\/strong><\/li>\n
        3. Make headNext<\/strong> to the new head if head<\/strong> is still the head of the stack<\/li>\n<\/ol>\n
          Here are the first two nodes of the stack:<\/p>\n
          \n
          Stack: TOP -><\/span> head -><\/span> headNext -> ...\r\n<\/pre>\n<\/div>\n
           <\/p>\n
          Let’s construct the ABA problem.<\/p>\n
          <\/span>ABA in action<\/span><\/h2>\n
          Let’s start with the following stack:<\/p>\n
          \n
          Stack: TOP -><\/span> A -><\/span> B -> C\r\n<\/pre>\n<\/div>\n
           <\/p>\n
          Thread 1 is active and wants to pop the head of stack.<\/p>\n