学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
循环渐进Forward-CSDN博客
进程调度简介
1.2进程查看命令
1.3进程的几个要素
二、进程的生命周期
2.1进程状态文字描述
2.2进程状态的切换
2.3task_struct数据结构
2.4进程优先级
⑴优先级的代码表示
⑵Linux内核下的进程分类
⑶优先级的在不同类型进程的分配
2.5进程调度的重要性
⑴提升系统性能
⑵确保公平性
三、进程系统调用
3.1系统调用函数
⑴fork系统调用代码
⑵vfork系统调用代码
⑶clone系统调用代码
⑷进程退出
⑸内核线程
3.2常见的进程调度算法
⑴先来先服务（FCFS）
⑵短作业优先（SJF）
⑶优先级调度
⑷轮转调度（RR）
⑸多级反馈队列调度
⑹高响应比优先调度算法
四、进程调度的实现与优化
4.1调度算法的选择
4.2调度器的设计与实现
4.3进程状态的转换机制
进程调度简介
在Linux中，进程是最基本的执行单位。进程调度在整个操作系统中属于核心地位，是操作系统实现多任务处理的关键操作，确保每个进程在有限的CPU资源下有序的完成相应操作。
在Linux操作系统中，同一时间下不仅仅只有一个进程在执行任务而是多个进程同时竞争有限的CPU资源。若没有进程调度操作，整个系统可能会陷入混乱，例如你正在听着歌却突然把歌停了给你播放视频。因此，进程调度尤为重要。
进程调度的高效性会直接影响到系统的性能。一个高效的进程调度算法能够迅速完成大量进程间的切换，从而确保CPU资源得到最大程度的利用。以轮转调度（Round Robin, RR）算法为例，该算法将CPU时间分割成多个固定的时间片，每个进程依次占用一个时间片进行执行。这种方式确保了所有进程都能获得一定的执行时间，进而提升了系统的整体处理能力。据统计，在合理设定时间片长度的情况下，轮转调度算法能显著提升系统吞吐量，增幅可达20%至30%。
公平性同样是进程调度中的一项关键考量。它要求每个进程都能获得适当的CPU时间片，以防止某些进程因长时间无法执行而陷入饥饿状态。例如，在优先级调度算法中，若高优先级进程持续不断地产生，可能会导致低优先级进程长时间得不到执行机会。为解决这一问题，可以采取老化等技术手段，逐步提高那些等待时间过长的进程的优先级。
公平性也是进程调度的重要目标之一。每个进程都应该有机会获得合理的 CPU 时间片，避免饥饿现象的发生。例如，优先级调度算法中，如果源源不断地产生高优先级的进程，那么低优先级的进程可能会长时间得不到执行。为了解决这个问题，可以采用老化等技术，逐渐增加等待很长时间的进程的优先级。
1.2进程查看命令
⑴ps (Process Status)命令是Linux及类Unix系统中最基础的进程查看工具之一，它提供了当前系统中进程状态的一次性快照视图。通过不同的选项，您可以获取到不同级别的进程信息。
以下是一些常用选项及其作用：
-e 或 --every：显示系统中所有的进程。
-f 或 --full：提供完整的格式输出，包括进程树状关系和环境变量等额外信息。
-l 或 --long：长格式输出，包含更多详细信息，如F旗表示进程正在等待文件锁。
-u 或 --user：按照用户来显示进程，并显示每个进程的CPU和内存使用情况。
-aux 是一个常见的组合选项，用于显示系统中所有用户的全部进程，包括后台进程（不与终端关联的进程）。
-
进程列表：按照默认排序（通常是CPU使用率或优先级）列出正在运行的进程及其相关信息，如PID、USER（执行进程的用户）、PR（优先级）、NI（nice值，影响优先级）、VIRT（虚拟内存大小）、RES（常驻内存大小）、%CPU和%MEM（CPU和内存使用百分比）等。
-
系统总体状态：包括系统运行时间、登录用户数、系统负载、CPU和内存的整体使用状况等统计数据。
-
交互式操作：在top运行过程中，用户可以通过键盘输入相应的命令（如按P键切换到按CPU使用率排序，按M键切换到按内存使用率排序，或使用k键杀死指定进程等）来进行进一步的进程管理和监控。
1.3进程的几个要素
有一段程序待其执行
有进程专用的系统堆栈空间
在内核有task_struct结构体
进程有独立的存储空间，拥有专用的用户空间
二、进程的生命周期
2.1进程状态文字描述
Linux操作系统属于多任务操作系统，系统中的每个进程能够分时复用CPU时间片，通过有效的进程调度策略实现多任务并行执行。而进程在被CPU调度运行，等待CPU资源分配以及等待外部事件时会属于不同的状态。
共有五种状态：
创建状态：新进程刚刚被创建，尚未开始执行。
就绪状态：进程已准备好所有必需资源，等待CPU分配时间片执行。
执行状态：进程已获得CPU资源并在其中运行。
阻塞状态：进程因等待某个资源或事件而暂时停止运行，从CPU队列中移除。
终止状态：进程已完成执行或被终止，不再存在。
进程状态程序中的体现：
#define TASK_RUNNING 0x00000000
#define TASK_INTERRUPTIBLE 0x00000001
#define TASK_UNINTERRUPTIBLE 0x00000002
#define __TASK_STOPPED 0x00000004
#define __TASK_TRACED 0x00000008
TASK_RUNNING 表示进程处于可运行状态。这意味着进程已经准备好在CPU上执行，并且调度器可以选择它来进行运行。当进程获取到CPU时间片时，它就会进入运行状态。
TASK_INTERRUPTIBLE 表示进程处于可中断睡眠状态。这种状态下，进程正在等待某个事件发生（例如I/O操作完成、锁可用等），并且如果收到信号或者等待的条件满足，它可以被唤醒并重新加入到可运行队列中。在可中断睡眠期间，进程可以响应信号并改变其状态。
TASK_UNINTERRUPTIBLE 表示进程处于不可中断睡眠状态。类似可中断睡眠，进程同样在等待某种资源或事件，但是在此状态下，进程不会响应任何信号，即使接收到信号也不会立即醒来，除非等待的资源变为可用或特定条件达成。
__TASK_STOPPED 标志意味着进程已停止执行，通常是因为收到了SIGSTOP或SIGTSTP这样的停止信号，或者是调试器暂停了进程。停止的进程不会消耗CPU资源，直到收到SIGCONT信号恢复执行。
__TASK_TRACED 表示进程正在被调试器或其他跟踪工具追踪，并进入了跟踪停止状态。在这种状态下，进程同样不会执行，等待调试器的进一步操作，比如单步执行、继续执行等。
这些状态标志会被组合在一个进程控制块（PCB，在Linux内核中表现为task_struct结构体的一个成员变量state）中，以表示进程的当前状态。调度器根据这些状态决定何时何地将进程投入运行或从运行状态移除。在实际的内核源码中，为了准确反映进程状态，这些宏可能会与其他标志位一起使用或组合起来形成更复杂的状态标识。
2.2进程状态的切换
如下图，便是进程进行状态之间的切换，这些工作都是有调度器来完成的。
2.3task_struct数据结构
进程是操作系统调度的一个实体，需要对进程所必须资源做一个抽象化，此抽象化为进程控制块 (PCB，Process Control BLock) ，PCB在Linux内核里面采用task_struct结构体来描述进程控制块。Linux内核涉及进程和程序的所有算法都围绕名为task_struct的数据结构而建立操作。具体Linux内核源码task_struct结构体核心成员如下（task_struct结构体过于庞大，暂时了解几个重要成员）task_struct定义在include\linux\sched.h：
__state：表示当前进程状态，例如可运行、睡眠、僵死等。
stack：指向进程的内核栈。
usage：引用计数，用于跟踪进程使用情况。
prio、static_prio和normal_prio：描述进程的调度优先级和策略。
se、rt和dl：分别对应CFS（完全公平调度器）、实时调度和Deadline调度的调度实体。
mm：指向进程的内存描述符结构（mm_struct），管理进程的虚拟内存。
active_mm：在没有独立内存空间时，指向当前活动的内存描述符。
exit_state、exit_code和exit_signal：进程退出时的状态、退出码和发送给父进程的信号。
pid和tgid：分别代表进程ID和线程组ID。
real_parent、parent、children和sibling：用于构建进程间的父子、兄弟关系，形成进程树。
files：指向进程打开的文件表，即files_struct结构体，记录所有已打开的文件描述符。
signal和sighand：管理和处理进程接收到的信号。
blocked、real_blocked和saved_sigmask：记录进程当前屏蔽的信号集合。
nsproxy：命名空间代理，用于管理和切换不同命名空间。
fs：指向文件系统信息结构，记录进程的当前工作目录、根目录等文件系统相关信息。
其他字段还包括了进程的调度统计信息、时间统计、内存页面错误统计、POSIX定时器、安全特性、审计信息等。
2.4进程优先级
⑴优先级的代码表示
描述进程的调度优先级和策略，之后的任务调度以及时间片分配都要用到优先级：
int prio;int static_prio;int normal_prio;unsigned int rt_priority;
int prio: 这个字段代表进程的动态优先级，它是根据进程的行为和系统负载动态调整的。在传统的Linux调度器（如CFS调度器）中，这个优先级通常被映射到调度实体（sched_entity）的一个虚拟运行时间（vruntime），而不是一个直观意义上的数字大小，较大的vruntime意味着较低的优先级。
int static_prio: 静态优先级，也称为nice值，在Linux中范围是-20至19，数值越小表示优先级越高。静态优先级可以通过nice值或者用户权限改变，但不会像动态优先级那样频繁变化。
int normal_prio: 此字段在某些Linux调度器实现中可能用来表示经过nice值调整后的正常优先级，它结合了静态优先级和可能的额外优先级调整因素。
unsigned int rt_priority: 实时优先级，仅适用于实时调度策略（如SCHED_FIFO或SCHED_RR）。实时进程有固定的优先级分配，rt_priority值越大，表示进程的实时优先级越高，抢占其他进程的可能性也就越大。实时进程一般不受nice值的影响，其优先级高于普通进程。在实时调度策略下，rt_priority用于确定进程在实时进程队列中的相对位置。
⑵Linux内核下的进程分类
在Linux内核中，进程可以按照其调度需求和优先级的不同分为不同的类别，主要包括：
SCHED_FIFO：实时进程中，优先级高的进程总是优先执行，一旦开始运行，除非进程主动放弃CPU（如阻塞等待I/O或睡眠），否则不会被优先级相同或更低的其他进程抢占。
SCHED_RR：同样是实时进程，但它在用完时间片后会重新加入队列等待下一次调度，这样可以保证在相同优先级的实时进程中实现时间片轮转。
普通进程（Normal Process）：又称为分时进程，这类进程在Linux系统中遵循默认的分时调度策略，如CFS（Completely Fair Scheduler）。它们按照各自权重（nice值）和虚拟运行时间（vruntime）来获取CPU时间片。nice值可以在[-20, 19]范围内调整，数值越小，优先级越高，但总体来说，普通进程之间是公平共享CPU资源的。
实时进程（Real-time Process）：实时进程在满足特定条件的情况下需要得到及时响应，具有更高的优先级。Linux内核提供两种实时调度策略：SCHED_FIFO（先进先出）和SCHED_RR（轮转调度）。
⑶优先级的在不同类型进程的分配
-
限期进程的优先级是-1;
-
实时进程的优先级1-99，优先级数值最大，表示优先级越高；
-
普通进程的静态优先级为: 100-139，优先级数值越小，表示优先级越高，可通过修改nice值改变普通进程的优先级，优先级等于120加 上nice值；
2.5进程调度的重要性
⑴提升系统性能
进程调度对系统性能的提升起着关键作用。通过合理地分配 CPU 资源，进程调度可以极大地提高 CPU 利用率。例如，在完全公平调度器（CFS）中，根据进程的虚拟运行时间来分配 CPU 时间，确保每个进程都能获得相对公平的执行机会，从而有效提高 CPU 的利用率。据统计，采用 CFS 的系统中，CPU 利用率可以提高 15% 至 20%。
系统吞吐量是衡量系统性能的另一个重要指标。良好的进程调度算法可以在单位时间内完成更多的进程，从而提高系统吞吐量。以多级反馈队列调度为例，它将就绪队列分成多个优先级不同的队列，每个队列采用不同的调度算法。短作业可以在高优先级队列中快速得到执行，而长作业则在低优先级队列中逐步执行，这样可以兼顾不同类型进程的需求，提高系统的整体吞吐量。实验表明，使用多级反馈队列调度的系统，吞吐量可以比传统的先来先服务调度提高 30% 至 40%。
此外，进程调度还可以降低周转时间、等待时间和响应时间。周转时间是指进程从提交到完成所花费的时间，等待时间是进程在就绪队列中等待的时间，响应时间是从进程提交到首次获得 CPU 时间的时间间隔。通过合理的调度算法，如短作业优先调度，可以优先执行短作业，减少这些时间指标。研究显示，在特定的工作负载下，短作业优先调度可以将平均周转时间降低 20% 至 30%，响应时间降低 15% 至 20%。
⑵确保公平性
公平性是进程调度的核心目标之一。为了避免进程饥饿现象，各种调度算法都采取了不同的措施。在优先级调度中，虽然高优先级的进程会优先获得 CPU 资源，但为了防止低优先级进程长时间得不到执行，可以采用动态调整优先级的方法。例如，随着低优先级进程的等待时间增加，逐渐提高其优先级，使其有机会获得 CPU 执行时间。
同时，一些调度算法还通过限制高优先级进程的执行时间来确保公平性。例如，在实时调度中，硬实时任务虽然要求在严格的时间限制内完成，但也不能无限占用 CPU 资源。调度算法会在保证硬实时任务按时完成的前提下，合理分配 CPU 时间给其他进程，以实现系统的整体公平性。
三、进程系统调用
3.1系统调用函数
当运行应用程序的时候，调用fork（）/vfork（）/clone（）函数就是系统调用。系统调用就是应用程序如何进入内核空间执行任务，程序使用系统调用执行一系列的操作: 比如创建进程、文件IO等等。
系统调用框图（使用Linux版本为6.1的内核，不同的内核其系统调用有点差异） 如下所示：
⑴fork系统调用代码
#ifdef __ARCH_WANT_SYS_FORK
SYSCALL_DEFINE0(fork)
{
#ifdef CONFIG_MMUstruct kernel_clone_args args = {.exit_signal = SIGCHLD,};return kernel_clone(&args);
#else/* can not support in nommu mode */return -EINVAL;
#endif
}⑵vfork系统调用代码
#ifdef __ARCH_WANT_SYS_VFORK
SYSCALL_DEFINE0(vfork)
{struct kernel_clone_args args = {.flags = CLONE_VFORK | CLONE_VM,.exit_signal = SIGCHLD,};return kernel_clone(&args);
}
#endif⑶clone系统调用代码
#ifdef __ARCH_WANT_SYS_CLONE
#ifdef CONFIG_CLONE_BACKWARDS
SYSCALL_DEFINE5(clone, unsigned long, clone_flags, unsigned long, newsp,int __user *, parent_tidptr,unsigned long, tls,int __user *, child_tidptr)
#elif defined(CONFIG_CLONE_BACKWARDS2)
SYSCALL_DEFINE5(clone, unsigned long, newsp, unsigned long, clone_flags,int __user *, parent_tidptr,int __user *, child_tidptr,unsigned long, tls)
#elif defined(CONFIG_CLONE_BACKWARDS3)
SYSCALL_DEFINE6(clone, unsigned long, clone_flags, unsigned long, newsp,int, stack_size,int __user *, parent_tidptr,int __user *, child_tidptr,unsigned long, tls)
#else
SYSCALL_DEFINE5(clone, unsigned long, clone_flags, unsigned long, newsp,int __user *, parent_tidptr,int __user *, child_tidptr,unsigned long, tls)
#endif
{struct kernel_clone_args args = {.flags = (lower_32_bits(clone_flags) & ~CSIGNAL),.pidfd = parent_tidptr,.child_tid = child_tidptr,.parent_tid = parent_tidptr,.exit_signal = (lower_32_bits(clone_flags) & CSIGNAL),.stack = newsp,.tls = tls,};return kernel_clone(&args);
}
#endif⑷进程退出
①、进程主动终止: 从main()函数返回，链接程序会自动添加到exit()系统调用; exit系统调用在内核定义如下\kernel\exit.c：
SYSCALL_DEFINE1(exit, int, error_code)
{do_exit((error_code&0xff)<<8);
}②、进程被动终止: 进程收到一个自己不能处理的信号;进程收到 SIGKILL等终止信息。
⑸内核线程
定义：它是独立运行在内核空间的进程，与普通用户进程区别在于内核线程没有独立的进程地址空间。task_struct数据结构里面有一个成员指针mm设置为NULL，它只能运行在内核空间。内核创建一个内核线程代码体现如下：
/** Create a kernel thread.*/
pid_t kernel_thread(int (*fn)(void *), void *arg, unsigned long flags)
{struct kernel_clone_args args = {.flags = ((lower_32_bits(flags) | CLONE_VM |CLONE_UNTRACED) & ~CSIGNAL),.exit_signal = (lower_32_bits(flags) & CSIGNAL),.fn = fn,.fn_arg = arg,.kthread = 1,};return kernel_clone(&args);
}3.2常见的进程调度算法
⑴先来先服务（FCFS）
先来先服务调度算法是一种最简单的调度算法，它按照进程到达的先后顺序进行调度。当一个进程进入就绪队列时，它会按照到达的顺序排队等待 CPU 的分配。这种算法的优点是实现简单，公平性较高，每个进程都按照其到达的顺序依次获得 CPU 时间。然而，它也存在明显的缺点。对于长进程来说，可能会长时间占用 CPU，导致后续到达的短进程和 I/O 繁忙型作业等待时间过长。例如，假设有三个进程 P1、P2 和 P3，P1 的执行时间为 30 秒，P2 的执行时间为 5 秒，P3 的执行时间为 20 秒。如果按照先来先服务的算法调度，P1 先执行，那么 P2 和 P3 就需要等待 30 秒后才能开始执行，这大大增加了短进程和 I/O 繁忙型作业的等待时间，降低了系统的整体效率。
⑵短作业优先（SJF）
短作业优先调度算法优先调度执行时间最短的进程。这种算法的目的是减少平均等待时间，提高系统的吞吐量。然而，它也存在一些问题。首先，它可能导致长作业饥饿，因为长作业可能一直等待短作业执行完毕后才能获得 CPU 时间。其次，准确估计作业的执行时间是非常困难的。在实际应用中，程序员很难准确估计作业的执行时间，通常会偏长估计，这可能导致算法的效果不如预期。例如，如果有一个长作业需要执行 100 秒，而不断有短作业到来，那么长作业可能永远也得不到调度，从而出现饥饿现象。
⑶优先级调度
优先级调度算法根据进程的优先级进行调度。每个进程都被赋予一个优先级，优先级高的进程优先获得 CPU 时间。这种算法可以根据进程的重要性或紧急程度来分配 CPU 资源，具有一定的灵活性。但是，它也可能导致低优先级进程饥饿。如果不断有高优先级进程到来，低优先级进程可能长时间得不到执行。静态优先级调度在进程创建时分配优先级，并在整个执行过程中保持不变；动态优先级调度则根据进程的行为和状态动态调整优先级。例如，在一些实时系统中，紧急任务被赋予高优先级，以确保它们能够及时得到处理。但是，如果高优先级任务过多，低优先级任务可能会被长时间忽略。
⑷轮转调度（RR）
轮转调度算法将 CPU 时间分成固定大小的时间片，所有进程轮流获得一个时间片的 CPU 使用权。这种算法具有较好的公平性，每个进程都能在一定时间内获得 CPU 时间。然而，时间片的大小对系统性能有很大影响。如果时间片太小，会导致进程切换频繁，增加系统开销；如果时间片太大，轮转调度算法就会退化为先来先服务算法。此外，轮转调度算法不利于处理紧急作业，因为每个进程都需要等待轮到自己才能获得 CPU 时间。例如，假设有一个紧急任务需要立即执行，但按照轮转调度算法，它可能需要等待很长时间才能获得 CPU 时间。
⑸多级反馈队列调度
多级反馈队列调度算法结合了多种调度策略，根据进程的特性将其分配到不同的队列中，每个队列采用不同的调度算法。这种算法具有较高的灵活性，可以适应不同类型的进程。例如，高优先级的短作业可以分配到高优先级队列中，采用短作业优先调度算法；长作业可以分配到低优先级队列中，采用先来先服务调度算法。然而，这种算法相对复杂，需要维护多个队列，增加了系统的开销和管理难度。
⑹高响应比优先调度算法
高响应比优先调度算法权衡了短作业和长作业，兼顾了等待时间和执行时间。响应比是等待时间与执行时间的比值，响应比高的进程优先获得 CPU 时间。这种算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。但是，计算响应比会增加系统开销，因为每次调度都需要计算每个进程的响应比。例如，在一个有多个进程等待调度的系统中，计算响应比需要消耗一定的时间和计算资源。
四、进程调度的实现与优化
4.1调度算法的选择
不同的场景和需求对进程调度算法有着不同的要求。在批处理系统中，主要追求高吞吐量和系统资源的充分利用。例如，短作业优先算法可以在一定程度上提高批处理系统的效率，因为它优先处理执行时间短的作业，从而在单位时间内可以完成更多的作业。据统计，在一些大型数据处理中心采用短作业优先算法，系统吞吐量可以提高 15% 至 20%。
对于交互式系统，响应时间是关键指标。此时，轮转调度算法可能更为合适，因为它可以确保每个进程都能在较短的时间内获得 CPU 时间，从而提高系统的响应速度。例如，在图形用户界面环境下，用户期望每个操作都能得到及时的反馈，轮转调度算法可以保证各个进程轮流执行，使得用户操作不会被长时间阻塞。
而在实时系统中，满足截止时间是最重要的目标。实时系统通常采用抢占式调度算法，如实时优先级调度，确保紧急任务能够在规定的时间内得到处理。例如，在飞机飞行控制系统中，对响应时间的要求极为严格，任何延迟都可能导致严重后果，实时优先级调度算法可以确保关键任务优先执行。
4.2调度器的设计与实现
调度器的设计通常采用模块化的方式，以便于适应不同的系统需求和优化目标。以 Linux 的 CFS（完全公平调度器）为例，它通过为每个进程安排一个虚拟运行时钟 vruntime，实现了公平性。当一个进程得以执行时，vruntime 的值不断增大，而没有运行的进程的 vruntime 保持不变。调度器总是选择 vruntime 最小的进程执行，从而确保每个进程都能获得相对公平的 CPU 时间。
CFS 的设计思路简单而有效，它根据每个进程的权重分配运行时间。例如，假设有两个进程 A 和 B，权重分别为 1 和 2，调度周期为 30ms。那么进程 A 的运行时间是 30*(1)/(1+2)=10ms，进程 B 的运行时间是 30*(2)/(1+2)=20ms。同时，CFS 通过调整 vruntime 的增长速度来体现不同进程的优先级，优先级高的进程 vruntime 增长得较慢，从而获得更多的运行机会。
为了降低调度延迟带来的不公平性，CFS 采用了红黑树数据结构来管理就绪队列。红黑树可以快速地找到 vruntime 最小的进程，从而减少调度时间。此外，CFS 还支持按组来分配时间片，通过 cgroup 机制，可以将 CPU 资源划分为不同的组，以便更好地满足不同应用场景的需求。
4.3进程状态的转换机制
进程在其生命周期内会经历多种状态的转换，这些转换受到资源分配的影响。例如，当一个进程从创建态转变为就绪态时，它需要获得除 CPU 以外的所有必要资源。一旦这些资源分配完成，进程就处于就绪状态，等待 CPU 的分配。
当进程获得 CPU 资源并开始执行时，它处于运行态。然而，在运行过程中，进程可能会因为等待某个事件（如等待 I/O 操作完成、等待资源分配等）而进入等待态。在等待态下，进程会被暂时挂起，以释放 CPU 资源供其他进程使用。当等待的事件发生时，进程会被唤醒并重新进入就绪态。
此外，进程还可能因为时间片用完或被更高优先级的进程抢占 CPU 而从运行态回到就绪态。而当一个进程完成其任务或出现无法克服的错误时，它会进入终止态，等待操作系统进行善后处理。
学习编程就得循环渐进，扎实基础，勿在浮沙筑高台