Virtual BoxをRetina Displayで動かした時に発生する画面のボヤけの対処
以前retina displayのmacでVirtual Boxを使うとゲスト側OSの画面が滲む、という趣旨のことを書いた
retina displayを使っている限り、1280x800の解像度でボケずに表示することができないらしいので諦めた。 整数倍の解像度を表示するくらい簡単にできそうなもんだが。。。。 ドライバ周りとか色々と大変なのかな。
以下の手順で解消することを確認した。
- 1.Virutual Boxの 設定>ディスプレイ の「スケールしないHiDPI出力を使用」にチェックを入れる
- 2.ゲスト側のOSの設定でScaleを200%もしくは300%に変更する
もしかしたらGUIやディストリビューションによって違いがあるかもしれないが、Ubuntuだとかなり綺麗に表示された。
hatena blogに画像をあげるとドットバイドットにならずボヤけてしまうので、カメラでとった画像でbefore afterを示してみる。
プログラマのためのSQL 読書会(31)に参加
今回は普段の会議室が取れなかったとかで和室でした。
本日の勉強会会場です🍵 pic.twitter.com/H9wKWc3Cor
— yuYabu (@yuyabu2) 2018年11月15日
- 作者: ジョー・セルコ,Joe Celko,ミック
- 出版社/メーカー: 翔泳社
- 発売日: 2013/05/24
- メディア: 大型本
- この商品を含むブログ (16件) を見る
32. 11 オーバーラップする被覆
期間(開始,終了)を扱うようなテーブルで、被覆していて切れ目のない範囲を抽出したいという趣旨のクエリです。
データ
CREATE TABLE Intervals (x INTEGER NOT NULL, y INTEGER NOT NULL, CHECK (x <= y), PRIMARY KEY (x, y)); --- INSERT INTO Intervals VALUES (1, 3),(2, 5),(4, 11), (10, 12), (20, 21), (120, 130), (120, 128), (120, 122), (121, 132), (121, 122), (121, 124), (121, 123), (126, 127);
実行結果
| min_x | max_y |
|---|---|
| 1 | 12 |
| 20 | 21 |
| 120 | 132 |
例のごとく、何パターンも紹介されていますが、そのうち1つにpostgreSQLだけ実行結果が違うものがありました。
--パターン1:ディーター・ネース のウィンドウ 関数を使ったクエリ SELECT min_x, MAX(y) FROM (SELECT x, y, MAX(CASE WHEN x <= MAX_Y THEN NULL ELSE x END) OVER (ORDER BY x, y ROWS UNBOUNDED PRECEDING) AS min_x FROM (SELECT x, y, MAX(y) OVER(ORDER BY x, y ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS max_y FROM Intervals) AS DT) AS DT GROUP BY min_x; ---パターン2:自己 結合と3レベルの相関サブクエリを使うクエリ SELECT I1.x, MAX(I2.y) AS y FROM Intervals AS I1 INNER JOIN Intervals AS I2 ON I2.y > I1.x WHERE NOT EXISTS (SELECT * FROM Intervals AS I3 WHERE I1.x - 1 BETWEEN I3.x AND I3.y) AND NOT EXISTS (SELECT * FROM Intervals AS I4 WHERE I4.y > I1.x AND I4.y < I2.y AND NOT EXISTS (SELECT * FROM Intervals AS I5 WHERE I4.y + 1 BETWEEN I5.x AND I5.y)) GROUP BY I1.x; --パターン3:サブクエリ の 代わりに左外部半結合を使ったクエリ SELECT I1.x, MAX(I2.y) AS y FROM Intervals AS I1 INNER JOIN Intervals AS I2 ON I2.y > I1.x LEFT OUTER JOIN Intervals AS I3 ON I1.x - 1 BETWEEN I3.x AND I3.y LEFT OUTER JOIN (Intervals AS I4 LEFT OUTER JOIN Intervals AS I5 ON I4.y + 1 BETWEEN I5.x AND I5.y) ON I4.y > I1.x AND I4.y < I2.y AND I5.x IS NULL WHERE I3.x IS NULL AND I4.x IS NULL GROUP BY I1.x; ---パターン4:トニー・アンドリュースのクエリ SELECT Starts.x, Ends.y FROM (SELECT x, ROW_NUMBER() OVER(ORDER BY x) AS rn FROM (SELECT x, y, LAG(y) OVER(ORDER BY x) AS prev_y FROM Intervals) AS Foo WHERE prev_y IS NULL OR prev_y < x) AS Starts, (SELECT y, ROW_NUMBER() OVER(ORDER BY y) AS rn FROM (SELECT x, y, LEAD(x) OVER(ORDER BY y) AS next_x FROM Intervals) AS Boo WHERE next_x IS NULL OR y < next_x) AS Ends WHERE Starts.rn = Ends.rn;
このパターン4のクエリのみ実行結果が違って出ます。
x | y -----+----- 1 | 12 20 | 21 120 | 124
ご覧の通り最後の被覆範囲が(120,132)ではなく(120 ,124)と出てしまいました。
Transactional Information Systems 5章 MVCC勉強会 第一回に参加
今回読んだ内容としてはMVCCでは
- xのWrite時にデータを上書きではなく、新しいバージョンのX2を作る
- xのread時にどのバージョンを読むかを決定する、バージョン決定関数
h()が存在する
が要点ですが、その定義や文言について議論が長く続きました。
- MVCCは理論がついてきていない。実装が先行している。→理論の再構築が必要
- MVCCは基本的にwriteロックを取らないが、現行のものでwriteロックを取らないものはない
p.188のExample 5.2の手前まで読みました。
- 作者: Gerhard Weikum,Gottfried Vossen
- 出版社/メーカー: Morgan Kaufmann
- 発売日: 2001/05/24
- メディア: ハードカバー
- クリック: 2回
- この商品を含むブログ (2件) を見る
感想
参加要件
と書かれていますが、CSR,FSR,VSRなど各シリアライゼーションの意味を把握した上で、本書の内容も理解できているような レベルの議論がなされています。また@okachimachiorz1さんがすでに全編音読という偉業を成し遂げられているためか、@okachimachiorz1さんが内容に関して批判点(議論したい点)などをまとめたレジュメを配られた状態で始まりました。
- 5章までの全内容+勉強会中に読む範囲の予習をした上で自分なりの意見を持つくらいのレベルが要求されていると思いました。
次回までにもうちょっとパワーアップして臨みたいです。
- okachimachiorz1さんkumagiさんがネット上に書かれたトランザクション関連の情報を読んで自分なりの理解を持つ。
- ぱとさんのブログに書かれているような感じで読んでいきたいです。 taityo-diary.hatenablog.jp
- Tx本2,3章の内容を重点的に読む
- トランザクションのアノマリーやisolationに関して自分なりに理解してブログを書く
以下ちょっとした内容のまとめです(まとまってない...)
5.1 Goal and Overview
処理中だけmultiversion。未来永劫マルチバージョンではない。
リカバリも重要。処理中のバッファとリカバリのためのバックアップは別。 バージョンという言葉が意味するものを正確に定義する必要がある。
commitの意味が変わってきた
We will also look at the storage space needed to hold multiple versions.
ディスクベースで書かれている。インメモリのことも考えないといけない。
- バージョンをストレージに保存する必要があるか
- リカバリできるならいらない。
マルチバージョンの時のバージョン数の問題をどう考えているか?
- マルチバージョンの性能をあげるには、バージョンの数を少なくする必要があるという風潮がある
- 古いものはほとんどいらない
- いると思う。read-onlyで必要。
- 複数書くのは賛成だが、沢山書くのは反対。
- LOSTアップデートのアノマリーの定義が必要(曖昧)
- インクリメンタルな操作を行う2つのスレッドだと、片方でロストアップデートが起こる。
- それはreadがおかしい
- インクリメンタルな操作を行う2つのスレッドだと、片方でロストアップデートが起こる。
- バージョンコントロールデータベース、というものもある。それはMVCCと混同すべきではない
The discussion in this chapter continues to consider unaborted transactions only.
重要なことが最後に書かれている...
- アボートはその種類の考慮が必要
- システムアボート
- ユーザーアボート
- ユーザーアボート不要論
- 半順序宣言をユーザーが終えた、というのがユーザーコミット?(よくわからない)
- アボートはその種類の考慮が必要
感想:アボート、コミット、チェックポイントなどなど、システムとユーザーで意味が大きく違う気がする
5.2 Multiversion Schedules
- CSRとは
- コンフリクトの定義は?
- writeが入ること?
- この本では交換可能性
- 順番を変えて意味が変わるならコンフリクト、変わらないならコンフリクトフリー
EXAMPLE 5.1
s = r1(x)w1(x)r2(x)w2(y)r1(y)w1(z)c1c2
バージョンという概念を導入するとExample5.1のhistoryの入れ替えができる。
DEFINITION 5.1
installとは何か?？commitと対になって出てきたが...
過去の論文でread,write,commit,abortの定義を調べたが、writeの明確な定義はない。(古い時代の論文のサーベイ結果)
- RWCAは個々のデータベースで定義すべき
DEFINITION 5.1の2の意味がわからない。
余談
スヌーピー！その発想はなかったです。これからはスヌーピーということにしていきます！
— ゆううき (@y_uuk1) 2018年11月15日
これからはスヌーピーでいきます
— ゆううき (@y_uuk1) 2018年11月15日
デッドロック検出におけるknotとcycleの違いについて
分散処理本読書会で度々話題になっているknotについて簡単にまとめました。
分散処理本でknotの出典としている論文「Some Deadlock Properties of Computer Systems」をknotの説明の箇所より少し後まで読み終えたため、knotについてわかったこと、つまりcycleとの違いやなぜ定義する必要があるのかなどを書きたいと思います。
cycleについて
参考にしている論文の定義を借ります。
定義:サイクルは開始ノードと終了ノードが同じになるようなpathのことです*1
例えば下記の図はc→d→cというcycleが存在しています。これを論文の表記を借りて(c,d,c)と書きます。
knotについて
定義:knotは集合K内の到達可能なノードの厳密な集合のことです。*2
集合Kがknotである場合、Kの要素は以下の特性を持ちます。
- 集合内の要素は互いにK内のどの要素にも到達可能である
- Kに含まれない要素には到達できない
例えば上記に掲載したHOLT論文のFig3の図で言えばcとdはc,d以外への到達を可能にするエッジを持っていません。こちらも論文の表記を借りて{c,d}と書きます。
違いは何か
knotはノードの集合の定義、cycleはエッジの集合(path)の定義です。
- knotを構成しているノードの組み合わせから作成できるcycleのパスが必ずあります。
- 逆にcycleを構成しているエッジのノードの集合は常にknotになっているわけではありません。
Holtの論文ではcとdはcycleを構成し、かつknotになっています。cycleでありながら、knotでは無い図はHoltの論文には掲載されていません。そのような図は分散処理本こと"Distributed Computing: Principles, Algorithms, and Systems"には掲載されています。
こちらの図では(P11,P21,P24,P54,P11)のサイクルが存在していますが、サイクルを構成しているノードの集合{P11,P21,P24,P54}はknotではありません。なぜなら(P11,P32)のエッジが存在しており、ノードP11は集合{P11,P21,P24,P54}以外のノードP32へ到達可能だからです。
定義している集合の要素の種類(ノード/エッジ)が違っていますが、あえていうなら、cycleよりknotの方が厳しい条件を備えているというべきでしょう。(cycleの方がゆるい)
なぜ分けて定義する必要があるのか。
ノード(プロセス)が複数のノードに同時に依存している場合、その依存の種類によってデッドロックの判定方法は変わります。あるケースではcycleを検出するだけではデッドロックの検出条件として不十分だからです。
ケース1.and modelではknotを検出する必要はない。cycleだけで十分
and modelは依存している複数のプロセスを 全て完了する必要がある とするモデル。 デッドロック検出を行うにはサイクルを示せば良い。分散処理本figure 10.1の図ではP11→P21→P24→P54→P11のサイクルが存在しているためデッドロックが発生している。
具体的に書くと、P11の要素はP32とP21の要素両方の終了を待つ必要があるが、P21はP11とサイクルを構成しているため、P21とP11は永遠の完了しない、これはデッドロックである。
ケース2.or modelではcycleだけだと不十分でありknotを示す必要がある
or modelは依存している複数のプロセスに対して、 どれか1つだけの完了を必要 とするモデル。デッドロック検出を行うにはcycleだけでは不十分でknotを示す必要がある。例えば分散処理本figure 10.1の図では
P11→P21→P24→P54→P11のサイクルが存在しているが、これはknotではないのでこのWait-for-graphではデッドロックは発生していない。
具体的に書くと、P11の要素はP32とP21の要素どちらかの終了を待つ必要があるが、P21はP11とサイクルを構成しているが、P32が完了するればP21の完了を待つ必要がないため、これはデッドロックではない。
分散処理本掲載の図のWFGでは赤矢印で示した順P33→P32→P11→P54→P24→P21→P44で処理を完了させることができる。*3
念の為ですが、knotは必ずcycleを構成するのでknotがあればand modelでもデッドロックが発生している事になる。
参考文献
- 1:Ajay D. Kshemkalyani and Mukesh Singhal(2011)Distributed Computing: Principles, Algorithms, and Systems
- 2:RICHARD C. HOLT (1972)Some Deadlock Properties of Computer Systems
Distributed Computing: Principles, Algorithms, and Systems
- 作者: Ajay D. Kshemkalyani
- 出版社/メーカー: Cambridge University Press
- 発売日: 2011/03/03
- メディア: ペーパーバック
- この商品を含むブログを見る
第22回横浜Go読書会に参加
go言語に関する書籍を読む会です。今回から本が新しくなり『Go言語による並行処理』を読んで行きます。
- 作者: Katherine Cox-Buday,山口能迪
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/10/26
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
初回なので参加者の方が多かったです(初参加の方も)
yokohama-go-reading.connpass.com
誤植など
epub版固有の誤植というのがいくつか見つかりました。
ちなみに電子版で呼んでる方はpdfが多い気がしますが、私はepub派です。
組み版や翻訳、原著との差分に関して気になる点
柴田さんをはじめ、複数の方から意見が出ました。
「驚異的並列」の元の単語(embarrassingly parallel)を書いて欲しい。
- 対応する原文の単語をよく併記している(by柴田さん)
原著ではソースに行番号が書かれている。
- p5では3行目、５行目と本文中で参照されているので消すべきではないと思うが...
var data int go func() { // ❶ data++ }() if data == 0 { fmt.Printf("the value is %v.\n", data) }
ここで、3 行目と 5 行目ではともに dataという変数にアクセスしようとしています。
- 組み版が気になる。原著ではソースがまたがっている(p5-6)が、これは無理やり改ページした後にソースを掲載するべき
並列性と並行性
- Goでは並列処理がかけない。並行処理だけ。並列処理ができる言語はないような気がする。
原著では並行性は Concurrency ,並列性は Parallelism になっているはず
- 確認したところそのようになってた。
アムダールの法則:並列化による性能向上
Spigotアルゴリズム:円周率の計算を並列化する方法
CPUのクロックは長いこと3,4Ghzで止まっている。
2010年頃は10GHzの時代が来る!とか言ってた時代もあった- 2000年前後だそうです
競合状態(race condition)
- 競合状態の検出は困難。
並列性を実現するのはシステムコールでやる。
- あるプロセスを特定のCPUに割り当てるシステムコールが存在する。
過去にはシングルコアで動かないプログラムをマルチコアCPUで動かすと、想定していなかった競合に関するバグが発生した。
golangのデッドロック検出機能
type value struct { mu sync.Mutex value int } var wg sync.WaitGroup printSum := func(v1, v2 *value) { defer wg.Done() v1.mu.Lock() // ❶ defer v1.mu.Unlock() // ❷ time.Sleep(2 * time.Second) // ❸ v2.mu.Lock() defer v2.mu.Unlock() fmt.Printf("sum=%v\n", v1.value+v2.value) } var a, b value wg.Add(2) go printSum(&a, &b) go printSum(&b, &a) wg.Wait()
$ go run sample.go
fatal error: all goroutines are asleep - deadlock!
goroutine 1 [semacquire]:
sync.runtime_Semacquire(0xc000014054)
/usr/local/go/src/runtime/sema.go:56 +0x39
sync.(*WaitGroup).Wait(0xc000014054)
/usr/local/go/src/sync/waitgroup.go:130 +0x64
main.main()
/Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:34 +0x122
goroutine 5 [semacquire]:
sync.runtime_SemacquireMutex(0xc000014074, 0x0)
/usr/local/go/src/runtime/sema.go:71 +0x3d
sync.(*Mutex).Lock(0xc000014070)
/usr/local/go/src/sync/mutex.go:134 +0xff
main.main.func1(0xc000014060, 0xc000014070)
/Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:24 +0xa1
created by main.main
/Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:32 +0xea
goroutine 6 [semacquire]:
sync.runtime_SemacquireMutex(0xc000014064, 0x0)
/usr/local/go/src/runtime/sema.go:71 +0x3d
sync.(*Mutex).Lock(0xc000014060)
/usr/local/go/src/sync/mutex.go:134 +0xff
main.main.func1(0xc000014070, 0xc000014060)
/Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:24 +0xa1
created by main.main
/Users/yuyabu/Documents/Study/go/chap1/training2/training2.go:33 +0x114
exit status 2
上記のプログラムはsleep関数を抜くとdeadlockが発生しにくくなる。
複数のロックを取るときは、同じ順番で取ることが重要。
- Edgar Coffmanのdeadlock検知の論文が挙げられている
golangで1ミリ秒ごとにxxするという書き方
golangでこの構文は何か？という話題になった。
for range time.Tick(1 * time.Millisecond) { cadence.Broadcast() }
- 1ミリ秒待ってブロードキャスト、という意味になる。
- 無限ループの先頭にsleep()関数を使うことでもかけるが、チャネルを使ってこのように書くこともできる
- 上記ソースのtime.Tickのチャネルは閉じなくていいのか?
- 残るけど、mainが死んだ時に全員死ぬのでOK
condとmutexの違い
- condは外部からbroadcast,signalで起こすことができる。
- broadcastとsignalの違いは全てのcondを起こせるか、どうかの違いがある。
cadence := sync.NewCond(&sync.Mutex{})
go func() {
for range time.Tick(1 * time.Millisecond) {
cadence.Broadcast()
//broadcastは全てが起きる
//
}
}()
takeStep := func() {
cadence.L.Lock()
cadence.Wait()
//waitじにはロックを解除する。、waitを抜けたときはlockを獲得している。
//ブロードキャスト、もしくはシグナルの受診時にロックを獲得した状態でwait()のいちに戻ってくる
//なお復帰、ロック再獲得はatomicに実行される
cadence.L.Unlock()
}
他
- Juliaは言語仕様にchanelがあるらしい
次回は2.3「これがどう役に立つのか」（p.29）から
go言語で数値-文字変換を行う方法
基本的にプログラミングをするときは全部Javaだと思って書いているので、他言語の挙動に困惑することがよくあります。
Go言語では文字と数値を+演算子で連結した時に、数値が文字コードとして解釈されているような変換がされたので、
数値を文字に変換する方法を調べました。
実行環境
jshell
$ jshell -v | JShellへようこそ -- バージョン9.0.1
go
$ go version go version go1.11 darwin/amd64
謝った文字列変換
fmt.Println("test" + 65) //出力結果:testA
この通り65がAに変換されました。
※おそらく内部でstring(65)が実行されているものと思われます
JavaだとStringとint型を+で連結すると文字型に型変換された65が連結に利用されています。
jshell> String a = "test" + 65 a ==> "test65"
strconv.Itoaを使う
fmt.Println("test" + strconv.Itoa(65)) //出力結果:test65
内部ではFormatIntを呼び出しているようです。
// FormatInt returns the string representation of i in the given base, // for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z' // for digit values >= 10. func FormatInt(i int64, base int) string { if fastSmalls && 0 <= i && i < nSmalls && base == 10 { return small(int(i)) } _, s := formatBits(nil, uint64(i), base, i < 0, false) return s } // Itoa is shorthand for FormatInt(int64(i), 10). func Itoa(i int) string { return FormatInt(int64(i), 10) }
FormatIntをそのまま利用しても結果は同じになります。
fmt.Println("test" + strconv.FormatInt(int64(65), 10)) //出力結果:test65
参考
https://stackoverflow.com/questions/10105935/how-to-convert-an-int-value-to-string-in-go
分散処理本第40回に参加
恒例のDistributed Computingこと分散処理本を読む会になります。
Distributed Computing: Principles, Algorithms, and Systems
- 作者: Ajay D. Kshemkalyani,Mukesh Singhal
- 出版社/メーカー: Cambridge University Press
- 発売日: 2008/04/17
- メディア: Kindle版
- この商品を含むブログを見る
「10.9 Kshemkalyani–Singhal algorithm for the P-out-of-Q model」の続き(10.9.2 The algorithm)から、10章の最後までを読みきりました。
次回は「CHAPTER 11 Global predicate detection」からになります。*1
学んだこと
P-out-of-Qリソースモデルにおけるデッドロック検出アルゴリズム""Kshemkalyani–Singhal algorithm”について学びました。 こちらは個別の記事でブログを書きたいと思います。
分散処理本のKindle版に見つかった落丁について
「Algorithm 10.4 Deadlock detection algorithm」として挙げられている擬似コードの図が 「Algorithm 10.3 Kshemkalyani–Singhal algorithm for the P-out-of-Q model.」の図と全く同じものば謝って掲載されています。(しかも同じ擬似コードを2回連続で並べています)
この落丁はKindle本だけであり、紙の本では10.4の擬似コードで適切なアルゴリズムが紹介されていました。
読み手の@okachimachiorz1さんと@Shin1Miyazawaさん以外の3人の参加者はKindleを参照していたので、 読み手の説明しているアルゴリズムと対応しているものが本中になく非常に混乱しました。
ちなみに表示すべき内容は以下の論文から引用されているアルゴリズムの図になります。
[26]の元はこれのようだ。https://t.co/lEeD89TR9B
— メメ明治。 (@meijik) 2018年11月7日
分散システムにおけるデッドロック対処の章を読み終えて
実際の分散システムではデッドロック検知や防止は難しので、タイムアウトでアボートさせる手法が一般的だそうです。 あえて本書に掲載されているような検知、防止を実装するようなシステムは アボートのコストが非常に高く、それを避けたいのでは? という議論になりました。
*1:キリがいいので参加しようと思っている人はチャンスですよ!!!
