Lock free queue
- 2. 覈谿 覃謂 Lock-free Lock-free Queue Push( T elem ) Pop( ) ABA 覓語 焔 豸′ 襷豺覃謂 誤 貊襯 覲願 苦殊る... 2
- 3. 覃謂 ppt 螳 襦語 Task Queue襦 蠍 伎 蟲 覲 Lock- free Queue 伎 る９. Lock-free Queue 貊螳 企蟆 讌譟讌 覲願 豕譬朱 焔 豌 企慨襦 蟆給. れ願蠍 れ 谿瑚 覦. 3
- 4. 覃謂 Ndc2014 讀 2 : 覃一磯 襦蠏碁覦 企Μ ? (Lock-free Transactional Memory蟾讌) 覦豬 4
- 5. 覃謂 蠍一 覲伎襴 貊 る螳 朱 譴 覲伎蠍 蟠. 5
- 6. Lock-free Lock-free Mutex 螳 蠍壱 襯 讌 螻 螻旧 一危一 蟆 蠏狩 蟆 詩. Lock-free Compare And Swap 企手 CAS 一一襯 牛 企 讌. 6
- 7. Lock-free CAS 覲蟆 , 螳, 覲蟆 螳 語襦 覦 覲蟆 螳 螻 螳朱 覲蟆 螳朱 螳 覲蟆渚螻 螳螻 るゴる 螳 覲蟆渚讌 一一. 蠏碁Μ螻 企 一一 朱 企讌. 7 lock prefix: れ 覈轟(cmpxchg8b)螳 覦壱朱 襦
- 8. Lock-free Lock-free 蠍磯蓋 蟲 覦覯 CAS一一襯 伎伎 覲蟆暑 炎概朱 覲蟆渚 蟾讌 覦覲牛 蟆. 8
- 9. Lock-free Queue 蠏碁 Lock-free Queue 企至 蟲 蟾. 蠍一 蟲 Queue 2螳讌 覃襯 螻牛. 1. Push( T elem ) : Queue 襯 曙. 2. T Pop( ) : Queue 豌 襯 觜朱. 伎 螳 覃螳 企至 蟲 讌 覲企襦 蟆給. 9
- 10. Push( T elem ) れ 貊襯 覲願鍵 蠏碁殊 牛 Push 覃 覲願給. Queue 焔覃 れ螻 螳 一危郁 覩 碁襯 Head Tail 螳襴り 豐蠍 襯 螳讌. 10 Head Tail Dummy Next
- 11. Push( T elem ) 蠍一 襦 一危磯ゼ Tail 豢螳る癌 1. Tail 螳襴る 覩 碁 Next螳 襦 一危 碁襯 螳襴り . 11 Head Tail Dummy Next New Data Next
- 12. Push( T elem ) 2. 伎 Tail 襦 碁襯 螳襴る襦 企. 覃螳 伎 殊 襷れ 螳. 蠏碁 貊襯 覲手. 12 Head Tail Dummy Next New Data Next
- 13. Push( T elem ) Push 覃 豌 貊. lock-free 螻襴讀 覦 覓語襯 願屋蠍 豢螳 貊襦 誤 覲 Push 覃 觜 貊 螳 覲旧″ 譟給. 一 Push 覃 讌譴 貊襯 危ｴ覲願給. 13
- 14. Push( T elem ) 1. 襦 一危磯ゼ 碁襯 麹. 2. 伎 曙 螳 . 一 Tail 螳襴り 碁(last) 企 碁 れ 碁(next)襯 讌 覲 給. 14 1 2
- 15. Push( T elem ) 3. Tail 覲讌 讌 蟆 . Tail 覲る 伎 曙 next 螳 蠍 覓 伎 . 4. next nullptr覿 磯 磯ジ 蟆 . 一 nullptr 襯 覲願 . 15 3 4
- 16. Push( T elem ) 5. next螳 nullptr 朱 覩 るジ る螳 Tail 螳襴る 碁 next 覲蟆渚讌襷 Tail 讌 覲蟆渚讌 覈詩 蟆曙一. 蟆曙一 ル朱 tail next襦 覲蟆渚 譴. 企蟆 伎 讌 蠏碁殊朱 危ｴ覲願給. 16 5 覲蟆 螳 覲蟆 螳 = m_tail 螳 last 螳朱 m_tail newTail襦 螳煙
- 17. Push( T elem ) m_tail.CompareExchange( last, newTail ) ろ蠍 蠏碁手骸 螳給. Next 襦 碁襯 郁屋讌襷 Tail 螳煙讌 . れ譴 ろ るジ る襦 螳り 螳企. 17 Head Tail Dummy Next New Data Next
- 18. Push( T elem ) るジ る 襦 一危磯ゼ 曙螻 . Queue 曙 螳 覲伎ル . 襾殊 曙 一危 覲企 曙 給. Queue Tail 螳襴る 碁 Next螳 nullptr 蠍 覓語 tail 豺 螳 曙 給. 18 Head Tail Dummy Next New Data Next
- 19. Push( T elem ) 蠍一 2螳讌 給. 1. る螳 Tail 企 蟾讌 蠍磯るΠ. 2. 讌 Tail 蠍企. 19 Head Tail Dummy Next New Data Next
- 20. Push( T elem ) る螳 Tail 蠍郁鍵襯 蠍磯るΠる 伎 るジ 覈 る る 蠍磯るΜ 觚襦 螳 . 危 覦 覈 Push一一 る螳 れ ろ 蠍 蟾讌 覈 ろ蟆 . 企 Convoying企手 . 20 Head Tail Dummy Next New Data Next
- 21. Push( T elem ) 企 觚襦 螻襴讀 伎 伎 Lock-free手 給. Lock-free るジ る 蟯 ろ . 蠏碁 ル朱 Tail 蟾. 覲碁 る 襦貉 レ last螳 Tail 螻 殊蠍 覓語 CAS螳 ろ蟆 覩襦 覓語 . 21 Head Tail Dummy Next New Data Next
- 22. Push( T elem ) れ next 螳 nullptr 襯 危ｴ覲願給. 6. next螳 nullptr 企朱 Tail Queue 襷讌襷 螳襴り 朱襦 Tail 螳襴る 碁 next螳 襦 碁襯 螳襴る襦 覲蟆渚. 22 6
- 23. Push( T elem ) 7. next螳 覲蟆暑る 曙 炎概 蟆. 襷讌襷朱 tail 蟆譯手 襭 給. 23 7
- 24. Pop( ) 伎 Pop 覃 . Pop 覃 襷谿螳讌襦 蠏碁殊 牛 襾殊 覲願給. Queue れ螻 螳給. 24 Head Tail Dummy Next New Data Next
- 25. Pop( ) Pop Push 觜伎 螳. 讌蠍 Queue Head Tail 狩 碁襯 螳襴り 讌 蠍 覓語 觜 讌 給. 磯殊 Head Next螳 螳襴る 碁 螳 覲 覲 ロ 給. 25 Head Tail Dummy Next New Data Next New Data Copy
- 26. Pop( ) 伎 Head螳 Next襯 螳襴る襦 覲蟆渚. 伎 碁 襦 覩 碁螳 給. 蠍一ヾ 覩 碁 . 蠏碁Μ螻 覲願 螳 覦覃 . 26 Head Tail Dummy Next New Dummy Next New Data Copy
- 27. Pop( ) Pop 覃 豌 貊. 1. Head 螳 螳襴り 碁 (first) Tail 螳襴り 碁 (last) Head れ 碁(next)襯 讌 覲 ロ 給. 27 1
- 28. Pop( ) 2. るジ る 伎 Head螳 覲蟆 讌 蟆螻 覲蟆暑 覃 . 3. Head Tail 狩 碁襯 螳襴り 讌 誤. 襷 狩 碁襯 螳襴り 覃 Queue 觜 . 一 Queue螳 觜 豌襴 襯 危ｴ覲願給. 28 2 3
- 29. Pop( ) 4. next螳 nullptr企朱 Queue 襷襦 觜 給. 觜 Queue Pop一 豌襴襯 伎. 貊 nullptr襯 覦 給. 蠏碁磯 next螳 nullptr 蟆曙 Queue螳 企 手. 29 4
- 30. Pop( ) Push 覃 覲伎 . 襦 碁螳 曙 讌襷 Tail 襦 碁襯 螳襴り鍵 るジ る CPU 觝鬭殊給. 伎 伎 給. れる Tail る 企給. 30 Head Tail Dummy Next New Data Next
- 31. Pop( ) 5. Queue螳 觜 讌 る next 一危磯ゼ 讌覲 覲旧 給. 6. Head襯 next襦 企り 蠍一ヾ Head 碁襯 れ 一危磯ゼ 覦覃 . 31 5 6
- 32. ABA 覓語 Push 覃襯 危ｴ覲企伎 Lock-free 螻襴讀 覦 企 覓語 瑚 蠍一 覯 危ｴ覲企襦 蟆給. れ螻 螳 Queue襯 螳 覲願給. 螳 碁 譯殊襯 a, b 蟆 . 32 Head Dummy Next New Data Next Tail a b
- 33. ABA 覓語 る1 Pop覃襯 ろり Head襯 讌り鍵 るジ る襦 CPU 蟠 觝鬭朱り 螳蟆給 蟆曙 る1 襦貉 覲 Head 譯殊 a Next 譯殊 b襯 ロ . 33 Head Dummy Next New Data Next Tail a b
- 34. ABA 覓語 伎 るジ るれ Push Pop ろ. 谿襦 覃覈襴 覦螻 轟 企讌 覓語 覃覈襴螳 る 蟆. れ螻 螳 襦 覃螳 ろ 蟆曙磯ゼ 覺. 34 Head Dummy Next New Data Next Tail a b
- 35. ABA 覓語 Pop() -> Push() -> Pop() 襾殊 Pop() 覃襯 牛 譯殊 a 覃覈襴 伎. 35 Head Dummy Next Tail b
- 36. ABA 覓語 Pop() -> Push() -> Pop() 伎 れ Push螳 ろ 覃覈襴螳 伎 a 譯殊螳 れ り 螳企. 36 Head Dummy Next Tail b New Data Next a
- 37. ABA 覓語 Pop() -> Push() -> Pop() 蠏碁Μ螻 れ Pop ろ覃 豕譬 Queue 螳 . 37 Tail Dummy Next a Head
- 38. ABA 覓語 伎 蠍瑚 蠍 螳 讌 る1 れ ろ り 螳企. る1 螳螻 Queue 覈 れ螻 螳給. a 譯殊 碁 れ朱 b 譯殊 碁螳 郁屋 譯. 讌襷 れ Queue 38 Head Dummy Next New Data Next Tail a b
- 39. ABA 覓語 a 譯殊 碁 れ 覓願 給. 覓語 る1 CAS(Head, a, b)螳 炎概. 蠏碁Μ螻 Head る1 襦貉 Next 覲 ロ b襯 螳襴り . 蟆り b 伎 覃覈襴 . 39 Tail Dummy Next a Head
- 40. ABA 覓語 覃覈襴 朱 誤伎 CAS一一 レ( 螳螻 螳 螳 襷 螳 覲蟆 )螳 覓危 給. 企 覓語襯 ABA 覓語手 . ABA 覓語 覈 CAS new, delete襯 蟆曙 覈 Lock-free 螻襴讀 覦 給. 蠏碁 願姥 企至 狩伎 蟾? 蠍一 2螳讌 覦覯 螳蟆給. 40
- 41. ABA 覓語 豌覯讌 覦覯 覃覈襴螳 螻щ襦 讌 襦 蟆 . 伎 る1 Head襯 襦貉 覲 ロ螻 給. 襷 Head 譯殊 覃覈襴螳 朱一 豺伎危語 伎 蟯襴螻 る るジ る Pop 朱 れ襦 覃覈襴螳 覦讌 讌 給. 蠏碁 GC螳 蟆(C#, Python, etc ) ABA 覓語 覦讌 給. 41
- 42. ABA 覓語 覯讌 覦覯 譯殊襯 ロ 蟆. Tag 轟 Stamp 覿襴 豢螳 觜碁ゼ 伎 襷 CAS 螳 るゴ蟆 れ. 覃覈襴螳 り 企 豢螳 觜瑚 襷る るゴ蠍 覓語 ABA覓語 襯 給. 42
- 43. ABA 覓語 StampIndex 企る ABA 覓語襯 願屋蠍 4byte Stamp 4byte 覃覈襴 Index襯 襦 覓苦 螻 給. 43
- 44. 焔 豸′ 蟲 朱 Lock 覯 Queue 焔レ 觜蟲 覲願給. Lock 覯 Queue れ螻 螳 蟲給. 44
- 45. 焔 豸′ ろ 貊 れ螻 螳給. 10000覯 危蟾讌 Push襷 り 危 襦 Push 轟 Pop 語. LoopCount = 64000000, ThreadCount = 8 45
- 46. 焔 豸′ 焔 豸′ PC . CPU : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz 2.30 GHz ( 2貊 4る ) RAM : 8 GB Visual Studio 2017 64 bit 觜 46
- 47. 焔 豸′ 1 谿 2 谿 3 谿 4 谿 5 谿 6 谿 7 谿 8 谿 9 谿 10 谿 Lock 6473 6204 6361 6001 6340 6182 6610 6139 6376 6062 Lock-Free 5369 5728 5374 5735 5694 5755 5310 5711 5720 5731 0 1000 2000 3000 4000 5000 6000 7000 蟆所骸 螳(milliseconds) 47
- 48. 焔 豸′ るジ PC 豸′ 襭 覲伎蟆給. CPU : Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz 3.60 GHz ( 4貊 8る ) RAM : 16 GB Visual Studio 2017 64 bit 觜 48
- 49. 焔 豸′ 1 谿 2 谿 3 谿 4 谿 5 谿 6 谿 7 谿 8 谿 9 谿 10 谿 Lock 8086 8104 7920 7361 7776 7853 7466 7740 7621 7496 Lock-Free 4599 4676 4665 4555 4547 4547 4617 4344 4512 4431 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 蟆所骸 螳(milliseconds) 49
- 50. 焔 豸′ Lock-Free Queue螳 Lock 覯 Queue 覲企 觜襯 蟆 誤 . 蠏碁磯 願 覲伎襦 蟆給. 狩 貊 32 bit 觜 覯. CPU : Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz 3.60 GHz ( 4貊 8る ) RAM : 16 GB Visual Studio 2017 32 bit 觜 50
- 51. 焔 豸′ 1 谿 2 谿 3 谿 4 谿 5 谿 6 谿 7 谿 8 谿 9 谿 10 谿 Lock 4607 4317 5736 4479 4598 4582 4975 5835 4799 4462 Lock-Free 14068 13103 14546 12394 13079 13408 14483 14495 13958 13128 0 2000 4000 6000 8000 10000 12000 14000 16000 蟆所骸 螳(milliseconds) 51
- 52. 焔 豸′ 64bit 襴 lock-free 焔レ 蠍螳給. 企螳 覓語 讌 襦朱 企慨覃癌 52
- 53. 焔 豸′ _InterlockedOr64_INLINE 企朱 螳 覿覿 螳 谿讌螻 給. std::atomic_load 語 . 讀 れ螻 螳 貊螳 焔レ ′ 襾豪 語 . 53
- 54. 焔 豸′ std::atomic_load 襯 讌 る 焔レ れ螻 螳 . 54 1 谿 2 谿 3 谿 4 谿 5 谿 6 谿 7 谿 8 谿 9 谿 10 谿 Lock-Free 4749 4624 4659 4747 4601 4599 4718 4733 4620 4634 4500 4550 4600 4650 4700 4750 4800 蟆所骸 螳(milliseconds)
- 55. 焔 豸′ 蠏碁磯 32bit 襦蠏碁 8byte 襭 所 れ螻 螳 2覯 蟇語 覃覈襴 蠏狩. 襷 14覯 讌 譴 ろ るジ る螳 企 覲 螳 郁 る 8byte 覦 一危碁 螳 ル. 55
- 56. 焔 豸′ 蠏碁覩襦 std::atomic_load 襯 蟇壱 給. 磯殊 32bit 焔レ 襴蠍 伎 るジ 覦覯 螳企 蟆 螳給. StampIndex襯 16bit Stamp, 16bit 覃覈襴 碁煙る 蟲燕 覦覯 蟆給. 企蟆 蟲燕覃 ABA 覓語螳 覦る 蟠 觜殊蠍 65,536覯 Push Pop 覦伎 . 覃 Stamp襯 讌 螻 朱一 豺伎危磯ゼ 牛 谿語＾螻 る 覃覈襴襯 讌 覈詩蟆 襷 覦覯 蟆給. 56
- 57. 襷豺覃謂 朱 螳 譴觜 伎 蠍郁讌 . 蠏碁襯 誤 覲伎 覿企朱 64bit lock 覯 Queue 焔レ 伎 蟆 豺 豈 譯殊 覯企 伎企 る讌 讌 襷 std::mutex 蟲 谿企 誤 焔レ 谿願 蟲一. 襷 焔レ 譴 螻ろ 襷 蟆 螳給. 57
- 58. 誤 貊襯 覲願 苦殊る... https://github.com/xtozero/LockFreeDataStructure/tree/master/LockFre eDataStructure/Source 58
- 59. 谿瑚襭 UE4 LockFreeList.h LockFreeList.cpp Boost lockfree/queue.hpp https://preshing.com/20130618/atomic-vs-non-atomic-operations/ 59