3
$\begingroup$

If we use the Timestamp Ordering for concurrency control in the following scheduling:

enter image description here

My TA says $T_2,T_3,T_5$ is Run and $T_4,T_5$ is Rollback. I think it's false. Is there any expert who could help us?

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jul 14 '16 at 6:10
1
$\begingroup$

Timestamp Ordering ensures serializability by serializing transactions in order of their timestamps.

The transaction that starts earlier is assigned smaller timestamp than a transaction started later. Assuming the given schedule shows each transaction's start. $T_{5}$ will have smallest timestamp.

So to ensure serializability the given schedule must be conflict serializable. In other words it must be conflict equivalent to a serial schedule(It is a schedule in which transactions are aligned in such a way that one transaction is executed first. When the first transaction completes its cycle, then the next transaction is executed) whose first transaction is $T_{5}$ because of smallest timestamp.

Because $Write(y)$ of $T_{5}$ conflicts with $Write(y)$ of $T_{3}$, $T_{5}$ is rolled back. Now considering $T_{1}$ , $T_{2}$, $T_{3}$ , $T_{4}$, their execution is already serial with respect to each other , the order being $T_{2}$ followed by $T_{1}$, followed by $T_{3}$, followed by $T_{4}$.

Hence only transaction $T_{5}$ is rolled back.

$\endgroup$
0
$\begingroup$

I know its a little too late, but here's my take:

All the read and writes by t1,t2,t3,t4 are sucessfully run, since there are just 1 instructions until that point. And assuming the systems assigns the timestamp just before each transaction's first instruction.

The last write(y) instruction by t5 is rejected, since the TS(T5) < W-TStamp and R-TStamp. Hence its restarted with a new time stamp.

$\endgroup$
  • 4
    $\begingroup$ Welcome! Late isn't a problem, since we always hope that questions here will be useful to more people than just the person who originally asked them. You've formatted most of your answer as a quotation. If it is a quotation, please acknowledge its source (e.g., with a link to the original page). If it isn't, could you edit it, to remove the visual distraction? Thanks! $\endgroup$ – David Richerby Apr 15 '16 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.