Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Всем привет Я тут в разделе Delphi пытался совместными усилиями покопать мою реализацию lock-free очереди. Она сбоит, но не понятно где. Разные эксперименты к результату не привели. Поэтому я решил обратиться к более широкой аудитории. Большинство "ответчиков" не пытались вникнуть в ситуацию и понять суть алгоритма. К примеру, один из форумчан упрекал меня в том, что код содержит AtomicExchange, а не цикл с AtomicCmpExchange. Я же пробовал много разных подходов, но на тестах алгоритм иногда давал сбой Критерий нахождения ошибки простой: нужно описать ситуацию (сценарий) при котором алгоритм сработает не корректно Я всю голову сломал, придумать такой вариант не смог, может быть у вас получится Суть в следующем: 1) Очередь представляет собой односвязный список от Head к Tail 2) Очередь пуста если Tail не указывает ни на что 3) Поток, изменивший Tail, важнее того, что модифицирует Head 4) Список может быть временно разорван (Next = nil, ещё не инициализирован) - в этом случае просто ждём 5) TSyncPointer - это "tagged pointer", т.е. указатель, в котором меняется счётчик при Atomic-операциях Отвечу на любые вопросы. Надеюсь на помощь. На всякий случай - вот репозиторий . Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:26 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Сори, вот код с родной разметкой Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:28 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Опиши ошибку. Что значит - сбой? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:47 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Ты взялся за очень сложную задачу. Ее либо решают, либо не решают. Помощи просить бесполезно. Почитай посты этого чела , он достаточно подробно расписывает почему не стоит пытаться писать свое lock-free. Он написал, но также описывает все встреченные им грабли, по которым пришлось пройти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:55 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima T, Интересно, кто их тогда пишет, инопланетяне? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 20:59 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, PNode(Tail.Value).Next := Node; Эта операция атомарна? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 21:23 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOU, Опиши ошибку. Что значит - сбой? Есть тестовое приложение. Там два пишущих потока и два читающих. Числа (вроде бы 10 млн) последовательно закидываются в очередь и тут же читаются А потом происходит анализ прочитанного. Сбой происходит если одно число извлечено несколько раз или наоборот ни разу Есть второй тест Там 5 потоков, каждый делает одно и то же: сначала записывает число, потом тут же его извлекает В этом тесте сбой - когда запись произошла, а прочитать не удалось (очередь считается пустой) mikronSOFT FOR YOU, PNode(Tail.Value).Next := Node; Эта операция атомарна? Да, Next это обычный указатель Когда узел кладётся в FTail - его Next равен nil Когда кладётся ещё один узел - тогда пишется Next предыдущего Здесь идёт обычное присвоение [volatile] указателя ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 21:59 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, я "ответчик" который сходу, нечитал то что ты написал. Но вброшу несколько поинтов. 1) Dephi-разработка в большинстве случаев ориентирована на Windows-среду исполнения. Я готов принять тот факт что существуют всякие там Лазарусы но все таки основной сегмент потребления это OS от Microsoft. Поэтому нас наверное будет интересовать тюнинг этой структуры данных под Windows и ее "родной" API. Если вопрос тюнинга для нас не стоит то тогда не нужен и lock-free и прочее. 2) Совершенно нет никакого смысла делать "классический связный" список. Нам достаточно массива. Завёрнутого в "бублик". Ну и два поинтера которые будут указывать на голову и хвост. Рискну предположить что это оптимально и экономно по месту и когерентно по кешу. 3) До кучи можно добавить эвристику которая будет "растягивать" бублик как только есть потребность. Растягивать экспоненциально. И эвристику которая будет "уплотнять" бублик если он давно не использовался. Над правилами можно подумать. Во времени или в циклах. Вот как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.11.2017, 23:53 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Atomic-функции кроссплатформенные. Под Windows, Mac, Linux, iOS или Android Есть реализации очереди в ограниченном массиве. Есть определённые плюсы в такой реализации Но какой смысл переписывать реализацию, если даже в коде выше мы не можем найти ошибку ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:06 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Тесты хорошие. Я не знаком с Делфи и наверняка глупость, но проверь Tail := FTail.Copy; Head := FHead.Copy; Тип у Tail и Head почему не Node? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:23 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOU, Тесты хорошие. Я не знаком с Делфи и наверняка глупость, но проверь Tail := FTail.Copy; Head := FHead.Copy; Тип у Tail и Head почему не Node? Это "tagged pointer" Т.е. это указатели на Ноды, но есть ещё счётчик Счётчик нужен для того, чтобы в случае AtomicCmpExchange не возник ABA ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:32 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Код собран с оптимизацией? Если собрать без оптимизации тесты пройдут? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:33 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUAtomic-функции кроссплатформенные. Под Windows, Mac, Linux, iOS или Android Есть реализации очереди в ограниченном массиве. Есть определённые плюсы в такой реализации Но какой смысл переписывать реализацию, если даже в коде выше мы не можем найти ошибку Сходу вопрос. Ты профилировал? Где у тебя bottleneck? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:38 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mayton, Нет, а зачем профилировать? Сейчас же вопрос в корректности, а не в производительности ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 00:43 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, У меня нечто подобное на с#. В паре мест код можно упростить но ошибок я не вижу. НО я думал TSyncPointer стандартная дейфийская комронента, и на её правильность можно положится. Тепер же выясняется что это твоя поделка, а значит проверять надо с неё. Причём очень внимательно смотреть на оптимизацию в плоть до генерируемого кода. Вопрос, я ту не мог бы переписать без использования TSyncPointer ? Что есть у дельфи для volatilr read и InterlockedExchange? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 01:15 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, В Delphi есть ряд Atomic-функций. Они работают над 4 и над 8 байтами. У меня же используется обёртка над ними с инкрементом счётчика Что же касается корректности, в тесте есть режим, когда вместо очереди используется стек Так вот на стеке всё работает отлично, а он тоже реализован на TSyncPointer ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 01:37 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Это не доказывает ничего т.к. Реализация другая и ошибка может не проявится. Мне кажется ошибка в cmpexchange? Убери пожалуйста в проверку на равенство перед системным вызовом. Это ведь оптимизация, верно? Значит не принципиально. И повтори тест. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 02:06 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Повторил Воспроизводится :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 02:55 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Вот примерно то что у тебя написано на Delphi. Работает как задумано. Попробуй перевести это в Delphi без TSyncPointer. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 10:51 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, вот ещё тест. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:27 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:36 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Не совсем Назови Slot --> Node для большей читабельности :) _head и _tail это не указатели на узлы, это указатели + счётчики Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA С другой стороны, Head.Value := Node на C# уже не сэмулируешь Ну и самое главное - на данном примере у меня проблема вообще не проявилась (i3). Но проявилась у другого участника (i5) У меня были траблы на другом тесте, где считаются повторяющиеся элементы и потеряные И то баг был задетекчен далеко не с первого запуска Но спасибо за попытку повторить :) Кто знает, может быть на C# с учётом памяти GC, это действительно очень грамотная реализация очереди ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:39 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Последная рабочая версия. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 11:43 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU_head и _tail это не указатели на узлы, это указатели + счётчики Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA Я не понимаю проблeмы ABA в контексте конкретной задачи. Я понимаю где она возможна в принципе, но где она имеет значение для конкретной реализации? Почему в С# нету проблемы? Откудого это. SOFT FOR YOUС другой стороны, Head.Value := Node на C# уже не сэмулируешь А где это имеет значение? SOFT FOR YOUНу и самое главное - на данном примере у меня проблема вообще не проявилась (i3). Но проявилась у другого участника (i5) У меня были траблы на другом тесте, где считаются повторяющиеся элементы и потеряные И то баг был задетекчен далеко не с первого запуска Я так понял, что проблема репродуцируема. С дрогой стороны тот же алгоритм на другом языке не имеет проблемы. (по крайней мере не воспроизводится) Следовательно проблема не в алгоритме а в базовых конструкциях. Поэтому попробуйте то же самое без ваших указателей. Просто переведите мой код в делфи для теста. Он к тому же несколько отличается от вашего. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 12:13 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOU_head и _tail это не указатели на узлы, это указатели + счётчики Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA Я не понимаю проблeмы ABA в контексте конкретной задачи. По моему понял: у вас при Enqueue освобождается Node, который ещё в использовании другим потоком. Next := PNode(Head.Value).Next; Здесь вы читаете из узла который уже может быть потерян / затёрт / переписан. Да, в шарпе такое невозможно. А ваши умные указатели со счётчиком проблему освобождения ИМХО не решают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 12:43 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Если без счётчика, то атомик считается успешным, если указатель на старте и указатель в конце совпадают. Проблема в том, что в промежутке поток исчерпает лимит времени, и пока он ожидает, из вершины кто-то извлечёт указатель, а потом вернёт, но уже совершенно с другим содержимым. С точки зрения логики первый поток должен уйти на следующую итерацию цикла, с точки зрения атомика - он отработает, приведя контейнер в некорректное состояние В традиционных менеджерах памяти, если ты удалил кусок памяти, потом при выделении ты можешь получить память с тем же указателем. В GC менеджерах такого не происходит. А а традиционных принято хранить не только указатель, но и условно говоря номер версии. И CAS происходит не над указателем, а сразу над парой указатель-счётчик. И да, при Dequeue мы можем рассматривать Node, который уже удалён, и в котором Next может содержать мусор. На практике там содержится указатель на ранее удалённую память или же nil. НО. Я так и не придумал ситуации, где это может привести к ошибке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 13:26 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUmikron, Если без счётчика, то атомик считается успешным, если указатель на старте и указатель в конце совпадают. Проблема в том, что в промежутке поток исчерпает лимит времени, и пока он ожидает, из вершины кто-то извлечёт указатель, а потом вернёт, но уже совершенно с другим содержимым. IMHO С counter вы защищаете указатель головы/хвоста а проблема начинается уже тогда, когда вы читаете из освобождённой памяти, т.е. сразу после освобождения памяти. Ваши счётчики что мёртвому припарка - поздно. Когда вы решите проблему с овобождением используемой/читаемой памяти, то и счётчики вам не понадобятся. SOFT FOR YOUВ традиционных менеджерах памяти, если ты удалил кусок памяти, потом при выделении ты можешь получить память с тем же указателем. В GC менеджерах такого не происходит. скажем так: с GC это маловероятно, но теоретически возможно. SOFT FOR YOUИ да, при Dequeue мы можем рассматривать Node, который уже удалён, и в котором Next может содержать мусор. На практике там содержится указатель на ранее удалённую память или же nil. НО. Я так и не придумал ситуации, где это может привести к ошибке. У вас нет гарантии что между удалением и в первом потоке и чтением Next := PNode(Head.Value).Next; во втором, первый или третий не затребуют память и не перепишут значения. К тому же часто Allocate вернёт тот-же участок при том же размере запрашиваемой памяти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 14:40 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronDima T, Интересно, кто их тогда пишет, инопланетяне? Тот кто понимает как их писать. Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое. Простой заменой мутекса на InterlockedExchange тут тоже не особо ускоришь, т.к. если несколько потоков меняют один и тот же кусок в памяти это уже тормоз из-за синхронизации кэшей ядер проца, надо более сложное решение. И самое главное очень сложно доказать что твое решение рабочее, т.к. твои тесты могут пройти, а где-то возникнет ситуация когда этот код отработает неправильно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 18:02 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUmayton, Нет, а зачем профилировать? Сейчас же вопрос в корректности, а не в производительности Тогда зачем ты это все затеял? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 18:09 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. Возможен случай, когда узел уже удалили и в Next лежит мусор Но тогда FHead будет уже не такой как при чтении, и FHead.AtomicCmpExchange(Next, Head) не сработает, а значит, уйдёт на следующую итерацию ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 18:22 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUmikron, Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. Возможен случай, когда узел уже удалили и в Next лежит мусор Но тогда FHead будет уже не такой как при чтении, и FHead.AtomicCmpExchange(Next, Head) не сработает, а значит, уйдёт на следующую итерацию Да, верно. Но TSyncPointer.SetValue счётчик не меняет. 0:Первоначально: очередь содержит один елемент. 1:T1: Dequeue: Читает голову / хвост 2:T2: Dequeue: Читает голову / хвост 3:T2: Удаляет елемент, изменяет хвост (До обновления головы) 4:T3: Enqueue: обновлает хвост и голову 5:Т2: не обновляет голову освобождает память 6:Т3: Dequeue: Читает голову / хвост, Удаляет елемент, изменяет хвост (До обновления головы) 7:T2: Enqueue: Получает память ту же что он осводил в начале, и ту же что видит Т1. т.к. хвост пустой, обновлает хвост, прописывает голову 8:Т3: не обновляет голову освобождает память. 9:Т3: Enqueue: новый елемент, обновлает хвост и склеивает с предидущим. 10:Т1: смотрит на нод, видит ссылку и успешно!! меняет голову, т.к. счётчик никогда не менялся и тот же елемент в голове. Так пойдёт? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 19:05 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima T Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое. Кто сдаётся без боя, не имеет шансов выиграть. Wer nicht wagt kann nicht gewinnen. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 19:15 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Попробуй в TSyncPointer.SetValue увеличивать счётчик. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 19:18 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronDima T Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое. Кто сдаётся без боя, не имеет шансов выиграть. Wer nicht wagt kann nicht gewinnen. Умный в гору не пойдет, умный гору обойдет (с) Надо задачи шире ставить, т.е. не просто создать Lock-free очередь, т.к. сам факт наличия очереди это решение в синхронном стиле, т.е. тут попытка улучшить плохое решение вместо поиска хорошего. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 19:59 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima TУмный в гору не пойдет, умный гору обойдет (с) Тоже верно, но некоторых тянет в горы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 20:09 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima T, У всех предел пытливости и развития разный. Если человек не развивается - он умирает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.11.2017, 22:16 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOUmikron, Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. Возможен случай, когда узел уже удалили и в Next лежит мусор Но тогда FHead будет уже не такой как при чтении, и FHead.AtomicCmpExchange(Next, Head) не сработает, а значит, уйдёт на следующую итерацию Да, верно. Но TSyncPointer.SetValue счётчик не меняет. 0:Первоначально: очередь содержит один елемент. 1:T1: Dequeue: Читает голову / хвост 2:T2: Dequeue: Читает голову / хвост 3:T2: Удаляет елемент, изменяет хвост (До обновления головы) 4:T3: Enqueue: обновлает хвост и голову 5:Т2: не обновляет голову освобождает память 6:Т3: Dequeue: Читает голову / хвост, Удаляет елемент, изменяет хвост (До обновления головы) 7:T2: Enqueue: Получает память ту же что он осводил в начале, и ту же что видит Т1. т.к. хвост пустой, обновлает хвост, прописывает голову 8:Т3: не обновляет голову освобождает память. 9:Т3: Enqueue: новый елемент, обновлает хвост и склеивает с предидущим. 10:Т1: смотрит на нод, видит ссылку и успешно!! меняет голову, т.к. счётчик никогда не менялся и тот же елемент в голове. Так пойдёт? Великолепный сценарий Благодарю! Заменил инициализацию FHead.Value на FHead.Full() Эта реализация берёт старый счётчик и в новом значении счётчик инкрементируется Правда делаю это обычным чтением и обычной записью, без атомиков Проблема осталась Я думаю, нужно взглянуть на вариант сравнения Next с nil (мусор) и Head.Value/Tail.Value ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2017, 00:08 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUDima T, У всех предел пытливости и развития разный. Если человек не развивается - он умирает Главное чтобы пытливость не превращалась в манию велосипедостроения. Ты по ссылке 20944940 сходил? Там автор не поленился, собрал много материала по lock-free алгоритмам. В т.ч. про очереди . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2017, 11:12 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima T, Да, я подробно изучил его материалы С его реализации очереди всё и пошло. Но у него Хазард Поинтер, а у меня фри лист Хазард плох тем, что ты должен контролировать создание и удаление всех потоков А у меня более универсальный подход, не зависимо от того, где и на каком языке создан поток Есть стек. Осталось очередь и хеш ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2017, 12:01 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Dima TГлавное чтобы пытливость не превращалась в манию велосипедостроения. Да почему такая увереность что ненужно изобретать велосипеды? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.11.2017, 13:55 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
Апаю тему Вопрос пока не решили :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.11.2017, 19:32 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, блоки памяти выделяемые в куче какое выравнивание имеют? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2017, 11:56 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikronSOFT FOR YOU, PNode(Tail.Value).Next := Node; Эта операция атомарна? А в Delphi вообще есть атомарные операции? А в Delphi вообще есть стандарт? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.12.2017, 22:53 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
mikron, Выравнивание 8 байт. Всё четко ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.12.2017, 17:50 |
|
||
|
Lock-free очередь
|
|||
|---|---|---|---|
|
#18+
MasterZiv, Да, есть атомарные операции AtomicIncrement, AtomicExchange, AtomicCmpExchange ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.12.2017, 17:52 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1340221]: |
0ms |
get settings: |
12ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
80ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
72ms |
get tp. blocked users: |
1ms |
| others: | 16ms |
| total: | 218ms |

| 0 / 0 |
