This question is from a previous question.
https://gateoverflow.in/31867/how-many-recoverable-schedules-are-possible-from-t1-and-t2
nilamd answered the question correctly, i.e. 42
I am trying to explain the answer. As shown on the previous question, there are 51 recoverable schedules. All Cascadeless schedules are also Recoverable schedules. Thus, we need to find the Cascading Recoverable schedules and we can remove them from the Recoverable Schedules to get the possible number of cascadeless schedules.
Two cases arise again.
Case 1
| T1 |
T2 |
|---|
| r(x) |
|
| r(y) |
|
| w(x) |
|
| |
r(x) |
| |
w(x) |
| w(y) |
|
| commit |
|
| |
commit |
Here, we can have the two last operations from T1 either before r2(x), between r2(x) and w2(x) or after w2(x). Also keep in mind that if you count the case where both w1(y) and commit1 come before r2(x) then it will become cascadeless schedule. We need to keep the schedule cascading but Recoverable. Number of possible ways of placing w1(y) and commit1 in different places is 5.
Case 2
| T1 |
T2 |
|---|
| |
r(x) |
| |
w(x) |
| r(x) |
|
| r(y) |
|
| w(x) |
|
| w(y) |
commit |
| commit |
|
| |
|
Here also, we can have commit2 not before r1(x) since then it will also become cascadeless schedule and also commit2 cannot come after commit1 since then it will be Irrecoverable schedule. Number of possible places to have commit2 in different places is 4.
Thus, total number of cascading schedules is 5 + 4 = 9
Number of cascadeless schedules is 51 - 9 = 42
