powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Lock-free: Доведём очередь до ума
25 сообщений из 147, страница 4 из 6
Lock-free: Доведём очередь до ума
    #39549924
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Да, BrainMM использует стек
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549931
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUРебята, потестируйте, пожалуйста, пример выше
У меня Exception не воспроизводится (i3-6100U)
Если воспроизведётся - давайте подумаем, почему

kealon(Ruslan),

А мой тест у тебя проходит?повторяется уже на 2-х потоках (так что по идее у тебя должен ловиться)

либо зависает
Код: pascal
1.
2.
3.
4.
5.
6.
7.
function TSyncQueue<T>.Dequeue(var Value: T): Boolean;
var
  Head, Tail: TSyncPointer;
  Next: Pointer;
begin
  repeat
     .... вот из этого цикла выйти не может
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549936
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У кого идея сценария, при котором может возникнуть ошибка
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549941
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

у меня идея не пытаться работать с данными по инвалидным адресам
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549944
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Может стоит по пробовать другие алгоритмы. Интересная статья
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549952
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Адреса валидные
Данные невалидны

Даже если взять стек (псевдокод):
Код: pascal
1.
2.
3.
4.
5.
6.
7.
while (True) do
begin
  Value := Head;
  if (Value = nil) then Exit(nil);
  Next := Value.Next; // <--
  if CAS(Head, Next) then Exit(Value)
end;



Даже в случае стека ты не можешь однозначно судить, внутри Value значение Next валидное, или это мусор
Value корректный только в том случае, если CAS прошёл успешно
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549953
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Там нет очереди
Да и смысл
Ты здесь найди ошибку :). А то будешь всё время подсматривать у других :)
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550027
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUАдреса валидные
Данные невалидны


Адрес перестает быть валидным, как только ты отдал его менеджеру памяти.

Это уже не твой адрес, это его адрес.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550034
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

Там нет очереди
Да и смысл
Ты здесь найди ошибку :). А то будешь всё время подсматривать у других :)
ошибка у тебя уже есть - 20937825
я уже прошёл твой этап - и поискал уже прилично в своём коде, потому и говорю тебе про ошибки в твоём коде, которые ты упорно не признаёшь.

красной тряпкой служат такие вещи:
IntelockedExchange

IsEmpty и похожие на них
Я плохой учитель, я не могу на пальцах объяснить почему так, это наверное что-то должно сдвинуться у обучаемого.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550038
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Существуют разные теории, как работать с памятью, чтобы при обращении по адресу не возник AV. Сейчас сделан общий пул в зависимости от размера. Ранее выделенные объекты больше не возвращаются менеджеру памяти. Фактически есть стек наших объектов и в Next хранится указатель на следующий объект. И да, он может быть равен nil.

Если Head успели удалить, а я считаю Next валидным - то AtomicCmpExchange не пройдёт
Если же Next равен nil - то всё равно значение (сам указатель) не должен быть равен Tail
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550041
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

То что ты приводишь - это предположения
Озвучь сценарий, при котором возможна некорректная работа алгоритма
Это и будет весомым аргументом
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550047
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

То что ты приводишь - это предположения
Озвучь сценарий, при котором возможна некорректная работа алгоритма
Это и будет весомым аргументом

по простому, по красным тряпкам

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
function TSyncQueue<T>.Enqueue(const Value: T): Boolean;
var
  Node: PNode;
  Tail: TSyncPointer;
begin
  // новый узел
  Node := TSyncAllocator<Pointer,TNothing,T>.New;
  Node.Value := Value;
  Node.Next := nil;

  // подмен€ем FTail на узел
  Tail := FTail.AtomicExchange(Node);
  // приехал, твоя очередь разорвана, когда она восстановитcя - вопрос
 




Код: pascal
1.
2.
3.
4.
  // инициализируем Next предущего узла или сам FHead
  if (Tail.Empty) then  // пока это проверяешь состояние может стать другим, т.е. играешь в теорию вероятности. 
 
   



так доступно?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550051
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

> приехал, твоя очередь разорвана, когда она восстановитcя - вопрос

Да, очередь разорвана
Потому что мы имеем не с одним указателем, а сразу с двумя
В рамках lock-free иначе ты не сделаешь, в любом случае будет некое промежуточное состояние, которое будет тормозить либо извлечение, либо добавление

> if (Tail.Empty) then // пока это проверяешь состояние может стать другим, т.е. играешь в теорию вероятности.

Не интересно состояние, которое будет потом
В любом случае очередь разорвана и мы должны восстановить связи
Tail в данном случае это узел, который был до Enqueue
И либо в его Next мы прописываем узел, либо инициализируем FHead
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550052
schi
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
"Среди кустарей с мотором, которыми изобиловал Старгород, он был самым непроворным и наиболее часто попадавшим впросак. Причиной к этому служила его чрезмерно кипучая натура. Это был кипучий лентяй. Он постоянно пенился. В собственной его мастерской, помещавшейся во втором дворе дома № 7 по Перелешинскому переулку, застать его было невозможно. Потухший переносной горн сиротливо стоял посреди каменного сарая, по углам которого были навалены проколотые камеры, рваные протекторы «Треугольник», рыжие замки, такие огромные, что ими можно было запирать города, мятые баки для горючего с надписями «Indian» и «Wanderer», детская рессорная колясочка, навеки заглохшая динамка, гнилые сыромятные ремни, масляная пакля, стертая наждачная бумага, австрийский шт ык и множество рваной, гнутой и давленой дряни.

Заказчики не находили Виктора Михайловича. Виктор Михайлович уже где-то распоряжался. Ему было не до работы. Он не мог видеть спокойно въезжающего в свой или чужой двор ломовика с кладью. Полесов сейчас же выходил во двор и, сложив руки на спине, презрительно наблюдал за действиями возчика. Наконец сердце его не выдерживало.

— Кто же так заезжает? — кричал он, ужасаясь. — Заворачивай! Испуганный возчик заворачивал.

— Куда ж ты заворачиваешь, морда?! — страдал Виктор Михайлович, налетая на лошадь. — Надавали бы тебе в старое время пощечин, тогда бы заворачивал!

Покомандовавши так с полчаса, Полесов собирался было уже возвратиться в мастерскую, где ждал его непочиненный велосипедный насос, но тут спокойная жизнь города обычно вновь нарушалась каким-нибудь недоразумением. То на улице сцеплялись осями телеги, и Виктор Михайлович указывал, как лучше всего и быстрее их расцепить; то меняли телеграфный столб, и Полесов проверял его перпендикулярность к земле собственным, специально вынесенным из мастерской отвесом; то, наконец, устраивалось общее собрание жильцов. Тогда Виктор Михайлович стоял посреди двора и созывал жильцов ударами в железную доску; но на самом собрании ему не удавалось побывать. Проезжал пожарный обоз, и Полесов, взволнованный звуками трубы и испепеляемый огнем беспокойства, бежал за колесницами."

Не могу удержаться.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550076
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
schi,

Забанить бы тебя за офтоп :)
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550095
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

> приехал, твоя очередь разорвана, когда она восстановитcя - вопрос

Да, очередь разорвана
Потому что мы имеем не с одним указателем, а сразу с двумя
В рамках lock-free иначе ты не сделаешь, в любом случае будет некое промежуточное состояние, которое будет тормозить либо извлечение, либо добавление Это не особенность lock-free, это особенность твоего алгоритма. С такой "гарантией" очередь нафиг не нужна - 20937825 . То что ты не знаешь как это сделать, не значит, что это невозможно.
SOFT FOR YOU > if (Tail.Empty) then // пока это проверяешь состояние может стать другим, т.е. играешь в теорию вероятности.

Не интересно состояние, которое будет потом
В любом случае очередь разорвана и мы должны восстановить связи
Tail в данном случае это узел, который был до Enqueue
И либо в его Next мы прописываем узел, либо инициализируем FHeadс lock-free не бывает неважного, просто пока ты не знаешь где неправ.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39550121
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Давай меньше флуда, больше дела
Опиши сценарий, при котором может возникнуть ошибка

К примеру я тебе привожу участки кода, где производится ожидание.
Ожидание - не возвращает False
Код: 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.
  repeat
    Tail := FTail.Copy;
    Head := FHead.Copy;

    if (Head.Empty) then
    begin
      // очередь пустая если Tail пустой - выходим
      // может быть задан Tail, а Head ещё не проинициализирован корректным значением
      if (Tail.Empty) then
        Exit(False);
    end else
    begin
      // заменяем FHead на Next, при необходимости заменяем FTail
      // Next пустой если ещё не инициализирован (ждём) или последний (обнуляем FTail)
      Next := PNode(Head.Value).Next;
      if (Next = nil) then
      begin
        if (Head.Value = Tail.Value) then
        begin
          ...
        end else
        begin
          // Next не инициализирован
          // просто ждём
        end;
      end 



И да. Будь другом, приведи пример очереди без промежуточных ожиданий. К примеру реализация Otl полна ожидающих стейтов
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39551365
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Запусти, пожалуйста, свой тест с таким классом:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
  TQueue = class(TSyncStack<Integer>)
    function Enqueue(const Value: Integer): Boolean;
    function Dequeue(var Value: Integer): Boolean;
  end;

function TQueue.Enqueue(const Value: Integer): Boolean;
begin
  Push(Value);
  Result := True;
end;

function TQueue.Dequeue(var Value: Integer): Boolean;
begin
  Result := Pop(Value);
end;



Хочу убедиться, что проблема не в TSyncPointer
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552445
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мы тут нашли одну ошибку. Когда счётчик FHead не инкрементировался
Сейчас потестируйте, пожалуйста, пример килона
https://bitbucket.org/d-mozulyov/lockfree/src
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552455
asutp2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

читаю я эту ветку и вспоминаю твой менеджер памяти. История повторяется один-в-один
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552516
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asutp2,

За тем лишь исключением, что BrainMM уже юзают, а лок фри ещё нет :)
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552522
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUBrainMM уже юзаютЧто, прям в продакшене? Я бы поостерегся
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552524
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
white_nigger,

Ну на однопоточных то он не сбоит. Почему бы нет
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552525
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUНу на однопоточных то он не сбоит. Почему бы нет
Так на одноточке от него проку нет, даже по твоим замерам.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39552531
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

Есть выравнивания, работа со страницами, executable куча
...
Рейтинг: 0 / 0
25 сообщений из 147, страница 4 из 6
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Lock-free: Доведём очередь до ума
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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