The key thing to keep in mind for this example is that we want it to look like transactions proceed atomically (either the entirety of T0 proceeds, followed by the entirety of T1, or vice versa).
In the third example, T0 needs to restart because it has read a value that T1 overwrote. But since we require that writers have priority, we must have the entirety of T1 proceed first. Therefore the read in T0 must return T1's written value, and the only way it can do so is if the transaction T0 restarts.
chenh1
What is the relationship between commit and read? For example, the write will be in memory until commit.
crow
This slide shows how transaction read/writes interact with other transactional read/writes.
What happens when a non-transactional read/write interacts with a transactional read/write. For example, suppose we make a non-transactional read, and then another thread makes a transactional write, in case 3 here, the read would abort. However, we can't do that in our case because it's a non-transactional read. So it seems like the right thing to do is to abort the writing transaction instead.
zckchange
What does the blue line of rd A mean in Case3 ? rd A is running before committing during the whole blue line, or only the transaction is still running but the rd A has finished ?
albusshin
In case 3, rd A was restarted because T1 (write A) has higher priority over T0.
ykt
In case 4, if we assume that writing to A is the only read/write conflicting operation that happens in the transactions, then it should be ok for neither of the transactions to abort, since no one will be able to question the atomicity or the isolation of the transactions. (No one could have read the value of A before the transactions committed). My guess on why this optimization is not done is because of the complexity of implementing this.
ykt
@crow I think if you mix non-transactional code with transactional code, we will no longer be able to make atomicity and isolation guarantees. For example, if we use eager versioning, then the non-transactional code will be able to read in-between values and transactions will/should not (I think) be able to detect read/write(s) in non-transactional code, so won't know when to abort.
kapalani
In case 2 why must T1 stall till T0 commits? Since T1 already has the updated value that T0 wrote and T0 hasn't doesn't write to A again, why can't T1 just proceed and if it is the case that T0 writes to A again, then T1 can abort?
I guess the diagram might be a bit misleading in the sense that when the rdA happens for T1, the actual value of A isn't read until the transaction commits
lya
@kapalani I think the diagram is correct. Remember in pessimistic detection, the checking for conflicts happens only during reads and writes. Therefore, during rdA, T1 cannot read the updated value of A from wrA of T0 and has to stall. If it reads A immediately, it could commit before T0 without double check. In this case, T1 is beforeT0 if we put transactions in a serial order. However, T1 reads the value of A updated by T0, so T1 is also afterT0 in this sense, which violates the serializability of transactions.
tarabyte
Are there other scenarios within pessimistic and/or optimistic detection in which livelock occurs?
vadtani
pessimistic detection usually has a conflict manager to prevent livelocks!
nishadg
What if readers have priority?
SR_94
I am confused as to why T1 stalls in case2, and in case3 T0 first restarts and then stalls.
This implies that in case 2, T1 detected that T0 had a write to addr A before it performed the read and hence stalled instead of restarting. In case 3, T0 aborts because it detected the write to A after it has read the value at A and then after that it detects the write to A before it reads A and hence stalls.
So when and how do we decide to detect early?
Bye
@SR_94 Simply put, if a transaction detects a write to the same address it is going to read during its Rd check, the transaction will stall. On the other hand, if a transaction receives a Wr check to the same address it has read(by checking its read-set), it will abort and restart. This is to preserve serializability of TM.
fxffx
In case 4, the two transactions are aborting each other because writers always have priority. So two transactions will not stall but keep restarting, resulting in live lock.
In this example, Writers have priority.
The key thing to keep in mind for this example is that we want it to look like transactions proceed atomically (either the entirety of T0 proceeds, followed by the entirety of T1, or vice versa).
In the third example, T0 needs to restart because it has read a value that T1 overwrote. But since we require that writers have priority, we must have the entirety of T1 proceed first. Therefore the read in T0 must return T1's written value, and the only way it can do so is if the transaction T0 restarts.
What is the relationship between commit and read? For example, the write will be in memory until commit.
This slide shows how transaction read/writes interact with other transactional read/writes.
What happens when a non-transactional read/write interacts with a transactional read/write. For example, suppose we make a non-transactional read, and then another thread makes a transactional write, in case 3 here, the read would abort. However, we can't do that in our case because it's a non-transactional read. So it seems like the right thing to do is to abort the writing transaction instead.
What does the blue line of rd A mean in Case3 ? rd A is running before committing during the whole blue line, or only the transaction is still running but the rd A has finished ?
In case 3, rd A was restarted because T1 (write A) has higher priority over T0.
In case 4, if we assume that writing to A is the only read/write conflicting operation that happens in the transactions, then it should be ok for neither of the transactions to abort, since no one will be able to question the atomicity or the isolation of the transactions. (No one could have read the value of A before the transactions committed). My guess on why this optimization is not done is because of the complexity of implementing this.
@crow I think if you mix non-transactional code with transactional code, we will no longer be able to make atomicity and isolation guarantees. For example, if we use eager versioning, then the non-transactional code will be able to read in-between values and transactions will/should not (I think) be able to detect read/write(s) in non-transactional code, so won't know when to abort.
In case 2 why must T1 stall till T0 commits? Since T1 already has the updated value that T0 wrote and T0 hasn't doesn't write to A again, why can't T1 just proceed and if it is the case that T0 writes to A again, then T1 can abort?
I guess the diagram might be a bit misleading in the sense that when the rdA happens for T1, the actual value of A isn't read until the transaction commits
@kapalani I think the diagram is correct. Remember in pessimistic detection, the checking for conflicts happens only during reads and writes. Therefore, during
rdA,T1cannot read the updated value ofAfromwrAofT0and has to stall. If it readsAimmediately, it could commit beforeT0without double check. In this case,T1is beforeT0if we put transactions in a serial order. However,T1reads the value ofAupdated byT0, soT1is also afterT0in this sense, which violates the serializability of transactions.Are there other scenarios within pessimistic and/or optimistic detection in which livelock occurs?
pessimistic detection usually has a conflict manager to prevent livelocks!
What if readers have priority?
I am confused as to why T1 stalls in case2, and in case3 T0 first restarts and then stalls. This implies that in case 2, T1 detected that T0 had a write to addr A before it performed the read and hence stalled instead of restarting. In case 3, T0 aborts because it detected the write to A after it has read the value at A and then after that it detects the write to A before it reads A and hence stalls. So when and how do we decide to detect early?
@SR_94 Simply put, if a transaction detects a write to the same address it is going to read during its Rd check, the transaction will stall. On the other hand, if a transaction receives a Wr check to the same address it has read(by checking its read-set), it will abort and restart. This is to preserve serializability of TM.
In case 4, the two transactions are aborting each other because writers always have priority. So two transactions will not stall but keep restarting, resulting in live lock.