Previous | Next --- Slide 48 of 64
Back to Lecture Thumbnails
rbcarlso

The potential issue here is possible starvation in Case 4. If T1 does the same thing again after T0 restarts, we find ourselves in the same boat. Fortunately this is fairness as opposed to strict correctness. And you could implement a policy like "If something has been restarted n times then anything that wants to interrupt it restarts instead of committing."

Sherry

I am still not very clear for the case 3, could someone help to tell the difference between case 3 in pessimistic detection examples and case 3 in this slide?

ChandlerBing

@Sherry - I think the key difference is that in the pessimistic case the checks happen immediately. First the rdA checks and then the wrA. Since the writer wins, it aborts the rd transaction which then stalls till the wr transaction commits. On the other hand, in the optimistic case here, we do not perform the checks immediately, rather defer them till the commits occur. Here, the rd commit occurs first (which wasn't the case with the pessimistic policy) and then the check is performed. There is nothing to be done and then sometime later the wrA commits too!

BigFish

@Sherry. I think in case 3, the reason why it can succeed is that from the whole system's perspective, T0 and T1 are serializable. Supposed before T0 and T1, A has version number v0. Since the system schedule T0 to execute first, it will read v0 and commit. In the same time, T1 will also read v0 and then update it to v1 later. However, T1's update should not be visible to T0 in the optimistic approach, and hence should not cause T0 to restart. From the whole system's perspective, A will end up with v1 after T0 and T1, which is equivalent to execute T0 and T1 serializable.

Sherry

@ChandlerBing@BigFish. Thank you for the detailed answer which helps me a lot.

ak47

On case 4, what's to stop both threads from trying to commit at the same time, such that their commit messages criss-cross and both restart?

aznshodan

In case 3, it succeeds because the what T1 saw initially wasn't modified by T0. So there is no need to abort.

amaliujia

I think in case 4 we assume that TM uses write buffer. Because if it is not write buffer but undo log, T1 will read data written by T0. But there is a chance that T1 read data before T0's transaction. Furthermore, restart T0 will lead to data in undo log written back to memory, which is disaster. Because here data before these two transactions will be back, and T1's write will lose, if restart occurs later than T1's commit.

BigFish

In case 4, if T0 wrA and then T1 wrA and commit, does T0 need to restart? It seems like in this case, T0 does not need to restart since it does not rely on the old value of A.

gryffolyon

@BigFish, I would like to agree with you. If you look at it, we can represent the writes by T0 and T1 separately on a timeline and as you mentioned, they do not depend on the old values of A if they just do a write. So I believe we don't need to restart any thread here unless I am grossly mistaken.

mingf

If we were to use eager versioning in case 2, T1 does not need to restart, since the rd A by T1 can read what wr A in T0 writes. Timestamps of each operations have to be maintained in order to resolve situations like this.

parallelfifths

@mingf "If we were to use eager versioning in case 2, T1 does not need to restart..." Is this true?

I thought that at the time of commit, T0's write will be in memory regardless of eager or lazy versioning (as the definition of commit is that everyone can see the write). Therefore, I am not sure that using an eager versioning system functionally changes anything in Case 2. An eager versioning system would just mean that T0's write goes directly to memory (and the previous value of A is stored in the undo log) instead of going to a write buffer and then memory. I think either of these versioning methods could occur within the current illustration.

ananyak

I don't think an eager versioning system will be functionally the same, although I agree that T1 probably has to restart in a eager versioning system as well, unless the versioning system is very intelligent.

In an eager system, T0's write to A will be visible to other processors even before T0 commits (immediately after the write!). So T1 will read T0's updated write to A. If T0 does not write to A after T1's read, and the transactional system somehow detects this, then T1 will not have to abort.

However, I think detecting that T0 did not write to A after T1's read will be very inefficient, because it would require keeping track of timestamps for reads/writes. So chances are T1 will just abort because the read/write sets intersect.

In any case, I think Kayvon assumed in his examples that we're using a lazy optimistic transactional memory system in class. He said that T1's reads in case 4 will not be affected by T0's writes. There's an excellent discussion (on a later slide) about why a lazy, optimistic system isn't practical.