CODEWITHSUNDEEP
multithreadingtransactionsmultiprocessingstm
Tim
Tim

Reputation: 355

Is Transactional Locking 2 algorithm serializable?

Consider two threads A and B

They commit at the same time: A.lock --> A.validation --> B.lock --> B.validation --> (A B installs updates)

Is this not serializable because B may overwrite A's reads before A commits?

Upvotes: 2

Views: 143

Answers (1)

Seun Osewa
Seun Osewa

Reputation: 5033

It is serializable because the the value written to Transaction A's writeset depends on the cached value of A's readset which was confirmed during validation. The over-writing of A's readset by B does not affect the cached values of A's readset which A's writes are based on. The values written to Transaction A's writeset are exactly the same values that would have been written if transaction A ran to completion before transaction B started, so it's serializable.

EXAMPLE

We have a transactional memory consists of 3 variables X, Y, Z = X1, Y1, Z1

Transaction A reads X and writes Y with a value that depends on X (X + P) Transaction B reads Z and writes X with a value that depends on Z (Z + Q)

SERIALIZED EXECUTION

  • Transaction A: locks Y, validates X = X1.
  • Transaction A: sets Y = X1 + P and commits.
  • Transaction B: locks X, validates Z = Z1.
  • Transaction B: sets X = Z1 + Q and commits
  • Final result: (X, Y, Z) = (Z1 + Q, X1 + P, Z1)

INTERLEAVED EXECUTION

  • Transaction A: locks Y, validates X = X1.
  • Transaction B: locks X, validates Z = Z1.
  • Transaction B: sets X = Z1 + Q and commits (writes A's readset X before A commits)
  • Transaction A: sets Y = X1 + P and commits (uses cached value of X not the latest value)
  • Final result: (X, Y, Z) = (Z1 + Q, X1 + P, Z1) (same result as serial execution)

Upvotes: 1

Related Questions