| Linux操作系统原理与应用03：进程 | 您所在的位置：网站首页 › linux操作系统原理与应用 › Linux操作系统原理与应用03：进程 |
Linux操作系统原理与应用03：进程
|
目录 1. 进程简介 1.1 程序和进程 1.2 进程的定义 1.2.1 正文段 1.2.2 用户数据段 1.2.3 系统数据段 1.3 进程的层次结构 1.3.1 进程的亲缘关系 1.3.2 进程树 1.3.3 祖先进程 1.4 进程状态 1.4.1 基本进程状态 1.4.2 进程状态的转换 1.5 从进程到容器 2. Linux中的进程控制块 2.1 进程控制块记录的信息 2.2 进程状态 2.2.1 PCB相关字段 2.2.2 进程状态说明 2.3 进程标识符 2.3.1 pid 2.3.2 tgid 2.3.3 用户标识与组标识 2.4 进程间亲属关系 2.5 进程控制块的存储 2.5.1 Linux 2.4实现 2.5.2 Linux 2.6实现 2.6 当前进程 3. Linux中的进程组织方式 3.1 进程链表 3.2 哈希表 3.3 就绪队列 3.3.1 概述 3.3.2 Linux 2.4实现 3.3.3 Linux 2.6实现 3.4 等待队列 3.4.1 概述 3.4.2 等待队列头数据结构 3.4.3 等待队列数据结构 3.4.4 等待队列操作 4. 进程调度 4.1 概述 4.1.1 进程调度的目标 4.1.2 基本调度模型 4.2 进程调度基本算法 4.2.1 时间片轮转调度算法 4.2.2 优先权调度算法 4.2.3 多级反馈队列调度 4.2.4 实时调度 4.3 时间片 4.3.1 时间片长度的设置 4.3.2 Linux时间片设置策略 4.4 Linux进程调度时机 4.5 进程调度的依据 4.5.1 need_resched 4.5.2 counter 4.5.3 nice 4.5.4 policy 4.5.5 rt_priority 4.5.6 goodness函数实现分析 4.6 调度函数schedule的实现 4.7 Linux 2.6调度程序的改进 4.7.1 单就绪队列问题 4.7.2 多处理器问题 4.7.3 内核态不可抢占问题 4.8 O(1)调度简介 4.8.1 O(1)调度器中的就绪队列 4.8.2 O(1)进程调度 4.9 机制与策略分离的调度模型 4.9.1 机制：核心调度层（core scheduler） 4.9.2 策略：调度类（specific scheduler） 4.10 完全公平调度CFS简介 5. 进程的创建 5.1 内核中的特殊进程 5.1.1 0号进程 5.1.2 1号进程 5.1.3 2号进程 5.2 进程和线程的关系 5.2.1 概述 5.2.2 Linux对进程和线程的统一描述 5.2.3 Linux对进程和线程的统一创建 5.3 do_fork函数流程简介 6. 实例：系统负载检测模块 6.1 正确理解系统负载 6.1.1 查看系统负载 6.1.2平均负载定义 6.1.3 单核系统负载图示 6.2 平均负载与CPU核心数的关系 6.3 负载检测模块实现分析 6.3.1 获取系统负载值 6.3.2 定时检测系统负载 6.3.3 打印所有线程调用栈 1. 进程简介 1.1 程序和进程① 程序是一个普通文件，是机器指令和数据的集合，这些指令和数据存储在磁盘上的一个可执行镜像（Executable Image）中 ② 进程是运行中的程序，除了包含程序中的所有内容，还包含一些额外数据，比如寄存器的值、用来保存临时数据的栈、被打开的文件及输入输出设备的状态等 所以说进程是一个执行环境的总和 ③ Linux是多任务操作系统，也就是说可以有多个程序同时装入内存并运行，操作系统为每个程序建议一个运行环境，即创建进程 ④ 从逻辑上说，每个进程都有自己的虚拟CPU，或者说每个进程都人为自己独占CPU，这里盗一张RTOS笔记中的图用于说明
⑤ 实际物理上的CPU是在各个进程之间来回切换运行，进程切换（Process Switching）又称作环境切换或上下文切换（Context Switching），这里的"进程的上下文"就是指进程的执行环境 1.2 进程的定义进程是由正文段（Text）、用户数据段（User Segment）和系统数据段（System Segment）共同组成的一个执行环境
① 存放被执行的机器指令 ② 正文段是只读的 ③ 允许系统中正在运行的多个进程之间共享正文段（e.g. 动态库） 1.2.2 用户数据段① 存放进程在执行时直接进行操作的所有数据 ② 数据段的信息可修改 ③ 数据段不共享，每个进程有自己专用的用户数据段 1.2.3 系统数据段① 存放程序运行的环境，这正是程序和进程的区别所在 ② 该段存放进程的控制信息，Linux为每个进程建立task_struct结构来容纳这些控制信息 说明：作为动态事物，进程是正文段、用户数据段和系统数据段信息的交叉综合体 1.3 进程的层次结构 1.3.1 进程的亲缘关系① 进程是一个动态的实体，具有生命周期，系统中进程的生死随时发生 ② 每个进程只有1个父进程，但是可以有0个或多个子进程 1.3.2 进程树进程逐级生成，构成进程树，可以使用pstree命令查看
说明1：pstree命令显示的进程中只有用户态进程，不包含内核态进程 说明2：init进程还负责收养系统中的孤儿进程，以保持进程树的完整性 1.3.3 祖先进程使用ps -el命令可以更好地体现进程间的亲缘关系
① 进程1（init）和进程2（kthreadd）都是由进程0产生 ② 进程0并不在进程列表中（是不是很神秘，后文会有说明） ③ 进程1（init）是所有用户态进程的祖先 ④ 进程2（kthreadd）是所有内核态进程的祖先 1.4 进程状态 1.4.1 基本进程状态
① 运行态：进程占有CPU并在CPU上运行 ② 就绪态：进程已经具备运行条件，但是由于CPU忙而暂时不能运行 ③ 阻塞态：进程因等待某种事件的发生而暂时不能运行（即使CPU空闲，进程也不可运行） 说明：这是操作系统理论中的3种基本状态，不同的操作系统在实现时会有所不同 1.4.2 进程状态的转换1.4.2.1 运行态 --> 阻塞态 ① 当进程发现自己不能继续运行时发生 ② 一般是因为进程发生IO请求或等待某事件的发生 1.4.2.2 运行态 --> 就绪态 ① 当进程耗尽时间片时发生 ② 一般由调度程序引起 1.4.2.3 就绪态 --> 运行态 ① 进程处于就绪态，被调度程序选择投入运行 1.4.2.4 阻塞态 --> 就绪态 ① 当进程等待的外部事件发生时发生 1.5 从进程到容器① 容器是目前云技术的核心技术 ② 容器技术的核心功能，就是通过约束和修改进程的动态表现，从而为其创造出一个边界 ③ 对于Docker等大多数Linux容器而言，cgroups技术是用来制造约束的主要手段；而namespace技术则是用来修改进程视图的主要方法 2. Linux中的进程控制块 2.1 进程控制块记录的信息Linux中使用task_struct结构描述进程生命周期中涉及的所有信息，这样的数据结构一般被称作PCB（Process Control Block） PCB中一般记录如下信息， ① 状态信息：描述进程动态的变化，如就绪态、阻塞态等 ② 链接信息：描述进程的亲属关系，如父进程、养父进程、兄弟进程、子进程等 ③ 各种标识符：用简单数字对进程进行标识，如进程标识符、用户标识符等 ④ 进程间通信信息：描述多个进程在同一任务上的协作，如管道、消息队列、共享内存、套接字等 ⑤ 时间和定时器信息：描述进程在生存周期内使用CPU时间的统计等信息 ⑥ 调度信息：描述进程优先级、调度策略等信息，如静态优先级、动态优先级、时间片轮转等 ⑦ 文件系统信息：对进程使用文件情况进行记录，如文件描述符、系统打开文件表、用户打开文件表等 ⑧ 虚拟内存信息：描述每个进程拥有的地址空间 ⑨ 处理器环境信息：描述进程的执行环境，即处理器的各种寄存器和栈等，这是体现进程动态变化最主要的场景 说明1：PCB是进程存在和运行的唯一标志 在进程的整个生命周期中，内核通过PCB感知进程的存在，并对进程进行控制。比如， ① 调度进程时，需要从PCB中取出运行状态与优先级 ② 进程切换时，需要从PCB中取出处理器环境信息用于恢复运行现场 ③ 实现进程同步与通信时，需要从PCB中取出进程间通信信息 ④ 当进程因某种原因需要暂停执行时，需要姜断点的处理机环境保存到PCB中 说明2：PCB是内核中被频繁读写的数据结构，故应常驻内存 2.2 进程状态 2.2.1 PCB相关字段
Linux中使用PCB的state字段标识当前进程状态，并使用一组宏（include/linux/sched.h）来进行标识 说明1：volatile long state volatile用于避免编译器优化，每次从内存而不是寄存器读取数据，以确保状态的变化能及时反映出来 说明2：内核中的进程状态均被定义为2的n次方，目的是便于位或运算，形成组合的进程状态 比如上图中的TASK_NORMAL状态就是TASK_INTERRUPTIBLE与TASK_UNINTERRUPTIBLE状态的位或 说明3：补充说明几种进程状态 __TASK_TRACED：由调试程序暂停进程的执行 EXIT_DEAD：最终状态，进程将被彻底删除，但需要父进程回收 TASK_DEAD：与EXIT_DEAD类似，但不需要父进程回收 TASK_WAKEKILL：接收到致命信号时唤醒进程，即使深度睡眠 2.2.2 进程状态说明
2.2.2.1 就绪态（TASK_RUNNING） ① 正在运行或准备运行 ② 处于就绪态的所有进程组成就绪队列，以备调度 2.2.2.2 睡眠（或等待）态 睡眠状态氛围深度睡眠和浅度睡眠， ① 浅度睡眠（TASK_INTERRUPTIBLE） 进程正在睡眠（被阻塞），等待资源有效时被唤醒，期间可以被其他进程通过信号或时钟中断唤醒 ② 深度睡眠（TASK_UNINTERRUPTIBLE） 与浅度睡眠类似，但是不能被其他进程发来的信号和时钟中断唤醒 2.2.2.3 暂停状态（TASK_STOPPED） ① 进程暂停执行，类似RTOS原理实现中的挂起 ② 当进程接收到如下信号后，进入挂起状态， SIGSTOP：停止进程执行 SIGTSTP：从终端发来信号停止进程 SIGTTIN：来自键盘的终端 SIGTTOU：后台进程请求输出 2.2.2.4 僵死状态（TASK_ZOMBIE） ① 进程执行结束但尚未消亡的状态 ② 此时进程已经结束并释放大部分资源，但尚未释放其PCB，可以使用wait系统调用回收该进程状态并释放PCB 2.3 进程标识符 2.3.1 pid① pid作为每个进程唯一的标识符，内核通过该标识符来识别不同进程 ② pid也是内核提供给应用程序的接口，e.g. waitpid & kill系统调用 ③ pid是32位无符号整型，按顺序编号，新创建进程的pid通常是前一个进程的pid加1 说明：Linux中允许的最大pid
可以在编译内核时配置CONFIG_BASE_SMALL的值，进而确定系统中默认的最大pid，当内核在系统中创建进程的pid超过这个值时，就必须重新开始使用已闲置的pid号 可以查看/proc/sys/kernel/pid_max结点的值来确定当前Linux中允许的最大pid，也可以通过该结点直接修改上限
① tgid即thread group id，该字段主要与Linux的线程实现模式相关 ② 在Linux中，线程是轻量级的进程，有自己的pid，只是共享进程的一些数据。在一个进程的多个线程之间，每个线程有自己的pid，但是tgid是相同的。关系如下图所示，
需要注意的是，从用户态视角，进程的不同线程调用getpid返回的pid是相同的，实际上返回的是task_struct的tgid 从内核态视角，每个线程有自己的pid，但是同一进程的不同线程有相同的tgid 验证：pid与tid的关系 #include #include #include #include #include #include // gettid系统调用没有封装例程 #define gettid() syscall(__NR_gettid) void *thread_1(void *arg) { printf("thread_1:\n"); printf("getpid() = %d\n", getpid()); printf("gettid() = %ld\n", gettid()); printf("pthread_self() = %ld\n", pthread_self()); printf("\n"); pause(); return (void *)0; } void *thread_2(void *arg) { printf("thread_2:\n"); printf("getpid() = %d\n", getpid()); printf("gettid() = %ld\n", gettid()); printf("pthread_self() = %ld\n", pthread_self()); printf("\n"); pause(); return (void *)0; } int main(void) { pthread_t pthread_1; pthread_t pthread_2; printf("main thread:\n"); printf("getpid() = %d\n", getpid()); printf("gettid() = %ld\n", gettid()); printf("pthread_self() = %ld\n", pthread_self()); printf("\n"); pthread_create(&pthread_1, NULL, thread_1, NULL); sleep(1); pthread_create(&pthread_2, NULL, thread_2, NULL); pthread_cancel(pthread_1); pthread_cancel(pthread_2); pthread_join(pthread_1, NULL); pthread_join(pthread_2, NULL); return 0; }运行结果如下，
① 主线程与2个子线程中，getpid的返回值相同，实际上返回的是task_struct中的tgid字段 ② 主线程与2个子线程中，gettid的返回值均不同，实际上返回的是task_struct中的pid字段 ③ POSIX thread库维护的tid（pthread_t类型）与内核态维护的pid & tgid完全不同，是用户态库的行为 补充：getpid & gettid的系统调用服务例程
看了内核态的实现，是不是一目了然，也能理解对多线程程序中用户视图 & 内核视图下"进程"的含义 2.3.3 用户标识与组标识task_struct中定义有用户标识符UID和组标识符GID，这两种标识符用于系统的安全控制，系统通过这两种标识符控制进程对文件和设备的访问 说明：Linux 2.4与Linux 2.6的实现不同 在Linux 2.4中，直接在task_struct中定义了uid、gid等字段
在Linux 2.6中，将相关内容打包为struct cred结构
task_struct中的如下字段用于维护进程间的亲属关系，
其中各字段的关系如下图所示，
说明1：父进程与养父进程 ① 父进程指向实际创建当前进程的进程，相当于亲生父亲 ② 但是父进程可能在子进程之前结束，此时init会收养该子进程，即成为该子进程的养父进程 说明2：因为一个进程可以创建多个子进程，所以有子进程链表，同时子进程之间是兄弟关系 2.5 进程控制块的存储在不同的Linux内核版本中，PCB都是和进程的内核栈一并存储的，这样可以达到2个目的， ① 节省内存空间，不再单独分配（当然，你也可以任务可用的栈空间减少了） ② 使用方便，进程一进入内核态，CPU就自动设置该进程的内核栈，而通过进程内核栈就很容易找到该进程的PCB 2.5.1 Linux 2.4实现2.5.1.1 数据结构
可见进程内核栈的总大小为8KB，PCB在内核栈地址的低端 2.5.1.2 分配与释放
PCB的分配与释放通过alloc_task_struct & free_task_struct函数实现，内存通过buddy系统分配 2.5.1.3 分配与释放流程 do_fork --> alloc_task_struct sys_wait4 --> release_task --> free_task_struct① 创建进程时分配PCB ② 调用wait系统调用回收进程时才释放PCB，所以僵尸进程（Zombie）会占用PCB资源 2.5.2 Linux 2.6实现2.5.2.1 数据结构
① 进程内核栈的大小依然为8KB ② 存储在进程内核栈中的不再是PCB，而是thread_info结构，该结构更小且包含指向PCB的指针
可见thread_info结构更贴近底层，且调用__switch_to进行进程上下文切换时就是使用该结构
在thread_info结构中包含了cpu_context_save结构，该结构根据体系结构不同，用于保存寄存器的值（下图示例中为ARM32体系结构）
那么问题就来了，PCB到哪儿了呢 ? 2.5.2.2 分配与释放
① PCB和内核进程栈分开分配 ② PCB通过slab系统分配（slab高速缓存读写速度更快） ③ 进程内核栈通过buddy系统分配 因此实际构成的内存布局如下图所示，
说明：将task_struct移出线程内核栈单独存储的原因 随着Linux版本的变化，进程控制块的内容越来越多，所需空间越来越大，这样就使得留给内核栈的空间变小。因此把部分进程控制块的内容移出这个空间，只保留访问频繁的thread_info 那么task_struct & thread_info的究竟多大呢 ? 我们在Ubuntu 16.04（Linux 4.15.0）上验证一下
可见task_struct的大小已经查过进程内核栈的大小了，所以必须移出该空间 在115-Ubuntu（Linux 3.2.0）上也验证一下，可见不移走真的没天理啊~
2.5.2.3 分配与释放流程 do_fork --> copy_process --> dup_task_struct --> alloc_task_struct // 分配PCB --> alloc_thead_info // 分配进程内核栈 do_wait --> do_wait_thread --> wait_consider_task --> wait_task_continued --> put_task_struct --> __put_task_struct --> free_task --> free_thread_info --> free_task_info 2.6 当前进程① 获得当前进程，就是找到当前进程的PCB ② 当前进程使用current宏获得，通过上述分析就很容易理解内核的实现方式了，本质上就是在进程内核栈中找到PCB 我们以Linux 2.6的实现为例，加以说明，
通过屏蔽sp的低13位，就可以获得进程内核栈的栈底（低端地址），也就获得了thread_info的地址，据此就可以获得当前进程的PCB 补充：加载 & 卸载内核模块时的当前进程 我们使用如下简单的内核模块进行验证， static int __init current_init(void) { printk("Hello world, from the kernel space\n"); printk("current task: %d --> %s\n", current->pid, current->comm); } static void __exit current_exit(void) { printk("Goodbye world, from the kernel space\n"); printk("current task: %d --> %s\n", current->pid, current->comm); } module_init(current_init); module_exit(current_exit);
3. Linux中的进程组织方式
3.1 进程链表
① Linux中的所有进程均被组织在进程链表中 ② task_struct中的tasks字段用于维护进程链表
③ 进程链表为双向循环链表，头节点为init_task，即0号进程的PCB
说明1：init_task静态分配
可见init_task的PCB和进程内核栈都是静态分配的，是一个全局变量，由于未再设置他的pid，所以init_task的pid为0，也就是整个Linux中的始祖进程 说明2：遍历所有进程实例 static int print_pid(void) { struct task_struct *task = NULL; struct task_struct *p = NULL; struct list_head *pos = NULL; int count = 0; // 打印0号进程信息 printk("init_task:%d --> %s\n", init_task.pid, init_task.comm); task = &init_task; list_for_each(pos, &task->tasks) { p = list_entry(pos, struct task_struct, tasks); ++count; printk("%d ---> %s\n", p->pid, p->comm); } printk("number of process is: %d\n", count); return 0; }在内核中调用print_pid函数可以打印当前系统中的所有进程，注意，此处不包含0号进程，可以单独打印
① 为了能够通过pid快速找到对应的PCB，Linux中的所有进程也被组织在哈希表中 ② task_struct中的pids字段用于维护哈希表
③ 内核中的pid_hash是一个全局变量，通过链地址法处理冲突，同一链表中pid由小到大排列
④ 通过find_task_by_vpid函数可以通过pid找到PCB
需要注意的是，此处为Linux 2.6中的实现，该版本已引入pid_namespace的概念 3.3 就绪队列 3.3.1 概述① 当内核需要寻址一个进程在CPU上运行时，只需要考虑处于就绪态（TASK_RUNNING）的进程 ② 就绪队列组织了系统中所有处于就绪态的进程 ③ 当进程不可运行时，需要被移出就绪队列，该操作在schedule函数中完成 3.3.2 Linux 2.4实现3.3.2.1 task_struct对应字段 task_struct中的run_list字段用于维护就绪队列
3.3.2.2 就绪队列定义 就绪队列runqueue_head为一个全局变量（kernel/sched.c），实现上就是一个内核链表头节点
说明：runqueue_head本身不具备互斥机制，对他的操作需要通过自旋锁runqueue_lock进行保护，下图为wake_up_process函数中的示例
3.3.2.3 就绪队列操作 ① add_to_runqueue函数将PCB加入就绪队列
说明：add_to_runqueue函数的调用时机 add_to_runqueue被wake_up_process & wake_up_process_synchronous调用，也就是当进程被唤醒时（准确说是可被调度时，比如do_fork中创建新的进程）将该进程加入就绪队列 ② del_from_runqueue函数将PCB移出就绪队列
说明：del_from_runqueue函数的调用时机 del_from_runqueue主要被schedule函数调用，当prev进程的状态不能再参与调度时，需要将该进程移出就绪队列，典型场景就是进程调用sleep_on等函数进入睡眠状态（在sleep_on函数中会调用schedule进行进程切换）
可见此处的操作也是需要自旋锁保护的 3.3.3 Linux 2.6实现3.3.3.1 task_struct对应字段 在Linux 2.6版本中，run_list字段被替换为2个调度实体结构，其中分别封装了cfs_rq和rt_rq结构
3.3.3.2 就绪队列定义
说明1：struct rq结构封装了就绪队列与调度相关信息，与task_struct中的字段是匹配的，整个进程调度的实现也更加复杂 说明2：多处理器场景（SMP） 在Linux 2.4中，多处理器共享一个就绪队列，即多处理器上的进程放在一个就绪队列中，使得这个就绪队列成为临界资源，从而降低了系统效率 在Linux 2.6中，每个处理器有自己的就绪队列 3.3.3.3 就绪队列操作 Linux 2.6中引入了调度类（sched class）的概念，task_struct中也包含了指向进程调度类的结构指针，当进程进出就绪队列时，会调用注册的hook函数
在调用enqueue_task函数入队时，会根据PCB的不同调度类加入不同的就绪队列，而加入就绪队列的时机仍然是调用wake_up_process函数
相同地，移出就绪队列的时机主要也是schedule函数 注：Linux 2.6的进程调度更为复杂，此处不做更多的分析 3.4 等待队列 3.4.1 概述① 当进程需要进入睡眠状态时（TASK_INTERRUPTIBLE & TASK_UNINTERRUPTIBLE），需要有可以实现睡眠和唤醒的机制，即有地方进入等待状态，有地方唤醒进程 ② 等待队列就是用于实现在事件上的条件等待，即希望等待特定事件的进程把自己放入放进合适的等待队列，并放弃控制权 ③ 除了等待队列，内核中的mutex、semaphore等机制也可以实现等待，实现的思路也是类似的（剧透一下，mutex & semaphore结构起到了等待队列头的作用） 注：后续分析基于Linux 2.6内核 3.4.2 等待队列头数据结构
等待队列头就是由等待队列链表（task_list）和相关的保护机制（自旋锁）构成 说明：等待队列头的定义 可以使用DECLARE_WAIT_QUEUE_HEAD宏直接定义一个初始化好的等待队列头
如果单独定义了wait_queue_head_t类型的变量，也可以调用init_waitqueue_head宏函数进行初始化，该函数的内部实现也就是初始化等待队列头结构中的自旋锁和链表
① flags 取值为0或1（即WQ_FLAG_EXCLUSIVE），标识睡眠进程是否互斥，后文将会看到，如果是互斥进程，唤醒时只会唤醒第1个；如果是非互斥进程，则会唤醒所有进程参与调度 ② func 唤醒函数 ③ private 传递给唤醒函数的参数，实际传输PCB指针 ④ task_list 用于构成等待队列，如下图所示
注：确实，这里称为等待队列项更好 说明：等待队列的初始化 DECLARE_WAITQUEUE宏可用于定义一个初始化好的等待队列
此处注意2点， ① 定义等待队列时指定的task一般就是current，也就是当前进程，因为要睡眠的就是当前进程 ② 此处提供的默认唤醒函数为default_wake_function，该函数就是去唤醒等待队列private字段指向的进程
如果单独定义了wait_queue_t类型的变量，也可以调用init_waitqueue_entry函数进程初始化，效果与上面的宏一致
补充：内核中还提供了init_waitqueue_func_entry函数，可用于指定等待队列的唤醒函数
但是要注意，该函数会将等待队列的private字段清空，可根据需要再次设置，以下为do_wait函数的示例
稍微多说一丢丢，这里的操作就是让wait系统调用阻塞等待回收子进程 3.4.4 等待队列操作3.4.4.1 等待队列入队操作
add_wait_queue & add_wait_queue_exclusive函数用于实现直接将等待队列插入等待队列头，差别在于2点， ① add_wait_queue_exclusive将等待队列的flags字段置为WQ_FLAG_EXCLUSIVE ② 非互斥进程插入队首，互斥进程插入队尾 3.4.4.2 在等待队列头上实现睡眠 以sleep_on函数族为例，最终都是调用sleep_on_common函数实现，差别在于是否可唤醒以及是否设置超时时间
当不需要超时时，将timeout值设置为MAX_SCHEDULE_TIMEOUT，实现中一般为long类型可表示的最大值，此时不会实际建立定时器，只是用于标识无需超时 下面就来分析以下sleep_on_common函数，
将等待队列移出等待队列头的操作需要在当前进程被再次调度运行时才进行，而此时有2种情况， ① 等待的事件就绪 ② 等待超时 此时就要分析一下schedule_timeout函数的实现，
说明1：process_timeout的行为 process_timeout为timer到期时调用的函数，该函数的作用就是唤醒指定的进程（此处指定的就是current进程）
说明2：sleep_on函数族无法识别被中断唤醒还是等待的事件就绪，只要带有timeout，返回的就是定时器剩余jiffies值 所以在使用中，当sleep_on函数族返回时（带timeout或interruptible的版本），可以调用signal_pending，判断进程是否是被中断唤醒
说明3：为何不能在中断上下文中睡眠 ① 通过上文对sleep_on函数族的分析可知，进入睡眠的主要步骤就是将当前进程（current）设置为睡眠态 + 调用schedule函数触发进程切换 但是在处理中断时（更准确地说，是在处理中断顶半部时），中断上下文却不是一个进程，他不存在task_struct，所以是不可调度的。如果在中断顶半部中调用类似sleep_on的函数，依然是将current睡眠，而这个睡眠完全是不符合预期的，被睡眠的是从当前栈中计算出的task_struct标识的进程 ② 为什么中断上下文不存在对应的task_struct结构 ? 中断的产生是很频繁的（比如Linux 2.6之后的timer中断每毫秒产生一个），并且中断处理过程很快。如果为中断上下文维护一个对应的task_struct结构，这个结构会被频繁地分配和回收（尤其是task_struct结构已经非常巨大），会影响调度器的管理，进而影响整个系统的吞吐量 ③ 但是在某些实时性的嵌入式Linux中，中断也被赋予task_struct结构。这是为了避免大量中断不断的嵌套，导致一段时间内CPU总是运行在中断上下文，使得某些优先级非常高的进程得不到运行 这种做法能够提高系统的实时性，但是代价是吞吐量的降低 ④ Linux 2.6之后的内核版本中还存在一些不可抢占的区间，如中断上下文、软中断上下文和自旋锁锁住的区间 如果给Linux内核打上RT-Preempt补丁，则中断和软中断都被线程化了，自旋锁也被互斥体替换，此时的Linux内核就可以支持硬实时 所以Linux 2.6之后的内核版本默认提供软实时的能力 3.4.4.3 在等待队列头上实现唤醒 唤醒等待队列可以使用wake_up函数族，这些函数最终都会调用到__wake_up_common函数
下面就分析下__wake_up_common函数的实现，
该函数的主体就是遍历等待队列，并调用唤醒函数。需要注意的是对互斥进程的处理，根据上文的分析，加入等待队列中的进程都是非互斥进程在前，互斥进程在后，所有非互斥进程会先被全部唤醒 对于非互斥进程，需要唤醒nr_exclusive个互斥进程后才会停止，如果nr_exclusive need_resched，当值为1时，调用schedule函数 ③ 将task_struct的need_resched字段置为1，就是说明该进程不能再运行了，需要被调度走，所以下面理解的重点就是在这些场景中为何要调度走这个进程 下面是将need_resched设置为1的一些场景（其实是Linux 2.4中的所有场景了）， 4.5.1.1 do_fork 创建子进程后，父子进程平分父进程剩余的时间片，如果平分后父进程时间片为0，则设置调度标志
4.5.1.2 start_kernel 在进入cpu_idle之前设置调度标志
补充一点，在进入cpu_idle函数之后，会将进程0的优先级设置为最低。由于在进入cpu_idle之前设置了need_resched字段，所以进入cpu_idle后会触发调度
4.5.1.3 reschedule_idle reschedule_idle函数被wake_up_process调用，该函数的作用是为唤醒的进程选择一个合适的CPU来执行，如果他选中了某个CPU，就会将该CPU上当前运行进程的need_resched标志置为1，即该CPU上有更值得运行的进程运行了 4.5.1.4 setscheduler
该函数被系统调用服务例程sys_sched_setparam & sys_sched_setscheduler调用，由于设置了目标进程的调度策略或优先级，可能有更值得运行的进程了，所以将当前进程的need_resched标志置为1 说明：此处对应的系统调用封装例程为sched_setparam & sched_setscheduler 4.5.1.5 sys_sched_yield
sys_sched_yield为系统调用服务例程，用于主动让出CPU 说明：此处对应的系统调用封装例程为sched_yield 4.5.1.6 update_process_times
update_process_times被系统时钟中断调用，该函数会递减当前正在运行进程的时间片，如果时间片耗尽，则标记需要调度 这里也顺带说明了task_struct结构中counter字段的作用~ 4.5.2 counter① 进程处于可运行状态时所剩余的时钟节拍数，根据上文，当进程在运行时，每次时钟中断到来，该值减1 ② 该值也称为进程的动态优先级 4.5.3 nice① 进程的基本优先级，也称作静态优先级。这个值在-20 ~ 19之间，值越小优先级越高，缺省值0对应普通进程 ② nice的值决定counter的初值，该转换通过NICE_TO_TICKS宏实现，
可见静态优先级越高，获得的时钟节拍数越多 注：20 - nice的值为[40, 1]，可见nice的取值确实是历史遗留现象，当时的目的就是为了让优先级高的进程获得更多的ticks 4.5.4 policy进程的调度策略，在Linux 2.4内核版本中支持如下3种调度测录， ① SCHED_FIFO：先入先出的实时进程 ② SCHED_RR：时间片轮转的实时进程 ③ SCHED_OTHER：普通分时进程 ④ SCHED_YIELD：主动让出CPU 说明1：SCHED_FIFO & SCHED_RR都是实时进程，与普通分时进程有本质区别，下文的goodness函数分析中可见，二者的调度优先级有天壤之别 说明2：Linux 2.6内核版本中支持的调度策略为， SCHED_NORMAL / SCHED_FIFO / SCHED_RR / SCHED_BATCH / SCHED_IDLE / SCHED_YIELD 4.5.5 rt_priority① 实时进程的优先级 ② 实时进程优先级有效值为[1, 99]，在setscheduler函数中设置（系统调用服务例程） 说明：Linux 2.6.35版本进程优先级简介 在task_struct中有如下和优先级相关的字段， int prio; // 动态优先级 int static_prio; // 静态优先级 int normal_prio; // 归一化优先级 unsigned int rt_priority; // 实时优先级其中，归一化优先级根据静态优先级、调度优先级和调度策略计算得到
4.5.6.1 概述与调用 ① goodness函数的作用就是根据上述依据计算一个进程的权重，之后调度程序可依据该权重选择出最值得运行的进程 ② schedule函数中对goodness函数的调用式如下图所示，
p：遍历就绪队列中的task_struct this_cpu：为前一进程（prev）运行的CPU prev->active_mm：为前一进程（prev）的active_mm字段 4.5.6.2 active_mm字段 Linux将进程的虚拟地址空间划分为用户态和内核态，每当进程上下文切换时，用户态虚拟地址空间发生切换，以便与当前运行的进程匹配；而内核态虚拟地址空间是所有进程共享的，不会发生切换 task_struct中包含2个mm_struct类型的指针，即mm和active_mm
其中mm指向进程的用户态虚拟地址空间，所以内核线程的mm为NULL；而active_mm字段指向进程最近一次使用的地址空间，调度程序可依据active_mm字段进行优化 这种情况主要发生在从用户进程切换到内核进程的场景，此时会将切换出去的用户进程的active_mm存放在内核进程的active_mm字段，这样内核空间就知道当前的用户空间包含了什么 而这里的优化空间就是如果内核线程之后运行的用户进程与之前是同一个，那么TLB中的信息仍然有效 参考资料： https://www.cnblogs.com/linhaostudy/archive/2018/11/04/9904846.html 4.5.6.3 函数实现分析 static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm) { int weight; /* * select the current process after every other * runnable process, but before the idle thread. * Also, dont trigger a counter recalculation. */ // 权重初始值为-1 weight = -1; // 如果进程调度策略为SCHED_YIELD，则直接返回-1 if (p->policy & SCHED_YIELD) goto out; /* * Non-RT process - normal case first. */ // 对于普通分时进程，返回的就是剩余ticks数 // 当进程时间片耗尽时，返回0 if (p->policy == SCHED_OTHER) { /* * Give the process a first-approximation goodness value * according to the number of clock-ticks it has left. * * Don't do any other calculations if the time slice is * over.. */ weight = p->counter; // 时间片耗尽，返回0 if (!weight) goto out; #ifdef CONFIG_SMP /* Give a largish advantage to the same processor... */ /* (this is equivalent to penalizing other processors) */ if (p->processor == this_cpu) weight += PROC_CHANGE_PENALTY; #endif /* .. and a slight advantage to the current MM */ // 轻微调整优先级 // p->mm == this_mm：该进程的用户空间就是当前进程，如果让其继续 // 运行，可减少一次进程切换 // !p->mm：该进程没有用户空间，是一个内核进程，如果调度其运行， // 无需切换到用户态 if (p->mm == this_mm || !p->mm) weight += 1; // 静态优先级在权重中的体现 weight += 20 - p->nice; goto out; } /* * Realtime process, select the first one on the * runqueue (taking priorities within processes * into account). */ // 实时进程直接加1000 weight = 1000 + p->rt_priority; out: return weight; }说明1：实时进程的权重至少为1000，且与counter和nice无关，所以优先级远高于普通分时进程 在系统中，如下进程就是实时进程，
我们写个小程序，来看下这几个实时进程的调度策略（这要用到下面一个小节介绍的系统调用），从结果看，系统的实时进程为SCHED_FIFO调度策略，也就是说在没有优先级更高的进程的情况下，这些实时进程会运行到主动放弃CPU为止
附上代码如下， #include #include #include int main(int argc, char *argv[]) { pid_t pid = 0; int policy = 0; pid = (pid_t)atoi(argv[1]); policy = sched_getscheduler(pid); if (policy < 0) { perror("get policy error"); return -1; } else { switch (policy) { case SCHED_FIFO: printf("SCHED_FIFO\n"); break; case SCHED_RR: printf("SCHED_RR\n"); break; case SCHED_OTHER: printf("SCHED_OTHER\n"); break; default: printf("policy = %d\n", policy); break; } return 0; } }说明2：普通分时进程的优先级取决于counter和nice，其中， ① counter越小，权重越小。这个就体现了如果进程虽然时间片的消耗，权重会降低，会将优先级让给剩余时间片较多的进程，这就是为啥counter字段被称作动态优先级的原因 ② nice就体现先天的优先级了，优先级越高，时间片越多 说明3：与调度策略 & 优先级相关的系统调用 Linux 2.4内核版本中和调度策略 & 优先级相关的系统调用有如下8个，
我们直接来看这7个系统调用服务例程的实现，理解了内核态的实现，用户态的调用也就很容易理解了，在需要时可以修改进程的调度策略，使其具有更高的优先级 ① sys_sched_getparam
② sys_sched_setscheduler & sys_sched_setparam
这2个函数都是通过调用setscheduler函数实现的，只是sys_sched_setparam只设置优先级，不设置调度策略，下面看一个setscheduler函数的实现 static int setscheduler(pid_t pid, int policy, struct sched_param *param) { struct sched_param lp; struct task_struct *p; int retval; retval = -EINVAL; if (!param || pid < 0) goto out_nounlock; retval = -EFAULT; if (copy_from_user(&lp, param, sizeof(struct sched_param))) goto out_nounlock; /* * We play safe to avoid deadlocks. */ read_lock_irq(&tasklist_lock); // 保护哈希表 spin_lock(&runqueue_lock); // 保护就绪队列 p = find_process_by_pid(pid); retval = -ESRCH; if (!p) goto out_unlock; // 此时就是不设置调度策略，仅设置优先级 if (policy < 0) policy = p->policy; else { retval = -EINVAL; // 检查要设置的调度策略是否合法 if (policy != SCHED_FIFO && policy != SCHED_RR && policy != SCHED_OTHER) goto out_unlock; } /* * Valid priorities for SCHED_FIFO and SCHED_RR are 1..99, valid * priority for SCHED_OTHER is 0. */ retval = -EINVAL; // 实时优先级有效值为[1, 99] // 如果是普通分时进程，动态优先级的值必须为0 if (lp.sched_priority < 0 || lp.sched_priority > 99) goto out_unlock; if ((policy == SCHED_OTHER) != (lp.sched_priority == 0)) goto out_unlock; // 检查是否有设置的权限 retval = -EPERM; if ((policy == SCHED_FIFO || policy == SCHED_RR) && !capable(CAP_SYS_NICE)) goto out_unlock; if ((current->euid != p->euid) && (current->euid != p->uid) && !capable(CAP_SYS_NICE)) goto out_unlock; // 设置调度策略与优先级 retval = 0; p->policy = policy; p->rt_priority = lp.sched_priority; // 如果被设置优先级的进程在就绪队列中，将其移至队首 if (task_on_runqueue(p)) move_first_runqueue(p); // 由于设置了目标进程的优先级，可能出现优先级更高的进程可运行 // 所以触发调度 current->need_resched = 1; out_unlock: spin_unlock(&runqueue_lock); read_unlock_irq(&tasklist_lock); out_nounlock: return retval; }③ sys_sched_getscheduler
④ sys_sched_yield
⑤ sys_sched_get_priority_max
⑥ sys_sched_get_priority_min
⑦ sys_sched_rr_get_interval
该函数用于返回SCHED_RR类型进程的时间片值，从实现分析需要注意2点， a. 如果是SCHED_FIFO类型进程，返回0，因为这类进程不是分时进程（其实分时进程都会返回时间值，不一定是SCHED_RR进程） b. 返回的是基于nice值计算出的时间片值 所以综合起来看，这个系统调用确实没啥用处 补充：用于设置静态优先级的sys_nice系统调用
注意2点， a. nice系统调用只能修改当前进程的静态优先级 b. nice系统调用的参数increment是一个增量，最终的计算结果会归一化到合法范围 4.6 调度函数schedule的实现注：本节以Linux 2.4版本为例 asmlinkage void schedule(void) { struct schedule_data * sched_data; // prev：前一进程，即要调度走的进程 // next：后一进程，即要调度执行的进程 struct task_struct *prev, *next, *p; struct list_head *tmp; int this_cpu, c; // 如果当前进程active_mm为空，出错 if (!current->active_mm) BUG(); need_resched_back: prev = current; this_cpu = prev->processor; // 在进程上下文调度，出错 if (in_interrupt()) goto scheduling_in_interrupt; // 释放全局内核锁，并开this_cpu的中断 release_kernel_lock(prev, this_cpu); /* Do "administrative" work here while we don't hold any locks */ // 如果此时有软中断要处理，则先处理软中断 // 处理完成后返回handler_softirq_back标签 if (softirq_active(this_cpu) & softirq_mask(this_cpu)) goto handle_softirq; handle_softirq_back: /* * 'sched_data' is protected by the fact that we can run * only one process per CPU. */ sched_data = & aligned_data[this_cpu].schedule_data; spin_lock_irq(&runqueue_lock); // 保护就绪队列 /* move an exhausted RR process to be last.. */ // 如果要调度走的是SCHED_RR进程，如果该进程时间片耗尽， // 将其移至就绪队列队尾，然后返回move_rr_back标签 if (prev->policy == SCHED_RR) goto move_rr_last; move_rr_back: switch (prev->state) { // 如果要被调度走的进程此时被信号打断，则恢复TASK_RUNNING状态 // 此时可继续参与调度 case TASK_INTERRUPTIBLE: if (signal_pending(prev)) { prev->state = TASK_RUNNING; break; } // 其余情况则移出就绪队列 default: del_from_runqueue(prev); case TASK_RUNNING: } // 清除前一进程的请求调度标志 prev->need_resched = 0; /* * this is the scheduler proper: */ repeat_schedule: /* * Default process to select.. */ next = idle_task(this_cpu); c = -1000; // 如果前一进程可以继续运行，则计算器权重，并默认后一进程就是前一进程 // 即不发生进程切换（除非有更高优先级的进程） if (prev->state == TASK_RUNNING) goto still_running; still_running_back: // 遍历就绪队列，找到权重最大的进程 list_for_each(tmp, &runqueue_head) { p = list_entry(tmp, struct task_struct, run_list); if (can_schedule(p, this_cpu)) { int weight = goodness(p, this_cpu, prev->active_mm); if (weight > c) c = weight, next = p; } } /* Do we need to re-calculate counters? */ // 如果返回的c为0，说明， // 1. 就绪队列中没有实时进程（实时进程的权重至少为1000） // 2. 所有普通分时进程的时间片均耗尽 // 此时需要重新设置所有进程的时间片，然后返回repeat_schedule重新调度 if (!c) goto recalculate; /* * from this point on nothing can prevent us from * switching to the next task, save this fact in * sched_data. */ sched_data->curr = next; #ifdef CONFIG_SMP next->has_cpu = 1; next->processor = this_cpu; #endif spin_unlock_irq(&runqueue_lock); if (prev == next) goto same_process; #ifdef CONFIG_SMP /* * maintain the per-process 'last schedule' value. * (this has to be recalculated even if we reschedule to * the same process) Currently this is only used on SMP, * and it's approximate, so we do not have to maintain * it while holding the runqueue spinlock. */ sched_data->last_schedule = get_cycles(); /* * We drop the scheduler lock early (it's a global spinlock), * thus we have to lock the previous process from getting * rescheduled during switch_to(). */ #endif /* CONFIG_SMP */ kstat.context_swtch++; /* * there are 3 processes which are affected by a context switch: * * prev == .... ==> (last => next) * * It's the 'much more previous' 'prev' that is on next's stack, * but prev is set to (the just run) 'last' process by switch_to(). * This might sound slightly confusing but makes tons of sense. */ prepare_to_switch(); { struct mm_struct *mm = next->mm; struct mm_struct *oldmm = prev->active_mm; // 如果后一进程为内核进程，没有用户虚拟空间 // 此时借用前一进程的用户虚拟空间 if (!mm) { if (next->active_mm) BUG(); next->active_mm = oldmm; atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next, this_cpu); // 后一进程为普通进程，需要切换用户虚拟空间 } else { if (next->active_mm != mm) BUG(); switch_mm(oldmm, mm, next, this_cpu); } // 如果被切换走的是内核进程，则归还他借用的用户虚拟空间 // mm_struct的共享计数减1 if (!prev->mm) { prev->active_mm = NULL; mmdrop(oldmm); } } /* * This just switches the register state and the * stack. */ // 实际进行进程切换，体系结构相关 switch_to(prev, next, prev); __schedule_tail(prev); same_process: reacquire_kernel_lock(current); if (current->need_resched) goto need_resched_back; return; recalculate: { struct task_struct *p; spin_unlock_irq(&runqueue_lock); read_lock(&tasklist_lock); for_each_task(p) p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice); read_unlock(&tasklist_lock); spin_lock_irq(&runqueue_lock); } goto repeat_schedule; still_running: c = goodness(prev, this_cpu, prev->active_mm); next = prev; goto still_running_back; handle_softirq: do_softirq(); goto handle_softirq_back; move_rr_last: if (!prev->counter) { prev->counter = NICE_TO_TICKS(prev->nice); move_last_runqueue(prev); } goto move_rr_back; scheduling_in_interrupt: printk("Scheduling in interrupt\n"); BUG(); return; }说明1：switch_to实现真正的切换，且实现是与体系结构相关的
当调用完switch_to之后，就会实际切换到后一进程运行，schedule函数中switch_to调用之后的语句需要调度程序又选择prev进程执行时由prev进程执行 说明2：详解进程空间切换 struct mm_struct *mm = next->mm; struct mm_struct *oldmm = prev->active_mm; // 如果后一进程为内核线程，由于内核线程没有进程用户空间 // 所以在进程切换时借用上一进程的用户空间 if (!mm) { // 此时要运行的内核线程的active_mm应该为空 if (next->active_mm) BUG(); // 即借用prev->active_mm，prev可能也是内核线程哦 next->active_mm = oldmm; // 可见mm_count是内核线程对用户进程空间的借用次数 atomic_inc(&oldmm->mm_count); // 由于即将进入内核线程，将当前CPU置为lazy tlb模式 // 因为内核线程并不访问用户空间，所以无需刷新页表 enter_lazy_tlb(oldmm, next, this_cpu); // 后一进程为普通进程，需要切换用户空间 } else { // 普通进程的mm和active_mm应该相同 if (next->active_mm != mm) BUG(); switch_mm(oldmm, mm, next, this_cpu); } // 如果被切换走的是内核线程，则归还他借用的进程用户空间 if (!prev->mm) { prev->active_mm = NULL; mmdrop(oldmm); }除了上述注释，补充说明如下4个问题， ① 内核线程为何要借用用户空间 内核线程访问内存时也是需要页表进行地址转换的，只是此时要使用的是内核页表，而内核页表是所有进程共享的。所以通过借用前一进程的用户空间，就可以正确访问内核空间 而正是这种用户空间的借用，使得切换到内核线程时无需进行页表集的切换，代价更小（这也是goodness函数中奖励这种行为的原因） ② 进程页表和内核页表 上文中提到的内核页表是所有进程共享的，这种共享在实现上就是进程页表的内核态部分是内核页表swapper_pg_dir的拷贝（在创建进程的pgd时进行拷贝） 这里就涉及一个如何将内核页表的修改同步到进程页表的问题，在Linux内核中，是将该同步推迟到第一次真正访问vmalloc分配的内核地址空间时，由内核空间的缺页异常进行处理 更进一步的细节本篇笔记不展开，可先参考如下blog： https://blog.csdn.net/l1259863243/article/details/54175300 ③ switch_mm的实现
可见switch_mm函数只做2件事儿，处理lazy tlb + 切换页表 ④ mmdrop的实现
可将当mm_struct的mm_count字段为0时，将释放该结构 4.7 Linux 2.6调度程序的改进随着Linux内核版本的更新，调度程序越来越复杂，此处不再详细说明新版调度程序的实现方式，只是列出Linux 2.4版本调度程序的不足，以指明改进的方向 4.7.1 单就绪队列问题① 即使时间片耗尽的进程，依然在就绪队列中，这就使得这些不可能被调度的进程仍然参与调度，浪费了遍历就绪队列的时间 ② 调度算法与就绪队列的长度密切相关，队列越长，挑选一个进程的时间就越长，不适合用在硬实时系统中 4.7.2 多处理器问题① 多个处理器的进程放在同一个就绪队列中，使得就绪队列称为临界资源，各个处理器为等待进入就绪队列而降低了系统效率 ② 后续版本中每个核有自己的就绪队列 4.7.3 内核态不可抢占问题① Linux 2.4版本是不支持内核抢占的，Linux 2.6版本才开始支持 ② 上文中将task_struct结构的need_resched字段置为1实现的是用户态抢占，此时如果内核从系统调用或者中断处理程序返回用户态，都会检查need_resched标志，如果被设置，内核会选择一个最合适的进程投入运行 ③ 所有抢占，包括内核态抢占，都是有时机的，比如从中断处理程序返回等。在支持内核抢占的内核中，只要重新调度是安全的，就可以抢占当前正在运行的任务 参考资料： https://blog.csdn.net/gatieme/article/details/51872618 4.8 O(1)调度简介 4.8.1 O(1)调度器中的就绪队列注：基于Linux 2.6.11
① 每个CPU均有一个就绪队列 ② O(1)调度器的基本优化思路就是把原先就绪队列上的单个链表根据优先级组织为多个链表，每个优先级的进程被加入不同链表中 ③ O(1)支持140个优先级，因此队列成员中有140个分别表示各个优先级的链表表头；bitmap表示各个优先级进程链表是空还是非空；nr_active表示这个队列中有多少任务 在这些队列中，100 ~ 139是普通进程的优先级，其余为实时进程优先级，由于不同类型的进程被区分开，普通进程不会影响实时进程的调度 ④ 就绪队列中有2个优先级队列，active队列管理时间片还有剩余的进程；expired队列管理时间片耗尽的进程 随着系统运行，active队列的任务耗尽时间片，被挂入expired队列，当active队列为空时，两个队列互换，开始新一轮的调度过程 4.8.2 O(1)进程调度
① 系统中所有就绪进程首先经过负载均衡模块，然后挂入各个CPU上的就绪队列 ② 主调度器（即schedule函数）和周期性调度器驱动CPU上的调度行为，其基本思路是从active队列的bitmap中寻找第一个非空的进程链表（即当前优先级最高的进程链表），让后调度该链表的第一个结点进程，因此时间复杂度为O(1) 4.9 机制与策略分离的调度模型
核心调度曾仍然分为两个部分， ① 通过负载均衡模块将各个就绪状态的任务分配到各个CPU的就绪队列 ② 各个CPU上的主调度器（Main scheduler）和周期性调度器（Tich scheduler）的驱动下进行单个CPU上的调度 调度器处理的任务各不相同，有实时任务（RT task）、普通任务（Normal task）和最后期限任务（Deadline task）等，无论是哪种任务，他们都有共同的逻辑，这部分就构成了核心调度层 4.9.2 策略：调度类（specific scheduler）各种特定类型的调度器可以定义自己的调度类（sched_class），并以链表形式加入到系统中。这样就实现了机制和策略的分离，用户可以根据自己的场景定义特定的调度器，而不需要改动核心调度层的逻辑 下面简要介绍调度器类的核心成员，
next：指向下一个比自己低一级的优先级调度类 enqueue_task：指向入队函数 dequeue_task：指向出队函数 check_preempt_curr：表示当前CPU上正在运行的进程是否可以被抢占 pick_next_task：从就绪队列中选择一个最适合运行的进程，是调度器类的核心操作 CFS调度器类的定义如下图所示，
在copy_process函数中会调用sched_fork函数，该函数中会设置新创建进程的调度类
① CFS调度器的目标是保证每个进程的完全公平调度 ② CFS调度器没有时间片的概念，而是分配CPU使用时间的比例 ③ 在实现层面，CFS通过每个进程的虚拟运行时间（vruntime）来衡量哪个进程最值得被调度，而虚拟运行时间是通过进程的实际运行时间和进程的权重（weight）计算出来的 ④ CFS中的就绪队列是一颗以虚拟运行时间为键值的红黑树，虚拟运行时间越小的进程越靠近整个红黑树的最左端，因此调度器每次选择位于红黑树最左端的进程运行
⑤ 在CFS调度器中，弱化了进程优先级的概念，而是强调进程的权重。一个进程权重越大，越说明这个进程需要运行，因此他的虚拟运行时间就越小，这样被调度的机会就越大 5. 进程的创建 5.1 内核中的特殊进程注：本节以Linux 2.6版本为例 5.1.1 0号进程① 由上文可知，0号进程是系统中唯一一个静态分配的进程，他的PCB被静态地分配在内核数据段中，永远不会被撤销 而其他进程的PCB在运行的过程中由系统根据当前的内存状况随机分配，撤销时再归还给系统 ② 从系统启动以来运行的进程，就是0号进程 ③ start_kernel函数调用rest_init函数之后，最终会进入cpu_idle函数，至此start_kernel就退化为idle process ④ 0号进程在很多链表中起到链表头的作用，当就绪队列中没有其他进程时，就会调度0号进程，cpu_idle中会进行pm_idle操作，以达到节电的目的 5.1.2 1号进程① 1号进程由rest_init函数调用kernel_thread函数生成
② kernel_init在完成进一步初始化之后，会运行用户态的init进程，至此1号进程成为所有用户态进程的祖先进程 ③ 首先会通过do_execve函数尝试运行/init，之后会按顺序尝试，只要有1个进程能运行成功即可
① 2号进程也由rest_int函数调用kernel_thread函数生成
② kthreadd进程在kthread_create_list链表为空时进入睡眠，当被唤醒时，根据请求建立内核进程，进而成为所有内核进程的祖先进程
③ 唤醒2号进程的方式就是调用kthread_create函数请求创建新的内核进程，该函数在将请求加入kthread_create_list列表后，就会唤醒2号进程
① 进程是系统资源分配的基本单位，线程是独立运行的基本单位 ② 进程和线程几乎共享所有资源，包括代码段、数据段、进程地址空间和打开的文件等，线程只拥有自己的寄存器和栈 下面就分析一下Linux内核中如何实现这种资源的共享，以及如何将线程作为轻量级的运行单位 5.2.2 Linux对进程和线程的统一描述
Linux内核使用唯一的数据结构task_struct来表示进程、线程和内核线程，并使用相同的调度算法对这三者进行调度（这就体现了为什么线程是独立运行的基本单位） 5.2.3 Linux对进程和线程的统一创建
① 创建进程和创建线程在用户态使用不同的API，在内核态也对应不同的系统调用 ② 但是最终都是调用do_fork函数实现新进程 / 线程的创建，只是调用时传递的参数不同 5.2.3.1 do_fork函数原型
clone_flags：拷贝参数及各种各样的标志信息，这是不同调用者的主要差别，即从父进程中拷贝不同的资源 stack_start：表示把用户态栈指针赋值给子进程的esp寄存器（调用进程应该总是为子进程分配新的栈） regs：指向通用寄存器组的指针，通用寄存器的值在从用户态切换到内核态时被保存在内核态栈中 statck_size：未使用，总是被设置为0 parent_tidptr：指向父进程的用户态变量地址 child_tidprt：指向新轻量级进程的用户态变量地址 5.2.3.2 sys_fork创建进程
① 指定SIGCHLD标志，标识要生成子进程，此时父进程会以写时拷贝技术和子进程共享资源 5.2.3.3 sys_vfork创建进程
① 指定SIGCHLD标志的含义与sys_fork相同 ② 指定CLONE_VFORK标志，标识父进程要等待子进程先运行，之后再继续运行 ③ 指定CLONE_VM标志，标识共享描述符和所有页表 ④ 指定SIGCHLD标识该信号 说明：目前因为写时拷贝技术更高效，vfork已被取代 5.2.3.4 sys_clone创建用户态线程
① sys_clone中指定的标志通过寄存器传递，实际内容为CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND ② 指定CLONE_FS，标识共享根目录和当前工作目录所在的表 ③ 指定CLONE_FILES，标识共享打开文件表 ④ 指定CLONE_SIGHAND，标识共享信号处理程序表 5.2.3.4 创建内核态线程
无论是创建内核进程还是用户进程，最终都是由内核态的do_fork函数完成，此处简介该函数都做了哪些工作
1. 调用alloc_task_struct在slab上分配PCB 2. 调用alloc_thread_info在buddy上分配进程内核栈 3. 把父进程PCB的内容拷贝到刚刚分配的新进程PCB中，此时二者是完全相同的 4. 检查新创建这个子进程后，当前用户所拥有的资源数量有没有超过限制 5. 将子进程状态设置为TASK_UNINTERRUPTIBLE，以确保他不会被立即调度 6. 为新进程获取有效的PID 7. 更新不能从父进程继承的PCB其他域，比如进程间的亲属关系等 8. 根据传递的clone_flags拷贝或共享打开的文件、文件系统信息、信号处理函数、进程的虚拟地址空间等 9. 把新的PCB插入进程链表，以确保进程间的亲属关系 10. 把新的PCB插入哈希表 11. 把子进程PCB的状态置为TASK_RUNNING，并调用wake_up_process，把子进程插入到就绪队列 12. 让父进程和子进程平分剩余的时间片 13. 返回子进程的PID，这个PID最终由用户态下的父进程读取 说明1：写时拷贝技术 Linux的fork使用写时拷贝（Copy-on-write）来实现，在do_fork中内核并没有把父进程的全部资源给子进程复制一份，而是将这些内容设置为只读状态，当父进程或子进程试图修改这些内容是，内核才在修改之前将被修改的部分进行拷贝（具体可见下一章内存管理笔记） 说明2：fork之后的父子进程谁先运行 fork之后的父子进程执行的先后顺序是由调度程序决定的，但是根据我们对Linux 2.4版本调度程序的分析，调度程序是倾向于让父进程先运行的，因为运气好的话可以减少一次进程切换（我进行了一个简单测试，也确实是父进程先运行） 但是从写时拷贝的角度分析，先运行子进程可以减少浪费，主要有2点依据， ① 如果父进程随后修改了共享的内容，就必须为子进程单独复制一份 ② 子进程被创建后，一般都是调用execve函数运行一个新的程序，所以先运行子进程可以避免不必要的拷贝 如果想控制子进程先运行，可以使用vfork系统调用，在do_fork的内核实现中，如果指定了CLONE_VFORK标志，父进程就会等待子进程运行之后再运行
注：由于fork使用写时拷贝技术，vfork在克隆父进程地址空间上的优势已不再存在 6. 实例：系统负载检测模块 6.1 正确理解系统负载 6.1.1 查看系统负载使用uptime或top命令可以查看当前系统的平均负载，load_average会分别显示最近1分钟、5分钟和15分钟的CPU平均负载值
单位时间内系统处于可运行状态（TASK_RUNNING）和不可打断状态（TASK_UNINTERRUPTIBLE）的平均进程数 6.1.3 单核系统负载图示
以车道模拟系统负载，当系统负载达到1.0时，说明任务已将CPU占满；当系统负载达到1.7时，说明等待的任务达到已经超过CPU可执行任务的70% 6.2 平均负载与CPU核心数的关系① 多CPU可分为多处理器和多核处理器，多处理器即计算机系统中有多个物理CPU；多核处理器表示单个物理CPU中有多个单独的并行工作单元 ② 使用nproc（print the number of processing units available）命令可以查看当前系统的计算单元个数
③ 多核心相当于多车道
负载检测模块需要完成如下3个子任务， ① 获取系统负载值 ② 定时检测系统当前负载是否超过阈值 ③ 当系统负载超过阈值时，打印所有线程的调用栈 下面我们逐个任务来说明 特别注意：该模块调用的很多函数在旧版本内核中没有，实测时使用的系统为Ubuntu 16.04（Linux 4.15.0） 6.3.1 获取系统负载值系统负载值存储在avenrun数组中，分别存储最近1分钟、5分钟和15分钟的系统负载
此处说明2点， ① Linux内核不支持浮点数，所以以unsigned long类型存储系统负载，其中低11位存储的是小数部分 ② 考虑到有些版本可能没有将avenrun数组export symbol，代码中使用kallsyms_lookup_name函数获取其地址 6.3.1.1 获取avenrun数组地址 static unsigned long *ptr_avenrun; ptr_avenrun = (void *)kallsyms_lookup_name("avenrun"); if (!ptr_avenrun) return -EINVAL;6.3.1.2 检查平均负载值 #define FSHIFT 11 /* nr of bits of precision */ #define FIXED_1 (1 FSHIFT) #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100) static void check_load(void) { static ktime_t last; u64 ms; int load = LOAD_INT(ptr_avenrun[0]); // 最近1分钟的Load值 // 当负载小于3时，直接返回 if (load < 3) return; /** * 如果上次打印时间与当前时间相差不到20秒，就直接退出 */ ms = ktime_to_ms(ktime_sub(ktime_get(), last)); if (ms < 20 * 1000) return; last = ktime_get(); print_all_task_stack(); // 打印所有线程的调用栈 } 6.3.2 定时检测系统负载此处使用高精度定时器实现对系统负载的定时检查 struct hrtimer timer; static enum hrtimer_restart monitor_handler(struct hrtimer *hrtimer) { enum hrtimer_restart ret = HRTIMER_RESTART; // 重启定时器 check_load(); // 检查系统负载 // 重置定时器到期时间为当前时间 + 10ms hrtimer_forward_now(hrtimer, ms_to_ktime(10)); return ret; } static void start_timer(void) { hrtimer_init(&timer, CLOCK_MONOTONIC, HRTIMER_MODE_PINNED); timer.function = monitor_handler; // 定时器到期时间为当前时间 + 10ms hrtimer_start_range_ns(&timer, ms_to_ktime(10), 0, HRTIMER_MODE_REL_PINNED); } 6.3.3 打印所有线程调用栈 #define BACKTRACE_DEPTH 20 static void print_all_task_stack(void) { struct task_struct *g, *p; unsigned long backtrace[BACKTRACE_DEPTH]; // 最多获取20层调用栈 struct stack_trace trace; memset(&trace, 0, sizeof(trace)); memset(backtrace, 0, BACKTRACE_DEPTH * sizeof(unsigned long)); trace.max_entries = BACKTRACE_DEPTH; trace.entries = backtrace; // 使用backtrace数组存储调用栈 printk("\tLoad: %lu.%02lu, %lu.%02lu, %lu.%02lu\n", LOAD_INT(ptr_avenrun[0]), LOAD_FRAC(ptr_avenrun[0]), LOAD_INT(ptr_avenrun[1]), LOAD_FRAC(ptr_avenrun[1]), LOAD_INT(ptr_avenrun[2]), LOAD_FRAC(ptr_avenrun[2])); printk("current: %d --> %s\n", current->pid, current->comm); printk("dump all task: \n"); // 上RCU读锁 rcu_read_lock(); printk("dump running task.\n"); do_each_thread(g, p) { if (p->state == TASK_RUNNING) { printk("running task, comm: %s, pid %d\n", p->comm, p->pid); // 每次打印都要初始化backtrace，否则会打印其他线程的调用栈 memset(&trace, 0, sizeof(trace)); memset(backtrace, 0, BACKTRACE_DEPTH * sizeof(unsigned long)); trace.max_entries = BACKTRACE_DEPTH; trace.entries = backtrace; // 获取并打印线程调用栈 save_stack_trace_tsk(p, &trace); print_stack_trace(&trace, 0); } } while_each_thread(g, p); printk("dump uninterrupted task.\n"); do_each_thread(g, p) { if (p->state & TASK_UNINTERRUPTIBLE) { printk("uninterrupted task, comm: %s, pid %d\n", p->comm, p->pid); memset(&trace, 0, sizeof(trace)); memset(backtrace, 0, BACKTRACE_DEPTH * sizeof(unsigned long)); trace.max_entries = BACKTRACE_DEPTH; trace.entries = backtrace; save_stack_trace_tsk(p, &trace); print_stack_trace(&trace, 0); } } while_each_thread(g, p); rcu_read_unlock(); }说明：do_each_thread & while_each_thread宏 这2个宏按如下形式成对调用， do_each_thread(g, p) { } while_each_thread(g, p);这2个宏定义如下，
展开后形式如下， // 遍历过程也体现出为何要上rcu读锁 #define next_task(p) \ list_entry_rcu((p)->tasks.next, struct task_struct, tasks) static inline struct task_struct *next_thread(const struct task_struct *p) { return list_entry_rcu(p->thread_group.next, struct task_struct, thread_group); } for (g = t = &init_task; (g = t = next_task(g)) != &init_task;) do { } while ((t = next_thread(t)) != g)此处就体现出了Linux内核中多进程和多线程的关系，即一个进程之中的多个线程tgid字段相同但pid字段不同 根据代码，在Linux内核中，先按进程组织在tasks字段表示的链表中；进程的线程又组织在进程的thread_group链表中 线程栈打印效果如下图所示，
验证：Linux中进程与线程的组织方式 上文中提到Linux内核中先按进程组织，然后线程又被组织在进程中，也就是说进程起到了线程组的作用，下面通过实验加以验证 测试用例如下， #include #include #include #include #include #include // gettid系统调用没有封装例程 #define gettid() syscall(__NR_gettid) void *th_fn(void *arg) { printf("th_fn run\n"); printf("th_fn getpid() = %d\n", getpid()); printf("th_fn gettid() = %ld\n", gettid()); sleep(1000); return (void *)0; } int main(void) { pthread_t thread; printf("main thread run\n"); printf("main getpid() = %d\n", getpid()); printf("main gettid() = %ld\n", gettid()); pthread_create(&thread, NULL, th_fn, NULL); sleep(1000); return 0; }从用户态打印结果分析，主线程和子线程是两个调度实体，对应内核态中的两个task_struct结构
之后加载上文中提到的打印进程链表的内核模块，从内核态打印分析，进程链表中只有主线程的task_struct，并没有子线程的task_struct
结论： ① Linux中的进程是资源分配的基本单位，线程是调度的基本单位 ② 进程内的所有线程构成线程组，其中主线程是线程组的组长，主线程的pid就是该线程组的tgid ③ 从用户态视角，进程中的所有线程有相同的pid，其实获取的是每个线程的tgid |
【本文地址】