线程安全——使二叉搜索树线程安全

Question

我对 C 语言和线程编程还很陌生。

我正在为二叉搜索树创建函数，例如插入、搜索和删除。但是我已经指定让这些函数线程安全。

所以我的问题是如何使这些函数线程安全，我需要做什么？还有关于线程的一般建议吗？

举个例子：我已经开始使用搜索功能，但是您如何确保该线程安全？您是否可以做一些简单的常见事情来使这些线程安全？

int search (node* root, int number)
{
    if(root==NULL)
      return 0;
    else if(number==root->data)
      return 1;
    else if(number<=root->data)
      return search(root->left,number);
    else 
      return search(root->right,number);
}

我正在使用 POSIX。

Answer 1

有几种方法可以使您的程序线程安全，尽管 C 标准中有一个 thread library exists 用于线程同步和简单的互斥机制，但更复杂的功能通常取决于操作系统及其库，赢得API、POSIX等

您应该从一个简单的互斥量开始。在您的特定情况下，考虑所有因素可能是最好的方法。

使用 POSIX，您声明并初始化启动和同步线程的互斥体：

pthread_mutex_t lock;

if (pthread_mutex_init(&lock, NULL) != 0) {
    puts("Unable to create mutex!");
    return EXIT_FAILURE;
}

并将其作为线程参数结构中的指针传递。

在线程中，您使用 pthread_mutex_lock(&lock) 和 pthread_mutex_unlock(&lock) 来保护关键部分，即部分发生数据竞争的代码，不多不少，仅访问或修改共享数据的地方，要格外小心僵局。

我假设您知道如何创建和同步线程，如果您不知道，这里有一个非常详尽的教程（它也涉及互斥锁）：

https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/pthreads.html

互斥是最简单的并发冲突解决机制之一，作为 eugenioperez very accurately pointed out，这可以使用 C 标准功能实现，使用上述 <threads.h> 库使您的程序更具可移植性。

线程安全——使二叉搜索树线程安全

Thread Safety - Making Binary Search Tree thread safe

c

multithreading

posix

thread-safety