Linux中的race condition方案

什么时候需要解决race condition问题

名词

常用的几种方法

信号量和互斥锁

LDD3: Chapter 5: Concurrency and Race Conditions 中说得很清楚： 

Semaphores are a well-understood concept in computer science. At its core, a sema-
phore is a single integer value combined with a pair of functions that are typically
called P and V. A process wishing to enter a critical section will call P on the relevant
semaphore; if the semaphore’s value is greater than zero, that value is decremented
by one and the process continues. If, instead, the semaphore’s value is 0 (or less), the
process must wait until somebody else releases the semaphore. Unlocking a sema-
phore is accomplished by calling V; this function increments the value of the sema-
phore and, if necessary, wakes up processes that are waiting.

When semaphores are used for mutual exclusion—keeping multiple processes from
running within a critical section simultaneously—their value will be initially set to 1 .
Such a semaphore can be held only by a single process or thread at any given time. A
semaphore used in this mode is sometimes called a mutex, which is, of course, an
abbreviation for “mutual exclusion.” Almost all semaphores found in the Linux ker-
nel are used for mutual exclusion.

读写信号量

正如 读写锁 一节讲的，内核中也有读写信号量 struct rw_semaphore。

Completions

有这类情况：线程A需要等待线程B执行后，才往下执行。使用信号量完全可以实 现上述情形的同步。不过，这种情况下使用信号量又感觉性能上不太好。因为此 时线程A可以确定一定会在信号量上等待，直到线程B执行完后释放信号量。

于是内核引入了Completions。它就是简直的让一个线程告诉另一个线程，事情搞 定了。

Completion是一次性的，用完就完了。如果需要再用，就需要重新初始化一下。

Spinlocks（自旋锁？）

自旋锁的意思是，线程A首先拿到这个锁，然后执行。线程B拿不到这个锁时，就 在那儿等（自旋一会儿），还是占着cpu的（如果是信号量的话，可能它们这时 候就不占用cpu，可以sleep啦。）。注意这里A和B是在不同的cpu上执行的。等A 执行完后，B马上就可以执行。

一般情况下，自旋锁是效率比信号量高，因为一般被锁住的资源会很快被释放的。 但是它也有限制条件。

  1. 获得自旋锁后的操作，一般来说需要是原子操作，它们不能sleep。也就是 说不能在获得了自旋锁后，又放弃了cpu。如果出现这种情况，别的程序来获取 自旋锁时，永远都会“自旋”啦。但是可能导致sleep的操作很多，比如 copy_to_user，kmalloc等等。在使用自旋锁的时候，需要很小心。
  2. 自旋锁的代码中已经处理了抢断。在程序获得了自旋锁后，在执行该程序的 cpu上，抢断会被关闭。使得此时该程序在获得自旋锁后可以一直占着该cpu。
  3. 自旋锁还有接口，可以在获得自旋锁前，关闭该cpu上的中断。目的也是使 得此时该程序在获得自旋锁后可以一直占着该cpu
  4. 还有一个原则是，自旋锁应该尽可能少得的被占用。因为占用时间越多，可 能等待的线程就越多。浪费的cpu也就越多。

总的来说，自旋锁可以在支持抢断式的单核，或者多核系统上使用。在不支持抢 断式的单核设备上不能使用自旋锁。维基百科是这样说的： 

显然，单核CPU不适于使用自旋锁，这里的单核CPU指的是单核单线程的CPU，因为，在同一时间只有一个线程是处在运行状态，假设运行线程A发现无法获取锁，只能等待解锁，但因为A自身不挂起，所以那个持有锁的线程B没有办法进入运行状态，只能等到操作系统分给A的时间片用完，才能有机会被调度。这种情况下使用自旋锁的代价很高。

自旋锁之前有一个问题，如果核很多，同时等待临界资源的线程也很多，最坏的 情况下，有一个线程总是得不到资源，需要等待很久。于是后面有人给自旋锁加 入了排队机制： Linux 内核的排队自旋锁(FIFO Ticket Spinlock)

问题：一般的锁，如果锁不住，会把cpu还给内核让它调度后面的线程吗？我现在理解应该是会的。

Linux Device Drivers, Third Edition 上说得很清楚： 

an atomic context is simply a state where multiple steps must be
performed without any sort of concurrent access. What that means, with
regard to sleeping, is that your driver cannot sleep while holding a
spinlock, seqlock, or RCU lock. You also cannot sleep if you have
disabled interrupts. It is legal to sleep while holding a semaphore,
but you should look very carefully at any code that does so. If code
sleeps while holding a sema- phore, any other thread waiting for that
semaphore also sleeps. So any sleeps that happen while holding
semaphores should be short, and you should convince your- self that,
by holding the semaphore, you are not blocking the process that will
even- tually wake you up.
在得到一个信号量后，是可以sleep的，也就是放弃cpu。其它等待该信号量的线 程也会sleep。其它比如自旋锁，是不行的。

读写自旋锁

和 读写信号量 一样，也有读写自旋锁。

读写锁

临界资源，有多个读和一个写时，这是比较有用的。没有写的线程时，多个读可 以同时进行。有写的线程时，读和写都必须等待。

条件变量 （这个是不是就是上面的信号量？）

在《UNIX环境高级编程》一书中，条件变量就是对应的P,V操作吧。一个线程V出 来一个资源，就可以唤醒一个等待的线程来P它。条件变量和互斥锁一起使用， 可以实现线程间的同步。

无锁算法

可以通过一些设计优良的算法来避免使用锁。比如 circular buffer（循环队 列）。它用于生产消费模型，不过只有一个reader和一个writer。writer不停得 往队尾写数据，reader不停地从队首读数据。仔细编写地话，这样的一个模型就可以不用锁。

原子操作

原子操作是意思是把对临界资源的操作全部放入api接口内部实现，这样就不需 要加锁了。Linux实现方式依赖于平台，每个平台都不一样，有些平台是直接用 汇编语言实现的，有些平台则是通过关中断的方法来实现的（如何通过关中断来实现这里我不太清楚）。

当需要保护的数据比较少的时候，使用原子操作是比较好的。一般情况下，就是 一些整型数等等。原子操作提供了一些比如加1减1，读取等的简单接口。

位操作

我理解位操作（读，写）都可以直接只由一条机器指令执行。所以就不存在race condition？如果是多核也不存在吗？

使用位操作，可以实现自旋锁，比如： 

/* try to set lock */
while (test_and_set_bit(nr, addr) != 0)
wait_for_a_while( );
/* do your work */
/* release lock, and check... */
if (test_and_clear_bit(nr, addr) = = 0)
something_went_wrong( ); /* already released: error */

seqlocks

这个比较好玩。读的线程read不管三七二十一直接先读数据，读完后，看这个数 据在它读的时候是否被writer动过，如果动过，丢弃当前读的重新再读一次。看 起来像这样： 

unsigned int seq;
do {
seq = read_seqbegin(&the_lock);
/* Do what you need to do */
} while read_seqretry(&the_lock, seq);

其中，seq就是来查看是否数据被writer动过的。seqlock的read还有关中断的接 口。writer写的时候需要拿一个锁－－自旋锁。所以自旋锁相关的限制对它也有。

seqlock一般锁的是简单，比较一致的数据。 它不能锁有指针的数据。 因为如果writer正在修改数据，谁也不知道reader读出来的指针是指向哪里的。

Read-Copy-Update

  1. 用在读很常见，写少见的情况。
  2. reader除了关闭抢断，啥也不管，读就是了，不过在读的操作，必须是原子 的。
  3. 数据全是通过指针访问。
  4. 申请新的空间，把旧的指针拷贝过来。
  5. 在新申请的空间中更新指针。这个时候，新的reader就直接访问新申请的空间的指针了。
  6. writer还需要等所有访问old数据的reader访问完成后，释放old数据。

参考资料

  1. Anatomy of Linux synchronization methods

  2. 维基百科： 自旋锁

  3. Linux 内核的排队自旋锁(FIFO Ticket Spinlock)

  4. TODO: Ticket spinlocks

如果你觉得本文不错，欢迎 donate