- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在使用一个 worker 双端队列,如“针对弱内存模型的正确和高效的工作窃取”中所述。我希望队列项的大小为 16 个字节,并且我只关心 Intel/AMD Windows x64 和 VS 2019。
我知道 16 字节(比如 __m128)对齐的加载/存储在现代处理器中通常是原子的,但它们不受规范保证。
双端队列的类型是:
typedef struct {
atomic_size_t size;
atomic_int buffer[];
} Array;
typedef struct {
atomic_size_t top, bottom;
Atomic(Array *) array;
} Deque;
重要的是,数组缓冲区项特别具有原子类型。如果我用 VS2019 编译它,我可以看到它使用自旋锁使缓冲区项大小膨胀——我不想要这个。有可能预防吗?特别是因为我只关心带有某些保证的 x64。
deque 上的操作由函数给出:
int take(Deque* q) {
size_t b = load_explicit(&q->bottom, relaxed) - 1;
Array* a = load_explicit(&q->array, relaxed);
store_explicit(&q->bottom, b, relaxed);
thread_fence(seq_cst);
size_t t = load_explicit(&q->top, relaxed);
int x;
if( t <= b ) {
/* Non-empty queue. */
x = load_explicit(&a->buffer[b % a->size], relaxed);
if( t == b ) {
/* Single last element in queue. */
if( !compare_exchange_strong_explicit(&q->top, &t, t + 1, seq_cst, relaxed) )
/* Failed race. */
x = EMPTY;
store_explicit(&q->bottom, b + 1, relaxed);
}
} else { /* Empty queue. */
x = EMPTY;
store_explicit(&q->bottom, b + 1, relaxed);
}
return x;
}
void push(Deque* q, int x) {
size_t b = load_explicit(&q->bottom, relaxed);
size_t t = load_explicit(&q->top, acquire);
Array* a = load_explicit(&q->array, relaxed);
if( b - t > a->size - 1 ) { /* Full queue. */
resize(q);
a = load_explicit(&q->array, relaxed);
}
store_explicit(&a->buffer[b % a->size], x, relaxed);
thread_fence(release);
store_explicit(&q->bottom, b + 1, relaxed);
}
int steal(Deque* q) {
size_t t = load_explicit(&q->top, acquire);
thread_fence(seq_cst);
size_t b = load_explicit(&q->bottom, acquire);
int x = EMPTY;
if( t < b ) {
/* Non-empty queue. */
Array* a = load_explicit(&q->array, consume);
x = load_explicit(&a->buffer[t % a->size], relaxed);
if( !compare_exchange_strong_explicit(&q->top, &t, t + 1, seq_cst, relaxed) )
/* Failed race. */
return ABORT;
}
return x;
}
其中很多都是多余的,应该在 x64 上进行优化。事实上,该论文指定在 thread_fence(seq_cst) 行的 take 函数中只需要一个内存栅栏。虽然我不确定如果队列项类型的大小是 16 个字节,这是否属实?
看起来take()/push() 必须发生在同一个线程中,所以它们之间没有问题。因此,危险在于任何调用 steal() 的线程都会读取部分写入的 16 字节项目。但是由于 push() 仅在写入所有 16 个字节后才执行内存栅栏,并且仅在此之后更新底部,因此在 x64 上似乎这不是问题?
我做了一个实验,我删除了缓冲区项上的原子限定符,并通过 volatile 指针对缓冲区使用简单的赋值。它似乎工作正常,但显然这并不确定!
如果这是不可能的,那么也许使用 cmpxchg16b 是加载/存储 16 字节我的具体情况的更好选择?或者通过将队列项作为索引并无锁地分配索引的 16 字节槽来使这一切复杂化。
所以我的问题的简化版本是:在 x64 上,我可以简单地将 Array 缓冲区类型的定义更改为指向非原子限定 16 字节结构项数组的 volatile 指针,并更改将上述函数中的那些项目加载和存储到简单的非原子赋值表达式?
最佳答案
这可能只是部分答案,因为我试图回答关于 16 字节原子的问题,但我不知道为什么你需要队列的元素是原子的,而不仅仅是计数器。
使用 MSVC 2019 完成此操作同时仍编写可能可移植的代码的最简单方法是:
std::atomic_ref<16 bytes type>
#define _STD_ATOMIC_ALWAYS_USE_CMPXCHG16B
static_assert
在 atomic_ref<...>::is_always_lock_free
确保你有真正的无锁原子或:
boost::atomic<16 bytes type>
或 boost::atomic_ref<16 bytes type>
static_assert
在 is_always_lock_free
确保你有真正的无锁原子MSVC 可能已经为 std::atomic<16 bytes type>
实现了同样的事情,但由于 ABI 兼容性问题,它仍然没有。 (预计在未来的某个版本中实现此功能,将打破当前的 ABI)
这会给你 cmpxchg16b
对于每一个操作,即使是轻松的负载和轻松的存储。这是您可以在任何 CPU 上保证获得的最佳结果。
128 位类型有单指令加载/存储,但它们保证是原子的。参见 SSE instructions: which CPUs can do atomic 16B memory operations?
关于 volatile
在 MSVC 中 volatile
读取和分配由 /volatile:ms
控制//volatile:iso
.参见 /volatile (volatile Keyword Interpretation) .那就是 /volatile:ms
,这是 x86-64 上的默认设置,应该获取负载,应该释放存储。
但是:
因此,如果您仍然希望在 objective-c PU 上依赖 128 位加载/存储作为原子操作,您最好使用内部函数 _mm_load_si128
/_mm_store_si128
, 使用 alignas(16)
以确保正确对齐,并使用 _ReadWriteBarrier以防止编译器重新排序。这可能有效(编译器可能会生成 128 位加载/存储,如所要求的那样,并且这些加载/存储在给定 CPU 上可能确实是原子的)。
关于c++ - 具有非原子大小项目的无锁双端队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69009046/
一、公平锁和非公平锁 1.1、公平锁和非公平锁的概述 公平锁:指多个线程按照申请锁的顺序来获取锁。 非公平锁:指在多线程获取锁的顺序并不是按照申请锁的顺序,有可能后申请的线程比先申请的线程优先获取到锁
阅读目录 1、简介 2、分类 3、全局锁 4、表级锁 5、表锁 6、元数据锁
因此,在我编写的程序中,我有三个函数,为了简单起见,我们将它们称为 A、B 和 C。每个函数都需要访问资源X才能工作。 限制是A和B不允许同时运行并且必须适当同步。但是,C 可以与 A 或 B 同时运
我听说过这些与并发编程相关的词,但是锁、互斥量和信号量之间有什么区别? 最佳答案 锁只允许一个线程进入被锁定的部分,并且该锁不与任何其他进程共享。 互斥锁与锁相同,但它可以是系统范围的(由多个进程共享
这个问题已经有答案了: What is an efficient way to implement a singleton pattern in Java? [closed] (29 个回答) 已关闭
这个问题已经有答案了: What is an efficient way to implement a singleton pattern in Java? [closed] (29 个回答) 已关闭
我对标题中的主题有几个问题。首先,假设我们使用 JDBC,并且有 2 个事务 T1 和 T2。在 T1 中,我们在一个特定的行上执行 select 语句。然后我们对该行执行更新。在事务 T2 中,我们
我希望我的函数只运行一次。这意味着如果多个线程同时调用它,该函数将阻塞所有线程,只允许它运行。 最佳答案 听起来您希望存储过程进行同步。为什么不直接将同步放在应用程序本身中。 pthread_mute
if (runInDemoMode) { lock (this) { //Initalization of tables dCreator.create
我相信无论使用什么语言都可以考虑我的问题,但是为了有一些“ anchor ”,我将使用 Java 语言来描述它。 让我们考虑以下场景:我有一个扩展 Thread 的类 PickyHost 及其实例 p
我知道异步不是并行的,但我现在遇到了一个非常有趣的情况。 async function magic(){ /* some processing here */ await async () =
我们正在使用 Scala、Play 框架和 MongoDB(以 ReactiveMongo 作为我们的驱动程序)构建一个网络应用程序。应用程序架构是端到端的非阻塞。 在我们代码的某些部分,我们需要访问
我需要一个简单的锁,JavaME 超时(concurrent.lock 的反向移植需要完整的 Java 1.3)。 如果其他人已经为 JavaME 发布了经过测试的锁定代码,我宁愿使用它。 锁定是出了
根据 boost : To access the object, a weak_ptr can be converted to a shared_ptr using the shared_ptr co
关于 Mutex 和 Critical 部分之间的区别存在一个问题,但它也不处理 Locks。 所以我想知道临界区是否可以用于进程之间的线程同步。 还有信号状态和非信号状态的含义 最佳答案 在 Win
锁 最为常见的应用就是 高并发的情况下,库存的控制。本次只做简单的单机锁介绍。 直接看代码: 每请求一次库存-1. 假如库存1000,在1000个人请求之后,库存将变为0。
线程和进程 1、线程共享创建它的进程的地址空间,进程有自己的地址空间 2、线程可以访问进程所有的数据,线程可以相互访问 3、线程之间的数据是独立的 4、子进程复制线程的数据 5、子进程启动
**摘要:**细心的你也一定关注到,有的网址是https开头的,有的是http。https开头的网站前面,会有一把小锁。这是为什么呢? 本文分享自华为云社区《还不知道SSL证书已经是刚需了?赶快来了解
试图在 C 中实现一个非常简单的互斥锁(锁)我有点困惑。我知道互斥锁类似于二进制信号量,除了互斥锁还强制执行释放锁的线程的约束,必须是最近获得它的同一线程。我对如何跟踪所有权感到困惑? 这是我到目前为
在阅读了很多与上述主题相关的文章和答案之后,我仍然想知道 SQL Server 数据库引擎在以下示例中是如何工作的: 假设我们有一个名为 t3 的表: create table t3 (a int ,
我是一名优秀的程序员,十分优秀!