普通C库中有TestAndSet(volatile int *lock)函数吗？

Question

...还是我必须自己写？（顺便说一句，我在 C 语言中工作）

我正在编写一个类似于维基百科上的实现：

volatile int lock = 0;

void Critical() {
    while (TestAndSet(&lock) == 1);
    critical section // only one process can be in this section at a time
    lock = 0 // release lock when finished with the critical section
}

但我似乎找不到预建的 TestAndSet(volatile int *lock)。

它们的外观示例包括：

#define LOCKED 1
int TestAndSet(volatile int* lockPtr) {
    int oldValue;
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    return oldValue;
}

理想情况下，我想要可以在 linux 和 windows 上工作的东西。同样，我读到原子指令的执行依赖于硬件。我不确定这会起到什么作用，也不确定如何判断硬件是否支持它，然后运行另一种选择。

谢谢！

其他上下文信息： 我问这个问题的原因是为了开发一组用于访问数据结构的函数（例如 add() fetch() delete() 等......）几个线程正在访问它以进行修改和实时显示某些元素。

互斥：我投票反对互斥体（如果我的理由没有根据，请纠正我）因为关键区域不是整个哈希 table，而是给定函数访问的特定成员。所以使用互斥锁会导致整个数据结构的性能瓶颈。

替代方案：促使我查看 TestAndSet() 的原因是在数据结构中的每个元素上放置一个 "beingAccessed" 标志更有意义。该标志将由想要访问它的函数检查，如果它为假，则设置为真，然后该函数将执行它必须执行的操作，然后释放该元素而不冻结整个结构。

评论@M.M: 由于@chux 和你们都提到的原因，示例实现感觉不对。对于busy wait，我的理解是在低层使用它来开发更高层的同步机制。请参阅我上面的编辑：互斥体。 volatile 不是为了确保原子性，而是为了确保在原子函数检查时每次访问该值时都加载该值，因为多个线程可以随时修改该变量。我 imagine/am 希望的原子性是由作用于相关变量的函数提供的。针对您所写内容的特定问题：您的代码说“注意：不要使用 "volatile"”，但您提供的标准函数原型是易失性的，那么非易失性标志变量是否在原子函数中转换为易失性？谢谢。

Answer 1

在 Linux 上（通常是所有 *nix-es）你可以使用 pthread:

#include <pthread.h>
pthread_mutex_t mutex;
void init_mutex() {
    pthread_mutex_init(&mutex, NULL);
}
void lock_mutex() {
    pthread_mutex_lock(&mutex);
}
void release_mutex() {
    pthread_mutex_unlock(&mutex);
}
void delete_mutex() {
    pthread_mutex_destroy(&mutex);
}

您当然可以获取指向 mutex 的指针并将其转换为 int*，但这是无意义的！这四个功能做：

init_mutex - 在程序启动时调用，甚至可以在 main 之前调用初始化资源（在“void”关键字之前用 __attribute__((constructor)) 标记。
delete_mutex - 调用程序完成，释放资源。
lock_mutex - 将锁定您的锁，不允许其他线程访问此功能（无法在进程之间限制它）。
release_mutex - 调用它让运行时知道临界区已经结束并且准备好接受下一个线程。

这些函数将建立一个等待互斥锁的线程队列。请参阅此示例（六个线程）：

A -> B -> C -> D -> E -> [MUTEX] -> F (critical) -> [MUTEX END]
[F] release_mutex
A -> B -> C -> D -> [MUTEX] -> E (critical) -> [MUTEX END] -> F

我不知道 Windows 上的方法。如果您考虑 Linux 和 Windows 的通用内容，那就不好了。如果你考虑硬件，我不得不说NO！线程由内核管理（有时由 C 库管理）。

Answer 2

这通常通过内联汇编语言或编译器扩展来完成。例如，您可以在 Linux 和 Windows 中使用 GCC Atomic Functions。 Microsoft C 编译器可能有一些等效的东西。

Answer 3

C11 包含新的 atomic library that provides this functionality. See the atomic_flag_test_and_set 功能；只需将 int* 替换为 atomic_flag*

您可能只想使用 C11 threads.h 中提供的 mutex (mtx_*) 函数，而不是滚动您自己的同步。

Answer 4

在 C11 标准中，您的标志看起来像：

#include <stdatomic.h>

// Lock-free atomic flag, initially unset. Note: do not use "volatile"
atomic_flag lock = ATOMIC_FLAG_INIT;

还有一个标准函数：

_Bool atomic_flag_test_and_set(volatile atomic_flag *object);

执行您需要的操作。

请注意，您的示例实现无效，因为该标志可能在 lock_ptr 的读取和写入之间被另一个线程更改。我用 clang 3.7 和 gcc 5.x 进行了测试，他们将 atomic_flag_test_and_set 实现为 XCHG 汇编指令。

此外，您的 Critical 函数实现了 "spin lock"，即它会最大化 CPU 不断尝试更改标志。这只是一个好主意，适用于锁只持有少数 CPU 个周期的情况。有关此主题的进一步阅读，请参阅 this thread。

对于受临界区保护的代码可能进行系统调用的正常使用，最好使用操作系统工具对标志进行非忙碌等待。

C11 线程库包含一个互斥体。 As of 2015，显然没有主要的 compiler/library 组合原生支持 C11 线程，尽管正如该线程的回答，有一个 github 项目在 POSIX 线程上实现 C11 线程。

当然你可以使用历史悠久的技术#if to select a CRITICAL_SECTION in Windows，以及所有其他操作系统中的pthread library mutex。

关于volatile的使用：这对于多线程来说既不必要也不充分

它不够因为它不保证原子性。一个 volatile 对象可能仍然 read/written 同时被多个线程（数据竞争，UB）。您必须使用原子对象，使用 C11 原子或特定于编译器的原子功能。

这不是 必需的 因为，从 C11 开始，语言规范包括防止编译器对原子操作重新排序的内存排序规则。您可以在 C11 标准（或 N1570）中阅读有关各种支持的内存排序模型的更多信息。

volatile sig_atomic_t 在 C99 中被推荐为有点 hack，因为 C99 标准没有任何内存栅栏的概念。然而，向前看，现在实际的原子可用了，volatile hack 应该被扔进垃圾堆。

普通C库中有TestAndSet(volatile int *lock)函数吗？

Is there a TestAndSet(volatile int *lock) function in a common C library?

c

multithreading

atomic

compare-and-swap