Linux内核学习——同步与并发

    多CPU（SMP，Symmetric multiprocessors）同时访问共享资源称为并发。在单个CPU上的多个进程也能访问共享资源，因为做不到像SMP那样的同时访问，所以称为伪并发。

多线程/多CPU并发访问共享资源往往是不安全的，这种情况称为竞争，防止竞争的操作称为同步。同步的目的是让对共享数据的操作做到原子化（atomic），也就是不可分割的。

 

• 竞争遇险

竞争遇险的例子1：

一个人去ATM机提款100元，同时银行也在操作这张***，比如扣款10元。两者对***里的金额操作流程是相同的：

判断扣款数额是否足够

扣除款项（吐钞、或者转账）

更新卡内余额

若卡内原有105元，在“扣除10元”的时候被“扣除100元”打断，那么尽管“扣除100元”之后的更新使得卡内余额为5元，但是再经过“扣除10元”之后的更新，卡内余额就变成了95元，这样就会凭空多了很多钱。

 

竞争遇险的例子2：

两个线程都对全局变量i进程操作：i++

理想的情况是：

但如果线程的操作不是原子的，结果就会不一样：

所以，对共享数据的操作要做到原子的：

像i++这种操作，系统本身就提供了能够做到原子化操作的指令，但是对于复杂的操作，就难以做到原子化了，这是因为：

中断，难以预料什么时候会发生

softirq、tasklet，同样难以预料

内核抢占，2.6之后内核就是可抢占的，所以即使是内核代码，也可能会被调度

sleep，发生调度就意味着其他process运行，而其他process的运行就有可能会访问共享资源

多CPU，多CPU同时访问共享资源

于是要引入锁（lock）的概念，锁让共享数据受到保护，同一时间只有一个操作者，没有并发也就没有竞争了。这就好比共享数据是一件房间，一个process若要进入这个房间，就需要获得lock，若是房间没锁上，该process就获得锁（相当于锁上房间）；若是房间已锁上，该process就只能等待。当然对lock的获取与释放也是要原子化操作的！

关键在于需要明确什么样的资源是需要保护的，一般都是全局变量，其实只要多个process都能访问到的资源，都需要保护的。

 

• 死锁

通常发生死锁的情况有：

一个线程重复的获取同一个lock

线程互相获取lock，但是都获取不到

获取多个lock的顺序不一致

优先级低的线程获取了lock，优先级高的又试图获取。比如一个线程获取了lock，然后发生了中断，中断处理程序中又试图去获取这个lock，线程中的lock释放不了，中断处理程序又在一直等待，所以发生了死锁。

 

• 同步

原子整数操作

atomic_t v;                      /* define v */

atomic_t u = ATOMIC_INIT(0);     /* define u and initialize it to zero */

atomic_set(&v, 4);               /* v = 4 (atomically) */

atomic_add(2, &v);               /* v = v + 2 = 6 (atomically) */

atomic_inc(&v);                  /* v = v + 1 = 7 (atomically) */

printk(“%d\n”, atomic_read(&v));   /* will print “7” */

 

原子bit操作

set_bit(0, &word);       /* bit zero is now set (atomically) */

set_bit(1, &word);       /* bit one is now set (atomically) */

clear_bit(1, &word);     /* bit one is now unset (atomically) */

change_bit(0, &word);    /* bit zero is flipped; now it is unset (atomically) */

 

Spin Locks

Spin lock防多CPU（通过lock）；在单CPU的情况下，spin lock防抢占（禁用preempt）；在单CPU且内核不启用抢占的情况下，spin lock为空语句。

也就是说，在支持内核抢占的情况下，如果一个内核线程获得了spin lock，它一定是执行完了critical region（获取和释放锁之间的代码区域）之后，系统才会发生调度（因为spin lock禁用了内核抢占）。所以获取spin lock的critical region一定要快速完成，因为这个影响了内核调度的latency！

一个进程获取了spin lock之后，不能调用任何可能造成sleep的语句，因为这可能会使得其他进程长时间的忙等。

DEFINE_SPINLOCK(mr_lock);

spin_lock(&mr_lock);

/* critical region ... */

spin_unlock(&mr_lock);

如果一个内核线程和ISR共享资源，那在通过lock进行同步之前，线程中要禁用中断，否则会发生上述第四种死锁的情况

DEFINE_SPINLOCK(mr_lock);

unsigned long flags;

spin_lock_irqsave(&mr_lock, flags); //防SMP、防抢占、防Interrupt

/* critical region ... */

spin_unlock_irqrestore(&mr_lock, flags);

如果一个内核线程和下半部共享资源，那也要禁用下半部：spin_lock_bh，该语句没有禁用中断。

如果下半部之间共享资源，则使用普通的spin lock就可以了，因为下半部不会互相抢占。

会不会一个线程获得spin lock（没有禁用中断），然后发生interrupt，interrupt返回到高优先级的线程？不会吧，因为禁用了抢占，interrupt返回也是返回到原来的线程。

 

读写spin lock

对于读来说，只要没有写，就可以获得lock；对于写来说，要没有其它写，也没有读，才可以获得lock。好处是允许多个读者共同获得lock。

read_lock(&mr_rwlock);

/* critical section (read only) ... */

read_unlock(&mr_rwlock);

write_lock(&mr_rwlock);

/* critical section (read and write) ... */

write_unlock(&mr_lock);

 

Semaphores

与spin lock的一个本质区别是，若是获取不到lock（semaphore），线程会sleep，而spin lock中，线程只是忙等。所以semaphores比spin lock的设计更为复杂，它需要维护一个等待队列，当semaphores被释放时，唤醒等待队列上的一个进程。

Semaphores是用在需要sleep的场合，即获取了semaphore的进程可以调用会导致sleep的语句，比如copy_from_user、某些kmalloc等。而spin lock是不应该sleep的，获取了spin_lock的进程不应该调用可能会导致sleep的语句，因为若是该进程sleep了，可能会造成其他线程为了获取spin_lock而长时间的忙等。

Semaphore允许多个lock holder（counter计数），而spin_lock只有一个lock holder。当semaphore设置为只允许一个lock holder时称为mutux。下述down/up操作都是针对counter进行的。

down()是uninterruptible，也就是不能被signal中断，不能被杀死，在“ps”命令中显示“D”（dreadful）的。与之相对应的是down_interruptible()，它可以被signal打断，所以要检查返回值：

if (down_interruptible(&dev->sem))        //semaphore放在驱动设备的结构体中

return -ERESTARTSYS;

对上述代码的说明为：执行该代码的进程试图获得一个semaphore，若获得了semaphore，返回0；若没有获得semaphore，不返回，因为该进程sleep了（被挂起）；若返回非0，说明该进程在sleep的时候收到了signal。

另外，内核也提供读写的semaphore。

 

Mutexes

互斥量（mutexe）是轻量级的信号量（semaphore），因为counter最大是1。

mutex_lock(&mutex);

/* critical region ... */

mutex_unlock(&mutex);

与spin lock的比较

QUESTION：为什么初始化要分runtime和complie？static不static区域的差别？

 

Completion Variables

用于一个线程通知另一个线程某个事件已经发生。

 

Sequential Locks

写总是可以获得lock，读若发现写正在进行，则looping。

数据结构为seqlock_t。

应用例子为jiffies。

 

Preemption Disabling

Spin lock是禁用抢占的，即若是某线程获得spin lock，它一定不会被抢占。

 

Ordering and Barriers

 

 

• 锁的替代方法

除了一开始说的atomic指令可以避免锁的使用以外，还有一些其他办法：

循环缓冲区

循环缓冲区（circular buffer），是一种数据结构，它可以进行producer/consumer型的操作。循环缓冲区的实现简单，只需要一个数组，两个指针用于读和写。因为读写指针操作数据的两端，所以可以同时进行：

读写指针需要适当的控制：写指针不能等于读指针，读指针不能超过写指针。可以看一下内核中kfifo的实现（）

RCU

RCU(Read-copy-update)的原理是，若共享数据需要被更改（写），那么创建一份新的拷贝，写直接操作在新的拷贝上，之后的读也建立在新的的拷贝上，待原先的在旧数据上进行读操作完成后，释放旧的数据（因为RCU是原子的，一轮schedule之后，就可以释放旧数据），相关的函数为rcu_read_lock/unlock等。

 

总之，一定要注意：进程在拥有spinlock、seqlock、RCU lock等的情况是不能够sleep的（会造成其他进程的忙等，甚至死锁）。获取semaphore的进程虽然能够sleep，但是也要意识到，这也使得其它要获得该semaphore的进程sleep了。

PS：ULNI的第九章也讲了后半部与并发，而且讲的很详细！