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

На 1 процессорном атомики не будут отваливаться

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

А я тебе говорил, что это сравнение Value на nil. И стоят они там, где нужно проверить Value на nil :)

вижу, что не доходит...

пример
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
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);

  // инициализируем Next предущего узла или сам FHead
  if (Tail.Empty) then
  begin
    sleep(3); 
    FHead.Value := Node;
  end else
  begin
    PNode(Tail.Value).Next := Node;
  end;
end;



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

Так работает, даже лучше . По крайней мере повторить ошибку не смог :)
Тебя здесь смущает наверное не Tail.Empty, а FHead.Value := Node
И ты прав, это место достойно более пристального внимания. Но из-за счётчика в FHead, а не из-за сравнения Tail на nil

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

Так работает, даже лучше . По крайней мере повторить ошибку не смог :)
Тебя здесь смущает наверное не Tail.Empty, а FHead.Value := Node
И ты прав, это место достойно более пристального внимания. Но из-за счётчика в FHead, а не из-за сравнения Tail на nil

В данном коде Tail играет роль не текущего хвоста, и хвоста, который был раньше
Т.е. если раньше хвост был пустой (очередь пустая) - FHead тоже инициализируем только что добавленным узлом

а ты тест нормальный сделай


Код: 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.
program TestUG;

{$APPTYPE CONSOLE}

//{$R *.res}

uses
  Winapi.Windows,
  System.SysUtils,
  System.Classes,
  System.Generics.Collections,
  LockFree in 'LockFree.pas';

type
  // поток, добавл€ющий элементы в очередь
  TEmissionThread = class(TThread)
  protected
    procedure Execute; override;
  end;


var
  i: Integer;
  Threads: TObjectList<TThread>;

  Q: TSyncQueue<Integer>;

procedure TEmissionThread.Execute;
var
  Value: Integer;
begin
  while (not Terminated) do
  begin
    Q.Enqueue(3);
    if not Q.Dequeue(Value) then
      raise Exception.Create('Error Message');
  end;
end;

begin
  try
    Q := TSyncQueue<Integer>.Create();
    try
      Threads:= TObjectList<TThread>.Create;
      try
        // инициализируем потоки
        for i := 1 to 5 do
          Threads.Add(TEmissionThread.Create);

        Writeln;
        Write('Press Enter to quit');
        Readln;
      finally
        Threads.Free;
      end;
    finally
      Q.Free;
    end;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.



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

Не очень понятно, что ты хотел показать этим тестом
Ошибок найдено не было
Ожидание потоков ты не делаешь
Проверок ты не делаешь

Возможно ты хотел указать на случай, когда Dequeue будет простаивать в ожидании инициализации
Но точно такой же "Sleep" может возникнуть во время Dequeue и очередь будет долго расти в Tail
В любом случае никакого отношения это к Empty не имеет
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549812
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUПроверок ты не делаешь
хочешь сказать, что у тебя эксепшн не срабатывает?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549822
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

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

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

Выложи тест полностью и какая версия Delphi
Потому что Dequeue не должен вернуть False

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
    Tail := FTail.Copy;
    Head := FHead.Copy;

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



Если выполнился Enqueue - то FTail не должен быть пустым
Код: pascal
1.
2.
3.
4.
5.
6.
7.
  // новый узел
  Node := TSyncAllocator<Pointer,TNothing,T>.New;
  Node.Value := Value;
  Node.Next := nil;

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

20937473 - он весь и есть, модуль с репа твоего
Delphi Xe 10.2

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

Не, давай для чистоты эксперимента выкладывай все файлы
Заодно народ у себя потестит
Пока возникает ощущение, что ты в модулях как-то не то поправил :)

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

Не, давай для чистоты эксперимента выкладывай все файлы
Заодно народ у себя потестит
Пока возникает ощущение, что ты в модулях как-то не то поправил :)

И да
Опиши модель на примере потоков A и B, как это могло произойти
Ибо запись и чтение (GetEmpty) - сами по себе атомарные операции. Если память выровнена. А она должны быть выровнена

вот Фома неверующий

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

kealon(Ruslan),

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

код не смотрел, но осуждаю. Чем докажешь, что операторы из кода в начале темы

Tail.Next := Node;
и
Next := PNode(Head.Value).Next;

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

kealon(Ruslan),

А мой тест у тебя проходит?

Коллеги, какая Delphi нужна? на 2010 не собирается :(
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549874
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Andy MezentsevКоллеги, какая Delphi нужна? на 2010 не собирается :(
Delphi Xe 10.2 точно собирает

SOFT FOR YOUРебята, потестируйте, пожалуйста, пример выше
У меня Exception не воспроизводится (i3-6100U)
Если воспроизведётся - давайте подумаем, почему

kealon(Ruslan),

А мой тест у тебя проходит?
не прошёл на 4-й раз
Код: plaintext
1.
2.
3.
Элемент 10000000 потерян

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

Очень хорошие вопросы
Давай разбираться

> Tail.Next := Node;

Это стало быть Enqueue
Единственное место, где могут получить доступ к этому узлу из другого потока - Dequeue
Важной особенностью этого узла является то, что Next у этого узла всегда равен nil

В Dequeue же анализируется Next узла
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
      // заменяем FHead на Next, при необходимости заменяем FTail
      // Next пустой если ещё не инициализирован (ждём) или последний (обнуляем FTail)
      Next := PNode(Head.Value).Next;
      if (Next = nil) then
      begin
        if (Head.Value = Tail.Value) then
        begin
          // извлекаем единственный элемент - обнуляем FTail
          // и по возможности обнуляем FHead
          if (FTail.AtomicCmpExchange(nil, Tail)) then
          begin
            FHead.AtomicCmpExchange(nil, Head);
            Break;
          end;
        end else
        begin
          // Next не инициализирован
          // просто ждём
        end;
      end



> Next := PNode(Head.Value).Next

Это уже Dequeue
На данный момент кто-то уже мог удалить элемент из очереди, и в Next будет содержаться мусор, вполне вероятно nil
Однако, если Head уже невалидный, то FHead.AtomicCmpExchange(Next, Head) не пройдёт и цикл уйдёт на следующую итерацию

Может быть возможен сценарий, когда в невалидном Head лежит ложный nil и это приводит к ошибке логики очереди?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549879
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Andy Mezentsev,

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

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

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

Я тестирую минимум на XE3
Может быть на первом заведётсяна XE2 уже не компилится

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

дальше можно не продолжать )

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

не только весь lock-free, но еще и весь BrainMM )
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549908
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
SOFT FOR YOUkealon(Ruslan)пропущено...
на XE2 уже не компилится

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


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