Linux之kernel(1)系统基础理论(4)

Linux之Kernel(1)系统基础理论(4)

Author: Once Day Date: 2025年2月16日

一位热衷于Linux学习和开发的菜鸟，试图谱写一场冒险之旅，也许终点只是一场白日梦…

漫漫长路，有人对你微笑过嘛…

全系列文章可参考专栏: Linux内核知识_Once-Day的博客-CSDN博客

参考文章:

• openEuler OS知识连载 - 知乎
• 引言 - rCore-Camp-Guide-2024A 文档
• 计算机操作系统知识点总结（有这一篇就够了！！！）-CSDN博客
• 5万字、97 张图总结操作系统核心知识点 - 程序员cxuan - 博客园
• 【王道】操作系统 知识点总结（合集）【超详细！】 - Zyyyyyyyyy - 博客园
• 全方位剖析Linux操作系统，太全了-linux操作系统的特点
• 《现代操作系统》

1. 调度介绍

进程和线程是操作系统中两个基本的执行单位。进程是资源分配的基本单位，而线程是CPU调度的基本单位。每个进程都有自己独立的地址空间、文件资源、内存资源等，而一个进程中可以包含多个线程，这些线程共享进程的资源，但每个线程有自己独立的运行栈和程序计数器。

为了让系统中多个进程和线程能够有序地执行，操作系统需要对它们进行调度。调度的目的是为了提高系统的效率，合理利用系统资源，让各个进程和线程都能够获得执行的机会。

对于进程调度，操作系统主要采用以下几种调度策略:

• 先来先服务(FCFS)：按照进程到达就绪队列的先后顺序来调度，先来的进程先执行。
• 最短作业优先(SJF)：优先调度估计运行时间最短的进程。
• 优先级调度：按照进程的优先级来调度，优先级高的进程先执行。优先级可以是静态指定的，也可以是动态计算的。
• 时间片轮转(RR)：按照FCFS策略排序，但每个进程只能执行一个时间片，用完时间片就要重新排队。
• 多级反馈队列：设置多个就绪队列，每个队列优先级不同，时间片大小也不同。新到达的进程先进最高优先级队列，如果用完时间片还没执行完，就进入下一级队列。

下面是不同调度策略的对比表：

对于线程调度，操作系统通常采用以下策略:

• 抢占式优先级调度：优先调度优先级高的线程，高优先级线程可以抢占低优先级线程的CPU。
• 时间片轮转：线程按时间片轮流使用CPU，当前线程用完分配的时间片后，切换到下一个线程执行。

除了这些基本调度策略，现代操作系统往往采用更加复杂的调度算法，比如多级反馈队列、彩票调度、公平调度等，以平衡CPU利用率、周转时间、响应时间等多方面的性能指标。

同时，很多操作系统还支持线程的亲和性(affinity)和负载均衡(load balance)机制。线程亲和性让线程绑定在特定CPU核心上执行，减少线程迁移的开销；负载均衡让系统动态地将线程分配到负载较低的CPU核心，充分利用多核性能。

1.1 三级调度

高级调度(作业调度)，也称为作业调度或长程调度，发生在用户作业提交给系统之后、作业被放入作业队列之前。高级调度负责决定多个提交的作业中哪些可以进入系统执行，哪些暂不能进入系统执行而应该等待。

高级调度的主要目的是为了提高系统吞吐量和资源利用率，平衡系统负载。它需要考虑作业的类型、优先级、估计执行时间、资源需求等因素，来选择合适的作业进入系统执行。

一些常见的高级调度策略包括先来先服务(FCFS)、最短作业优先(SJF)、响应比高者优先(HRN)等。

中级调度(内存调度)，也称为内存调度或中程调度，发生在作业被高级调度选中进入系统后、被低级调度选中执行前。中级调度负责决定多个进入系统的作业中哪些可以进入内存等待执行，哪些暂时放到外存等待调入内存。

中级调度的主要目的是为了提高内存和CPU的利用率，减少作业的平均周转时间。当内存空间不足以容纳所有进入系统的作业时，中级调度需要将部分作业换出到外存，等到内存空间足够时再换入内存。这个过程称为内存换入换出(swapping)。

一些常见的换入换出策略包括先进先出(FIFO)、最少使用(LRU)、最佳适配(Best Fit)等。此外，中级调度还需要与虚拟存储管理机制配合，采用请求分页、请求分段等方式来实现内存的高效管理。

低级调度(进程调度)，也称为进程调度或短程调度，发生在进程已经进入内存、等待CPU执行的阶段。低级调度负责决定多个处于就绪状态的进程中哪个可以获得CPU执行，以及执行多长时间。

低级调度的主要目的是为了提高系统的响应性和公平性，让各个进程都能够合理分配CPU时间。低级调度需要考虑进程的优先级、时间片大小、就绪队列的排队策略等因素，来选择合适的进程执行。

1.2 调度目标

操作系统调度的五个主要目标：CPU利用率、系统吞吐率、周转时间、等待时间和响应时间。

CPU利用率指CPU处于非空闲状态的时间比例，表示CPU被充分利用来执行任务的程度。maximizing CPU utilization 是调度的重要目标之一。

理想情况下，我们希望CPU一直处于繁忙状态，不存在空闲浪费。但实际上，由于I/O操作、进程同步等因素的影响，CPU难免会出现空闲等待。好的调度算法应该尽量减少CPU的空闲时间，提高其利用率，通常可以通过时间片轮转、多级队列等方式来实现。

系统吞吐率指系统在单位时间内完成作业的数量。maximizing throughput 也是调度追求的重要目标。

high system throughput 意味着系统能够在较短时间内处理更多作业，工作效率较高。为了提高吞吐率，调度算法通常会优先调度短作业、I/O密集型作业等，尽快完成更多作业。同时，高吞吐率还需要平衡资源利用，避免某些资源被过度占用而成为瓶颈。

周转时间(turnaround time)指一个作业从提交到完成的总时间，包括作业在各个队列中等待的时间、实际执行的时间和I/O操作的时间。minimizing turnaround time 是调度希望达成的另一个目标。

shorter turnaround time 意味着作业从开始到结束的耗时更短，用户能够更快地获得作业的结果。为了缩短平均周转时间，调度算法通常会考虑作业的预期执行时间，给予短作业更高优先级，先完成处理时间较短的作业。

等待时间(waiting time)指一个进程从进入就绪队列到第一次获得CPU执行的时间。minimizing waiting time 是调度力求实现的又一目标。

shorter waiting time 意味着进程从就绪到开始执行的等待时间更短，不会出现某些进程长时间得不到响应的情况。为了减少平均等待时间，调度算法通常采用时间片轮转，让each process 能够较快地获得一定时间的执行，避免进程饥饿(starvation)。

响应时间(response time)指用户提交请求到系统开始产生响应的时间。minimizing response time 对于交互式系统尤其重要。

shorter response time 意味着用户的请求能够更快地得到系统的响应和反馈，提升了用户体验。为了缩短响应时间，调度算法通常会为交互式进程设置较高优先级，让它们能够抢占式地获得CPU，及时响应用户的操作。

1.3 调度实现

调度程序(Scheduler)，也称为调度器，是操作系统内核中负责进程调度的模块。它主要包含两部分：调度策略和调度机制。

调度策略决定了调度算法的选择和配置，即按照什么原则和优先级来调度进程。这涉及前面讨论的各种调度算法，如FCFS、SJF、优先级调度、时间片轮转等。

调度机制则负责实现调度策略，包括将进程插入就绪队列、将进程从就绪队列中选出、分配CPU时间片、进行进程切换等具体操作。调度机制的实现依赖于底层硬件和操作系统的支持，如定时器、上下文切换指令等。

操作系统进行进程调度有以下几个主要时机:

• 进程状态发生变化时，如进程由运行态变为阻塞态(等待I/O或同步原语)，或由就绪态变为运行态。
• 时间片用完时，当前运行进程的时间片耗尽,需要进行调度选择下一个进程执行。
• 有更高优先级的进程进入就绪队列时，可能触发抢占式调度，暂停当前进程，转而执行优先级更高的进程。
• 在中断处理程序中，硬件中断或软中断会打断当前进程的执行，转而执行中断处理，之后根据需要进行调度。

根据进程切换的时机和触发方式，进程调度可以分为以下几种方式:

• 非剥夺调度(非抢占调度)：一旦进程开始执行，它就一直执行下去，直到自己主动放弃CPU或执行完毕。
• 剥夺调度(抢占调度)：在进程执行过程中，如果有更高优先级的进程就绪，或时间片用完，当前进程会被暂停并被迫让出CPU。
• 协作式调度：进程主动周期性地释放CPU控制权，通过显式的系统调用(如yield())让调度程序选择下一个执行的进程。

现代通用操作系统基本都采用抢占式调度，以提供更好的响应性和实时性。而早期和某些特殊场景下的操作系统可能采用非抢占调度或协作式调度。

当调度程序决定从一个进程切换到另一个进程时，就会发生进程上下文切换(Context Switch)。上下文切换需要保存当前进程的执行现场，并恢复将要执行进程的现场，这个过程涉及以下几个步骤:

• 保存当前进程的CPU寄存器状态(如程序计数器PC、程序状态字PSW、通用寄存器等)到进程控制块PCB中。
• 更新PCB中的进程状态、优先级、统计信息等属性。
• 将当前进程的PCB放入相应的队列(如就绪队列、阻塞队列)。
• 从就绪队列中选择下一个要执行的进程，并从其PCB中恢复CPU寄存器状态。
• 更新内存管理相关的数据结构，如页表、地址映射等(如果使用虚拟内存)。
• 将CPU控制权转移给新选中的进程，开始执行其指令。

上下文切换是一个比较耗时的操作，涉及大量的数据保存和恢复。因此，过于频繁的进程切换会导致系统开销加大，从而影响整体性能。所以调度时机和频率的选择需要适度把握。

当系统中没有任何用户进程处于就绪状态时，调度程序会选择一个特殊的系统进程来执行，称为空闲进程(或闲逛进程)。空闲进程通常具有最低优先级，它的主要任务是释放CPU，进入低功耗状态，直到有新的进程就绪。

空闲进程的执行可以避免CPU空转浪费，同时也为操作系统提供了一个维护系统状态、处理后台任务的时间窗口。一些操作系统还利用空闲进程来执行周期性的内存整理、缓存刷新等系统任务。

2. 调度算法

2.1 批处理中的调度

批处理系统中常用的几种调度算法：先来先服务(FCFS)、最短作业优先(SJF)、最短剩余时间优先(SRTN)和多级反馈队列调度算法(Multilevel Feedback Queue)。

（1）先来先服务(First-Come, First-Served, FCFS)

FCFS是最简单的调度算法，它按照作业到达的先后顺序依次执行。先提交的作业先执行，后提交的作业等待前面的作业完成后再执行。

FCFS的优点是简单易实现，公平对待每个作业。但它的缺点也很明显：平均等待时间可能很长，尤其是当一个长作业阻塞在队首时，后面的所有短作业都必须等待它完成，导致"护航效应"(Convoy Effect)。

FCFS适合于CPU繁忙型作业较多、作业执行时间差异不大的批处理系统。

（2）最短作业优先(Shortest Job First, SJF)

SJF优先调度执行时间最短的作业。它要求作业提交时提供预估的执行时间，调度程序按照执行时间从短到长的顺序依次调度作业。

SJF的优点是可以显著减少作业的平均等待时间，提高系统吞吐率。短作业无需等待长作业完成，更快地得到执行。

但SJF的缺点是对长作业不利，可能导致长作业饥饿。此外，要求用户预估执行时间也不太现实，预估的准确性影响调度的效果。

SJF适合于作业执行时间差异较大、并且能够准确预估执行时间的批处理环境。

（3）最短剩余时间优先(Shortest Remaining Time Next, SRTN)

SRTN是SJF的抢占式版本。当一个新作业到达时，如果它的执行时间比当前正在执行的作业的剩余时间更短，则抢占当前作业，优先执行这个新作业。

SRTN进一步优化了SJF，新到达的超短作业可以得到最快响应，不必等待正在运行的长作业完成。这有助于缩短平均周转时间。

但SRTN同样存在对长作业不利、可能导致饥饿的问题。而且频繁的抢占和上下文切换也会带来一定开销。

SRTN适合于作业执行时间差异很大、并且作业到达时间随机分布的批处理环境。

（4）多级反馈队列调度算法(Multilevel Feedback Queue, MFQ)

MFQ是一种更复杂、更全面的调度算法，综合考虑了作业的执行时间、等待时间、系统资源利用等多方面因素。它设置了多个就绪队列，每个队列对应不同的优先级和时间片。

• 新到达的作业首先进入第1级队列，该队列优先级最高、时间片最小。
• 如果作业在当前队列的时间片内完成，则撤离系统；如果未完成，则进入下一级队列等待，并获得更大的时间片。
• 随着作业在系统中等待时间的增加，逐级下降直至进入最后一级队列，该队列优先级最低、时间片最大。
• 各级队列采用不同的调度算法，高优先级队列使用FCFS，低优先级队列使用RR。
• 每隔一个时间片，就检查高优先级队列是否有作业，如果有则抢占低优先级队列的作业。

MFQ的核心思想是让短作业和I/O繁忙型作业优先执行，让长作业逐步下降到低优先级，防止其长期占用CPU。这种策略兼顾了系统吞吐率和用户响应时间。

MFQ适合于通用的、负载较重的批处理系统，能够在多种作业类型混合的情况下取得较好的调度效果。但它的参数配置(如队列数、时间片大小)需要根据系统实际情况进行调优。

2.2 交互式系统中的调度

交互式系统中常用的几种调度算法：轮转调度(Round Robin)、优先级调度(Priority Scheduling)、彩票调度(Lottery Scheduling)和公平分享调度(Fair-Share Scheduling)。

（1）轮转调度(Round Robin, RR)

RR是一种基于时间片的调度算法，适用于分时系统。它将就绪队列看作一个循环队列，每个进程被分配一个固定的时间片(如10ms)。调度程序按照先来先服务的原则，依次让每个进程执行一个时间片，时间片用完则剥夺CPU，将进程重新加入队尾，轮转到下一个进程执行。

RR的优点是公平、响应快，每个进程都能在有限时间内获得响应。时间片的大小可以调节系统的响应时间和切换开销。

但RR也存在一些问题，如平均周转时间较长，高响应比的进程可能会饥饿，I/O繁忙型进程会频繁阻塞和唤醒。

RR适合于大部分通用的分时系统，用户数较多、交互频繁的场景。

（2）优先级调度(Priority Scheduling)

优先级调度根据进程的优先级来决定执行顺序。每个进程被赋予一个优先级，优先级越高的进程越先执行。优先级可以是静态指定的，也可以是动态计算的。

优先级调度的优点是能够灵活控制进程的重要程度，高优先级的进程可以优先响应，低优先级的进程在系统空闲时得到执行。

但优先级调度也存在一些问题，如低优先级进程可能长时间得不到执行(饥饿)，高优先级进程可能独占CPU导致系统失去响应。

为了解决这些问题，优先级调度通常与其他调度机制结合使用，如老化(aging)机制动态提升等待时间过长的进程优先级，或者使用多级反馈队列根据进程行为动态调整优先级。

优先级调度适合于有明确重要度区分的交互式系统，如实时控制、多媒体应用等。

（3）彩票调度(Lottery Scheduling)

彩票调度是一种基于随机性的调度算法。它将系统的CPU时间看作一组彩票，每个进程持有一定数量的彩票，彩票数量代表了进程的权重。调度程序在每个调度点随机抽取一张彩票，拥有该彩票的进程获得执行机会。

彩票调度的优点是实现简单，引入随机性避免了饥饿问题。进程可以通过调整彩票数量来控制执行的份额和优先级。

但彩票调度也存在一些问题，如引入了非确定性，调度结果具有随机波动。短期内可能出现某些进程被频繁选中而其他进程很少得到机会的情况。

彩票调度适合于对公平性要求较高、负载均衡的交互式系统，如分布式计算、网格计算等。

（4）公平分享调度(Fair-Share Scheduling)

公平分享调度的目标是在进程组(或用户)之间公平地分配系统资源，防止个别用户或进程组长期垄断系统。它根据进程的资源使用历史、优先级、用户权重等因素动态调整调度策略。

具体来说，公平分享调度跟踪每个进程组的资源使用情况，并设置一个资源使用目标(如CPU份额)。如果一个进程组的资源使用超过了目标，则降低其优先级；如果低于目标，则提高其优先级。这样，资源使用较少的进程组能够获得更多的调度机会，而资源使用过多的进程组受到限制。

公平分享调度的优点是能够在用户之间实现资源分配的公平性和合理性，防止少数用户垄断系统。

但公平分享调度的计算开销较大，需要维护每个进程组的资源使用统计信息。此外，资源使用目标的设置和动态调整策略也需要根据系统的实际情况进行优化。

公平分享调度适合于多用户共享的大型交互式系统，如分时系统、服务器集群等。

2.3 实时系统中的调度

实时系统是指那些对任务的响应时间有严格要求的计算机系统。实时任务必须在指定的截止时间(deadline)之前完成，否则就会导致系统失效或发生灾难性后果。根据对截止时间的严格程度，实时任务可以分为硬实时任务和软实时任务。

（1）硬实时调度(Hard Real-Time Scheduling)

硬实时任务必须绝对地在截止时间之前完成，任何违反截止时间的情况都是不允许的，否则会导致严重的经济损失或人身伤害。硬实时调度的目标就是确保所有硬实时任务在最坏情况下也能满足截止时间约束。

常见的硬实时调度算法包括:

• 速率单调调度(Rate Monotonic Scheduling, RMS)：为周期性任务分配固定优先级，周期越短优先级越高。
• 最早截止时间优先调度(Earliest Deadline First, EDF)：动态分配优先级，离截止时间越近的任务优先级越高。
• 最少松弛时间优先调度(Least Laxity First, LLF)：优先调度松弛时间(截止时间-执行时间)最少的任务。

硬实时调度除了要满足截止时间约束，还需要考虑任务的可调度性分析、资源访问控制、容错机制等，以构建一个可预测、安全、可靠的实时系统。

硬实时系统的应用场景包括工业控制、航空航天、机器人、医疗设备等领域。

（2）软实时调度(Soft Real-Time Scheduling)

与硬实时不同，软实时任务允许偶尔违反截止时间，只要这种违反的程度和频率在可接受的范围内即可。也就是说，软实时系统允许一定程度的性能降级，但要尽可能地满足大部分任务的截止时间要求。

常见的软实时调度算法包括:

• valuative 调度：根据任务的重要性(value)动态调整优先级，重要性越高的任务优先级越高。
• 反馈调度：根据任务的动态行为(如执行时间、资源使用)调整优先级，表现好的任务优先级提高，表现差的任务优先级降低。
• 预测执行时间调度(Predictive Execution Time Scheduling)：根据任务的预测执行时间来安排调度，尽量满足大部分任务的截止时间。

软实时调度通常与其他非实时任务混合运行，需要在实时性和系统利用率之间权衡。一些软实时系统还会结合服务质量(Quality of Service, QoS)管理机制，根据系统负载动态调整任务的服务质量，以满足实时性要求。

软实时系统的应用场景包括多媒体播放、网络通信、人机交互等领域。

2.4 Linux的CFS调度

CFS(Completely Fair Scheduler)调度算法是Linux从2.6.23版本开始引入的默认进程调度算法，其设计目标是实现完全的公平性，即让每个进程获得与其权重成正比的CPU时间。与传统的时间片轮转调度不同，CFS摒弃了时间片的概念，而是根据进程的权重动态计算其应获得的CPU时间。

CFS为每个进程维护一个虚拟运行时间vruntime，表示该进程已经运行的时间。但这个时间不是实际的物理时间，而是根据进程的权重scaled 后的一个值。权重越高的进程，其vruntime增长得越慢；权重越低的进程，其vruntime增长得越快。

具体来说，每个进程的vruntime更新公式为:

vruntime += delta_exec * (NICE_0_LOAD / weight)

其中，delta_exec是进程实际运行的时间，NICE_0_LOAD是一个常量(代表nice值为0的进程的权重)，weight是进程的权重。

CFS使用一棵以vruntime为key的红黑树来组织所有可运行进程。红黑树是一种自平衡二叉搜索树，可以高效地进行插入、删除、查找等操作。

在调度时，CFS总是选择vruntime最小的进程来运行，即红黑树最左边的节点。当进程执行一段时间后，其vruntime会增大，从而沿着树向右移动。这样，vruntime较小的进程总是优先被调度，而vruntime较大的进程要等待更长时间。

CFS引入了一个重要的参数：调度延迟(sched_latency)。它表示一个进程被调度后应该运行多长时间。调度延迟的默认值是6ms，可以通过sysctl命令进行调整。

CFS根据当前可运行进程的数量和调度延迟计算出一个理想的最小运行时间(sched_min_granularity)。每个进程在一次调度中至少应该运行这么长时间，以减少上下文切换的开销。

CFS使用进程的权重来决定其获得CPU时间的多少。权重是一个正整数，默认为1024。权重越高，进程获得的CPU时间就越多。

进程的权重可以通过Nice值来调整。Nice值是一个整数，范围从-20到19,默认为0。Nice值越小，进程的权重就越大，优先级越高。进程的权重和Nice值的关系可以用如下公式表示:

weight = NICE_0_LOAD / (1.25 ^ nice)

其中，NIE_0_LOAD是一个常量，代表nice值为0的进程的权重，通常为1024。

CFS还支持组调度，即对进程组而不是单个进程进行调度。每个进程组也有一个权重，组内进程共享这个权重。这样可以实现更灵活的资源分配策略，如限制一个用户或者一个任务的总CPU使用时间。

组调度通过一个层次结构的红黑树来实现，每个节点代表一个进程组。组内进程的vruntime相对于组的vruntime计算，组间的vruntime相对于父节点的vruntime计算。

对于实时进程，CFS采用了一种简单的策略：总是优先调度实时进程，直到实时进程用完了它们的时间片。这种策略可能会导致普通进程饥饿，因此需要谨慎使用实时进程。

CFS通过两个红黑树来分别管理实时进程和普通进程，实时进程的红黑树总是先于普通进程的红黑树被访问。
个进程进行调度。每个进程组也有一个权重，组内进程共享这个权重。这样可以实现更灵活的资源分配策略，如限制一个用户或者一个任务的总CPU使用时间。