So if I'm thinking about this right, in case 2 does load A actually happen after the stall and the rd A mentioned before was just a check?

@Calloc I'm not exactly sure what happens during the rd A (it could actually read A, or just perform the check). Regardless, the outcome is the same because the transaction loads A with the newly written value right after the stall.

In lecture we established that the rdA would check, but not occur until after the commit had gone through. I would recommend rewatching the lecture for the exact reasons why. For example, if T0 aborts.

Is checking really all that expensive? It seems like since memory operations are generally pretty expensive, the overhead of checking would get drowned out.

But I suppose checking involves some bus traffic...

@Calloc, @hofstee is correct. The rdA here means "check that I can rdA, and if I get the thumbs up, go ahead and read A".

In case 4, why can't T1 abort first before write to A by T0 completes?

I think there can be deadlock here. For example,

T0 : wr A ----------- rd B (stall)

T1 : wr B -- rd A (stall)

Am I right or not?

For case 2, the read in T1 hasn't happened yet when it detects that T0 has a write operation on A, so it stalled until T0 completes, the actual read happens in the end of stall, so the notation is a bit misleading here as mentioned in the lecture. The sequential order in this case is T0 -> T1.

For case 3, when T1 wants to write to A, there are two options: T0 restart or T1 stall in order to keep the thread execution appear sequential, since we have a rule that write wins on contention(see the notes in the top right of the slide), T0 will restart. The rest of the graph is the same as case 2. The sequential order the trace is equivalent to is T1 -> T0.

To deal with the live lock in Case 4, there might be a conflict manager that can mitigate the livelock, using something like random back-off.

@xiaoguaz I think that's possible and there will be some deadlock detection mechanism (e.g. wait-for graph construction and cycle detection).

One interesting idea mentioned in class for case 2 (maybe not relevant to previous questions) is "speculative read/write": when T1 does rdA, an alternative is to read the "dirty uncommitted" value of A modified by T0, and continue on next instruction without stalling. If T0 committed successfully, T1 read the correct value; if T0 didn't commit, T1 has to abort.

Such alternative avoids stalling when reading uncommitted value, but has to keep track of dependencies between transactions, and abort other transactions when their dependent transactions didn't commit.

@Funky9000: One way to implement your suggestion is to set priorities for threads. If T0 has priority over T1, and there is a write-write conflict, then T1 will abort instead of T0. This would solve the livelock issue, but then we introduce the possibility of starvation, where if T0 continuously writes, T1 will keep getting aborted because it has lower priority than T0.

Can we relate case 4 to the problem on Slide 36 (if we replace synchronization with atomic) because a new write comes in before the earlier one has committed leading to livelock?

How is Case 3 an Abort case? T0 eventually read successfully and committed. Also, the "check" is done by the transactional memory system not the threads themselves. The pictures make them look as if the threads are doing the active checking.

@xingdaz, i think it is because T0 discard its read value, and restart from beginning. It is eventually succeed but with 1 retry.

Is this using eager versioning? How would the results differ with lazy?

For case 4 to avoid livelock, I think there are multiple ways to deal with that, such as setting priority to each transaction, or making them stall for random time, or we can just abort the second write when W-W conflict happens.

@huehue I think it is not related to the versioning. A pessimistic detection can be used in either eager versioning or lazying versioning.

A conflict detection means when to detect the conflict while the versioning means when to write the transaction to memory (note that write doesn't mean commit).

For example, the transaction in case2 can either write A immediately to the memory and create a roll back log (eager versioning) or it can write A to the buffer (lazy versioning)

I wonder if the diagram is a sequential consistent memory system? Is it correct that even if the memory system is sequential consistent, the concurrent threads would cause non-deterministic behavior of instruction stream.

I noticed that in this slide the index of vertical line is the thread while in the memory consistency slide the index is the memory address. Those are different point of view to look at the instruction stream.

In case 3, Why T0 needs to restart instead of stall considering T1 may abort?

In case 3, T0 read the value that T1 is going to overwrite assuming that it succeeds, so it restarts in case T1 succeeds. So the difference in the value is what makes it abort. Notice that after it restarts from the write check, T0 stalls instead of restarting because it's just waiting for A to become free.