How atomic is Compare and Swap against global variable in modern computer?

Viewed 124

Assume we implement in a modern programming language like C++. Let's say we have 5 threads t1 to t5, and we also have an array of timestamps TS[5] one for each thread. We also have a global timestamp GT which will increase gradually as the process runs. So now each of the five thread tx makes a local copy of TS[x] as local_ts and is trying to do a compare and swap on its timestamp CAS(&TS[x],local_ts,TS). Then my question is will the final timestamps in TS[5] reflect the order of when each thread's compare and swap actually takes place. For example, if a thread does CAS before another thread, its stored timestamp must be less than or equal to the other thread's timestamp. Please refer to the following as a simple code example in C++

TS timestamps[5];//assuming TS ia a class enclosing a long value.
TS GT=0;//it is periodically increased by another thread not shown here.

void work_load(int id){
    for(int i=0;i<10000;i++);//simulate the thread does some work
    TS local = timestamps[id];
    timestamps[id].compare_exchange_strong(local,GT,std::some_memotry_order);
//each thread reads other threads' entries in the array and does things accordingly to their values against its own value
}

void main(){
    for(int i=0;i<5;i++){
       std::thread t(work_load,i); 
    }
}

So the goal is to design a transactional system with no locks. Each transaction appends its updates to a record as deltas. In validation phase, a transaction needs to check its deltas against other deltas on the same records that may conflict. I'm trying to design a global data structure which records atomically when each transaction starts its commit phase so transactions can decide if they need to abort based on observing who makes the conflicting deltas.

1 Answers

So many thanks and kudos to the people in the comment section. So my question is answered. The atomic CAS does not include an atomic read of the value I want to replace with upon success. Basically CAS(&object, expected, new_value) does not include fetching new_value from the global variable as an operation within the atomic CAS. Read_modify_write only guarantees the atomicity on the target object.

Related