001-进程管理与进程调度算法

进程管理与进程调度算法

---

一、进程管理基础

1. 进程与线程对比

特性	进程 (Process)	线程 (Thread)
资源分配	独立内存空间、文件、I/O资源	共享进程资源
创建开销	大（需复制父进程资源）	小（仅需栈和寄存器）
通信方式	IPC（管道、共享内存等）	直接读写进程内存
切换开销	高（需切换地址空间）	低（共享地址空间）
安全性	高（隔离性强）	低（线程间可能相互破坏）
代表实例	Chrome多进程架构	Java多线程程序

2. 进程控制块 (PCB)

操作系统中每个进程对应一个PCB，包含：

struct task_struct {        // Linux内核PCB结构
    long state;             // 进程状态（运行/就绪/阻塞）
    unsigned int flags;     // 进程标志位
    int prio;               // 动态优先级
    struct mm_struct *mm;   // 内存管理信息
    struct files_struct *files; // 打开文件表
    pid_t pid;              // 进程ID
    struct list_head tasks; // 进程链表
    // ... 超过100个字段
};

3. 进程生命周期与状态转换

stateDiagram-v2
    [*] --> New: 创建进程
    New --> Ready: 资源就绪
    Ready --> Running: 被调度器选中
    Running --> Ready: 时间片用完
    Running --> Blocked: 等待I/O事件
    Blocked --> Ready: 事件完成
    Running --> Terminated: 执行结束

4. 进程控制原语

操作	系统调用	操作说明
创建进程	fork() / CreateProcess()	复制父进程PCB创建子进程
终止进程	exit() / TerminateProcess()	释放资源并通知父进程
等待进程	wait() / WaitForSingleObject()	父进程等待子进程结束
加载程序	exec() / CreateProcess()	替换进程内存空间为新程序
进程同步	semaphore / mutex	控制进程执行顺序

---

二、进程调度算法详解

1. 调度层次结构

┌───────────────────────┐
│   长程调度 (Job)       │◄── 控制内存进程数量
├───────────────────────┤
│   中程调度 (Swapping)  │◄── 内存↔外存进程交换
├───────────────────────┤
│   短程调度 (CPU)       │◄── 纳秒级CPU分配 (重点)
└───────────────────────┘

2. 调度算法性能指标

• 周转时间 = 完成时间 - 到达时间
• 响应时间 = 首次运行时间 - 到达时间
• 等待时间 = 就绪队列等待总时间
• 吞吐量 = 单位时间完成进程数
• 公平性 = 资源分配均衡度

3. 经典调度算法对比

算法	类型	特点	优点	缺点	适用场景
FCFS	非抢占	按到达顺序执行	简单公平	护航效应（长进程阻塞）	批处理系统
SJF	非抢占	执行时间最短优先	最小平均等待时间	需预知执行时间	嵌入式系统
SRTF	抢占	SJF的抢占版	响应更快	长进程可能饥饿	交互式系统
Priority	抢占/非抢占	按优先级执行	高优先级快速响应	低优先级饥饿	实时系统
Round Robin	抢占	固定时间片轮转	公平性好	上下文切换开销大	分时系统
Multilevel Queue	混合	多队列不同策略	灵活适应不同需求	配置复杂	通用操作系统
Multilevel Feedback Queue	混合	动态调整队列优先级	平衡响应和吞吐量	实现最复杂	Linux/Windows

4. 算法执行过程图示

FCFS (先来先服务)

进程 | 到达时间 | 执行时间
P1  | 0       | 24
P2  | 1       | 3
P3  | 2       | 3

执行顺序: 
[ P1 ████████████████████████ ] 0-24
[ P2 ███ ] 24-27
[ P3 ███ ] 27-30
平均等待时间 = (0 + 23 + 25)/3 = 16

SJF (最短作业优先)

进程 | 到达时间 | 执行时间
P1  | 0       | 6  
P2  | 2       | 8
P3  | 4       | 7  
P4  | 5       | 3

执行顺序:
[ P1 ██████ ] 0-6
[ P4 ███ ] 6-9
[ P3 ███████ ] 9-16
[ P2 ████████ ] 16-24
平均等待时间 = (0 + 4 + 5 + 1)/4 = 2.5

Round Robin (时间片=4)

进程 | 执行时间
P1  | 24
P2  | 3
P3  | 3

执行轮转:
[ P1 ████ ] 0-4 → [ P2 ███ ] 4-7 → [ P3 ███ ] 7-10 
→ [ P1 ████ ] 10-14 → [ P1 ████ ] 14-18 → [ P1 ████ ] 18-22 
→ [ P1 ████ ] 22-26 → [ P1 ██ ] 26-28
平均等待时间 = (0+4+7)/3 = 3.67

5. Linux CFS 调度器 (Completely Fair Scheduler)

核心思想：虚拟运行时间（vruntime）决定调度顺序

// 关键数据结构
struct sched_entity {
    u64         vruntime;      // 虚拟运行时间
    u64         exec_start;    // 本次执行开始时间
    u64         sum_exec_runtime; // 总实际运行时间
};

// 虚拟时间计算
vruntime = actual_runtime * NICE_0_LOAD / weight

调度过程：

1. 选择红黑树最左侧（vruntime最小）进程
2. 运行进程直到：
   • 时间片用完（由sched_latency_ns控制）
   • 主动放弃CPU（如I/O阻塞）
   • 更高优先级进程就绪
3. 更新vruntime并重新插入红黑树

动态优先级调整：

bonus = sleep_avg / (sleep_avg + run_avg) * MAX_BONUS
priority = static_priority - bonus + 5

6. Windows 调度算法

多优先级队列结构：

┌──────────────┐
│ 实时优先级   │ 31-16 (固定优先级)
├──────────────┤
│ 可变优先级   │ 15-0  (动态调整)
│  ├───────────┤
│  │ 时间配额  │ 每个线程分配CPU时间单元
│  └───────────┤
└──────────────┘

动态调整规则：

• I/O型线程：优先级提升（+1~+2）
• CPU密集型线程：优先级降低（-1）
• 前台进程：时间配额加倍
• 饥饿线程：优先级提升至15

---

三、高级调度技术

1. 多核调度策略

策略	实现方式	优势
对称多处理 (SMP)	所有核共享就绪队列	负载均衡简单
非对称多处理 (AMP)	特定核运行特定任务	减少缓存失效
核心亲和性	绑定进程到指定CPU	提高缓存命中率
负载均衡	定期迁移进程	避免核心空闲

2. 实时调度算法

关键指标：

• **截止期限 (Deadline)**：任务必须完成的时间点
• 松弛时间 (Laxity) = 截止期限 - 剩余执行时间 - 当前时间

算法	策略	适用场景
RM	周期越短优先级越高	周期性任务
EDF	截止时间越早优先级越高	动态任务集
LLF	选择松弛时间最小的任务	高利用率系统

3. 容器调度 (Docker/Kubernetes)

核心机制：

# Kubernetes 调度配置示例
apiVersion: v1
kind: Pod
metadata:
  name: nginx
spec:
  containers:
  - name: nginx
    image: nginx:1.14
    resources:
      requests:
        cpu: "500m"   # 0.5个CPU核心
        memory: "512Mi"
      limits:
        cpu: "1000m"  # 不超过1个核心
        memory: "1Gi"
  nodeSelector:        # 节点选择
    disktype: ssd

调度器类型：

• BinPack：尽可能填满节点（提高资源利用率）
• Spread：分散部署（提高可用性）
• Custom：用户自定义策略

---

容器调度系统深度解析（以 Kubernetes 为例）

容器调度需解决 资源分配、负载均衡 和 高可用 问题，其核心流程分为 过滤 → 打分 → 绑定。

1. 调度核心机制

• 节点过滤（Predicates）：
  淘汰不满足条件的节点，例如：
  • PodFitsResources：节点剩余资源需 ≥ 容器需求。
  • NoDiskConflict：存储卷冲突检测。
• 节点打分（Priorities）：
  对合格节点多维度评分：
  • 资源平衡分（BalancedResourceAllocation）：优选 CPU/内存利用率接近的节点（避免单一资源瓶颈）。
  • 低负载分（LeastRequestedPriority）：选择资源空闲率高的节点。

2. 高级调度策略

• 亲和性（Affinity）：

  affinity:
    nodeAffinity:
      requiredDuringSchedulingIgnoredDuringExecution:
        nodeSelectorTerms:
        - matchExpressions:
          - key: disktype
            operator: In
            values: [ssd]  # 强制调度到 SSD 节点

• 反亲和性（Anti-Affinity）：
  避免同一服务的多个实例共存于同一节点（提升容灾能力）。
• 跨域调度：
  将容器调度至用户地理最近的节点（减少延迟）。

3. 工业级优化策略

• 动态资源预测（阿里 Sigma 系统）：
  基于历史监控数据（如 Prophet 算法）预测资源需求，实现错峰部署（如日间计算型 + 夜间存储型容器混部）。

  # 伪代码：利用时间序列预测资源峰值
  predicted_cpu = prophet.predict(historical_cpu_data)
  schedule_to_node_with_lowest_peak_overlap()

• 资源超售与回收：
  • 生产任务（Prod）优先使用物理资源。
  • 非生产任务（Non-prod）使用剩余资源，可被强占。
• 公平调度（DRF）：
  按“主导资源”（如 GPU 密集型容器的 GPU 占比）分配资源，避免小任务饿死。

4. Kubernetes 调度流程示例

graph TD
    A[新 Pod 创建] --> B{过滤节点}
    B --> C[资源足够]
    B --> D[端口冲突]
    C --> E[生成候选节点列表]
    E --> F[按策略打分]
    F --> G[选择最高分节点]
    G --> H[绑定 Pod 到节点]

---

实践案例与性能优化

1. 阿里双 11 调度实战

• 挑战：应对瞬时 100 倍流量增长。
• 方案：
  • 混部技术：在线业务（CPU 敏感）与离线任务（I/O 敏感）混合部署，提升资源利用率 40%。
  • 打散部署：同服务容器分散至不同机架/机房，单点故障影响下降 90%。

2. 调度算法优化方向

• 装箱算法改进：
  结合 BinPack（减少节点数）与 Spread（均衡分布），平衡成本与可用性。
• 实时迁移：
  基于节点负载预测（如线性回归）自动迁移容器，避免热点。

---

总结

• 磁盘调度：LOOK/C-LOOK 是现代系统首选，兼顾效率与公平性。
• 容器调度：动态预测 + DRF 公平策略 + 亲和性规则 是 Kubernetes 高性能调度基石。
• 工业实践：阿里、Google 等通过 混部技术 与 资源超售 实现超大规模集群利用率提升（如 Borg 系统资源利用率达 60% 以上）。

更详细的调度过程动态演示可参考 Kubernetes 调度器文档。

---

四、现代调度器实现分析

Linux CFS 调度器

// 调度主循环 (kernel/sched/core.c)
void schedule(void) {
    struct task_struct *prev, *next;
    prev = current;
    
    // 1. 选择下一个任务
    next = pick_next_task(rq);
    
    // 2. 上下文切换
    if (prev != next) {
        rq->curr = next;
        context_switch(prev, next);
    }
}

// 选择下一个任务 (kernel/sched/fair.c)
static struct task_struct *
pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    
    // 从红黑树取最左节点
    se = __pick_first_entity(cfs_rq);
    return task_of(se);
}

Windows 调度器关键流程

; Windows内核调度入口 (KiDispatchInterrupt)
KiDispatchInterrupt:
    call KiFindReadyThread  ; 寻找就绪线程
    test eax, eax
    jz no_thread_ready
    call KiSwapContext      ; 执行上下文切换
    ret
no_thread_ready:
    call KiIdleLoop         ; 进入空闲循环

---

五、性能优化实践

1. 调度延迟优化

• 禁用内核抢占：preempt_disable()
• CPU隔离：isolcpus=1,2（隔离CPU核）
• 实时优先级：sched_setscheduler(policy, SCHED_FIFO)

2. 负载均衡策略

graph TD
    A[检测负载不均衡] --> B{迁移类型}
    B -->|任务迁移| C[选择迁移进程]
    B -->|CPU迁移| D[调整进程亲和性]
    C --> E[在目标CPU唤醒进程]
    D --> F[更新硬件上下文]

3. NUMA调度优化

Node0 (CPU0-CPU3)      Node1 (CPU4-CPU7)
├── 本地内存           ├── 本地内存
└── 远程访问延迟高      └── 远程访问延迟高

优化策略：
1. 进程绑定到Node
2. 内存分配优先本地
3. 中断绑定到指定CPU

---

六、调度算法实战分析

场景：Web服务器进程调度

要求：
- 高并发I/O密集型
- 低延迟响应
- 避免CPU饥饿

解决方案：
1. 使用多级反馈队列 (MLFQ)
   - 高优先级队列：时间片短 (10ms) 
   - 低优先级队列：时间片长 (50ms)
2. 动态优先级调整：
   - 完成I/O后提升优先级
   - CPU长时间运行降低优先级
3. 设置最低保证时间片

调度器配置示例 (Linux)

# 设置CFS参数
echo 1000000 > /proc/sys/kernel/sched_latency_ns
echo 100000 > /proc/sys/kernel/sched_min_granularity_ns

# 实时进程优先级
chrt -f -p 99 <pid>

---

七、未来发展趋势

1. AI驱动调度：基于机器学习预测任务行为
2. 异构计算调度：CPU/GPU/DPU统一调度
3. 量子计算调度：量子比特任务分配算法
4. 边缘计算调度：低延迟分布式调度

关键结论：
进程调度是操作系统性能的核心，现代系统通过动态优先级、多级队列和公平分配策略，在响应性、吞吐量和公平性之间取得平衡。理解不同调度算法特性，是优化系统性能的关键基础。