锁

C语言协程库实现

锁是很常见的同步原语,那么锁的实现原理是怎样的呢?下面我们就自己模拟实现一下各种锁来更好地理解锁的实现和代价.

自旋锁

自旋锁是一种成本较低的锁,因为它只会在当前cpu循环忙等直到获取到锁而不会让出控制权.
自旋锁的特点也使其只能用于保护操作较短的临界区,且不能睡眠.

代码实现

主要是通过cas等原子操作来模拟.

typedef volatile spin_lock_t;

spin_lock(spin_lock_t *lock)
{
    do {
        if (cas(&lock, 0, 1) == 0)  // cas循环判断,直到加锁成功.
            break;
    } while (1);
}

spin_unlock(spin_lock_t *lock)
{
    atomic_set(&lock, 0); // 锁变量置0
}

互斥锁

用原子操作和信号量实现互斥锁

typedef struct {
    int val;
    int waiters;
    spin_lock_t lock;
    sem_t *sem;
}mutex_lock_t;

mutex_lock(mutex_lock_t *lock)
{
    while(cas(&lock->val, 0, 1) != 0)
    {
        sem_wait(sem);
    }

}

mutex_unlock(mutex_lock_t *lock)
{
    atomic_set(&lock->val, 0);
    sem_post(sem);
}

读写锁

用自旋锁和信号量实现读写锁

typedef struct {
    int readers;
    int writers;
    int writer_waiters;
    int cur_writer;
    sem_t *sem;
    spin_lock_t lock;
}mutex_rw_lock_t;

mutex_rlock(mutex_rw_lock_t *lock)
{

    do {
        spin_lock(lock->lock);
        if (lock->writers == 0)
        {
            break;
        }
        else
        {
            spin_unlock(lock->lock):
            sem_wait(sem);
        }
    }
    lock->readers++;
    spin_unlock(lock->lock);
}

mutex_wlock(mutex_rw_lock_t *lock)
{
    do {
        spin_lock(lock->lock);
        if (!lock->readers && !lock->writers)
            break;

        spin_unlock(&lock->lock);
        sem_wait(&lock->sem);
    }

    lock->cur_writers = current();
    lock->writers++;
    spin_unlock(&lock->lock);
}

mutex_unlock(mutex_rw_lock_t *lock)
{
    if(lock->cur_writers == current())
        mutex_wunlock(lock);
    else
        mutex_runlock(lock);
}

mutex_runlock(mutex_rw_lock_t *lock)
{
    spin_lock(&lock->lock);
    lock->readers--;
    spin_unlock(&lock->lock);

    sem_post(&lock->sem);
}

mutex_wunlock(mutex_rw_lock_t *lock)
{
    spin_lock(&lock->lock);
    lock->writers--;
    lock->cur_writer = 0;
    spin_unlock(&lock->lock);

    sem_post(&lock->sem);
}

上面的读写锁实现有一个问题就是但读者很多时,可能会将写者饿死.一种改进的方法是将等待者进行排队.