内核简介

单内核&微内核

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

微内核：内核的功能被划分为多个单独的过程，每一个过程叫做一个服务器，某些服务器运行在用户空间，有些运行在内核空间中，所以不同服务器之间的通过消息传递机制通信：系统采用了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)来调整进程的状态。

进程上下文

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

进程家族树

所有进程都是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时需要传入额外的参数：

1
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中能避免并发访问的代码

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

要保护什么

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

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

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

死锁