问题标签 [mutual-exclusion]

我正在研究多线程并试图理解信号量和互斥的概念。我在网上找到的大多数示例都使用某种库（例如pthread）来实现信号量或互斥量，但我更感兴趣的是实现一个建立临界区的简单信号量——不超过一个线程访问特定内存区域。

对于这项任务，我相信我需要一个互斥锁（如果我正确理解术语，也就是二进制信号量）。我可以看到信号量如何通过将代码段“锁定”到单个线程来防止竞争条件，但是是什么阻止了信号量本身发生竞争条件？

我想象一个二进制信号量来保存一个int值来跟踪锁：

假设两个线程同时调用该P函数，它们都同时到达if(lock > 0)检查并将条件评估为真——这将创建一个竞争条件，其中两个线程都被授予同时访问同一内存区域的权限。

那么是什么阻止了这种竞争条件在现实世界的信号量实现中发生呢？

我正在尝试使用 Hoare 的监视器实现证券交易所。

它有两个函数 buy() 和 sell() 如下：

并且应该打印有关买方 ID、卖方 ID、股票代码、股票数量和价格的信息。公平总是得到满足。

我的解决方案的伪代码如下，但并不完整。它基本上为每个代码使用条件变量队列。当向证券交易所发送卖单时，卖方进程在此队列中进入休眠状态，并且买方进程向该卖方进程发出信号，如果条件（匹配价格限制和股票数量）满足，它想要购买。

这种方法是否能够处理多个代码的多个买卖订单？还是会导致死胡同？

我有这个用于交换元素的代码：

我将如何使用细粒度锁定来实现这一点以达到相同的效果？

我正在为学校开发一个 java 项目，你必须处理一个多线程程序。我需要一个类，在许多线程之间共享，它基本上是一个必须管理并发访问的值矩阵，它看起来像：

我正要使用 ReentrantReadWriteLock 矩阵来管理它，每个项目一个，但我意识到矩阵大小约为 10^3 X 10^3 所以我将拥有 100 万个锁！

你认为这是要走的路吗？（创建这么多锁可以吗？）

考虑到使用这个类的线程数被限制在一个小数 N（N 的范围从 2 到 8），你能找到一种更好的方法，它几乎只保留最小互斥但使用更少的锁吗？

感谢您的支持！

在尝试使用它解决更复杂的问题之前，我正在尝试在 C 中实现 Lamport's Bakery Algorithm 的简化版本。* 我所做的简化是锁仅由两个线程而不是 N 共享。

我设置了两个线程（通过 OpenMP 使事情变得简单），它们循环，试图在它们的关键部分增加一个共享计数器。如果一切都按计划进行，那么最终的计数器值应该等于迭代次数。但是，这里有一些示例输出：

嗬！有些东西坏了，但是什么？我的实现是相当教科书（供参考），所以也许我在滥用内存屏障？我是否忘记将某些内容标记为易失性？

我的代码：

要编译和运行（在 Linux 上），请执行以下操作：

• 我打算将简单的 Bakery 锁链接成二叉树（锦标赛风格），以实现 N 个线程之间的互斥。

我正在使用 mysql get_lock 来确保我为同一行代码运行的多个 php 脚本实例之间的互斥。我需要确保 is_free_lock 的两个同时执行不会产生 0，在这种情况下，我将最终被脚本的两个实例锁定，然后执行该代码两次。请帮忙。

我正在通过这个链接。根据这个 ：

类锁实际上是作为对象锁实现的。当 JVM 加载一个类文件时，它会创建一个 java.lang.Class 类的实例。当您锁定一个类时，您实际上是在锁定该类的 Class 对象。

但是根据 java 规范，堆上所有相同类型（类）的对象共享一个 Class 对象。那么对于对象的多线程同步访问来说，这怎么可能呢？

以下是 Peterson 的 2 线程锁定算法的通用版本，允许“n”个线程/进程竞争临界区。

基本上有“n”个级别和“n”个线程。处于非活动状态或在非临界区区域中执行的线程处于级别 0。级别 n-1 是临界区。每个线程/进程在进入临界区之前必须跨越 n-1 级。

有 2 个数组，级别 [n] 和受害者 [n]。第一个数组由线程的threadId索引，entry level[i]存储threadId为'i'的线程的当前级别。第二个数组由级别编号索引，条目victim[i] 存储最近进入级别“i”的线程的threadId。

level[] 的所有元素都初始化为 0。victim[] 没有特定的初始化。

该代码直接摘自 Maurice Herlihy 和 Nir ​​Shavit 所著的《多处理器编程的艺术》一书。

问题是代码似乎不满足互斥属性！

推理：- 第 6 行暗示，一个线程将保持在一个级别循环，直到有一些线程处于相同或更高级别，并且线程本身是最近进入它当前所在级别的线程。此外，只有一个线程可以保持在一个水平。如果第二个线程到达同一级别，那么第一个线程的“victim[i] == me”表达式将变为假，因此将被推到下一个级别。

现在，如果每个级别都有一个线程，并且级别 0 的线程尝试前进到级别 1。这会将级别 1 的线程推到级别 2，因为它不再是级别 1 的受害者。因此会有涟漪效应，每个线程将被下推一级，导致第 n-2 级的线程也进入其临界区！！

那么代码实际上是错误的还是我解释了什么错误？

I have some doubts about Peterson algorithm in a binary tree.

I am making some exercises of the book "The Art of Multiprocessor Programming" and i'm stuck in chapter 2, ex 13:

"Another way to generalize the two-thread Peterson lock is to arrange a number of 2-thread Peterson locks in a binary tree. Suppose n is a power of two. Each thread is assigned a leaf lock which it shares with one other thread. Each lock treats one thread as thread 0 and the other as thread 1."

That´s OK, but what? If Peterson only treats 2 threads, how will be this tree? One tree with ONE single leaf? (because if I have 2 threads, and each leaf treats 2 threads... the result will be a tree with a single leaf?)

"In the tree-lock’s acquire method, the thread acquires every two-thread Peterson lock fromthat thread’s leaf to the root. The tree-lock’s releasemethod for the tree-lock unlocks each of the 2-thread Peterson locks that thread has acquired, from the root back to its leaf."

What did he mean with that? How can a leaf go through the root node? Very confused!! :S

Thank you guys!

How can you use a semaphore to create a special critical section that allows two threads to be executing inside instead of the usual one thread?