台大電機丙的CA/OS多選題「全對才給分」
所以去年這張考卷我只拿了五分...... Orz
※ 引述《KiroKu ()》之銘言：
: 我查wiki
: http://en.wikipedia.org/wiki/Serializability
: 因為transaction都是同時進行
: 它定義是說若是執行的結果跟執行時間不重疊一樣的話
: 就是serilable，
: 順序不會影響執行結果
: 我理解是這樣的
: 不知道是不是要考這東西
: 我只有選A
我覺得這個好難講...
恐龍書上的定義是「如果我們可以透過Swapping noconflicting operations
來把一個本來不是Serial Shedule者轉成Serial，我們稱為Conflict Serializable」
其中Conflict的Operation指的是對同一個Data讀取，且其中至少有一個在Write
而Timestamp protocol只是「其中一個」解決Conflict Serializable的方法
稍微看了一下rnbjacky的解法，覺得不太對勁，也寫了我的想法
以下所有作法中，TS(T1) = 1，TS(T2) = 2，所有R/W-Timestamp在Time=0時皆為0
Ti作Read(A)時須確保TS(Ti) >= Write-Timestamp(A)，然後改Read-Timestamp(A)
Ti作Write(A)時須確保TS(Ti) >= Write-Timestamp(A)且TS(Ti) >= Read-Timestamp(A)
然後改Write-Timestamp(A)
無法確保的情況下該Transaction會被rollback
所以這題我猜(A)(B)，想法如下：
(A) True
T1 T2
──────
1 R1(A)
2 R2(B)
3 W1(A)
4 W2(B)
用Timestamp-based Protocol：這個應該沒做錯，直接貼上 XDDDDDD
Time 1 2 3 4
W-timestamp(A) 0 0 1 1
R-timestamp(A) 1 1 1 1
W-timestamp(B) 0 0 0 2
R-timestamp(B) 0 2 2 2
用定義：交換W1(A)和R2(B)的執行次序之後會變成Serial Schedule
T1 T2
──────
1 R1(A)
2 W1(A)
3 R2(B)
4 W2(B)
(B) True
T1 T2
──────
1 R1(A)
2 W2(A)
3 W1(B)
4 R2(B)
用Timestamp-based Protocol（Time=3開始我的答案不一樣）：
Time 1 2 3 4
W-timestamp(A) 0 2 2 2
R-timestamp(A) 1 1 1 1
W-timestamp(B) 0 0 1 1
R-timestamp(B) 0 0 0 2
用定義：交換W1(B)和W2(A)之後會變成Serial Schedule
(C) False
T1 T2
──────
1 R1(A)
2 W2(B)
3 R1(B)
4 W2(A)
用Timestamp-based Protocol（Time=3開始我的答案不一樣）：
Time 1 2 3 4
W-timestamp(A) 0 0
R-timestamp(A) 1 1
W-timestamp(B) 0 2
R-timestamp(B) 0 0
Time = 3的R1(B)時，TS(T1) = 1 < 2 = W-Timestamp(B)
因此這題無法使用Timestamp-based protocol達成Serialize
(D) False
T1 T2
──────
1 R1(A)
2 R2(B)
3 W1(B)
4 W2(B)
用Timestamp-based Protocol（答案一致）：
Time 1 2 3 4
W-timestamp(A) 0 0
R-timestamp(A) 1 1
W-timestamp(B) 0 0
R-timestamp(B) 0 2
Time = 3的W1(B)時，TS(T1) = 1 < 2 = R-Timestamp(B)
(e) False
T1 T2
──────
1 W1(A)
2 R2(A)
3 W2(B)
4 R1(B)
用Timestamp-based Protocol（答案一致）：
Time 1 2 3 4
W-timestamp(A) 1 1 1
R-timestamp(A) 0 2 2
W-timestamp(B) 0 0 2
R-timestamp(B) 0 0 0
Time = 4的R1(B)時，TS(1) = 1 < 2 = W-Timestamp(B)
-----
隨便寫寫，希望會有用qq
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.131.200.56