北海市网站建设_网站建设公司_JavaScript_seo优化

1.调度的概念

1.1 调度的基本概念

1. 什么是调度？

在多道程序环境中，内存中通常有多个进程等待执行，但 CPU 的核心数量是有限的。调度就是操作系统按照一定的策略，从就绪队列中选择一个进程，把 CPU 的使用权分配给它的过程。

• 根本目的： 提高 CPU 利用率，让系统更高效、公平地运行。

1.2.调度的三个层次


操作系统中的三级调度分别是：高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）。

以下是详细的层级拆解：

1. 高级调度 (High-Level / Job Scheduling)

• 别名： 作业调度、长程调度 (Long-term Scheduler)。
• 生活类比： “医院大门口的安检和分流”。
  • 医院里的人（内存中的进程）已经很挤了，保安（高级调度）决定外面排队的人（磁盘上的作业）谁能进大厅，谁得在外面等着。
• 任务： 决定哪些作业 (Job) 从外存（磁盘）调入内存，并为它们创建进程、分配必要的资源（如内存、IO设备）。
• 频率： 最低（可能几分钟一次）。
• 关键作用： 控制多道程序的度 (Degree of Multiprogramming)。即决定系统里同时有多少个进程在跑。进得太多，系统会卡死（颠簸）；进得太少，CPU 没事干。

2. 中级调度 (Medium-Level / Memory Scheduling)

• 别名： 交换调度、中程调度 (Medium-term Scheduler)。
• 生活类比： “在大厅等待区的调整”。
  • 如果大厅（内存）里人太多挤不动了，或者有病人正在等化验结果（阻塞），保安就把暂时不看病的人请到外面的休息区（挂起状态/外存交换区），腾出空间给急需看病的人。等休息区的人条件具备了，再叫回来。
• 任务： 负责进程在内存和外存之间的交换 (Swapping)。
  • 挂起 (Swap Out)： 将暂时不能运行的进程调至外存，腾出内存空间。
  • 激活 (Swap In)： 当具备运行条件且内存有空闲时，再调回内存。
• 频率： 中等。
• 关键作用： 提高内存利用率和系统吞吐量。

3. 低级调度 (Low-Level / CPU Scheduling)

• 别名： 进程调度、短程调度 (Short-term Scheduler)。
• 生活类比： “叫号进诊室”。
  • 这是最频繁的动作。医生（CPU）看完一个病人，护士（低级调度）立马从候诊椅（就绪队列）上叫下一个病人进去。
• 任务： 从就绪队列中挑选一个进程，将 CPU 分配给它。
• 频率： 最高（毫秒级，一秒钟可能发生几十上百次）。
• 关键作用： 决定谁真正占有 CPU 干活。这是操作系统中最核心的调度，也是必不可少的调度（前两种在简单的系统中可能没有）。

---

三级调度对比总结表

调度类型	别名	调度对象	发生频率	核心任务
高级调度	作业调度	作业 (磁盘->内存)	低 (分钟级)	“准入”：决定谁能进内存，控制多道程序数量。
中级调度	交换调度	进程 (内存<->外存)	中	“交换”：内存不够时“腾笼换鸟”，优化内存利用。
低级调度	进程调度	进程 (就绪->CPU)	高 (毫秒级)	“执行”：决定谁现在能用 CPU。

它们是如何协作的？

想象一个进程的一生：

1. 出生： 高级调度把它从磁盘拉进内存，变成了“进程”。
2. 排队： 它进入就绪队列，等待低级调度选中它去用 CPU。
3. 波折： 运行过程中，内存不够了，或者它在等很慢的 I/O，中级调度可能会把它踢出内存（挂起），过一会再接回来。
4. 工作： 它在低级调度的指挥下，断断续续地使用 CPU。
5. 结束： 任务完成，退出系统。

1.3三级调度的联系

1. 核心联系：全生命周期的接力

一个作业从进入系统到完成，实际上就是在这三级调度之间“接力”：

• 第一棒（高级调度）： 负责“进门”。它决定谁有资格从磁盘进入内存，拿到“准考证”（创建进程，建立 PCB）。它为低级调度提供了候选池。
• 第二棒（低级调度）这是操作系统中最核心的调度，也是必不可少的调度（前两种在简单的系统中可能没有）： 负责“干活”。它从高级调度送来的（或中级调度换回来的）就绪队列中，挑选进程上 CPU 运行。
• 救火队（中级调度）： 负责“调节”。当高级调度放进来的人太多，导致内存不足或 CPU 忙不过来时，中级调度就把部分进程暂时踢回磁盘（挂起），等系统缓过气来再接回来。

2. 具体协作关系图解

我们可以通过“多道程序的度” (Degree of Multiprogramming) 这个指标来看它们的配合：

1. 高级调度决定了度的上限。它控制最初有多少个进程能进入内存。
2. 中级调度动态降低度的数值。当内存紧张时，它减少内存中的进程数，防止系统“死机”或颠簸。
3. 低级调度在既定的度下，尽可能提高利用率。它负责在这些有限的进程间快速切换，保证 CPU 不闲着。

3. 状态转换视角 (The Connection in State Transitions)

三级调度的联系主要体现在进程状态的流转上：

• 新建态 $\rightarrow$ 就绪态：高级调度说了算。
• 就绪态 $\rightarrow$ 运行态：低级调度说了算。
• 就绪/阻塞态 $\leftrightarrow$ 挂起态：中级调度说了算（挂起与激活）。

4. 总结：如果配合不好会怎样？

• 如果高级调度太激进： 内存塞满，导致中级调度疯狂“交换”进程，磁盘读写频繁，CPU 反而空闲（系统颠簸）。
• 如果低级调度太慢： 即使内存里有进程，CPU 也经常闲置，用户觉得电脑反应极慢。
• 如果中级调度缺席： 内存一旦用完，新进程进不来，老进程卡住，系统弹性极差。

2.调度的实现

2.1调度程序(调度器)

它的核心职责只有一句话：在众多的任务中，决定把“老板”（CPU）的时间分给谁。

以下从 定义、工作机制、核心组成、真实案例 四个方面为你拆解：

1. 什么是调度程序？

它是一段操作系统的代码，负责管理 CPU 资源。它维护着一个“任务清单”（就绪队列），并根据特定的算法（策略），不断地从清单中选择一个进程/线程，让它在 CPU 上运行。

• 输入： 一堆等待运行的进程（就绪队列）。
• 输出： 下一个获得 CPU 使用权的进程。

2. 调度程序是怎么工作的？ (When & How)

调度程序不是一直在运行的，它需要被“触发”。通常在以下几种情况，调度程序会醒来干活：

1. 当前进程“由于自身原因”不干了：
   • 进程运行结束（Exit）。
   • 进程需要等 I/O（读取磁盘、等键盘输入），主动放弃 CPU（Block）。
2. 当前进程“被迫”停止（抢占）：
   • 时间片用完了： 闹钟响了（时钟中断），该轮到下一个人了。
   • 有更重要的人来了： 一个高优先级的进程突然就绪（比如你移动了鼠标，中断处理程序唤醒了相关进程）。

3. 核心双子星：调度器 vs 分派器

在很多教材中，会把“决定谁来跑”和“让它跑起来”区分开，这涉及两个概念：

• 调度器 (Scheduler)： “决策者”。
  • 它只负责选。它看着一堆进程，计算优先级、权衡公平性，最后手指一指：“下一个就是你！”
• 分派器 (Dispatcher)： “执行者”。
  • 它负责搬。它负责具体的上下文切换 (Context Switch)。
  • 动作： 保存当前进程的现场（寄存器、PC指针） -> 加载被选中进程的现场 -> 跳转到新进程的代码地址开始执行。

4. 现实中的调度程序长什么样？

理论上我们学 FCFS、轮转调度，但在真实的操作系统（如 Linux 和 Windows）中，调度程序要复杂得多，且通常是混合型的。

A. Linux 的调度器 (CFS - Completely Fair Scheduler)

• 设计哲学： 公平。它不单纯看优先级，而是看谁“占便宜”少了。
• 数据结构： 红黑树 (Red-Black Tree)。
  • 不是简单的队列。它把所有等待的进程挂在一棵树上。
  • 树的左边是“CPU 用得最少”的进程（vruntime 最小），树的右边是“用得很多”的进程。
• 策略： 调度器每次闭着眼去抓树最左边的那个节点，让它运行。运行一会后，它的 vruntime 变大了，就把它插回到树的右边去，给别人机会。

B. Windows 的调度器

• 设计哲学： 响应优先（为了让界面不卡顿）。
• 数据结构： 多级反馈队列 (32个优先级)。
  • Windows 简单粗暴地把进程分成 32 个等级（0-31）。
  • 系统总是先扫描最高优先级的队列，如果有进程就运行；如果空了，才看下一级。
• 策略： 抢占式 + 时间片轮转。为了防止前台窗口卡顿，Windows 会给当前聚焦的窗口（前台进程）“开小灶”，临时提升它的优先级或给更长的时间片。

总结

概念	比喻	关键点
调度程序	拥有排班权力的行政秘书	决定 Who (谁下一个运行)
分派器	负责换座位的后勤人员	负责 Switch (上下文切换)
触发时机	闹钟响了或有人请假	时钟中断、I/O 阻塞、进程结束
Linux (CFS)	天平	用红黑树保证大家用的时间尽量公平
Windows	VIP通道	用多级队列保证重要的任务（界面）响应快

5. 调度程序的三个核心组件

(1) 排队器 (Enqueuer)

• 职责： 它是调度程序的“预处理”部分。
• 工作： 当一个进程变为就绪态 (Ready) 时（例如刚创建完成，或者时间片用完，或者 I/O 结束），排队器负责把它放到这就绪队列的正确位置。
• 关键点： “按照一定的策略”。
  • 如果是先来先服务 (FCFS)，就插到队尾。
  • 如果是优先级调度，就插到优先级对应的位置。
  • 如果是多级反馈队列，就插到对应的那个队列里。

(2) 分派器 (Dispatcher)

• 职责： 它是调度程序的“执行”部分（取出者）。
• 工作： 依据调度算法选定了一个进程后，分派器负责把这个进程从就绪队列里取出来，并准备把 CPU 给它。
• 注意： 在这张图的定义里，它主要负责逻辑上的“取出”和“分配权利”。

(3) 上下文切换器 (Context Switcher)

• 职责： 它是最底层的“搬运工”，负责硬件级别的状态切换。
• 工作： 这是一个非常消耗资源的过程。文中提出了一个很多同学容易忽略的细节——两对上下文切换。

6. 重点难点：为什么是“两对”上下文切换？

• 第一对切换（当前进程 $\to$ 分派器）：
  1. 保存： 将当前进程的上下文（寄存器、PC指针等）保存到它的 PCB 中。
  2. 装入： 装入分派器程序的上下文，以便分派器代码能够运行（去做“选择下一个进程”这个逻辑判断）。
• 第二对切换（分派器 $\to$ 新进程）：
  1. 移出： 分派器工作做完了，移出分派器的上下文。
  2. 装入： 将新选出的进程的 CPU 现场信息装入寄存器，开始运行新进程。

思考： 在现代操作系统（如 Linux）中，调度器通常是内核代码的一部分，并不一定需要完整的“加载分派器上下文”这一步（因为已经在内核态了），但考研理论模型中，通常强调这个“进程 A -> 调度程序 -> 进程 B”的完整过程。

7. 硬件优化：如何减少开销？

• 问题： 上下文切换需要执行大量的 load (读取) 和 store (存储) 指令，把寄存器里的数据搬进搬出内存，非常慢。
• 解决方案（硬件支持）： 采用两组（或多组）寄存器。
  • 一组给内核使用。
  • 一组给用户使用。
• 效果： 切换时，不需要真的把数据搬来搬去，只需要改变指针，让 CPU 指向另一组寄存器即可。这能极大地提升切换速度（从“搬家”变成了“换房间”）。

2.2 调度的时机、切换和过程

调度程序是内核程序

1. 调度的时机 (When to Schedule?)

操作系统并不是随时随地都能进行进程调度的。调度通常发生在“CPU 此时无事可做”或者“当前进程不得不让出 CPU”的时候。

我们可以把时机分为两类：

A. 主动放弃 (Voluntary / Non-preemptive)

当前进程因为自身的行为，无法继续运行，必须让出 CPU：

1. 进程终止 (Termination)： 进程执行结束 (exit)，CPU 空闲了。
2. 发生阻塞 (Blocking)： 进程请求 I/O（读磁盘、发网络包）、等待锁 (mutex) 或信号量。此时进程进入阻塞态，必须调度其他进程。

B. 被动抢占 (Involuntary / Preemptive)

当前进程还想跑，但操作系统强制把它踢下来：

1. 时间片用完 (Time Slice Expiration)： 最常见的情况。时钟中断发生，内核发现当前进程配额用光了。
2. 更高优先级的进程到达 (Wakeup)：
   • 例如：你正在通过键盘输入（中断发生），等待输入的文本编辑器进程被唤醒。它的优先级通常高于后台正在跑的编译任务，因此发生抢占。
3. 硬件中断： 某些硬件错误或异常导致必须切换。

⚠️ 考研/面试高频考点：什么时候不能调度？

• 在中断处理程序 (ISR) 执行过程中。（中断理应极快，不能被切走）
• 进程在操作系统内核临界区中（且持有自旋锁 Spinlock）时。（这会导致死锁或数据不一致）
• 注：在现代 Linux 中，普通的内核态代码是可以抢占的（Preemptible Kernel），但持有自旋锁时绝对不行。

---

2. 进程切换 vs. 模式切换 (The Distinction)

这是初学者最容易混淆的概念，也是理解性能开销的关键。

A. 模式切换 (Mode Switch)

• 定义： 用户态 $\leftrightarrow$ 内核态的切换。
• 场景： 系统调用、中断、异常。
• 开销： 小。只需要保存很少的寄存器（PC, PSW 等）到内核栈。
• 关键点： 进程没变。还是同一个进程，只是执行权限变了。

B. 进程切换 (Process Context Switch)

• 定义： 进程 A $\to$ 进程 B。
• 场景： 调度器决定运行另一个进程。
• 开销： 极大。
  • 需要保存/恢复所有通用寄存器。
  • 最痛的代价： 切换内存地址空间（修改 CR3 寄存器/页表基址）。这意味着 TLB（页表缓存）会被刷空，L1/L2 Cache 的命中率也会瞬间暴跌。
• 关键点： 只有进程切换才涉及调度。

---

3. 调度的具体过程 (The Procedure)

结合 Linux 内核逻辑，一个完整的进程调度过程可以拆解为以下四个微观阶段：

第一阶段：触发 (Triggering)

调度不是随时发生的，通常需要一个“契机”来打断当前进程。

• 中断/陷入 (Interrupt/Trap)：
  • 当发生时钟中断（时间片用完）或系统调用（如 IO 请求）时，CPU 会从用户态（User Mode）切换到内核态（Kernel Mode）。
• 延迟调度的检测 (Lazy Check)：
  • Linux 不会立即调度，而是设置一个标志位。
  • 关键点：当中断处理程序结束，准备返回用户态之前，内核会检查 current_thread_info()->flags 中的 TIF_NEED_RESCHED 标志位。
  • 如果为真，说明内核决定要换人了，此时调用核心调度函数 schedule()。

第二阶段：保存与选择 (Save & Pick)

这是“大脑”进行决策的阶段。

• 保存现场 (Save Context)：
  • 将当前进程 A 的 CPU 状态（包括 PC 指针、通用寄存器、浮点寄存器等）保存到它的 内核栈 或 task_struct (PCB) 中。
• 执行调度算法 (Pick Next)：
  • 内核调用调度类（Scheduling Class），例如 CFS (完全公平调度器)。
  • 逻辑：根据红黑树上的 vruntime (虚拟运行时间)，找到最左边的节点。
  • 结果：选定下一个要运行的进程 B。

第三阶段：切换 (The Heavy Lifting)

这是最消耗性能的“体力活”，通常由 context_switch() 函数完成。

• 1. 切换内存空间 (switch_mm)：
  • 动作：修改 CPU 的 CR3 寄存器（页表基址寄存器），将其指向进程 B 的页目录。
  • 性能代价 (高)：
    • 一旦 CR3 改变，CPU 的 TLB (快表) 会被刷新（Flush）。
    • 这意味着接下来的内存访问会有大量的 TLB Miss，导致 CPU 必须去查物理内存中的页表，速度瞬间变慢。(注：这是上下文切换开销大的主要原因)
• 2. 切换内核栈与硬件上下文 (switch_to)：
  • 动作：这是一个汇编宏。它将 CPU 的 SP (栈指针) 和 FP (帧指针) 从进程 A 的内核栈切换到进程 B 的内核栈。
  • 关键一跳：最后恢复进程 B 之前保存的 PC (程序计数器)。
  • 瞬间转移：当 PC 被加载的那一刻，CPU 就开始执行进程 B 的指令了（通常是它上次被中断的地方）。

第四阶段：恢复 (Restore)

此时，CPU 已经是在运行进程 B 的代码逻辑了。

• 恢复用户态 (Return to User)：
  • 进程 B 的内核栈中，保存着它上次被打断时的用户态寄存器上下文。
  • 指令：执行 IRET (x86) 或类似指令。
  • 效果：CPU 特权级从 Ring 0 变回 Ring 3，栈指针切回用户栈，程序继续在用户空间运行。

4.四大调度时机

一、 四大调度时机

1. 创建新进程后 (fork)

• 教材说法： 父子进程谁先运行？调度器决定。
• Linux 内核实战：
  • 当你调用 fork() 时，内核会通过 do_fork 创建子进程。
  • 关键问题： 谁先跑？在早期的 Unix 中，倾向于让子进程先跑，因为子进程往往紧接着调用 exec()（替换代码段），这样可以避免父进程先写内存导致 COW (Copy-On-Write) 发生不必要的页面复制。
  • 现代 Linux (CFS)： 完全公平调度器（CFS）会通过对比父子进程的 vruntime（虚拟运行时间）来决定。通常可以通过 /proc/sys/kernel/sched_child_runs_first 参数来控制这个偏好。

2. 进程结束 (exit)

• 教材说法： 进程结束了，必须选个新的，没得选就选“闲逛进程”。
• Linux 内核实战：
  • 闲逛进程 (Idle Task, PID 0)： 这不是一个普通的进程。当就绪队列为空时，CPU 会运行 cpu_idle_loop。
  • 硬件联动： Idle 进程通常会执行 HLT 指令（x86），让 CPU 进入休眠状态以省电，直到下一个中断（通常是时钟中断）把它“叫醒”。

3. 进程阻塞 (Blocking)

• 教材说法： 也就是主动放弃。比如 I/O 请求、信号量 (P操作 / wait)。
• C++ 编程启示：
  • 这是高性能服务器最忌讳的场景。
  • 反面教材： 传统的 cin >> x 或 read(fd, ...) 是阻塞的。一旦调用，你的线程就被踢出 CPU，发生了昂贵的上下文切换。
  • 正面教材： 现代 C++ 网络库（如你关注的 Reactor 模式、epoll）使用 非阻塞 I/O (O_NONBLOCK)。如果没有数据，函数立即返回错误（EAGAIN），线程不让出 CPU，而是去处理其他连接。这就避免了这里提到的“必须调度其他进程”，从而极大提升吞吐量。

4. I/O 中断发生 (Interrupt / Preemption)

• 教材说法： 比如磁盘读完了，发个中断。原来等待数据的进程醒了（变就绪）。此时是抢占的好时机。
• 场景还原：
  • 网卡收到一个数据包 $\to$ 触发中断 $\to$ 网卡驱动处理 $\to$ 唤醒正在 epoll_wait 的 Nginx 进程。
  • 决策： 调度器会立刻计算：这个刚醒来的 Nginx 进程，优先级是不是比当前正在跑的进程高？如果是，立刻抢占（Preempt）；如果不是，标记一下 need_resched，等当前进程时间片用完再说。

2.3进程调度的方式

一、 按照调度机制分类（两大模式）

这是最基础的分类，决定了操作系统是否可以强制剥夺一个正在运行的进程的 CPU 使用权。

1. 非抢占式调度 (Non-preemptive Scheduling)

• 机制： 一旦 CPU 分配给某进程，该进程就会一直运行，直到它自动释放 CPU（例如：进程终止、执行 I/O 操作阻塞、或主动调用 yield）。
• 特点： 实现简单，系统开销小（上下文切换少）。
• 缺点： 响应时间差。如果一个进程死循环，整个系统可能卡死。
• 适用场景： 批处理系统、简单的嵌入式系统。

2. 抢占式调度 (Preemptive Scheduling)

• 机制： 操作系统可以在进程未执行完时，强制剥夺其 CPU 使用权，暂停该进程并保存状态，将 CPU 分配给另一个进程。
• 触发条件： 时间片耗尽（时钟中断）、更高优先级的进程进入就绪队列。
• 特点： 响应快，公平性好，防止单一进程独占 CPU。
• 适用场景： 现代通用操作系统（Windows, Linux, macOS, Android）。

---

二、 经典的调度算法

操作系统根据不同的目标（吞吐量、响应时间、周转时间），采用了不同的算法。

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

• 原理： 像超市排队结账一样，谁先进入就绪队列，谁先执行。
• 类型： 非抢占式。
• 优点： 简单，易于理解和实现。
• 缺点： 存在护航效应 (Convoy Effect)。如果一个 CPU 密集型的大进程在前面，后面所有的小进程都要等待很久，导致平均等待时间很长。

2. 最短作业优先 (SJF - Shortest Job First)

• 原理： 选择预计运行时间（Burst Time）最短的进程先执行。
• 类型： 可以是非抢占式，也可以是抢占式（称为 SRTF, Shortest Remaining Time First）。
• 优点： 理论上能获得最短的平均等待时间。
• 缺点：
  • 难以准确预测进程的下一次 CPU 执行时间。
  • 饥饿现象 (Starvation)： 长作业可能永远抢不到 CPU。

3. 优先级调度 (Priority Scheduling)

• 原理： 每个进程有一个优先级，CPU 分配给优先级最高的进程。
• 类型： 抢占式或非抢占式。
• 缺点： 低优先级进程可能产生饥饿。
• 解决方案： 老化 (Aging) 技术——随着等待时间的增加，逐渐提高进程的优先级。

4. 时间片轮转 (RR - Round Robin)

• 原理： 专门为分时系统设计。将 CPU 时间划分为固定的时间片 (Time Quantum)（如 10ms - 100ms）。就绪队列中的进程轮流执行一个时间片。
• 类型： 抢占式。
• 关键点： 时间片的大小选择至关重要。
  • 太大：退化为 FCFS，响应变慢。
  • 太小：上下文切换（Context Switch）太频繁，浪费 CPU 资源。
• 优点： 响应时间短，公平（每个进程都能获得 1/n 的 CPU 时间）。

5. 多级反馈队列 (MLFQ - Multilevel Feedback Queue)

这是现代操作系统调度算法的雏形，最通用且复杂。

• 原理： 设置多个就绪队列，每个队列优先级不同，且时间片大小也不同。
• 规则：
  • 新进程进入最高优先级队列。
  • 如果进程在当前队列的时间片内没执行完，它会被降级到下一个优先级的队列（认为它是 CPU 密集型）。
  • 只有高优先级队列为空时，才调度低优先级队列。
• 优点： 兼顾了短作业（高响应）和长作业（高吞吐），且不需要预知进程运行时间。

2.4闲逛进程

在操作系统中，闲逛进程（Idle Process），通常也被称为 System Idle Process 或 PID 0，是系统中最特殊、最基础的进程之一。

简单来说，它是操作系统在“无事可做”时运行的进程。

以下是关于闲逛进程的核心概念、工作原理以及它存在的意义：

---

1. 核心定义

当操作系统的调度器（Scheduler）在就绪队列（Runqueue）中找不到任何其他处于“就绪”状态的进程时，CPU 就会切换到闲逛进程。

• 它的格言是：“兜底”。
• 它的优先级：是全系统最低的。任何其他进程只要准备好运行，都会立即抢占闲逛进程。

2. 为什么要有一个“闲逛进程”？

你可能会问，如果没任务做，CPU 直接停下来不就行了吗？

• 硬件特性：CPU（中央处理器）是一个必须不断执行指令的电子元件。只要电脑开着，程序计数器（PC）就必须指向某个地址，CPU 必须不断地取指、解码、执行。它不能处于“真空”状态。
• 占位符：因此，操作系统需要一个永远处于“就绪”状态的代码段，填补 CPU 的空闲时间。这就是闲逛进程。

3. 它具体在干什么？

在早期的操作系统或极其简单的嵌入式系统中，闲逛进程可能只是一个死循环：

C

while(1) {// 啥也不干，单纯烧电
}

但在现代操作系统（如 Linux、Windows）中，闲逛进程承担着极其重要的节能（Power Management）任务：

1. 执行 HLT 指令：闲逛进程的循环中通常包含特殊的 CPU 指令（如 x86 架构下的 hlt，或 ARM 下的 wfi - Wait For Interrupt）。
2. 进入睡眠：当 CPU 执行到 hlt 指令时，它会停止执行后续指令，切断流水线的部分时钟信号，进入低功耗状态（C-State）。
3. 等待唤醒：CPU 会一直保持这个状态，直到接收到硬件中断（比如时钟中断、键盘输入、网络包到达）。中断发生后，CPU 醒来，处理中断，调度器检查是否有新进程被唤醒。如果有，运行新进程；如果没有，继续运行闲逛进程并再次休眠。

4. 在 Linux 中的实现细节

在 Linux 内核中，闲逛进程有一些有趣的特性：

• PID 0：它通常被称为 Process 0 或 swapper。
• 不是通过 fork 创建的：它是内核启动时手动创建的第一个进程。所有其他进程（包括 init 进程，PID 1）最终都是由它衍生或间接衍生出来的。
• Per-CPU 变量：在多核（SMP）系统中，每个 CPU 核心都有一个属于自己的闲逛进程。因为每个核心如果没事做，都必须独立地去执行闲逛循环。
• 代码路径：在 Linux 内核源码中，核心逻辑通常位于 cpu_startup_entry 函数中，最终调用 do_idle。

5. 如何观察它？

• 在 Windows 上：打开任务管理器，你会看到一个名为“System Idle Process”的进程。如果它的 CPU 占用率是 99%，不要惊慌，这实际上是好消息，说明你的电脑很空闲，CPU 正在休息。
• 在 Linux 上：使用 top 或 htop 命令时，你通常看不到 PID 0，因为它是内核的一部分，不参与普通的用户态调度统计。但是 top 输出头部的 %id (idle) 字段就是 CPU 运行闲逛进程的时间比例。

总结

特性	描述
优先级	最低（永远被抢占）
功能	填补 CPU 空闲时间，执行节能指令
存在形式	每个 CPU 核心一个
状态	永远处于就绪态（Ready），除非 CPU 正在运行其他进程

2.5两种线程的调度

一、 用户级线程 (User-Level Threads, ULT)

核心概念： 线程的管理（创建、同步、销毁、调度）完全由用户空间的线程库（如早期的 Pthreads 库、Java 早期的 Green Threads、Go 语言的 Goroutines）负责。

• 对内核是透明的： 操作系统内核完全不知道这些线程的存在。内核只看到一个单线程的进程。
• 调度者： 应用程序内部的运行时系统（Runtime System）。

调度方式： 通常采用 “多对一”模型 (Many-to-One)。多个用户级线程映射到一个内核执行实体上。

• 优点：
  1. 切换极快： 线程切换只需要保存/恢复用户寄存器，不需要切入内核态（无 System Call 开销），效率极高。
  2. 调度策略灵活： 应用程序可以根据自己的需求实现特定的调度算法，不依赖 OS。
  3. 跨平台： 可以在不支持多线程的操作系统上运行。
• 缺点：
  1. 无法利用多核： 因为内核只把它看作一个进程，所以同一时刻只能在一个 CPU 核心上运行。
  2. 阻塞问题： 如果其中一个线程发起了阻塞的系统调用（如 read），内核会挂起整个进程，导致所有其他线程也被阻塞（因为内核不知道还有其他线程可以运行）。

---

二、 内核级线程 (Kernel-Level Threads, KLT)

核心概念： 线程的创建、调度和管理全部由操作系统内核直接负责。这是现代操作系统（Windows, Linux, macOS）的标准实现方式。

• 内核可见： 内核维护了每个线程的上下文信息（TCB - Thread Control Block）。
• 调度者： 操作系统内核调度器。

调度方式： 通常采用 “一对一”模型 (One-to-One)。每一个用户程序创建的线程，都直接对应一个内核线程。

• 优点：

  1. 真正的并发： 多线程可以被内核分配到不同的 CPU 核心上并行执行。
  2. 不阻塞： 如果一个线程执行系统调用阻塞了，内核可以立即调度该进程中的其他线程继续执行。

• 缺点：

  1. 开销大： 线程切换需要从用户态切换到内核态（Context Switch），开销比用户级线程大得多。
  2. 资源消耗： 每个线程都需要内核分配栈空间和 TCB，大量线程会给内核带来压力。

  特性	用户级线程 (ULT)	内核级线程 (KLT)
  管理者	用户态的库	操作系统内核
  内核感知	不可见	可见
  切换开销	极小 (数十纳秒)	较大 (数微秒)
  并行性	无法利用多核	可利用多核
  阻塞影响	一人阻塞，全家阻塞	一人阻塞，他人照跑
  常见例子	Go Goroutine, Python asyncio	Linux Pthreads (NPTL), Windows Threads

3.调度的目标

一、 五大核心衡量指标 (Quantitative Metrics)

这是我们在设计或评价一个调度算法好坏时的“数学标准”，也是研究生考试或面试中的重点。

1. CPU 利用率 (CPU Utilization)

• 目标： 让 CPU 尽可能忙碌，不要闲着。
• 理想状态： 在重负载下，CPU 利用率应接近 100%（实际系统中 40%-90% 都很常见）。
• 反例： 如果 I/O 操作频繁导致 CPU 经常空转，说明调度或系统架构有问题。

2. 吞吐量 (Throughput)

• 定义： 单位时间内完成的进程（或作业）数量。
• 目标： 最大化吞吐量。
• 适用： 对于服务器和批处理系统至关重要。

3. 周转时间 (Turnaround Time)

• 定义： 从进程提交（Create）到进程完成（Terminate）的总时间。

  $$T_{周转} = T_{完成时刻} - T_{到达时刻}$$

• 目标： 最小化周转时间。

• 意义： 用户最关心的指标之一——“我让电脑跑个程序，多久能跑完？”

4. 等待时间 (Waiting Time)

• 定义： 进程在就绪队列 (Ready Queue) 中等待 CPU 的总时间。
• 目标： 最小化等待时间。
• 重要性： 这是调度算法唯一能直接控制的指标。进程在 CPU 上跑多久取决于程序逻辑，做 I/O 多久取决于硬件，唯独“排队等多久”是调度器决定的。

5. 响应时间 (Response Time)

• 定义： 从用户提交请求到系统产生第一次响应（而非完成）的时间。
• 目标： 最小化响应时间。
• 适用： 交互式系统（如 Windows 桌面、游戏、终端输入）。如果不及时响应，用户会觉得“卡顿”。

---

二、 不同系统的调度目标侧重

没有一种算法能同时满足所有目标，因为它们往往是冲突的。操作系统根据用途权衡：

1. 批处理系统 (Batch Systems)

• 场景： 科学计算、大数据处理、编译大型 C++ 项目。
• 核心目标：
  • 最大化吞吐量 (单位时间处理更多任务)。
  • 最小化周转时间。
• 牺牲： 响应时间。用户不在电脑前盯着，所以延迟几秒没关系。

2. 交互式系统 (Interactive Systems)

• 场景： 个人电脑、手机、Web 服务器。
• 核心目标：
  • 最小化响应时间 (Response Time)。
• 牺牲： 吞吐量。为了快速响应鼠标点击，频繁切换上下文会消耗 CPU 资源，降低整体处理能力。

3. 实时系统 (Real-Time Systems)

• 场景： 汽车刹车控制、工业机器人、DPDK 网络包处理。
• 核心目标：
  • 满足截止时间 (Meeting Deadlines)：必须在规定时间内完成，否则后果严重。
  • 可预测性 (Predictability)：调度行为必须是确定的，不能忽快忽慢。

---

三、 经典的“权衡困境” (Trade-offs)

理解调度目标的关键在于理解冲突：

1. 响应时间 vs. 吞吐量
   • 想要响应快，就必须把时间片切得很小（频繁切换）。
   • 但是上下文切换（Context Switch）是有开销的。切换太频繁，CPU 都在忙着保存/恢复寄存器，干正事的时间就少了，导致吞吐量下降。
2. 公平性 vs. 优先级
   • 想要公平，就大家轮流坐庄（Round Robin）。
   • 但是重要的任务（如内核中断处理）需要特权。如果完全公平，紧急任务就会被拖慢。

总结图表

指标	目标	谁最在乎？
CPU 利用率	Max	资源管理者 (云服务商)
吞吐量	Max	批处理系统 (编译服务器)
周转时间	Min	批处理用户
响应时间	Min	交互式用户 (玩游戏的你)
截止时间	Meet	实时系统 (嵌入式/工控)

4.进程的切换

进程的生命周期（创建、撤销、IO、切换）都必须通过系统调用 (System Call) 进入内核来处理。

在进程看来，它好像在独占 CPU，但实际上是内核在背后不断地“暂停-保存-恢复-启动”，维持着多任务的假象。

---

1. 什么是进程切换？

在单核 CPU 中，同一时刻只能有一个进程在运行。为了让用户感觉到多个程序在并行，操作系统会将 CPU 时间划分为极短的时间片。当一个进程的时间片用完，或者因为它需要等待某些资源（如磁盘 IO）而阻塞时，内核就会暂停当前进程，并将 CPU 交给另一个进程。

---

2. 进程切换的核心：上下文 (Context)

进程切换最关键的工作是保存和恢复“上下文”。上下文主要包含以下信息：

• 程序计数器 (PC)：下一条要执行的指令地址。
• 寄存器集合：通用寄存器、状态寄存器、栈指针等。
• 内存管理信息：页表、段表（用于虚拟地址映射）。
• 进程状态：如运行、就绪、阻塞等。

这些信息通常存储在内核为每个进程维护的 PCB (Process Control Block，进程控制块) 中。

---

3. 进程切换的具体步骤

进程切换是一个复杂的过程，通常由内核态代码完成，主要步骤如下：

1. 保存当前进程 (A) 的上下文：将 CPU 寄存器中的数据保存到进程 A 的 PCB 中。
2. 更新 PCB 状态：将进程 A 的状态从“运行态”改为“就绪态”或“等待态”。
3. 选择新进程 (B)：调度程序（Scheduler）根据调度算法（如时间片轮转、优先级调度）从就绪队列中选出下一个要运行的进程。
4. 更新进程 B 的状态：将进程 B 的状态改为“运行态”。
5. 恢复进程 B 的上下文：从进程 B 的 PCB 中读取之前保存的寄存器数值，载入到 CPU 中。
6. 跳转执行：根据恢复后的程序计数器，从进程 B 上次中断的地方继续执行。

---

4. 触发进程切换的时机

进程切换不会无缘无故发生，通常由以下事件触发：

• 中断 (Interrupt)：例如硬件时钟中断，表示当前进程的时间片已到。
• 系统调用 (System Call)：进程主动请求内核服务（如读取文件），在等待结果时会被切换。
• 自愿放弃：进程执行完毕或遇到无法继续执行的错误。
• 抢占 (Preemption)：一个更高优先级的进程进入就绪状态，内核强制切换当前进程。

---

5. 进程切换的代价 (Overhead)

虽然进程切换让系统看起来很流畅，但它是有开销的：

• CPU 周期消耗：保存和恢复寄存器需要时间。
• Cache 失效：这是最大的隐藏成本。新进程载入后，原先缓存在 L1/L2 Cache 中的数据可能不再适用，导致大量缓存缺失（Cache Miss），降低运行速度。
• 内核开销：调度算法本身也需要消耗计算资源。

注意： 相比之下，线程切换的开销通常比进程切换要小，因为线程共享相同的内存地址空间，不需要切换页表。

1. 传统切换：软件保存 (Standard Software Context Switch)

在大多数通用处理器（如典型的 x86 或 ARM 处理器）中，进程切换是一个昂贵的软件操作：

• 动作：内核代码必须手动发出指令，将 CPU 当前所有寄存器的值（如通用寄存器、栈指针等）一一写入主内存中的 PCB（进程控制块） 或内核栈中。
• 代价：这涉及大量的访存操作。此外，切换后往往会伴随高速缓存（Cache）失效，导致新进程启动初期性能极低。

2. 切换技术：硬件寄存器组 (Multiple Register Sets)

CPU 会在硬件内部直接集成多套寄存器组。其核心原理如下：

• 硬件备份：CPU 内部不只有一套 $R0-Rn$ 寄存器，而是有两套甚至更多。
• 指针跳转：当需要切换进程时，操作系统不需要搬运数据，只需修改一个名为 CWP (Current Window Pointer，当前窗口指针) 的硬件寄存器，指向另一套已经存在的寄存器组。
• 近乎零耗时：这种切换只需要一个或几个时钟周期，完全消除了将寄存器保存到内存的延迟。

6.模式切换 vs 上下文切换

维度	模式切换 (Mode Switch)	上下文切换 (Context Switch)
定义	CPU 在用户态和内核态之间转换	CPU 从一个进程切换到另一个进程运行
进程标识	不改变。逻辑上还是同一个进程	改变。切换前后是不同的进程
开销	较小。主要涉及栈指针和少量寄存器的切换	较大。涉及虚拟内存、页表、全局变量等资源的完全替换
关系	进程切换一定发生在内核态（意味着包含模式切换）	模式切换不一定会导致进程切换（如仅仅是普通的系统调用）

7.调度和切换

调度 vs 切换：决策与执行

很多人容易混淆这两个概念，但它们在操作系统中分工明确：

• 调度 (Scheduling)：“大脑决策”。调度程序（Scheduler）根据特定算法（如 RR 时间片轮转、CFS 完全公平调度）从就绪队列中挑选出下一个应该运行的进程。这是一种策略行为。
• 切换 (Switching)：“体力干活”。一旦决定了新进程，内核的切换代码（Dispatcher）就会执行具体的动作：把 CPU 资源从旧进程手中移交给新进程。这是一种执行行为。

先后顺序：通常是“先调度、后切换”。只有先选好了目标，才有切换的目标。

5.CPU调度算法

1.FCFS

先来先服务（First-Come, First-Served, FCFS） 是最简单、最直观的进程调度算法。它的核心思想正如其名：按照进程到达就绪队列的先后顺序来分配 CPU 资源。

以下是该算法的详细解析：

1. 算法原理

• 决策机制：这是一种典型的“调度”行为，即决定将 CPU 资源分配给哪个进程。
• 执行方式：系统维护一个就绪队列。每当有进程进入就绪态，就将其挂在队列末尾。每当当前运行的进程释放 CPU（运行结束或因 I/O 阻塞），调度程序就会选择队列头部的第一个进程。
• 性质：属于非抢占式（Non-preemptive）算法。一旦一个进程获得了 CPU，除非它自己运行结束或发生阻塞，否则它会一直占用 CPU，不会被中途强制切换。

2. 算法优点

• 简单易行：逻辑非常简单，只需要一个 FIFO（先进先出）队列即可实现。
• 公平性：从“排队”的角度来看是公平的，每个进程最终都能获得执行机会，不会出现“饥饿”现象（某个进程永远等不到 CPU）。

3. 算法缺点（核心问题）

• 平均周转时间长：如果一个长进程先到达，后面跟着几个短进程，那么短进程必须等待很长时间，导致系统整体的平均等待时间显著增加。
• 护送效应（Convoy Effect）：
  • 想象一个计算密集型的长进程先运行，后面跟着一堆 I/O 密集型的短进程。
  • 这些短进程可能只需要极短的 CPU 时间来发起 I/O 请求，但由于 FCFS 的限制，它们必须死等长进程完成。这会导致 CPU 和设备利用率的不均衡。
• 不利于交互式系统：响应时间无法保证，用户体验较差。

4. 性能衡量示例

假设有三个进程：

• P1：执行时间 24ms，0ms 时到达。
• P2：执行时间 3ms，1ms 时到达。
• P3：执行时间 3ms，2ms 时到达。

在 FCFS 下：

1. P1 先运行（0-24ms）。
2. P2 接着运行（24-27ms）。
3. P3 最后运行（27-30ms）。

• 平均等待时间：$(0 + 24 + 27) / 3 = 17ms$。

对比（如果短进程先运行）：

如果顺序是 P2 -> P3 -> P1，平均等待时间仅为 $(0 + 3 + 6) / 3 = 3ms$。可以看出 FCFS 对作业长度非常敏感。

5. 适用场景

• 目前主要作为辅助算法，例如在多级反馈队列调度中，对同一优先级的就绪队列常采用 FCFS。
• 适用于作业调度（将作业从外存调入内存）。
• 在对响应时间要求不高的后台批处理系统中仍有使用。

进程类型	FCFS 待遇	原因
长作业 / CPU 繁忙型	优待	非抢占式确保其能连续、高效地完成大量计算。
短作业 / I/O 繁忙型	冷落	极短的请求被堵在长任务后，导致响应慢且设备利用率低。

2.SJF

短作业优先（Shortest Job First, SJF） 是一种以进程的 CPU 执行时间（Burst Time） 为调度依据的算法。它优先选择估计运行时间最短的进程，以追求最佳的系统性能指标。

以下是该算法的详细解析：

1. 核心原理

• 调度准则：当 CPU 空闲时，从就绪队列中选择估计运行时间（CPU 区间）最短的进程，将处理机分配给它。
• 决策性质：这是一种典型的以“作业长度”为优先级的调度策略。

2. 算法分类

根据是否允许中断正在运行的进程，SJF 分为两种形式：

• 非抢占式 SJF（Non-preemptive SJF）：
  • 一旦 CPU 分配给某个进程，它就会一直运行直到完成或发生阻塞，即使中途有更短的进程到达，也不会切换。
• 抢占式 SJF（也称为 最短剩余时间优先，SRTF）：
  • 如果新到达的进程的预计运行时间比当前正在运行进程的剩余时间更短，则系统会暂停当前进程，转而执行新进程。

---

3. 算法优点

• “理论上”的最优平均等待时间：在所有进程同时到达的情况下，SJF 能够实现最小的平均等待时间和平均周转时间。
• 提高系统吞吐量：由于短作业能快速执行并退出系统，单位时间内完成的任务数量增加。

4. 算法缺点（核心难点）

• “饥饿”现象（Starvation）：这是 SJF 最严重的问题。如果系统中源源不断地有短作业进入，长作业可能会永远得不到 CPU 资源，从而产生“饿死”现象。
• 运行时间难以预估：在实际的通用操作系统中，很难准确知道一个进程接下来需要运行多久。通常只能通过历史记录进行“加权平均”预测。
• 对长作业不公平：虽然 FCFS 歧视短作业，但 SJF 则是极端地歧视长作业。

---

5. 性能对比示例

沿用之前 FCFS 的例子，假设 P1(24ms), P2(3ms), P3(3ms) 同时到达：

• FCFS 顺序 (P1, P2, P3)：平均等待时间 17ms。

• SJF 顺序 (P2, P3, P1)：

  1. P2 运行（0-3ms）
  2. P3 运行（3-6ms）
  3. P1 运行（6-30ms）
  • 平均等待时间：$(0 + 3 + 6) / 3 = 3ms$。
  • 结论：SJF 的平均等待时间远优于 FCFS。

6. 适用场景

• 主要用于早期批处理系统中的作业调度（因为作业量化较明确）。
• 在现代交互式系统中，SJF 很少直接作为唯一的调度算法，但其“短任务优先”的思想被广泛借鉴。

3.高响应比优先调度算法

高响应比优先（Highest Response Ratio Next, HRRN） 调度算法是一种综合平衡了 FCFS（先来先服务）和 SJF（短作业优先）优缺点的动态优先级调度算法。

它的核心设计目标是：既能照顾短作业，又能防止长作业因“饥饿”而死。

---

1. 核心公式

HRRN 算法的核心在于“响应比”（Response Ratio, $R_p$）的计算。每当调度程序需要挑选进程时，会计算就绪队列中每个进程的响应比：

$$R_p = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$$

---

2. 算法逻辑

• 短作业优先：当多个进程的等待时间相同时，要求服务时间越短，响应比越高，因此短作业会优先执行。
• 长作业不饿死：对于长作业，虽然其分母（要求服务时间）较大，但随着它在队列中等待时间不断增加，其分子也会变大，最终响应比会提高到足以获得 CPU 的程度。
• 性质：通常属于非抢占式算法。只有当当前进程运行完毕或主动阻塞时，才会计算并重新调度。

---

3. 算法优点

• 兼顾长短作业：它在一定程度上保留了 SJF 降低平均周转时间的优点，同时又弥补了 SJF 可能导致长作业饥饿的缺陷。
• 较好的响应时间：新到达的短作业能快速提升响应比，从而得到及时的响应。

4. 算法缺点

• 系统开销大：每次调度前都需要计算就绪队列中所有进程的响应比。如果队列中进程很多，频繁的浮点运算会增加系统的 CPU 负担。
• 服务时间预估难：和 SJF 一样，HRRN 仍然需要预知（或预测）进程的“要求服务时间”，这在实际的通用分时系统中很难做到准确。

4.优先级调度算法

优先级调度算法（Priority Scheduling Algorithm） 是一种更加灵活的调度策略，它为每个进程分配一个“优先级”，调度程序总是选择就绪队列中优先级最高的进程投入运行。

根据你之前上传的资料，调度是决策行为（决定给谁），而优先级就是这种决策的核心依据。

---

1. 算法核心机制

• 优先级表示：通常用一个整数表示。注意，不同系统定义不同（有些系统数字越小优先级越高，如 Linux；有些则相反）。
• 调度准则：当 CPU 空闲时，检查所有就绪进程，将 CPU 分配给优先级最高的那个。

2. 算法分类

优先级调度根据是否允许中途“换人”，分为两种模式：

• 非抢占式优先级调度：一旦最高优先级的进程占有了 CPU，它就会运行到结束或主动阻塞。即使中途来了更高优先级的进程，也必须等当前进程放手。
• 抢占式优先级调度：如果新到达的进程优先级比当前正在运行的进程还要高，内核会立即触发进程切换，保存当前进程上下文并运行新进程。

---

3. 优先级的类型

优先级可以根据是否改变分为两类：

• 静态优先级：进程创建时确定，整个运行期间保持不变。
  • 依据：进程类型（系统进程 vs 用户进程）、资源需求、用户级别等。
• 动态优先级：根据进程的运行情况动态调整。
  • 典型例子：你刚才提到的 HRRN（高响应比优先） 就是一种动态优先级调度，它的优先级随等待时间的增加而提高。

---

4. 核心问题：饥饿与老化

优先级调度算法面临的最大挑战是 “饥饿” (Starvation)。

• 问题：如果系统中不断有高优先级的进程进入，低优先级的进程可能永远无法获得 CPU。据说在 1973 年关闭麻省理工学院的一台计算机时，发现一个 1967 年提交的低优先级作业一直没被运行。
• 解决方案：老化 (Aging)：
  • 这是一种增加在系统中等待很长时间的进程优先级的技术。
  • 例如，每等待 1 分钟，就将该进程的优先级提升 1 级。最终，即使是优先级最低的作业也会变成最高优先级并被执行。

[Image explaining the Aging technique where process priority increases over time]

---

5. 优先级分配的常用原则

在操作系统内核设计中，通常遵循以下优先级逻辑：

1. 系统进程 > 用户进程：内核相关的任务（如内存管理、中断处理）必须优先处理。
2. 交互式进程 > 批处理进程：为了保证用户操作不卡顿。
3. I/O 繁忙型 > CPU 繁忙型：优先让 I/O 进程发起设备请求，从而让 I/O 设备和 CPU 并行工作，提高效率。

5.时间片轮询调度算法

时间片轮转（Round Robin, RR） 调度算法是专门为分时系统设计的。它的核心思想是：将所有就绪进程排成一个队列，并为每个进程分配一个固定的、极短的时间段，称为时间片（Time Quantum）。

以下是该算法的深度解析，结合了你提供的有关“进程切换”和“内核支持”的背景：

1. 算法工作原理

• 循环队列：操作系统将 CPU 资源按顺序分配给就绪队列中的每个进程。
• 强制抢占：这是一种抢占式算法。当一个进程的时间片用完时，即使它没有运行结束，系统也会由时钟装置发出中断信号，强制剥夺其 CPU 使用权。
• 循环往复：被剥夺 CPU 的进程会被放回就绪队列的末尾，等待下一轮调度。

2. 核心性能指标：时间片的大小

时间片的选择是 RR 算法性能的关键。根据你提供的资料，这直接影响了系统的开销：

• 如果时间片太大：它会退化为 FCFS（先来先服务） 算法。在这种情况下，短作业可能又要排在长作业后面等待很长时间，失去了“分时”的意义。
• 如果时间片太小：虽然响应速度变快了，但会导致极其频繁的上下文切换。
  • 每次切换都涉及“模式切换”（从用户态进入内核态）和“上下文保存与恢复”。
  • 过多的切换会使 CPU 大量时间浪费在内核管理而非真正的业务计算上，导致系统整体效率大幅下降。

3. 算法优缺点

• 优点：
  • 极致公平：每个进程都能定期获得 CPU，没有任何进程会“饥饿”。
  • 响应快：非常适合人机交互系统，用户能感觉到程序在“同时”运行。
• 缺点：
  • 平均等待时间长：由于每个进程都走走停停，总的平均周转时间往往比 SJF（短作业优先）要长。
  • 对进程类型不敏感：它不区分 I/O 繁忙型还是 CPU 繁忙型，这可能导致 I/O 设备的利用率不够理想（相比于那些会优先调度 I/O 进程的算法）。

---

4. 深度关联：为什么 RR 依赖内核与硬件？

• 内核支持：RR 调度完全是在操作系统内核的支持下实现的。每一次时间片到期，都必须通过中断进入内核态，由内核执行调度决策。
• 硬件加速的可能性：如果 CPU 支持多个寄存器组，那么 RR 算法在切换时间片时的开销会显著降低，因为“上下文切换”只需要简单地改变寄存器组指针，而不需要繁重的内存读写。
• 执行行为：RR 强调了“调度”和“切换”的紧密配合——时钟中断决定了“切换”的时机，而 RR 算法规则决定了“调度”给队列中的下一个谁。

6.多级队列调度算法

多级队列调度算法（Multi-level Queue Scheduling, MLQ） 是一种将就绪队列划分为多个独立队列的调度策略。它不是一种单一的算法，而是一个组合调度框架，旨在根据进程的性质（如重要性、响应需求）提供不同的处理方式。

以下是该算法的深度解析：

1. 核心设计思想：分类管理

在实际系统中，进程的类型多种多样。MLQ 算法将就绪队列永久地划分为若干个单独的队列。

• 分类标准：通常根据进程的属性进行划分，如：
  • 系统进程（优先级最高）
  • 交互式进程（如前台窗口程序，需要快速响应）
  • 批处理进程（如后台计算，对响应时间不敏感）
• 固定归属：在一个纯粹的多级队列算法中，进程进入系统时就被固定分配到某个队列，在运行过程中不能跨队列移动。

2. 双层调度机制

MLQ 涉及两个层次的调度决策：

• 内部调度（Intra-queue）：每个队列可以根据其进程特点，使用不同的调度算法。
  • 比如：前台队列使用 时间片轮转（RR） 以保证响应；后台队列使用 先来先服务（FCFS） 以减少切换开销。
• 外部调度（Inter-queue）：决定哪一个队列优先获得 CPU。
  • 固定优先级抢占调度：通常系统进程队列优先级 > 交互队列 > 批处理队列。只要高优先级队列有进程，低优先级队列就必须等待。
  • 给定时间配额：为了防止低优先级队列完全饿死，可以给每个队列分配一定的 CPU 时间百分比（如交互队列占 80%，批处理占 20%）。

---

3. 算法优缺点

• 优点：
  • 针对性强：可以为不同响应要求的进程量身定制算法。
  • 低调度开销：由于进程不需要在队列间移动，内核管理逻辑相对简单。
• 缺点：
  • 缺乏灵活性：如果一个进程的性质在运行中发生了变化（比如从 I/O 繁忙型变成了 CPU 繁忙型），它无法调整位置。
  • 饥饿问题（Starvation）：如果高优先级队列一直有任务，低优先级队列的进程可能永远得不到执行。

---

4. 关键区分：多级队列 (MLQ) vs 多级反馈队列 (MLFQ)

这是很多学习者容易混淆的地方：

特性	多级队列 (MLQ)	多级反馈队列 (MLFQ)
队列间移动	不允许	允许（根据运行表现升/降级）
灵活性	较低	极高，是现代系统的首选
解决饥饿	较难，依赖时间配额	较好，通过“老化”或降级机制解决

7.多级队列反馈调度算法

多级反馈队列调度算法（Multilevel Feedback Queue, MLFQ） 是现代操作系统（如 Windows、Linux、macOS）中应用最广泛、最复杂的 CPU 调度算法。

它通过动态调整进程的优先级，完美解决了“短作业优先”需要预知运行时间的问题，同时也有效避免了长作业的“饥饿”现象。

---

1. 核心运行机制

MLFQ 将就绪队列划分为多个优先级不同的队列（如 $Q_0$ 到 $Q_n$），并遵循以下规则：

• 初始进入：新进程进入系统时，首先被放入最高优先级的队列 $Q_0$。
• 按优先级调度：调度程序总是优先执行优先级最高队列中的进程。只有当 $Q_0$ 为空时，才会调度 $Q_1$ 中的进程，以此类推。
• 时间片差异化：优先级越高的队列，分配到的时间片越短；优先级越低的队列，时间片越长。
  • 例如：$Q_0$ 时间片为 8ms，$Q_1$ 为 16ms，$Q_2$ 为 32ms。
• 动态反馈（升/降级）：
  • 降级：如果一个进程在当前队列的时间片内没运行完，说明它是 CPU 繁忙型，它会被降入下一级低优先级队列。
  • 保持/升级：如果进程在时间片用完前因 I/O 阻塞（说明是 交互型/IO 繁忙型），它在就绪后会被放回原队列，或者在某些实现中被提拔到更高优先级队列。

---

2. 为什么它是“全能型”算法？

MLFQ 能够自动识别进程类型并采取不同的策略：

1. 对短作业友好：短作业通常能在 $Q_0$ 的第一个时间片内完成，这使它的平均周转时间接近于“短作业优先（SJF）”。
2. 对交互式进程友好：I/O 繁忙型进程频繁放弃 CPU，能长期留在高优先级队列，保证了极快的响应速度。
3. 防止饥饿（老化机制）：为了防止长作业在底层队列被“饿死”，系统会定期执行“优先级提升（Priority Boost）”，将所有等待过长的进程全部移回 $Q_0$。


6.多处理机调度

1.多处理机调度的亲和性和负载均衡

1. 处理器亲和性 (Processor Affinity)

亲和性是指一个进程在某个给定的 CPU 上尽量长时间运行，而不被迁移到其他处理器的倾向。

• 核心原因（高速缓存命中率）：当进程在 CPU 1 上运行时，它最近访问的数据会存留在 CPU 1 的一级/二级缓存（Cache）中。如果进程下次还在 CPU 1 上运行，它可以直接从缓存读取数据，速度极快。
• 迁移代价：如果进程被迁移到 CPU 2，那么 CPU 2 的缓存中没有该进程的数据（“冷”缓存），进程必须从内存重新读取，这会产生明显的性能损耗。
• 两种类型：
  • 软亲和性 (Soft Affinity)：操作系统内核尽量让进程留在原处理器上，但不做硬性保证。如果为了全局利益（如负载均衡），内核仍可能将其迁移。
  • 硬亲和性 (Hard Affinity)：通过系统调用（如 Linux 的 sched_setaffinity）显式将进程绑定到特定的一个或多个 CPU 核上运行。

---

2. 负载均衡 (Load Balancing)

负载均衡是指在对称多处理（SMP）系统中，为了充分利用所有 CPU 的计算能力，尝试将工作负载均匀地分配到每个处理器上。

• 必要性：如果没有负载均衡，可能会出现一个 CPU 忙得不可开交，而另一个 CPU 却在“摸鱼”闲置的情况。
• 实现方式：
  • 推送迁移 (Push Migration)：一个特定的内核任务会定期检查各 CPU 的负载。如果发现负载不平衡，它会主动将进程从繁忙的 CPU“推”向空闲的 CPU。
  • 拉取迁移 (Pull Migration)：当一个 CPU 运行完自己的队列而变得空闲时，它会主动从其他繁忙 CPU 的就绪队列中“拉”一个进程过来执行。

---

3. 亲和性与负载均衡的“矛盾”

这两个机制在设计目标上是冲突的：

• 负载均衡要求频繁地迁移进程，以达到 CPU 利用率的最大化。
• 亲和性则要求尽量减少迁移，以保证缓存命中率和执行速度。

现代系统的策略：操作系统内核（如 Linux 的 CFS 调度器）会在这两者之间寻找平衡。它通常会划定“调度域”，在同一个物理 CPU 的不同核心（共享 L3 缓存）之间进行负载均衡时，迁移成本较低；而只有当负载极度失衡时，才会进行跨物理 CPU 的迁移。

2.多处理机调度方案

1. 非对称多处理 (Asymmetric Multiprocessing, ASMP)

也称为“主从式（Master-Slave）”模式。

• 分配方式：系统中有一个特定的处理器作为“主处理器（Master）”，负责处理所有的调度决策、I/O 请求和其他系统活动。
• 从属处理器：其他的“从处理器（Slave）”只负责执行用户代码。
• 优点：由于只有一台机负责调度，避免了多处理器之间对共享数据结构的竞争，设计简单。
• 缺点：主处理器容易成为系统的性能瓶颈；如果主处理器故障，整个系统都会瘫痪。

2. 对称多处理 (Symmetric Multiprocessing, SMP)

这是目前最主流的方案（如现代的 Windows、Linux、macOS 均采用此方案）。

• 平等地位：每个处理器都是平等的，都可以进行调度决策。
• 自调度 (Self-Scheduling)：每个处理器都会检查共同的就绪队列，或者使用自己的私有队列来选择进程执行。
• 实现细节：
  • 静态分配：进程从创建到销毁都固定在某个 CPU 上。
  • 动态分配：进程可以在不同的 CPU 之间迁移，这需要负载均衡（如拉取迁移或推送迁移）来保证各核忙闲均匀。

---

3. 自调度与专用处理器分配

在多核环境下，调度策略可以更精细化：

• 自调度 (Self-Scheduling)：使用一个全局的就绪队列，所有 CPU 空闲时都去这个队列“抢”任务。
  • 优点：负载最平衡。
  • 缺点：需要对全局队列加锁，可能导致竞争；此外，进程频繁在不同 CPU 间跳动会导致 CPU 亲和性下降，Cache 命中率变低。
• 成组调度 (Gang Scheduling)：将一组相关的线程（如属于同一个并行作业的线程）同时调度到一组处理器上运行。这对于需要频繁通信的并行程序非常有效。
• 专用处理器分配 (Dedicated Processor Assignment)：在程序运行期间，为其专门分配一组处理器。这通常用于高性能计算，避免了任务切换带来的开销。

7.为什么要进行CPU调度

进行 CPU 调度（CPU Scheduling）是多任务操作系统能够高效运行的基础。如果不进行调度，计算机同一时间只能运行一个程序，且在程序等待输入输出（I/O）时，昂贵的 CPU 资源将被白白浪费。

根据你提供的资料和操作系统设计原理，进行 CPU 调度主要有以下几个核心原因：

---

1. 实现多任务处理 (Multitasking)

CPU 调度是多任务操作系统中的一个必需的特性。

• 并发执行：通过调度，操作系统可以在多个进程之间快速切换，使用户感觉到多个程序正在“同时”运行。
• 身份切换：调度程序负责决定“换哪个演员上场”，从而实现从一个进程到另一个进程的上下文切换。

2. 提高 CPU 利用率 (CPU Utilization)

这是调度最直接的目的。

• 避免闲置：当一个进程因为等待 I/O（如读取磁盘、等待网络响应）而阻塞时，如果不进行调度，CPU 就会处于空闲状态。
• 资源转换：调度程序会立即做出决策，将 CPU 分配给另一个处于“就绪”状态的进程，确保 CPU 尽可能保持繁忙。

3. 改善系统吞吐量 (Throughput)

• 任务管理：通过合理的调度决策（如短作业优先 SJF），系统可以在单位时间内完成更多的进程任务。
• 效率最大化：调度算法通过平衡 CPU 繁忙型和 I/O 繁忙型进程，使系统各部件（CPU 和外设）都能充分联动。

4. 保证公平性与防止“饥饿” (Fairness)

• 资源分配：调度是一种决策行为，旨在决定如何公平地将资源分配给各个进程。
• 防止独占：如果没有调度（如简单的 FCFS 遇到长作业），短作业或高优先级任务会被一直阻塞。调度算法（如时间片轮转或多级反馈队列）确保每个进程都有机会获得 CPU。

5. 缩短响应时间 (Response Time)

• 用户体验：在交互式系统中，用户不希望点击鼠标后等待太久。调度程序通过优先处理交互式进程，确保系统能够快速响应用户操作。
• 内核支持：这种快速响应必须在操作系统内核的支持下实现，通过频繁的模式切换和上下文切换来维持流程度。

---

总结：决策与执行的配合

如你上传的图片所述：

• 调度（决策）：解决“给谁”分配资源的问题。
• 切换（执行）：解决“如何”实际移交资源的问题。

正是因为有了 CPU 调度，计算机才能从单一任务的“计算器”进化为能够同时处理办公、娱乐、后台下载的“智能终端”。

8.调度算法有哪几种

1. 基础/批处理系统算法 (注重效率与平衡)

这些算法通常用于对实时性要求不高的场景。

• 先来先服务 (FCFS)：按到达顺序排队，简单但对短作业不友好（护卫效应）。
• 短作业优先 (SJF)：优先执行时间短的任务，能实现最短的平均等待时间。
• 高响应比优先 (HRRN)：根据 $R_p = 1 + \frac{\text{等待时间}}{\text{服务时间}}$ 动态计算优先级，兼顾长短作业并防止饥饿。

---

2. 分时操作系统调度 (注重交互性与公平)

分时系统（Time-sharing OS）（如 Linux、Windows）的主要目标是提供流畅的人机交互，让每个用户感觉独占 CPU。

• 时间片轮转 (RR)：
  • 原理：每个进程轮流执行一个固定的时间片。
  • 核心：完全依赖于内核发出的时钟中断进行强制抢占。
  • 挑战：由于切换极快，上下文切换开销成为瓶颈，此时硬件提供的多组寄存器优化能极大提升响应速度。
• 多级反馈队列 (MLFQ)：
  • 原理：设置多个优先级队列，时间片随优先级降低而增大，且进程能在队列间动态升降。
  • 优势：它是目前工业界最成熟的方案，能自动区分 I/O 繁忙型（高优）和 CPU 繁忙型（低优）进程。

---

3. 实时操作系统调度 (注重确定性与截止时间)

实时系统（RTOS）（如车载控制、工业控制系统）的核心不是“快”，而是“准”，即必须在规定的截止时间 (Deadline) 前完成任务。

• 固定优先级抢占调度 (RMS, Rate Monotonic Scheduling)：
  • 原理：属于静态优先级。周期越短（发生频率越高）的任务，优先级越高。
  • 应用：目前大多数商用 RTOS（如 VxWorks, uC/OS）都基于此理论。
• 最早截止时间优先 (EDF, Earliest Deadline First)：
  • 原理：属于动态优先级。截止时间越近的任务，优先级越高。
  • 挑战：虽然它能实现最高的 CPU 利用率，但实现复杂且在任务过载时系统行为难以预测。

---

总结：三种系统的核心差异

特性	批处理系统	分时操作系统	实时操作系统
典型算法	FCFS, SJF	RR, MLFQ, CFS	RMS, EDF
首要目标	吞吐量	交互响应时间	任务截止时间 (Deadline)
底层要求	较少的切换开销	频繁、高效的上下文切换	极低的中断响应延迟
调度性质	非抢占为主	必须具备抢占能力	极高优先级的强制抢占

9.补充

1. 调度级别	术语名称	形象比喻	核心目的
   高级调度	作业调度	大门保安：决定哪些应聘者（作业）可以进厂变成正式员工（进程）。	控制多道程序度
   中级调度	内存调度	宿舍宿管：把暂时没活干的员工送去校外宿舍（硬盘），给新员工腾床位。	提高内存利用率/节省内存
   低级调度	进程调度	流水线组长：决定谁现在上机器操作（CPU），频率极高。	提高 CPU 利用率

2. 互斥性 (Mutual Exclusion)： 注意： 互斥性是进程同步与通信的概念，属于“并发控制”范畴。它要求同一时间只有一个进程访问临界资源。调度算法的任务是决定“谁先用”，而不是“如何保证独占”。因此，它不是调度算法的设计指标

3. 进程上下文 (Process Context) 是指操作系统为了让一个进程在被中断（挂起）后能重新恢复运行，而必须保存的所有信息。它通常分为以下几部分：

   1. 用户级上下文 (User-level Context)：包含进程的用户程序、用户数据、用户堆栈 (D) 等。
   2. 寄存器上下文 (Register Context)：包含程序计数器 (PC)、状态寄存器、通用寄存器、堆栈指针等，这被称为进程现场信息 (A)。
   3. 系统级上下文 (System-level Context)：包含 进程控制信息 (B)（即 PCB 中的内容，如 PID、调度优先级等）、进程页表、内核栈等。

4. 为什么“中断向量”不属于进程上下文？

   • 中断向量 (Interrupt Vector) 是指中断服务程序的入口地址，通常存储在内存中的一个固定表格（中断向量表）里。
   • 它是操作系统内核在处理中断请求时使用的全局资源，由硬件和内核维护，用于确定发生某种中断时应该跳转到哪段代码去执行。
   • 中断向量与特定的进程无关，它不随进程的切换而改变。因此，它不属于任何特定进程的“上下文”。

5. 临界区 $\neq$ 不可调度

   • 进程在临界区被调度可能会导致其他想进入同一临界区的进程阻塞，但这不代表系统“无法”进行调度。

6. 上下文切换主要涉及 CPU 寄存器、内核栈 和 PCB 信息 的保存与恢复。进程的代码和数据通常保留在主存 (RAM) 中。只有在发生“页面置换”或“进程挂起（Swapping）”时，才会将数据移至磁盘。如果每次切换都读写磁盘，系统性能将因磁盘 I/O 过慢而彻底崩溃。

7. 切换类型	程序计数器 (PC)	寄存器与栈指针	虚拟地址空间 (页表)	进程资源 (文件表等)
   进程切换	更新	更新	更新	更新
   同一进程线程切换	更新	更新	不更新	不更新

8. 时间片轮询算法是据对可抢占的

9. 在操作系统中，作业和进程是两个既有联系又有区别的概念：

   1. 单位属性不同（答案B的核心）：
      • 作业是用户向计算机提交任务的任务实体。它是以用户任务为单位的，用户将程序、数据和操作说明书组织在一起形成一个作业。
      • 进程是操作系统进行资源分配和调度运行的基本单位。它是以操作系统控制为单位的，代表了程序在处理机上的一次执行过程。
   2. 存在形式不同：
      • 作业主要存在于外存（磁盘）中，处于“后备状态”。
      • 进程则是动态的，它存在于内存中，拥有自己的生命周期（创建、运行、撤销）。
   3. 对应关系：
      • 一个作业通常由一个或多个进程组成。当系统决定执行某个作业时，会为其创建一个或多个进程。

   ---

   排除其他选项：

   • A. 两者执行不同的程序段：错误。作业中的程序段最终就是通过进程来运行的，两者执行的代码内容是一致的。
   • C. 前者是批处理的，后者是分时的：错误。作业和进程的概念在批处理系统和分时系统中都存在。
   • D. 后者是可并发执行，前者则不同：错误。作业在后备队列中也可以看作是某种形式的并发准备，且多个作业对应的多个进程是在系统中并发执行的