powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Lock-free очередь
25 сообщений из 47, страница 1 из 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
25 сообщений из 47, страница 1 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Lock-free очередь
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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