《Linux 内核设计与实现》 读书笔记

Linux 进程与线程

Linux 的 fork 采用写时拷贝 Copy On Write(页的拷贝推迟到进行写入时才进行,在写入前只有拷贝父进程页表以及给子进程创建进程描述符的开销,避免根本不被使用的数据的拷贝带来的性能开销)

vfork 与 fork 的不同在于它不拷贝父进程的页表项

Linux 的内核中并不存在线程这种概念,所有的线程都被当做进程来实现,它们与其他进程共享某些资源,没有特殊的调度算法或数据结构。而很多其他系统所实现的线程更像一种轻量级的进程,一种耗费时间少,执行迅速的执行单元。它与普通进程的区别仅仅在于是否共享地址空间。

Linux 中还有一种特殊的进程叫做『内核线程』,它往往被用来在内核中后台执行一些操作,与普通进程的不同在于它没有独立的地址空间,只在内核空间运行。

Linux 中进程终结会释放掉相关联的大部分资源,但仍会占用内核栈, thread_infotask_struct 结构的内存,直到父进程检索到该信息或通知该信息是无用信息后,才会将最后的一部分资源释放。(通过 wait)

如果父进程在子进程之前结束,则为了避免子进程永远处于僵死状态,会为它找到一个父进程。首先会尝试在当前进程组中寻找,找不到则会将init进程作为它的父进程。

Linux 进程调度

Linux 采用了抢占式多任务系统,由调度程序来决定什么时候停止一个进程的运行,进程被抢占前所能运行的时间被叫做时间片。

而非抢占式的多任务模式,除非进程主动停止运行,否则它会一直执行,需要进程主动挂起自己。这非常容易让恶意程序轻而易举地造成系统崩溃(不做出让步)

2.4 版本及以前的Linux调度程序都是十分简陋的,在 2.5 中引入了一种新的调度程序—— O(1) 调度器,解决了之前的许多不足。但它对于响应时间敏感的程序走很大的不足,因此在 2.6.23 版本中,被 CFS (完全公平调度算法)所替代。

通常来说,I/O 密集型(大部分时间在进行 I/O)的进程需要需要高频且短暂的调度策略(即时性高),而 CPU 密集型(大部分时间在执行代码)的进程则需要调度时间长而调度频率低的调度策略(即时性低)。Linux 为了保证交互式应用的性能,更倾向于调度 I/O 密集型的进程,但同时也不会忽略 CPU 密集型的进程。

进程优先级算法的思想就是高优先级先运行,低优先级后运行,但 Linux 并未完全采用。它用了两种不同的优先级范围:

  1. nice 值。越低代表优先级越高(越高人越好的意思)
  2. 实时优先级。值是可以配置的,越高意味着进程优先级越高。任何实时进程优先级都高于普通进程。

CFS 并不是直接分配时间片给进程,而是将处理器的使用比重划分给进程。这个比例与系统负载密切相关,同时受到 nice 值的影响。

虽然 CFS 不再分配时间片,但它仍然会对进程的运行时间进行记录,使用了了一个名为 sched_entity 的结构体进行记录,它保存在了 task_struct 中。在 sched_entity 中,记录了一个 vruntime 字段,它记录了进程实际运行了多少时间。而 CFS 调度算法的核心就是选择 vruntime 最小的进程,从而保证公平调度。

CFS 使用了红黑树组织可运行进程队列,通过红黑树可以快速找到最小 vruntime 的进程。

抢占及上下文切换

Linux 上下文切换 context_switch() 函数主要分为两步:

  1. switch_mm() 将虚拟内存从上一个进程切换到新进程
  2. switch_to() 将上一个进程的处理器状态切换到新进程的处理器状态,包括保存、恢复栈信息及寄存器信息,以及其他相关的状态信息

Linux 内核需要知道何时调用 schedule(),提供了一个 need_resched 变量用于标志是否需要重新进行调度。当某个进程应当被抢占时,scheduler_tick() 会对这个标志进行设置。同时,唤醒的函数 try_to_wake_up() 也会设置这个标志。如果它被设置,内核会调用 schedule() 切换到一个新进程。

用户抢占

内核返回用户空间时,会检查 need_resched,若被设置,就会调用 schedule(),发生用户抢占。

因此用户抢占的发生有下列情形:

  • 从系统调用返回用户空间时
  • 从中断处理程序返回用户空间时

内核抢占

Linux 还支持了内核抢占,可以在内核级的进程执行时进行重新调度。不过内核抢占的前提是 重新调度是安全的。

安全的前提是,需要当前进程没有持有锁。因此在进程的 thread_info 中引入了 preempt_count 用于表示持有锁的数量。当从中断返回内核空间时,若 need_resched 被设置并且 preempt_count 为 0 时,调度程序就会被重新调用。若不为 0,则会回到当前进程,等到该进程释放所有锁时,便会再次去检查 need_resched,若被设置,则会重新进行调度。

同时,内核中的进程还可以显式调用 schedule() 从而主动发生内核抢占。

因此内核抢占主要有下列四个场景:

  • 中断程序正在执行,且返回内核空间前
  • 内核代码再次具有可抢占性时(不持有锁)
  • 内核中的任务显式调用schedule()
  • 内核中的任务阻塞

实时调度

Linux 提供两种实时调度策略: SCHED_FIFO SCHED_RR。默认的非实时调度策略则是 SCHED_NORMAL。实时策略并不受完全公平调度器管理,而是被特殊的实时调度器管理。

SCHED_FIFO 即先入先出调度,不使用时间片,处于这个级别的进程会比任何 SCHED_NORMAL 的进程优先调度。处于该级别的进程会一直执行下去,直到受阻塞或显式释放处理器。

SCHED_RR SCHED_FIFO 大体相同,只是该级别的进程耗尽实现被分配的时间后就不能再继续执行了,之后在同一级别的其他实时进程轮流调度,但不能被低优先级的进程抢占

同时,Linux 提供了 sched_yield() 来让进程能够主动让出CPU。

Linux 中断及中断下半部

Linux 中断处理程序需要注册在对应的中断线上,中断线是可以共享的。因此使用了参数 dev 来标志同一中断线上的不同设备(如多个鼠标,多个键盘等)

为什么需要中断下半部

由于中断处理程序运行时,当前中断线在所有处理器上都会被屏蔽,甚至在设定 IRQF_DISABLED 后,中断程序运行会屏蔽所有本地中断,因此中断处理程序需要减少自己的工作量以加快运行,将一些不需要即时响应的任务留到之后执行,以更快地返回被中断的程序。

Linux 的中断下半部机制

Linux 有如下的几种中断下半部机制:

  1. Bottom Half: 是 Linux 最早采用的下半部机制,它需要静态创建,并且不支持同时执行多个相同的 Bottom Half,尽管是处于不同的处理器。因此有极大的性能瓶颈。
  2. 任务队列: 驱动程序可以将下半部注册到一个任务队列中,它会稍后在某个时刻执行。但它有个很大的不足是对于一些性能要求高的子系统无法胜任。
  3. 软中断: 软中断是一个需要在编译时期就静态注册的机制,最大可以注册 32 个软中断。两个相同的软中断可以同时执行,性能非常高但存在并发问题,适用于一些高性能需求的场景。(一般来说加锁就失去了软中断的高性能意义,因此一般采用只属于一个处理器的数据或者其他的技巧避免显式加锁)
  4. tasklet: 是一个基于软中断实现的机制,不同类型的 tasklet 可以在不同处理器上同时执行,并且可以动态注册。性能不如软中断,但可以适用大部分场景。

2.6 之后,Bottom Half 及任务队列就已经被移除,只剩下了软中断、tasklet 以及工作队列。

tasklet 使用了引用计数的方式来保证同时没有多个 tasklet 运行,使用了 atomic 的 int 来保证线程安全。

Linux 内核内存管理

内核中以物理页作为了内存管理基本单位,原因是 MMU 以页的大小为单位来管理系统中的页表。页是虚拟内存中的最小单位

页在内核中的定义如下(已简化):

struct page {
        unsigned long                 flags;
        atomic_t                            _count;
        atomic_t                            _mapcount;
        unsigned long                 private;
        struct address_space* mapping;
        pgoff_t                                index;
        struct list_head            lru;
        void*                                    virtual;
}

flag 用于存放页的状态(是否脏页等...)。每一位表示了一种状态。

_count 用于存放页的引用计数,为 0 代表内核中没有引用该页,则该页可以用于分配。一般来说调用 page_count 函数对其检查。一个页可以被多个页缓存使用(此时 mapping 指向了与这个页关联的 address_space 对象),也可以作为私有数据(private 指向),或者作为进程页表中的映射。

virtual 是页的虚拟地址,一般来说就是其在虚拟内存中的地址。有的内存并不永久映射到内核地址空间,此时它的值为 NULL。

page 是与物理页相关,而不是与虚拟页相关的,内核仅仅用它来描述当前时刻在相关的物理页中的信息,描述的是物理内存本身而不是其包含的数据。对于每个物理页,都需要分配一个 page 结构体。

由于有的页位于一些特定的物理地址,因此不能将其用于一些特殊任务。因此内核无法将所有的页一视同仁,对有着相似特性的页进行了分组,这个分组就被称为了区。

Linux 需要处理一下的两种硬件缺陷造成的内存寻址问题:

  1. 一些硬件只能用某些特定内存地址进行 DMA(直接内存访问)
  2. 一些体系结构内存的物理寻址范围比虚拟寻址范围大得多,有的内存无法永久映射到内核空间上

因为上述制约,Linux 主要分为了以下的四种区(还有两种不重要的):

  1. ZONE_DMA:这个区包含的页能用于执行 DMA 操作。
  2. ZONE_DMA32:这个区包含的页能用于执行 DMA 操作,但只能被 32 位设备访问
  3. ZONE_NORMAL:这个区包含的都是能正常映射的页
  4. ZONE_HIGHEM:这个区包含『高端内存』,其中的页不能永久映射到内核地址空间。

Linux 通过将页分为了区的设计,就形成了不同的内存池,这样就可以根据具体用途进行分配了。

slab 机制

为了便于数据的分配及回收,一般来说会采用空闲链表这一技术。这种技术设计了一种数据结构,包含了可供使用的、已分配好的数据结构块。当代码需要新的数据结构实例时,可以直接从空闲链表中抓取一个,而不需要分配内存。当不需要该实例时,就将其放入空闲链表中,而不去释放它。(有点类型对象池的思路)

但在内核中各个部分自己去实现空闲链表的话存在一个问题:无法全局控制。内存稀缺时,内核无法通知每个空闲列表去收缩一定大小以便释放内存。因此 Linux 内核提供了 slab 层(slab 分配器),来作为通用数据结构缓存层的角色。

slab 分配器需要在下列原则中找到平衡:

  • 频繁使用的数据结构也会频繁分配及释放,因此需要对它们缓存
  • 频繁分配和回收会导致内存碎片问题,空闲链表的缓存需要连续地存放
  • 回收的对象可以立即投入下一次的分配
  • 若部分缓存专属于单个处理器,则分配和释放就不需要在加 SMP(对称多处理器)锁的前提下进行。
  • 对存放的对象着色,避免多个对象映射到相同的高速缓存行(cache line)

slab 层将不同的对象划分为了高速缓存组,其中每个高速缓存组存放了不同类型的对象,每种对象类型对应一个高速缓存。(例如 task_struct 类型的高速缓存)。而内核中分配内存的 kmalloc() 建立在了 slab 层之上,使用了同一组通用高速缓存。

而这些高速缓存又被划分为 slab,slab 由一个或多个物理上连续的页组成(一般来说是一页)

每个 slab 都包含了一些对象成员,它有三种状态:满、部分满、空。当内核某部分需要一个新的对象时,先从部分满的 slab 中进行分配,若没有部分满的 slab,则从空的 slab 中进行分配。若仍没有,则会创建一个新的 slab。

下图展示了高速缓存与 slab、对象之间的关系:

image-20191030142815001

高速缓存所对应的结构体为 kmem_cache,这个结构体包含三个链表:slabs_fullslabs_partialslabs_empty,均存放于 kmem_list3 结构体中,分别存放了三种不同状态的 slab。

slab 所对应的结构体为 slab,它的定义如下:

struct slab {
        struct list_head     list;                    // 满、部分满或空链表
        unsigned long         colouroff;        // slab 着色的偏移量
        void*                         s_mem;                // slab 中的第一个对象
        unsigned int             inuse;                // slab 中已分配的对象数
        kmem_bufctl_t         free;                    // 第一个空闲对象(若存在)
}

slab 层的管理是在每个高速缓存的基础上,通过提供给整个内核一个接口来完成的,通过接口即可创建和撤销新的高速缓存,并在高速缓存内分配及释放对象,这个过程中的复杂管理均由 slab 层的内部机制来处理。

slab层负责了内存紧缺情况下所有底层的对齐、着色、分配、释放和回收,因此如果我们要频繁创建许多相同类型对象,可以采用 slab 高速缓存而不再需要自己去实现空闲链表。

内核栈

在用户空间,我们可以事先知道所分配的空间大小,因此可以负担起非常大的栈,但作为内核来说,不能太奢侈地使用内存,因此内核栈往往是小而固定的。一般来说,每个进程都有两页的内核栈。

2.6 系列内核早期,提供了一个选项使得内核栈只占用单页。这样设计主要是因为:

  1. 可以减少每个进程的内存消耗
  2. 随着运行时间增加,分配两个连续的页的难度会越来越大(内存碎片问题)

同时,中断处理程序所用的内存往往也使用了进程的内核栈,这就造成内核栈的约束条件更加严格。因此,在配置了单页内核栈的选项的情况下,每个进程会单独具有一个用于中断处理程序的栈——中断栈。

并且在内核中,大量地在栈上分配内存是十分危险的。因为这不像用户空间,内核是完全信任自己的。当发生了栈溢出时,是悄无声息的,溢出的部分会覆盖掉紧邻的堆栈末端的数据。

高端内存映射

高端内存中的页不能永久地映射到内核地址空间上,在 x86 体系中,高于 896MB 的所有物理内存范围基本都是高端内存。尽管 x86 的处理器能够寻址物理 RAM 的范围是 4GB,一旦这些页被分配,就必须映射到内核的逻辑地址空间上,高端内存中的页被映射到 3GB ~ 4GB 的区域。

CPU 独有数据

对于每个 CPU 有自己独有数据的情况, 往往采用数组来实现,如下所示:

unsigned long my_percpu[NR_CPUS];

之后,就可以通过下列方式来进行访问:

int cpu = get_cpu();        // 获取处理器号,并禁止内核抢占
my_percpu[cpu]++;                // 对数据进行操作
put_cpu();                            // 激活内核抢占

可以看到,这里并不需要加锁,因为每个处理器所访问到的数据是不同的,所操作的数据对于该处理器是唯一的。

那为什么 get_cpu() 获取处理器号需要禁止内核抢占呢?因为在获取到处理器号后,有可能会发生内核抢占并重新调度,这时这个 CPU 变量就指向了错误的处理器。

因此需要在 get_cpu() 调用时禁止内核抢占,put_cpu() 调用后恢复内核抢占。

这种每个 CPU 独有的数据的好处在于:

  1. 减少了数据锁定,每个 CPU 访问了自己独有的数据,不再需要任何锁,不存在并发问题
  2. 使用 CPU 独有数据可以减少缓存失效

Linux 进程地址空间管理

Linux 采用了虚拟内存技术来管理进程地址空间,系统中的所有进程以虚拟的方式共享内存。对于一个进程来说,它就像可以访问整个系统的所有物理内存一般。即使对于单独的进程,它所拥有的地址空间也远大于系统物理内存。

地址空间

进程地址空间由进程可寻址的虚拟内存构成,且内核允许进程使用虚拟内存中的地址。每个进程都有一个 32 位或 64 位的平坦(独立的连续区间)地址空间,两个进程中同样的内存地址,实际上也是毫不相干的。

内存地址是一个给定的范围内的值,每个内存区域有相关的权限。若一个进程访问了不在有效范围内的内存区域,或以不正确的方式访问了有效地址,则内核会终止该进程,并返回段错误信息。

内存描述符

内核使用了 mm_struct 结构体表示进程的地址空间,它包含了和进程地址有关的全部信息。

struct mm_struct {
    struct vm_area_struct*     mmap;                   // 内存区域链表
    struct rb_root                     mm_rb;                        // VMA形成的红黑树
    struct vm_area_struct*  mmap_cache;                // 最近使用的内存区域
    unsigned long                        free_area_cache;    // 地址空间第一个空洞
    pgd_t*                                     pgd;                            // 页全局目录
    atomic_t                                mm_users;                    // 使用地址空间的用户数
    atomic_t                                 mm_count;                    // 主使用计数器
    int                                         map_count;                // 内存区域个数              
    struct rw_semaphore         mmap_sem;                    // 内存区域的信号量
        // ...
        cpumask_t                                cpu_vm_mask;            // 懒惰(lazy)TLB交换掩码
        mm_context_t                        context;                    // 体系结构特殊数据
        unsigned long                        flags;                        // 状态标志
        // ...
};

mm_users 记录了正在使用该地址的进程数目,mm_countmm_struct 的主引用计数。这两个值比较容易混淆, 当有九个线程共享该地址空间的时候,mm_users 为 9,而 mm_count 仅为 1。同时使用这两个计数器是为了区分主使用计数(mm_count)与使用该地址空间的进程数(mm_users)。

mmapmm_rb 所描述的对象是相同的,区别在于前者使用链表形式存放,后者使用红黑树形式。为何要使用这种冗余的存放方式呢?mmap 作为链表,可以简单、高效地遍历所有元素。而 mm_rb 作为红黑树,可以快速地搜索指定元素。

所有 mm_struct 都通过自身的 mmlist 连接在了一个双向链表中,该链表的首元素 init_mm 代表了 init 进程的地址空间,操作该链表时需要 mmlist_lock 锁避免并发访问。

mm_struct 这样的内存描述符被存储于 task_struct.mm 中,每个进程往往只有唯一的内存描述符。当父进程希望与子进程共享地址空间的时候,可以在 clone 时设置 CLONE_VM 这个 flag,这样子进程就只会将其 task-struct.mm 字段指向父进程的即可。

对于内核线程来说,它没有对应的内存描述符,没有用户上下文。

虚拟内存区域

Linux 中的内存区域用 vm_area_struct 这个结构体描述,它描述了指定的地址空间中上的一块内存范围,作为一个单独的对象管理,这种区域就是 VMA。每个 VMA 可以代表不同类型的内存区域(例如数据、代码、内存映射文件、进程用户空间栈等)

struct vm_area_struct {
      struct mm_struct* vm_mm;            // 相关的 mm_struct
      unsigned long vm_start;                // 首地址
      unsigned long vm_end;                    // 尾地址
      struct vm_area_struct* next;    // 链表上下一个 VMA 节点
      struct rb_node vm_rb;                    // 红黑树上 VMA 的节点
      unsigned long vm_flags;                // 标志
      // ...
}

vm_area_struct 实际上就是 mm_structmmapmm_rb 所存储的区域集合,它主要包含了 vm_startvm_endvm_flags 等属性。

vm_flags 主要是描述了这个内存区域的一些属性,例如可读、可写、可共享、增长方法等等。

因此,Linux 中对虚拟内存的组织结构大致如图:

缺页处理

当进行虚拟地址到物理地址转换时,如果 Linux 中发生了页错误,页错误处理程序会经过如下的步骤:

  1. 检查该虚拟地址是否合法:会通过 mm_rb 这颗红黑树查找该虚拟地址所对应的 VMA,具体是通过对 vm_startvm_end 进行比较,若最后发现该虚拟地址并不合法,则会抛出一个段错误,终止该进程。
  2. 对内存访问的合法性进行判断:判断进程是否有读写这个区域对应的权限等,若不合法则会排出一个保护错误。
  3. 将需要的页换入:当发现对页的访问合法时,操作系统就会通过换出一个页,之后换入对应的页并更新页表。之后硬件会重新执行访问页的指令,此时该页已经存在于内存中,就能够正常的进行地址的转换了。

本文链接:

http://n0texpecterr0r.cn/index.php/archives/41/
1 + 2 =
快来做第一个评论的人吧~