Linux Kernel Development 读书笔记

调度

  • Linux 的进程调度是基于 “处理器比重” 策略,具体实现通过 vruntime 成员。所有进程以各自的 vruntime 作为 Key,链接成为一个 RBTree。调度核心通过查找最小的 vruntime 对应的进程,作为下一刻需要运行的进程。vruntime 作为进程调度的核心,那它的计算方法是什么?

  • 应用程序进行系统调用(system call)时,通过 软中断(soft irq) 陷入内核态,将 系统调用号 以及 参数指针 通过 CPU 通用寄存器 传入(exp. eax, ebx…),由内核代表应用程序在 内核空间 执行系统调用。

  • Linux 内核常用的 内建数据结构 : 链表 list, 队列 kfifo, 映射 idr, 二叉树 rbtree


中断

  • Linux 中断实现机制怎样? 中断发生时,通过 中断向量表 跳转到预定义入口点。初始入口点将 中断号保存在栈中,然后跳转调用 unsigned int do_IRQ(struct pt_regs regs) 进行处理。因为 C 的调用惯例是要把函数参数放在 栈的顶部,因此可以从 pt_regs 结构中提取出中断号 进行进一步处理。

  • 什么是中断上下文?当执行一个中断处理程序时,内核即处于中断上下文 (interrupt context) 中。

  • 为什么中断里面不能休眠? 因为没有后备进程,所以中断上下文不可以休眠,否则又怎能对它重新调度呢? 这段话中的,后备进程 要怎么理解? 中断栈又是什么鬼?

  • 为什么中断处理需要分成 上半部 和 下半部 ? 上半部分 简单快速,执行的时候禁止一些或者全部中断。 下半部分 稍后执行,而且执行期间可以相应所有的中断。这种设计可使系统处于中断屏蔽状态的时间尽可能的短,以此来提高系统的相应能力。

  • softirq 和 sys_call 中的软中断意义是否一致? 答案是:不一致!sys_call 中的软中断指的是 体系结构 预留的软中断,有固定的中断号,触发后 立即 经由中断向量表进行映射跳转;softirq 中的软中断仅仅是一种 软件机制,维护一组静态注册的回调函数列表,触发后 无法立即 回调处理函数,需等待时机 (硬中断代码返回、ksoftirqd 内核线程中、do_softirq 显示调用刷新)

  • softirq 中为什么不能休眠? 难道是 softirq 是处于中断上下文 interrupt context?

  • tasklet 和 工作队列 的主要区别? tasklet 是 基于 softirq 实现,调用者将目标 tasklet 注册到 __this_cpu更好利用处理器的高速缓存)的 tasklet list 中,然后触发软中断等待执行,回调处理中 不允许休眠; 工作队列 是 基于 内核线程kthread等待队列 waitqueue 实现,硬中断函数中唤醒对应内核线程,在线程函数中检查并遍历执行 worklist,回调处理中 允许调度及休眠


同步

  • 为什么全局变量自加操作,在多线程中是不安全的? 请看以下例子:
线程 1 线程 2 线程 1 线程 2
获得 i (7) —— 获得 i (7) 获得 i (7)
增加 i (7->8) —— 增加 i (7->8) ——
写回 i (8) —— ——- 增加 i (7->8)
—— 获得 i (8) 写回 i (8) ——
—— 增加 i (8->9) —— 写回 i (8)
—— 写回 i (9)
  • 造成并发执行的原因?为什么数据需要同步?
    • Userspace: 用户程序在任何时刻都可能 被调度程序抢占和重新调度
    • Userspace: 异步发生的 信号 处理(什么信号?)
    • Kernel: 中断 — 几乎可以任何时刻异步发生
    • Kernel: 软中断和 tasklet — 内核能在 任何时刻 唤醒或调度 软中断 和 tasklet ( 怎么理解这里的任何时刻?具体是什么 Case 下? )
    • Kernel: 内核抢占 — 内核具有抢占性,内核中的任务可能会被另一任务抢占
    • Kernel: 睡眠及用户空间的同步 — 内核执行的进程可能会睡眠,这就会 唤醒调度程序,从而导致调度一个新的用户进程执行
    • Kernel: 对称多处理器 SMP — 两个或多个处理器可以同时执行代码
  • 在编写内核代码时,你要问自己下面这些问题:
    • 这个数据是不是全局的?除了当前线程外,其他线程能不能访问它?
    • 这个数据会不会在 进程上下文 和 中断上下文 中共享?它是不是要在两个不同的中断处理程序中共享?
    • 进程在访问数据时可不可能被抢占?被调度的新程序会不会访问同一数据?
    • 当前进程是不是会休眠(阻塞)在某些资源上,如果是,它会让共享数据处于何种状态?
    • 怎样防止数据失控?
    • 如果这个函数又在另一个处理器上被调度将会发生什么呢?
    • 如何确保代码远离并发威胁呢?
  • 常用的内核同步手段有哪些?简单介绍实现机制

    • atomic_t 原子操作:由 体系结构 提供的原子操作简单算术指令实现(经典用途:计数器)

    • spinlock 自旋锁:忙循环 - 旋转 - 等待,自旋锁不应被长时间持有。( rwlock 读写自旋锁 )

      由于下半部可以抢占进程上下文中的代码,所以当下半部和进程上下文共享数据时,必须对进程上下文中的共享数据进行保护,所以需要加锁的同时还要 禁止下半部执行 spin_lock_bh().

      同样,由于中断处理程序可以抢占下半部,所以如果中断处理程序和下半部共享数据的话,那么就必须在获取恰当的锁的同时还要 禁止中断 spin_lock_irqsave().

    • semaphone 信号量:基于等待队列实现的睡眠锁,适用于长时间持有的情况。( rwsem 读写信号量 & mutex 互斥信号量)

      函数 down_interruptible() 试图获取制定的信号量,如果信号量不可用,将把进程设置为 TASK_INTERRUPTIBLE 状态。而函数 down() 则会让进程在 TASK_UNINTERRUPTIBLE 状态下休眠,此状态无法响应其他信号了。所以 使用 down_interruptible() 比使用 down() 更为普遍(也更正确)

    • completion 完成变量:用于一个任务发出信号通知另一个任务发生了特定事件,实现思想和信号量一致。

    • seqlock 顺序锁:基于一个序列计数器实现,经典应用例程 jiffies。

    • preempt 禁止抢占:preempt_enable() or preempt_disable()

    • 顺序和屏障:处理多处理器和硬件设备之间的同步问题,确保跨越屏障的读/写不发生重排序,rmb(), wmb(), mb(), read_barrier_depends()


定时器

  • 内核中的 HZ 代表什么? 赫兹 HZ 代表每秒钟 pre-second 时钟中断发生的次数,也代表定时器精度,是通过静态预处理定义的。

  • 内核中的 jeffies 怎么来的? 全局变量 jeffies 用于记录自系统启动以来产生的节拍的总数 unsigned long volatile jeffies

    由于 jeffies 在 32-bit 机器上,字节数为 4 byte,存在 溢出后回绕 为 0 的问题。如果用户采用直接比较 jeffies 来判断时序,则有可能导致逻辑错误。因此内核提供了以下四个宏帮助比较节拍计数,正确处理节拍计数回绕问题:

    1
    2
    3
    4
    #define time_after(unknow, know) ((long)(know) - (long)(unknow) < 0)
    #define time_before(unknow, know) ((long)(unknow) - (long)(know) < 0)
    #define time_after_eq(unknow, know) ((long)(unknow) - (long)(know) >= 0)
    #define time_before_eq(unknow, know) ((long)(know) - (long)(unknow) >= 0)
  • 内核中的 xtime 全局变量用途? xtime 是用来代表 wall time (实际时间),RTC 模块主要在启动时协助初始化 xtime 变量。(xtime 全局变量的同步方式和 jeffies 一样,采用 seqlock 顺序锁同步)

    用户空间可以通过 gettimeofday() 系统调用来获取 wall time,内核也可以通过 do_gettimeofday() 来获取。

    1
    2
    3
    4
    struct timespec {
    _kernel_time_t tv_sec; /* second */
    long tv_nsec; /* ns */
    } xtime;
  • 可用的延时执行机制?说明简单实现

    • jeffies 忙等待:通过对 jeffies 进行判断,加上一定的空闲调度 cond_resched()
    • udelay 短延时:依靠执行数次循环达到延时效果,循环次数是根据 BogoMIPS 参数进行比例换算;
    • schedule_timeout:结合 timer 和 schedule 实现;

      如果任务既要等待一个特定事件到来,又在等待一个特定时间到期,这时可以简单使用 schedule_timeout() 代替 schedule() + wait_queue


内存管理与地址空间

  • 基本术语概念:页、区
    • Page 页:内存管理单元 (MMU,管理内存并把虚拟地址转换为物理地址的 硬件) 通常以页为单位进行处理,尽管处理器的 最小可寻址单位 通常是字(Or 字节)。大多数 32 位体系结构支持 4KB 的页,而 64 位体系结构一般会支持 8KB 的页
    • Zone 区:由于硬件存在缺陷而引起的内存寻址问题,内核并不能对所有页一视同仁,所以分成四种区:ZONE_DMA, ZONE_DMA32, ZONE_NORMAL, ZONE_HIGHMEM
      • 一些硬件只能用于某些特定的内存地址来执行 DMA.
      • 一些结构的内存的物理寻址范围比虚拟寻址范围大的多。这样,就有一些内存不能永久地映射到内核空间上
  • gfp_mask 分配器标志可分成三类:行为修饰符、区修饰符及类型。
    • 行为修饰符:标志内核应该如何分配所需的内存。(__GFP_WAIT 分配器可以休眠)
    • 区修饰符:表示内存区应当从何处分配。(默认从 ZONE_NORMAL 分配)
    • 类型标志:行为修饰符和区修饰符的指定组合。(GFP_KERNEL 常规分配可能会阻塞, GFP_ATOMIC 用在不能睡眠的上下文中)
  • Slab 分配器(Linux 通用数据结构缓存层)的 设计准则
    • 频繁使用的数据结构也会频繁分配和释放,因此应当缓存它们;
    • 频繁分配和回收必然会导致内存碎片,难以找到大块连续的可用内存。为了避免这种现象,应采用空闲链表的来缓存存放;
    • 回收的对象可以立即投入下一次分配,因此对于频繁的分配和释放,空闲链表能够提高决策;
    • 如果分配器知道对象大小、页大小和总的高速缓存的大小,它会做出更正确的决策;
    • 如果让部分缓存专属于单个处理器,那么分配和释放就可以不加 SMP 锁;
    • ?如果分配器是与 NUMA 相关的,它就可以从相同的内存节点为请求者进行分配;
    • ?对存放的对象进行着色,以防止多个对象映射到相关的高速缓存行 (cache line)
  • Slab 对象管理模型:基于 动态增长 的高速缓存 cachep,将其分成两级 Slab 与 对象 进行管理。高速缓存以页为单位,划分成为多个 Slab(一般 Slab 暂用一页)。然后 Slab 再以对象大小为单位,管理多个对象的申请与释放。
    高速缓存、Slab 及对象之间的关系图

  • 如何理解:进程栈、内核栈、中断栈三者的关系?以及分别有何种用途? 内核栈和中断栈分别独立占用一个页,其空间全部来至于进程栈。

  • precpu 每个 CPU 私有化数据资源的好处 : 减少了 SMP 数据锁(需要禁止内核抢占); 大大减少缓存失效;

  • mem_struct 与内核线程? 内核线程没有进程地址空间,也没有相关的内存描述符。所以内核线程对应的进程描述符中 mm 域为空。事实上,这也正是内核线程的真实含义 - 它们没有用户上下文。当一个内核线程被调度时,内核发现它的 mm 域为 NULL,就会保留前一个进程的地址空间,随后内核更新内核线程对应的进程描述符中的 active_mm 域,使其指向前一个进程的内存描述符。因为内核线程不访问用户空间的内存,它们仅仅使用地址空间中和内核内存相关的信息。

  • 虚拟内存域 vm_area_struct 和 内存描述符 mm_struct 的关系? mm_struct 描述整个进程的内存空间对象,vm_area_struct 是对进程内存空间进行区域划分,vm_area_struct 从属于 mm_struct。

    • 每个 VMA 对其相关的 mm_struct 结构体来说都是唯一的;所以即使两个独立的进程将同一个文件映射到各自的地址空间,它们分别都会有一个 vm_area_struct 结构体来标志自己的内存区域;
    • 同一个进程地址空间内的不同内存区域不能重叠;
    • Note: 可用使用 pmap $PID 来查看对应进程的虚拟内存域组织情况;
  • 页表:虽然应用程序操作的对象是映射到物理内存之上的虚拟内存,但是处理器直接操作的确实物理内存。所以当应用程序访问一个虚拟地址时,首先必须将虚拟地址转化为物理地址,然胡处理器才能解析地址访问的请求,而地址转化的过程就是页表查询的过程。

    地址转化需要将虚拟地址分段,使每段虚拟地址都作为一个索引指向页表,而页表项则指向下一级别的页表或者指向最终的物理页面。Linux 采用三级页表完成地址转化,三级页表名称分别为:PGD, PMD, PTE
    虚拟地址通过页表找到物理地址的过程.png
    页表空间大小解析.png

    • TLB 翻译后缓冲器:由于几乎每次对虚拟内存中的页面访问都必须先解析它,从而得到物理内存中的对应地址,所以页表操作的性能非常关键。TLB 是一个将虚拟地址映射到物理地址的硬件缓存,当请求访问一个虚拟地址时,处理器将首先检查 TLB 中是否缓存了改虚拟地址到物理地址的映射,如果缓存命中,就不需要通过页表搜索对应的物理地址了。

转载请注明出处: http://kyang.cc/