How would the idea of a "memory transaction" typically be exposed to the programmer? For hardware solutions would it be exposed in the instruction set?

These two articles give a good idea of how to use _xbegin() and _xend() exposed by intel Example 1 Example 2

I believe that underneath they are an extension to the Intel x86 ISA

Can anyone help explain this situation? Will T0 restart or not?

T0 : ------ rd A --- (try to commit) success or abort?

T1 : wr A ---------------- (continue)

Updated. Sorry about the confusion before.

@xiaoguaz Can you clarify the timelines a little more. Isn't this exactly like case 2 with T0 and T1 interchanged?

@xiaoguaz, I think T0 will successfully commit, because the modification of T1 is not visible to other threads before commit. This is equivalent to T0 happening before T1(the sequential order would be T0->T1).

@jerryzh Thank you for explanation. But how can you explain the case 2 and case 3 in the link.

@xiaoguaz, pessimistic detection is different from optimistic detection, for cases in slide 47, I think we can understand every step as taking effect immediately("eager").

I have wrote my understanding of case 2 and case 3 in slide 47.

It is understandable if pessimistic detection takes steps immediately. However, I think pessimistic / optimistic is independent with eager / lazy. In other word, they are two different aspect and they can combine with each other link. Under this situation, it is hard to explain what is happen here.

Or, the slide 47 is taking about the "pessimistic + eager" and slide 49 is about "optimistic + lazy" ?

I'm not very clear about this part, either. It seems that even though they are different concept, there is still some restrictions, like "eager + optimistic" is not practical in hardware TM systems and "eager + optimistic write" seems not practical in software systems.

I suppose that we can understand the slide 47 and slide 49 better if we assume a "eager + pessimistic" and "lazy + optimistic" implementation.

Why doesn't T1 abort in case 3? Would it abort if T0's rd A happened after T1 started?

@huehue Because read in T0 won't affect T1's write. (Think that: whether or not T0 exist, the result of T1 won't change)

Does that mean any read before a write doesn't result in a conflict? For example:

T0: rd A -------- rd B -------- rd C ------ commit

T1: -------- wr A ------- wr B ------ wr C -------- commit

Is that successful?

@huehue Yes I think so. Both of two transaction will success as long as T0 finished before T1.

What if T1 finished before T0? Would that not succeed?

@huehue T1 will success and T0 will restart, just like Case2.

So in case 2, if T1 committed before T0, there would be no abort? The only reason it aborts is that T0 commits first, not that write A happened before read A?

@huehue To be clear, here we assume "optimistic + lazy" implementation in this slide, i.e. the change won't be seen be other threads until it is committed. As a result, the first committed thread will succeed (because of the optimistic) no matter what the operations before its commitment and its relative orders with others (because of the lazy). More information is included in the former discussion. For other implementation like "optimistic + eager", I am not very clear about it, too. Sorry.

@xiaogauz Actually transaction memory semantics dictate that the writes are not observed until the commit takes place irrespective of the data versioning scheme used hence even with optimistic + eager we should observe the same.(How the eager versioning does this when its writing to memory I dont know).

Is it assumed that we always abort the other transactions instead of committing one?

Yes. The optimistic scheme implementation gives priority to committing transaction.

If both eager and lazy mean that writes aren't visible until commits, how does eager vs. lazy affect the results of conflict detection? Or does it not?

It affects conflict detection by determining which thread will abort or stall.

You can think about which transaction aborts in terms of the properties of transactions. Transactions are viewed by all processors to occur in some serial order. In conflict detection, there are two issues: write-reads and write-writes on the same address.

In case 1, there is no conflicts so both commit.

In case 2, T0 is the first to end, and it commits (per definition of optimistic detection). Since there is a perceived serial order, it must be that T1 occurs after T0, since T0 already committed. Now we have a WR conflict on A: T0 wrote to A, and T1 is reading from A. Since the order of transactions observed to all processors is T0 then T1, when T1 reads from A, it must be the new value which T0 wrote. But since T1 read the old value of A, as writes within a transaction are not visible (isolation), T1 is incorrect. So it must restart.

In case 3, T0 commits first. Hence T1 must appear after T0. The order on A is read, write. This does not create any conflicts, since the read occurs first and does not affect the write. So both transactions commit.

In case 4, T1 commits first. So T0 must appear afterwards in the sequential order. We have the same WR conflict in case 2, that in the total sequential order, T1 writes to A, and T0 subsequently reads from A. But due to isolation, T0 has the old copy of A. So it must restart to preserve the notion of sequential consistency of transactions.

I hope this clears things up.

So is this example using lazy? How would which thread aborts differ if eager was used?

@huehue Actually, it seems that optimistic detection cannot combine with eager versioning. As you may be confused, optimistic detection only works correctly if every "read" within each transaction doesn't see other transaction's "write" before they commit. Only the lazy versioning with a write buffer can guarantee this, while the eager versioning with an undo log can't.

In case 2, when T1 read A, the A is the value before T0 commit because of the isolation property. So T1 need to restart again.

I have a question... If the "read A" in case 3 is replaced with "write A", will T1 abort the transaction when it learns that T0 just write to A? Since it's using lazy versioning, I guess the answer is "no"...

@Richard I think you are right, because the result could be thought of as T1 happens after T0

@Richard I don't think T1 will learn about the write A till T0 commits, which is when T1 will restart. Lazy versioning of the writes doesn't imply that committed transactions won't propagate. When T0 commits a write to A, T1 has to restart.

good read about optimistic concurrency control. Though its for databases, the principles are the same. http://www.cs.cmu.edu/~15712/papers//kung81.pdf