分类： LINUX
2010-08-15 23:54:25
自从各种任务不再顺序执行的那一天起，自从多道程序设计开始上线的那天，进程就戴上了脚镣。古老的操作系统的变体当然也接过了父亲的狼牙棒，信号量 杯证明是一种有效的互斥方式，可是它却存在很多弊端。其实unix不喜欢混乱，因此unix创造了进程这个可被操纵系统内核强制管理的执行绪概 念，unix几乎给了所有可以执行的东西一个进程上下文，然后管理这些进程，unix的进程管理是很强大的，可是总有管不了的，就是中断，中断处理机制被 视为一个硬件的无序性和软件进程管理的有序性之间的协调接口，因此中断处理程序并不属于任何进程的上下文，因此在中断中就不能像在别的进程上下文可以请求 信号量，因为中断处理中根本就没有地方放床导致任意进程上下文下没有地方睡眠。中断处理不能睡眠是不能在中断处理用信号量的原因，因此必须提供一个中断处 理中的互斥方案，另外，即使在进程上下文，如果需要的信号量很多，那么势必会造成进程频繁睡眠/被唤醒，这样进程调度的开销就过大，因此自旋锁就出来了， 不用睡眠，只是自旋，很简单，在内核中很高效。
可是自旋锁是个平均的权衡结果，没有考虑到数据的客观特殊类型以及操作类型，自旋锁太机 制化了，没有一点策略，其实想想便知道，读请求根本就不用锁也就是不用互斥，而写才需要互斥，在这种特殊需求下，linux提出了读写锁的概念，而且实现 的十分艺术，如果看看很多学生写的读写锁再看看linux内核实现的读写锁，你会认为学生们的作品就是垃圾，国产的教科书就是垃圾堆！我们欣赏一下这种艺 术：
static inline int __raw_read_trylock(raw_rwlock_t *lock)
{
atomic_t *count = (atomic_t *)lock;
atomic_dec(count); //以小跨度递减读信号量
if (atomic_read(count) >= 0)
return 1;
atomic_inc(count);
return 0;
}
static inline int __raw_write_trylock(raw_rwlock_t *lock)
{
atomic_t *count = (atomic_t *)lock;
if (atomic_sub_and_test(RW_LOCK_BIAS, count)) //以大跨度递减写信号量
return 1;
atomic_add(RW_LOCK_BIAS, count);
return 0;
}
static inline void __raw_read_unlock(raw_rwlock_t *rw)
{
asm volatile(LOCK_PREFIX "incl %0" :"+m" (rw->lock) : : "memory");
}
static inline void __raw_write_unlock(raw_rwlock_t *rw)
{
asm volatile(LOCK_PREFIX "addl %1, %0" : "+m" (rw->lock) : "i" (RW_LOCK_BIAS) : "memory");
}
static inline void __raw_read_lock(raw_rwlock_t *rw)
{
asm volatile(LOCK_PREFIX " subl $1,(%0)\n\t"
"jns 1f\n"
"call __read_lock_failed\n\t"
"1:\n"
::LOCK_PTR_REG (rw) : "memory");
}
static inline void __raw_write_lock(raw_rwlock_t *rw)
{
asm volatile(LOCK_PREFIX " subl %1,(%0)\n\t"
"jz 1f\n"
"call __write_lock_failed\n\t"
"1:\n"
::LOCK_PTR_REG (rw), "i" (RW_LOCK_BIAS) : "memory");
}
就 这么多吗？是的，就这么多！很简单，很对称，如果不看函数名和宏定义，你根本就看不出来哪个是读锁哪个是写锁，它们的形式是一样的，也没有队列，也没有复 杂的数据结构，从本质上说，读写锁是用自旋锁的思想实现的，自旋锁就是不断判断一个数字的大小，如果小于0就说明得不到锁，如果为1就得到了锁，释放锁就 是将锁设置为1就可以，近来又实现了ticket自旋锁，使得锁变得有序化了，照顾到了硬件缓存的缓存结果。自旋锁就是不断判断一个数的大小，不管谁想得 到锁都要经过竞争，也就是自旋，得不到锁就是因为将那个数减1后，它小于0了，如果让它不小于0不就可以得到锁了吗？我们的需求是读之间可以随意，但是写 之间必须互斥，另外读写之间也要互斥，而在自旋锁中，无论读写都要一样的动作，那么我们只需要将读写分开成为不同的动作就可以了，目的就是要体现出读和写 的不对称性，先看看自旋锁的实现，只要请求锁都要将锁变量减去1，只要释放都要将锁设置为1，那么读写锁中我们将读和写减去的数设置为不同就可以了，设置 写锁请求时要减去一个很大的数N，而读锁只需要减去1，只要大于0就可以得到锁，如果不是就忙等待，这样的话，如果初始化的时候将锁初始化为N，那么只要 有一个读，那么所就是N-1，如果再读，就是N-2，仍然大于0，如果写，就是-2，小于0，忙等，等待两个读者释放了锁，就是0了，那么写可以进行，写 完后释放锁，就是将锁加上N，于是锁恢复N，其实这个实现和信号量有点类似，不同的是等不到锁时不睡眠而是忙等，此实现给了读很多的N个可用信号量，因为 对于读，信号量的跨度是1，而对于写，只有1个信号量，写的跨度是N，这可以说是信号量的升级版，一个信号量支持两个不同的跨度，不过在等待的意义上，它 又像是自旋锁，总之，linux内核的实现很是艺术吧。
说完了读写锁，那么看看顺序锁，顺序锁更具有创意，它基于一个事实，在读写锁 中，如果读的时候恰好有一个写者在写，那么读者就要忙等，忙等是因为害怕读到不一致的数据，反过来如果写者发现有读者在读，它也要忙等，忙等是因为怕读者 读到不一致的数据，这种互相照顾必然会影响效率，不管怎样我们都可以赌一把，这种赌博需要很小的赌注就值得，没有必要每次读的时候都要请求锁，而是随时都 可以读，一旦读到不一致的数据，那么大不了再读一次，这个设想应该是很不错的，读写随时进行，谁也不管谁，自己注点意就可以了，比如以写者为主，读者自己 进行数据一致性的判断，这样效率会提高不少的。
分析到这里可以想到，有两个点要注意，一个就是读开始，一个就是读结束，这两个点将时间 分为了三个部分，读前，读中，读后，读前写完成和读后写完成都不会影响读操作，那么只有三类写操作会污染读者读到的数据，一个就是写在读前开始在读中结 束，一个是在读中开始在读中结束，一个是在读中开始，在读后结束，于是我们只需要监控写开始和写结束即可，按照最简单的数学原理，如果设定一个变量，在写 开始和写结束时都对它递增，我们就可以知道写的状态，这个数只要是偶数就说明没有在写中或者相反，取决于初始设置，那么读的时候可以尽量等到没有在写中的 时候进行，然后在读结束的时候判断这个变量，如果被增加了就说明开始了一次写已经结束或者开始了一次写还没有结束，总之我们的数据被污染了，那么就需要再 读一次，即使再读一次也不能保证没有写进行，但是我们可以再赌一把，这实际上是一个循环。这个顺序锁最起码解放了写操作，写操作不必关心读的情况，对于读 操作纯粹是赌博，但是读写锁对读操作是有好处的，因为大多数情况下只要没有写者，读者都可以随意，总而言之，顺序锁还是比读写锁好的。我们还是看一眼顺序 锁吧：
static inline void write_sequnlock(seqlock_t *sl)
{
smp_wmb();
sl->sequence++; //递增一个数字
spin_unlock(&sl->lock);
}
static inline void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock);
++sl->sequence; //释放锁也一样要递增一个数字
smp_wmb();
}
static __always_inline unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret;
repeat:
ret = sl->sequence; //在读之前，先取得这个数字
smp_rmb();
if (unlikely(ret & 1)) { //确保没有在写中
cpu_relax();
goto repeat;
}
return ret;
}
static __always_inline int read_seqretry(const seqlock_t *sl, unsigned start)
{
smp_rmb();
return (sl->sequence != start); //判断这个数字是否改变
}
最 后一类锁就是经典的RCU锁，这个锁我就不说那么多了，前面写过两篇文章说明这个锁。RCU锁基本没有利用什么锁，可是除了真正的锁之外，其它的特性它都 用到了，比如RCU用到的就是cpu调度的周期，因为RCU确信自己不会破坏自己，只有别人可能破坏自己，如果不想自己被破坏，那么就不让别人运行，于是 传统的RCU锁就是禁用抢占，而最新的RCU锁允许了抢占，但是Rcu的机制保护着rcu应该保护的数据。
