ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Lock-free очередь
22 сообщений из 47, страница 2 из 2
  2  все
Lock-free очередь
    #39551439
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
mikronSOFT FOR YOU_head и _tail это не указатели на узлы, это указатели + счётчики
Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA

Я не понимаю проблeмы ABA в контексте конкретной задачи.

По моему понял: у вас при Enqueue освобождается Node,
который ещё в использовании другим потоком.
Next := PNode(Head.Value).Next;
Здесь вы читаете из узла который уже может быть потерян / затёрт / переписан.

Да, в шарпе такое невозможно. А ваши умные указатели со счётчиком проблему освобождения ИМХО не решают.
...
Рейтинг: 0 / 0
11.11.2017, 12:43
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551443
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
mikron,

Если без счётчика, то атомик считается успешным, если указатель на старте и указатель в конце совпадают. Проблема в том, что в промежутке поток исчерпает лимит времени, и пока он ожидает, из вершины кто-то извлечёт указатель, а потом вернёт, но уже совершенно с другим содержимым. С точки зрения логики первый поток должен уйти на следующую итерацию цикла, с точки зрения атомика - он отработает, приведя контейнер в некорректное состояние

В традиционных менеджерах памяти, если ты удалил кусок памяти, потом при выделении ты можешь получить память с тем же указателем. В GC менеджерах такого не происходит. А а традиционных принято хранить не только указатель, но и условно говоря номер версии. И CAS происходит не над указателем, а сразу над парой указатель-счётчик.

И да, при Dequeue мы можем рассматривать Node, который уже удалён, и в котором Next может содержать мусор. На практике там содержится указатель на ранее удалённую память или же nil. НО. Я так и не придумал ситуации, где это может привести к ошибке.
...
Рейтинг: 0 / 0
11.11.2017, 13:26
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551463
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
SOFT FOR YOUmikron,

Если без счётчика, то атомик считается успешным, если указатель на старте и указатель в конце совпадают. Проблема в том, что в промежутке поток исчерпает лимит времени, и пока он ожидает, из вершины кто-то извлечёт указатель, а потом вернёт, но уже совершенно с другим содержимым.

IMHO С counter вы защищаете указатель головы/хвоста а проблема начинается уже тогда, когда вы читаете из освобождённой памяти, т.е. сразу после освобождения памяти. Ваши счётчики что мёртвому припарка - поздно.
Когда вы решите проблему с овобождением используемой/читаемой памяти, то и счётчики вам не понадобятся.

SOFT FOR YOUВ традиционных менеджерах памяти, если ты удалил кусок памяти, потом при выделении ты можешь получить память с тем же указателем. В GC менеджерах такого не происходит. скажем так: с GC это маловероятно, но теоретически возможно.

SOFT FOR YOUИ да, при Dequeue мы можем рассматривать Node, который уже удалён, и в котором Next может содержать мусор. На практике там содержится указатель на ранее удалённую память или же nil. НО. Я так и не придумал ситуации, где это может привести к ошибке.
У вас нет гарантии что между удалением и в первом потоке и чтением Next := PNode(Head.Value).Next; во втором, первый или третий не затребуют память и не перепишут значения. К тому же часто Allocate вернёт тот-же участок при том же размере запрашиваемой памяти.
...
Рейтинг: 0 / 0
11.11.2017, 14:40
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551518
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mikronDima T,

Интересно, кто их тогда пишет, инопланетяне?
Тот кто понимает как их писать. Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое.

Простой заменой мутекса на InterlockedExchange тут тоже не особо ускоришь, т.к. если несколько потоков меняют один и тот же кусок в памяти это уже тормоз из-за синхронизации кэшей ядер проца, надо более сложное решение.

И самое главное очень сложно доказать что твое решение рабочее, т.к. твои тесты могут пройти, а где-то возникнет ситуация когда этот код отработает неправильно.
...
Рейтинг: 0 / 0
11.11.2017, 18:02
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551519
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SOFT FOR YOUmayton,

Нет, а зачем профилировать?
Сейчас же вопрос в корректности, а не в производительности
Тогда зачем ты это все затеял?
...
Рейтинг: 0 / 0
11.11.2017, 18:09
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551520
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
mikron,

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
while True do
begin
  Head := FHead.Copy; 
  // допустим, здесь поток стопорится, и кто-то из другого потока удаляет Head
  Next := PNode(Head.Value).Next;
  if (FHead.AtomicCmpExchange(Next, Head)) then
    Break;
end;



Возможен случай, когда узел уже удалили и в Next лежит мусор
Но тогда FHead будет уже не такой как при чтении, и FHead.AtomicCmpExchange(Next, Head) не сработает, а значит, уйдёт на следующую итерацию
...
Рейтинг: 0 / 0
11.11.2017, 18:22
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551540
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
SOFT FOR YOUmikron,

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
while True do
begin
  Head := FHead.Copy; 
  // допустим, здесь поток стопорится, и кто-то из другого потока удаляет Head
  Next := PNode(Head.Value).Next;
  if (FHead.AtomicCmpExchange(Next, Head)) then
    Break;
end;



Возможен случай, когда узел уже удалили и в 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: смотрит на нод, видит ссылку и успешно!! меняет голову,
т.к. счётчик никогда не менялся и тот же елемент в голове.

Так пойдёт?
...
Рейтинг: 0 / 0
11.11.2017, 19:05
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551549
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima T Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое.

Кто сдаётся без боя, не имеет шансов выиграть.
Wer nicht wagt kann nicht gewinnen.
...
Рейтинг: 0 / 0
11.11.2017, 19:15
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551550
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
SOFT FOR YOU,

Попробуй в TSyncPointer.SetValue увеличивать счётчик.
...
Рейтинг: 0 / 0
11.11.2017, 19:18
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551559
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mikronDima T Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое.

Кто сдаётся без боя, не имеет шансов выиграть.
Wer nicht wagt kann nicht gewinnen.
Умный в гору не пойдет, умный гору обойдет (с)

Надо задачи шире ставить, т.е. не просто создать Lock-free очередь, т.к. сам факт наличия очереди это решение в синхронном стиле, т.е. тут попытка улучшить плохое решение вместо поиска хорошего.
...
Рейтинг: 0 / 0
11.11.2017, 19:59
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551562
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima TУмный в гору не пойдет, умный гору обойдет (с)

Тоже верно, но некоторых тянет в горы.
...
Рейтинг: 0 / 0
11.11.2017, 20:09
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551592
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Dima T,

У всех предел пытливости и развития разный. Если человек не развивается - он умирает
...
Рейтинг: 0 / 0
11.11.2017, 22:16
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551621
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
mikronSOFT FOR YOUmikron,

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
while True do
begin
  Head := FHead.Copy; 
  // допустим, здесь поток стопорится, и кто-то из другого потока удаляет Head
  Next := PNode(Head.Value).Next;
  if (FHead.AtomicCmpExchange(Next, Head)) then
    Break;
end;



Возможен случай, когда узел уже удалили и в 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
...
Рейтинг: 0 / 0
12.11.2017, 00:08
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551658
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SOFT FOR YOUDima T,

У всех предел пытливости и развития разный. Если человек не развивается - он умирает
Главное чтобы пытливость не превращалась в манию велосипедостроения.
Ты по ссылке 20944940 сходил? Там автор не поленился, собрал много материала по lock-free алгоритмам. В т.ч. про очереди .
...
Рейтинг: 0 / 0
12.11.2017, 11:12
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551668
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Dima T,

Да, я подробно изучил его материалы
С его реализации очереди всё и пошло. Но у него Хазард Поинтер, а у меня фри лист
Хазард плох тем, что ты должен контролировать создание и удаление всех потоков
А у меня более универсальный подход, не зависимо от того, где и на каком языке создан поток

Есть стек. Осталось очередь и хеш
...
Рейтинг: 0 / 0
12.11.2017, 12:01
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39551698
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima TГлавное чтобы пытливость не превращалась в манию велосипедостроения.

Да почему такая увереность что ненужно изобретать велосипеды?

 
Вы на чем предпочтёте ездить:




или


...
Рейтинг: 0 / 0
12.11.2017, 13:55
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39553850
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Апаю тему
Вопрос пока не решили :)
...
Рейтинг: 0 / 0
15.11.2017, 19:32
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39562959
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
SOFT FOR YOU,

блоки памяти выделяемые в куче какое выравнивание имеют?
...
Рейтинг: 0 / 0
02.12.2017, 11:56
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39563375
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
mikronSOFT FOR YOU,

PNode(Tail.Value).Next := Node;
Эта операция атомарна?

А в Delphi вообще есть атомарные операции?
А в Delphi вообще есть стандарт?
...
Рейтинг: 0 / 0
03.12.2017, 22:53
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39563949
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
mikron,

Выравнивание 8 байт. Всё четко
...
Рейтинг: 0 / 0
04.12.2017, 17:50
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39563952
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
MasterZiv,

Да, есть атомарные операции
AtomicIncrement, AtomicExchange, AtomicCmpExchange
...
Рейтинг: 0 / 0
04.12.2017, 17:52
| Ответить | Цитировать | Написать  
Lock-free очередь
    #39564114
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SOFT FOR YOUmikron,

Выравнивание 8 байт. Всё четко
При 64 быстрее будет .
...
Рейтинг: 0 / 0
05.12.2017, 07:15
| Ответить | Цитировать | Написать  
22 сообщений из 47, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Lock-free очередь
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]