【Linux系统】进程切换 | 进程调度——O(1)调度队列
1. 进程切换
1.1 什么是进程切换？
进程切换（Process Switch）是操作系统中的一种机制，用于在多个进程之间分配CPU的执行时间。在多任务操作系统中，多个进程可以同时运行，但实际上CPU在同一时刻只能执行一个进程的代码。为了实现这种“同时”运行的假象，操作系统需要在进程之间快速切换。这个切换过程就称为进程切换。
1.2 故事引入
假设在一个繁忙的办公室里，有一位多才多艺的员工（CPU），他需要同时处理多个任务，比如写报告（进程A）、回邮件（进程B）和打电话（进程C）。这位员工的工作方式如下：
写报告（进程A）：他开始写报告，专注地工作了一段时间。
被打断（时间片耗尽）：突然，他的时间片用完了，或者他的秘书提醒他该处理邮件了。
保存进度（保存上下文）：他放下手中的笔，把写到一半的报告放在一旁，记住自己写到哪里了。
切换任务（进程切换）：他转向邮件，开始回邮件。
恢复进度（恢复上下文）：他打开邮件窗口，继续从上次停下的地方开始回邮件。
重复（多任务处理）：他不断在写报告、回邮件和打电话之间切换，每次都被秘书提醒时间片用完或者有更高优先级的任务。
在这个故事中，员工就是CPU，写报告、回邮件和打电话是不同的进程。每次员工在任务之间切换时，他都需要保存当前任务的进度，然后恢复下一个任务的进度。这个保存和恢复的过程就是上下文切换。
1.3 进程切换的具体步骤——上下文切换
上下文切换（Context Switch）是进程切换的核心部分，具体包括以下几个关键步骤：
保存当前进程的上下文：
寄存器保存：将当前进程的寄存器内容（如通用寄存器、程序计数器PC、指令寄存器IR、累加器ACC等）保存到该进程的进程控制块（PCB）中。
状态信息保存：保存当前进程的状态信息，如中断标志位、条件码寄存器等。
内存管理信息保存：如果进程有自己的地址空间，还需要保存内存映射、页表等信息。
更新调度程序的数据结构：
将当前进程从运行队列中移出，并根据调度算法（如时间片轮转、优先级调度等）选择下一个要运行的进程。
恢复下一个进程的上下文：
寄存器恢复：将下一个进程的寄存器内容从其PCB中恢复到CPU的寄存器中。
状态信息恢复：恢复下一个进程的状态信息。
内存管理信息恢复：如果需要，恢复下一个进程的内存映射和页表信息。
开始执行下一个进程：
CPU根据恢复的上下文继续执行下一个进程的代码。
1.4 示例故事的详细步骤
回到之前的办公室故事，我们详细描述上下文切换的过程：
写报告（进程A）：员工正在专注地写报告，CPU寄存器中保存着当前写到的位置（程序计数器PC）和一些中间计算结果（累加器ACC）。
时间片耗尽：当时间片用完时，操作系统的调度程序（秘书）提醒员工需要切换任务。
保存上下文：
员工将当前写报告的进度（寄存器内容）记录在自己的笔记本（PCB）中。
他还将当前的写作状态（如是否需要进一步查阅资料）记录下来。
更新调度数据结构：
秘书（调度程序）将当前任务（写报告）从“进行中”列表中移出。
根据优先级和任务队列，秘书选择下一个任务——回邮件（进程B）。
恢复上下文：
员工从回邮件任务的笔记本（PCB）中恢复之前保存的进度，包括邮件的回复位置和相关的参考信息。
开始执行新任务：
员工开始回复邮件，CPU寄存器中的内容被更新为邮件任务的状态信息。
通过这个办公室故事，我们形象化地理解了进程切换和上下文切换的过程。进程切换是操作系统为了实现多任务处理而进行的任务切换，而上下文切换是其中保存和恢复任务状态的核心步骤。这种机制让多个进程能够共享CPU资源，实现“同时”运行的假象。
1.5 参考一下Linux内核0.11代码
task_struct 结构体
struct task_struct {/* 这些是硬编码的 - 不要修改 */long state; /* -1 不可运行, 0 可运行, >0 停止 */long counter; /* 进程的时间片计数器 */long priority; /* 进程的优先级 */long signal; /* 信号信息 */struct sigaction sigaction[32]; /* 信号处理动作数组 */long blocked; /* 被屏蔽的信号位图 *//* 各种字段 */int exit_code; /* 进程退出码 */unsigned long start_code, end_code, end_data, brk, start_stack; /* 进程地址空间信息 */long pid; /* 进程ID */long father, pgrp, session, leader; /* 父进程ID、进程组ID、会话ID、会话领导者ID */unsigned short uid, euid, suid; /* 用户ID、有效用户ID、保存的用户ID */unsigned short gid, egid, sgid; /* 组ID、有效组ID、保存的组ID */long alarm; /* 报警时间 */long utime, stime, cutime, cstime, start_time; /* 用户态时间、内核态时间、子进程用户态时间、子进程内核态时间、进程启动时间 */unsigned short used_math; /* 是否使用了数学协处理器 *//* 文件系统信息 */int tty; /* -1 表示没有终端，因此必须是带符号的 */unsigned short umask; /* 文件创建掩码 */struct m_inode *pwd; /* 当前工作目录的inode指针 */struct m_inode *root; /* 根目录的inode指针 */struct m_inode *executable; /* 可执行文件的inode指针 */unsigned long close_on_exec; /* 执行时关闭的文件描述符位图 */struct file *filp[NR_OPEN]; /* 文件描述符数组 *//* 该任务的局部描述符表 */struct desc_struct ldt[3]; /* 0 - 零描述符, 1 - 代码段描述符, 2 - 数据段描述符 *//* 该任务的任务状态段 */struct tss_struct tss; /* 任务状态段结构体，保存进程的上下文数据 */
};tss_struct 结构体
tss_struct 是任务状态段的数据结构，用于保存进程的上下文信息，以便在进程切换时恢复。
// 任务状态段数据结构（参见列表后的信息）。
struct tss_struct {long back_link; /* 返回链接，16位高字节为0 */long esp0; /* 特权级别0的栈指针 */long ss0; /* 特权级别0的段选择器，16位高字节为0 */long esp1; /* 特权级别1的栈指针 */long ss1; /* 特权级别1的段选择器，16位高字节为0 */long esp2; /* 特权级别2的栈指针 */long ss2; /* 特权级别2的段选择器，16位高字节为0 */long cr3; /* 页目录基址寄存器 */long eip; /* 指令指针 */long eflags; /* 标志寄存器 */long eax, ecx, edx, ebx; /* 通用寄存器 */long esp; /* 栈指针 */long ebp; /* 基址指针 */long esi; /* 源索引寄存器 */long edi; /* 目的索引寄存器 */long es; /* 附加段寄存器，16位高字节为0 */long cs; /* 代码段寄存器，16位高字节为0 */long ss; /* 栈段寄存器，16位高字节为0 */long ds; /* 数据段寄存器，16位高字节为0 */long fs; /* 文件段寄存器，16位高字节为0 */long gs; /* 通用段寄存器，16位高字节为0 */long ldt; /* 局部描述符表，16位高字节为0 */long trace_bitmap; /* 跟踪位图，位0表示
};task_struct中的tss字段指向tss_struct结构体。tss_struct中保存了进程的上下文信息，包括寄存器状态和栈指针等，以便在进程切换时恢复。
1.6 关于时间片拓展
时间片的作用与意义
在分时操作系统中，时间片（Time Slice）是一种核心机制，用于在多个进程或线程之间分配 CPU 的执行时间，确保每个进程都能获得一定时间的 CPU 资源。时间片的引入使得多个任务能够在系统中“同时”运行，从而提高了系统的响应性和资源利用率。
时间片的具体定义与功能
时间片的定义非常简单：它是一个固定的时间间隔，通常以毫秒为单位。在分时操作系统中，系统会为每个进程分配一个时间片，允许该进程在这个时间段内独占 CPU 进行运行。 当时间片用完（即分配给该进程的时间到了），操作系统会触发一个时钟中断，强制当前进程暂停运行，然后将其状态保存到进程控制块（PCB）中，同时调度下一个进程运行。这个过程就是进程切换。
分时操作系统的定义与特点
分时操作系统（Time-Sharing Operating System，TSOS）是一种允许多个用户通过终端设备同时访问计算机资源的操作系统。它的目标是提高系统的响应性，让每个用户都能快速地得到服务。分时操作系统的几个主要特点如下：
多用户访问：允许多个用户同时使用计算机资源。
交互性：用户可以通过终端设备直接与系统进行交互，快速得到响应。
资源分配：通过时间片的机制，公平地分配 CPU 和其他资源，确保每个用户都能获得服务。
任务调度：使用多任务处理的方式，同时运行多个程序。
实时操作系统与分时操作系统对比
实时操作系统（Real-Time Operating System，RTOS）与分时操作系统在时间片的使用和系统设计上有所不同。实时操作系统的目标是保证任务在严格的时间限制内完成，通常用于嵌入式系统和控制系统等需要快速响应的场景。实时操作系统的任务调度通常是基于优先级的，而不是时间片轮转。在实时操作系统中，任务的执行时间往往受到严格限制，以确保关键任务能够及时完成。
时间片的大小与影响
时间片的大小对系统性能有重要影响：
时间片过小：会导致进程切换过于频繁，增加系统开销。频繁的上下文切换会消耗大量的 CPU 时间，从而降低整体系统性能。
时间片过大：可能导致系统响应性下降，因为一个进程会占用 CPU 较长时间，其他进程需要等待更久才能得到执行机会。
因此，合理设置时间片的大小是操作系统设计中的一个重要考虑因素。通常，时间片的大小会根据系统的用途和需求进行调整。
时间片耗尽的后果
当一个进程的时间片用完时，操作系统会触发时钟中断，强制该进程暂停运行。此时，系统会保存该进程的上下文（包括寄存器内容、程序计数器等），然后调度下一个进程运行。这个过程会导致进程切换和上下文切换，从而带来一定的系统开销。
实时操作系统中的时间片
在实时操作系统中，时间片的使用不如分时操作系统中普遍。实时操作系统更关注任务的优先级和截止时间，确保关键任务能够在规定时间内完成。然而，某些实时操作系统也会采用时间片机制来处理低优先级任务。
总结
时间片是分时操作系统中用于实现多任务处理和资源公平分配的关键机制。它通过为每个进程分配固定的时间间隔，确保多个进程能够交替使用 CPU，从而提高了系统的响应性和资源利用率。理解时间片的作用和影响，有助于深入理解操作系统的调度机制和性能优化策略。
2. Linux2.6内核进程O(1)调度队列
进程切换现在知道了，但是是如何进行调度的呢？
上图展示了Linux 2.6内核中进程队列的数据结构，下图用图示清晰地呈现了各组件间的关联关系，以便于理解。
在多任务操作系统中，进程调度是决定哪个进程在何时使用 CPU 的核心机制。其目标是最大化 CPU 利用率、确保公平性，并减少任务响应时间。
2.1 runqueue
单 CPU 的 Runqueue：
在单 CPU 系统中，有一个名为
runqueue的就绪队列，用于存放所有可运行状态的进程。操作系统调度器从
runqueue中选择进程并让其在 CPU 上运行。若无进程在运行且该队列非空，调度器会选择优先级最高的进程投入运行。
多 CPU 的负载均衡：
在多 CPU 系统中，每个 CPU 都有对应的
runqueue，这可能引发负载不均衡问题。若某一 CPU 的runqueue过长，而其他 CPU 的队列为空，就会导致系统性能瓶颈和资源浪费。负载均衡机制在此时发挥关键作用。它通过监视各
runqueue的长度，并将进程从繁忙队列迁移至空闲队列，从而实现整体性能的提升。
2.2 优先级
在Linux 2.6内核中，进程的优先级分为普通优先级和实时优先级两种。
进程优先级：
普通进程的优先级范围在 100 至 139 之间。在 Linux 系统中，与
nice值相关联，nice值越小，进程优先级越高。用户可使用nice和renice命令来查看和调整进程优先级。实时进程的优先级在 0 至 99 之间，享有比普通进程更高的优先级，确保关键任务迅速执行。实时进程调度策略如 SCHED_FIFO 和 SCHED_RR 等，为实时应用提供了低延迟保障。
拓展：
普通进程的优先级范围 [100, 139] 是如何映射到内核优先级范围 PRI[60, 99]呢？
优先级范围说明：
普通优先级范围：在用户视角中，普通进程的优先级通常用一个范围表示，例如 [100, 139]。这是用户或系统调用中使用的优先级表示方式。
内核优先级范围 PRI[60, 99]：在操作系统内核层面，优先级可能使用不同的数值范围来表示，例如 PRI[60, 99]。内核需要将用户指定的优先级映射到它自己的表示方式。
映射过程：
偏移量的计算：
用户指定的普通优先级范围是 [100, 139]。
内核的优先级范围是 PRI[60, 99]。
将用户优先级范围映射到内核优先级范围，需要一个线性转换：
内核优先级=(用户优先级−100)+60这里的偏移量是 60，从用户的 100 开始计算。
具体计算示例：
用户优先级 100：
内核优先级=(100−100)+60=60用户优先级 110：
内核优先级=(110−100)+60=70用户优先级 139：
内核优先级=(139−100)+60=99
总结：
通过简单的线性变换，用户指定的普通优先级范围 [100, 139] 可以映射到内核的优先级范围 PRI[60, 99]。这种方式确保内核能够按照统一的优先级数值范围来调度进程。
2.3 活动队列
活动队列的结构：
活动队列包含时间片未耗尽的进程，这些进程按优先级排列。其结构中：
nr_active：表示处于运行状态的进程总数，为调度器提供就绪进程数量的快速参考。queue[140]：数组的每个元素代表一个优先级的进程队列。索引从 0 至 139，对应实时和普通进程的优先级，相同优先级的进程遵循 FIFO 原则排队。
调度时，系统从
queue[140]的索引 0 开始查找非空队列。找到的第一个非空队列对应最高优先级的进程队列，队列中的第一个进程被选中运行。但遍历整个数组的效率较低。
位图优化：
bitmap[5]通过 5 个 32 位整数来标记queue[140]中哪些队列非空。每个位对应一个优先级，非空队列对应的位置为 1。查找时，系统利用位运算快速定位第一个非空队列，显著提升调度效率。
2.4 过期队列
过期队列的作用：
过期队列与活动队列结构相同，用于存放时间片已耗尽的进程。当活动队列的进程全部处理完毕后，系统会对过期队列中的进程重新计算时间片，使其有机会重新进入活动队列。
2.5 active指针和expired指针
active 指针与 expired 指针：
active指针指向活动队列，expired指针指向过期队列。随着进程时间片到期，过期队列中的进程增多，系统在适当时刻交换这两个指针的指向。这种交换机制使过期队列的进程重新成为活动队列的一部分，从而获得新的时间片并被调度运行。
2.6 总结
O(1) 调度算法：
在这种调度机制下，查找最优进程的时间复杂度为 O(1)。无论系统中有多少进程，调度器总能以固定时间成本找到合适的进程进行调度。这一特性对于提升系统性能、降低调度延迟至关重要。
部分内核源码如下：
struct rq {spinlock_t lock;/** nr_running and cpu_load should be in the same cacheline because* remote CPUs use both these fields when doing load calculation.*/unsigned long nr_running;unsigned long raw_weighted_load;
#ifdef CONFIG_SMPunsigned long cpu_load[3];
#endifunsigned long long nr_switches;/** This is part of a global counter where only the total sum* over all CPUs matters. A task can increase this counter on* one CPU and if it got migrated afterwards it may decrease* it on another CPU. Always updated under the runqueue lock:*/unsigned long nr_uninterruptible;unsigned long expired_timestamp;unsigned long long timestamp_last_tick;struct task_struct *curr, *idle;struct mm_struct *prev_mm;struct prio_array *active, *expired, arrays[2];int best_expired_prio;atomic_t nr_iowait;
#ifdef CONFIG_SMPstruct sched_domain *sd;/* For active balancing */int active_balance;int push_cpu;struct task_struct *migration_thread;struct list_head migration_queue;
#endif#ifdef CONFIG_SCHEDSTATS/* latency stats */struct sched_info rq_sched_info;/* sys_sched_yield() stats */unsigned long yld_exp_empty;unsigned long yld_act_empty;unsigned long yld_both_empty;unsigned long yld_cnt;/* schedule() stats */unsigned long sched_switch;unsigned long sched_cnt;unsigned long sched_goidle;/* try_to_wake_up() stats */unsigned long ttwu_cnt;unsigned long ttwu_local;
#endifstruct lock_class_key rq_lock_key;
};/** These are the runqueue data structures:*/
struct prio_array {unsigned int nr_active;DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */struct list_head queue[MAX_PRIO];
};