C语言公平锁实现

Linux的mutex是不保证公平性，最后调用lock的线程经常更容易拿到锁，那在此基础上，实现一个具有公平性的锁。
首先需要一个队列，可以用链表实现。

struct node {
  struct node *next;
};

struct fairlock{
  pthread_mutex_t mutex;
  pthread_cond_t cond;
  struct node *head;
  struct node *tail;
}

那么每次新有lock的时候需要把它放到链表的尾部，然后当尾部变成头部的时候，说明前面上锁的都已经离开了，这个时候就能获得锁了。
然后如果头部不是自己，就没必要着急，等到解锁的时候再检查也行，所以这里用了条件变量。
这里有一点是同一个地址是不会被分配给两个线程的，所以这里只要比较head的地址是否与new_node相等就能知道是不是轮到自己了。

void fairlock_lock(struct fairlock *lock)
{
  struct node *new_node = calloc(1, sizeof(struct node));
  new_node->next = NULL;
  pthread_mutex_lock(&lock->mutex);
  if (lock->tail == NULL) {
    lock->tail = new_node;
    lock->head = new_node;
  } else {
    lock->tail->next = new_node;
    lock->tail = new_node;
  }
  while (lock->head != new_node) {
    pthread_cond_wait(lock->cond);
  }
  pthread_mutex_unlock(&lock->mutex);
}

解锁的时候注意唤醒正在等待锁的线程

void fairlock_unlock(struct fairlock *lock)
{
  assert(lock->head->tid == gettid());
  pthread_lock(&lock->mutex);
  struct node *next = lock->head->next;
  free(lock->head);
  lock->head = next;
  pthread_cond_broadcast(lock->cond);
  pthread_unlock(&lock->mutex);
}

对于条件变量而言只要释放锁，然后调用库中的条件变量就好了。然后在等待结束后获得锁即可。

struct faircond{
  pthread_mutex_t mutex;
  pthread_cond_t cond;
};

void fairlock_cond_wait(struct faircond *cond, struct fairlock *lock) {
  fairlock_unlock(lock);
  pthread_mutex_lock(&cond->mutex);
  pthread_cond_wait(&cond->cond, &cond->mutex);
  pthread_mutex_unlock(&cond->mutex);
  fairlock_lock(lock);
}

void fairlock_cond_broadcast(struct faircond *cond, struct fairlock *lock) {
  pthread_mutex_lock(&cond->mutex);
  pthread_cond_broadcast(&cond->cond);
  pthread_mutex_unlock(&cond->mutex);
}

调试小技巧
在死锁的时候ctrl + c, 然后输入

thread apply all bt

可以看到所有线程的backtrace，这样就能知道死锁是什么情况了。