处理器活动

  • 用户空间, 执行用户进程
  • 内核空间, 处于进程上下文, 代表某个特定的进程执行
  • 内核空间, 处于中断上下文, 与任何进程无关, 处理某个特定的中断

当 CPU 空间时, 内核运行一个空进程, 处于进程上下文, 运行于内核空间

Linux 内核

  • 源码
  • 配置内核 (配置好的文件, 保存到源码的根目录下的 .config 文件中)
    • make config : 字符界面配置
    • make menuconfig : 基于 ncurse 库编制的图形界面工具
    • make gconfig : 基于 gtk+ 的图形界面工具
    • make defconfig : 默认的配置
    • 验证和更新配置
    • make oldconfig
    • 配置选项 CONFIG_IKCONFIG_PROC : 把完整的压缩过的内核配置文件存放在 /proc/config.gz 下. 如果旧的内核启用了此选项, 就可以复制出来, 并使用它来编译一个新的内核
    • zcat /proc/config.gz > .config
    • make oldconfig
  • 编译
    • make -j8
    • make -j8 > ../detritus 减少编译垃圾信息的输出
    • make -j8 > /dev/null 直接丢弃标准输出
  • 安装 : 参考 GRUB 或相关的引导文档
    • GRUB
    • LILO
  • 安装模块: make modules_install
  • 内核开发特点
    • 不能访问 C 库或标准 C 头文件
    • 必须使用 GNU C
    • 内联 inline : static inline void functionName(parameter)
    • 内联汇编 asm volatile(xxx)
    • 分支声明
    • 缺乏用户空间那样的内存保护机制
    • 用户程序访问非法内存, 内核会发送 SIGSEGV信号, 并结束进程. 内核中发生内存错误会导致 oops
    • 内核中的内存都不分页. 也就是说, 直接使用的是物理内存.
    • 难以执行浮点运算
    • 用户空间的浮点操作, 内核会完成从整数模式到浮点模式的转换
    • 内核空间并不能完美地支持浮点操作, 因为它本身并不能陷入. 在内核中使用浮点数时, 除了要人工保存和恢复浮点寄存器, 还有其他的琐碎事要做.
    • 内核给每个进程一个很小的定长堆栈
    • 用户空格的程序可以从栈上分配大量的空间来存放变量
    • 内核栈的准确大小随体系结构而变.
    • X86. 页大小可以是 4KB 或 8KB. 而内核栈的大小是两页. 这意味着 32 位内核栈是 8KB, 而 64 位内核栈是 16KB.
    • 内核支持异步中断, 抢占和 SMP, 所以时刻要注意同步和并发
    • 常用的解决竞争办法是
      • 自旋锁
      • 信号量
    • 要考虑可移植性

进程管理

  • 每个线程都拥有一个独立的程序计数器, 进程栈和一组进程寄存器
  • 内核调度的对象是线程, 而不是进程.
  • Linux 并不对线程和进程特别区分. 线程只是一种特殊的进程.
  • 系统给进制两种虚拟机制, 让进程觉得自己在独享这些虚拟资源
    • 虚拟处理器
    • 虚拟内存
  • 内核把进程的列表存放在任务队列的双向循环链表中
    • 每一项都是类型为 task_struct , 称为进程描述符的结构. 在 <linux/sched.h> 文件中
    • task_struct 在 32 位机器上, 大约为 1.7KB
    • 通过 slab 分配器分配 task_struct 结构
    • 用 PID 来标识每个进程. 最大值为 32768 (short int 的最大值). PID 存放在进程描述符中. cat /proc/sys/kernel/pid_max
    • 进程描述符中的 state 描述了进程的当前状态
    • TASK_RUNNING : 这是在用户空间唯一的可能状态
    • TASK_INTERRUPTIBLE : 可中断 – 进程正在睡眠(也称为阻塞), 等待某些条件达成. 一旦达成, 内核就会把进程状态设置为运行.
    • TASK_UNINTERRUPTIBLE : 不可中断 – 除了就算接收到信号也不会被唤醒或准备投入运行外, 这个状态与可中断状态相同.
    • _TASK_TRACED : 被其他进程跟踪. 例如通过 ptrace 对调试程度进行跟踪
    • _TASK_STOPPED : 停止. 进程停止执行. 通常是接收到信号: SIGSTOP, SIGTSTP, SIGTTIN, SIGTOU 等.
    • 进程家族树. 所有进程都是 PID 为 1 的 init 进程的后代. task_struct 中的 parent 指向父进程. children 指向子进程链表
  • 创建进程
    • fork() -> exec()
    • fork() 拷贝当前进程创建一个子进程.
    • exec() 负责读取可执行文件并将载入地址空间开始运行
    • 写时拷贝. copy-on-write
    • fork() 时使用 COW 技术实现.
    • 一般情况下, 进程创建后就马上运行, 这种技术可以避免大量根本不会被使用的数据.
    • fork() 的实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符.
    • fork() -> clone() -> do_fork() -> copy_process()
    • 步骤(copy_process())
      1. dup_task_struct() 为新进程创建一个内核栈. 此时子进程和父进程的描述符是完全相同的
      2. 检查当前用户所拥有的进程数目没有超出给它分配资源的限制
      3. 子进程着手跟父进程区别开来. 进程描述符许多成员清 0 或初始化.
      4. 子进程的状态设置为 TASK_UNINTERRUPTIBLE . 以保证它不会投入运行
      5. 调用 copy_flags() 以更新 task_struct->flags 成员.
      6. 调用 allo_pid() 为新的进程分配一个有效的 PID
      7. 根据传递给 clone() 的参数标志, copy_process() 拷贝或共享打开的文件, 文件系统信息, 信号处理函数, 进程地址空间和命名空间等. 进程内的线程, 这些资源是共享的. 否则这些资源对每个进程是不同的.
      8. 最后 copy_process() 做扫尾工作并返回一个指向子进程的指针.
    • 线程
    • 在 Linux 中, 把所有的线程都当做进程来实现.
    • 每个线程仅仅被视为一个与其他进程共享某些资源的进程.
    • 每个线程都拥有唯一隶属于自己的 task_struct
    • 创建线程
      • 与创建普通进程类似, 只不过在调用 clone() 时需要传递一些参数标志来指明需要共享的资源.
      • 一般线程调用的是 clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0)
      • 一个普通的 fork() 调用 : clone(SIGCHLD, 0)
    • 内核线程
      • 没有独立的地址空间
      • 只在内核空间运行, 从不切换到用户空间.
      • 和普通进程一样, 可以被调度, 也可以被抢占.
      • 是由 kthreadd 内核进程中衍生出所有新的内核线程的
  • 进程终结 do_exit()
    • 将 task_struct 的标志成员设置为 PF_EXITING
    • 调用 del_timer_sync() 删除任一内核定时器.
    • 如果 BSD 的进程记账功能是开启. 则调用 acct_update_integrals() 输出记账信息
    • 调用 exit_mm() 函数释放进程占用的 mm_struct
    • 调用 sem_exit() . 如果进程在排队等候 IPC 信号, 则离开队列.
    • 调用 exit_files() 和 exit_fs() 以分别递减文件描述符, 文件系统数据的引用计数. 如果引用计数为 0, 则释放资源.
    • 接着把存放在 task_struct 的 exit_code 成员中的任务退出代码置为 exit() 提供的退出代码, 或去完成任何其他由内核机制规定的退出动作.
    • 调用 exit_notify() 向父进程发送信号. 给子进程重新找养父, 其为线程组中的其他线程或 init 进程, 并把进程状态设置为 task_struct->exit_state=EXIT_ZOMBIE .
    • 调用 schedule() 切换到新的进程. 因为 ZOMBIE 状态的进程不会再被调度, 所以这是进程所执行的最后一段代码, do_exit() 永不返回.
    • 但系统还保留了它的进程描述符.
    • 这是为了让进程终结后还可以获得它的信息
    • 父进程获得已终结的子进程信息后, 或通知内核它并不关注那些信息后, 子进程的 task_struct 才会被释放.
    • 父进程调用 wait4() : 挂起调用它的进程, 直到其中一个的子进程退出, 此时函数返回该子进程的 PID . 还包含子函数退出时的退出代码.
    • 最终释放进程描述符 release_task()
    • 调用 __exit_signal() -> _unhash_process() -> detach_pid() 从 pidhash 上删除该进程, 同时也要从任务列表中删除该进程.
    • __exit_signal() 释放目前僵死进程所使用的剩余资源, 并进行最终统计和记录
    • 如果这个进程是线程组最后一个进程, 并且 leader 已经死掉, 则通知 leader 的父进程
    • 调用 put_task_struct 释放进程内核栈和 thread_info 结构所占的页, 并释放 task_struct 所占用的 slab 高速缓存
    • 孤儿进程
    • 父进程在子进程退出之前退出.
    • 则在当前线程组找一个线程作为父进程. 如果没有, 则让 init 作为父进程

进程调度

  • 多任务系统分类
    • 非抢占式多任务 cooperative multitasking
    • 除非进程自己主动停止运行, 否则它会一直执行.
    • 主动挂起的操作称为让步 yielding
    • 典型的是 Mac OS 9 及之前版本. 以及 Windows 3.1 及之前版本.
    • 抢占式多任务 preemptive multitasking
    • 由调度器来决定什么时候停止一个进程的运行, 以便其其他进程能够有机会执行
    • 这个强制的挂起动作就叫 抢占.
    • 进程被抢占之前能够运行的时间是预先设置好的, 而且有个专门的名字叫时间片 time slice
  • 进程类型
    • IO 消耗类型. Linux 更倾向于优先调度 I/O 消耗型进程.
    • CPU 消耗类型
  • 调度策略 : 在 响应时间短 和 高吞吐 之间寻找平衡
    • 进程优先级.
    • nice 值. 范围是 -20 ~ +19 . 默认为 0. 越大 表示优先级越低. 在 Linux 中, nice 值代表时间片的比例. 可通过命令 ps -el 查看 NI 值.
    • 实时优先级. 变化范围是 0~99 (包括 0 和 99). 与 nice 的值相反. 实时优先级越高, 意味着进程优先级越高. 可通过命令 ps -eo state,uid,pid,ppid,rtprio,time,comm 来查看 RTPRIO 列. 如果为 - 表示不是实时进程.
    • 时间片
    • 它表明进程在被抢占前所能持续运行的时间.
    • Linux 的 CFS 调度器并没有直接分配时间片到进程. 而是将处理器的使用比例分给进程. 并且这个比例还会受 nice 值的影响, nice 值作为权重将调整进程所使用的处理器时间的使用比例.
  • 调度器
    • 以模块方式提供, 允许多种不同的可动态添加的算法并存, 去调度属于自己范畴的进程.
    • 每个调度器都有一个优先级, 然后按优先级遍历调度器.
    • Linux 中使用 CFS (完全公平调度器)
    • 允许每个进程运行一段时间, 循环轮转, 选择运行最少的里程作为下一个运行进程
    • 不再采用分配给每个进程时间片的做法, CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久. 比如 1/n , 而不依靠 nice 值来计算时间片.
    • nice 值在 CFS 中被作为进程获得的处理器运行比的权重.
    • 但每个进程获得的时间片的最小粒度是 1ms
    • nice 的权重计算公式 W = 1024 / (1.25)^(nice) . 参考 https://oakbytes.wordpress.com/2012/06/06/linux-scheduler-cfs-and-nice/
      • 测试 nice 值对进程 CPU 的影响
      • taskset -c 5 dd if=/dev/zero of=/dev/null &
      • taskset -c 5 dd if=/dev/zero of=/dev/null &
      • htop -p xx1,xx2 (即上面两个命令返回的 PID 结果)
      • 然后在其他窗口修改其中一个 PID 的 nice 值: renice 1 xx1
      • 普通用户一般只能降低(即增加 nice) 权重
      • 可修改 sudo vim /etc/security/limits.conf 添加 用户名- nice -20 来实现普通用户使用指定 nice 值来启动.
    • CPU时间比 = W(a) / W(总权重).
    • CFS 的实现 kernel/sched_fair.c
    • 时间记账
      • CFS 使用 sched_entitys struct 来追踪进程的运行时间. <linux/sched.h> 它保存在 task_struct 名为 se 的成员变量中.
      • 虚拟运行时 vruntime. 用来记录一个程序到底运行了多长时间以及它还应该再运行多久. 由系统周期性更新, 无论进程处在可运行状态, 还是被阻塞.
    • 进程选择
      • CFS 调度算法的核心: 选择具有最小 vruntime 的进程(任务).
      • CFS 使用红黑树来组织可运行进程队列, 并利用其迅速找到最小 vruntime 值的进程.
      • 向红黑树中加入进程
      • 进程被唤醒
      • 通过 fork() 调用第一次创建进程
      • 从树中删除进程
      • 进程阻塞时
      • 进程终止时
    • 调度器入口
      • schedule() : 位于 kernel/sched.c 文件中
      • 它会从最高优先级的调度器中选择
      • 然后从相应调度器中选择最高优先级的进程来运行
    • 睡眠和唤醒
      • 休眠时, 从可执行队列中删除, 移到等待队列, 然后调用 schedule() 选择和执行下一个进程
      • 调用 DEFINE_WAIT() 创建一个等待队列项
      • 调用 add_wait_queue() 把自己加入等待队列中.
      • 调用 prepare_to_wait() 将进程状态变为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE . 接下来循环遍历.
        • 如果为 TASK_INTERRUPTIBLE , 则信号唤醒进程.
        • 当进程被唤醒, 它会再检查条件是否为真. 为真的话, 则退出循环. 否则, 再次调用 schedule() 并一直重复这步操作
        • 条件满足后, 进程将自己设置为 TASK_RUNNING 并调用 finish_wait() 把自己移出等待队列.
      • 唤醒时, 从等待队列删除, 移到可执行队列.
      • 通过函数 wake_up()
    • 抢占和上下文切换
    • 当一个新的进程准备投入运行的时候, schedule() 就会调用 context_switch() 函数负责处理.
    • context_switch() 完成两项基本工作
      • 调用 switch_mm() : 负责把虚拟内存从上一个进程映射切换到新进程中.
      • 调用 switch_to() : 负责从上一个进程的处理器状态切换到新进程的处理器状态. 这包括保存, 恢复栈信息和寄存器信息等.
    • 用户抢占发生情况
      • 从系统调用返回用户空间时
      • 从中断处理程序返回用户空间时
    • 内核抢占
      • 中断处理程序正在执行, 且返回内核空间之前
      • 内核代码再一次具有可抢占性的时候
      • 内核中的任务显式地调用 schedule()
      • 内核中的任务阻塞(也会导致调用 schedule() ).
    • CPU 绑定
    • 由进程描述符的 cpus_allowed 设置的.
    • cat /proc/$PID/status 查看

系统调用

  • 内核只与系统调用打交道
  • 程序只与系统提供的 API 打交道
  • 每一个系统调用, 都被赋予一个系统调用号. 独一无二. 比如 x86-64 位于 arch/i386/kernel/syscall_64.c 中.
  • 系统调用号放在 eax 寄存器来传递给内核的. 返回值也是保存在 eax 参数放在 ebx, ecx, edx, esi, edi 等寄存器上

内核数据结构

  • 链表
    • 单向链表
    • 双向链表
    • 环形链表
  • 队列
    • kfifo_alloc()
  • 映射
    • kv
  • 二叉树

比较算法性能时, 除了考虑时间复杂度 , 还要考虑输入规模.

中断

  • 硬件发送通知给处理器.
  • 硬件发送通知 -> 处理器 -> 通知内核 -> 触发中断处理
  • 不同的中断都可通过唯一的数字标志. 这些中断值通常称为中断请求 IRQ .
  • cat /proc/interrupts

定时顺和时间管理

  • 节拍率 : 内核在 <asm/param.h> 中定义了频率. 即每秒中断多少次.
  • 实时时钟 : RTC, 用来持久存放系统时间的设备. 系统初始化时, 会读取 RTB 来初始化 wallclock , 存放在 xtime 变量中.
  • 系统定时器. 主要采用可编程中断时钟 PIT . 使其能以 HZ/秒 的频率产生时钟中断.

内存管理

  • 页
    • 内存管理单元(MMU, 管理内存并把虚拟内存转换为物理地址的硬件), 通常以页为单位进行处理. 正因为如此, MMU 以页大小为单位来管理系统中的页表.
    • 从虚拟内存的角度来看, 页就是最小的单位. 通常 32 位为 4KB 页, 64 位为 8KB 页.
    • 内核使用 struct page 结构来表示系统中的每个物理页.
    • 成员 flags 表示页的状态
    • _count 存放页的引用计数
    • virtual 是页的虚拟地址.
  • 区(逻辑上的分组)
    • 由于硬件的限制, 内核并不能对所有页一视同仁. 所以再把页划分为不同的区.
    • 四种区(x86-32 为例 )
    • ZONE_DMA : <16MB
    • ZONE_DMA32 : 只能被 32 位设备访问.
    • ZONE_NORMAL : 能被正常映射的页. 16 ~ 896MB
    • ZONE_HIGHEM : 这里的页不能被永久地映射到内核空间. > 896MB
  • 想以字节为单位分配内存 kmalloc()

页高速缓存和页回写

ls /proc/sys/vm/ | grep dir | xargs -I{} bash -c "ls {}; cat {}; echo"

变量 描述
dirty_background_ratio 脏页超出该系统总内存百分比时进行回写
dirty_expire_interval(ms) 新 linux 为 dirty_expire_centisecs (厘秒) 脏页过期时间. 超出该时间, 也会回写
dirty_ratio 脏页占总内存百分比之前回写. 超出的话, 会阻塞新 IO 请求
dirty_writeback_interval (ms) 新 linux 为 dirty_writeback_centisecs 定期回写周期.