26 views
What is the difference between number of schedules which are conflict equal to S and number of serial schedules which are conflict equal to S? Can anybody show an example of the same ? This is very confusing.
| 26 views

+1 vote

S$_{1}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), R$_{2}$(Y), W$_{1}$(Y), W$_{2}$(Y)

S$_{2}$ : R$_{1}$(X), W$_{1}$(X), R$_{2}$(Y), R$_{1}$(Y), W$_{1}$(Y), W$_{2}$(Y)

these two schedules are conflict equivalent.

in other words, i can say, S$_{2}$ is conflict equivalent to S$_{1}$

number of schedules which are conflict equal to S$_{1}$

https://gateoverflow.in/118640/gate2017-2-44?show=289691#a289691

one is the original one, i.e., S$_{1}$ and one more is S$_{2}$

remaining two are

S$_{3}$ : R$_{1}$(X), R$_{2}$(Y), W$_{1}$(X), R$_{1}$(Y), W$_{1}$(Y), W$_{2}$(Y)

S$_{4}$ : R$_{2}$(Y), R$_{1}$(X), W$_{1}$(X), R$_{2}$(Y), R$_{1}$(Y), W$_{1}$(Y), W$_{2}$(Y)

Note :- If  a Schedule is not conflict serializable then NONE of it's conflict equivalent schedules are conflict serializable.

number of serial schedules which are conflict equal to S$_{1}$?

Here, you are Comparing Serial schedules with given Schedule like

for(i=0;i<n;i++)

{
if( a[i] == j)
{

}
else
{

}
}

here i is variying but not j. So, i represent Serial Schedule and j represent given Schedule S$_{1}$

There are 2 Transactions, So you have 2 ! = 2  Serial schedules. And None of them is equivalent to S$_{1}$

Let T$_{1}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), W$_{1}$(Y) and  T$_{2}$ : R$_{2}$(Y), W$_{2}$(Y)

No.of Total Schedules Possible = $\frac{(4+2)!}{4!.2!} = \frac{720}{48} = 15$

No.of Serial Schedules Possible = 2 ! = 2

Non-Serial Schedules = (10-2)=13 Schedules, in that Some are conflict equivalent to T$_{1}$ to T$_{2}$, Some are conflict equivalent to T$_{2}$ to T$_{1}$ and some of them not equivalent to any serial schedule.

let S : R$_{1}$(X), W$_{1}$(X), R$_{2}$(Y), W$_{2}$(Y),  R$_{1}$(Y), W$_{1}$(Y)

number of schedules which are conflict equal to S

number of serial schedules which are conflict equal to S?

Answer is 1. ( T$_{2}$ to T$_{1}$ )

The total number of conflict serializable schedules that can be formed by T1 and T2 is

No.of conflict serializable schedules = No.of conflict equivalent to Schedule T$_{1}$ to T$_{2}$ + No.of conflict equivalent to Schedule T$_{2}$ to T$_{1}$  = 1 + 6 = 7

Non-Conflict serializable schedules = 15-7 = 8

Those 8 schedules are :

S$_{1}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), R$_{2}$(Y), W$_{1}$(Y), W$_{2}$(Y)

and it's remaining 3 conflict equivalent schedules.

S$_{5}$ : R$_{1}$(X), W$_{1}$(X), R$_{1}$(Y), R$_{2}$(Y), W$_{2}$(Y), W$_{1}$(Y)

and it's remaining 3 conflict equivalent schedules.

by (539 points)
0

number of schedules which are conflict equal to S

number of serial schedules which are conflict equal to S?

Answer is 1. (T2 to T1 )

Sir,dint understand this part. For T1 to T2 it should be 1 right? Also, i dint understand the last part how you found those 8 schedules.

0
Can't you apply the method which provided on gate question, to found how it is 6 ?

Which serial schedule is conflict equivalent to given schedule ? T2 -> T1 but not T1 -> T2.

Finding Those eight schedules need some experience, i just want to show the sum is obtained to no.of schedules