快速且无锁的单写入器、多读取器 [英] Fast and Lock Free Single Writer, Multiple Reader

问题描述

我有一个写入器，它必须以相当高的频率递增一个变量，还有一个或多个读取器以较低的频率访问该变量.

I've got a single writer which has to increment a variable at a fairly high frequence and also one or more readers who access this variable on a lower frequency.

写入由外部中断触发.

因为我需要高速写入，所以我不想使用互斥锁或其他昂贵的锁定机制.

Since i need to write with high speed i don't want to use mutexes or other expensive locking mechanisms.

我想出的方法是在写入后复制值.读者现在可以将原件与副本进行比较.如果它们相等，则变量的内容有效.

The approach i came up with was copying the value after writing to it. The reader now can compare the original with the copy. If they are equal, the variable's content is valid.

这里是我在 C++ 中的实现

Here my implementation in C++

template<typename T>
class SafeValue
{
private:
    volatile T _value;
    volatile T _valueCheck;
public:
    void setValue(T newValue)
    {
        _value = newValue;
        _valueCheck = _value;
    }

    T getValue()
    {
        volatile T value;
        volatile T valueCheck;
        do
        {
            valueCheck = _valueCheck;
            value = _value;
        } while(value != valueCheck);

        return value;
    }
}

这背后的想法是在读取时检测数据竞争并在发生时重试.但是，我不知道这是否总是有效.我在网上没有找到关于这种方法的任何信息，因此我的问题是:

The idea behind this is to detect data races while reading and retry if they happen. However, i don't know if this will always work. I haven't found anything about this aproach online, therefore my question:

当一个作者和多个读者一起使用时，我的方法有什么问题吗?

我已经知道高写入频率可能会导致读者饿死.是否还有更多的不良影响需要我警惕?难道这根本就不是线程安全的吗?

I already know that high writing frequencys may cause starvation of the reader. Are there more bad effects i have to be cautious of? Could it even be that this isn't threadsafe at all?

编辑 1:

我的目标系统是 ARM Cortex-A15.

My target system is a ARM Cortex-A15.

T 至少应该能够成为任何原始整数类型.

T should be able to become at least any primitive integral type.

编辑 2:

std::atomic 在读写站点上太慢了.我在我的系统上对其进行了基准测试.与未受保护的原始操作相比，写入速度大约慢 30 倍，读取速度大约慢 50 倍.

std::atomic is too slow on reader and writer site. I benchmarked it on my system. Writes are roughly 30 times slower, reads roughly 50 times compared to unprotected, primitive operations.

推荐答案

您应该先尝试使用 std::atomic，但要确保您的编译器了解并理解您的目标架构.由于您的目标是 Cortex-A15 (ARMv7-A cpu)，请确保使用 -march=armv7-a 甚至 -mcpu=cortex-a15.

You should try using std::atomic first, but make sure that your compiler knows and understands your target architecture. Since you are targeting Cortex-A15 (ARMv7-A cpu), make sure to use -march=armv7-a or even -mcpu=cortex-a15.

第一个应生成 ldrexd 指令，根据 ARM 文档应该是原子的:

The first shall generate ldrexd instruction which should be atomic according to ARM docs:

单拷贝原子性

在 ARMv7 中，单拷贝原子处理器访问是:

In ARMv7, the single-copy atomic processor accesses are:

• 所有字节访问
• 对半字对齐位置的所有半字访问
• 对字对齐位置的所有字访问
• 由 LDREXD 和 STREXD 指令对双字对齐位置引起的内存访问.

• all byte accesses
• all halfword accesses to halfword-aligned locations
• all word accesses to word-aligned locations
• memory accesses caused by LDREXD and STREXD instructions to doubleword-aligned locations.

后者应生成 ldrd 指令，该指令在支持大型物理地址扩展的目标上应该是原子的:

The latter shall generate ldrd instruction which should be atomic on targets supporting Large Physical Address Extension:

在包含大型物理地址扩展的实现中，LDRD 和 STRD 对 64 位对齐位置的访问是 64 位单副本原子，如翻译所见表走动和访问转换表.

In an implementation that includes the Large Physical Address Extension, LDRD and STRD accesses to 64-bit aligned locations are 64-bit single-copy atomic as seen by translation table walks and accesses to translation tables.

--- 注意---

Large Physical Address Extension 添加此要求是为了避免在更改转换表条目时需要采取复杂措施来避免原子性问题，而不要求内存系统中的所有位置都是 64 位单副本原子.

The Large Physical Address Extension adds this requirement to avoid the need to complex measures to avoid atomicity issues when changing translation table entries, without creating a requirement that all locations in the memory system are 64-bit single-copy atomic.

您还可以查看 Linux 内核如何实现那些:

You can also check how Linux kernel implements those:

#ifdef CONFIG_ARM_LPAE
static inline long long atomic64_read(const atomic64_t *v)
{
    long long result;

    __asm__ __volatile__("@ atomic64_read\n"
"   ldrd    %0, %H0, [%1]"
    : "=&r" (result)
    : "r" (&v->counter), "Qo" (v->counter)
    );

    return result;
}
#else
static inline long long atomic64_read(const atomic64_t *v)
{
    long long result;

    __asm__ __volatile__("@ atomic64_read\n"
"   ldrexd  %0, %H0, [%1]"
    : "=&r" (result)
    : "r" (&v->counter), "Qo" (v->counter)
    );

    return result;
}
#endif

这篇关于快速且无锁的单写入器、多读取器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！