Previous | Next --- Slide 36 of 64
Back to Lecture Thumbnails
TomoA

This code, when replaced with atomic, will livelock. Thread 1 will try to read from flagB, and when thread 2 writes to flagB, thread 1 will have to restart, and then the reverse happens. The main issue is that we can't leak out state from an atomic block while we can from a critical section, so thread 2 can't show thread 1 only its write without the reads and vice versa.

qqkk

When we use atomicCAS() to implement other atomic operations, we usually use a while loop to make sure the subject is not changed during the call. If it's changed, the whole process will restart. I think this kind of helps explain why there's a livelock, instead of deadlock.

maxdecmeridius

@TomoA Why does thread 1 restart when thread 2 writes to flagB? I don't really see where that happens in the code. I don't understand why this code will create a livelock situation.

TomoA

@maxdecmeridius That's the definition of a transaction (atomic block), see the other slides in this lecture on the implementation details.

mallocanswer

Hi @TomoA, can I use isolation to explain this situation? Because isolation makes sure that no other code can observe writes before commit. So Thread1 cannot observe the change of flagB before Thread2 commits. However, Thread2 cannot commit because it cannot see the change of flagA. So both of two threads will abort.

Please correct me if I am wrong.

Renegade

@ mallocanswer, I don't think isolation is the proper reason here, because isolation is to prevent other "concurrent running" code from seeing what's happening inside transaction.

What happens here is to replace "synchronized" with "atomic", i.e. to form two transactions. Originally, it works fine because two thread blocks run concurrently. With "atomic", however, two transactions must proceed in serial order. Due to the RW conflict here, they just abort and retry over and over again, i.e. a live lock.

mallocanswer

@Renegade, what does "two threads must run in serial" mean? Do you mean two threads cannot run concurrently, one must wait until another one finishes?

Renegade

@mallocanswer, sorry for the confusion. Two transactions should be equivalent to a serial execution order, however they are implemented. Here, the RW conflict would lead to live lock of these two threads, whether the update is isolated between them or not.

mallocanswer

Hi @Renegade, can you elaborate a bit more about how RW conflict leads to live lock? I guess I miss something here. Thanks!

Renegade

@mallocanswer, just as @TomoA put it, "Thread 1 will try to read from flagB, and when thread 2 writes to flagB, thread 1 will have to restart, and then the reverse happens." For more details, you can refer to slide 47.

msfernan

I just wanted to confirm if I am thinking correctly. When we replace synchronized by atomic and any one of the threads has to restart, the thread restarts from the beginning i.e. it performs the write followed by the read. It is not just the read that aborts and restarts because in a transaction, either the complete transaction takes place or none of it.

Like on slide 39, the definition of atomicity has to do with all the writes appearing or none at all. If the thread aborts then it restarts from the beginning. Right?

lol

Doesn't this depend on conflict detection policy? For a pessimistic policy I agree it would livelock, but for a optimistic policy, nothing happens until one of the transactions ends, so it would be deadlock?

leis1

@lol I think you are right.