2k views

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by $r(x)$ and $w(x)$ respectively. Which one of them is conflict serializable?

1. $r_1(x)$; $r_2(x)$; $w_1(x)$; $r_3(x)$; $w_2(x)$;
2. $r_2(x)$; $r_1(x)$; $w_2(x)$; $r_3(x)$; $w_1(x)$;
3. $r_3(x)$; $r_2(x)$; $r_1(x)$; $w_2(x)$; $w_1(x)$;
4. $r_2(x)$; $w_2(x)$; $r_3(x)$; $r_1(x)$; $w_1(x)$;

(D)  make precedence graph for all the options, for option (D) only graph will be acyclic, hence (D) is CSS.

edited ago by
0
Is R - W a conflict ??
0
yup. only R -R is not conflict.
0
R=-W is conflict only when one more read is performed . It is called unrepeatable read. Is it NOt ?
0
Here there is No unrepeatable read in any of the 4 options . Then How can one get cycles in all the graphs . Could some one explain it in a nice manner .
+5

take node for evry transaction

procedure is simple scan left to right for

take first element => scan from 2nd elemnt to right for every r-w . w-w or w-r  conflict in diffrent transaction thier is a edge

take 2nd element => scan from 3rd elemnt to right for every r-w . w-w or w-r  conflict in diffrent transaction thier is a edge

do like this skip left side one elemnt evry time.

if u found cycle then not css otherwise css.

0
@ Arjun Sir,

I wrote D which was given wrong saying correct ans is 4 (GO Full length test). Can you please tell me what to write if similar situation arises in gate exam.
0
@amolagrawal same happened with mebut don't worry this will not happen in gate.
In option D, there is no interleaving of operations. The option D has first all operations of transaction 2, then 3 and finally 1 There can not be any conflict as it is a serial schedule with sequence 2 --> 3 -- > 1
0
when we make precedence graph  for option C ,D  only graph will be acyclic, then why option C is not correct ?
0
In option C there is a conflict in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!
+3
only  option D is correct as there is no cycle in precedence graph, but in C there is cycle as there are  conflicts in r1(x) -> w2(x) and w2(x) -> w1(x) which makes cycle!