Простейшие Lock-Free объекты для двух потоков

[goobit]

К стыду своему обнаружил, что перепутал смысл полей Head и Tail в очереди: в примере запись происходит в хвост, а чтение с головы. На самом деле, конечно, должно быть наоборот. Функциональность от этого не страдает, но, возможно, затрудняет понимание.

[svd71]

А чем вам не подходят глобальные переменные? Весь механизм работы с ними реализован уже лет 10 как.

[goobit]

Смысл же в доступе из двух разных потоков. Без lock-free как минимум нужны были бы критические секции. Это же очевидно, или я не понял вопрос?

[goobit]

Еще одна мысль: константу QueueCapacity вполне можно сделать полем класса по аналогии с TList.Capacity, а массив Items сделать динамическим. Тогда при переполнении очереди рабочий поток может создавать новый объект с увеличенным значением QueueCapacity, подстраиваясь под способности рабочего потока плодить элементы и главного потока их считывать.

Это будет работать так как память под динамический массив будет выделяться только в конструкторе очереди, вызываемом только из рабочего потока (за исключением создания первого объекта), и в дальнейшем указатель меняться не будет. Таким образом можно реализовать поведение очереди, схожее с TList.Grow.

[uvelichitel]

Для реализации lock-free передачи состояния нам потребуется три его экземпляра (разных объектов одного класса):

Почему недостаточно двух ReadItem, WriteItem?

[goobit]

Потому, что тогда объекты ReadItem и WriteItem не будут находиться в эксклюзивном пользовании потока-читателя и потока-писателя соответственно, так как InterlockedExchange меняет их оба. Т.е. поток-писатель не сможет «спокойно» инициализировать свой WriteItem — в любой момент поток-читатель мог бы его подменить.

[uvelichitel]

Пусть только писатель делает подмену.

[goobit]

Тогда проблемы возникнут у читателя, так как при чтении в любой момент его объект может забрать писатель

[goobit]

Собственно тут вот какой момент: если бы поток-писатель для передачи состояния всегда создавал новый объект, а поток-читатель после прочтения его удалял, то тогда достаточно было бы вообще одного указателя. Собственно этот случай вырождается в очередь из одного элемента, только с удалением существующего при переполнении.

Тут же важным моментом является тот факт, что при передаче состояния не требуется создавать объекты вообще (и дергать при этом менеджер памяти со своими блокировками). Правда расплата за это тоже есть: потоку-писателю требуется всегда инициализировать все поля объекта состояния, а не только изменившиеся с последнего раза так как после обмена с CurrentItem во WriteItem попадает объект с устаревшими данными.

[goobit]

После этого еще пришла мысль, что очередь тоже можно делать с предварительно созданными объектами или вообще массивом record-ов. Тогда вместо указателей можно использовать дополнительный массив флажков, где 0 будет эквивалентен Nil, а 1 — записанным элементом. При этом писатель может спокойно изменять Items[Tail], а потом сделать InterlockedExchange(Written[Tail], 1). При этом читатель будет делать InterlockedCompareExchange(Written[Head], 0, 1) и, если возвращается 0, то чиатть Items[Head].

[goobit]

Уф, нет, не совсем… Перед тем как писать в Items[Tail] писатель должен убедиться, что очередь не переполнена, а это надо сделать каким-то иным способом…

[goobit]

Хотя вроде бы для этого писатель вместо простого InterlockedExchange достаточно сделать так же InterlockedCompareExchange(Written[Tail], 1, 0). Должно работать, так как читатель может только увеличивать количество свободных элементов, но никак не уменьшать.

Не, тоже не подойдет, так как тогда читатель может прочитать не до конца записанный элемент… Но возможно достаточна обычная проверка «if Written[Tail] = 0 then », в худшем случае мы просто увидим что очередь переполнена.