Quote:Original post by ToohrVyk
Thread B begins a transaction for the same value, modifies the value,
OK.
Quote:then it checks if another transaction already committed and gets the answer "no",
Exactly after this point, the value is changed by another thread.
Quote: so it prepares to commit.
And you commited stale value.
Thread A also determines that no commit happened yet,After exactly this point, the change happens.
Quote:and so it commits its modification.
And it too commits stale value.
Quote:Thread B commits its modification.
During which point, actual value may be anything, since two threads already modified the data in between.
Quote:So, the modifications from Thread A were dropped.
No, they succeeded, since atomic swap doesn't prevent other threads from moving on, and atomic swap succeeded.
The problem here isn't in atomic swap, those can check for validity. The problem lies in the fact that there's no transaction-wide guarantees.
if (atomic_compare(a,b)) { commit();}
is not safe, unless entire statement is within a lock, or it atomic_compare is commit by itself. But as soon as you have two statements, you no longer have transactional guarantees.
To me, this sounds exactly like the problem with the following:
LockelssLinkedList ll;1) ll.add("An Item");2) assert(ll.pop_first() == "An Item");3) assert(ll.count() == 0);
Though modifications are lock-less, the whole algorithm isn't a transaction.
Count() is a nice example of an operation which is hard/impossible to implement on lock-less structures, or at best, has no real meaning. Although the list maintains integrity through entire process, the users operate on some non-deterministic data set.
One problem that arises in relation to this is how to dynamically allocate the data (internal nodes) used by linked list. Even though you attempt to delete a pointer you retrieved from the list, there's no guarantee those contents are not being currently accessed by another thread within the LinkedList.
IMHO, the whole system sounds like STM, and those are notoriously hard to get working right, especially with decent performance during contention. But it's been a while since I checked on progress, perhaps something has changed.
Then again, I could be missing something.
