pthread_mutex_lock/unlock 的性能表现

Question

我发现当我有一个频繁锁定和解锁线程的算法时，会有相当大的性能损失。

有没有办法减少这种开销？使用信号量是否更高效？

谢谢

typedef struct _treenode{
   struct _treenode *leftNode;
   struct _treenode *rightNode;
   int32_t data;
   pthread_mutex_t mutex;
}TreeNode;

pthread_mutex_t _initMutex = PTHREAD_MUTEX_INITIALIZER;

int32_t insertNode(TreeNode **_trunk, int32_t data){
   TreeNode **current;
   pthread_mutex_t *parentMutex = NULL, *currentMutex = &_initMutex;

   if(_trunk != NULL){
      current = _trunk;
      while(*current != NULL){
         pthread_mutex_lock(&(*current)->mutex);
         currentMutex = &(*current)->mutex;
         if((*current)->data < data){
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            pthreadMutex = currentMutex;
            current = &(*current)->rightNode;
         }else if((*current)->data > data){
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            parentMutex = currentMutex;
            current = &(*current)->leftNode;
         }else{
            pthread_mutex_unlock(currentMutex);
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            return 0;
         }
      }
      *current = malloc(sizeof(TreeNode));
      pthread_mutex_init(&(*current)->mutex, NULL);
      pthread_mutex_lock(&(*current)->mutex);
      (*current)->leftNode = NULL;
      (*current)->rightNode = NULL;
      (*current)->data = data;
      pthread_mutex_unlock(&(*current)->mutex);
      pthread_mutex_unlock(currentMutex);
   }else{
      return 1;
   }
   return 0;
}

int main(){
   int i;
   TreeNode *trunk = NULL;
   for(i=0; i<1000000; i++){
      insertNode(&trunk, rand() % 50000);
   }
}

- poy

---

信号量（semaphore）执行不同（更复杂）的操作，因此可能会更慢。你用的是什么操作系统？你能否将锁变得更细粒度，以便不会阻塞太长时间？ - Steve Townsend

可以将它们变得更粗粒度/在每次锁定时执行更多的工作，这样就不会有太多的上下文切换。这需要保持一个微妙的平衡。 - nos

如果您展示/描述算法，我们可能会给出提示。解决方案应该是：使用更少的锁定（将工作分配到专用核心上，这样您就不需要锁定子区域）或使其无锁定（非常困难）。除了摩尔定律之外，没有任何东西可以帮助。 - sehe

一些算法本质上比其他算法更串行化。但是，锁定和限制访问以获得正确的结果比不加锁并更快地获得错误结果要好。 - Martin York

1. 你正在锁定刚分配的对象，如果你不立即将其放入树中，则绝对没有必要这样做。
2. 我认为你设置 pthreadMutex 时有一个拼写错误；它应该是 parentMutex。
3. 你重叠的自上而下锁定策略存在死锁风险，如果你曾经以相反方向遍历树结构。
4. 我不确定你通过重叠的父/子锁定实际上是否实现了你想要的结果；你需要提供一份允许操作的列表。
5. 如果树可能变得很大，请为整个树使用单个 RWLock，但请参阅我的其他评论。

- class stacker

Answer 1

不要过于关注细节，要放眼全局。

任何依赖于两个线程可能会相互干扰的算法都是自然效率低下的。试着找到一种方法来大幅度减少交互的需求。

例如，如果一个线程产生数据而另一个线程消费数据，人们可以很容易地想出一种低效的算法：生产者将数据发布到共享内存中，然后等待消费者消费它。与此同时，消费者正在等待生产者完成等等。通过让生产者写入文件或管道，消费者从中读取，可以简化这个问题。

- wallyk

Answer 2

pthread_mutex_lock和pthread_mutex_unlock的成本取决于竞争情况：

1. 单线程使用 - 只存在一个线程，或只有一个线程正在使用互斥锁和它保护的资源：锁定是几乎免费的，最多可能只需80-100个周期。
2. 多个线程同时使用资源，但锁定时间很短且竞争很少：锁定操作具有一些成本，并且很难衡量；该成本主要包括使其他核心/ CPU缓存行失效。
3. 重要的锁竞争：几乎每个锁定和解锁操作都需要从内核获取帮助，成本很容易达到每个锁/解锁数千（甚至数万）个周期。

尽管如此，在大多数情况和实现中，互斥锁应该是最廉价的锁定原语。偶尔自旋锁可能表现更好。我从不指望信号量表现更好。

- R.. GitHub STOP HELPING ICE

---

有些情况下，80到100个周期并不是“几乎免费”的。 - Michael

也许我应该澄清一下：我是在将其与一对琐碎的外部函数调用进行比较，即如果 pthread_mutex_lock 和 pthread_mutex_unlock 是近乎空的函数（但仍无法内联并仍会设置堆栈帧），您将获得的性能。我手头没有数据，但我认为“no-op locks”的情况可能会接近80个周期，除非是在高端x86机器上。 - R.. GitHub STOP HELPING ICE

对于基于原子环的简单生产者/消费者，当有数据可用时，使用信号量进行信号通知可以优于条件变量/互斥锁，因为后者需要生产者也要锁定以更改条件。 - CashCow

@CashCow：我关于信号量的评论是指使用二进制信号量作为锁。我的直觉是，这应该最多与互斥锁的性能相匹配，但可能也会稍微差一些。特别是，POSIX信号量具有一些可能使它们更昂贵的属性--能够对取消操作进行操作，要求post操作是异步信号安全的（这限制了实现选择），等等。此外，虽然下一个POSIX问题可能会放松互斥锁的要求以允许获取/释放语义，但信号量几乎肯定仍将保持“seq_cst”。 - R.. GitHub STOP HELPING ICE

Answer 3

据我所见，您的锁策略并不是最佳的，因为大多数锁不是用来更改数据的，而只是用来读取并在树中找到路径。 pthread_rwlock_t可以帮助解决这个问题。您只需要在树下路径上获取读锁，直到遇到要进行修改的节点。然后，您将获取写锁。通过这种方式，当其他线程在不同分支中遍历树时，它们可以执行相同的任务而不会相互干扰。

良好的pthread_rwlock_t实现应该使用原子操作更改读者计数器，只要没有与写者竞争。这应该非常快。一旦有竞争，它的代价就像一个互斥锁，我想。

- Jens Gustedt

---

@Andrew，抱歉是pthread_rwlock_t。如果在您的系统上实现了它，它应该只需在<pthread.h>中存在。 - Jens Gustedt

@Andrew和Jens。1）RWLock并不总是更好的解决方案。如果所有读操作都非常短，而所有写操作都很长，与MutEx相比，它们的开销很容易抵消其概念上的好处。这取决于读者和写者的数量以及他们在并行访问该部分的频率。2）据我所知，RWLock是建立在MutEx之上的，但即使不是，它们的成本也比MuitExes高。3）如果写入很少发生，我会为整个树使用单个RWLock。然后，所有读者都可以并行地获得满足。 - class stacker

Answer 4

你的锁可能过于细粒度了。当然，最佳粒度可能因工作负载而异。

你可以为整个树使用单个锁，这样可能会表现更好。但是，如果你进行大量读取和相对较少的插入/删除操作，你最终会发现整个树经常被锁定，没有什么好的理由。你可能需要使用读写锁，它允许同时有几个读者。

你的问题让我想起了另一个问题，其中比较了链表的细粒度锁定和粗粒度锁定。虽然在粗粒度版本中，每个线程依次运行（不并行），总运行时间略长于每个线程的运行时间之和，在细粒度版本中，总运行时间远远少于每个线程的运行时间之和，但细粒度锁定的额外开销完全抵消了这些好处，使得细粒度版本比粗粒度版本更慢。

- ninjalj

Answer 5

在pthread_mutex_lock/unlock的情况下，锁定和解锁是非常昂贵的操作。如果有更多关于算法的细节，我可以提出一些建议，但就我所知，我无法确定任何事情。 信号量是一种替代方法（同样取决于算法），屏障也是另一种有效的并发方法。为了帮助降低开销，您可以采取这样或那样的措施，例如将锁定变得更小或更大粒度。 循环内部的锁定是不好的，特别是循环多次迭代时，您可能需要将它们移动到循环外部。 这只是一个例子，但我可能还能想出更多的例子。 关键是要确定锁的成本是否大于代码中的临界区成本。 如果您提供您的算法或一些示例代码，我会很乐意为您查看。

- Jesus Ramos

---

他确实提到了pthread_mutex_lock/unlock，这些操作相当耗费资源。不过你说得对，我应该修改我的答案，只包括pthread_mutex_lock/unlock，因为CriticalSection和Boost锁的性能相对较快。我还建议他发布一些代码，并提出一些可以改变被锁定部分以提高性能的方法。 - Jesus Ramos

Answer 6

pthread_mutex_lock和pthread_cond_wait是操作系统原语 - 它们将调用线程置于睡眠状态，将控制权转移给另一个线程。也就是说，它们涉及系统调用和大量开销。在两个线程之间的紧密集成中，您实际上不想放弃任何控制权，即使只有一个周期。

鉴于此，我建议使用volatile int变量代替互斥锁：

volatile int data_ready = 0;
/*  ... */
while (!data_ready);
process_data();
data_ready = 0;

- SmugLispWeenie