计算机操作系统

机制和策略

多级反馈队列

概述
基本规则

比例份额

彩票调度

示例
代码分析
输出结果

彩票机制

彩票货币

示例
总结

其他机制

步长调度

示例
输出结果
对比测试
应用场景

往期推荐

大家好呀！我是小笙，本章我主要分享计算机操作系统 – 多级反馈队列&比例份额学习总结，希望内容对你有所帮助！！

机制和策略

上述提到的进程调度策略，更多是从理论/理想的角度去思考方式，但是实际往往要复杂的多，以下几个调度方式更多的是结合多个调度策略理论以及实际来展开的叙述

多级反馈队列

概述

多级反馈队列（MLFQ）是一种用于优化调度的著名方法，首次由Corbato于1962年提出，应用于CTSS系统

MLFQ旨在解决两个主要问题

优化周转时间：通过优先执行短作业，类似于SJF算法。然而，操作系统通常不知晓每个作业的运行时间，因此不能直接应用SJF
改善交互用户体验：通过减少响应时间，尤其适合交互式任务。虽然轮转算法能够改善响应时间，但会牺牲周转时间

结构

MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）

基本规则

多级反馈队列的基本规则里面融合了先进先出、最短任务时间优先以及轮转等调度策略的思想

首先，多级反馈队列的核心逻辑就是高优先级优先执行策略以及相同优先级以轮转的公平方式运行，所以提出规则 1、2

规则 1：如果A的优先级 > C的优先级，运行 A（不运行C）
规则 2：如果A的优先级 = B的优先级，轮转运行高优先级 A 和 B

但是上述存在一个问题就是，高优先级如果能够永远抢占运行，是否会导致饥饿？如何通过调整优先级的方式来解决该问题

默认工作到达系统的时候放在最高优先级，然后通过运行完一个时间片来判断是否需要降低优先级

规则 3：工作进入系统时，放在最高优先级（最上层队列）
规则 4a：工作用完整个时间片后，降低其优先级（移入下一个队列）
规则 4b：如果工作在其时间片以内主动释放 CPU，则优先级不变

在上述规则下，长任务会随着时间片的运行，优先级逐级降低（动态分析出长短任务，不需要提前预测任务的执行时长，更合理）

这里存在一个问题，如果主动释放 CPU 就可以保证其优先级，那是否可以设计出对应的程序主动在时间片内都释放其 CPU 呢，规则 4c 是对规则 4a、4b 的优化调整

规则 4c：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）

图中直观的对比了规则4c 是否采取的区别

如果长任务长时间处于低优先级，就会导致出现“饥饿”的问题，所以提出规则 5

规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列

图中直观的对比了规则 5 是否采取的区别（假设 S 为 50）

关于该调度算法还有一些问题。其中一个大问题是如何配置一个调度程序

配置多少队列？
每一层队列的时间片配置多大？
为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？

这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡

比例份额

比例份额算法的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间

本章主要介绍比例份额调度的两种实现方式：彩票调度和步长调度

彩票调度

核心思想是通过概率随机性实现动态比例资源分配，将资源管理抽象为”彩票数量管理”，以彩票数量反映进程对 CPU 时间的占有权重

示例

假设彩票数量一共为 100 张有，两个进程 A 和 B，A 拥有 35 张彩票，B 拥有 65 张彩票

彩票调度过程

彩票分配：调度程序知道总共的彩票数是 100 张

进程 A 拥有的彩票编号是 0 到 34（共 35 张）
进程 B 拥有的彩票编号是 35 到 99（共 65 张）

抽取彩票：调度程序从 0 到 99 之间的一个数字中随机抽取

如果抽取的数字在 0 到 34 之间，表示进程 A 中标，进程 A 将运行
如果抽取的数字在 35 到 99 之间，表示进程 B 中标，进程 B 将运行

概率分配：通过反复执行调度，彩票调度机制确保进程 A 和 B 大约会按照 75% 和 25% 的比例占用 CPU 时间

代码分析

定义进程结构体

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 定义进程结构体
typedef struct {
              
    char name[2];       // 进程名：'A' 或 'B'
    int lottery_count;  // 该进程持有的彩票数
    int range_start;    // 彩票编号的开始范围
    int range_end;      // 彩票编号的结束范围
} Process;

模拟彩票调度的函数，随机抽取一张彩票并执行

// 函数：模拟彩票调度
void lottery_scheduling(Process *A, Process *B) {
    // 总彩票数
    int total_lottery = A->lottery_count + B->lottery_count;
    
    // 随机抽取一个数字（从 0 到 total_lottery-1 之间的数字）
    int draw = rand() % total_lottery;

    printf("抽取的数字是: %d
", draw);
    
    // 判断是哪个进程中奖
    if (draw >= A -> range_start && draw <= A -> range_end) {
        printf("进程 %s 被选中运行
", A->name);
    } else {
        printf("进程 %s 被选中运行
", B->name);
    }
}

主函数用于初始化进程以及调用彩票调度算法

int main() {
    // 初始化随机种子
    srand(time(NULL));

    // 创建两个进程
    Process A = {"A", 35, 0, 34};  // 进程 A 拥有 35 张彩票，彩票编号范围 0 到 34
    Process B = {"B", 65, 35, 99}; // 进程 B 拥有 65 张彩票，彩票编号范围 35 到 99

    // 进行 10 次调度
    for (int i = 0; i < 10; i++) {
        printf("
第 %d 次抽取:
", i + 1);
        lottery_scheduling(&A, &B);  // 调用彩票调度函数
    }

    return 0;
}

输出结果

// 输出结果（去掉部分换行）
标准输出：// A 被执行 3 次 ; B 被被执行 7 次
第 1 次抽取:  抽取的数字是: 6   进程 A 被选中运行
第 2 次抽取:  抽取的数字是: 98  进程 B 被选中运行
第 3 次抽取:  抽取的数字是: 37  进程 B 被选中运行
第 4 次抽取:  抽取的数字是: 73  进程 B 被选中运行
第 5 次抽取:  抽取的数字是: 68  进程 B 被选中运行
第 6 次抽取:  抽取的数字是: 10  进程 A 被选中运行
第 7 次抽取:  抽取的数字是: 90  进程 B 被选中运行
第 8 次抽取:  抽取的数字是: 76  进程 B 被选中运行
第 9 次抽取:  抽取的数字是: 96  进程 B 被选中运行
第 10 次抽取: 抽取的数字是: 24  进程 A 被选中运行

彩票调度算法中利用随机性的优势，主要从以下三个方面进行阐述

避免边角情况的优势：与传统的调度算法（例如LRU替换策略）相比，彩票调度可以避免遇到一些边角情况（避免了这种最差情况）
轻量性：彩票调度算法的一个显著优势是它非常轻便（与需要大量状态记录和计时的传统公平份额调度算法不同，彩票调度只需要为每个进程分配一个彩票号码，几乎不需要跟踪每个进程的运行状态）
快速性：由于彩票调度的决策过程基于随机数的生成，通常来说它的执行速度非常快

注意：尽管它的优势在于简单、快速和避免最坏情况，但它也有可能导致某些进程因为没有足够的彩票而长时间无法获得 CPU 资源以及不好确认该如何分配给不同任务多少的彩票数量

彩票机制

彩票调度还提供了一些机制，以不同且有效的方式来调度彩票

彩票货币

提出了彩票货币的概念，就和现实的货币机制很像，每个国家都有自己的一套货币体系，当进行比较/流通的时候又会通过汇率相互转换

用于不同用户可以使用不同份额的彩票来给予不同的进程，但是当和其他用户一起占用资源的时候，需要兑换成全局的彩票份额来计算占用资源的比例

示例

假设前提

用户 A 有两个工作：A1 和 A2，每个工作各自拥有 500 张彩票，共 1000 张彩票
用户 B 只有一个工作：B1，它拥有 50 张彩票，共 50 张彩票
全局彩票一共有 100 张，分别可以分给用户 A、B 为 50 张全局彩票

第一步：兑换彩票

操作系统将用户 A 和用户 B 持有的彩票兑换为系统中的全局彩票

工作 A1、A2 分到的全局彩票数为 50/2 = 25 张
工作 B1 分到的全局彩票数为 50 张

第二步：抽奖决定调度

现在，全局彩票池总共有 100 张彩票（50 + 25 + 25）
操作系统会进行一次“抽奖”，通过随机选择一张全局彩票，决定哪个工作（A1、A2、B1）将获得 CPU 资源并执行

总结

彩票调度通过将用户的本地彩票转换成全局彩票来实现公平的资源分配
每个工作获得的调度机会与它持有的彩票数量成正比
这种调度方式随机决定哪个工作会运行，且其执行机会取决于彩票数量

其他机制

彩票转让：允许一个进程将自己的彩票临时转交给另一个进程
彩票通胀：一个进程可以临时增加或减少自己的彩票数量（这对于进程间信任的环境很有用，进程可以通过增加彩票数量告诉操作系统它需要更多的CPU时间，进而获得更多资源。然而，在没有信任的环境下，这可能被滥用）

虽然随机方式可以使得调度程序的实简单（且大致正确），但偶尔并不能产生正确的比例，尤其在工作运行时间很短的情况下，如下图两个拥有相同彩票数量任务的执行情况

因此提出了步长调度的方式来解决随机性带来的不确定性问题

步长调度

步长调度是一种基于确定性公平分配的进程调度算法，其核心是通过虚拟步长值实现资源按权重比例分配

基本思路：当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长，循环直至任务结束

示例

定义结构体和常量

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#define BASE_STRIDE 0x7FFFFFFF  // 防止溢出的大质数
#define TIME_SLICE  10          // 默认时间片
#define EXIT_FAILURE 1          // 异常退出

typedef struct {
              
    int pid;        // 进程ID
    int tickets;    // 分配的票数
    int stride;     // 计算出的步长
    int pass;       // 累计步长值
    int remain;     // 剩余执行时间（单位：ms）
} Process;

步长调度算法

// 步长调度
void stride_scheduler(Process *procs, int n) {
              
    int total_tickets = 0;
    
    // 初始化总票数
    for (int i = 0; i < n; i++) {
              
        total_tickets += procs[i].tickets;
    }

    // 计算初始步长
    for (int i = 0; i < n; i++) {
              
        calc_stride(&procs[i], total_tickets);
        procs[i].pass = 0;  // 初始累计值为0
    }

    // 调度循环
    while (1) {
              
        int selected = find_next_process(procs, n);
        
        // 如果所有进程都完成了，退出调度
        if (selected == -1) break;

        // 执行选中的进程
        execute_process(&procs[selected]);
        
        // 更新该进程的步长
        update_pass(&procs[selected]);
    }
}

// 计算步长
void calc_stride(Process *p, int total_tickets) {
              
    if (p->tickets == 0) {
              
        fprintf(stderr, "Error: Process %d has 0 tickets
", p->pid);
        exit(EXIT_FAILURE);
    }
    p->stride = total_tickets > 0 ? BASE_STRIDE / p->tickets : 0;
}

// 执行进程
void execute_process(Process *p) {
              
    // 执行时间
    int exec_time = (p->remain > TIME_SLICE) ? TIME_SLICE : p->remain;
    // 剩余时间
    p->remain -= exec_time;
    printf("Executing PID %d for %d ms, remaining: %d ms
", p->pid, exec_time, p->remain);
}

// 更新进程的累计步长值
void update_pass(Process *p) {
              
    p->pass += p->stride;
}

// 查找剩余时间大于 0 的最小累计步长值的进程
int find_next_process(Process *procs, int n) {
              
    int min_pass = INT_MAX;
    int selected = -1;

    for (int i = 0; i < n; i++) {
              
        if (procs[i].remain > 0 && procs[i].pass < min_pass) {
              
            min_pass = procs[i].pass;
            selected = i;
        }
    }
    return selected;
}

主函数 main

int main() {
              
    // 初始化三个进程
    Process processes[] = {
              
        {
              1, 30, 0, 0, 50},  // PID1: 30票，需执行50ms
        {
              2, 20, 0, 0, 30},  // PID2: 20票，需执行30ms
        {
              3, 10, 0, 0, 20}   // PID3: 10票，需执行20ms
    };
    
    stride_scheduler(processes, 3);
    return 0;
}

输出结果

Executing PID 1 for 10 ms, remaining: 40 ms
Executing PID 2 for 10 ms, remaining: 20 ms
Executing PID 3 for 10 ms, remaining: 10 ms
Executing PID 1 for 10 ms, remaining: 30 ms
Executing PID 2 for 10 ms, remaining: 10 ms
Executing PID 1 for 10 ms, remaining: 20 ms
Executing PID 1 for 10 ms, remaining: 10 ms
Executing PID 2 for 10 ms, remaining: 0 ms
Executing PID 3 for 10 ms, remaining: 0 ms
Executing PID 1 for 10 ms, remaining: 0 ms

对比测试

设置了两个流，其吞吐量比例为1:2，下图中显示了两种调度方法实现的吞吐量比

由于步长调度本质上是确定性的，因此在吞吐量比例上优于彩票调度，能够快速且稳定的接近目标比例值

但是步长调度需要为每个流维护更多的状态，并涉及相当多的处理开销；而彩票调度几乎不需要任何状态以及最少的处理

步长调度与彩票调度的对比测试

测试指标	步长调度	彩票调度
公平性误差（100次）	0.8%	5.2%
调度延迟（μs）	12.3	8.7
上下文切换次数	38	42
权重调整开销	需重新计算步长	只需修改票数

应用场景

虽然它们能够按比例分配 CPU 时间，但由于不能有效处理 I/O 密集型进程且票数分配问题复杂，这些方法并未广泛应用。相反，通用的调度算法（如 MLFQ）更为常见。然而，比例份额调度在一些特定场景中仍然有用，例如虚拟化环境中，能够更高效地为不同虚拟机分配 CPU 资源（VMware ESX 系统便采用了这种方式进行资源共享）