1. 锁与硬件支持
2. 测试并设置 = 原子交换
3. 比较并交换
4. 链接加载和条件存储指令对
5. 获取并增加
6. 改进自旋 - Solaris系统中的加锁和唤醒机制
7. 改进自旋 - Linux的futex机制

锁与硬件支持

测试并设置 = 原子交换

int test_and_set(int *old_ptr, int new){
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

//需要将锁初始化为0

void lock(lock_t *lock){
    //去测试和更新是不是1
    while(test_and_set(lock, 1) == 1){
        //自旋, 什么也不做
    }
    //成功往下执行, 即lock()函数正常结束, 进入线程自己的临界区代码
}

void unlock(lock_t *lock){
    *lock = 0
}

比较并交换

//这个函数全部原子化操作
int cas(long *addr, long old, long new)
{
    int result = *addr;
    if(*addr == old)
        *addr = new;
    return result;
}

//需要将锁初始化为0

void lock(lock_t *lock){
    //比较原来的值是不是0, 如果是0就更新成1, 如果原来的值是0就返回0. 如果原来的值是1就返回1.
    while(cas(lock, 0, 1) == 1){
        //自旋, 什么也不做
    }
    //成功往下执行, 即lock()函数正常结束, 进入线程自己的临界区代码
}

void unlock(lock_t *lock){
    *lock = 0
}

链接加载和条件存储指令对

Alpha: ldl_l/stl_c , ldq_l/stq_c
PowerPC: lwarx/stwcx , ldarx/stdcx
MIPS架构: ll/sc
ARM架构: ldrex/strex (ARMv6 , v7), ldxr/stxr (ARM version 8)
RISC-V: lr/sc

int ll(int *ptr){
    return *ptr;
}

int sc(int *ptr, int new){
    //如果ptr未改变, 更新其值为new, 然后返回1, 表示成功
    if(*ptr has not changed){
        *ptr = new;
        return 1;
    //返回0, 表示更新失败, 什么也没做
    } else {
        return 0;
    }
}

//需要将锁初始化为0

void lock(lock_t *lock){
    while(1){

        //LEVEL1 打断

        while(ll(lock) == 1){

        //LEVEL2 打断
            //自旋
        }

        //LEVEL3 打断

        if(sc(*lock,1) == 1){
            return;
        }

    }
}

void unlock(lock_t *lock){
    *lock = 0
}

获取并增加

int fetchAndAdd(int *ptr){
    int result = *ptr;
    *ptr = result + 1;
    return result;
}

//定义一个锁结构变量
typedef struct lock_t {
    int ticket;
    int turn;
} lock_t;

//初始化锁结构变量中的ticket和turn都是0

lock(lock_t *lock){
    //对ticket原子加1, 返回原来的值
    int myturn = fetchAndAdd(&lock->ticket);

    //判断锁里的turn是不是等于我的顺序, 是的话就进入临界区, 不是的话继续等待.
    while(lock->turn != myturn){
        //自旋
    }
}

void unlock(lock_t *lock){
    fetchAndAdd(&lock->turn);
}

改进自旋 - Solaris系统中的加锁和唤醒机制

//创建一个锁数据结构, 其中有两个int flag 和 guard, guard相当于原来的互斥锁变量, queue_t是存放线程号的队列. flag下边来看
typedef struct lock_t {
    int flag;
    int guard;
    queue_t *q;
} lock_t;

//初始化, 所有变量为0, 然后创建一个队列
void lock_init(lock_t *m){
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

//lock函数, 如果成功进入到临界区的时候, 还需要做点事情
void lock(lock_t *lock){
    while(test_and_set(&lock->guard, 1) == 1){
        //自旋, 什么也不做
    }
    //只要通过这里, 就可以认为是临界区了

    //如果flag=0, 将其设置为1, 然后恢复guard为0 , 可以看到这其实相当于用guard给flag上了一个锁, 而flag此时又标记着有没有线程在临界区.
    if(lock->flag == 0){
        lock->flag =1;
        lock->guard = 0;
    } else {
        queue_add(m->q, gettid());
        lock->guard = 0;
        //这个调用让线程休眠
        //危险打断点
        park();
    }
}

void unlock(lock_t *lock){

    //也是先尝试去获取guard锁, 注意这和原来直接设置互斥锁为0不同. 因为guard锁保护着flag和队列, 因此对flag和队列的操作需要去拿到guard锁
    while(test_and_set(&lock->guard, 1) == 1){
        //自旋, 什么也不做
    }

    //如果队列为空, 即没有任何等待中的线程, 将flag设置为0
    if(queue_isEmpty(lock->q){
        lock->flag = 0;

    //如果队列不为空, 在一个线程结束之后, 会执行unlock, 去唤醒其他的线程
    } else {
        //从队列中弹出一个线程id并且唤醒这个线程id
        unpark(queue_remove(lock->q));
    }

    //解除guard锁
    lock->guard = 0;

}

void lock(lock_t *lock){
    while(test_and_set(&lock->guard, 1) == 1){
        //自旋, 什么也不做
    }
    //只要通过这里, 就可以认为是临界区了

    //如果flag=0, 将其设置为1, 然后恢复guard为0 , 可以看到这其实相当于用guard给flag上了一个锁, 而flag此时又标记着有没有线程在临界区.
    if(lock->flag == 0){
        lock->flag =1;
        lock->guard = 0;
    } else {
        queue_add(m->q, gettid());
        setpark();
        lock->guard = 0;
        //即使这里被打断, 被其他线程在queue中叫醒, 再执行park()也不会睡眠.
        park();
    }
}

改进自旋 - Linux的futex机制

void mutex_lock(int *mutex){
    int v;

    //原子的比较并设置, 作用是取出mutex的31位也就是最高位并尝试设置为1(这个函数的set意思就是设置成1), 检测是不是0, 如果是0, 说明没有锁, 就会返回, lock函数结束, 进入临界区, 而且此时mutex最高位就是1
    if(atomic_bit_test_set(mutex, 31) == 0){
        return;
    }

    //如果不通过, 说明当前有锁, 需要想办法让线程睡眠
    //刚才的solaris是在临界区执行的再用一个锁来标记睡眠. Linux不是在临界区执行, 而是在没取到锁的时候执行

    //断点1

    //策略是第一次没有拿到锁的话, 去增加mutex1, 表示多了一个线程在等待. 然后让线程进行自旋, 如果拿到锁, 肯定要return, 但是在return之前去减少一次mutex的计数.
    atomic_increment(mutex);

    //断点2
    while(1){
        if(atomic_bit_test_set(mutex, 31) == 0){
            atomic_decrement(mutex);
            return;
        }

        //自旋中又没拿到锁, mutex为负数, 此时要确认一下mutex是不是真的是负数, 如果真的有锁, 就尝试睡眠.
        //这里没有原子操作, 如果出现不相等(很可能, 因为其他线程更新mutex), 那就不睡了, 正好继续去抢, 如果相等, 说明某个线程一直在临界区或者线程很少, 都停止了争抢, 就休眠.
        v = *mutex;
        if(v > 0){
            continue;
        }
        //断点3
        futex_wait(mutex, v);
    }
}

void mutex_unlock(int *mutex){

    //这个作用是将1加到mutex的最高位上, 然后检查结果是不是0. 很显然, 这里首先必定会释放最高位(作为锁, 因为只有一个线程能进入到执行unlock), 然后会检查是不是0, 只有剩下的31位也都是0, 即线程队列中已经没有线程, 才会直接返回, 否则就会通知内核去唤醒一个线程.
    if(atomic_add_zero(mutex, 0x80000000)){
        return;
    }

    //执行到这里的话, 之前的atomic_add_zero已经释放了作为锁的最高位变量, 可以唤醒等待队列中的一个线程了.
    futex_wait(mutex);
}