• 临界区和竞争条件
• 如何保护临界区？--加锁
  • 造成并发执行的原因
  • 锁要保护什么？
  • 配置选项：SMP、UP
• 死锁
• 争用和扩展性
• 小结

这部分讲操作系统内核中的并发和同步问题。

为什么需要同步？
因为计算机中很多共享的资源有限，如共享内存，在同一时间被多个执行并发访问的话，有可能发生各个线程间相互覆盖共享数据的情况，造成访问数据处于不一致状态，从而造成系统不稳定的隐患，而且很难跟踪和调试。
而同步就是保护共享资源的手段，避免同一时刻共享资源被同时访问。

临界区和竞争条件

临界区（critical region）是访问和操作共享数据的代码段。多个线程并发访问同一个资源，通常是不安全的。
临界区应该原子地执行，避免并发访问。如果2个执行线程处于同一临界区，那么程序包含bug，我们称这种情况为竞争条件（race condition）。出现竞争条件机会很小，不容易复现，因此调试这种错误很难。

避免并发和防止竞争条件被称为同步（synchronization）。

1. 临界区为什么需要保护？
   临界区往往是访问共享数据的一段代码，如果不加以保护，多线程或多处理器访问时，很可能造成数据的不一致性，从而产生错误。

2. 单个变量为什么需要保护？
   高级语言的变量一个操作，很可能对应多个机器指令，多线程或多处理器访问时，同样容易造成数据的混乱。

[======]

如何保护临界区？--加锁

线程访问临界区时，先要获得锁，如果锁已经被其他线程取得，则当前线程阻塞，等待其他线程释放锁；如果锁没有被其他线程取得（或者已经释放），则当前线程直接取得锁。
线程访问完临界区后，要主动释放锁，唤醒等待该锁的线程。

锁的主要通过阻止其他线程并发访问，从而实现临界区保护。
锁的使用是自愿的、非强制的，属于编程者自选的编程手段。什么意思？
意思是你可以使用锁访问共享资源，也可以绕过锁访问共享资源，这并不是强制的。不过，绕过锁来访问，可能造成竞争。典型案例，文件锁。

造成并发执行的原因

用户空间需要同步，是因为用户程序会被调度程序抢占和重新调度。用户进程可能在任何时刻，被优先级更高的另外一个进程抢占。另外，多处理器也会造成多线程并发访问共享资源。

内核中也有类似可能造成并发执行的原因：

• 中断：几乎可以在任何时刻异步发生，打断当前正在执行的代码。 -- 中断，打断当前线程
• 软中断和tasklet：内核能在任何时刻唤醒或调度软中断和tasklet，打断当前正在执行的代码。-- 软中断，打断当前线程
• 内核抢占：因为内核具有抢占性，所以内核中的任务可能会被另一个抢占。 -- 进程调度，打断当前线程
• 睡眠及与用户空间的同步：在内核执行的进程可能会睡眠，这会唤醒调度程序，从而导致一个新用户进程执行。 -- 主动放弃导致进程重新调度
• 对称多处理：2个或多个处理器可以同时执行代码。-- 多处理器

中断安全代码（interrupt-saft）：在中断处理程序中能避免并发访问的安全代码。
SMP安全代码（SMP-safe）：在对称多处理的机器中能避免并发访问的安全代码。
抢占安全代码（preempt-safe）：在内核抢占时能避免并发访问的安全代码。

TIPS：在编码开始阶段，就要设计恰当的锁，而不是代码写好的后期再加锁。

锁要保护什么？

所有可能被代码并发访问的数据，都可能需要保护。
不需要保护的数据：

• 线程的局部数据：只有执行线程能访问，如自动变量，threadlocal（线程本地）变量。
• 特定进程访问的数据：进程一次只在一个处理器上执行，相当于单线程访问的数据，不需要加锁。

需要保护的数据：

• 大多数内核数据结构
• 其他执行线程可以访问的数据

加锁的对象是数据，而非代码。除了当前线程，什么东西能看到该数据，就锁住它。

配置选项：SMP、UP

Linux内核裁剪时，
CONFIG_SMP选项 => 控制内核是否支持SMP。单处理器可以不需要该选项。
CONFIG_PREEMPT选项 -> 控制是否允许内核抢占。

编写内核代码时，需要确认以下问题，并根据情况决定是否需要支持加锁：

• 该数据是否全局？除当前线程外，其他线程能不能访问？
• 该数据会不会在进程上下文和中断上下文共享？它是不是要在两个不同的中断处理程序中共享？
• 进程在访问数据时，可不可能被抢占？被调度的新进程会不会访问同一数据？
• 当前进程是不是会阻塞在某些资源上，如果是，它会让共享数据处于何种状态？
• 怎样防止数据失控？
• 如果这个函数又在另一个处理器上被调度，将会发生什么？
• 你要对这些代码做什么？

[======]

死锁

死锁产生条件：所有线程循环占用且等待资源。

最简单的死锁例子是自死锁：一个线程试图获取一个自己已经持有的锁。这个锁永远没机会释放，因为线程忙等着锁被释放，最终形成死锁。当然，前提是该锁是非递归锁。
逻辑示意：

线程A
获得锁
再次试图获得锁
等待锁重新可用
... /* 持有锁，但又无限循环等待锁 */

另一个常见例子是ABBA死锁：两个线程和两把锁，相互占有对方所需要的锁，又都等待对方释放锁。

线程1          线程2
获得锁A        获得锁B
试图获得锁B    试图获得锁A
等待锁B        等待锁A

预防死锁简单规则：
1）加锁顺序很关键，用嵌套的锁时，使用相同顺序获取锁。获取锁的顺序要和释放锁的顺序相反。
2）防止发生饥饿，试问，这个代码的执行是否一定会结束？如果某件事不发生，另外一件事要一直等下去吗？
3）不要重复请求同一个锁。
4）力求简单加锁方案 ---- 越复杂的锁方案越有可能造成死锁。

规则1很重要，特别是多个锁在同一时间被请求，那么以后其他函数请求它们也必须按前次的加锁顺序进行。否则，很有可能造成死锁。这是因为任何一个线程都不会放弃自己已持有的锁，如果不同线程持有锁的顺序不同，可能造成循环相互等待的死锁问题。

[======]

争用和扩展性

锁的争用（lock contention），简称争用：指当锁正在被占用时，有其他线程试图获取该锁。
一个锁处于高度争用状态，是指有多个线程在等待该锁。这种状态会导致系统性能降低。

扩展性（scalability）：是对系统可扩展程度的一个度量。对于OS，谈及可扩展性时会和大量的进程、处理器，或大量的内存等联系起来。
提供可扩展性可以提供Linux在更大型、处理能力更强的系统上的性能。但一味提高可扩展性，却会导致Linux在小型SMP和UP机器上的性能降低，因为小型机可能用不到特别精细的锁，过细的锁只会增加设计复杂度，以及运行开销。

[======]

小结

1）编写SMP安全代码，不要等到编码完成后才加锁，而应该在编码初期。
2）恰当的加锁，既要满足不死锁、一定可扩展性，而且还有清晰、简洁，整个编码过程可能需要不断完善。
3）无论编写哪种内核代码，系统调用 or 驱动，首先应该考虑保护数据不被并发访问。