Chapter 10 - 内核同步方法

Created by : Mr Dk.

2019 / 10 / 26 15:57

Nanjing, Jiangsu, China

10.1 原子操作

保证指令以原子的方式执行，两个原子操作绝不可能并发访问同一个变量。内核提供了两组原子操作接口：

  • 一组对整数进行操作
  • 一组对位进行操作

在 Linux 支持的所有体系结构上都实现了这两种接口，大多数体系结构提供了原子操作的指令。部分体系结构没有这样的指令，但为单步执行提供了锁内存总线的指令。

10.1.1 原子整数操作

针对整数的操作只能对 atomic_t 类型的数据进行处理

  • 确保原子操作只用这种数据类型
  • 保证该类型不会被传递给任何非原子函数
  • 确保编译器不对相应值的访问进行优化，原子操作最终接收到正确的内存地址，不是别名
typedef struct {
    volatile int counter;
} atomic_t;

有些体系结构会提供一些独有的额外原子操作方法，但所有体系结构都能保证一个最小集合：

atomic_t u = ATOMIC_INIT(0);

atomic_set(&v, 4);
atomic_add(2, &v);
atomic_inc(&v);
printk("%d\n", atomic_read(&v));

原子操作通常是内联函数，通过内嵌汇编指令实现。能使用原子操作时，就尽量不要使用复杂的加锁机制。

10.1.2 64 位原子操作

功能与 32-bit 无异，使用方法完全相同。为了在 Linux 支持的体系结构之间移植代码，应该使用 32-bit 的 atomic_t 类型。

10.1.3 原子位操作

内核提供针对位进行操作的原子函数，实现与体系结构相关。没有特殊的数据类型，只要指针指向了任何希望的数据，就可以进行操作。为了方便，内核还提供了一组与上述操作对应的非原子位函数：

  • 不保证原子性
  • 名字前缀多两个下划线
  • 非原子函数执行得更快些

10.2 自旋锁

Linux 中最常见的锁：自旋锁 (spin lock)。自旋锁最多只能被一个可执行线程持有，如果试图获得一个已被持有的锁，就要进行忙循环-旋转-等待锁可用。当锁未被持有，则可以立即得到它。自旋锁能够防止多于一个执行线程同时进入临界区。

自旋锁相当于坐在门外等同伴从里面出来，并把钥匙交给你。如果里面没人，则可以直接拿到钥匙进入；如果里面有人，则需要不断检查房间是否为空。

一个被争用的自旋锁使得请求它的线程在等待锁重新可用时 自旋，很浪费 CPU 时间。因此自旋锁不应当被长时间持有，适合短时间内的轻量级加锁。可以让请求锁的线程休眠，锁可用时再重新唤醒，这样带来上下文切换的代价——如果持有锁的时间不会太长，则使用自旋锁更好。信号量 是使请求线程进入睡眠的锁机制，而不是旋转。

10.2.1 自旋锁方法

自旋锁的实现和体系结构密切相关，通常通过汇编实现：

DEFINE_SPINLOCK(my_lock);
spin_lock(&mr_lock);
// 临界区
spin_unlock(&mr_lock);

注意：自旋锁不可递归。如果一个线程试图得到一个正在持有的锁，则会永远自旋，从而发生死锁。自旋锁可以用在中断处理程序中，但是需要在获取锁之前，关闭本地中断。不然，另一个中断可能会打断正持有锁的内核代码，如果后一个中断处理程序也请求这个锁，则发生了双重请求死锁。

禁止中断同时请求锁的接口：保存当前中断状态，禁止本地中断，获得锁。

DEFINE_SPINLOCK(mr_lock);
unsigned long flags;

spin_lock_irqsave(&mr_lock, flags);
// 临界区
spin_unlock_irqrestore(&mr_lock, flags);

使用锁的原则：

  • 保护数据而不是代码
  • 针对代码加锁会使程序难以理解
  • 操作数据前，首先占用恰当的锁，完成后再释放

10.2.2 其它针对自旋锁的操作

可以使用 spin_lock_init() 函数动态创建自旋锁。spin_try_lock() 试图获得某个特定的自旋锁，相当于测试锁的状态，立刻返回：只做判断，并不实际占用。

10.2.3 自旋锁和下半部

  • 由于下半部可以抢占进程上下文，在进程上下文中加锁时，要禁止下半部的执行
  • 由于中断处理程序可以抢占下半部，在下半部中加锁时，要禁止中断

10.3 读 - 写自旋锁

在进行写入操作时，不能有其它代码并发 写入 或 读取 数据——写操作要求完全互斥；而读取时，只要其它代码不进行写入，就是安全的——没有写操作时，多个并发读操作是安全的。

DEFINE_RWLOCK(mr_rwlock);

read_lock(&mr_rwlock);
// 只读临界区
read_unlock(&mr_rwlock);

write_lock(&mr_rwlock);
// 读写临界区
write_unlock(&mr_rwlock);

不能把读锁升级为写锁，因为写锁会不断自旋，等待所有读者释放锁，其中包括等待自身。多个读者可以安全地获得同一个读锁。线程递归获得同一个读锁也是安全的。显然，这种锁照顾读比照顾写更多，读锁被持有时，写操作为了互斥只能等待，但读者可以继续占用锁，写者在所有读者释放锁之前是无法获得锁的，大量读者会使写者处于饥饿状态。总结，自旋锁提供了一种简单快速的锁实现：

  • 加锁时间不长
  • 代码不会睡眠

10.4 信号量

Linux 中的信号量是一种睡眠锁。如果任务试图获得一个已被占用的信号量，信号量会将其推进一个等待队列，然后让其睡眠。当信号量被释放后，处于等待队列中的任务将被唤醒，并获得信号量

与刚才类似的例子。某个到了房间门口，抓到钥匙进入房间。另一个人到了门口，发现房间有人。他不会傻等，而是将自己登记到一个列表中，然后去打盹了。房间里的人出来后，在门口查一下列表。如果有名字，就去把他叫醒，让他进入房间。

这种方式相比自旋锁，有更好的 CPU 利用率，但是信号量比自旋锁的开销更大，适用于锁会被长时间持有的情况。锁被短时间持有时，睡眠、维护等待队列、唤醒的开销可能比占用锁的时间还长。中断上下文中不进行调度，所以不能用信号量。可以在持有信号量的前提下睡眠，但占用信号量的同时不能占用自旋锁，因为你可能就睡了。

10.4.1 计数信号量和二值信号量

信号量的一个有用的特性：

  • 允许任意数量的锁持有者 (在声明时指定)
  • 自旋锁在一个时刻最多允许一个任务持有

当信号量只允许一个锁持有者，那么就和自旋锁类似了。这种信号量称为 二值信号量 或 互斥信号量，否则就称为 计数信号量。计数信号量不能用于强制互斥。信号量在 1968 年由 Edsger Wybe Dijkstra 提出，支持两个原子操作，操作名称来自荷兰语：

  • P() - Proberen (探查 / 测试)，相当于获取信号量，计数器减 1
  • V() - Vershogen (增加)，相当于释放信号量，计数器加 1

10.4.2 创建和初始化信号量

信号量的实现和体系结构相关：

struct semaphore name;
sema_init(&name, count); // 信号量的使用数量

10.4.3 使用信号量

down_interruptible() 试图获得信号量。如果不可用，则将进程设置为 TASK_INTERRUPTIBLE 并进入睡眠。down() 函数则将进程设置为 TASK_UNINTERRUPTIBLE 并睡眠。区别在于进程在休眠时是否会被信号唤醒。也可以用 down_trylock() 函数以堵塞方式获取信号量

  • 被占用时，立刻返回非 0 值
  • 否则，返回 0，且立刻成功持有信号量锁

10.5 读 - 写信号量

与之前的读 - 写自旋锁类似，所有的读 - 写信号量都是互斥信号量。

  • 引用计数为 1
  • 只对写者互斥
  • 只要没有写者，并发持有读锁的读者数不限
  • 只有唯一的写者可以获得写锁

所有读 - 写锁的睡眠都不会被信号打断，即只有一个版本的 down() 操作：

static DECLARE_RWSEM(mr_rwsem);

down_read(&mr_rwsem);
// 临界区 (只读)
up_read(&mr_rwsem);

down_write(&mr_rwsem);
// 临界区 (读写)
up_write(&mr_rwsem);

与读 - 写自旋锁类似，如果代码中读和写可以明白无误地分割开来，否则最好不要使用。

10.6 互斥体

信号量的用途较为通用，使得信号量适合那些较复杂的互斥访问。为了找到一个更简单的睡眠锁，内核开发者引入了互斥体 (mutex)，特指任何可以睡眠的强制互斥锁，比如计数为 1 的信号量。mutex 在内核中对应数据结构 mutex，行为和计数为 1 的信号量类似，相当于一个简化版的、不管理计数的信号量。但操作更简单，实现更高效，使用限制更强。

DEFINE_MUTEX(name);
mutex_init(&mutex);

mutex_lock(&mutex);
// 临界区
mutex_unlock(&mutex);

mutex 仅实现了 Dijkstra 设计初衷中的最基本行为：

  • 任何时刻只有一个任务可以持有 mutex
  • 给 mutex 上锁的人必须负责给其解锁
  • 递归上锁和解锁是不允许的
  • 持有 mutex 时，进程不可以退出
  • mutex 不能在中断或下半部中使用
  • mutex 只能用官方 API 管理，不能拷贝、手动初始化、重复初始化

一般来说优先选用 mutex，再考虑信号量。

10.7 完成变量

内核中的一个任务发出信号通知另一个任务发生了特定事件，使用完成变量 (completion variable) 是使两个任务得以同步的简单方法：

  • 一个任务在完成变量上等待
  • 另一个任务在完成工作后，使用完成变量唤醒在等待的任务

10.8 BLK：大内核锁

10.9 顺序锁

通常简称 seq 锁，是 2.6 版本内核中新引入的。这种锁依靠计数器，当写操作发生时，获得一个锁，并且序列值增加，释放时会序列值变为偶数。在读取数据前后，序列号都被读取

  • 如果序列值相同，说明没有被写操作打断
  • 如果读取的值是偶数，则表明写操作没有发生

当有多个读者和少数写者共享一把锁时，seq 对于写者更有利——只要没有其它写者，写锁总能被成功获得，因此不会引起写者饥饿。使用 seq 锁最有说服力的是 jeffies。

10.10 禁止抢占

内核抢占代码使用自旋锁作为非抢占区域的标记。如果一个自旋锁被持有，内核便不能进行抢占。内核抢占和 SMP 面对相同的并发问题。

10.11 顺序和屏障

没咋看懂... 😥

Summary

大致弄明白了几种锁的机制和区别。