Multithreading - why use, why difficult, how to solve -

マルチスレッド プログラミングについて
- 必要となる背景
- なぜ難しいのか
- 難しさを解決するためにどのような手法があるのか
のご紹介です。

主にマルチスレッド プログラミングの全体的な理解を得たいプログラマー向け。

Transcript

1. ϚϧνεϨου ϓϩάϥϛϯά - ࢖͏ҙٛͱͦͷ೉͠͞ฤ - and - σʔλෆ੔߹Λղܾ͢Δฤ - saiya_moebius 1
2. ϚϧνεϨου ϓϩάϥϛϯά લฤ - ࢖͏ҙٛͱͦͷ೉͠͞ฤ - 2
3. ϚϧνεϨου • Web Application Runtime • Ruby: puma (Heroku), Raptor (Passenger 5) • Java: tomcat, weblogic, GlassFish … • Native Application • Most of modern Apps (incl. Smartphone Apps) • Large scale batch process 3
4. ϚϧνεϨου͕਎ۙͳ࣌୅ • ੲ: ͦ΋ͦ΋ϋʔυతʹͦ͜·Ͱ΍Δҙٛͳ͠ • গ͠ੲ: Ϛϧνϓϩηε(ޙड़)ͷ࣌୅ • ࠷ۙ: ࣗ෼ͷॻ͍ͨΞϓϦ͕ϚϧνεϨου؀ڥʹ৐͔ͬΔ / ࣗ෼ͰϚϧνεϨουରԠ͢Δ࣌୅ ݱ୅తϓϩάϥϛϯάͰ͸਎ۙʹͳ͖͍ͬͯͯΔϚϧνεϨου ϓϩάϥϛϯάʹ͍ͭͯ • ͦ΋ͦ΋ͲͷΑ͏ͳಈػͰɺԿͷͨΊʹ΍Δͷ͔ • ͲͷΑ͏ͳࠔ೉͕͋͞Δͷ͔ • ͦΕʹର͢ΔΞϓϩʔν Λ͝঺հ 4
5. εϨου • ϓϩάϥϜΛىಈ͢Δͱ࡞ΒΕΔͷ͕ϓϩηε • Windows Task Manager Ͱݟ͑Δ͋Ε • ϓϩηε͸ϝϞϦྖҬΛ࣋ͭ • ϓϩάϥϜͷ࣮ߦঢ়ଶ͕εϨου • ࠓ͜ͷίʔυΛ࣮ߦͯ͠·͢Αɺͱ͍͏ঢ়ଶΛ࣋ͭ http://www.atmarkit.co.jp/ait/articles/0503/12/news025.html • ϚϧνεϨου: ϓϩηε಺ʹεϨουΛෳ਺࡞Δ • 1 ͭͷϝϞϦ(σʔλ)Λڞ༗͠ͳ͕ΒίʔυΛෳ਺ฒྻ࣮ߦ • Ϛϧνϓϩηε: ϓϩηεΛෳ਺࡞Δ (εϨου͸ 1 ͭͮͭ) • ϝϞϦΛڞ༗͠ͳ͍ͰίʔυΛෳ਺ฒྻ࣮ߦ 5
6. ͳͥϚϧνεϨου͔? • ϚϧνίΞ CPU ͷར༻ • ୯ҰίΞੑೳͷਐาͷಷԽ (ϑϦʔϥϯνͷऴᖼ) • I/O ଴ͪ࣌ؒͷ༗ޮ׆༻ • Disk : Resource file, log file • Over Network : HTTP API call, DB query • ଴ͨͤΔ΂͖Ͱͳ͍ॲཧΛ଴ͨͤͳ͍ • ཪଆͰ࣌ؒͷֻ͔ΔॲཧΛ͠ɺදଆ͸ࢭΊͳ͍ ίΞ : εϨουΛ࣮ߦ͢ΔͨΊͷϋʔυ, ݱ୅త CPU ʹ͸ෳ਺͋Δ 1 ͭͷ I/O ଴ͪͷؒʹ CPU ͸਺ສʙ਺ඦສճҎ্ͷ໋ྩΛॲཧͰ͖Δ 6
7. ͳͥϚϧνϓϩηεͰͳ͍ʁ ϝϞϦ͕ڞ༗͞Εͳ͍͜ͱʹΑΔແବ͕͍ͬͺ͍: • ϓϩάϥϜࣗମΛෳ਺ϩʔυ • OS ଆͷ޻෉(CoW ౳)΋͋Δ͕ɺಛʹ GC ͷ͋Δݴޠͱ૬ੑѱ • σʔλίϐʔͷΦʔόʔϔου • CPU ଆͷ࣋ͭΩϟογϡͷώοτ཰ͷ௿Լ • ϛυϧ΢ΤΞɾΞϓϦଆͰͷϝϞԽ࣮૷ͱ૬൓ • ΞϓϦଆ͕΍Βͳͯ͘΋ϛυϧ΢ΤΞଆͰ৭ʑ΍͍ͬͯΔ͜ͱ͕ଟ͍ ϓϩάϥϜͦΕࣗମ͕਺ඦ MB ఔ౓ߦ͘͜ͱ͸βϥ ϝϞԽ : ࢖͍·ΘͤΔσʔλɾܭࢉ݁ՌΛอଘ͠࢖͍ճ͢࠷దԽख๏ 7
8. ࣮ʹద౰ͳᄻ͑ Ϛϧνϓϩηε ֤͕ࣗࣗ෼ͷ͓ՈͰݸผʹ࡞ۀ͢Δ ( ࡞ۀ৔ॴ͕ਓ਺෼ඞཁɺ࡞ۀաఔ΍݁ՌΛ૬ޓڞ༗͠ͳ͍ ) ϚϧνεϨου શһ͕ҰՕॴͰڞಉ࡞ۀ͢Δ ( ࡞ۀ৔ॴ΋ɺ࡞ۀͷதؒɾ࠷ऴ݁Ռ΋શһͰڞ༗ ) 8 ݫີʹ͸ɾ࣮ࡍͷ࣮૷্͸৭ʑͳࣄ৘͕͋Δ͕ɺ͜ͷࢿྉͰ͸ ʮฒߦॲཧʹͯϝϞϦۭؒΛڞ༗͍ͯ͠Δ൱͔ʯͰ࢖͍෼͚
9. ϚϧνεϨουʹͯ͠Έͨʂ → രࢮ ϚϧνεϨου͸ݪཧతʹߴੑೳʂ ͨͩ͠ɺͦΕ͸ͪΌΜͱಈ͚͹ͷ࿩… • ԿͰ΋ͳ͍͸ͣͷίʔυͰҟৗऴྃ͢Δ͜ͱ͕͋Δ • ܭࢉ݁Ռ͕߹ͬͯͳ͍͜ͱ͕͋Δ • ී௨ʹϛυϧͷػೳΛ࢖ͬͨΒམͪΔ͜ͱ͕͋Δ ͱ͍֤ͬͨछόάΛ৯Β͏͜ͱ͕େมଟ͍ 9 ࡞ۀ৔ॴ΋աఔ΋ڞ༗͍ͯ͠ΔͷͰɺޓ͍ͷॲཧ͕ѱ͍ҙຯͰ΋૬ޓ࡞༻ͯ͠͠·͏
10. Α͘ݴΘΕΔྫ ۜߦޱ࠲ͷᄻ͑ (200+200\ ༬͚ͨͷʹยํϩετ) http://www.atmarkit.co.jp/ait/articles/0505/25/news113.html
11. γϯάϧεϨουͷෳࡶ౓ ϓϩάϥϜͷ࣮ߦεςοϓ਺ͱൺྫ: ͳΜ͔ॲཧ 1 ϝϞϦ εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 4 11
12. ϚϧνεϨουͷෳࡶ౓ શεϨου͕ಉ͡λΠϛϯάͰಈ͘ͳΒͱ΋͔͘… ͳΜ͔ॲཧ 1 ϝϞϦ ෳ਺εϨου͔Β ಡΈॻ͖ εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 4 ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 4 12
13. ϚϧνεϨουͷෳࡶ౓ ࣮ࡍ͸ಈ͚Δ࣌ʹಈ͘ͷͰɺॲཧεςοϓ਺ͷεϨου਺৐ͷ૊Έ߹Θ͕ͤ… ϝϞϦ ಡΈॻ͖͕ ೖΓཚΕͯෆ੔߹ εϨου ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 4 1000 Λ 4 ৐͢Δ͚ͩͰ 1 ஹ ࣮ࡍͷϓϩμΫτͷෳࡶ౓͸ߋʹେ ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 3 13
14. ͞Βʹ࠷దԽ͕ೖΔ͜ͱͰ… ݴޠॲཧܥɾCPU ͷ࠷దԽ͸ʮผεϨου͔Βಉ͕͡σʔλΛಡΈॻ͖͞Εͳ͍ʯલఏ ίϯύΠϥɾJIT ͷ࠷దԽྫ • ॲཧͷॱংೖΕସ͑ → ผͷεϨου͔ΒݟΔͱมͳॱংͰσʔλ͕ॻ͖׵ΘΔ • ϝϞϦͷಡΈॻ͖Λ 1 ճʹ·ͱΊΔ → ม਺ΛԿճಡΜͰ΋ݹ͍஋͕औΕͯ͠·͏ CPU ͷ࠷దԽྫ • ໋ྩͷॱংೖΕସ͑, ϝϞϦͷಡΈॻ͖Λ·ͱΊΔ, ϝϞϦͷಡΈॻ͖தʹଞͷ໋ྩΛ࣮ ߦ • ϝϞϦͷ಺༰ΛखݩʹΩϟογϡ (CPU Core ผͷΩϟογϡ΋ͦ͏Ͱͳ͍΋ͷ΋͋Δ) 14
15. Ͳ͏͢Δ͔ εϨου ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 4 ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 3 ϝϞϦ ಡΈॻ͖͕ ೖΓཚΕͯෆ੔߹ ύϑΥʔϚϯεΛ֬อͭͭ͠΋σʔλෆ੔߹Λ๷͙΂͠ʂ → ϚϧνεϨου ϓϩάϥϛϯάͷͨΊʹੵΈॏͶΒΕ͖ͯͨ஌ݟΛ׆༻ 15
16. ϚϧνεϨου ϓϩάϥϛϯά ޙฤ - σʔλෆ੔߹Λղܾ͢Δฤ - 16
17. ෆ੔߹ʹରॲ͢ΔͨΊͷΞϓϩʔν ಉ࣌ʹσʔλʹ৮ΕΔεϨουΛݶఆ͢Δܥ (௿ฒྻ౓, ൺֱతສೳ) • Lock / Semaphore • Read-Write Lock • Optimistic Lock (CAS loop) • Asynchronous Callback / Event Driven • Queueing / Pipelining • Messaging • Immutable Object (Atomic Reference, Hazard Pointer) • Local Variable, Thread Local Storage ͦ΋ͦ΋ڝ߹͠ͳ͍͔Βେৎ෉ͩΑܥ (ߴฒྻ౓, ϝϦοτେ) 17
18. Lock (a.k.a Semaphore) 1. σʔλͷಡΈɾॻ͖։࢝લʹϩοΫΛ֬อ 2. σʔλͷಡΈɾॻ͖׬ྃޙʹϩοΫΛղ์ ଞεϨου͕ϩοΫΛ֬อ͠Α͏ͱ͢Δͱɺ2 ·Ͱ଴ͨ͞ΕΔ • ෆ੔߹ͳσʔλॻ͖׵͑Λ͞Εͯ͠·͏৺഑͕ͳ͘ͳΔ • ͦ΋ͦ΋ಉ࣌ʹσʔλΛಡΈॻ͖͍ͯ͠ͳ͍ 18 ॳֶऀ޲͚ʹ঺հ͞Ε͕͕ͪͩɺ᠘͕ଟ͠ (ޙड़) ͜ͷؒɺଞεϨου͸ϩοΫΛ֬อͰ͖ͳ͍
19. Lock ͷ᠘ 0: ղ์࿙Ε • ͢ͰʹϩοΫ͕ѲΒΕ͍ͯΔͱɺ୭΋ϩοΫͰ͖ͳ͍ • ϩοΫͷղ์͠๨Ε͕ҰՕॴͰ΋͋ΔͱγεςϜશମͷఀࢭʹ, ྫ͑͹͜ͷΑ͏ͳ: 1. ୯ʹղ์ॲཧΛॻ͖๨Εͨ 2. ޙ͔Β৚݅෼ذॲཧΛ଍ͨ͠෦෼Ͱղ์๨Ε 3. ྫ֎ൃੜ࣌(ҟৗൃੜ࣌)ʹղ์͢ΔͨΊͷϑΥϩʔॲཧ͕ͳ͔ͬͨ 4. ϑΥϩʔॲཧ͸ॻ͍͕ͯ͋ͬͨɺͦͷϑΥϩʔॲཧ్͕தͰҟৗऴྃ͢Δ͜ͱ͕͋ͬͨ 5. εϨουڧ੍ऴྃ࣌ʹղ์͞Εͳ͍࢓༷ͩͬͨ • synchronised (Java), lock (C#), RAII (C++) ͱ͍ͬͨݴޠػೳ͕࢖͑Δہ໘Ͱ͸ੋ͕ඇͰ΋࢖͏΂͠ • ͨͩ͠OSɾݴޠॲཧܥɾϥΠϒϥϦͷݶքΛ͖ͪΜͱௐ΂ͯˍݕূͯ͠࢖͏͜ͱ (ಛʹ্ه 3, 4, 5) • ݴޠػೳ͕࢖͑ͳ͍ہ໘Ͱ͸ɺ্هͷΑ͏ͳ͋ΒΏΔέʔεΛ૝ఆͯ͠ॻ͘΂͠ 19
20. Lock ͷ᠘ 1: ੑೳ͕ग़ͳ͍ • ฒߦͰॲཧΛ͢Δͷ͕ϚϧνεϨου • ͕ͩɺLock ΛѲΒΕ͍ͯΔͱɺ1 ͭҎ֎ͷεϨου͸଴ͨ͞ΕΔ ฒߦॲཧͷͨΊʹฒߦॲཧ͠ͳ͍ࠜຊతໃ६… ϚϧνεϨουʹ͢Δ͜ͱͰಘ͔ͨͬͨੑೳ޲্͕ಘΒΕͳ͍ 20 ଞͷεϨουΛ͋·Γ଴ͨͤͳ͍ͱ͍͏֬৴͕͋ΔͳΒΞϦ
21. Lock ͷ᠘ 2: Dead Lock εϨουͦΕͧΕ͕ Lock Λอ࣋ ࣍ͷϩοΫΛཁٻ -> ͓ޓ͍Λ଴ػ -> ͣͬͱ଴ػ… Possible Solution: • ϩοΫ֫ಘͷॱংΛܾΊɺؾΛ͚࣮ͭͯ૷͢Δ • ࣮૷͕େมɺ(ઌड़ͷෳࡶੑͷͨΊ)όάΓ΍͍͢͠ςετ΋ࠔ೉ɺͱےѱ • Ұఆ࣌ؒҎ্ϩοΫऔΕͳ͔ͬͨΒ and/or Dead Lock ݕ஌ͨ͠Β rollback • rollback & retry Ͱ͖ΔΑ͏ͳॲཧ಺༰ͳΒ͋Γ (࣮૷ͷख͕ؒ૿͑Δ͕) 21 DBMS ͷߦϩοΫͰ΋ಉ͡໰୊͕ى͜Γ͑Δ͜ͱͰ༗໊ MySQL (InnoDB) ͸࢖͍खʹ rollback ʹରԠ͢Δ͜ͱΛڧ੍͍ͯ͠Δ
22. Lock ͷ᠘ 3: Unfair ը໘΍ API ͳͲϦΞϧλΠϜͰ࢖ΘΕΔ༻్Ͱ͸ɺॲཧͷਐḿ͕ภΒͳ͍ੑ࣭(fairness)͕ඞཁ Fairness ͕֬อ͞Ε͍ͯͳ͍৔߹ɺӡ࣍ୈͰಛఆͷεϨου͹͔Γ଴ͨ͞ΕΔ͜ͱ͕͋Δ • ଟ͘ͷ Lock ࣮૷͸ fairness อূ͕ͳ͍ͷͰɺʮҰ෦ͷϦΫΤετʹର͚ͯͩ͠Ϩεϙϯε͕ڧ྽ʹѱԽ ͢Δʯͱ͍ͬͨ঱ঢ়͕ى͜ΔݪҼʹͳΔ • ݴޠॲཧܥɾϥΠϒϥϦʹΑͬͯ͸ΦϓγϣϯͰ fairness ΛอূͰ͖Δ Lock ࣮૷΋͋Δ • ͨͩ͠ɺଟ͘͸ʮઌணॱͰϩοΫ͢Δ͜ͱΛอূ͢Δʯͱ͍͏ҙຯͰͷ fairness อূ • fairness ͷҙຯ͕χʔζͱҰக͍ͯ͠Δ͔͸ཁ஫ҙ • ຊ౰ʹඞཁͩͬͨͷ͸ϩοΫઐ༗࣌ؒͰͷ fairness Ͱ͋ͬͨɺͱ͍ͬͨ͜ͱ͕ଟ͠ • ͦ͏͍ͬͨ৔߹ɺޙड़ͷ pipeline ύλʔϯ(+ ༏ઌ౓෇͖Ωϡʔ)Λݕ౼͢΂͠ 22 fair ͳϩοΫ࣮૷΋಺෦తʹ͸༏ઌ౓෇͖Ωϡʔʹͳ͍ͬͯΔ΋ͷ͕ଟ͍
23. Lock ͷ᠘ 4: ༏ઌॱҐͷٯస ࢀߟ: Ր੕Ͱ͍͍ͬͨԿ͕ى͖ͨͷ͔? - Glenn Reeves http://www.unixuser.org/~euske/doc/risks-ja/mars.html Possible Solution: • Mars Pathfinder ͷ vxWorks ͷΑ͏ʹ͜ͷ໰୊ʹରॲ͢ΔͨΊͷ Semaphore ֦ு͕͋Ε͹ར༻͢Δ • lock ΛѲ͍ͬͯΔ࠷தͷॲཧΛ୹࣌ؒͰऴΘΒͤΔ (ଟ͘ͷܭࢉػ͸ϕετΤϑΥʔτࢤ޲…) • ͦ΋ͦ΋௿༏ઌ౓λεΫ͸ϩοΫΛѲΒͳ͍Α͏ʹઃܭ͢Δ 23
24. Read-Write Lock Lock ͷѥछ, σʔλΛಡΉ͚ͩͷॲཧ͕ෳ਺ฒྻ૸ͬͯ΋σʔλෆ੔߹͸ͳ͍͜ͱΛ׆༻: • Read Lock : σʔλͷಡΈऔΓεϨου͸ෳ਺ಉ࣮࣌ߦ OK • Write Lock : σʔλͷॻ͖ࠐΈεϨου͕͍Δؒ͸ଞશһ଴ػ Lock ͷ᠘ 1, 3 (ੑೳ͕ग़ͳ͍, Unfair)͕؇࿨͞ΕΔ ଟ͘ͷΞϓϦɾγεςϜͰ͸ߋ৽ܥΑΓ΋ࢀরܥΞΫηε͕1ܻҎ্ଟ͍ͨΊ༗༻ Lock ͷ᠘ 2, 4 (Dead Lock, ༏ઌॱҐͷٯస)͸վળ͠ͳ͍ Ճ͑ͯɺRead Lock தʹ Write Lock ଴͕ͪೖͬͨ৔߹ͷڍಈʹผͷ᠘͕͋ΔͷͰ஫ҙ ( Write Lock ଴͕ͪ͋Δ৔߹ɺଟ͘ͷ࣮૷Ͱ͸ޙଓͷ Read Lock ཁٻ΋଴ͨͤΔ(Write Lock ͷͨΊʹ Reader ͕͍ͳ͍ঢ়ଶΛ࡞Ζ͏ͱ͢Δ)ɻ ͦͷ݁ՌɺWrite Lock Λ଴͍ͨͤͯΔ Read Lock ͕ผͷ Read Lock Λؒ઀తʹ଴ͨͤΔ͜ͱʹͳΓɺར༻ऀ͕ظ଴͍ͯ͠ΔͰ͋Ζ͏ฒྻੑ͕ຬͨ͞Εͳ͍ɻ Write Lock ͢Δଆ͸ timeout ෇͖ͰϩοΫΛ਺ճࢼΈ͔ͯΒ timeout ͳ͠ͰϩοΫཁٻ͢ΔΑ͏ʹ͢ΔͳͲͷ workaround ͕ඞཁɻ) 24 ଟ͘ͷ RDBMS ͷ࣮૷͸ޙड़ͷ Versioning + ͜Ε
25. Optimistic Lock (CAS loop) Lock ͷѥछ, ͱΓ͋͑ͣखݩͰॲཧΛਐΊͯ͠·ͬͯɺ࠷ޙʹ੔߹ੑΛ୲อ: 1. ॲཧ։࢝࣌఺Ͱͷର৅σʔλΛऔಘ 2. ॲཧΛਐΊΔɺͨͩ͠ॻ͖ࠐΉ༧ఆͷσʔλ͸खݩʹஷΊ͓ͯ͘ 3. ͦͷޙϩοΫΛऔͬͯɺόʔδϣϯ൪߸Λ্͛ͭͭ΋σʔλΛॻ͖ࠐΉ • ͨͩ͠ɺ1 Ҏ߱ʹผεϨου͔Βߋ৽͞Ε͍ͯͨͳΒɺ1 ͔Β΍Γ௚͠ • ࣗ෼ͷܭࢉ݁Ռ͕ӡྑ͘࠷৽Ͱ͋ͬͨͳΒॻ͖ࠐΉ • ͜ͷॲཧΛ 1 ໋ྩͰߴ଎ɾ҆શʹߦ͑Δ CAS (Compare and Swap) ໋ྩ͕Α͘࢖ΘΕΔ ֤छ Lock ͷ᠘ͦͷ΋ͷ΁ͷࠜຊରॲʹ͸ͳΒͳ͍͕ɺϩοΫظؒΛڱΊΔ͜ͱ͕Ͱ͖Δ ͦΕʹΑ֤ͬͯछ Lock ͷ᠘(ੑೳ, fairness, ༏ઌॱҐٯస)͕؇࿨͞ΕΔ ͨͩ͠ɺϦτϥΠ͕܁Γฦ͠ൃੜ͠ॲཧ͕௕Ҿ͘͜ͱ΋͋ΔͨΊɺඇৗʹunfair ͳڍಈ͕ӡ࣍ୈͰൃੜ͢ Δ 25
26. Asynchronous Callback / Event Driven Lock ͱٯͷൃ૝ ͕࣌དྷͨ࣌ʹ callback ΛݺΜͰىͯ͜͠΋Β͏ (node.js ͕͜ͷϞσϧ) ྫ͑͹௨৴΍ Disk I/O ͷॲཧ݁ՌΛ callback Ͱड͚औΔΑ͏ʹ͠ɺcallback ͞ΕΔ·Ͱ͸ผͷॲཧΛ࣮ߦ • callback ͷλΠϛϯάͰͷΈεϨου͕੾ΓସΘΔͨΊɺϚϧνεϨουͷෳࡶੑ͕ܰݮ͞ΕΔ • ͦͷ୅ΘΓ callback ͷ୯ҐͰ͔͠ॲཧ͕੾ΓସΘΒͳ͍ͨΊɺCPU ར༻ޮ཰΍ fairness ͸ඍົ • fairness ΍ CPU ͷ༗ޮ׆༻͸ͦΕ΄Ͳؾʹ͠ͳ͍͕ I/O ଴͙ͪ࣌ؒΒ͍͸༗ޮ׆༻͍ͨ͠ɺͱ͍͏χʔζ޲͖ • ϓϩάϥϛϯάͷύϥμΠϜ͕ҟͳΔͨΊॾʑ͕ରԠ͍ͯ͠Δ͜ͱ͕ඞཁ • ίʔυ্͕͔ΒԼ΁ͱॱ൪ʹ૸Βͳ͍, Ϋϩʔδϟ΍ callback ΁ͷཧղ͕લఏ (ಛʹσόοά࣌ʹ׳Ε͕ඞཁ) • ैདྷܕͷσόοΨͩͱͦΕΒͷঢ়ଶΛ௥͏ͷʹखֻ͕͔ؒΔ͜ͱ͕ଟ͠ (ϒϥ΢β JavaScript Ͱݦஶ) • ͦ΋ͦ΋ϥΠϒϥϦɾϛυϧ΢ΤΞ౳͕Ұ؏ͯ͠ callback ϕʔεͷ I/O ͳΓʹରԠ͍ͯ͠Δ͜ͱ͕ඞཁ 26 ϒϥ΢β JS ΍ node.js, winRT ౳ɺҰ؏ͯ͠ callback ϞσϧͰ੔උ͞Ε͍ͯΔ؀ڥ͕͓͢͢Ί
27. Queueing / Pipelining • લஈ͔Β࣍ஈ΁ͱσʔλΛ౉͍ͯ͘͠ • ֤ஈ͸ී௨ʹ࣮૷ͯ͠ queue ܦ༝Ͱܨ͙͚ͩͳͷͰ࣮૷͠΍͘͢όά͕গͳ͍ • ஈʹ෼͚Δ͜ͱͰࣗવͱߏ଄Խɾ෼ׂ౷࣏͞ΕΔޮ༻΋ • queue ΛڬΉ͜ͱͰɺଟগͷ଎౓ͷϜϥ͕͋ͬͯ΋༡ΜͰ͠·͏εϨου͕ग़ͳ͍ • ͱ͸͍֤͑ஈͷϖʔε͕ฏۉతʹ͸Ұக͠ͳ͍ͱɺॲཧ଴͕ͪग़ͯ͠·͏ • queue ʹ଺ࡏ͢Δ͕࣌ؒ͋ΔͨΊɺϨΠςϯγ͕ॏཁͳ web ը໘౳ʹ͸ෆ޲͖ • ݸผσʔλͷॲཧ࣌ؒΑΓεϧʔϓοτ͕ॏཁͳόον༻్ͱ͸ඇৗʹߴ૬ੑ • ؒʹڬΉ queue ͸ϚϧνεϨουରԠͷ΋ͷΛ࢖͏͜ͱ (Ͱͳ͍ͱ Queue ಺෦Ͱෆ੔߹) • Java: java.util.concurrent ҎԼͷίϨΫγϣϯΫϥε • Ruby: (Sized)Queue (require ‘thread’) or ͍ͬͦͷ͜ͱ Redis 27 Map Reduce ͸͜ͷҰछ
28. Messaging Pipeline ߏ੒͕ࣗ༝ʹͳͬͨ൛, ॎԣແਚ Erlang (ϓϩάϥϛϯάݴޠ)΍ Windows ͷ window message ౳͕͜ͷϞσϧ ͳΜͰ΋Ͱ͖Δॊೈੑ͕͋Δ͕ɺ͋·Γࣗ༝ࣗࡏʹ࢖͏ͱ: • ϝοηʔδ͕ࢥΘ͵৔ॴʹूதͯ͠ੑೳ௿Լ… • ܦ࿏͕ෳࡶʹͳΔʹͭΕͯωοτϫʔΫߏ଄ͷอक͕େม… • ςετɾσόοά͕೉͍͠ɺԿ͔͋ͬͨ࣌ͷӨڹ΋ಡΈͮΒ͍… ͱ͍ͬͨ໽հ͞Λ൐͏ ΋࣮͠૷͢Δ৔߹ɺωοτϫʔΫ෼໺ͷ஌ݟ͔Βֶ΂Δͱ͜Ζ͕େͳͷͰࢀߟʹ 28
29. Immutable Object Atomic Reference, Hazard Pointer ڞ༗σʔλΛݟͳͯ͘΋σʔλΛ࡞ΕΔ৔߹(DB ͔Βͷϩʔυ, ܭࢉ݁ՌͷΩϟογϡ౳)ʹ༗༻ • σʔλΛҰ୴࡞ͬͨΒೋ౓ͱॻ͖׵͑ͳ͍ (ॻ͖׵͑ෆೳͳΦϒδΣΫτ, Immutable Object) • ॻ͖׵ΘΒͳ͍͔Βෆ੔߹ͷ৺഑͕શ͘ͳ͍ → ໽հͳෆ੔߹όά͔Βͷղ์ • Immutable Object ΁ͷࢀরΛڞ༗͢ΔΑ͏ʹ͠ɺࢀরઌΛ੾Γସ͑Δ͜ͱͰߋ৽͢Δ • ݹ͍൛ͷ Object Λࢀর͍ͯ͠ΔεϨουΛࢭΊͨΓ͠ͳ͍ → Lock ͷ᠘ʹϋϚΒͳ͍ ࠷৽σʔλ͕ଞͷεϨου͔Βݟ͑ΔΑ͏ʹͯ͠΍Δඞཁ͕͋ΔͷͰ஫ҙ: • Java, C# ͳΒ͹ΦϒδΣΫτ΁ͷࢀরΛ volatile ʹ͢Δ • C++11 ͳΒ͹ memory_order_seq_cst ͔ memory_order_release/acquire ͳ atomic ૢ࡞ Immutable Object Λෳ਺ݟʹߦ͘Α͏ͳઃܭ͸ཁ஫ҙ (Ͳ͏͍͏ॱংͰಡΈʹߦ͔͘ෆఆʹͳΔ) ·ͨɺGC ͷແ͍ݴޠͰ͸ΦϒδΣΫτͷճऩʹ޻෉͕ඞཁ (→ Hazard Pointer Ͱݕࡧ) 29
30. Local Variable, Thread Local Storage ͦΕ͸ຊ౰ʹෳ਺εϨουͰڞ༗͢Δඞཁͷ͋Δσʔλ͔Ͳ͏͔ ྫ͑͹ը໘ͷϦΫΤετ 1 ͭ 1 ͭͷॲཧঢ়ଶΛෳ਺εϨουͰڞ༗͢Δඞཁ͸ͳ͍ͷͰ͸ ෳ਺ͷεϨουͰ෼୲ͯ͠ॲཧΛͨ͠Γಉ࣌ʹࢀর͢ΔσʔλҎ֎͸ɺͦ΋ͦ ΋ෳ਺εϨου͔Βݟ͑Δ৔ॴʹஔ͔ͳ͍ϙϦγʔ͕༗༻ • ؔ਺ͷϩʔΧϧม਺΍ɺϩʔΧϧม਺ͷΈ͔ΒḷΕΔΦϒδΣΫτ • Thread Local Storage : ؔ਺Λލ͍Ͱ஋Λอଘɺͨͩ͠εϨου͝ͱʹผ࿮ • TLS ʹσʔλ͕ஔ͖ͬͺͳ͠ʹͳΔ͜ͱͰϝϞϦফඅ͕ଟ͘ͳΓա͗ͳ ͍͔ɺϦʔΫ͠ͳ͍͔ɺʹ͸ؾΛ͚ͭΑ͏ 30
31. ෆ੔߹ʹରॲ͢ΔͨΊͷΞϓϩʔν ಉ࣌ʹσʔλʹ৮ΕΔεϨουΛݶఆ͢Δܥ (௿ฒྻ౓, ൺֱతສೳ) • Lock / Semaphore • Read-Write Lock • Optimistic Lock (CAS loop) • Asynchronous Callback / Event Driven • Queueing / Pipelining • Messaging • Immutable Object (Atomic Reference, Hazard Pointer) • Local Variable, Thread Local Storage ͦ΋ͦ΋ڝ߹͠ͳ͍͔Βେৎ෉ͩΑܥ (ߴฒྻ౓, ϝϦοτେ) 31
32. Welcome to concurrent processing world ! Next slide: Q & A session memo
33. Q & A memo (1/3) • Java Ͱ Pipelining ͢Δࡍʹɺpipeline ʹೖΕͨΦϒδΣΫτͷϑΟʔϧυʹ͸ volatile Λ෇͚ͳ͍ͱ͍͚ͳ͍ʁ • No. Concurrent ͳίϨΫγϣϯͰ͋Ε͹ɺίϨΫγϣϯʹΦϒδΣΫτΛೖΕ Δ·Ͱૢ࡞ͷ݁Ռ͕ɺίϨΫγϣϯ͔ΒಡΈऔΔଆ͔ΒՄࢹͰ͋Δ͜ͱ͕࢓༷ ͱͯ͠نఆ͞Ε͍ͯΔ • https://docs.oracle.com/javase/jp/7/api/java/util/concurrent/package- summary.html ͷʮϝϞϦʔ੔߹ੑಛੑʯΛࢀর • ͨͩ͠ɺPipeline ʹ৐ͤΔΦϒδΣΫτ͸ Immutable ʹ͢Δͷ͕҆શ • ෳ਺εϨου͔ΒΞΫηε͞ΕΔͨΊ (Ұൠతͳ Pipeline ઃܭͰ͸ಉ࣌ʹΞ Ϋηε͸͞Εͳ͍͕) 33
34. Q & A memo (2/3) • ͜͜Ͱड़΂ΒΕ͍ͯΔख๏͸ϚϧνεϨουʹݶΒͳ͍ͷͰ͸ʁ • Yes, ΄ͱΜͲ͸޿ٛͷʮσʔλΛڞ༗͢Δฒߦॲཧʯશൠʹݴ͑Δϊ΢ϋ΢Ͱ͋Δ • ຊࢿྉʹ͓͚Δ ϚϧνεϨου ͷ࣮ࡍʹҙຯ͢Δͱ͜Ζ͸ σʔλΛڞ༗͢Δฒߦॲཧશൠ • ΠϕϯτϞσϧ(࣮ thread ͸ 1 ຊ)ͷ node.js ͳͲʹݴٴ͍ͯ͠Δͷ΋ͦͷͨΊ • ྫ͑͹ Ruby 2.0 Ͱ͸ OS ଆͷ Copy-on-Write Λҙࣝͨ͠ GC ͷվળ(Bitmap Marking)͕͋ΓɺϚϧν ϓϩηε͔ͩΒͱ͍ͬͯϑοτϓϦϯτ͕େ͖͍Θ͚Ͱ͸ͳ͍ͷͰ͸ • fork લ͔Βͷϓϩηεͷಈ͖ͰݟΔͱ Immutable Object ύλʔϯΛݴޠॲཧܥ͕࣮૷ͯ͘͠Εͯ ͍Δͱ΋ݴ͑ɺσʔλΛڞ༗͢Δฒߦॲཧͱͯ͠ͷ࠷దԽ͕ߦΘΕͨঢ়ଶͰ͋Δ • σʔλΛڞ༗͠ͳ͍ฒߦॲཧ(Ϛϧνϓϩηεͱ͍͏දݱΛͨ͠)ͷඇޮ཰͕͞ղফ͞Εͨঢ়ଶ • ࠓճड़΂ͨഎܠ΍ख๏͸ɺͦ͏͍ͬͨOS ΍ॲཧܥͷ΍͍ͬͯΔ޻෉Λཧղ͢Δࡍͷࢀߟʹ • Compaction Ͱ͖Δ GC ͱ fork & CoW ͷ૬ੑ͕ݪཧతʹѱ͍͜ͱ͸มΘΒͳ͍ 34
35. Q & A memo (3/3) • ϚϧνεϨουʹ͢Δ͔Ͳ͏͔͸ɺ͍ͭͲ͏൑அ͢Δ͔ • ࠷ॳʹ࣮૷͢Δ࣌఺ͰʮͳͥϚϧνεϨου͔?ʯ(Slide 6) Ͱड़΂ͨಈػΛຬͨ͢৔߹ • ·ͨ͸ෛՙࢼݧͳΓ࣮ӡ༻ͰϠό͍ʂͱͳͬͨ৔߹ • ޙ͔ΒϚϧνεϨουԽ͢Δ৔߹ͲͷΑ͏ͳखΛଧ͔ͭ • Immutable Object ύλʔϯʹͰ͖Δ΋ͷ͸͢Δ • Pipeline ύλʔϯʹ͠ɺ֤ஈʹγϯάϧεϨουͳطଘίʔυΛԡ͠ࠐΉ • ίʔυ͕ڧ੍తʹ෼ׂ͞ΕΔ͜ͱʹΑΔϦϑΝΫλϦϯάޮՌ΋ಘΒΕΔ • ඞཁ࠷খݶͰͷϩοΫͷಋೖ (ϩοΫͷ᠘ʹ͸ཁ஫ҙ) • ͦΕ΋μϝͳΒ࡞Γ௚͢ • ࣮ࡍ໰୊ɺϚϧνεϨουʹ͢Δඞཁੑ͕ͳ͍ͳΒɺ͠ͳ͍ͷ͕࠷ળ • ͦ͏͸ݴ͍ͬͯΒΕͳ͍ঢ়گʹͳͬͨͱ͖ʹࠓճͷ࿩͕ࢀߟʹͳΕ͹޾͍ 35