linux内核设计与实现

内核简介

单内核&微内核

单内核：作为一个单独的大过程运行，运行在单独的地址空间上（不就是单个进程吗？），内核之间的通信很方便。

微内核：内核的功能被划分为多个单独的过程，每一个过程叫做一个服务器，某些服务器运行在用户空间，有些运行在内核空间中，所以不同服务器之间的通过消息传递机制通信：系统采用了IPC机制。但是，IPC特别消耗资源，所以现在的微内核的服务器都运行在内核空间上，可以直接进行通信。

Linux内核的特点

• 可以动态加载内核模块
• 支持SMP机制，
• 内核可以抢占，在内核的任务优先执行
• 对线程的支持，内核不区分线程、进程，只是有些共享资源而已

进程管理

进程描述符与任务结构

内核将进程的列表存放在叫任务队列的双向循环链表中，链表的每一项都是类型为task_struct的进程描述符的东西（ucos的TCB）。他其中包含的内容有：打开的文件、地址空间、挂起的信号等。

分配进程描述符

在内核栈的尾端会存放任务的thread_info, 他其中会包含指向进程描述符的指针：

进程描述符的存放

进程描述符中的state描述了当前的状态，包含如下五个：

• 运行：可执行的；要么正在执行，要么在等待执行（按照一般的逻辑，这里要分成就绪态和运行态，不知道这里为什么没有分开呢）

  GPT:

  在 Linux 的进程状态中，TASK_RUNNING 表示进程处于就绪态或运行态，因此没有单独细分出就绪态。这种设计简化了状态管理，因为就绪进程可以立即被调度运行，而系统只需关注运行中的进程。尽管就绪态和运行态是不同的概念，实际操作中将它们统一处理有助于提高效率和简化调度算法。

• 可中断：进程正被阻塞，等待某些条件达成,收到信号后可以提前唤醒准备运行（这里的信号应该指的是SIGINT、SIGKILL等信号，收到信号就会进入中断，与该任务等待的条件是两个东西）

• 不可中断：进程正被阻塞，等待某些条件达成，收到信号也不会唤醒

• __TASK_TRACED:被跟踪的进程，如ptrace对程序进行跟踪，

• 停止：进程被停止执行，比如收到SIGSTOP、SIGTSTP等。

设置当前的进程状态

内核可以通过set_task_state(task, state)来调整进程的状态。

进程上下文

一般程序在用户空间执行，一个程序执行了系统调用或者出发了异常，就陷入了内核空间，这时，我们说，内核代表进程执行并处于进程上下文中。

关于进程上下文与中断上下文：进程上下文和中断上

处理器总处于以下状态中的一种：

1. 内核态，运行于进程上下文，内核代表进程运行于内核空间；
2. 内核态，运行于中断上下文，内核代表硬件运行于内核空间；
3. 用户态，运行于用户空间。

Linux内核工作在进程上下文或者中断上下文。提供系统调用服务的内核代码代表发起系统调用的应用程序运行在进程上下文；另一方面，中断处理程序，异步运行在中断上下文。中断上下文和特定进程无关。

系统调用的详细过程：系统调用

Linux 在x86上的系统调用通过 int 80h 实现，用系统调用号来区分入口函数。操作系统实现系统调用的基本过程是：（可以看到系统调用函数是处于中断中的）

1. 应用程序调用库函数（API）；
2. API 将系统调用号存入 EAX，然后通过中断调用使系统进入内核态；
3. 内核中的中断处理函数根据系统调用号，调用对应的内核函数（系统调用）；
4. 系统调用完成相应功能，将返回值存入 EAX，返回到中断处理函数；
5. 中断处理函数返回到 API 中；
6. API 将 EAX 返回给应用程序。

应用程序调用系统调用的过程是：

1. 把系统调用的编号存入 EAX；
2. 把函数参数存入其它通用寄存器；
3. 触发 0x80 号中断（int 0x80）。

进程家族树

所有进程都是PID为1的init进程的后代

每个进程描述符会包含指向父进程描述符的指针与子进程链表的指针。

可以通过任何一个进程描述符访问他的父进程，最终达到init进程。

可以通过任务队列访问系统中的所有任务。

进程创建

常见办法是：先fork在exec组合运行

写时拷贝

因为fork后一般要指向exec开启新的进程。如果fork后，立刻进行第一次拷贝，然后exec又会进行第二次拷贝，这样第一次拷贝就是多余的。

写时拷贝是可以推迟甚至免除拷贝数据的技术，fork时，内核不复制整个地址空间，而是让父子进程共享同一个拷贝。只有在需要写入时，数据才会被复制，在此之前都是以只读形式共享的。（调用exec后，就会建立新的地址空间了）

fork

LInux中的fork()、vfork()、__clone()等库函数都通过各自需要的参数去调用clone(),然后clone()再去调用do_fork()。

do_fork完成了创建中的大部分工作。他会先调用copy_process函数，然后让进程开始运行。copy_process成功返回后，一般会让子进程先执行（因为如果子进程执行了exec，就可以赶紧处理了）

vfork除了不拷贝父进程的页表项，vfork系统调用与fork的功能都是相同的。

线程

LInux内核没有线程的概念，LInux的线程实际上就是与其他进程共享某些资源（地址空间）的进程，他也有自己的task_struct,看起来就是一个普通的进程。

这种实现方式与Windows差异很大，这些系统在内核提供了专门支持线程的机制

创建线程

创建过程与进程类似，在调用clone时需要传入额外的参数：

clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0)

上面的代码共享了地址空间、文件系统资源、文件描述符、信号处理函数。

内核线程

内核为了在后台完成一些任务，定义了一些内核线程–独立运行在内核空间的标准线程。内核线程与普通线程的唯一区别在于没有独立的地址空间，他只在内核空间运行。

进程终结

终结的原因：exit系统调用，主程序的return，不能处理与忽视的信号

终结首先要释放自己的资源，然后通知父进程。终结的工作主要靠do_exit来完成，他会重新设置进程描述符中的标志成员、释放内存、递减文件描述符等、向父进程发信号、给子进程找养父、最后调用schedule切换到新的进程，这是该进程执行的最后一段代码（好伤感）。

到这里，进程的大部分资源都已经被释放，还剩下内核栈、thread_info、task_struct结构还保存着，待父进程查看(waitpid?)后通知内核，这些最后的资源也将被释放。

删除进程描述符

释放剩下的资源等，

孤儿进程

如果父进程在子进程之前退出，那么必须有机制保证子进程找到一个新的父亲。否则这些孤儿进程在退出时会变成僵死状态，浪费内存。（其实上面的进程终结部分也说了：会给子进程找继父）

进程调度

多任务

LInux提供了抢占式的多任务模式。（轮转调度是实现抢占式调度的一种方法）

LInux的进程调度

Linux2.5版本引入了O（1）调度程序，他性能好，但是调度交互进程有些缺点。

LInux2.6版本引入了RSDL算法来提高交互性能，将公平调度的概念引入了Linux调度程序，他最终取代了O（1）调度算法，被称为完全公平调度算法CFS。

策略

IO消耗型和处理器消耗型进程

进程可以分为这两类：IO消耗型（键盘输入）和处理器消耗型进程（MATLAB），对于处理器消耗型，应该尽可能减低调度频率，延长运行时间。调度策略需要在两个矛盾的目标间找平衡：进程响应迅速（响应时间：从发出请求到系统开始响应的时间间隔）和系统利用率高。LInux更倾向于优先调度IO消耗型进程。

进程优先级

根据优先级进行调度。Linux采用了两种不同的优先级范围，

• 第一种是nice值（意味着该进程受到优待的程度），范围是-20到19，默认为0，越小优先级越高。在Linux中，优先级高的时间片比例高。
• 第二种是实时优先级，范围是0到99，值越高越优先，

时间片

不同的时间片造成的影响是不同的，不同类的进程需要不同的时间片。LInux的CFS调度器不直接分配时间片，而是分配处理器的使用比例，这个比例还会受到nice的影响。

Linux使用的CFS调度器，如果新程序消耗的处理器占比比当前任务小，则将新进程离开投入运行，进行抢占。否则，推迟运行。

调度策略的活动

假设文本编辑器与视频编码器，一种做法是分配给编辑器更高的优先级与更多的时间片。Linux采用了不同的方法，处理器使用比，比如nice设为50%，则他们会平方处理器时间。当文本编辑器被唤醒后，CFS注意到文本编辑器的实际使用时间很少，为了兑现公平的承诺，会立刻抢占视频编码程序。

Linux调度算法

调度器类

CFS是真的普通进程的调度类，SCHED_NORMAL.(普通进程与实时进程)。

Unix中的进程调度

如何使用nice值映射到绝对的时间，几个问题：

• 如果将nice值对应到处理器的绝对时间：不合理
• 相对nice值，nice0和nice1对应100ms和95ms，而nice18和nice19对应10ms和5ms，时间翻倍了，这是不合理的。
• 定时器节拍，时间片应该是节拍的整数倍（引入CFS的唯一原因）
• 给刚唤醒的进程提升优先级，

这些都是由于分配绝对的时间片造成的，CFS的方法是对时间片分配方式重新设计。

公平调度

CFS不分配时间片，而是允许每个进程运行一段时间，选择运行最少的进程作为下一个运行进程。假设20ms为一个周期，有二十个相同优先级的任务，每个都分得1ms。为了防止运行时间过短，设置一个时间片底线为1ms。所有进程获得的处理器时间由他自己与其他进程的nice差值决定的。

Linux调度的实现

主要包含四个部分：时间记账、进程选择、调度器入口、睡眠和唤醒

时间记账

实体结构体是sched_entity, 为task_struct中的se成员。其中的vruntime保存的是给定进程的运行时间。（vruntime=实际运行时间 * （nice为0的权重/当前任务nice对应的权重））

进程选择

如果是一个完美的多任务处理器，那么所有进程的vruntime将保持一致。选择下一个算法时，会选择最小vruntime值的进程。

CFS使用红黑树来组织可运行进程队列。

• 挑选下一个任务，即红黑树最左边那个
• 向树中加入进程，
• 从树中删除进程（发生在阻塞或终止时）

调度器入口

入口时schedule，找到最高优先级的调度类后，然后问那个是下一个该运行的进程。

休眠与唤醒

当需要等待一些事件时，比如文件IO,硬件事件，信号量，会将自己标记为休眠态，然后从红黑树中移除，放到等待队列中。（两种休眠态：可中断、不可中断）

• 等待队列，由等待某些事件的进程组成的链表。

为了避免虚假唤醒，一般会通过一个while循环来保证。

抢占与上下文

找出下一个进程后，schedule会调用context_switch函数来切换上下文。

切换进程的内存映射

切换处理器状态，包括栈、寄存器等。

一般来说，返回到用户空间时，需要检查need_resched标志，如果被设置，需要重新进行调度。

用户抢占

内核抢占

只要重新调度是安全的，就可以在任何时间抢占正在执行的内核任务。从中断返回到内核空间时，内核会检查need_resched和preempt_count（锁的个数）的值来判断能否安全的抢占。如果内核的进程被阻塞了，也会显示的发生内核抢占。

实时调度策略

• Linux提供了两种实时调度策略：SCHED_FIFO、SCHED_RR。
• 而普通的非实时的调度策略是SHCED_NORMAL

实时策略不被CFS管理。

• SCHED_FIFO实现了先进先出的调度算法。只要该级别进程处于可执行状态，就会一直执行，直到被阻塞或显示的释放处理器为止。只有更高优先级的实时进程才能抢占该进程，更低级别的实时进程只能一直等待。（所有实时进程会比普通进程先得到调度）
• SCHED_RR，与上面基本类似，可以看成带有时间片的SCHED_FIFO。时间片用完时，同一优先级的其他进程被调度。

实时进程优先级范围是0-99，普通进程的优先级是100-139（是根据nice值确定的是哪个优先级）

系统调用

与内核通信

系统调用的作用有三个（别太在意）：

• 为用户空间提供了硬件的抽象接口，读文件就不用管具体的文件类型
• 内核可以对部分系统调用进行裁决，保证安全
• 管理对硬件的访问

API、POSIX和C库

程序通过用户空间的应用编程接口而不是系统调用来编程。

C库实现了Unix系统的主要API。

系统调用

要访问系统调用，一般是通过C库的函数来进行的。一般会返回一个值，非零代表错误，出错时会把错误码写入errno全局变量，可通过perror翻译。

系统调用号

每个系统调用都有一个系统调用号。

系统调用处理程序

软件中断与软中断软中断与软件中断 - 知乎

软件中断：属于同步中断（CPU内部引发的中断，也叫异常,与硬件中断对应），工作在进程上下文

软中断：其实叫中断下半部，类似硬件中断机制，是异步中断，工作在中断上下文

用户空间的程序在运行时没法直接执行内核空间的函数。所以，应用程序应该以某种方式告诉系统，自己要执行一个系统调用，让系统切换到内核态，从而可以代表应用程序在内核空间执行。

通知内核的机制是通过软件实现的，通过引发一个异常来促使系统切换到内核态执行中断程序（系统调用处理程序）。软件中断中断号是128，通过int $0x80指令可以触发该中断，这会导致系统切换到内核态并执行128号异常处理程序（即系统调用处理程序）。

指定恰当的系统调用

其实前面的0x80指的是中断号，为了指定具体的系统调用还需要系统调用的编号，这个是通过eax寄存器传给内核的。

参数传递

如果需要传递额外的参数，最简单的办法是把这些参数也存放在寄存器里，ebx、ecx、edx、esi、edi按照顺序存放前五个参数。

系统调用的实现

每个系统调用永远都有一个单一并明确的用途。尽量然系统调用更加通用。

参数验证

系统调用必须检查所有的参数是否合法有效。系统调用在内核空间执行，如果输入了不合法的东西，对于系统的安全有很大影响。（比如检查文件描述符，进程pid是否正确，指针是否有效）

如果参数有指针，内核必须保证：指针指向的内存区域属于用户空间，却不能是内核空间。

内核提供了两个方法来完成必须的检查以及内核空间与用户空间的来回拷贝。copy_to_user和copy_from_user。

系统调用上下文

内置在执行系统调用的时候处于进程上下文，current指针指向的是当前的任务，即引发系统调用的哪个进程。在进程上下文中，内核可以休眠并且可以被抢占。

绑定一个系统调用的最后步骤

写完后，需要完成如下三步：

• 在系统调用表增加一个表项
• 定义系统调用号
• 将系统调用写进内核映像

从用户空间访问系统调用

一种方式是通过C库访问

另一种方式是通过Linux提供的一组宏访问

中断和中断处理

中断

中断本质上是一种电信号，由硬件设备发给处理器。

异常，与中断的差异在于是由软件引起的。异常是由处理器本身产生的同步中断。

可以分成上下两部分，上半部分负责紧急任务的处理，如拷贝网卡中数据包，拷贝完则中断结束，下半部分负责处理和操作数据包。

注册中断

通过int request_irq(unsigned int irq, irq_hander_t handler, unsigned long flags, const char *name, void *dev)注册一个中断处理程序，第一个参数代表要分配的中断号，第二个参数指的是一个中断处理程序。

中断处理程序标志

flag可以为0，也可以为：

• IRQF_DISABLED, 设置后，内核在处理中断时，会禁止其他中断

• IRQF_SAMPE_RANDOM，表示该中断内核熵池可以有贡献（内核熵池负责从随机事件导出真正的随机数），如果中断是一个以预知的速率触发的，不要设置这个参数。

• IRQF_SHARED, 一般来说，每个中断线（不是中断号，应该和STM32中的EXTI_Line很类似，外部设备一般都要连上这种线才能向CPU发中断，不过Linux也需要处理这么底层的事情么？）只能有一个处理程序，开启这个标志后，多个处理程序可以注册在同一个中断线上。

  from gpt

  中断号和中断线不一定是一一对应的关系。通常情况下，多个设备可以共享同一条中断线，这种情况称为“共享中断”。在这种情况下，所有共享同一条中断线的设备在发生中断时，CPU接收到的信号只能表示有某个设备请求了中断。

  当中断请求发生时，CPU会根据中断线的信号来判断哪个设备需要处理。接着，它会通过其他机制（例如询问设备状态或使用优先级）来确定具体是哪个设备触发了中断，然后根据该设备的类型来分配中断号。

  因此，尽管每条中断线通常会有一个或多个中断号与之关联，但它们之间并不一定是一一对应的关系。

request_irq申请不成功时，返回非零值，常见的错误是-EBUSY,代表中断线已经在使用。

中断上下文

中断控制

为了实现同步，需要对中断进行控制，

• 锁，防止其他处理器或者其他进程的并发访问。
• 禁止中断，防止其他中断处理程序的并发访问

禁止和激活中断

禁用当前处理器中断的语句local_irq_disable()

禁止中断线

disable_irq()

中断下半部

下半部

理想情况下，所以工作都应该由下半部去完成，但中断处理程序注定要完成一些工作：对中断进行确认、拷贝数据。剩下的工作由下半部完成。8

下半部的环境

实现方式：

• BH（当前已废弃）
• 任务队列（被工作队列取代）
• 软中断和tasklet，软中断是一组静态定义的下半部接口，有32个。两个类型相同的软中断也可以在不同处理器同时执行。tasklet是简单易用的软中断。类型相同的tasklet不能在不同的处理器同时执行。向网络这样对性能要求高的就会使用软中断。

软中断

软中断由softirq_action表示，内核定义了一个包含有32个该结构体的数组，最大数目没法变化。只有中断能抢占软中断，其他的（甚至是同类型的）软中断可以在其他处理器上执行。软中断不能动态的注册或注销，是在编译器静态分配的。

执行

中断处理程序返回前会标记软中断，让他在稍后被执行，在什么时候检查软中断：

• 从硬件中断返回时
• 在ksoftirqd线程
• 在那些显示检查的代码中

使用

目前只有网络和SCSI直接使用软中断。内核定时器和tasklete都是建立在软中断之上的。

• 编译时，分配索引

• 运行时，注册处理程序，第一个参数是前面定义的索引号，第二个是处理函数。为了避免不同处理器运行相同处理程序造成的问题，大部分软中断处理程序使用单处理器数据（无需加锁）。

使用软中断主要原因就是其可以在多个处理器运行相同程序，如果没有这个需求，使用tasklet吧

• 触发软中断，完成上面两部后，raise_softirq（通常在中断处理函数中执行这个命令）会将一个软中断设置为挂起状态，下次调用do_softirq时，该软中断的处理程序就会立刻执行。

tasklet

一种利用软中断实现的下半部机制。

实现

首先在中断处理程序中时，返回前会执行tasklet_schedule, 在其中会

• 将需要调度的tasklet加到每一个处理器的一个tasklet或者tasklet_hi_vec链表上去，
• 唤醒软中断。

在do_softirq时，因为前文唤醒了软中断，所以会指向相应的软中断处理程序：tasklet_action, tasklet_hi_action:

• 遍历tasklet链表，如果是多处理器系统，检测该tasklet是否在其他处理器运行（是则跳到下一个tasklet），不断循环

使用

ksoftirqd

为了避免软中断自己触发自己，一直占用CPU导致用户空间没法使用CPU。会将重复触发的软中断放到优先级最低的内核线程上运行，这能保证过量的软中断终会被处理，也能留给用户程序足够的处理数据。

工作队列

工作队列也是一种推迟执行的方法，工作队列允许将任务交给内核进程执行，如果推迟执行的任务需要睡眠，就选择工作队列，否则使用软中断/tasklet。（软中断/tasklet在中断上下文运行，而任务队列是在任务上下文运行）

from GPT, 什么是中断上下文：

中断上下文的特点

• 无进程上下文：
  • 在中断上下文中，CPU 不再关联具体的用户进程，也没有用户态堆栈。
  • 中断处理代码无法直接访问用户态数据，所有操作基于内核态的资源。
• 禁止阻塞：
  • 不能调用可能引发睡眠的函数（如 schedule()、mutex_lock()）。
  • 因为中断上下文的执行是不可中断的，无法调度到其他任务。
• 优先级高：
  • 中断上下文会抢占普通进程和某些低优先级的内核任务（如软中断和工作队列）。
  • 高优先级的中断甚至可以打断低优先级的中断。
• 使用独立的中断堆栈：
  • 每个 CPU 有一个固定的中断堆栈，用于处理中断上下文的局部变量和调用栈。

工作队列的实现

工作队列可以创建一个工作者线程，来为其他部分处理需要推后执行的工作。提供了一个缺省的工作者线程名为events/n，n为处理器的编号。

通常内核线程没法访问用户空间，只有在发生系统调用时，内核会代表用户空间的进程运行，此时他才能访问用户空间。

锁

• 下半部和进程访问可以相同的数据，那么进程在访问数据前，需要禁下半部的处理并加锁（因为下半部是在中断上下文，不能被阻塞，所以只能在进程中提前做好处理；应该是谁低级，谁做处理）
• 下半部和中断访问可以相同的数据，那么下半部在访问数据前，需要禁中断并加锁

内核同步

要对共享数据进行保护。

• 没有对称多处理器时，并发访问数据的方法很容易识别，要么是发生了中断，要么是内核代码明确请求调度。（把这两种方法禁了就能保护共享数据）

• 支持对称多处理器时，内核可以运行在不同的处理器上。Linux2.6就支持抢占式内核，意味着内核线程能被调度程序抢占。（同一段内核代码可以运行在不同的处理器上，但同一个线程只能运行在一个处理器上）

临界区和竞争条件

临界区是访问共享数据的代码段。临界区不能被多个线程访问，临界区不能被打断。避免并发（协调进程的执行顺序）称为同步。

为什么要保护

举例，两人用同一个银行账户取钱。

单个变量

处理器提供了指令来原子的读、写、增加变量。

内核也提供了实现原子操作的接口

加锁

• 有些指令体系提供了专门的指令来对某些值进行计算和比较。
• 如果要对不定长度的临界区进行保护，需要使用锁，

锁有不同形式：

• 当锁被其他线程持有时，会进行循环并检测是否获得锁，忙等待
• 当锁被其他线程持有时，会进行睡眠

锁的作用就是把临界区缩小到加锁和开锁之间的代码（为了保证整段代码的原子性，需要保证开锁和加锁两个代码的原子性），而锁是由原子操作实现的，很多处理器都实现了测试指令，比如x86的compare和exchange。

造成并发执行的原因

并发和并行都会导致竞争条件。

内核中的代码也有类似的可能导致并发执行的原因。

• 中断——可以随时打断当前正在执行的代码
• 软中断和tasklet——内核可以在任何时刻唤醒这两者，打断正在执行的代码
• 内核抢占——内核任务也能被其他任务抢占
• 睡眠
• 对称多处理

比较常见的错误：

• 一段内核在操作某一个资源时，产生了一个中断，该中断也会访问该资源（其实按理说，临界区不应该产生中断，毕竟只要操作系统掌握了CPU，他就可以进行调度）
• 一段内核在操作某一个资源时，可以被抢占
• 一段内核在临界区睡眠

真正困难的是找到潜在并发执行的可能（重点是共享的数据和相应的临界区），并防止并发。

中断安全代码——中断处理程序中能避免并发访问的代码

SMP安全代码——SMP中能避免并发访问的代码

抢占安全代码——内核抢占时能避免安全访问的代码

要保护什么

可能被并发访问的代码都需要保护。先看看哪些资源不用被保护：

• 线程的局部数据，（这些数据只会被该线程访问，不可能被并发访问）

大多数内核数据结构需要加锁，如果其他线程可以访问这些数据，就需要加锁。

死锁

一些避免的简单规则：

• 按顺序加锁（记得在代码中对锁的使用加上注释），最好按照申请的相反顺序释放锁

争用和拓展性

如果锁处于高度争用状态，就是指有多个线程等待获得该锁，锁的作用就是让进程以串行方式访问资源，所以锁会降低系统的性能。被高度争用的锁会成为系统的瓶颈。

在Linux2.6的内核中，内核加的锁是非常细的粒度（最开始，粒度很大，同一时刻只允许一个任务在内核运行）。

当多处理器出现时，如果维护一个全局的运行队列，供所有CPU访问，那么非常低效，如果为每个处理器维护一个运行队列，效率会变高，锁变得更精细化了。这提升了系统的可拓展性。（可拓展性意味着当加入更多处理器、内存时，系统仍然运行的很好）

提高可拓展性是件好事，这让Linux在更大型的、处理能力更强的系统上的性能，但这会导致Linux在小型SMP和UP机器上的性能降低。（因为他们用不到这么精细化的锁）（比如说一开始，一个链表是共享资源，那么给链表加一个锁就行了，但是随着处理器数目增加，如果多个处理器都要访问这个链表，那么效率很低，所以就只给每一个节点加锁，这样加锁粒度变细。但如果多个处理器同时访问某个节点，还是会发生争用。还有没有必要在更细的粒度上加锁呢，比如每个元素，没有必要，过细的粒度会导致系统在低数量处理器上的表现太差，加大系统开销）。

初期加锁应该尽量简单，加锁不要太粗和太细。

内核同步方法（这些操作一般用于内核，可能没法在用户空间使用）

Linux提供了一组同步方法，来使内核开发者们编写高效而自由竞争的代码。

原子操作

内核提供了两组原子操作接口。

原子整数操作

针对整数的原子操作只能对atomic_t类型的数据进行操作。

原子性和顺序性：

原子性：指令不可拆分，要么执行完，要么没有执行完，比如：atomic_t i = ATOMOC_INIT(0), 然后两个线程执行i++,，那么被atomic_inc(&i)执行后，i的结果只能是2， 而如果被普通的i++指令执行后，结果也可能为1，它不具有原子性。

顺序性：我们的代码通常有比原子性更高的要求，比如要求读在特定的写前执行。顺序性需要通过屏障指令来实施。

原子操作与复杂的同步方法相比，开销非常小。

原子位操作

原子位操作是用来对普通的内存地址进行操作的。

常见的参数是给定一个变量地址，然后给定一个位号，然后就对这个位号进行读写。

原子操作保证该函数内部指令一一执行，如果要连续执行多个原子操作，很可能出现问题，即原子操作没法保证外部的顺序

现代处理器通常通过硬件指令（如 x86 的 LOCK 前缀或 compare-and-swap 指令）实现原子性。这些指令在执行时会锁定必要的内存地址或总线，防止其他处理器对该内存区域进行并发访问。比如：

#include <stdatomic.h>
#include <stdio.h>

int main() {
    atomic_int counter = 0;
    atomic_fetch_add(&counter, 1);  // 原子递增
    printf("Final counter value: %d\n", counter);
    return 0;
}
//编译后反汇编
    1184:       c7 45 f0 00 00 00 00    movl   $0x0,-0x10(%rbp)
    118b:       f0 83 45 f0 01          lock addl $0x1,-0x10(%rbp) //可以发现，使用了lock前缀防止并发

自旋锁

原子操作没办法处理一些复杂操作：比如从一个数据结构读取数据，处理后添加到另一个数据结构上，这需要更复杂的同步方法——锁。

Linux最常见的锁是自旋锁。

如果要申请的锁已经被其他线程持有，那么当前线程会一直忙等待（不会阻塞，其实中断也可以用自旋锁，但是不符合中断快进快出的特点）。

• 自旋锁，等待是忙等待，会浪费处理器的等待时间
• 信号量，等待是让线程睡眠，会浪费两次上下文切换的时间

所以要让持有自旋锁的时间尽可能短，短于上下文切换的时间。

自旋锁方法

自旋锁不能递归。一个线程不能连续加两次锁。

在中断中可以使用自旋锁，那么在申请一个自旋锁时就需要注意了，为了防止申请一个自旋锁之后突然被一个中断打断，进而出现再次申请锁的情况，需要先禁（当前处理器的）中断，然后申请锁。只用禁当前处理器的中断就行了，因为即使中断处理在一个锁上自旋，也不妨碍其他处理器释放锁。

spin_lock_irqsave(&mr_lock, flags), 会保存本地中断的状态，并禁止中断，然后获取锁。

spin_unlock_irqrestore(&mr_lock, flags)

锁什么，锁的是数据而非代码，所以每个锁是跟数据关联起来的，比如数据loo，可以用loo_lock加锁。

自旋锁与下半部

读写自旋锁

信号量

计数信号量和二值信号量（又名互斥信号量）

更多的看看操作系统那篇吧。

读写信号量

读者无限，写者唯一。

互斥体

• mutex的使用计数永远是1
• mutex不能在中断或者下半部使用
• mutex可以通过特殊的调试模式，通过内核来检查一些错误行为。内核配置有CONFIG_DEBUG_MUTEXES。

禁止抢占

现在Linux内核是运行内核抢占的，但是如果某一段区域，线程持有了自旋锁，那么内核在该段区域是不能被抢占的，

顺序与屏障

rmb()提供读屏障，wmb()提供写屏障。

又白看了

内存管理

页

内核用struct page来表示每个物理页，

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存放该页的引用计数，如果值为-1说明没有进程需要该物理页
• virtual代表该页的虚拟地址，

这个page结构只与物理结构相关，所以该结构对页的描述是短暂的，当物理页需要加载新的程序时，该结构的值就会随之改变。

区

对于不同的物理内存，不能一视同仁：

• 一些硬件只能用特定的内存地址进行DMA
• 一些体系的物理地址比虚拟地址大

为此，Linux使用了如下的几种区：

• ZONE_DMA, 该区只能执行DMA操作

• ZONE_DMA32

• ZONE_NORMAL，该区可以正常映射

• ZONE_HIGHEM，这个区包含高端内存，其中的页不能永久的映射到地址空间

  

  from:linux内存空间分配和内存管理

  在kernel image下面有16M的内核空间用于DMA操作。位于内核空间高端的128M地址主要由3部分组成，分别为vmalloc area，persistent kernel mapping(持久化内核映射区)，tempoary kernel mapping(临时内核映射区)。

  由于ZONE_NORMAL和内核线性空间存在直接映射关系，所以内核会将频繁使用的数据如kernel代码、GDT、IDT、PGD、mem_map数组等放在ZONE_NORMAL里。而将用户数据、页表(PT)等不常用数据放在ZONE_ HIGHMEM里，只在要访问这些数据时才建立映射关系(kmap())。比如，当内核要访问I/O设备存储空间时，就使用ioremap()将位于物理地址高端的mmio区内存映射到内核空间的vmalloc area中，在使用完之后便断开映射关系。

  由于开启了分页机制，内核想要访问物理地址空间的话，必须先建立映射关系，然后通过虚拟地址来访问。为了能够访问所有的物理地址空间，就要将全部物理地址空间映射到1G的内核线性空间中，这显然不可能。于是，内核将0~896M的物理地址空间一对一映射到自己的线性地址空间中，这样它便可以随时访问ZONE_DMA和ZONE_NORMAL里的物理页面；此时内核剩下的128M线性地址空间不足以完全映射所有的ZONE_HIGHMEM，Linux采取了动态映射的方法，即按需的将ZONE_HIGHMEM里的物理页面映射到kernel space的最后128M线性地址空间里，使用完之后释放映射关系，以供其它物理页面映射。虽然这样存在效率的问题，但是内核毕竟可以正常的访问所有的物理地址空间了。

x86_64系统中，虚拟地址空间可以映射所有的64位的地址，所以没有ZONE_HIGHMEM区。

获得页（这些操作都是提供给内核开发者的，普通的用户程序不应该使用这些函数）

struct page * alloc_pages(gfp_t gfp_mask, unsigned int order)，

如果只是要分配若干字节，可以使用kmalloc

kmalloc

slab层

很多操作都需要分配和释放数据结构，为了避免频繁的申请和释放，会利用到空闲链表。当代码需要一个数据结构实例时，就从空闲链表中拿一个，不需要时，就将它放回空闲链表而不是释放它。（空闲链表就相当于对象高速缓存，感觉和线程池也很类似的）

空闲链表有个缺点，内核内存紧张时，没办法通知空闲链表，让他释放一点内存。为了弥补这一缺陷，Linux提供了slab层。

slab层的设计

slab层把不同的对象分为高速缓存组。每个高速缓存组存放不同的对象。比如，一个高速缓存存放进程标识符task_struct, 一个高速缓存存放索引节点对象inode。kmalloc接口也建立在slab层之上。

每个高速缓存又被划分为slab。slab由一个或多个页组成。程序申请一个数据结构时，

• 先从部分满的slab分配资源，
• 没有部分 满的slab时，从空slab分配资源
• 没有空slab时，新建slab

这可以减少内存碎片。

举个例子，inode结构，它是由inode_cachep高速缓存来分配的。

在栈上的静态分配

内核栈需要存储的是内核模式下的上下文信息，这包括CPU寄存器状态、内核函数调用的参数和返回地址等。这是为了与用户空间隔离，才建立的内核栈。

进程在内核有一个内核栈，中断程序也可以获得一个栈。

在栈上工作

一旦栈溢出了，就会覆盖掉临近栈末端的数据。进行动态分配是一种明智的选择。

高端内存的映射

将高端物理地址内存映射到内核空间上。

虚拟文件系统

VFS虚拟系统，是一个抽象层。既然是一层，就必然会使用相关信息，给上层提供一个接口。他的接口主要是位于VFS对象的结构体中，之后要讲。

文件系统抽象层

内核底层提供了抽象层，使得Linux支持各种文件系统。（如果是FAT或NFTS等非Unix风格的文件系统，也必须在内存提供索引节点结构体，这会带来很大的开销）

每一层都需要提供一个接口，供上层使用。

上图中文件系统部分，它可以是ext4、NFTS、FAT等文件格式，每种文件格式都提供了向物理磁盘读写数据的接口。这些接口会供上层使用。

操作系统提供给用户的是write系统调用。

Unix文件系统

四种抽象概念：

• 文件，
• 目录项，目录的名字。目录也是普通文件，他的文件内容包含该目录的所有文件，VFS把目录当作文件对待，可以对目录执行与文件相同的操作。
• 索引节点，inode。索引节点是一个独立于文件本身的数据结构，它存储文件的相关信息，如权限，大小（文件的元数据）。
• 安装点

文件系统的控制信息是存储在超级块中。

VFS对象及其数据结构

• 超级块对象，代表一个具体的已安装文件系统
• 索引节点对象，代表一个具体文件
• 目标项对象，代表一个目录项，是路径的一个组成部分（不是目录对象，目录项对象是文件系统中的一个文件或目录的名称）
• 文件对象，代表由进程打开的文件

每个主要对象结构体（比如上面的四个对象）都包含了一个操作对象结构体，这些操作对象结构体包含了一些函数指针，描述了针对该对象可以使用的方法。对于很多方法来说，可以直接使用VFS提供的通用函数，也可以替换为实际文件系统对应的独有方法。

超级块对象

该对象由super_block结构体表示，在安装操作系统时，会从磁盘读取文件系统超级块，并把其信息填充到内存中的超级块对象中。

超级块操作

上面的超级块对象中包含一个成员s_op，它是之前讲过的包含了函数指针的结构体。这个结构体的每一项都是指向超级块操作函数的指针，这个超级块操作函数执行文件系统和索引节点的低级操作。

常见的几种操作：

索引节点对象

索引节点对象包含了内核在操作文件或目录需要的全部信息。

索引节点需要从磁盘读入内存。分为两种情况

• 是Unix风格的文件系统，那么索引节点直接从磁盘索引节点读入
• 不是Unix风格的文件系统，那么物理文件系统没有索引节点，所以会将文件的相关信息和文件的内容都作为文件的一部分来存放。这会导致没有将控制信息和数据分开。

不管哪种方式，索引节点对象都需要在内存中创建。

索引节点对象由inode结构体表示。一个索引节点（当要访问某个文件时，才在内存中创建）代表文件系统中的一个文件。这个文件也可以是设备或管道这样的特殊文件。在结构体中会有一些和特殊文件相关的项，比如i_pipe、i_bdev。

索引节点操作

inode结构体也包含了一个inode_operations项，它描述了VFS用来操作该索引节点的所有方法。

dentry 结构代表了目录项，即文件系统中的一个文件或目录的名称。下面是一些结构体中包含的函数指针。

目录项对象

VFS把目录和文件都看成是相同的。路径的每个组成部分都由一个索引节点表示，比如inode可以表示一个文件，也可以表示一个目录。

VFS需要执行目录相关的操作，为了方便查找，引入了目录项的概念。路径的每个部分都是一个目录项对象，比如/bin/vi, /、bin、vi都是目录项对象。

目录项对象没有对应的磁盘数据结构，VFS会根据字符形式的路径名现场创建它。

目录项状态

三种有效状态：

• 被使用，一个被使用的目录项对应一个有效的索引节点，并且该对象有一个或多个使用者(即d_count为正值), 这意味着它正被VFS使用，因此不能被丢弃
• 未被使用，一个被使用的目录项对应一个有效的索引节点，并且该对象没有被VFS使用。该目录项对象仍然指向一个有效对象，而且被保留在缓存中，之后需要时可以迅速的使用。
• 负状态，没有对应的索引节点，因为索引节点已经被删除了。

目录项缓存

如果VFS按层解析路径名中所有的元素，这非常费时间，所以内核会把目录项对象缓存在目录项缓存（dcache）中。

目录项缓存包括三个部分：

• “被使用的”目录项链表，
• “最近被使用的”双向链表，未被使用的和负状态的链表都在该链表中
• 散列表和散列函数用来快速的将路径解析为相关的目录项对象。

文件对象

文件对象是已打开的文件在内存中的表示，文件对象只在进程观点上代表已打开文件，（文件对象指向目录项，目录项指向索引节点，索引节点指向每一个文件的实际位置）

和进程有关的数据结构

每个进程都有一组打开的文件，如根文件系统、当前工作目录、安装点等。

有三个数据结构将VFS层与系统的进程联系在一起。

• files_struct, 进程task_struct中的files目录项指向这个结构体。file_struct中的fd_array数组包含了指向文件对象的指针。
• fs_stuct，进程task_struct中的fs项指向这个结构体。它包含文件系统和进程相关的信息。其中会包含root路径和当前工作目录路径。
• namespace结构体

进程地址空间

内存描述符

内核使用内存描述符结构体来标识进程的地址空间，用mm_struct表示，它有两个成员，mmap与mm_rb都描述该地址空间的全部内存区域，前者以链表存放，后者以二叉树存放。

分配内存描述符

进程描述符中的mm域指向了该进程使用的内存描述符。

进程可以通过allocate_mm从slab缓存中得到mm_struct结构体。

也可以将mm域指向父进程的内存描述符，这样该进程就是线程了。

mm_struct与内核线程

内核线程没有进程地址空间，没有内存描述符，mm域为空——他们没有用户上下文。

但是内核线程还是需要访问内核内存，为了避免向内核线程分配内存描述符，内核线程会直接使用前一个进程的内存描述符，但仅仅使用与内核内存相关的内存。

虚拟内存区域

内存区域用vm_area_struct结构体表示。内存区域描述了指定地址空间内连续区域上的一个独立内存范围。每个内存区域都有一致的属性，比如访问权限等。

实际的内存区域

如果一段区域是不可写的或共享的，那么内核只需要在内存为文件保留一份映射。

mmap和do_mmap：创建内存区域