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

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

как его соорудить? (КА)

Построить имитационную модель, описывающую очередь (включая общую память) + 2-3 читающих потока + 2-3 пишущих потока (с их локальными данными).
Определить возможные состояния потоков между операторами, работающими с очередью (включая общую память) + локальные данные.
Определить общее состояние системы как сумму всего.
Прогнать модель по всем возможным переходам состояний системы.
Наткнуться на ошибки при работе очереди и исправить их.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549504
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Теоретиков много и реализаций много. Для Delphi я видел только одну реализацию (два стека, инверсия) и мне этот вариант не нравится непрогнозируемостью времени исполнения. Есть в Tail накопится 100500 элементов, то при Dequeue бог знает, сколько займёт инверсия.

Не факт, что теорию ты грамотно реализуешь на Delphi. Или в теории нет ошибок. Или в реализации на другом языке. Вон, с точки зрения теории, мой вариант прекрасен. Однако где-то закралась ошибка (и).

Ну или вот реализация MSQueue от автора известной lock-free библиотеки libcds. Однако, его реализация не подходит для менейджед-типов (описал в первом посте почему)

Я тебя спросил (как и всех впрочем), потому что у тебя глаз не замылен. И могут появиться идеи )
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549505
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да, тестовое приложение, где два пишущих потока и два читающих - есть (в репозитории )
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549576
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUреализация MSQueue от автора известной lock-free библиотеки libcds ... не подходит для менейджед-типов (описал в первом посте почему)


Честно говоря, не понял, почему оно не должно работать для указателя на строку.
Кто строку юзает, тот ее и освобождает )
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549580
vavan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUДля Delphi я видел только одну реализациюGpLockFreeQueue, OTL смотрел?
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549626
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
vavanSOFT FOR YOUДля Delphi я видел только одну реализациюGpLockFreeQueue, OTL смотрел?
первое я ему уже подкидывал, когда он ещё супер-пупер-мега-менеджер памяти делал
чем-то не подошло ему
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549639
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

Строка D11
Пока один поток копирует строку, второй поток может её удалить

Код: 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.
procedure _UStrAsg(var Dest: UnicodeString; const Source: UnicodeString);
var
  S, D: Pointer;
  P: PStrRec;
  Len: Integer;
begin
  S := Pointer(Source);
  if S <> nil then
  begin
    if __StringRefCnt(Source) < 0 then   // make copy of string literal
    begin
      Len := __StringLength(Source);
      S := _NewUnicodeString(Len);
      Move(Pointer(Source)^, S^, Len * SizeOf(WideChar));
    end else
    begin
      P := PStrRec(PByte(S) - SizeOf(StrRec));
      AtomicIncrement(P.refCnt);
    end;
  end;
  D := Pointer(Dest);
  Pointer(Dest) := S;
  _UStrClr(D);
end;

function _UStrClr(var S): Pointer;
var
  P: PStrRec;
begin
  if Pointer(S) <> nil then
  begin
    P := Pointer(PByte(S) - SizeOf(StrRec));
    Pointer(S) := nil;
    if P.refCnt > 0 then
    begin
      if AtomicDecrement(P.refCnt) = 0 then
        FreeMem(P);
    end;
  end;
  Result := @S;
end;



Поток A читает валидный указатель-строку
Поток B освобождает валидую строку
Поток А обращается к несуществующей области памяти
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549650
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUAleksandr Sharahov,
Строка D11
Пока один поток копирует строку, второй поток может её удалить
...
Поток A читает валидный указатель-строку
Поток B освобождает валидую строку
Поток А обращается к несуществующей области памяти

1. Я там не вижу строку D11.
2. Зачем они это делают? Почему вместо того, чтобы работать с *указателем* на строку, они работают со строкой? К работе со строкой надо переходить, когда есть полная уверенность в успешном извлечении данных из очереди. В нашем случае это указатель на данные. Его-то можно безопасно извлечь.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549656
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vavanSOFT FOR YOUДля Delphi я видел только одну реализациюGpLockFreeQueue, OTL смотрел?

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

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

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

Ну если ты пишешь шаблоны - то копирование происходит просто Value := Node.Value. А финализация Finalize(Node.Value)
Строку я привёл в качестве примера. Это может быть структура, содержащая строки, интерфейсы и динамические массивы. Или вообще Weak экземпляры классов :)
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549684
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати я избавился от ассемблера, заменил FTail на "tagged pointer"
Сейчас работает стабильнее, но ошибки всё равно детектятся:
Код: plaintext
1.
2.
Элемент 9975462 изъят больше одного раза
Элемент 9975465 потерян
Элемент 9975466 потерян

Код теперь выглядит так:
Код: 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.
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
    FHead.Value := 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);
    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
          // извлекаем единственный элемент - обнуляем 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
        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: Доведём очередь до ума
    #39549687
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Правильные пацаны помещают в очередь указатели на свои структуры данных.

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

Ну если ты пишешь шаблоны - то копирование происходит просто Value := Node.Value. А финализация Finalize(Node.Value)
Строку я привёл в качестве примера. Это может быть структура, содержащая строки, интерфейсы и динамические массивы. Или вообще Weak экземпляры классов :)

Финализировать раздельно надо.
Отдельно элемент очереди.
И отдельно (после разыменования указателя и использования структуры) свою структуру данных.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549704
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,

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

Ну во-первых, претензии не ко мне - а к автору статьи :)
Во-вторых, если мы храним указатель, то где-то его нужно выделять и освобождать. Либо должны будем юзать свой ограниченный буфер памяти в виде lock-free стека, что приведёт к лимитированности очереди и дополнительным атомикам, либо будем обращаться к стандартному менеджеру, который синхронизируется критической секцией, со всеми вытекающими. Тем более, для малых типов данных использовать указатель на память в куче - очень расточительно.

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

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

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

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

Никто ж не против Иван Иваныча или адресов. Меня интересует общий случай, когда можешь поместить адрес, Иван Иваныча или динамический массив - и все они войдут и выдут из очереди во время

ну, тогда это действительно серьезный случай )
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549720
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahovkealon(Ruslan)Aleksandr Sharahov,

как его соорудить? (КА)

Построить имитационную модель, описывающую очередь (включая общую память) + 2-3 читающих потока + 2-3 пишущих потока (с их локальными данными).
Определить возможные состояния потоков между операторами, работающими с очередью (включая общую память) + локальные данные.
Определить общее состояние системы как сумму всего.
Прогнать модель по всем возможным переходам состояний системы.
Наткнуться на ошибки при работе очереди и исправить их.
Добавлю, что на однопроцессрной машине бесполезно этим заниматься.. 1 процессор и N ядер не подходят тоже.
От автора статьи так и не дождались его конфигурации ради чего это затевается.
...
Рейтинг: 0 / 0
Lock-free: Доведём очередь до ума
    #39549723
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
X-CiteДобавлю, что на однопроцессрной машине бесполезно этим заниматься.. 1 процессор и N ядер не подходят тоже.
От автора статьи так и не дождались его конфигурации ради чего это затевается.

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

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


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