使用futex实现互斥和条件变量

Question

我使用futex syscall实现了互斥变量和条件变量。我相信我的实现是正确的，但希望得到其他人的验证。对于进一步改进互斥变量和条件变量的性能的任何建议也将不胜感激。

  #ifndef __SYNCHRONIZATION__
  #define __SYNCHRONIZATION__

  #include <unistd.h>
  #include <limits.h>
  #include <sys/syscall.h>
  #include <linux/futex.h>
  #include "types.h"
  #include "assembly.h"

  typedef UINT32 mutex;
  typedef struct condvar condvar;

  struct condvar    {
   mutex *m;
   int seq;
  };

  void mutex_init(mutex *m) {
   *m = 0;
  }

  void mutex_destroy(mutex *m)  {
   *m = 0;
  }

  void mutex_lock(mutex *m) {
   UINT32 c;
   if((c = __sync_val_compare_and_swap(m, 0, 1)) != 0)  {
    do  {
        if((c == 2) || __sync_val_compare_and_swap(m, 1, 2) != 0)
            syscall(SYS_futex, m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
    } while((c = __sync_val_compare_and_swap(m, 0, 2)) != 0);
   }
  }

  void mutex_unlock(mutex *m)   {
   if(__sync_fetch_and_sub(m, 1) != 1)  {
    *m = 0;
    syscall(SYS_futex, m, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
   }
  }

  void cond_init(condvar *c, mutex *m)  {
   c->m = m;
   c->seq = 0;
  }

  void cond_destroy(condvar *c) {
   c->m = NULL;
   c->seq = 0;
  }

  void cond_signal(condvar *c)  {
   __sync_fetch_and_add(&(c->seq), 1);
   syscall(SYS_futex, &(c->seq), FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
  }

  void cond_broadcast(condvar *c)   {
   __sync_fetch_and_add(&(c->seq), 1);
   syscall(SYS_futex, &(c->seq), FUTEX_REQUEUE_PRIVATE, 1, (void *) INT_MAX, c->m, 0);
  }

  void cond_wait(condvar *c)    {
   UINT32 oldSeq = c->seq;
   mutex_unlock(c->m);
   syscall(SYS_futex, &(c->seq), FUTEX_WAIT_PRIVATE, oldSeq, NULL, NULL, 0);
   while (xchg32(c->m, 2))  {
    syscall(SYS_futex, c->m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
   }
  }

  #endif

Answer 1

我对Futex代码没有特别的经验，所以请谨慎对待这一点：

看看mutex_lock，我认为一些评论是有用的。据我所知，它就是这样做的：

• 首先，让我们定义您的值0、1、2的含义。我理解它们分别意味着“自由”、“锁定”、“锁定”和“争夺”。一些#定义的常量会清楚地说明这一点(假设它是正确的)。
• 第一个比较和交换试图锁定互斥对象。如果((c= __sync_val_compare_and_swap(m，0，1)) != 0) {如果成功，则函数退出时互斥锁住(即。它的价值是1)。但是，如果互斥锁没有解锁(0)，这就失败了，我们进入了do...while循环。
• 在这一点上，我们知道互斥锁(确切地说，它可能已经改变了)要么是锁定的，要么是有争议的。如果有争议，我们希望进行一个futex系统调用，等待它被解锁。如果( (c == 2) x= 0) syscall(SYS_futex，m，FUTEX_WAIT_PRIVATE，2，NULL，NULL，0)；因此，如果我们知道互斥是有争议的(c == 2)，或者只锁定了它并成功地设置了竞争，我们就进行系统调用。但是，由于互斥对象可能在第一次比较和交换之后发生了变化，我们必须进行另一次比较和交换，将其锁定的1替换为有争议的2。如果互斥对象改变了状态，并且不再被锁定，这将失败，并且我们不会进行系统调用。(请注意，系统调用本身在输入互斥变量状态之前就对其进行了保护，因此使用了“2”参数，它可以确保如果*m不是2，内核就不会被输入。)
• 如果我们没有进行系统调用(因为互斥对象已经更改)，或者我们进行了调用并返回(同样是因为互斥体状态已经改变)，那么我们将到达循环的while部分。} while((c = __sync_val_compare_and_swap(m，0，2)) != 0)；此时我们可以期望互斥体是空闲的，并且我们可以尝试锁定它。但是，代码尝试将其设置为有争议的(2)。如果它成功了，则循环和函数退出，互斥设置为有争议的，而不仅仅是锁定。这似乎是错误的-最后的比较和交换应该是设置'1'，而不是'2‘。如果用1替换2，则循环退出条件与函数开始时的条件相同，可以简化为: enum mutex_state { FREE = 0，LOCKED，mutex_state }；mutex_lock(mutex *m) { enum mutex_state c；而((c = __sync_val_compare_and_swap(m，FREE，LOCKED)) // set LOCKED { if ((c ==争议)x\x __sync_val_compare_and_swap(m，锁定，有争议) != FREE) / set调度{ syscall(SYS_futex，m，FUTEX_WAIT_PRIVATE，争议，NULL，0)}