本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-process-address-space/ 看完 Linux kernel block I/O 层之后来到进程地址空间管理部分，本文中的很多知识和之前的 [进程基本]、[进程调度]、[内存管理] 等章节的知识相关。 1、基础知识： Linux kernel 给每个进程提供的进程地址空间一般是 32 位或 64 位（硬件相关）的平坦地址空间，但进程是没有权限访问这段地址空间中的所有地址的，能访问的一般是很多的内存地址区间。这种内存地址区间被称为内存区域，进程可以动态添加和删除内存区域到它的地址空间中。内存区域可以有不同的权限，相关进程必须遵守这些权限，例如可读、可写、可执行等。如果进程访问的地址不在一个有效的内存区域中，或者访问时的权限不正确，kernel 将会杀掉进程并给出常见的 “Segmentation Fault” 段错误日志。 内存区域通常包括： 可执行文件的代码段，称为 text 段； 可执行文件的已初始化全局变量段，称为 data 段； 未初始化全局变量段（通常以 0 page 填充），称为 bss 段； 进程的用户空间栈（通常以 0 page 填充）； 每个共享库文件的额外 text、data、bss 段，也被装入进程的地址空间； 内存映射文件； 共享内存区域； 匿名内存映射（新版本的 malloc 函数就除了 brk 之外也通过 mmap 实现）； 应用程序中的堆 2、内存描述符： kernel 使用 mm_struct 内存描述符结构来表示进程的地址空间信息，它定义在 <linux/mm_types.h> 头文件中，这也是一个非常大的结构。 结构的注释中已经包含比较多的注解了哦。mmap 为地址空间的内存区域（用 vm_area_struct 结构来表示啦，也是上面的代码中）链表，mm_rb 则将其以红黑树的形式进行存储，链表形式方便遍历，红黑树形式方便查找。mm_users 为以原子变量形式保护的使用此地址空间的进程数量值（例如：如果有 4 个线程共享此地址空间，则 mm_users 值为 4），mm_count 为引用计数（所有 mm_users 等于一个引用计数），当 mm_count 值为 0 时表示没有再被使用，可以被释放。total_vm 成员表示所有内存区域的数量。 所有的 mm_struct 结构以链表的形式存在 mm_struct 的 mmlist 成员中，该链表的第一个成员就是 init 进程的 mm_struct ：init_mm，该链表被 mmlist_lock 锁保护。 进程的内存描述符是在 task_struct 的 mm 成员中的。fork() 进行创建进程时调用 copy_mm 函数将父进程的内存描述符拷贝给子进程，调用 clone() 函数时如果指定 CLONE_VM 参数将使父进程和子进程地址空间共享（实际上将 mm_users 计数加 1），这种子进程就被称为线程。mm_struct 结构一般是通过 alloc_mm 宏从名为 mm_cachep 的 Slab cache 中分配。 进程退出时调用 exit_mm 函数，该函数再调用 mmput() 函数，此函数中减小地址空间的 mm_users 计数，如果 mm_users 变为 0，调用 mmdrop() 函数减小 mm_count 计数，如果 mm_count 变为 0，则最终调用 free_mm() 宏来释放内存描述符（回归到 Slab cache 中）。 另外需要说明的是 kernel 线程是没有地址空间，也就没有对应的 mm_struct（值为 NULL），kernel 线程使用之前运行的进程的内存描述符，有关 kernel 线程请参考之前的 [进程基本] 文章。 3、VMA 概念： vm_area_struct 结构即内存区域常被称为虚拟内存区域（简写为 VMA），表示的是在一个地址空间中的一个连续内存地址区间，每个内存区域是一个惟一的对象。vm_area_struct 中的 vm_mm 成员指向关联的内存描述符，vm_ops 成员为非常重要的关联的操作函数结构，vm_start 为起始地址，vm_end 为结束地址之后第一个字节的地址，即地址范围为：[vm_start, vm_end)。每个 VMA 对于它关联的内存描述符来说是惟一的，因此如果两个单独的进程映射相同的文件到各自的地址空间，它们的 VMA 也是不同的。 VMA 中的 vm_flags 表示内存区域中的页的行为状态，常见的状态有：VM_READ（页可读）、VM_WRITE（页可写）、VM_EXEC（页可被执行）、VM_SHARED（页被共享，被设置了称为共享映射，未设置称为私有映射）、VM_SHM（此区域被用作共享内存）、VM_LOCKED（页被锁）、VM_IO（此区域用于映射设备 I/O 空间）、VM_RESERVED（表示内存区域不可被交换出去）、VM_SEQ_READ（连续读，增强 readahead）、VM_RAND_READ（随机读，减弱 readahead）等。VM_SEQ_READ 和 VM_RAND_READ 标志可以通过 madvise() 系统调用来设置。 看看 vm_ops 操作函数结构的 vm_operations_struct 的定义，它在 <linux/mm.h> 头文件中： 当指定的内存区域被添加到地址空间时，open 函数被调用，反之移除时 close 函数被调用。如果一个不在内存中的页被访问，将触发缺页异常， fault 函数被缺页异常处理函数调用。当一个只读的页变为可写的时候，page_mkwrite 函数也被缺页异常处理函数调用。 mm_struct 中的 mmap 为内存区域链表，通过 VMA 的 vm_next 成员指向下一个内存区域，而且链表中的内存区域是按地址上升排序的，链表中最后一个 VMA 值为 NULL。而对于 mm_struct 的 mm_rb 红黑树，mm_rb 为红黑树的根，每个 VMA 通过其 vm_rb 红黑树节点类型链到红黑树中。 在应用层中可以通过 cat /proc/<pid>/maps 或者 pmap 程序等方法查看应用程序的内存区域列表。 操作 VMA： kernel 提供 find_vma() 函数用于查找指定的内存地址在哪个 VMA 上，它的实现在 mm/mmap.c 文件中，输入参数为内存描述符和内存地址： 如果找不到对应的 VMA 则返回 NULL。需要注意的是返回的 VMA 的开始地址可能比指定的内存地址大。find_vma() 函数返回的结果会被缓存到内存描述符的 mmap_cache 成员中用于提高之后的查找性能，因为后续的操作很可能还是在同样的 VMA 上。如果在 mmap_cache 中找不到则通过红黑树进行查找。 find_vma_prev() 函数与 find_vma() 函数类似，不过它也会返回指定地址之前的最后一个 VMA： struct vm_area_struct * find_vma_prev(struct mm_struct *mm, unsigned long addr, struct vm_area_struct **pprev) kernel 另外还提供了 find_vma_intersection() 函数返回符合 find_vma() 的条件并且其开始地址不在指定内存结束地址之后的 VMA。 4、mmap 和 munmap： kernel 提供 do_mmap() 函数创建新的线性地址区间，这是用户层 mmap() 函数的底层实现，它用于将一段地址区间添加到进程的地址空间中。 unsigned long do_mmap(struct file *file, unsigned long addr, unsigned long len, unsigned long prot, unsigned long flag, unsigned long offset) do_mmap 映射 file 参数指定的文件，并最终返回新创建的地址区间的初始地址。 offset 和 len 指定偏移量和长度。如果 file 为 […]
Tag: Process
Linux kernel学习-进程调度
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-process-scheduling/ 接着上面进程基本概念的文章，进程调度器决定系统中什么进程需要运行，运行多长时间。Linux kernel 实现的是抢占式的时间片调度方式，而不是进程主动让出时间片的方式。 Linux 从 2.5 开始使用名为 O(1) 的调度器，它解决了 2.4 及之前早期的调度器中很多设计上就存在的问题，O(1) 就表示该算法可以在常数时间内完成工作。在 ULK3 对应的 2.6.11 内核中仍然在使用此调度器，它对于很大的服务器负载的情况是很理想的，但由于 O(1) 调度器对于延迟敏感的程序（被称为交互式进程）而言却有缺陷，因此从 2.6.23 内核开始 Linux 引入一种调度器类的框架，并且默认使用一种新的调度器：Completely Fair Scheduler（CFS）完全公平调度器，鉴于历史的车轮在前进着，本文就主要讨论 CFS 调度器了。 进程通常可以分为两类：I/O密集型 和 计算密集型。I/O密集型进程花费更多的时间在等待 I/O 请求上（不一定是磁盘I/O，也可以是键盘、网络 I/O 等），大多数的 GUI 程序都是 I/O密集型进程。计算密集型的进程则要求运行频率小些但运行时间更多，像各种加解密程序和 MATLAB 这种就是典型的计算密集型进程。一个好的调度策略应该能同时满足低延迟和高吞吐量，Linux 调度器会采取偏向I/O密集型进程的策略。 Linux kernel 实现了两种独立的进程优先级：一种是 nice 值，从 -20 到 +19，默认值为 0，越大的值表示优先级越低（表示你对其它进程更加 “nice”，哈哈），nice 值在所有 Unix 系统中是一个通用的进程优先级范围，运行 ps -el 可以看到进程的 nice 值；第二种是可配置的实时优先级，范围从 0 到 99，越大的值表示优先级越高，实时进程比普通进程的优先级高，Linux 根据 POSIX.1b Unix 标准实现了实现了实时优先级，运行 ps 时增加 rtprio 参数可以在 RTPRIO 栏中看到实时优先级（如果值为 - 表示不是实时进程）。 Linux 2.6.34 默认的 CFS 完全公平调度器并不像传统调度器那样，根据 nice 绝对值为相应的进程分配固定的时间片，它没有明确的时间片概念，而是根据每个进程的 nice 相对差异值作为权重得到进程可以运行的时间在处理器时间中的比例。CFS 设置了一个预定的 targeted latency 值作为调度持续时间来根据比例计算时间片，当然此值越小越接近完全公平。假设 targeted latency 值为 20 毫秒，系统中有两个进程 nice 值分别为 0 和 5，根据权重计算出来的时间片分别为 15 和 5 毫秒，当两个进程为 10 和 15 时，计算出来的仍然为 15 和 5 毫秒，因为 nice 值的相对差异值并没有变。在系统中进程不是特别多时，CFS 调度器可以做到接近完全公平，而进程数量特别多甚至接近无限时，每个进程获得的时间片将非常小，为了避免进程切换导致的开销，CFS 又规定了一个 minimum granularity 值作为每个进程最小的时间片，默认为 1 毫秒，也即即使进程无限，每个进程也最少能运行 1 毫秒的时间，因此进程特别多时 CFS 就不会那么公平了。 1、CFS调度器： CFS 调度器实现在 kernel/sched_fair.c 文件中，这在上面一篇博文：进程基本 中有简单的介绍的。CFS 使用 sched_entity 调度实体结构，task_struct 中就有这个成员，看看 sched_entity 的定义，它定义在 include/linux/sched.h 头文件中： 可以看到此结构中下面很大一部分是开启了 CONFIG_SCHEDSTATS 之后才有用的。其中 vruntime 为进程的虚拟运行时间（实际运行时间经可运行的进程个数进行权重计算后的结果），在理想的 CFS 环境中，处理器都处于理想状态，所有同级别的进程的 vruntime 值应该都相同。但实际上多处理器不能做到完美多任务，CFS 调度器就用 vruntime 记录进程的运行时间并得到它应当还要运行多长时间。 再看到下面会用到的 cfs_rq 运行队列属性的定义，在 kernel/sched.c 中定义： cfs_rq 中的 curr 字段即指向当前队列上正在运行的实体（如果没有则为 NULL 了），rq 字段即为 CPU 运行队列。 来看看 sched_entity 的 vruntime 是如何在 update_curr 函数中更新的： update_curr 会被系统定时器周期性的调用，进程转变为可运行或不可运行状态时都会被调用，而 update_curr 本身则调用 __update_curr 增加实际运行时间和 vruntime 虚拟运行时间。 由于实际情况下，每个进程的 vruntime 并不会像理想状况那样完全一样，CFS 调度器在需要调度时从运行队列里中取 vruntime 最小的那个进程来运行。CFS 调度器使用一个红黑树来管理可运行进程的列表，并用于快速查找最小的 vruntime 进程。 红黑树在 Linux 中被称为 rbtree，可以用于存储任意数据的节点，由特定的关键字来标识。sched_entity 调度实体中的 run_node 就是一个红黑树节点，cfs_rq 中的 rb_leftmost 即是红黑树最左边的节点（缓存在 cfs_rq 结构中以加快访问速度，这样可以避免遍历红黑树），最小的 vruntime 进程就在此节点上，如果找不到此进程（返回 NULL），CFS 唤醒 idle 任务。 看看将进程加到红黑树的实现： enqueue_entity 中更新了当前进程的 vruntime，并最终调用 __enqueue_entity 将进程加到红黑树中。__enqueue_entity 中先通过遍历找到正确位置，遍历过程中就能确定红黑树中最左边的节点是什么，然后设置红黑树中节点左右信息，调用 rb_link_node 添加节点，必要时更新 cfs_rq 中保存的最左边的节点缓存。 好吧，看了添加过程再看从红黑树中删除进程： 同样 dequeue_entity 先调用 update_curr 更新当前进程的 vruntime，删除的实际操作由 __dequeue_entity 来完成。__dequeue_entity 中判断如果最左边节点正是要删除的进程，必须更新最左边的节点缓存，然后调用 rb_erase 删除节点。 Linux 中进程调度入口是 schedule() 函数，定义在 kernel/sched.c 中。对于一个进程，schedule() 会先查找最高优先级的调度器类并调用此调度器类中的函数进行调度。看看 pick_next_task 的实现： 首先由于 Linux 普通进程默认使用 CFS 调度器，pick_next_task 先判断是不是所有进程都在 CFS 调度器中，如果是就直接调用 CFS 的 pick_next_task 函数节省遍历时间。sched_class_highest 的定义在上面也可以看到，就是 RT 调度器类，for_each_class 用于遍历调度器类。而其它类中找不到时，idle 调度器类的 pick_next_task 就返回一个有效 task_struct。在 CFS 调度器中 pick_next_task 会调用 pick_next_entity 函数选择下一个运行的进程。 2、睡眠与唤醒： 进程需要睡眠时，kernel 的处理大体如下：进程将自己标记为睡眠状态，将自己加到等待队列，从记录可运行进程的红黑树上删除自己，调用 schedule() 选择新进程来运行，schedule() 会调用 deactivate_task() 函数将进程从运行队列中移除。唤醒的过程则相反：进程被设置为可运行，从等待队列删除，重新加回到红黑树中。 等待队列在 kernel 中以 wait_queue_head_t 表示，定义在 include/linux/wait.h 头文件中，它其实是一个 __wait_queue_head 结构，下面的头文件中有一些经常用到的声明： 需要注意的是每个等待队列都需要可以在中断时被修改，因此操作等待队列之前必须获得一个自旋锁。而在实际使用中等待时需要处理竟态条件，为此 kernel 定义了几个很好用的等待条件的宏，为调用者减少操作，这些宏也是定义在上面的文件中。常用的有 wait_event 根据条件在队列上无限等待，wait_event_timeout 相对加了超时处理，它是调用 schedule_timeout 进行调度，wait_event_interruptible 即在等待时进程是可以响应信号之类的唤醒。 内核中的 completion 完成量机制也是基于等待队列的，用于等待某一操作结束。__wait_queue 结构的 task_list 成员通过双链表链接到 __wait_queue_head 中，__wait_queue 中的 private 成员指向等待进程的 task_struct。__wait_queue 中 […]
Linux kernel学习-进程基本
本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-process/ Linux 中进程通过 fork() 被创建时，它差不多是和父进程一样的，它得到父进程的地址空间拷贝，运行和父进程一样的代码，从 fork() 的后面开始执行，父进程和子进程共享代码页，但子进程的 data 页是独立的（包括 stack 和 heap）。 早期的 Linux kernel 并不支持多线程的程序，从 kernel 来看，一个多线程的程序只是一个普通的进程，它的多个执行流应该完全在 user mode 来完成创建、处理、调度等操作，例如使用 POSIX pthread 库。当然这样的实现是无法让人满意的，Linux 为此使用轻量级进程为多线程程序提供更好的支持，两个轻量级进程可以共享资源（例如：地址空间、打开的文件等等），一个比较简单的方法是将为每个线程关联一个轻量级进程，这样每个线程可以被 kernel 单独调度，使用 Linux 轻量级进程的库有：LinuxThreads、NPTL、NGPT 等。Linux kernel 同时也支持线程组（可以理解为轻量级进程组）的概念。 1、进程描述符： 进程描述符由 task_struct 结构来表示，一般来说，每个可以被独立调度的执行上下文都必须有自己的进程描述符，因此尽管轻量级进程共享了很大一部分 kernel 数据结构，它也必须有自己的 task_struct。task_struct 中包含关于一个进程的差不多所有信息，它定义在 include/linux/sched.h 文件中，你会看到这是非常大的结构，其中还包含指向其它结构的指针。访问进程自身的 task_struct 结构，使用宏操作 current。 task_struct 中的 struct mm_struct *mm 即指向进程的地址空间。task_struct 的 state 字段表示进程的运行状态，取值有 TASK_RUNNING（正在运行或正在队列中等待运行，进程如果在用户空间只能为此状态）、TASK_INTERRUPTIBLE（可响应信号）、TASK_UNINTERRUPTIBLE（不响应信号）、TASK_STOPED 等，另外 state 还有特殊的两个值是 EXIT_ZOMBIE（僵尸进程） 和 EXIT_DEAD（进程将被系统移除）。kernel 提供 set_task_state 宏修改进程状态，set_task_state 最终调用 set_mb，set_current_state 用于当前进程的状态。task_struct 的 pid 字段就是咱们喜闻乐见的进程 ID 了。 这是一个典型的 Linux 进程状态机图： POSIX 1003.1c 标准规定一个多线程程序的每个线程都应该有相同的 PID，这样的好处是例如发一个信号给一个 PID，一个线程组里的所有线程都能收到。同一线程组中的线程有相同的线程组号（Thread Group ID），线程组组号放在 task_struct 的 tgid 成员变量中，一般是线程组里的第一个轻量级进程的 PID。特别需要注意 getpid() 系统调用返回的就是 tgid 的值，而不是 pid 值，这样一个多线程程序的所有线程可以共享一个 PID。 对每个进程，kernel 在通过 slab 分配器分配 task_struct 时，通常是实际分配了两个连续的物理页面（8KB），以 thread_union 联合表示，其中包括一个 thread_info 结构（其 task 成员是指向 task_struct 的指针）以及 kernel 模式的进程堆栈。esp CPU 堆栈指针即表示此进程堆栈的栈顶地址，进程从用户模式切换到 kernel 模式时，kernel 堆栈会被清空。为了效率考虑，kernel 会将这两个连续的物理页面的第一个页面按 2^13（也就是 8KB） 对齐，为了避免内存较少时产生问题，kernel 提供配置选项（就是下面的 THREAD_SIZE 了）可以将 thread_info 和堆栈包含在一个页面也就是 4KB 的内存区域里。一般来说，8KB 的堆栈对于内核程序已经够用。 看看 Linux 2.6.34 中 thread_union 的定义： 由于 thread_info 和内核堆栈是合并在连续的页面里的，kernel 就可以从 esp 指针得到 thread_info 结构地址，这是通过 current_thread_info 函数来实现的。 假设 thread_union 是 8KB 大小，也即 2^13，将 esp 的最低 13 位屏蔽掉即可得到 thread_info 的地址，如果是 4KB 的栈大小，屏蔽掉最低 12 位即可（和上面的代码一致），这样通过 current_thread_info()->task 就能得到当前的 task_struct，这就是 current 宏的实现了。 系统中进程的列表保存在 init_task 所在的双向链表中，task_struct 的 tasks 字段就是 list_head，init_task 表示的就是 PID 为 0 的 swapper 进程（或者叫 idle 进程），其 tasks 会依次指向下一个 task_struct，PID 为 1 的进程就是 init 进程，这两个进程都由 kernel 来创建。 而关于可以运行的进程的调度，Linux 2.6.34 和 ULK 上说的已经有很大的不同了。2.6.34 上加上了 struct sched_class 结构体表示不同类型的调度算法类，目前 2.6.34 上实现了三种：Completely Fair Scheduling (CFS) Class（完全公平算法，见 kernel/sched_fair.c）、Real-Time Scheduling Class（实时算法，见 kernel/sched_rt.c）和 idle-task scheduling class（见 kernel/sched_idletask.c），这三个源文件都被 include 在 kernel/sched.c 中进行编译了。CFS Class 使用 sched_entity 结构作为调度实体，其中包含权重、运行时间等信息，比 RT Class 复杂，其中还有专门的红黑树。RT Class 使用 sched_rt_entity 作为调度实体。 每个 task_struct 中都包含了 sched_entity 和 sched_rt_entity 这两个字段，sched_class 中则有 enqueue_task、dequeue_task 等函数指针指向对应调度算法中的实现函数，enqueue_task 将进程加入运行队列，dequeue_task 将进程从队列中移除，由于这段变化较大而且比较复杂，有关这三种调度算法的具体实现以后再来介绍了。 task_struct 的 real_parent 字段指向创建该进程的进程（如果父进程已不存在则为 init 进程），parent 指向当前进程的父进程，children 为该进程子进程列表，sibling 为该进程的兄弟进程列表，group_leader 字段指向该进程的线程组长。与 ULK 不同的是，ULK 中 ptrace_children 为被调试器 trace 的该进程的子进程列表，2.6.34 中 ptraced 字段包含该进程原本的子进程和 ptrace attach 的目标进程，ptrace_list 改为 ptrace_entry。另外 2.6.34 kernel 中已经引入 namespace 的概念，获得进程组 ID 和会话期 ID 的方式也于 ULK 中的有不少区别。 kernel 中进程的 PID 散列表存在 pid_hash 中以加快根据 PID 搜索 task_struct 的速度，pidhash_init 函数初始化此 PID 散列表，由于 2.6.34 中已有 namespace，pid_hashfn 也由原来的一个参数变为两个参数（增加一个 ns 参数表示哪个 namespace）。Linux kernel 也增加了 pid 和 […]