深入理解 Linux 内核—内核同步

释放双眼,带上耳机,听听看~!

内核如何为不同的请求提供服务

把内核看作必须满足两种请求的侍者:一种来自中断,另一种来自用户态进程发出的系统调用或异常。前者的优先级更高。

侍者提供的服务对应于 CPU 处于内核态时所执行的代码。如果 CPU 在用户态执行,则认为侍者处于空闲状态。

内核抢占

如果进程正在执行内核函数时,即在内核态运行,允许发生内核切换,这个内核就是抢占的。

Linux 中的抢占类型

  • 计划性进程切换:无论在抢占内核还是非抢占内核中,运行在内核态的进程都可以自动放弃 CPU,比如等待资源。
  • 强制性进程切换:抢占式内核可响应引起进程切换的异步事件(如唤醒高优先权进程的中断处理程序)。
  • 所有的进程切换都由 switch_to 完成。

内核抢占的好处
使内核可抢占的目的是降低一个进程被另一个运行在内核态进程延迟的风险。

什么时候禁止抢占
当被 current_thread_info() 宏所引用的 thread_info 描述符的 preempt_count 字段大于 0 时,禁止内核抢占,存在以下情况:

  1. 内核正在执行中断服务例程。
  2. 可延迟函数被禁止(当内核正在执行软中断或 tasklet 时经常如此)。
  3. 将抢占计数器设置为正数,显示禁用内核抢占。

所以,只有当内核正在执行异常处理程序(尤其时系统调用),且内核抢占没有被显式禁用,才可抢占内核。

内核抢占相关的宏、函数
preempt_enable() 宏递减抢占计数器,检查 TIF_NEED_RESCHED 是否被设置。此时,进程切换请求是挂起的,因此调用
preempt_schedule() 函数:


1
2
3
4
5
6
7
8
1// 检查 preempt_count 是否为0,以及是否允许本地中断
2if(!current_thread_info->preempt_count && !irqs_disabled()){
3   current_thread_info->preempt_count = PREMPT_ACTIVE;
4   schedule();   // 选择另外一个进程运行
5   current_thread_info->preempt_count = 0;
6}
7
8

内核抢占的时机

  • 结束内核控制路径时(通常是一个中断处理程序)
  • 异常处理程序调用 preempt_enable() 重新允许内核抢占时。
  • 启用可延迟函数时。

Linux 2.6 允许用户在编译内核时通过设置选项决定是否使用内核抢占。

什么时候同步是必需的

当计算结果依赖于两个或两个以上的交叉内核控制路径的嵌套方式时,可能出现竞争条件。

临界区是一段代码,在其他的内核控制路径能进入临界区前,进入临界区的内核控制路径必须执行完这段代码。

什么时候同步是不必要的

  • 中断处理程序和 tasklet 不必编写成可重入的函数。
  • 仅被软中断和 tasklet 访问的 每 CPU 变量不需要同步。
  • 仅被一种 tasklet 访问发数据结构不需要同步。

同步原语

每 CPU 变量

每 CPU 变量,内核变量,每 CPU 变量是一个数组,系统中的每个 CPU 对应数组的一个元素。

一个 CPU 不应访问其他 CPU 对应的数组元素,另外,它可以随意修改它自己的元素而不用担心出现竞争条件。

虽然每 CPU 变量为来自不同 CPU 的并发访问提供包含,但对来自异步函数(中断处理程序和可延迟函数)的访问不提供保护,这需要另外的同步原语。

原子操作

原子操作:将操作一个单个指令执行,中间不能中断,且避免其他的 CPU 访问同一存储单元。

本地中断的禁止只适用于一个 CPU(系统中的其他 CPU 不受影响)。

原子操作的指令:inc、dec、操作码前缀是 lock 字节(0xf0)的汇编指令等。

优化和内存屏障

优化屏障原语保证编译程序不会混淆放在原语操作之前的汇编指令和放在原语操作之后的汇编语言指令。

Linux 中,优化屏障是 barrier() 宏,展开为 asm volatile("":::“memory”)。

  • volatile 禁止编译器把 asm 指令与程序中的其他指令重新组合。
  • memory 强制编译器假定 RAM 中的所有内存单元已经被汇编指令修改,因此,编译器不能使用存放在 CPU 寄存器中的内存单元的值来优化 asm 指令前的代码。

内存屏障原语确保在原语执行之后的操作执行之前,原语前的操作已经完成。

自旋锁

当内核控制路径必须访问共享数据结构或进入临界区时,就需要为自己获取一把“锁”。

自旋锁时用来在多处理器环境中工作的一种特殊的锁。如果内核控制路径发现锁被运行在另一个 CPU 上的内核控制路径 “锁着”,就会在周围”旋转“,反复执行一条紧凑的循环指令(”忙等“),直到锁被释放。

等待自旋锁释放的进程可能被更高优先级的进程替代。

spinlock_t

  • slock,自旋锁的状态,1:未加锁;<=0:加锁。
  • break_slock,进程正在忙等自旋锁。

具有内核抢占的 spin_lock 宏

  1. preempt_disable() 禁用内核抢占。

  2. _raw_spin_trylock() 对自旋锁的 slock 字段执行原子性的测试和设置操作。


1
2
3
4
1movb $0, %al
2xchgb %al, slp-&gt;slock  // xchg 原子性地交换 8 位寄存器 %al 和 slp-&gt;slock
3
4
  1. 如果自旋锁中的旧值是正数,宏结束:内核控制路径已经获得自旋锁。

  2. 否则,内核控制路径无法获得自旋锁,必须忙等。preempt_enable() 递减在第 1 步 递增了的抢占计数器。忙等期间可被其他进程抢占。

  3. 如果 break_lock 字段等于 0,则设置为 1。通过检测该字段,拥有锁且在别的 CPU 上运行的进程就能知道是否有其他进程在等待该锁。如果进程持有某个自旋锁的时间过长,该进程可提前释放锁。

  4. 执行等待循环:


1
2
3
4
1while(spin_is_locked(slp) &amp;&amp; slp-&gt;break_lock)
2   cpu_relax();  // 宏 cpu_relax() 简化为一条 pause 汇编指令
3
4
  1. 回到第 1 步,再次试图获取自旋锁。

非抢占式内核中的 spin_lock 宏
如果在内核编译时没有旋转内核抢占选项,spin_lock 宏本质上为:


1
2
3
4
5
6
7
8
9
11: lock; decb slp-&gt;slock  // decb 递减自旋锁的值,该指令是原子的,因为带有 lock 前缀
2   jns 3f  // 检测符号标志,如果被清 0,说明自旋锁被设置为 1(未锁),从 3 处继续执行,f:forward
32: pause   // 否则,在 2 处执行紧凑的循环,直到自旋锁出现正值
4   cmpb $0, slp-&gt;slock
5   jle 2b
6   jmp 1b  // 然后从 1 处重新执行,检查是否其他的处理器抢占了锁
73:
8
9

spin_unlock 宏


1
2
3
1movb $1, slp-&gt;slock
2
3

随后调用 preempt_enable()(如果不支持内核抢占,什么也不做)。

读/写自旋锁

是为了增加内核的并发能力。

  • 只有没有内核控制路径对数据结构修改,读/写自旋锁就允许多个内核控制路径同时读同一个数据结构。
  • 如果一个内核控制路径想对数据结构进行写操作,必须首先获得读/写锁的写锁,写锁授权独占访问这个资源。

读/写锁是一个 rwlock_t 结构,lock 字段是一个 32 位的字段,分两部分:

  • 0~23 位,计数器,对受保护的数据结构并发进行读操作的内核控制路径的数目。
  • 第 24 位,“未锁”标志字段,当没有内核控制路径在读或写时设置该位,否则清 0。

lock 值:

  • 0x01000000:自旋锁为空(设置了“未锁”标志,且无读者)。
  • 0x00000000:写者获得了自旋锁(“未锁”标志清 0,且无读者)。
  • 0x00ffffff,0x00fffffe 等:一个或多个读者获得了自旋锁(“未锁”标志清 0,读者个数的二进制补码在 0~23 位上)。

rwlock_t 结构也包括 break_lock 字段。

rwlock_init 宏把读/写自旋锁的 lock 字段初始化为 0x01000000(“未锁”),把 break_lock 初始化为 0。

读自旋锁

read_lock 宏,作用于读/写自旋锁的地址 rwlp,与 spin_lock 相似。如果编译内核时选择了内核抢占选项,read_lock 与 spin_lock 只有一点不同:执行 _raw_read_trylock() ,在第 2 步获得读/写自旋锁。


1
2
3
4
5
6
7
8
9
10
11
1int _raw_read_trylock(rwlock_t  *lock)
2{
3   atomic_t *count = (atomic_t *)lock-&gt;lock;
4   atomic_dec(count);
5   if(atomic_read(count) &gt;= 0)
6       return 1;
7   atomic_inc(count);
8   return 0;
9}
10
11

如果编译内核时没有选择内核抢占选项,read_lock 宏产生如下汇编代码


1
2
3
4
5
6
7
1   movl $rwlp-&gt;lock, %eax
2   lock; subl $1, (%eax)    // 将自旋锁原子减 1,增加读者个数
3   jns 1f                   // 如果递减操作结果非负,就获得自旋锁    
4   call __read_lock_failed  // 否则,调用 __read_lock_failed()
51:
6
7

1
2
3
4
5
6
7
8
9
10
11
1// 试图获取自旋锁
2__read_lock_failed:
3   lock; incl (%eax)   // 原子增加 lock 字段,以取消 read_lock 宏执行的递减操作
41:     pause  
5   cmpl $1, (%eax)     // 循环,直到 lock 字段 &gt;= 0
6   js 1b
7   lock; decl (%eax)
8   js __read_lock_failed
9   ret
10
11

read_unlock 释放读自旋锁


1
2
3
1lock; incl rwlp-&gt;lock    // 减少读者计数
2
3

然后调用 preempt_enable() 重新启用内核抢占。

写自旋锁

write_lock 宏与 spin_lock() 和 read_lock() 相似。如果支持内核抢占,则禁用内核抢占并调用 _raw_write_trylock() 获得锁。


1
2
3
4
5
6
7
8
9
10
1int _raw_write_trylock(rwlock_t *lock)
2{
3   atomic_t *count = (atomic_t *)lock-&gt;lock;
4   if(atomic_sub_and_test(0x01000000, count))  // 从读/写自旋锁中减去 0x01000000,清除未上锁标志并返回 1
5       return 1;
6   atomic_add(0x01000000, count);  // 原子地在自旋锁值上增加 0x0100000,以抵消减操作。
7   return 0;                       // 锁已经被占用,需重新启用内核抢占并开始忙等待
8}
9
10

write_unlock 宏,释放写锁


1
2
3
1lock; addl $0x0100000, rwlp  // 把 lock 字段中的“未锁”标识置位
2
3

再调用 preempt_enable()

顺序锁

顺序锁与读/写锁相似,只是为写者赋予了较高的优先级:读者读的时候允许写者运行。好处是写者永远不会等待(除非另一个写者在写),缺点是读者有时需多次读相同的数据直到获得有效的副本。

seqlock_t 包括两个字段:

  • 类型为 spinlock_t 的 lock 字段。
  • 整型的 sequence 字段,是一个顺序计数器。每个读者都必须在读数据前后两次读顺序计数器,如果两次读到的值不同,说明新的写者开始写并增加了顺序计数器,读取的数据无效。

初始化:将 SEQLOCK_UNLOCKED 赋给变量 seqlock_t,或执行 seqlock_init 宏,将 seqlock_t 初始化为”未上锁“。

write_seqlock():写者获取顺序锁。获取 seqlock_t 中的自旋锁,然后使顺序计数器加 1。

write_sequnlock():写者释放顺序锁。再次增加顺序计数器,然后释放自旋锁。可保证有写者写时,计数器值为奇数,没有写者时,计数器值是偶数。

读者执行下面临界区代码:


1
2
3
4
5
6
7
8
1unsigned int seq;
2do
3{
4   seq = read_seqbegin(&amp;seqlock);    // 返回顺序锁的当前序号。如果是奇数,或 seq 的值与顺序锁的顺序计数器值不匹配,read_deqretry() 返回 1
5   /* ... 临界区 ... */
6}while(read_deqretry(&amp;seqlock, seq));
7
8

读者进入临界区,不必禁用内核抢占。由于写者获取自旋锁,它进入临界区时自动禁用内核抢占。

使用顺序锁的条件

  • 被保护的数据结构不包括被写者修改和被读者间接引用的指针。
  • 读者的临界区代码没有副作用。

另外:

  • 读者的临界区代码应该简短。
  • 写者不应常获取顺序锁。

典型例子:保护与系统时间处理相关的数据结构。

读-拷贝-更新(RCU)

是为了保护在多数情况下被多个 CPU 读的数据结构而设计的一种同步技术。

RCU 允许多个读者和写者并发执行,且不使用锁,相比读/写自旋锁、顺序锁有更大的优势。

通过限制 RCP 的范围,可不使用共享数据结构而实现多个 CPU 同步:

  • RCU 只包含被动态分配并通过引用指针引用的数据结构。
  • 在被 RCU 保护的临界区中,任何内核控制路径不能睡眠。

内核控制路径读取被 RCU 保护的数据结构流程

  1. rcu_read_lock() 等同于 preempt_disable()。
  2. 读者间接引用该数据结构指针所对应的内存单元,并开始读该数据结构。读者在完成读操作前,不能睡眠。
  3. rcu_read_unlock() 等同于 preempt_enable(),标记临界区的结束。

内核控制路径写被 RCU 保护的数据结构

需要做一些事情防止竞争条件的出现。

  • 写者要更新数据结构时,间接引用指针并生成整个数据结构的副本。
  • 写者修改该副本。
  • 修改完毕,写者改变指向数据结构的指针,使其指向被修改后的副本。修改指针的操作是一个原子操作。需要内存屏障保证:只有数结构被修改后,已更新的指针对其他 CPU 才是可见的。如果把自旋锁与 RCU 结合以禁止写者的并发执行,就隐含地引入了内存屏障。

使用 RCU 技术的困难:写者修改指针时不能立即释放数据结构的旧副本。只有 CPU 上所有的读者都执行完宏 rcu_read_unlock() 后,才能释放旧副本。

内核要求每个读者在执行以下操作前执行 rcu_read_unlock() 宏:

  • CPU 执行进程切换。
  • CPU 开始在用户态执行。
  • CPU 执行空循环。

对于以上任何情况中,认为 CPU 经过了静止状态。

call_rcu() 写者释放数据结构的旧副本。

  • 将 rcu_head 描述符的地址和将要调用的回调函数地址作为参数。
  • 把回调函数和其参数的地址存放在 rcu_head 描述符中,然后把描述符插入回调函数的每 CPU 链表中,内核每经过一个时钟滴答检查本地 CPU 是否经历了一个静止状态。
  • 如果所有 CPU 都经历了静止状态,本地 tasklet 执行链表中的所有回调函数。

信号量

实现了一个加锁原语,即让等待者睡眠,直到等待的资源变为空闲。

Linux 提供两种信号量:

  • 内核信号量,由内核控制路径使用。
  • System V IPC 信号量,由用户态进程使用。

内核控制路径试图获取内核信号量保护的资源时,会被挂起,直到资源被释放。因此,只有可睡眠的函数才能获取内核信号量,中断处理程序和可延迟函数不能使用内核信号量。

内核信号量数据结构:struct semaphore,包含的字段:

  • count,存放 atomic_t 类型的值。> 0,资源空闲;= 0,信号量忙,但没有进程等待;< 0,资源不可用,至少一个进程等待资源。
  • wait,存放等待队列链表的地址。
  • sleepers,标志,表示是否有一些进程在信号量上睡眠。

初始化信号量的几种情形

  • init_MUTEX() 将 count 字段设置为 1(资源空闲)
  • init_MUTEX_LOCKED() 将 count 字段设置为 0。
  • 宏 DECLARE_MUTEX 和 DECLARE_MUTEX_LOCKED 完成同样的功能,也静态分配 semaphore 结构的变量。
  • 将 count 初始化为任意的正整数 n 时,最多有 n 个进程可以并发地访问该资源。

释放信号量

释放内核信号量时,调用 up() 函数,等价于:


1
2
3
4
5
6
7
8
9
10
11
12
1   movl $sem-&gt;count, %ecx  
2   lock; incl (%ecx)   // 增加 *sem 信号量 count 字段的值
3   jg 1f  // 如果大于 0,说明没有进程在等待队列上睡眠,什么也不做,否则,调用 __up() 唤醒睡眠的进程
4   lea %ecx, %eax
5   pushl %edx
6   pushl %ecx
7   call __up   // 从 eax 寄存器接收参数
8   popl %ecx
9   popl %edx
101:
11
12

1
2
3
4
5
6
1__attribute_((regparm(3))) void __up(struct semaphore *sem)
2{
3   wake_up(&amp;sem-&gt;wait);
4}
5
6

获取信号量

调用 down() 函数,等价于:


1
2
3
4
5
6
7
8
9
10
11
12
13
1down:
2   movl $sem-&gt;count, %ecx
3   lock; decl (%ecx);  // 减少 *sem 信号量的 count 值
4   jns 1f              // 如果 count &gt;= 0,当前进程获得资源并继续正常执行
5   lea %ecx, %eax      // 否则,当前进程必须挂起,将一些寄存器内容压栈后,调用 __down()
6   pushl %edx
7   pushl %ecx
8   call __down
9   popl %ecx
10  popl %edx
111:
12
13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1// 挂起当前进程,直到信号量被释放
2__attribute__((regparam(3))) void __down(struct semaphore *sem)
3{
4   DECLARE_WAITQUEUE(wait, current);
5   unsigned long flags;
6   current-&gt;state = TASK_UNINTERRUPTIBLE;  // 将当前进程的状态从 TASK_RUNNGING 变为 TASK_UNINTERRUPTIBLE
7   spin_lock_irqsave(&amp;sem-&gt;wait.lock, flags);   // 在访问信号量数据结构的字段前,获得保护信号量等待队列自旋锁 sem-&gt;wait.lock,并禁止本地中断
8   add_wait_queue_exclusive_locked(&amp;sem-&gt;wait, &amp;wait);  // 将进程放入信号量的等待队列
9   sem-&gt;sleepers++;
10  for(;;)
11  {
12      if(!atomic_add_negative(sem-&gt;sleepers-1, &amp;sem-&gt;count))  // count -= 1
13      {
14          sem-&gt;sleepers = 0;   // 如果 count 字段 &gt;= 0,将 sleepers 置 0,表示没有进程在信号量等待队列上睡眠
15          break;
16      }
17
18      // 如果 count &lt; 0
19      sem-&gt;seleepers = 1;
20      spin_unlock_irqrestore(&amp;sem-&gt;wait.lock, flags);
21      schedule();               // 调用 schedule() 挂起当前进程
22      spin_lock_irqsave(&amp;sem-&gt;wait.lock, flags);
23      current-&gt;state = TASK_UNINTERRUPTTIBLE;
24  }
25  remove_wait_queue_locked(&amp;sem-&gt;wait, &amp;wait);
26  wake_up_locked(&amp;sem-&gt;wait);   // 试图唤醒信号量等待队列中的另一个进程,并终止保持的信号量
27  spin_unlock_irqrestore(&amp;sem-&gt;wait.lock, flags);
28  current-&gt;state = TASK_RUNNTING;
29}
30
31

down_trylock() 函数在资源繁忙时,立即返回,而不是让进程睡眠。

down_interruptible() 广泛应用于设备驱动程序中,如果睡眠的进程在获得需要的资源前被一个信号唤醒,该函数会增加信号量的 count 字段的置并返回 -EINTR,可放弃 I/O 操作。如果正常获得需要的资源,返回 0。

读/写信号量

类似于读/写自旋锁,不同之处:信号零再次变为打开之前,等待进程挂起而不是自旋转。

只有在内核控制路径不持有读信号量和写信号量时,才能获取写信号量。

数据结构为 rw_semaphore

  • count,两个 16 位计数器。高 16 位以二进制补码形式存放非等待写者进程的总数(0 或 1)和等待的写内核控制路径数。低 16 位存放非等待的读者和写者总数。
  • wait_list,等待进程的链表。链表中的每个元素是 rwsem_waiter 结构,包含一个指针和一个标志,指针指向睡眠进程的描述符,标志表示进程为读信号量还是写信号量。
  • wait_lock,自旋锁,保护等待队列链表和 rw_semaphore 结构。

函数

  • init_rwsem() 初始化 rw_semaphore 结构,把 count 置为 0,wait_lock 置为未锁,wait_list 置为空链表。
  • dwon_read()、down_write() 获取读或写信号量。
  • up_read()、up_write() 释放读或写信号量。
  • down_read_trylock()、down_write_trylock() 类似于 down_read()、down_write(),但在信号量忙的情况下,不阻塞进程。
  • downgrade_write() 自动将写锁转换为读锁。

补充原语

为了解决多处理器系统上发生的一种微妙的竞争关系,当进程 A 分配了一个临时信号变量,并将其初始化为关闭的 MUTEX,然后将其地址传递给进程 B。A 调用 down(),打算一旦被唤醒旧撤销该信号量,而运行在不同 CPU 上的 B 在该信号量上调用 up(),结果,up() 可能访问一个不存在的数据结构。

上述现象的原因:up() 和 down() 可在同一信号量上并发执行。


1
2
3
4
5
6
7
1struct completion
2{
3   unsigned int done;  
4   wait_queue_head_t wait;
5};-
6
7

up() 对应 complete()

  • 将 completion 的地址作为参数。
  • 在补充等待队列的自旋锁上调用 spin_lock_irqsave() 递增 done 字段,唤醒在 wait 等待队列上睡眠的互斥进程.
  • 调用 spin_unlock_irqrestore()。

down() 对应 wait_for_completion()

  • 将 completion 的地址作为参数,如果 done > 0,说明 complete() 已在另一个 CPU 上运行,终止。
  • 把 current 作为一个互斥进程加到等待队列的末尾,将 current 置为 TASK_UNINTERRUPTIBLE 状态并让其睡眠。
  • 一旦 current 被唤醒,将其从等待队列中删除,如果 done = 0,结束;否则,再次挂起 current。

补充原语和信号量之间的真正差别:如果使用等待队列中包含的自旋锁。

  • 补充原语中,自旋锁确保 complete() 和 wait_for_completion() 不会并发执行。
  • 信号量中,自旋锁用于避免并发执行的 down() 函数弄乱信号量的数据结构。

禁止本地中断

当硬件设备产生了一个 IRQ 信号,中断禁止也让内核控制路径继续执行,确保中断处理程序访问的数据结构受到保护。然而,禁止本地中断不保护运行在另一个 CPU 上的中断处理程序对数据结构的并发访问,因此需要与自旋锁结合使用。

local_irq_disable() 使用 cli 汇编指令关闭本地 CPU 上的中断。cli 清除 eflags 控制寄存器上的 IF 标志。
local_irq_enable() 使用 sti 汇编指令打开被关闭的中断。sti 设置 eflags 控制寄存器上的 IF 标志。

中断可以以嵌套方式执行,因此内核在临界区末尾不能简单设置 IF 标志。控制路径必须保存先前赋给 IF 标志的置,并在执行结束时恢复它。

local_irq_save 宏将 eflags 的内容保存到一个局部变量中,然后用 cli 汇编指令将 IF 标志清 0。
local_irq_restore 宏在临界区末尾恢复 eflags 的内容。

禁止和激活可延迟函数

禁止可延迟函数在一个 CPU 上执行的一种简单方式是禁止在那个 CPU 上的中断,使得软中断不能异步开始。

另一种方式是禁止可延迟函数而不禁止中断,通过操作当前 thread_info 描述符 preempt_count 字段中存放的软中断计数器即可。

如果软中断计数器是正数,do_softirq() 函数就不会执行。tasklet 会在软中断之前被执行,并将该计数器设置为大于 0 的值。

local_bh_disable 宏给本地 CPU 的软中断计数器加 1。

local_bh_enable() 函数从本地 CPU 的软中断计数器中减 1。

  • 如果本地 CPU 的 preempt_count 字段中硬中断计数器和软中断计数器的值都等于 0,且有挂起的软终端,就调用 do_softirq()。
  • 如果本地 CPU 的 TIF_NEED_RESCHED 标志被设置,说明进程切换请求时挂起的,调用 preempt_schedule()。

对内核数据结构的同步访问

在自旋锁、信号量及中断禁止之间选择

只要内核控制路径获得自旋锁(还有读/写锁、顺序锁或 RCU“读锁”),就禁用本地中断或本地软中断,自动禁用内核抢占。

保护异常所访问的数据结构

最常见的产生同步问题的异常是系统调用服务例程,仅由异常访问的数据结构通常表示一种资源,竞争条件可通过信号量避免。

保护中断所访问的数据结构

如果一个数据结构仅被中断处理程序的“上半部分”访问,无需任何同步原语,因为中断处理程序本身不能同时多次运行。

但是,如果多个中断处理程序访问一个数据结构时,情况有所不同:

  • 单处理器系统中,必须在中断处理程序的所有临界区上禁止中断来避免竞争条件,其他同步原语都不行。因为信号量能阻塞进程,自旋锁可能使系统冻结。
  • 多处理器系统中,避免竞争条件最简单的方法时禁止本地中断,并获取保护数据结构的自旋锁或读/写自旋锁。

保护被可延迟函数所访问的数据结构

单处理器系统上不存在竞争条件,因为可延迟函数的执行总是在一个 CPU 上串行执行,不需要同步原语。

多处理器系统上存在竞争条件,因为几个可延迟函数可以并发执行。

  • 由软中断访问的数据结构必须收到保护,通常使用自旋锁,因为同一个软中断可在多个 CPU 上并发运行。
  • 仅由一种 tasklet 访问的数据结构不需要保护,因为同种 tasklet 不能并发执行。
  • 由几种 tasklet 访问,必须对数据结构进行保护。

保护由异常和中断访问的数据结构

单处理系统上,

  • 以本地中断禁止访问数据结构。
  • 如果数据结构被一种中断处理程序访问,中断处理程序不用禁止本地中断就可访问数据结构。

多处理器系统上,

  • 本地中断禁止必须外加自旋锁,强制并发的内核控制路径等待。

有时使用信号量代替自旋锁可能更好。

  • 因为中断处理程序不能被挂起,必须用紧循环和 down_trylock() 函数获得信号量,在这里,信号量的作用与自旋锁一样。
  • 系统调用服务例程可在信号量忙时挂起调用进程,提高系统并发度。

保护由异常和可延迟函数访问的数据结构

与异常和中断处理程序访问的数据结构处理方式类似。可延迟函数本质上是由中断的出现激活的,而可延迟函数执行时不可能产生异常。因此,把本地中断禁止与自旋锁结合起来即可。

异常处理程序可用过使用 local_bh_disable() 宏禁止可延迟函数,而不禁止本地中断。在每 CPU 上可延迟函数的执行都被串行化,不存在竞争条件。

多处理器系统上,使用自旋锁可确保任何时候只有一个内核控制路径访问数据结构。

保护由中断和可延迟函数访问的数据结构

类似于中断和异常访问的数据结构。可延迟函数执行期间禁用本地中断。没有其他的中断处理程序访问数据结构时,中断处理程序可随意访问被可延迟函数访问的数据结构而不用关中断。

多处理器系统上,需要自旋锁禁止对多个 CPU 上数据结构的并发访问。

保护由异常、中断和可延迟函数访问的数据结构

禁止本地中断和获取自旋锁几乎总是避免竞争条件所必须的,但没有必要显式禁止可延迟函数。

避免竞争条件的实例

引用计数器

是一个 atomic_t 计数器,与特定的资源,如内存页、模块或文件相关。

  • 内核控制路径开始使用资源,原子减少计数器值。
  • 内核控制路径用完资源,原子增加计数器值。
  • 原子计数器变为 0,说明资源未被使用,如果必要,释放该资源。

大内核锁

粗粒度的自旋锁,确保每次只有一个进程运行在内核态。

用叫 kernel_sem 的信号量实现大内核锁,但比信号量复杂。

每个进程描述符含有 lock_depth 字段,允许同一个进程几次获得大内核锁。

  • -1,进程未获得过锁。
  • 正数,表示请求了多少次锁。

lock_kernel() 获得大内核锁:


1
2
3
4
5
6
1depth = current-&gt;lock_depth + 1;
2if(depth == 0)
3   down(&amp;kernel_sem);
4current-&gt;lock_depth = depth;
5
6

unlock_kernel() 释放大内核锁:


1
2
3
4
1if(--current-&gt;lock_depth &lt; 0)
2   up(&amp;kernel_sem);
3
4

持有大内核锁的进程可调用 schedule() 放弃 CPU。

当一个持有大内核锁的进程被强占时,schedule() 一定不能释放信号量,因为在临界区内执行代码的进程没有主动触发进程切换。

为避免被强占的进程事情大内核锁,preempt_schedule_irq() 临时把进程的 lock_depth 字段设置为 -1,这样 schedule() 假定被替换的进程不拥有 kernel_sem 信号量,也就不能释放它。一旦该进程再次被调度程序选中,preempt_schedule_irq() 函数就恢复 lock_depth 原来的值。

内存描述符读/写信号量

mm_struct 类型的内存描述符的 mmap_sem 字段为信号量。因为几个轻量级进程之间可以共享一个内存描述符,因此信号量可保护该描述符,以避免可能产生的竞争条件。

这种信号量为以读/写信号量方式实现,因为一些内核函数,如缺页异常处理程序只需要扫描内存描述符。

slab 高速缓存链表的信号量

slab 高速缓存描述符链表是通过 cache_chain_sem 信号量保护的,允许互斥地访问和修改该链表。

索引节点的信号量

Linux 把磁盘文件的信息存放在一种叫做索引节点的内存对象中。相应的数据结构包括自己的信号量,存放在 i_sem 字段中。

rename() 涉及两个不同的索引节点,必须采用两个信号量。为避免死锁,信号量的请求按预先确定的地址顺序进行。

给TA打赏
共{{data.count}}人
人已打赏
安全运维

WordPress网站专用docker容器环境带Waf

2020-7-18 20:04:44

安全运维

运维安全-Gitlab管理员权限安全思考

2021-9-19 9:16:14

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索