Transactional Information Systems 第６章演習問題解答

Transactional Information Systemsにおける第６章演習問題の自分なりの解答。

間違っていたらご指摘ください。

6.1 Q

図6.12の2層スケジュールはtree reducibleか？

6.1 A

$t_1, t_3$ の高レベル操作 $Withdraw_1(a), GetBalance_3(a)$ が非可換であり、その一方、ページレベルではそれらの子の操作である $r_3(p), w_1(p)$ が逆向きかつ非可換なのでtree reducibleでない。

6.2

3層スケジュールを描く問題なので略。

6.3 Q

図6.2の2つのスケジュールについて、それぞれtree reducibleか？

6.3 A

一つ目はtree reducibleである。

ページレベルの $w_1(t), w_2(t)$ が非可換なので、reducibleになるとしたら $t_1 \lt t_2$ という順である。

$Withdraw_1(a)$ 直下の $w_1(p)$ や $w_1(t)$ はページレベルの可換性で手前に出せる。 $Deposit_1(c)$ は高レベルの可換性を用いて $Withdraw_2(b), Deposit_2(c)$ と入れ替えて手前に出せる。

二つ目もtree reducibleである。

根直下の $w_2(r) \lt w_1(r)$ から、reducibleになるとしたら $t_2 \lt t_1$ である。 $Withdraw_1(a), Withdraw_2(b)$ はそれぞれ部分木をisolatedにできるので、それらが可換なことを合わせて $t_2$ を手前に出せる。

6.4 Q

図6.6のスケジュールを実際に既約にせよ。

6.4 A

まず $CheckItem_1$ の部分木をページレベルの可換性で手前に出してisolatedにする。
同様に $Payment_2$ の部分木をページレベルの可換性で手前に出してisolatedにする。
枝刈り規則に基づき、のみが残り、それ以下の部分木は全て枝刈りされる。
- ここでは $CheckItem_1CheckItem_2Shipment_1Payment_2Payment_1$ となっている。
これらの高レベル操作は互いに可換なので並び替えて $CheckItem_1Shipment_1Payment_1CheckItem_2Payment_2$ を得る。

6.5 Q

図6.13の階層的なスケジュールについて、tree reducibleか？conflict faithfulか？

各層間スケジュールはそれぞれCSRか？OCSRか？

6.5 A

tree reducibleである。

$d_2(\mu')$ をisolatedにできるので、可換性に基づいて $d_2(\mu')$ を末尾にも先頭にも動かせる。よってtree reducible。

conflict faithfulである。

高レベル操作のうち非可換なのは $m_1(a), m_2(a)$ のみで、その直下の操作 $w_1(q), w_2(q)$ が競合しているため。

層間スケジュールはOCSR。

CSRは明らかだし、競合の順が出現順と矛盾することもないのでOCSR。

6.6 Q

返り値に基づく可換性の表を以下の操作について作成せよ。

increment：カウンタを加算し、上限を超えていないならOK、超えていたらカウンタを変更せずにNOを返す。
decrement：カウンタを減算し、下限を下回っていないならOK、下回っていたらカウンタを変更せずにNOを返す。
getvalue：カウンタの値を取得する。

6.6 A

	Inc:OK	Inc:NO	Dec:OK	Dec:NO	Getvalue
Inc:OK	○	✕	✕	○	✕
Inc:NO	○	○	✕	○	○
Dec:OK	✕	○	○	✕	✕
Dec:NO	✕	○	○	○	○
Getvalue	✕	○	✕	○	○

6.7 Q

FIFOキューが返り値可換性に基づいて高い並列性を実現できるようなスケジュールの例を考えよ。

6.7 A

最初から多くの要素を持つFIFOキュー $q$ において、多くのトランザクションによる $enq(q,~)$ と $deq(q)$ が大量に混ざったスケジュールを考える。

このとき、enqueueとdequeueは返り値がOKになるので相互に可換であり、enqueueどうし、dequeueどうしの順番さえ変えなければそれ以外の順番は自由に決めることができ、並列性が高くなる。

6.8 Q

semi-queue (dequeueにより取り出す要素が非決定的であるキュー) における操作の可換性を示し、これが高い並列性を実現するスケジュールの例を示せ。

6.8 A

	Enq:ok	Enq:one	Deq:ok	Deq:empty
Enq:ok	○	imp	✕	imp
Enq:one	✕	imp	✕	✕
Deq:ok	✕	✕	○	✕
Deq:empty	✕	✕	imp	○

通常のFIFOキューと比較すると、enqueueとdequeueが非可換になった代わりに、enqueueどうし、dequeueどうしが可換になっている。

したがって、多くのトランザクションによるenqueueだけが大量にあるスケジュールにおいて、どの順番で実行しても良いため極めて並列性が高くなる。dequeueについても同様。

6.9 Q

$s = enq_1(q,a)enq_2(q,b)deq_3(q)enq_1(q,c)deq_3(q)$

において、

(a) 一般の可換性に基づいて考えるとserializableか？

(b) キューの返り値可換性で考えるとserializableか？

6.9 A

(a) 一般の可換性で考えるとserializableでない。

一般の可換性では、 $enq(q,~), deq(q)$ は競合する操作であり非可換で、したがって逐次的なスケジュールにできない。

(b) キューの返り値可換性で考えるとserializableでない。

返り値も含めてスケジュールを書き直すと

$s = enq_1(q,a):one\rightarrow enq_2(q,b):ok\rightarrow deq_3(q):ok\rightarrow enq_1(q,c):ok \rightarrow deq_3(q):ok$

$deq_3(q)$ を $enq_1(q,c)$ と入れ替えて後ろに出す。その後、 $enq_2(q,b)$ は前後の $t_1$ の操作と非可換なので行き詰まる。

(c) semi-queueの返り値可換性で考えるとserializableでない。

$enq, deq$ が交互にあり、これらすべてsemi-queueにおいては非可換なので括り出せない。

結局どの可換性に基づいてみてもserializableでない。

6.10

メールボックスのADTをデザインせよ。略。

6.11 Q

預金の引き出し操作は、預金には下限が存在するため一般に非可換であると考えられる。

これを実質的に可換にするために、預金が0を下回った場合でも引き出しを許す代わりに一定額のペナルティを課すこととする。

relaxed_withdraw(x, delta) {
  x.balance = x.balance - delta;
  if (x.balance < 0) x.balance = x.balance - 10;
}

一般的な可換性のもとではserializableでないが、この緩和されたwithdrawのもとでserializableになるようなスケジュールを考えよ。

また、アプリケーションとしての観点から、銀行とユーザにとってこの変更が受け入れられるか考えよ。

6.11 A

$Withdraw_1(a,10)Withdraw_2(a,10)Withdraw_2(b,30)Withdraw_1(b,30)$

というスケジュールを考えると、一般的な意味の可換性ではこれはserializableでないが、緩和されたwithdrawのもとではserializableになる。

このような緩和の問題点は以下。

預金の下限を無くすことで無限の借金が可能になってしまっている。
- この方法で可換性を保証するためには、極論100億ドル一気に引き出されても断れない。
  - なので現実的に無理。
ユーザとしても、預金がマイナス時に引き出しの全てにペナルティがかかるのは困る。

u-ar.hatenablog.com

u-ar’s blog

研究や技術について。もろもろ。