时间戳

首页 > 解决方案 > 无法理解或修复我的程序中的竞争条件

c - 无法理解或修复我的程序中的竞争条件

问题描述

我正在实现我自己的 malloc 版本，它与 glibc malloc 非常相似，因为它通过创建 arenas 来支持多线程，这是一个线程可以在没有与另一个线程竞争的风险的情况下工作的内存区域。

我的数据结构如下：

typedef struct          s_arena {
    pthread_mutex_t     mutex;
    t_pool              *main_pool;
}                       t_arena;

typedef struct          s_arena_data {
    _Atomic int         arena_count;
    t_arena             arenas[M_ARENA_MAX];
}                       t_arena_data;

t_arena_data 是一个全局变量，其中包含已创建的竞技场数量，第一次调用从 0 开始，上限为 M_ARENA_MAX（我目前定义为 8），以及包含我所有竞技场的数组。

一个 arena 只包含一个 mutex，它使用 pthread_mutex_init() 初始化，以及一个指向内存池的指针。内存池对于这个主题并不重要，因为竞争条件在到达它之前就发生了。

我的程序是如何工作的：当每个线程进入 malloc 时，它会尝试 pthread_try_lock 第一个 arena 的互斥锁。如果是这样，一切都很好，它会继续进行我在这里没有描述的分配。如果没有，可能会发生几件事。

如果数组中的下一个条目为空且未达到 M_ARENA_MAX，则将锁定一个新的互斥体以创建新的 arena 并将其添加到数组中。互斥锁是全局的，这意味着没有两个线程可以同时创建一个 arena。

如果该互斥体被锁定，则线程将循环回到 arena[0] 并继续搜索打开的互斥体。

现在，我很确定由于变量 arena_count 会发生竞态条件。多亏了调试 printf 语句，我观察到无论何时函数段错误，都没有达到 M_ARENA_MAX。如果有，程序将不会崩溃。所以我怀疑一个线程可能在另一个线程增加它之前读取 arena_count 的值，当它完成读取它时，增加它的线程释放 new_arena_mutex 并且第一个线程开始创建一个使用一个错误的索引。

这是我的第一个多线程程序，所以如果我的解释或代码不清楚，我深表歉意，但我在过去 4 个小时里一直在解决这个问题，虽然我认为我缩小了问题的范围，但我真的不知道如何解决这个问题。

这是错误的代码部分：

    current_arena = &arena_data.arenas[0];
    int arena_index = 0;
    while (pthread_mutex_trylock(&current_arena->mutex) != 0) {

        printf("THREAD %p READS[0] ARENA COUNT AT %d\n", (void *)pthread_self(), arena_data.arena_count);
        if (arena_index == arena_data.arena_count - 1) {
            printf("THREAD %p READS[1] ARENA COUNT AT %d\n", (void *)pthread_self(), arena_data.arena_count);

            if (pthread_mutex_trylock(&new_arena_mutex) != 0 || arena_data.arena_count == M_ARENA_MAX) {
                current_arena = &arena_data.arenas[(arena_index = 0)];
                continue;
            }

            creator = true;
            break;
        }

        current_arena = &arena_data.arenas[arena_index++];
    }

    /* All arenas are occupied by other threads but M_ARENA_MAX isn't reached. Let's just create a new one. */
    if (creator == true) {

        printf("THREAD %p READS[2] ARENA COUNT AT %d\n", (void *)pthread_self(), arena_data.arena_count);

        current_pool = create_new_pool(MAIN_POOL, chunk_type, size, pagesize, &new_arena_mutex);
        if (current_pool == MAP_FAILED) return NULL;

        ++arena_data.arena_count;
        arena_data.arenas[arena_index + 1] = (t_arena){ .main_pool = current_pool };
        pthread_mutex_init(&arena_data.arenas[arena_index + 1].mutex, NULL);
        pthread_mutex_lock(&arena_data.arenas[arena_index + 1].mutex);
        pthread_mutex_unlock(&new_arena_mutex);

        return user_area((t_alloc_chunk *)current_pool->chunk, size, &arena_data.arenas[arena_index + 1].mutex);
    }

这是 printf 语句之一，它安慰了我的理论，即存在竞争条件：

THREAD 0x7f9c3b216700 READS[1] ARENA COUNT AT 4
THREAD 0x7f9c3b216700 READS[2] ARENA COUNT AT 5

该值应该相等，但事实并非如此。

标签： cmultithreadingrace-condition

解决方案

我可以在您的代码中发现三个问题。

1.两个线程创建arenas时的竞争条件

这是您在问题中描述的竞争条件：

所以我怀疑一个线程可能在另一个线程增加它之前读取 arena_count 的值，当它完成读取它时，增加它的线程释放 new_arena_mutex 并且第一个线程开始创建一个使用一个错误的索引。

是的，这可能发生。来自的负载arena_data.arena_count是原子发生的，但线程通常可能不会假设该值（仍然）正确。您答案中的修改版本不能解决问题。

为了解决这个问题，以下保证可能会有所帮助：在arena_data.arena_count持有new_arena_mutex. 结果，持有互斥锁的线程可以安全地加载arena_data.arena_count（当然，在持有互斥锁的同时），并且可以确保它的值在解锁互斥锁之前不会改变。让我尝试通过更改和评论您更新的代码来解释：

  while (pthread_mutex_trylock(&current_arena->mutex) != 0) {

    if (arena_index == arena_data.arena_count - 1) {
// This thread checks the condition above _without_ holding the
// `new_arena_mutex`. Another thread may hold the mutex (and hence it
// may increment `arena_count`).

      if (pthread_mutex_trylock(&new_arena_mutex) == 0) {
// Now, this thread can assume that no other thread writes to
// `arena_data.arena_count`. However, the condition
//
//     arena_index == arena_data.arena_count - 1
//
// may no longer be true (because it had been checked before locking).

    if (arena_data.arena_count < M_ARENA_MAX) {
// This thread may create a new arena at index
// `arena_data.arena_count`. That is safe because this thread holds
// the `new_arena_mutex` (preventing other threads from modifying
// `arena_count`.
//
// However, it is possible that `arena_index` is not at the position
// of the most recently created arena (checked _before_ locking). Let
// us just assume that all the recently created arenas are still
// locked. Hence we just skip the check and directly jump to the most
// recently created arena (as if we failed locking).
      arena_index = arena_data.arena_count - 1;
      current_arena = &arena_data.arenas[arena_index];
      ++arena_data.arena_count;
      assert(
        arena_index + 1 == arena_data.arena_count &&
        "... and this thread is holding the mutex, so it stays true."
      );
      creator = true;
      break;
    } else {
      pthread_mutex_unlock(&new_arena_mutex);
    }

在我看来，如果您将这些操作提取到诸如

// both functions return `arena_index` or `-1`
int try_find_and_lock_arena();
int try_create_and_lock_arena();

2. 可疑（错误？）后增量运算符

以下行中的后增量运算符在我看来是错误的：

current_arena = &arena_data.arenas[arena_index++];// post-increment
// now, `&arena_data.arenas[arena_index]` is one beyond `current_arena`.

写成两行，可能更容易推理该行为：

assert(
  current_arena == &arena_data.arenas[arena_index] &&
  "this is an invariant I expect to hold"
);

current_arena = &arena_data.arenas[arena_index];// this is a no-op...
arena_index++;// ... and now, they are out of sync

assert(
  current_arena == &arena_data.arenas[arena_index] &&
  "now, the invariant is broken (and this assert should fire)"
);

3.互斥锁/解锁对的可读性

我发现很难为所有可能的路径匹配互斥锁的锁定/解锁操作，因为它们发生在不同的范围内。

    // [new_arena_mutex is locked]

    current_pool = create_new_pool(/* ... */, &new_arena_mutex);

    if (current_pool == MAP_FAILED) return NULL;// error-path return
    // `create_new_pool` unlocks iff it returns `MAP_FAILED`...

    /* ... */

    pthread_mutex_unlock(&new_arena_mutex);
    // ... otherwise, the mutex is unlocked here

    return user_area(/* ... */);

推荐阅读