尝试使用 "Readers Writer Lock" 时的竞争条件

Question

我正在使用 pthreads 开发一个项目，我自己实现了 Readers Writer Lock，它具有以下方法：

锁定 reader（多个可以同时读取）
写者锁定（只能写一个人）
解锁（两者都reader/writer）

我已经测试过了，效果很好，我的问题更符合逻辑，在我的程序中，我希望多个线程对特定范围内的数字进行一些测试，如果找到符合我的标准的数字，我希望它们将它们添加到共享资源中，该资源是一个数组。

如果该数字已经被另一个线程找到并且存在于数组中，则继续搜索。

这是我的算法的伪代码：

X = lowest number to search, X' = highest number to search,
func = the test for the number, ARR = the array shared between the threads, 
RWL_R = Lock for reader, RWL_W Lock for writer, RWL_U = Unlock.


FOR each NUM from X to X' DO:
    IF func(NUM) = true DO:
        FOR each cell of ARR DO:
            RWL_R // lock for reader since i'm reading from ARR
            IF ARR[cell] contains NUM DO:
                RWL_U // unlock since no longer reading from ARR
                skip to the next iteration of the first FOR loop
            ENDIF
        END FOR

        RWL_U // unlock since no longer reading from ARR
        ////// PROBLEM HERE ////////
        RWL_W // lock to write to array since for loop ended without finding the same NUM

        ARR[cell] <- NUM
        RWL_U // unlock since finished writing into array
    END IF
END FOR

如您所见，逻辑很好，因为我用丑陋的大写字母标记了那条小线 "PROBLEM HERE"。在 reader 解锁和写入器锁之间的小间隙内，可能（并且确实）会发生竞争条件。

所以我有 2 个可能的结果：

（好的）
- Thread_A找到第N个，锁定数组读取
- Thread_B找到相同的数字N，等待检查数组但当前被Thread_A锁定。
- Thread_A 完成遍历数组但数字 N 不存在，解锁锁并再次锁定它作为 writer，将 N 添加到数组，解锁锁并完成他的工作。
- Thread_B 现在可以检查数组，数字 N 在那里，所以它跳到数字 N2，其余的按预期工作。
（差）
- Thread_A找到第N个，锁定数组读取
- Thread_B找到相同的数字N，等待检查数组但当前被Thread_A锁定。
- Thread_A遍历完数组，N不存在，开锁
- Thread_B 接管锁并锁定为reader，检查数组，数字N 仍然没有（Thread_A 尚未添加）。
- Thread_B解开锁
- Thread_A或Thread_B现在锁定写锁，添加数字N，解锁并完成。
- 现在等待的线程加锁，加同号N，解锁完成。

所以我现在正在尝试找到解决问题的最佳逻辑方法，我只能考虑在检查数组时锁定作为编写器，直到完成写入才解锁它，或者创建一个切换的方法"atomically" 从 reader 锁到写锁，但这有点像 "Cheating" 而不是使用“Readers Writer Lock”机制，因为它应该是使用过。

在这里使用它有什么更好的逻辑方法？

Answer 1

i can only think about locking as a writer when checking the array and not unlocking it until finishing writing

这当然可行，但它会阻止阵列扫描的任何并发。如果这些消耗了程序运行时间的很大一部分，那么让扫描并发是非常可取的。

or to create a method that switches "atomically" from reader lock to writer lock, but that's kind of "Cheating" and not using the "Readers Writer Lock" mechanism as it's supposed to be used.

这是不可行的，因为当多个线程持有读锁时，您不能将读锁提升为写锁。写锁不仅必须排除其他写入者，还必须排除所有 readers。在您描述的情况下，您最终会遇到死锁，因为持有读锁的两个或多个线程需要将其提升为写锁，但是在所有其他线程都释放锁之前，它们中的任何一个都不会发生这种情况。

在任何情况下，即使您允许写锁与读锁共存，也不能可靠地阻止两个考虑相同数字的线程同时扫描文件到其当前末尾，看不到数字，并且，转，将其追加到数组中。

如果您想提供并发数组扫描但又想防止重复项被添加到您的数组中，那么您至少需要在线程之间进行更多的通信。

一个相对简单的方法是实现一个简单的交易系统。当有多个 reader 时，您的 reader / writer 锁将支持将读锁提升为写锁，但仅适用于自上次释放 writer 锁以来获得的 reader 锁。成功执行此类提升的线程可以确信数据在读取数据时未被修改，因此可以安全地更新数组。提升失败类似于未能提交事务——遇到这种失败的线程将需要从头开始重新扫描。

如果每个数字的出现次数相对较多，这将相当有效，因为随着重新扫描成本的增加，重新扫描的可能性会降低。

您还可以考虑更复杂的机制，通过该机制获取写锁的线程以某种方式通知 reader 它们正在写入什么值，以便任何 reader 对该值的扫描都可以提前中止。然而，这将更难编写，虽然听起来很高效，但在某些情况下，由于需要线程之间的更多同步，它实际上可能会更慢。

Answer 2

不要使用单个 readers/writer 锁，而是使用两个锁：一个用于读取，一个用于写入。每个线程都将获取读锁并扫描数组。如果要修改数组，则线程将获取写锁并重新扫描数组以确保尚未添加该数字。

这是伪代码：

acquire_read_lock();
if (!is_value_in_array(value)) {
    acquire_write_lock();
    if (!is_value_in_array(value)) {
        add_value_to_array(value);
    }
    release_write_lock();
}
release_read_lock();

Answer 3

你给出的两个选项在大多数情况下都不是最优的，因为一个选项可以防止多个 readers 同时检查（并且大概在一段时间后，readers 更常见比作家），而另一个是不可能的；即使您将 "atomically" 从 reader 锁切换到写锁，两个不同的 reader 都可以确定值 X 不存在，都请求升级到写锁，第一个写X 然后解锁，而第二个等待轮到它然后再次写入 X，你最终违反了唯一性不变量。

真正的答案取决于常见的使用模式：

如果一般情况下写入比读取更有可能发生（并发读取不常见），那么您只需删除 reader/writer 锁并使用简单的互斥锁。 Reader/writer 锁通常会产生不值得的开销，如果您不经常使用并发 readers，即使开销很小（有时是；Windows' SRW Locks 仅用于 "exclusive" (writer) 不需要递归获取的模式与临界区一样快或更快)，如果程序逻辑变得更复杂，或者你需要不断地从读切换到写锁定和返回，额外的逻辑和 acquisition/release 开销可能比单个锁定和独占访问解锁的成本更高。
如果您有其他经常使用但从不写入的代码，并且可能需要编写的 reader 不太常见 and 经常要写，然后使用你建议的解决方案；保留 reader/writer 锁，但从头开始使用 "might write" 代码锁进行写入；它消除了 "might write" 代码路径中的并发性，但 "only read" 用户可以并发操作。
如果读取比写入更常见（如果提供的代码是访问数组的唯一代码，这是类似这种情况的常见用例；否则你的数组将失去控制), 然后在 "upgrading" 之后执行双重检查写锁；升级到写锁后再次执行相同的扫描，以确保没有人抢到写锁并添加缺失值，如果值仍然缺失则写入。如果数组仅添加了新值，而现有值永远不会更改或删除，则可以对此进行优化以避免重新扫描。您只需记住在何处停止检查，并扫描在原始扫描和获取写锁之间添加的任何新条目。

#3 的伪代码如下所示：

FOR each NUM from X to X' DO:
    IF func(NUM) = true DO:
        RWL_R // lock for reader outside inner loop since repeatedly reading from ARR
        cell = 0
        WHILE cell < ARR.length DO:
            IF ARR[cell] contains NUM DO:
                RWL_U // unlock since no longer reading from ARR
                skip to the next iteration of the first FOR loop
            ENDIF
            cell += 1
        END WHILE

        RWL_U // unlock since no longer reading from ARR
        RWL_W // lock to write to array since for loop ended without finding the same NUM
        // NEW!!! Check newly added cells
        WHILE cell < ARR.length DO:
            IF ARR[cell] contains NUM DO:
                RWL_U // unlock since no longer reading from ARR
                skip to the next iteration of the first FOR loop
            ENDIF
            cell += 1
        END WHILE
        // If we got here, not in newly added cells either, so add to end
        ARR[cell] <- NUM
        RWL_U // unlock since finished writing into array
    END IF
END FOR

尝试使用 "Readers Writer Lock" 时的竞争条件

Race condition while trying to use "Readers Writer Lock"

c

linux

arrays

multithreading

pthreads