Mutexを実装する implementation of mutex
- 1. Mutexを実装する Implementation of Mutex The 17/01/05 MTG of Eyes, JAPAN ito
- 2. 自己紹介/Self-Introduction - 伊藤勇希/Yuki Ito - ito/acomagu/publmag1 - おすすめのメイドカフェはシャッツ キステ/橙幻郷(ノマドに最適) My favorite Maid-Cafe: Schatzkiste, TouGenKyo - ももくりが終わっちゃって悲しい I’m really sad for end of MomoKuri.
- 3. 今夜はみんなの目線をLock! Today, I gonna Lock your eyes at me!
- 4. 目次/Index 1. 並行処理/並列処理とは? What is concurrent/parallel processing? 2. What are Atomic, Semaphore and Mutex? 3. Mutexの実装 / Implement Mutex 4. Lockのその先へ / Beyond the Lock
- 6. is
- 7. 何 what
- 8. “並列処理/並行処理” “Concurrent/Parallel Processing” 複数の仕事を同時にする Do multiple tasks at the same time
- 9. 複数の仕事を同時にする Do multiple tasks at the same time
- 10. 複数の仕事を同時にする Do multiple tasks at the same time 誰が / Who
- 11. 複数の仕事を同時にする Do multiple tasks at the same time 僕が / I
- 12. 複数の仕事を同時にする Do multiple tasks at the same time 僕と兼沢さんが I and Kanesawa
- 13. 僕が / I 複数の仕事を同時にする Do multiple tasks at the same time 僕と兼沢さんが I and Kanesawa 複数の仕事を同時にする Do multiple tasks at the same time
- 14. 僕が / I 複数の仕事を同時にする Do multiple tasks at the same time 僕と兼沢さんが I and Kanesawa 複数の仕事を同時にする Do multiple tasks at the same time 並行処理 Concurrent Processing 並列処理 Parallel Processing 諸説あります
- 15. まとめると 並行処理 → ひとつのCPUが複数の処理を 同時に(見えるように)行う 並列処理 → 複数のCPUが別の処理を同 時に行う 諸説あります
- 16. ITO KANESAWA
- 17. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! あるお昼時 / One lunchtime
- 18. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. あるお昼時 / One lunchtime
- 19. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... あるお昼時 / One lunchtime
- 20. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 4人にすればいいんだな! 書き換えよう! It’s 4! Let’s rewrite! あるお昼時 / One lunchtime
- 21. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! あるお昼時 / One lunchtime
- 22. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は4人か From the roster, 4 people will do. あるお昼時 / One lunchtime
- 23. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は4人か From the roster, 4 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... あるお昼時 / One lunchtime
- 24. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は4人か From the roster, 4 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 5人にすればいいんだな! 書き換えよう! It’s 5! Let’s rewrite! あるお昼時 / One lunchtime
- 25. 5人分たのむよ? I’m ordering it for 5.
- 26. 5人分たのむよ? I’m ordering it by 5. SUCCESS!!
- 27. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! またあるお昼時 / Another lunchtime
- 28. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. またあるお昼時 / Another lunchtime
- 29. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... またあるお昼時 / Another lunchtime
- 30. おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch! 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... またあるお昼時 / Another lunchtime おなかへったー! そうだ、お弁当頼もう! I’m so hungry! Oh right, let’s order a lunch!
- 31. 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. またあるお昼時 / Another lunchtime
- 32. 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... またあるお昼時 / Another lunchtime
- 33. 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 4人にすればいいんだな! 書き換えよう! It’s 4! Let’s rewrite! またあるお昼時 / Another lunchtime
- 34. 名簿を見ると、今頼む予定の人数は3人か From the roster, 3 people will do. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 4人にすればいいんだな! 書き換えよう! It’s 4! Let’s rewrite! またあるお昼時 / Another lunchtime 4人にすればいいんだな! 書き換えよう! It’s 4! Let’s rewrite!
- 35. 4人分たのむよ? I’m ordering it for 4.
- 36. 4人分たのむよ? I’m ordering it by 4.Uh?
- 37. 整理すると / In summary, ● 伊藤が人数を読み取り、計算し、結果を書き込む Ito read the number of people, calculate and write the result. ● 兼沢が人数を読み取り、計算し、結果を書き込む Kanesawa read the number of people, calculate and write the result. どちらかが読み取った後、書き込む前にもう一方が読み取ってしま うと、矛盾が生じてしまう! It makes conflicts that one’s reading between another’s reading and writing!
- 39. 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 解決策: もう一人が書き込むまで待つ Solution: Wait until another writes to read 名簿は... おや、伊藤くんが考え中みたいだ Roster… Oh, Ito is considering deeply. 伊藤くんが書き終わるまで待ってあげよう! I’ll do after his writing!
- 40. 名前をつけよう - 「どちらかが読み取った後、書き込む前にもう一方 が読み取ってしまうと、矛盾が生じてしまう!」問題 →データ競合 “It makes conflicts that one’s reading between another’s reading and writing” Problem: Data Race - 「もう一人が書き終わるまで待つ」こと→Mutex To “wait until another writes to read”: Mutex
- 41. 名簿は... おや、伊藤さんが考え中みたいだ Roster… Oh, Ito is considering deeply. どうやってMutexする? 伊藤さんが書き終わるまで待ってあげよう! I’ll do after his writing!
- 42. 他人をブロックする? 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 一人増やせばいいんだから...ええと... I only have to increase it by one… well... 父さんはここを絶対に通さん! I never make way for you! ...なにっ! ...Shit!
- 45. 札を置いておく?
- 52. 「札」の改良アルゴリズム - デッカーのアルゴリズム - ピーターソンのアルゴリズム - ランポートのパン屋のアルゴリズム - Szymanskiのアルゴリズム - Taubenfeld の Black-White Bakery Algorithm
- 53. 世の中には頭のいい人がいる - デッカーのアルゴリズム - ピーターソンのアルゴリズム - ランポートのパン屋のアルゴリズム - Szymanskiのアルゴリズム - Taubenfeld の Black-White Bakery Algorithmこれを実装してみよう!
- 54. 元のプログラム
- 55. 元のプログラム
- 56. 元のプログラム
- 57. 元のプログラム
- 58. 元のプログラム
- 59. 元のプログラム 結果は!?
- 66. えーっ!
- 67. こんだけためといて
- 69. うまく行かなかった理由 ハッ...! もしや... Out of Order実行!? 「「「残像だ」」」 ?????！！
- 71. Out-of-Order実行とは What’s Out-of-Order execution 実行順序を守らない実行である! Not to keep execution in the decided order!
- 72. 何だって OMG
- 73. - プロセッサは高速化のために、先に実行 できる命令から先に実行することがある - 現代ではほとんどのプロセッサが Out-of-Order実行をする - コンパイラも似たような最適化を行うこと がある Out-of-Order実行とは What’s Out-of-Order execution
- 78. Mutexは実装できない Mutex can’t be implemented.
- 81. 最初?
- 84. Good Luck!
- 85. 解決策: 読んだ後誰かが書き換えていないか確認す る Solution: Check if anyone rewrite it or not この名簿... くんくん... This roster… Sniff sniff... なんだか伊藤さんが書き換えたにおいがするぞ It’s like the smells of Ito’s rewriting. 最初から計算し直そう Start over again.
- 86. 解決策: 書き込むときに変わっていないか確認する Solution: Check if it changed or not when write 4人にすればいいんだな! 書き換えよう! It’s 4! Let’s rewrite! あれ、既に3人から4人に書き換わってる...? Hmm, it was changed from 3 to 4 already…? なにか変だから最初から計算し直すか Something is wrong so start over again.
- 87. LL&SCとは What’s LL&SC? - Load-Link and Store-Conditional - Alpha、PowerPC、MIPS、ARM等に定 義される命令
- 88. CASとは What’s CAS? - Compare-And-Swap - Intel, AMD and so on
- 89. LL&SCとは What’s LL&SC? ● LL命令→読み取り LL Instruction→Reading ● SC命令→書き込み。しかしもし前回のLL命令の 後誰かが書き換えた形跡があれば、命令は失敗 する SC Instruction→Writing. But if updates have occurred since last LL instruction, it fails.
- 90. Increment関数の全体 and it can be called in Golang as function.
- 91. LL命令で読み込み Read with LL instruction.
- 92. 1を足し、 Add 1.
- 93. SC命令で書き込む。 Write the value with SC instruction.
- 94. もしSC命令が失敗したら、戻ってもう一度 If SC instruction fails, go back and try again.
- 95. こんな感じでアセンブリを書くと Write assembly such like,
- 96. Go言語で関数として呼び出せる and it can be called in Golang as function.
- 97. 動け! Works!
- 100. ん? Hmm?
- 101. LL&SC使えば With LL&SC,
- 103. 使用中の札をかけておこう 札を置いておく? 札がないから、誰も使用中じゃないな! 札がないから、誰も使用中じゃないな! 使用中の札をかけておこう 読み取り Reading 読み取り Reading 書き込み Writing 書き込み Writing これもできんじゃね? I can also this, possibly?
- 104. LL命令でフラグの内容を読み取り。 Read the value of flag with SC instruction.
- 105. SC命令で”1”を書き込む Write “1” to it with SC instruction.
- 106. もしSC命令が失敗したら、戻ってもう一度 If SC instruction fails, go back and try again.
- 107. もし既にフラグが”1”だったら、戻ってもう一回(スピンロッ ク) If the value of the flag is “1”, go back and try again.
- 108. The whole code.
- 109. lock()では、lockedフラグ(札)を1に変更(さっきのアセンブリ) In lock(), change the value of locked flag to 1(the assembly)
- 110. unlock()では、lockedフラグを0に変更 In lock(), change it to 0
- 111. あとはlock()とunlock()で囲めば... And, put it between lock() and unlock()...
- 113. できた! It worked!
- 114. まとめ MutexはLL&SCやCAS等の アセンブリ命令を使用すると作れる! (それ以外だと厳しい) Mutex can implemented by assembly instructions like LL&SC or CAS. (The other ways will be difficult)