Share
Embed
Multithreading - why use, why difficult, how to solve -
マルチスレッド プログラミングについて
- 必要となる背景
- なぜ難しいのか
- 難しさを解決するためにどのような手法があるのか
のご紹介です。
主にマルチスレッド プログラミングの全体的な理解を得たいプログラマー向け。
saiya_moebius
January 28, 2015
Transcript
35 slides
-
ϚϧνεϨου • 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 -
εϨου • ϓϩάϥϜΛىಈ͢Δͱ࡞ΒΕΔͷ͕ϓϩηε • Windows Task Manager Ͱݟ͑Δ͋Ε • ϓϩηεϝϞϦྖҬΛ࣋ͭ
• ϓϩάϥϜͷ࣮ߦঢ়ଶ͕εϨου • ࠓ͜ͷίʔυΛ࣮ߦͯ͠·͢Αɺͱ͍͏ঢ়ଶΛ࣋ͭ http://www.atmarkit.co.jp/ait/articles/0503/12/news025.html • ϚϧνεϨου: ϓϩηεʹεϨουΛෳ࡞Δ • 1 ͭͷϝϞϦ(σʔλ)Λڞ༗͠ͳ͕ΒίʔυΛෳฒྻ࣮ߦ • Ϛϧνϓϩηε: ϓϩηεΛෳ࡞Δ (εϨου 1 ͭͮͭ) • ϝϞϦΛڞ༗͠ͳ͍ͰίʔυΛෳฒྻ࣮ߦ 5 -
ͳͥϚϧνεϨου͔? • ϚϧνίΞ CPU ͷར༻ • ୯ҰίΞੑೳͷਐาͷಷԽ (ϑϦʔϥϯνͷऴᖼ) • I/O
ͪ࣌ؒͷ༗ޮ׆༻ • Disk : Resource file, log file • Over Network : HTTP API call, DB query • ͨͤΔ͖Ͱͳ͍ॲཧΛͨͤͳ͍ • ཪଆͰ࣌ؒͷֻ͔ΔॲཧΛ͠ɺදଆࢭΊͳ͍ ίΞ : εϨουΛ࣮ߦ͢ΔͨΊͷϋʔυ, ݱత CPU ʹෳ͋Δ 1 ͭͷ I/O ͪͷؒʹ CPU ສʙඦສճҎ্ͷ໋ྩΛॲཧͰ͖Δ 6 -
ͳͥϚϧνϓϩηεͰͳ͍ʁ ϝϞϦ͕ڞ༗͞Εͳ͍͜ͱʹΑΔແବ͕͍ͬͺ͍: • ϓϩάϥϜࣗମΛෳϩʔυ • OS ଆͷ(CoW )͋Δ͕ɺಛʹ GC ͷ͋Δݴޠͱ૬ੑѱ
• σʔλίϐʔͷΦʔόʔϔου • CPU ଆͷ࣋ͭΩϟογϡͷώοτͷԼ • ϛυϧΤΞɾΞϓϦଆͰͷϝϞԽ࣮ͱ૬ • ΞϓϦଆ͕Βͳͯ͘ϛυϧΤΞଆͰ৭ʑ͍ͬͯΔ͜ͱ͕ଟ͍ ϓϩάϥϜͦΕࣗମ͕ඦ MB ఔߦ͘͜ͱβϥ ϝϞԽ : ͍·ΘͤΔσʔλɾܭࢉ݁ՌΛอଘ͍͠ճ͢࠷దԽख๏ 7 -
࣮ʹదͳᄻ͑ Ϛϧνϓϩηε ֤͕ࣗࣗͷ͓ՈͰݸผʹ࡞ۀ͢Δ ( ࡞ۀॴ͕ਓඞཁɺ࡞ۀաఔ݁ՌΛ૬ޓڞ༗͠ͳ͍ ) ϚϧνεϨου શһ͕ҰՕॴͰڞಉ࡞ۀ͢Δ ( ࡞ۀॴɺ࡞ۀͷதؒɾ࠷ऴ݁ՌશһͰڞ༗
) 8 ݫີʹɾ࣮ࡍͷ্࣮৭ʑͳࣄ͕͋Δ͕ɺ͜ͷࢿྉͰ ʮฒߦॲཧʹͯϝϞϦۭؒΛڞ༗͍ͯ͠Δ൱͔ʯͰ͍͚ -
ϚϧνεϨουʹͯ͠Έͨʂ → രࢮ ϚϧνεϨουݪཧతʹߴੑೳʂ ͨͩ͠ɺͦΕͪΌΜͱಈ͚ͷ… • ԿͰͳ͍ͣͷίʔυͰҟৗऴྃ͢Δ͜ͱ͕͋Δ • ܭࢉ݁Ռ͕߹ͬͯͳ͍͜ͱ͕͋Δ •
ී௨ʹϛυϧͷػೳΛͬͨΒམͪΔ͜ͱ͕͋Δ ͱ͍֤ͬͨछόάΛ৯Β͏͜ͱ͕େมଟ͍ 9 ࡞ۀॴաఔڞ༗͍ͯ͠ΔͷͰɺޓ͍ͷॲཧ͕ѱ͍ҙຯͰ૬ޓ࡞༻ͯ͠͠·͏ -
ϚϧνεϨουͷෳࡶ શεϨου͕ಉ͡λΠϛϯάͰಈ͘ͳΒͱ͔͘… ͳΜ͔ॲཧ 1 ϝϞϦ ෳεϨου͔Β ಡΈॻ͖ εϨου ͳΜ͔ॲཧ 2
ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 4 ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 4 12 -
ϚϧνεϨουͷෳࡶ ࣮ࡍಈ͚Δ࣌ʹಈ͘ͷͰɺॲཧεςοϓͷεϨουͷΈ߹Θ͕ͤ… ϝϞϦ ಡΈॻ͖͕ ೖΓཚΕͯෆ߹ εϨου ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ
2 ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 4 1000 Λ 4 ͢Δ͚ͩͰ 1 ஹ ࣮ࡍͷϓϩμΫτͷෳࡶߋʹେ ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 3 13 -
͞Βʹ࠷దԽ͕ೖΔ͜ͱͰ… ݴޠॲཧܥɾCPU ͷ࠷దԽʮผεϨου͔Βಉ͕͡σʔλΛಡΈॻ͖͞Εͳ͍ʯલఏ ίϯύΠϥɾJIT ͷ࠷దԽྫ • ॲཧͷॱংೖΕସ͑ → ผͷεϨου͔ΒݟΔͱมͳॱংͰσʔλ͕ॻ͖ΘΔ •
ϝϞϦͷಡΈॻ͖Λ 1 ճʹ·ͱΊΔ → มΛԿճಡΜͰݹ͍͕औΕͯ͠·͏ CPU ͷ࠷దԽྫ • ໋ྩͷॱংೖΕସ͑, ϝϞϦͷಡΈॻ͖Λ·ͱΊΔ, ϝϞϦͷಡΈॻ͖தʹଞͷ໋ྩΛ࣮ ߦ • ϝϞϦͷ༰ΛखݩʹΩϟογϡ (CPU Core ผͷΩϟογϡͦ͏Ͱͳ͍ͷ͋Δ) 14 -
Ͳ͏͢Δ͔ εϨου ͳΜ͔ॲཧ 1 εϨου ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 εϨου
ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 1 ͳΜ͔ॲཧ 2 ͳΜ͔ॲཧ 4 ͳΜ͔ॲཧ 3 ͳΜ͔ॲཧ 3 ϝϞϦ ಡΈॻ͖͕ ೖΓཚΕͯෆ߹ ύϑΥʔϚϯεΛ֬อͭͭ͠σʔλෆ߹Λ͙͠ʂ → ϚϧνεϨου ϓϩάϥϛϯάͷͨΊʹੵΈॏͶΒΕ͖ͯͨݟΛ׆༻ 15 -
ෆ߹ʹରॲ͢ΔͨΊͷΞϓϩʔν ಉ࣌ʹσʔλʹ৮ΕΔεϨουΛݶఆ͢Δܥ (ฒྻ, ൺֱతສೳ) • 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 -
Lock (a.k.a Semaphore) 1. σʔλͷಡΈɾॻ͖։࢝લʹϩοΫΛ֬อ 2. σʔλͷಡΈɾॻ͖ྃޙʹϩοΫΛղ์ ଞεϨου͕ϩοΫΛ֬อ͠Α͏ͱ͢Δͱɺ2 ·Ͱͨ͞ΕΔ •
ෆ߹ͳσʔλॻ͖͑Λ͞Εͯ͠·͏৺͕ͳ͘ͳΔ • ͦͦಉ࣌ʹσʔλΛಡΈॻ͖͍ͯ͠ͳ͍ 18 ॳֶऀ͚ʹհ͞Ε͕͕ͪͩɺ᠘͕ଟ͠ (ޙड़) ͜ͷؒɺଞεϨουϩοΫΛ֬อͰ͖ͳ͍ -
Lock ͷ᠘ 0: ղ์࿙Ε • ͢ͰʹϩοΫ͕ѲΒΕ͍ͯΔͱɺ୭ϩοΫͰ͖ͳ͍ • ϩοΫͷղ์͠Ε͕ҰՕॴͰ͋ΔͱγεςϜશମͷఀࢭʹ, ྫ͑͜ͷΑ͏ͳ: 1.
୯ʹղ์ॲཧΛॻ͖Εͨ 2. ޙ͔Β݅ذॲཧΛͨ͠෦Ͱղ์Ε 3. ྫ֎ൃੜ࣌(ҟৗൃੜ࣌)ʹղ์͢ΔͨΊͷϑΥϩʔॲཧ͕ͳ͔ͬͨ 4. ϑΥϩʔॲཧॻ͍͕ͯ͋ͬͨɺͦͷϑΥϩʔॲཧ్͕தͰҟৗऴྃ͢Δ͜ͱ͕͋ͬͨ 5. εϨουڧ੍ऴྃ࣌ʹղ์͞Εͳ͍༷ͩͬͨ • synchronised (Java), lock (C#), RAII (C++) ͱ͍ͬͨݴޠػೳ͕͑Δہ໘Ͱੋ͕ඇͰ͏͠ • ͨͩ͠OSɾݴޠॲཧܥɾϥΠϒϥϦͷݶքΛ͖ͪΜͱௐͯˍݕূͯ͠͏͜ͱ (ಛʹ্ه 3, 4, 5) • ݴޠػೳ͕͑ͳ͍ہ໘Ͱɺ্هͷΑ͏ͳ͋ΒΏΔέʔεΛఆͯ͠ॻ͘͠ 19 -
Lock ͷ᠘ 1: ੑೳ͕ग़ͳ͍ • ฒߦͰॲཧΛ͢Δͷ͕ϚϧνεϨου • ͕ͩɺLock ΛѲΒΕ͍ͯΔͱɺ1 ͭҎ֎ͷεϨουͨ͞ΕΔ
ฒߦॲཧͷͨΊʹฒߦॲཧ͠ͳ͍ࠜຊతໃ६… ϚϧνεϨουʹ͢Δ͜ͱͰಘ͔ͨͬͨੑೳ্͕ಘΒΕͳ͍ 20 ଞͷεϨουΛ͋·Γͨͤͳ͍ͱ͍͏֬৴͕͋ΔͳΒΞϦ -
Lock ͷ᠘ 2: Dead Lock εϨουͦΕͧΕ͕ Lock Λอ࣋ ࣍ͷϩοΫΛཁٻ ->
͓ޓ͍Λػ -> ͣͬͱػ… Possible Solution: • ϩοΫ֫ಘͷॱংΛܾΊɺؾΛ͚࣮ͭͯ͢Δ • ࣮͕େมɺ(ઌड़ͷෳࡶੑͷͨΊ)όάΓ͍͢͠ςετࠔɺͱےѱ • Ұఆ࣌ؒҎ্ϩοΫऔΕͳ͔ͬͨΒ and/or Dead Lock ݕͨ͠Β rollback • rollback & retry Ͱ͖ΔΑ͏ͳॲཧ༰ͳΒ͋Γ (࣮ͷख͕ؒ૿͑Δ͕) 21 DBMS ͷߦϩοΫͰಉ͕͡ى͜Γ͑Δ͜ͱͰ༗໊ MySQL (InnoDB) ͍खʹ rollback ʹରԠ͢Δ͜ͱΛڧ੍͍ͯ͠Δ -
Lock ͷ᠘ 3: Unfair ը໘ API ͳͲϦΞϧλΠϜͰΘΕΔ༻్Ͱɺॲཧͷਐḿ͕ภΒͳ͍ੑ࣭(fairness)͕ඞཁ Fairness ͕֬อ͞Ε͍ͯͳ͍߹ɺӡ࣍ୈͰಛఆͷεϨου͔Γͨ͞ΕΔ͜ͱ͕͋Δ •
ଟ͘ͷ Lock ࣮ fairness อূ͕ͳ͍ͷͰɺʮҰ෦ͷϦΫΤετʹର͚ͯͩ͠Ϩεϙϯε͕ڧʹѱԽ ͢Δʯͱ͍ͬͨঢ়͕ى͜ΔݪҼʹͳΔ • ݴޠॲཧܥɾϥΠϒϥϦʹΑͬͯΦϓγϣϯͰ fairness ΛอূͰ͖Δ Lock ࣮͋Δ • ͨͩ͠ɺଟ͘ʮઌணॱͰϩοΫ͢Δ͜ͱΛอূ͢Δʯͱ͍͏ҙຯͰͷ fairness อূ • fairness ͷҙຯ͕χʔζͱҰக͍ͯ͠Δ͔ཁҙ • ຊʹඞཁͩͬͨͷϩοΫઐ༗࣌ؒͰͷ fairness Ͱ͋ͬͨɺͱ͍ͬͨ͜ͱ͕ଟ͠ • ͦ͏͍ͬͨ߹ɺޙड़ͷ pipeline ύλʔϯ(+ ༏ઌ͖Ωϡʔ)Λݕ౼͢͠ 22 fair ͳϩοΫ࣮෦తʹ༏ઌ͖Ωϡʔʹͳ͍ͬͯΔͷ͕ଟ͍ -
Lock ͷ᠘ 4: ༏ઌॱҐͷٯస ࢀߟ: ՐͰ͍͍ͬͨԿ͕ى͖ͨͷ͔? - Glenn Reeves http://www.unixuser.org/~euske/doc/risks-ja/mars.html
Possible Solution: • Mars Pathfinder ͷ vxWorks ͷΑ͏ʹ͜ͷʹରॲ͢ΔͨΊͷ Semaphore ֦ு͕͋Εར༻͢Δ • lock ΛѲ͍ͬͯΔ࠷தͷॲཧΛ࣌ؒͰऴΘΒͤΔ (ଟ͘ͷܭࢉػϕετΤϑΥʔτࢤ…) • ͦͦ༏ઌλεΫϩοΫΛѲΒͳ͍Α͏ʹઃܭ͢Δ 23 -
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 + ͜Ε -
Optimistic Lock (CAS loop) Lock ͷѥछ, ͱΓ͋͑ͣखݩͰॲཧΛਐΊͯ͠·ͬͯɺ࠷ޙʹ߹ੑΛ୲อ: 1. ॲཧ։࢝࣌ͰͷରσʔλΛऔಘ 2.
ॲཧΛਐΊΔɺͨͩ͠ॻ͖ࠐΉ༧ఆͷσʔλखݩʹஷΊ͓ͯ͘ 3. ͦͷޙϩοΫΛऔͬͯɺόʔδϣϯ൪߸Λ্͛ͭͭσʔλΛॻ͖ࠐΉ • ͨͩ͠ɺ1 Ҏ߱ʹผεϨου͔Βߋ৽͞Ε͍ͯͨͳΒɺ1 ͔ΒΓ͠ • ࣗͷܭࢉ݁Ռ͕ӡྑ͘࠷৽Ͱ͋ͬͨͳΒॻ͖ࠐΉ • ͜ͷॲཧΛ 1 ໋ྩͰߴɾ҆શʹߦ͑Δ CAS (Compare and Swap) ໋ྩ͕Α͘ΘΕΔ ֤छ Lock ͷ᠘ͦͷͷͷࠜຊରॲʹͳΒͳ͍͕ɺϩοΫظؒΛڱΊΔ͜ͱ͕Ͱ͖Δ ͦΕʹΑ֤ͬͯछ Lock ͷ᠘(ੑೳ, fairness, ༏ઌॱҐٯస)͕؇͞ΕΔ ͨͩ͠ɺϦτϥΠ͕܁Γฦ͠ൃੜ͠ॲཧ͕Ҿ͘͜ͱ͋ΔͨΊɺඇৗʹunfair ͳڍಈ͕ӡ࣍ୈͰൃੜ͢ Δ 25 -
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 ϞσϧͰඋ͞Ε͍ͯΔڥ͕͓͢͢Ί -
Queueing / Pipelining • લஈ͔Β࣍ஈͱσʔλΛ͍ͯ͘͠ • ֤ஈී௨ʹ࣮ͯ͠ queue ܦ༝Ͱܨ͙͚ͩͳͷͰ࣮͘͢͠όά͕গͳ͍ •
ஈʹ͚Δ͜ͱͰࣗવͱߏԽɾׂ౷࣏͞ΕΔޮ༻ • queue ΛڬΉ͜ͱͰɺଟগͷͷϜϥ͕͋ͬͯ༡ΜͰ͠·͏εϨου͕ग़ͳ͍ • ͱ͍֤͑ஈͷϖʔε͕ฏۉతʹҰக͠ͳ͍ͱɺॲཧ͕ͪग़ͯ͠·͏ • queue ʹࡏ͢Δ͕࣌ؒ͋ΔͨΊɺϨΠςϯγ͕ॏཁͳ web ը໘ʹෆ͖ • ݸผσʔλͷॲཧ࣌ؒΑΓεϧʔϓοτ͕ॏཁͳόον༻్ͱඇৗʹߴ૬ੑ • ؒʹڬΉ queue ϚϧνεϨουରԠͷͷΛ͏͜ͱ (Ͱͳ͍ͱ Queue ෦Ͱෆ߹) • Java: java.util.concurrent ҎԼͷίϨΫγϣϯΫϥε • Ruby: (Sized)Queue (require ‘thread’) or ͍ͬͦͷ͜ͱ Redis 27 Map Reduce ͜ͷҰछ -
Messaging Pipeline ߏ͕ࣗ༝ʹͳͬͨ൛, ॎԣແਚ Erlang (ϓϩάϥϛϯάݴޠ) Windows ͷ window message
͕͜ͷϞσϧ ͳΜͰͰ͖Δॊೈੑ͕͋Δ͕ɺ͋·Γࣗ༝ࣗࡏʹ͏ͱ: • ϝοηʔδ͕ࢥΘ͵ॴʹूதͯ͠ੑೳԼ… • ܦ࿏͕ෳࡶʹͳΔʹͭΕͯωοτϫʔΫߏͷอक͕େม… • ςετɾσόοά͕͍͠ɺԿ͔͋ͬͨ࣌ͷӨڹಡΈͮΒ͍… ͱ͍ͬͨհ͞Λ͏ ࣮͢͠Δ߹ɺωοτϫʔΫͷݟ͔ΒֶΔͱ͜Ζ͕େͳͷͰࢀߟʹ 28 -
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 -
Local Variable, Thread Local Storage ͦΕຊʹෳεϨουͰڞ༗͢Δඞཁͷ͋Δσʔλ͔Ͳ͏͔ ྫ͑ը໘ͷϦΫΤετ 1 ͭ 1
ͭͷॲཧঢ়ଶΛෳεϨουͰڞ༗͢Δඞཁͳ͍ͷͰ ෳͷεϨουͰ୲ͯ͠ॲཧΛͨ͠Γಉ࣌ʹࢀর͢ΔσʔλҎ֎ɺͦͦ ෳεϨου͔Βݟ͑Δॴʹஔ͔ͳ͍ϙϦγʔ͕༗༻ • ؔͷϩʔΧϧมɺϩʔΧϧมͷΈ͔ΒḷΕΔΦϒδΣΫτ • Thread Local Storage : ؔΛލ͍ͰΛอଘɺͨͩ͠εϨου͝ͱʹผ • TLS ʹσʔλ͕ஔ͖ͬͺͳ͠ʹͳΔ͜ͱͰϝϞϦফඅ͕ଟ͘ͳΓա͗ͳ ͍͔ɺϦʔΫ͠ͳ͍͔ɺʹؾΛ͚ͭΑ͏ 30 -
ෆ߹ʹରॲ͢ΔͨΊͷΞϓϩʔν ಉ࣌ʹσʔλʹ৮ΕΔεϨουΛݶఆ͢Δܥ (ฒྻ, ൺֱతສೳ) • 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 -
Welcome to concurrent processing world ! Next slide: Q &
A session memo -
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 -
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 -
Q & A memo (3/3) • ϚϧνεϨουʹ͢Δ͔Ͳ͏͔ɺ͍ͭͲ͏அ͢Δ͔ • ࠷ॳʹ࣮͢Δ࣌ͰʮͳͥϚϧνεϨου͔?ʯ(Slide 6)
Ͱड़ͨಈػΛຬͨ͢߹ • ·ͨෛՙࢼݧͳΓ࣮ӡ༻ͰϠό͍ʂͱͳͬͨ߹ • ޙ͔ΒϚϧνεϨουԽ͢Δ߹ͲͷΑ͏ͳखΛଧ͔ͭ • Immutable Object ύλʔϯʹͰ͖Δͷ͢Δ • Pipeline ύλʔϯʹ͠ɺ֤ஈʹγϯάϧεϨουͳطଘίʔυΛԡ͠ࠐΉ • ίʔυ͕ڧ੍తʹׂ͞ΕΔ͜ͱʹΑΔϦϑΝΫλϦϯάޮՌಘΒΕΔ • ඞཁ࠷খݶͰͷϩοΫͷಋೖ (ϩοΫͷ᠘ʹཁҙ) • ͦΕμϝͳΒ࡞Γ͢ • ࣮ࡍɺϚϧνεϨουʹ͢Δඞཁੑ͕ͳ͍ͳΒɺ͠ͳ͍ͷ͕࠷ળ • ͦ͏ݴ͍ͬͯΒΕͳ͍ঢ়گʹͳͬͨͱ͖ʹࠓճͷ͕ࢀߟʹͳΕ͍ 35