c - 向等待锁的线程发出信号，表明该锁已变得无关紧要

Question

我有一个用 C 语言实现的哈希表，其中表中的每个位置都是一个链接列表(用于处理冲突)。这些链表本质上是线程安全的，因此如果表的大小是恒定的，则不需要在哈希表级别编写额外的线程安全代码 - 哈希表是线程安全的。

但是，我希望哈希表随着值的添加而动态扩展，以保持合理的访问时间。不过，为了使表扩展，它需要额外的线程安全性。

就本问题而言，可以安全并发发生的过程是“良性”的，而表大小调整过程(不能同时发生)是“关键”的。当前使用该列表的线程称为“用户”。

我的第一个解决方案是为所有锁定互斥锁的关键函数添加“前导码”和“后导码”代码，然后等待，直到没有当前用户继续操作。然后，我向良性函数添加了前导码和后导码代码，以检查关键函数是否正在等待，如果是，则在同一个互斥锁处等待，直到关键部分完成。

在伪代码中，前/后同步函数应该如下所示:

benignPreamble(table) {
    if (table->criticalIsRunning) {
        waitUntilSignal;
    }
    incrementUserCount(table);
}

benignPostamble(table) {
    decrementUserCount(table);
}

criticalPreamble(table) {
    table->criticalIsRunning = YES;
    waitUntilZero(table->users);
}

criticalPostamble(table) {
    table->criticalIsRunning = NO;
    signalCriticalDone();
}

我的实际代码显示在这个问题的底部并使用(也许不必要)caf's PriorityLock from this SO question 。坦率地说，我的实现是 smells awful 。处理这种情况的更好方法是什么？目前，我正在寻找一种方法向互斥体发出信号，表明它是不相关的，并同时“解锁所有等待线程”，但我一直认为必须有一种更简单的方法。我试图以这样的方式进行编码:如果关键进程没有运行，任何线程安全机制都会被“忽略”。

---

当前代码

void startBenign(HashTable *table) {

    // Ignores if critical process can't be running (users >= 1)
    if (table->users == 0) {
        // Blocks if critical process is running
        PriorityLockLockLow(&(table->lock));
        PriorityLockUnlockLow(&(table->lock));
    }
    __sync_add_and_fetch(&(table->users), 1);

}

void endBenign(HashTable *table) {
    // Decrement user count (baseline is 1)
    __sync_sub_and_fetch(&(table->users), 1);
}

int startCritical(HashTable *table) {

    // Get the lock
    PriorityLockLockHigh(&(table->lock));

    // Decrement user count BELOW baseline (1) to hit zero eventually
    __sync_sub_and_fetch(&(table->users), 1);

    // Wait for all concurrent threads to finish
    while (table->users != 0) {
        usleep(1);
    }

    // Once we have zero users (any new ones will be
    // held at the lock) we can proceed.
    return 0;
}

void endCritical(HashTable *table) {

    // Increment back to baseline of 1
    __sync_add_and_fetch(&(table->users), 1);

    // Unlock
    PriorityLockUnlockHigh(&(table->lock));
}

Answer 1

看起来您正在尝试重新发明读写锁，我相信 pthreads 作为原语提供了这种锁。您尝试过使用它吗？

更具体地说，您的良性功能应该采用“读取器”锁，而您的关键功能则需要“写入器”锁。最终结果将是，可以根据需要执行尽可能多的良性函数，但是当关键函数开始执行时，它将等待，直到没有良性函数正在处理，并且将阻止其他良性函数直到其完成。我想这就是你想要的。