powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Lock-free очередь
47 сообщений из 47, показаны все 2 страниц
Lock-free очередь
    #39551289
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Всем привет
Я тут в разделе 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.
  TSyncQueue<T> = class(TSyncObject, ISyncQueue<T>)
  private
    FHead: TSyncPointer;
    FTail: TSyncPointer;

    type
      TNode = TAllocatorNode<Pointer,TNothing,T>;
      PNode = ^TNode;

    function GetEmpty: Boolean; inline;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Clear;

    function Enqueue(const Value: T): Boolean;
    function Dequeue(var Value: T): Boolean;

    property Empty: Boolean read GetEmpty;
  end;

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);
  // что если значение, которые было по FTail - уже не корректное?

  // инициализируем Next предущего узла или сам FHead
  if (Tail.Empty) then
  begin
    FHead.Value := Node; //FHead.Fill(Node);
    // что если Node портит какую-то малину?
    // что если не пересчёт инкремента портит чью-то логику?
  end else
  begin
    PNode(Tail.Value).Next := Node;
  end;
end;

function TSyncQueue<T>.Dequeue(var Value: T): Boolean;
var
  Head, Tail: TSyncPointer;
  Next: Pointer;
begin
  repeat
    Tail := FTail.Copy;
    Head := FHead.Copy;

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

      // что если на момент Head равен Empty, Tail.Empty, а FTail не Empty?
    end else
    begin
      // заменяем FHead на Next, при необходимости заменяем FTail
      // Next пустой если ещё не инициализирован (ждём) или последний (обнуляем FTail)
      Next := PNode(Head.Value).Next;
      // что если Head.Value и в Next лежит мусорный nil???
      if (Next = nil) then
      begin     // что если Head.Value невалидный, но равен Tail.Value?
        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 else
      begin
        // Next содержит валидный указатель на следующий узел - кладём его в FHead
        // что если здесь происходит ABA из-за некорректного счётчика в Head?
        if (FHead.AtomicCmpExchange(Next, Head)) then
          Break;
      end;
    end;
  until (False);

  // результат
  Value := PNode(Head.Value).Value;
  TSyncAllocator<Pointer,TNothing,T>.Dispose(Head.Value);
  Result := True;
end;

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

Код: 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.
  TSyncQueue<T> = class(TSyncObject, ISyncQueue<T>)
  private
    FHead: TSyncPointer;
    FTail: TSyncPointer;

    type
      TNode = TAllocatorNode<Pointer,TNothing,T>;
      PNode = ^TNode;

    function GetEmpty: Boolean; inline;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Clear;

    function Enqueue(const Value: T): Boolean;
    function Dequeue(var Value: T): Boolean;

    property Empty: Boolean read GetEmpty;
  end;

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);
  // что если значение, которые было по FTail - уже не корректное?

  // инициализируем Next предущего узла или сам FHead
  if (Tail.Empty) then
  begin
    FHead.Value := Node; //FHead.Fill(Node);
    // что если Node портит какую-то малину?
    // что если не пересчёт инкремента портит чью-то логику?
  end else
  begin
    PNode(Tail.Value).Next := Node;
  end;
end;

function TSyncQueue<T>.Dequeue(var Value: T): Boolean;
var
  Head, Tail: TSyncPointer;
  Next: Pointer;
begin
  repeat
    Tail := FTail.Copy;
    Head := FHead.Copy;

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

      // что если на момент Head равен Empty, Tail.Empty, а FTail не Empty?
    end else
    begin
      // заменяем FHead на Next, при необходимости заменяем FTail
      // Next пустой если ещё не инициализирован (ждём) или последний (обнуляем FTail)
      Next := PNode(Head.Value).Next;
      // что если Head.Value и в Next лежит мусорный nil???
      if (Next = nil) then
      begin     // что если Head.Value невалидный, но равен Tail.Value?
        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 else
      begin
        // Next содержит валидный указатель на следующий узел - кладём его в FHead
        // что если здесь происходит ABA из-за некорректного счётчика в Head?
        if (FHead.AtomicCmpExchange(Next, Head)) then
          Break;
      end;
    end;
  until (False);

  // результат
  Value := PNode(Head.Value).Value;
  TSyncAllocator<Pointer,TNothing,T>.Dispose(Head.Value);
  Result := True;
end;

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

Опиши ошибку. Что значит - сбой?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551307
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты взялся за очень сложную задачу. Ее либо решают, либо не решают. Помощи просить бесполезно.

Почитай посты этого чела , он достаточно подробно расписывает почему не стоит пытаться писать свое lock-free. Он написал, но также описывает все встреченные им грабли, по которым пришлось пройти.
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551310
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

Интересно, кто их тогда пишет, инопланетяне?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551320
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

PNode(Tail.Value).Next := Node;
Эта операция атомарна?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551327
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikronSOFT FOR YOU,

Опиши ошибку. Что значит - сбой?

Есть тестовое приложение. Там два пишущих потока и два читающих.
Числа (вроде бы 10 млн) последовательно закидываются в очередь и тут же читаются
А потом происходит анализ прочитанного.
Сбой происходит если одно число извлечено несколько раз или наоборот ни разу

Есть второй тест
Там 5 потоков, каждый делает одно и то же: сначала записывает число, потом тут же его извлекает
В этом тесте сбой - когда запись произошла, а прочитать не удалось (очередь считается пустой)


mikronSOFT FOR YOU,

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

Да, Next это обычный указатель
Когда узел кладётся в FTail - его Next равен nil
Когда кладётся ещё один узел - тогда пишется Next предыдущего

Здесь идёт обычное присвоение [volatile] указателя
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551344
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU, я "ответчик" который сходу, нечитал то что ты написал.

Но вброшу несколько поинтов.

1) Dephi-разработка в большинстве случаев ориентирована на Windows-среду исполнения. Я готов принять тот факт что
существуют всякие там Лазарусы но все таки основной сегмент потребления это OS от Microsoft. Поэтому нас наверное
будет интересовать тюнинг этой структуры данных под Windows и ее "родной" API. Если вопрос тюнинга для нас не стоит
то тогда не нужен и lock-free и прочее.

2) Совершенно нет никакого смысла делать "классический связный" список. Нам достаточно массива.
Завёрнутого в "бублик". Ну и два поинтера которые будут указывать на голову и хвост.
Рискну предположить что это оптимально и экономно по месту и когерентно по кешу.

3) До кучи можно добавить эвристику которая будет "растягивать" бублик как только есть потребность.
Растягивать экспоненциально. И эвристику которая будет "уплотнять" бублик если он давно не использовался.
Над правилами можно подумать. Во времени или в циклах.

Вот как-то так.
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551346
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Atomic-функции кроссплатформенные. Под Windows, Mac, Linux, iOS или Android
Есть реализации очереди в ограниченном массиве. Есть определённые плюсы в такой реализации
Но какой смысл переписывать реализацию, если даже в коде выше мы не можем найти ошибку
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551348
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Тесты хорошие. Я не знаком с Делфи и наверняка глупость, но проверь
Tail := FTail.Copy;
Head := FHead.Copy;

Тип у Tail и Head почему не Node?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551351
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikronSOFT FOR YOU,

Тесты хорошие. Я не знаком с Делфи и наверняка глупость, но проверь
Tail := FTail.Copy;
Head := FHead.Copy;

Тип у Tail и Head почему не Node?

Это "tagged pointer"
Т.е. это указатели на Ноды, но есть ещё счётчик
Счётчик нужен для того, чтобы в случае AtomicCmpExchange не возник ABA
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551352
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Код собран с оптимизацией? Если собрать без оптимизации тесты пройдут?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551355
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не проходят
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551356
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUAtomic-функции кроссплатформенные. Под Windows, Mac, Linux, iOS или Android
Есть реализации очереди в ограниченном массиве. Есть определённые плюсы в такой реализации
Но какой смысл переписывать реализацию, если даже в коде выше мы не можем найти ошибку
Сходу вопрос.

Ты профилировал? Где у тебя bottleneck?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551357
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

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

У меня нечто подобное на с#. В паре мест код можно упростить но ошибок я не вижу.
НО я думал TSyncPointer стандартная дейфийская комронента, и на её правильность можно положится. Тепер же выясняется что это твоя поделка, а значит проверять надо с неё.
Причём очень внимательно смотреть на оптимизацию в плоть до генерируемого кода.

Вопрос, я ту не мог бы переписать без использования TSyncPointer ? Что есть у дельфи для volatilr read и InterlockedExchange?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551364
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron,

В Delphi есть ряд Atomic-функций. Они работают над 4 и над 8 байтами.
У меня же используется обёртка над ними с инкрементом счётчика

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

Это не доказывает ничего т.к. Реализация другая и ошибка может не проявится.

Мне кажется ошибка в cmpexchange? Убери пожалуйста в проверку на равенство перед системным вызовом. Это ведь оптимизация, верно? Значит не принципиально. И повтори тест.
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551375
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron,

Повторил
Воспроизводится :)
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551403
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
using System;
using System.Threading;

namespace TestCApp
{
    public class ConcurrentQueue<T>
    {
        class Slot
        {
            public Slot Link;
            public T Data;
        }

        Slot _head;
        Slot _tail;

        public ConcurrentQueue()
        {
            _head = _tail = null;
        }

        public void Enqueue(T data)
        {
            var next = new Slot() { Data = data };
            var curr = Interlocked.Exchange(ref _tail, next);
            if (curr == null)
                _head = curr;
            else
                curr.Link = next;
        }

        public bool Dequeue(ref T data)
        {
            while (true)
            {
                var slot = Volatile.Read(ref _head);
                if (_head == null)
                {
                    if (Volatile.Read(ref _tail) == null)
                        return false;
                }
                else if (slot.Link != null)
                {
                    if (Interlocked.CompareExchange(ref _head, slot.Link, slot) == slot)
                    {
                        data = slot.Data;
                        return true;
                    }
                }
                else if(Interlocked.CompareExchange(ref _tail, null, slot) == slot)
                {
                    Interlocked.CompareExchange(ref _head, null, slot);
                    data = slot.Data;
                    return true;
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            bool cancel = false;
            var queue = new ConcurrentQueue<int>();
            for (var i = 5; --i >= 0;)
            {
                var ii = i;
                var jj = i;
                new Thread(() =>
                {
                    while (!Volatile.Read(ref cancel))
                    {
                        queue.Enqueue(ii);
                        if (!queue.Dequeue(ref jj))
                            throw new InvalidOperationException();
                    }
                });
            }
            Thread.Sleep(20000);
            cancel = true;
            Thread.Sleep(1000);
        }
    }
}
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551408
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
        static void Test2()
        {
            var cancel = false;
            var queue = new ConcurrentQueue<int>();
            var sum = 0L;
            for (var i = 5; --i >= 0;)
            {
                var ii = i;
                var jj = i;
                var ss = 0L;
                new Thread(() =>
                {
                    while (!Volatile.Read(ref cancel))
                    {
                        queue.Enqueue(ii);
                        if (!queue.Dequeue(ref jj))
                            throw new InvalidOperationException();
                        ss += ii;
                        ss -= jj;
                    }
                    Interlocked.Add(ref sum, ss); 
                });
            }
            Thread.Sleep(20000);
            cancel = true;
            Thread.Sleep(1000);
            if (sum != 0)
                throw new InvalidOperationException();
        }
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551410
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
                new Thread(() =>
                {
                    while (!Volatile.Read(ref cancel))
                    {
                        queue.Enqueue(ii);
                        if (!queue.Dequeue(ref jj))
                            throw new InvalidOperationException();
                        if (ii != jj)
                        {
                            ss += ii;
                            ss -= jj;
                        }
                    }
                    Interlocked.Add(ref sum, ss); 
                }).Start();
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551412
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron,

Не совсем
Назови Slot --> Node для большей читабельности :)

_head и _tail это не указатели на узлы, это указатели + счётчики
Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA
С другой стороны, Head.Value := Node на C# уже не сэмулируешь

Ну и самое главное - на данном примере у меня проблема вообще не проявилась (i3). Но проявилась у другого участника (i5)
У меня были траблы на другом тесте, где считаются повторяющиеся элементы и потеряные
И то баг был задетекчен далеко не с первого запуска

Но спасибо за попытку повторить :)
Кто знает, может быть на C# с учётом памяти GC, это действительно очень грамотная реализация очереди
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551413
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.
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.
using System;
using System.Threading;

namespace TestCApp
{
    public class ConcurrentQueue<T>
    {
        class Slot
        {
            public Slot Link;
            public T Data;
        }

        Slot _head;
        Slot _tail;

        public ConcurrentQueue()
        {
            _head = _tail = null;
        }

        public void Enqueue(T data)
        {
            var next = new Slot() { Data = data };
            var curr = Interlocked.Exchange(ref _tail, next);
            if (curr == null)
                _head = next;
            else
                curr.Link = next;
        }

        public bool Dequeue(ref T data)
        {
            while (true)
            {
                var slot = Volatile.Read(ref _head);
                if (_head == null)
                {
                    if (Volatile.Read(ref _tail) == null)
                        return false;
                }
                else if (slot.Link != null)
                {
                    if (Interlocked.CompareExchange(ref _head, slot.Link, slot) == slot)
                    {
                        data = slot.Data;
                        return true;
                    }
                }
                else if(Interlocked.CompareExchange(ref _tail, null, slot) == slot)
                {
                    Interlocked.CompareExchange(ref _head, null, slot);
                    data = slot.Data;
                    return true;
                }
            }
        }
    }

    class Program
    {
        static void Test1()
        {
            var cancel = false;
            var queue = new ConcurrentQueue<int>();
            for (var i = 50; --i >= 0;)
            {
                var ii = i;
                var jj = i;
                new Thread(() =>
                {
                    while (!Volatile.Read(ref cancel))
                    {
                        queue.Enqueue(ii);
                        if (!queue.Dequeue(ref jj))
                            throw new InvalidOperationException();
                    }
                }).Start();
            }
            Thread.Sleep(20000);
            cancel = true;
            Thread.Sleep(1000);
        }

        static void Test2()
        {
            var cancel = false;
            var queue = new ConcurrentQueue<int>();
            var sum = 0L;
            for (var i = 10; --i >= 0;)
            {
                var ii = i;
                var jj = i;
                var ss = 0L;
                new Thread(() =>
                {
                    while (!Volatile.Read(ref cancel))
                    {
                        queue.Enqueue(ii);
                        if (!queue.Dequeue(ref jj))
                            throw new InvalidOperationException();
                        if (ii != jj)
                        {
                            ss += ii;
                            ss -= jj;
                        }
                    }
                    Interlocked.Add(ref sum, ss); 
                }).Start();
            }
            Thread.Sleep(20000);
            cancel = true;
            Thread.Sleep(1000);
            if (sum != 0)
                throw new InvalidOperationException();
        }

        static void Main(string[] args)
        {
            // Test1();
            Test2();
        }
    }
}

...
Рейтинг: 0 / 0
Lock-free очередь
    #39551424
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU_head и _tail это не указатели на узлы, это указатели + счётчики
Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA

Я не понимаю проблeмы ABA в контексте конкретной задачи.
Я понимаю где она возможна в принципе, но где она имеет значение для конкретной реализации?
Почему в С# нету проблемы? Откудого это.

SOFT FOR YOUС другой стороны, Head.Value := Node на C# уже не сэмулируешь

А где это имеет значение?


SOFT FOR YOUНу и самое главное - на данном примере у меня проблема вообще не проявилась (i3). Но проявилась у другого участника (i5)
У меня были траблы на другом тесте, где считаются повторяющиеся элементы и потеряные
И то баг был задетекчен далеко не с первого запуска


Я так понял, что проблема репродуцируема.
С дрогой стороны тот же алгоритм на другом языке не имеет проблемы. (по крайней мере не воспроизводится) Следовательно проблема не в алгоритме а в базовых конструкциях.
Поэтому попробуйте то же самое без ваших указателей. Просто переведите мой код в делфи для теста. Он к тому же несколько отличается от вашего.
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551439
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikronSOFT FOR YOU_head и _tail это не указатели на узлы, это указатели + счётчики
Сделаны счётчики для обхода ABA, но с другой стороны в C# не бывает ABA

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

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

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

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

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

И да, при Dequeue мы можем рассматривать Node, который уже удалён, и в котором Next может содержать мусор. На практике там содержится указатель на ранее удалённую память или же nil. НО. Я так и не придумал ситуации, где это может привести к ошибке.
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551463
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
Lock-free очередь
    #39551518
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikronDima T,

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

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

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

Нет, а зачем профилировать?
Сейчас же вопрос в корректности, а не в производительности
Тогда зачем ты это все затеял?
...
Рейтинг: 0 / 0
Lock-free очередь
    #39551520
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
Lock-free очередь
    #39551540
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
Lock-free очередь
    #39551549
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T Лично я понимаю что есть куча нюансов, поэтому даже не буду пытаться написать, возьму готовое.

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

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

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

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

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

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

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

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

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

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

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




или


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

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

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

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

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

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

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


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