通信网理论基础作业：GPS和WFQ调度的实现

——基于C++和Qt 6.9

信息科学技术学院    24信息与通信工程学硕

引言

声明：本文所有用到AI工具的部分都已经声明具体的AI工具，并明确给出了相关的提示词，其他未声明部分均为人工撰写或AI辅助不超过10%

这段时间学了点Qt，正好用这个作业练练手，我把所有工作过程都写了上来，所以可能全文比较长。

本文将同步更新在CSDN：https://honev.blog.csdn.net/article/details/149208796

相关调度的打包安装程序将放在CSDN文章附件部分。欢迎下载试用！

本文全部代码也已开源，欢迎访问与fork： 鸥梨菌Honevid/通信网GPS和WFQ调度和Qt可视化实现

上图演示的是教学PPT上的例子，权重为1:1，该程序理论上能支持最多10个业务的调度，但由于时间有限，没有做具体的测试。

GPS和WFQ的介绍

声明：本部分由AI（豆包）生成，仅供算法实现前的学习使用，提示词如下：

详细介绍GPS调度算法和WFQ调度算法，需要算法的完整步骤、各举一个清晰直观的例子

GPS调度算法（广义处理器共享）

算法原理与核心思想

GPS（Generalized Processor Sharing）是一种理想的调度模型，其核心思想是根据每个流的权重分配系统资源（如带宽），确保每个流获得的服务速率与权重成正比。它是一种非抢占式的调度模型，理论上为不同业务流提供精确的公平性保证。

完整步骤

1. 定义权重与服务速率
   设系统中有$n$个队列（流），每个队列$i$分配权重$w_i$，总权重为$W={\sum }_{i=1}^n{w}_i$。队列$i$的理论服务速率为$r_i=\frac{w_i}{W}\times R$，其中$R$是系统总带宽。

2. 虚拟时间与完成时间计算
   对于每个到达队列$i$的分组$j$，其虚拟开始时间$S_{i,j}$和虚拟完成时间$F_{i,j}$计算如下：

   • 若队列为空，分组到达时立即开始服务：
     $S_{i,j}=A_{i,j}(\text{其中 }{A}_{i,j}\text{ 为分组到达时间})$
     $F_{i,j}=S_{i,j}+\frac{L_{i,j}}{r_i}(\text{其中 }{L}_{i,j}\text{ 为分组长度})$
   • 若队列非空，分组需等待前一个分组完成：
     $S_{i,j}=\max (A_{i,j},F_{i,j-1})$
     $F_{i,j}=S_{i,j}+\frac{L_{i,j}}{r_i}$

3. 调度决策
   系统始终选择所有就绪分组中 虚拟完成时间最小 的分组进行服务。

直观例子

场景：系统有2个队列A和B，权重分别为$w_A=2$，$w_B=1$，总带宽$R=3$Mbps，因此$r_A=2$Mbps，$r_B=1$Mbps。分组到达情况如下：

队列	分组	到达时间$A_{i,j}$	长度$L_{i,j}$（bit）
A	1	0	2000
A	2	1	2000
B	1	0	1000

步骤计算：

1. 分组A1：
   $S_{A1}=0$，$F_{A1}=0+\frac{2000}{2000000}=0.001$秒（1 ms）。
2. 分组B1：
   $S_{B1}=0$，$F_{B1}=0+\frac{1000}{1000000}=0.001$秒（1 ms）。
   此时A1和B1的完成时间相同，按任意顺序调度（假设先调度A1）。
3. 分组A2：
   到达时间1 ms，此时A队列前一个分组A1的完成时间为1 ms，因此：
   $S_{A2}=\max (1,1)=1$ms，$F_{A2}=1+\frac{2000}{2000000}=2$ms。
4. 调度顺序：
   • 0 ms：调度A1（完成时间1 ms）。
   • 1 ms：A1完成，此时B1的完成时间1 ms，A2的完成时间2 ms，调度B1（完成时间1 ms + 1 ms服务时间=2 ms）。
   • 2 ms：B1完成，调度A2（完成时间2 ms）。

结果：分组按A1→B1→A2的顺序服务，A获得2/3的带宽，B获得1/3的带宽，符合权重比例。

WFQ调度算法（加权公平队列）

算法原理与核心思想

WFQ（Weighted Fair Queuing）是GPS的近似实现，通过虚拟时间戳和队列管理，在实际网络设备中模拟GPS的公平性。它为每个队列分配权重，并根据虚拟时间戳决定分组的调度顺序，避免高带宽流垄断资源。

完整步骤

1. 初始化参数
   为每个队列$i$分配权重$w_i$，维护每个分组的虚拟开始时间$S_{i,j}$和虚拟完成时间$F_{i,j}$。

2. 分组到达处理
   当分组$j$到达队列$i$时：

   • 若队列为空，计算虚拟开始时间和完成时间：
     $S_{i,j}=A_{i,j}$
     $F_{i,j}=S_{i,j}+\frac{L_{i,j}}{w_i}$
   • 若队列非空，前一个分组的虚拟完成时间为$F_{i,j-1}$，则：
     $S_{i,j}=\max (A_{i,j},F_{i,j-1})$
     $F_{i,j}=S_{i,j}+\frac{L_{i,j}}{w_i}$

3. 调度决策
   系统从所有非空队列的队首分组中，选择 虚拟完成时间最小 的分组进行服务，服务完成后从队列中移除该分组。

直观例子

场景：同样使用2个队列A和B，权重$w_A=2$，$w_B=1$，分组到达情况与GPS例子相同：

队列	分组	到达时间$A_{i,j}$	长度$L_{i,j}$
A	1	0	2000
A	2	1	2000
B	1	0	1000

步骤计算：

1. 分组A1：
   $S_{A1}=0$，$F_{A1}=0+\frac{2000}{2}=1000$（虚拟时间单位，假设无实际时间单位，仅比较相对大小）。
2. 分组B1：
   $S_{B1}=0$，$F_{B1}=0+\frac{1000}{1}=1000$。
   此时A1和B1的完成时间相同，假设先调度A1。
3. 分组A2：
   到达时间1（虚拟时间单位），A队列前一个分组A1的完成时间为1000，因此：
   $S_{A2}=\max (1,1000)=1000$，$F_{A2}=1000+\frac{2000}{2}=2000$。
4. 调度顺序：
   • 初始：A1（F=1000）和B1（F=1000），调度A1。
   • A1服务完成后，B1的F=1000，A2的F=2000，调度B1（F=1000）。
   • B1服务完成后，调度A2（F=2000）。

结果：调度顺序与GPS一致（A1→B1→A2），WFQ通过虚拟时间戳模拟了GPS的权重比例，保证了公平性。

算法对比与总结

• GPS：理论上的理想模型，精确按权重分配带宽，但需要实时计算虚拟完成时间，且无法处理突发流量，实际实现困难。
• WFQ：GPS的近似算法，通过离散分组调度和虚拟时间戳实现公平性，易于在网络设备中部署，是实际网络中常用的公平调度算法。

两者的核心均为“按权重分配资源”，WFQ通过简化计算和队列管理，在实际场景中实现了对GPS的有效模拟，广泛应用于路由器、交换机等网络设备的流量调度。

使用C++实现GPS和WFQ的核心代码

声明：该部分实现全部由本人手撸C++代码，包括数据结构（类）的定义和函数的声明、实现。

核心代码编写思路

目标是使用Qt绘制折线图实时显示任务的处理情况，那么显然纵坐标是已完成的任务量，横坐标是时间轴，那么很清晰了，需要写两个函数GPS()和WFQ()，输入时间（x轴数据）进去，返回一个当前完成的任务量（y值）出来，为了折线图的连续性，时间的精度越小（比如每0.01s计算一次函数y值）图像越精准，这也就要求设计两个函数GPS()和WFQ()的时候要保证小颗粒的访问也能得到精确的已完成任务量返回值。

由于一开始未能有明确的架构，在写了初版代码后频繁打断点调试有了目前能够符合书本样例的代码，当然代码中有许多冗余啰嗦之处，鉴于能够成功跑通，我就没有再花功夫精简了。

数据结构及成员函数定义

为保证数据结构访问的灵活性，全部成员变量都设为公有类型，如果后续有人想完善代码，可以考虑设置严格的访问权限，注释中已经给出了相关变量的介绍。

//定义数据结构:时间片
class TimeSlice {
public:
  //用于描述到达
  float arriveTime; //到达时间
  float workLoad; //业务量
  //用于描述执行
  float startTime; //开始处理的时间
  float lastCheckTime;
  float leftWorkLoad; //剩余业务量
  float endTime; //结束处理的时间
  TimeSlice(float arrive, float work)
    : arriveTime(arrive), workLoad(work), startTime(0), endTime(0),lastCheckTime(0),leftWorkLoad(work) {
  }//初始化时间片
};

//定义数据结构:业务
class Business {
public:
  float weight;//权重，各个业务的占比
  bool isBeingServiced = false; //是否正在被服务，如果队列为空，必须设置为false
  // 创建业务到达队列
  std::queue<TimeSlice> timeSlice;
  float currentWorkLoad; //当前完成的业务量总和
  float getCurrentWorkLoadSum(float time, float otherWeight);
};

接下来是成员函数float getCurrentWorkLoadSum(float time, float otherWeight);的定义，其中time表示时间输入（x轴数据），otherWeight表示当前系统中业务的总权重，如果采用GPS，函数增长的斜率与此有关，该业务成员函数的目的是，能够根据输入的时间和总权重值得到当前业务的已完成工作量，代码如下：

float Business::getCurrentWorkLoadSum(float time, float otherWeight) {//根据时间获取当前业务量总和（即Y轴的坐标）
  if (!isBeingServiced)
  {
    return currentWorkLoad;
  }
  //如果正在被服务，则需要计算当前时间点的业务量
  TimeSlice& currentSlice = timeSlice.front();//不出队读取当前正在服务业务的时间片
  float servicedWorkLoad = (time - currentSlice.lastCheckTime) * weight / otherWeight;//自从开始服务，完成的业务量
  currentSlice.leftWorkLoad -= servicedWorkLoad; //更新剩余业务量

  float workOffset = 0;
  workOffset = currentSlice.workLoad - currentSlice.leftWorkLoad;
  return  currentWorkLoad + workOffset; //返回当前业务量总和
}

核心代码实现

以教学PPT的例子为例，讲述实现的代码含义

GPS实现

输入：

1. businessQueue[]：业务组，即示例中的两个优先级，每个数组的业务元素包含权重和时间片到达队列
2. time：当前时间
3. size：业务组长度：教材中两个优先级，那么size为2
4. y：输出的已完成工作量数组，y[0]即为优先级1在当前time采用GPS调度的y轴值
5. &otherWeight：系统中总权重值，由于此值影响系统的后续运行，因此是引用调用，每次都可能修改

输出：int类型数据，表示当前time下，系统中执行的项目数，这个输出如果一直为0表示已经完成了所有的工作量。

功能流程：

1. 计算当前各个业务完成的工作量
2. 判断是否有新的时间片到达，如果有，需要更新权重（增加）
3. 判断是否有旧的时间片执行完成，如果有，需要视情况更新权重：如果有新的接续，那么权重不变，如果没有新的时间片接续，权重减少

本函数最难实现的就是权重的变换，由于权重已经是引用值，一开始将getCurrentWorkLoadSum()的参数otherWeight也设置成了引用，且判断旧时间片是否完成的功能写在了getCurrentWorkLoadSum中，于是频繁导致otherWeight变成脏数据，举个例子：

假设业务1在time下已经完成当前的时间片，后续的时间片不用立即执行，那么otherWeight的值需要减去业务1的权重变成new-otherWeight，但这会导致接下来计算业务2已完成任务量的时候出现错误，因为业务1和业务2在同一time下，应该使用相同的总权重值来计算已完成任务量。

//测试通过
//非抢占的 GPS 调度算法
int GPS(Business businessQueue[], float time, int size, float y[],float & otherWeight) {
  //统计当前time下，哪些业务到达需要服务
  int countWork = 0;//业务计数
  //第一次遍历业务，输出上个时间段的执行情况
  for (int i = 0; i < size; i++)
  {
    //无论是否执行，都要计算上次check到这次完成了多少，用旧的权重
    y[i] = businessQueue[i].getCurrentWorkLoadSum(time, otherWeight);//获取当前业务量总和
  }
  //第二遍遍历业务：判断执行情况，跟新业务量和权重总和
  for (int i = 0; i < size; i++)
  {
    if (businessQueue[i].timeSlice.empty())
    {
      continue;
    }
    TimeSlice& currentSlice = businessQueue[i].timeSlice.front();//不出队读取当前正在服务业务的时间片
    currentSlice.lastCheckTime = time; //更新上次检查时间
    //统计正在执行的业务
    if (businessQueue[i].isBeingServiced)
    {
      countWork++;
    }
    //统计正好要开始的业务，如果刚开始，那么就让加上此权重，给下次用
    if (currentSlice.arriveTime == time) {
      currentSlice.startTime = time; //设置开始时间
      countWork++;//业务计数
      if (!businessQueue[i].isBeingServiced)
      {
        otherWeight += businessQueue[i].weight; //统计新到达的业务权重总和
        businessQueue[i].isBeingServiced = true;
      }
    }
    //统计结束的业务
    //如果当前完成的业务量就是当前时间片的业务量，则将其出队
    if (currentSlice.leftWorkLoad <= 0)
    {
      //更新当前完成的业务量总和
      businessQueue[i].currentWorkLoad += currentSlice.workLoad;//只在出队后更新
      //设置结束时间
      currentSlice.endTime = time;
      businessQueue[i].timeSlice.pop();//出队
      if (!businessQueue[i].timeSlice.empty())
      {
        //判断下一个队首是否在此刻之前到达，如果到达，则服务状态不变
        if (businessQueue[i].timeSlice.front().arriveTime > time)
        {
          otherWeight -= businessQueue[i].weight;
          businessQueue[i].isBeingServiced = false;
        }
        else {
          businessQueue[i].timeSlice.front().lastCheckTime = time;
        }
      }
      else {
        otherWeight -= businessQueue[i].weight;
        businessQueue[i].isBeingServiced = false;
      }
    }
  }
  //替换otherWeight为新的权重总和
  return countWork;
}

WFQ实现

WFQ的代码输入和输出与上面的GPS基本一致，不做赘述，仅描述与GPS不同之处：

1. 不需要otherWeight参与计算了，因为只要业务运行，都是全速服务
2. 同一时间，需要计算当前系统中所有已经到达的时间片，计算按照GPS哪个执行得更快，选择一个快的来执行（根据我本科操作系统的学习，怀疑这种实现可能会导致业务的饥饿，比如某业务的时间片很大，需要执行时间很长，如果后续这个时间片抢夺服务权时总有小的时间片到达，那么就一直得不到执行，导致饿死）
3. 业务结束后，就算它接下来的时间片刚好到达，那也需要归还服务权，跟其他的时间片一起竞争。

//非抢占的WFQ调度算法
int WFQ(Business businessQueue[], float time, int size, float y[]) {
  int countWork = 0;//业务计数，其实可以不计
  bool competeSlices[10] = {false}; //竞争时间片是否参与竞争，业务数不能超过10个
  float competeTime[10] = {0}; //竞争时间片虚拟完成时间，业务数不能超过10个

  //第一次遍历业务，输出上个时间段的执行情况
  for (int i = 0; i < size; i++)
  {
    //无论是否执行，都要计算上次check到这次完成了多少，用旧的权重
    y[i] = businessQueue[i].getCurrentWorkLoadSum(time, businessQueue[i].weight);//获取当前业务量总和
  }

  //第二遍遍历业务：判断执行情况，跟新业务量和权重总和
  for (int i = 0; i < size; i++)
  {
    if (businessQueue[i].timeSlice.empty())//业务执行完就不判断执行情况了
    {
      continue;
    }
    TimeSlice& currentSlice = businessQueue[i].timeSlice.front();//不出队读取当前正在服务业务的时间片
    currentSlice.lastCheckTime = time; //更新上次检查时间

    //统计正在执行的业务
    if (businessQueue[i].isBeingServiced)
    {
      countWork++;
    }
    //统计正好要开始的业务，如果刚开始，那么就让加上此权重，给下次用
    if (currentSlice.arriveTime <= time&&countWork==0) {//
      competeSlices[i] = true; //标记当前业务的时间片正在竞争
      competeTime[i] = currentSlice.workLoad / businessQueue[i].weight; //计算当前业务的虚拟完成时间]
    }
    //统计结束的业务
    //如果当前完成的业务量就是当前时间片的业务量，则将其出队
    if (currentSlice.leftWorkLoad <= 0)
    {
      //更新当前完成的业务量总和
      businessQueue[i].currentWorkLoad += currentSlice.workLoad;//只在出队后更新
      //设置结束时间
      currentSlice.endTime = time;
      businessQueue[i].timeSlice.pop();//出队
      countWork--;
      businessQueue[i].isBeingServiced = false;

      if (!businessQueue[i].timeSlice.empty())
      {
        //判断下一个队首是否在此刻之前到达，如果到达，则服务状态不变
        if (businessQueue[i].timeSlice.front().arriveTime <= time)
        {
          businessQueue[i].timeSlice.front().lastCheckTime = time;

          //统计正好要开始的业务，如果刚开始，那么就让加上此权重，给下次用
          if (businessQueue[i].timeSlice.front().arriveTime <= time && countWork == 0) {//
            competeSlices[i] = true; //标记当前业务的时间片正在竞争
            competeTime[i] = businessQueue[i].timeSlice.front().workLoad / businessQueue[i].weight; //计算当前业务的虚拟完成时间]
          }
        }
      }
    }
  }
  if (countWork == 0)
  {
    int winnerIndex = -1; //没有业务在竞争
    //遍历竞争时间片，找到完成时间最短的时间片
    for (int i = 0; i < size; i++)
    {
      if (competeSlices[i]) {
        if (winnerIndex==-1)
        {
          winnerIndex = i;
        }
        if (competeTime[i]<competeTime[winnerIndex])
        {
          winnerIndex = i;
        }
      }
    }
    if (winnerIndex!=-1) {
      businessQueue[winnerIndex].timeSlice.front().startTime = time; //设置开始时间
      countWork++;//业务计数
      if (!businessQueue[winnerIndex].isBeingServiced)
      {
        businessQueue[winnerIndex].isBeingServiced = true;
      }
    }
  }
  //替换otherWeight为新的权重总和
  return countWork;
}

核心代码测试

测试代码

// 深度复制Business
Business createDeepCopy(const Business& A) {
  Business B;
  B.weight = A.weight;
  B.isBeingServiced = A.isBeingServiced;
  B.currentWorkLoad = A.currentWorkLoad;

  // 深度复制队列中的每个元素
  std::queue<TimeSlice> tempQueue = A.timeSlice;
  while (!tempQueue.empty()) {
    B.timeSlice.push(tempQueue.front());
    tempQueue.pop();
  }

  return B;
}

int main()
{
  // 创建测试数据
  const int SIZE = 2;
  Business businessQueue[SIZE];

  // 初始化业务1: 权重1, 四个时间片
  businessQueue[0].weight = 1.0;
  businessQueue[0].currentWorkLoad = 0;
  businessQueue[0].timeSlice.push(TimeSlice(1, 1));  // 到达时间1，业务量2
  businessQueue[0].timeSlice.push(TimeSlice(2, 1));  // 到达时间2，业务量1
  businessQueue[0].timeSlice.push(TimeSlice(3, 2));  // 到达时间3，业务量2
  businessQueue[0].timeSlice.push(TimeSlice(11, 2)); // 到达时间11，业务量2

  // 初始化业务2: 权重1, 三个时间片
  businessQueue[1].weight = 1.0;
  businessQueue[1].currentWorkLoad = 0;
  businessQueue[1].timeSlice.push(TimeSlice(0, 3));  // 到达时间0，业务量3
  businessQueue[1].timeSlice.push(TimeSlice(5, 2));  // 到达时间5，业务量2
  businessQueue[1].timeSlice.push(TimeSlice(9, 2));  // 到达时间9，业务量2

  // 创建业务队列的深拷贝用于测试
  Business testQueue[SIZE];
  for (int i = 0; i < SIZE; i++) {
    testQueue[i] = createDeepCopy(businessQueue[i]);
  }

  // 测试时间点
  float testTimes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,15,16,17,18,19,20 };
  const int TIME_COUNT = sizeof(testTimes) / sizeof(testTimes[0]);

  // 输出表头
  std::cout << "时间\t业务1完成量\t业务2完成量\n";

  float otherWeight = 0; // 用于存储其他业务的权重总和


  // 对每个测试时间点运行GPS算法
  for (int i = 0; i < TIME_COUNT; i++) {
    float time = testTimes[i];
    float y[SIZE] = { 0 };

    // 运行GPS算法
    int t = GPS(testQueue, time, SIZE, y,otherWeight);
    // 运行WFQ算法
    //int t = WFQ(testQueue, time, SIZE, y);
    // 输出结果
    //cout << endl<<"\t" << testQueue[0].isBeingServiced << "\t\t" << testQueue[1].isBeingServiced<<"\t" <<t<< endl;
    std::cout << time << "\t" << y[0] << "\t\t" << y[1]<<"\t\t" <<t<< "\n";
  }

  return 0;
}

测试结果

使用Qt进行可视化

声明：本部分代码部分借助AI工具（豆包），提示词包括：改错、修改代码以实现预期的效果等。

输入并解析成业务数据

如下图，业务权重栏输入权重表达式，如： 1:1; 的数据，即：业务0权重:业务1权重;

最多支持10个业务，即(2<=i<=9)：业务0权重:业务1权重:...:业务i权重;

业务到达时间输入框输入时间片，如：1:1.0-1.0,2-1,3-2,11-2; 2:0-3,5-2,9-2;的数据，即：

业务序号（1-10对应business数组序号的0-9）:到达时间(arriveTime)-工作量(workLoad),到达时间(arriveTime)-工作量(workLoad);

用户输入后需要按照上述规则进行解析，作为后续制图的数据来源，于是利用正则表达式进行识别，定义如下函数：

// 解析业务数据
bool Widget::parseBusinessData()
{
    // 清空原有数据
    for (int i = 0; i < 10; ++i) {
        business[i].weight = 0;
        business[i].isBeingServiced = false;
        while (!business[i].timeSlice.empty()) {
            business[i].timeSlice.pop();
        }
        business[i].currentWorkLoad = 0;
    }
    businessNumber = 0;

    // 解析业务权重数据
    QString weightsText = ui->lineEditWorksValue->text().trimmed();
    if (weightsText.isEmpty() || !weightsText.endsWith(';')) {
        QMessageBox::critical(this, "解析错误", "权重数据格式不正确，必须以分号结尾!");
        return false;
    }

    QStringList weightItems = weightsText.split(';', Qt::SkipEmptyParts);
    if (weightItems.size() != 1) {
        QMessageBox::critical(this, "解析错误", "权重数据格式不正确，应为多个权重用冒号分隔并以分号结尾!");
        return false;
    }

    QStringList weights = weightItems[0].split(':', Qt::SkipEmptyParts);
    businessNumber = weights.size();
    if (businessNumber < 1 || businessNumber > 10) {
        QMessageBox::critical(this, "解析错误", "业务数量必须在1-10之间!");
        return false;
    }

    for (int i = 0; i < businessNumber; ++i) {
        bool ok;
        business[i].weight = weights[i].toFloat(&ok);
        if (!ok || business[i].weight <= 0) {
            QMessageBox::critical(this, "解析错误", QString("业务%1的权重不是有效的正数!").arg(i+1));
            return false;
        }
    }

    // 解析业务到达数据
    QString arrivalText = ui->textEdit->toPlainText().trimmed();
    if (arrivalText.isEmpty()) {
        QMessageBox::critical(this, "解析错误", "业务到达数据不能为空!");
        return false;
    }

    QStringList businessItems = arrivalText.split(';', Qt::SkipEmptyParts);
    for (const QString& item : businessItems) {
        QStringList parts = item.split(':', Qt::SkipEmptyParts);
        if (parts.size() != 2) {
            QMessageBox::critical(this, "解析错误", QString("业务数据格式错误: %1").arg(item));
            return false;
        }

        bool ok;
        int businessIndex = parts[0].toInt(&ok) - 1; // 业务序号转数组索引
        if (!ok || businessIndex < 0 || businessIndex >= businessNumber) {
            QMessageBox::critical(this, "解析错误",
                                  QString("业务序号超出范围(1-%1): %2").arg(businessNumber).arg(parts[0]));
            return false;
        }

        QStringList timeSlices = parts[1].split(',', Qt::SkipEmptyParts);
        for (const QString& ts : timeSlices) {
            QStringList params = ts.split('-', Qt::SkipEmptyParts);
            if (params.size() != 2) {
                QMessageBox::critical(this, "解析错误", QString("时间片格式错误: %1").arg(ts));
                return false;
            }

            float arriveTime = params[0].toFloat(&ok);
            if (!ok || arriveTime < 0) {
                QMessageBox::critical(this, "解析错误", QString("到达时间无效: %1").arg(params[0]));
                return false;
            }

            float workLoad = params[1].toFloat(&ok);
            if (!ok || workLoad <= 0) {
                QMessageBox::critical(this, "解析错误", QString("工作量无效: %1").arg(params[1]));
                return false;
            }

            business[businessIndex].timeSlice.push(TimeSlice(arriveTime, workLoad));
        }
    }

    // 检查每个业务是否至少有一个时间片
    for (int i = 0; i < businessNumber; ++i) {
        if (business[i].timeSlice.empty()) {
            QMessageBox::critical(this, "解析错误", QString("业务%1没有有效的时间片数据!").arg(i+1));
            return false;
        }
    }

    return true;
}

创建业务到达的柱状图

当用户输入完成，点击生成柱状图，需要生成相应的业务到达柱状图。

需要实现的功能为：
按时间从0到最后一个业务到达，列出每个业务到达的任务量，不同业务需要用不同颜色的柱条显示在同一张柱状图中，business[]中的所有业务的所有到达业务都要按照时间顺序列在柱状图中，关键点有：

1. 数据预处理：
   • 深度复制业务数据，确保不修改原business[]数组
   • 遍历所有业务的timeSlice，计算最大到达时间，确定 X 轴范围为[0, 最大到达时间+1]
2. 横坐标配置：
   • 使用QValueAxis（数值轴）作为 X 轴，而非分类轴，确保分度值固定（此处固定为 1）
   • 刻度范围严格从 0 到最大到达时间+1，覆盖所有业务到达时间
3. 柱条数据处理：
   • 为每个业务创建独立QBarSet，使用不同颜色区分
   • 对每个时间点（按分度值间隔）统计对应业务的工作量总和（同一时间可能有多个任务到达，需累加）
   • 未到达任务的时间点填充 0，确保柱条连续显示

代码实现如下：

// 柱状图生成
void Widget::on_pushButtonBar_clicked()
{
    parseBusinessData();
    if (businessNumber == 0) {
        QMessageBox::information(this, "提示", "没有业务数据可供显示");
        return;
    }

    // 深度复制业务数据
    QVector<Business> copiedBusiness;
    for (int i = 0; i < businessNumber; ++i) {
        copiedBusiness.push_back(createDeepCopy(business[i]));
    }

    // 收集所有原始到达时间点
    QSet<float> allArrivalTimes;
    float maxWorkLoad = 0.0f;
    for (const auto& biz : copiedBusiness) {
        std::queue<TimeSlice> tempQueue = biz.timeSlice;
        while (!tempQueue.empty()) {
            const TimeSlice& ts = tempQueue.front();
            allArrivalTimes.insert(ts.arriveTime);
            if (ts.workLoad > maxWorkLoad) maxWorkLoad = ts.workLoad;
            tempQueue.pop();
        }
    }

    // 1. 处理原始时间点，插入中间间隔时间点（-1业务的到达时间）
    QVector<float> sortedArrivalTimes = allArrivalTimes.values();
    std::sort(sortedArrivalTimes.begin(), sortedArrivalTimes.end());

    // 存储插入间隔后的所有时间点（包含原始和中间间隔）
    QVector<float> allTimes = sortedArrivalTimes;

    // 遍历相邻时间点，计算并插入中间间隔时间
    if (sortedArrivalTimes.size() >= 2) {
        for (int i = sortedArrivalTimes.size() - 1; i > 0; --i) { // 从后往前插，避免索引混乱
            float tPrev = sortedArrivalTimes[i-1];
            float tCurr = sortedArrivalTimes[i];
            int intervalCount = static_cast<int>(tCurr - tPrev - 1); // 中间间隔数量（tPrev+1 到 tCurr-1）

            // 插入中间时间点（如tPrev=9, tCurr=11 → 插入10）
            for (int j = 1; j <= intervalCount; ++j) {
                float midTime = tPrev + j;
                allTimes.insert(allTimes.indexOf(tCurr), midTime); // 插入到当前时间点前
            }
        }
    }

    // 2. 构建数据模型（包含原始业务和间隔业务）
    int totalBizCount = businessNumber + 1; // 原有业务数 + 1个间隔业务（-1）
    QMap<float, QVector<float>> timePointData; // 时间点 → [业务0, 业务1, ..., 间隔业务-1]

    // 初始化所有时间点的数据（所有业务工作量为0）
    for (float t : allTimes) {
        timePointData[t] = QVector<float>(totalBizCount, 0.0f);
    }

    // 填充原有业务的数据
    for (int bizIdx = 0; bizIdx < businessNumber; ++bizIdx) {
        std::queue<TimeSlice> tempQueue = copiedBusiness[bizIdx].timeSlice;
        while (!tempQueue.empty()) {
            const TimeSlice& ts = tempQueue.front();
            float arriveTime = ts.arriveTime;
            if (timePointData.contains(arriveTime)) {
                timePointData[arriveTime][bizIdx] += ts.workLoad; // 原有业务数据
            }
            tempQueue.pop();
        }
    }
    // 间隔业务（-1）的数据始终为0，无需额外处理

    // 3. 创建柱状图系列（包含原有业务和间隔业务）
    QBarSeries* series = new QBarSeries();
    series->setBarWidth(0.8);

    // 颜色配置（最后一个颜色用于间隔业务）
    QVector<QColor> colors = {
        Qt::red, Qt::green, Qt::blue, Qt::cyan, Qt::magenta,
        Qt::yellow, Qt::darkRed, Qt::darkGreen, Qt::darkBlue, Qt::gray,
        Qt::lightGray // 间隔业务的颜色（淡灰色，区分原有业务）
    };

    // 创建原有业务的柱条集
    for (int bizIdx = 0; bizIdx < businessNumber; ++bizIdx) {
        QBarSet* barSet = new QBarSet(QString("业务%1").arg(bizIdx + 1));
        barSet->setColor(colors[bizIdx % (colors.size() - 1)]); // 留最后一个颜色给间隔业务

        for (float t : allTimes) {
            barSet->append(timePointData[t][bizIdx]);
        }
        series->append(barSet);
    }

    // 创建间隔业务（-1）的柱条集（始终为0，作为间隔）
    QBarSet* intervalSet = new QBarSet("间隔");
    intervalSet->setColor(colors.last()); // 间隔业务颜色
    for (float t : allTimes) {
        intervalSet->append(timePointData[t][businessNumber]); // 间隔业务索引为businessNumber
    }
    series->append(intervalSet);

    // 4. 配置图表和坐标轴
    QChart* chart = new QChart();
    chart->addSeries(series);
    chart->setTitle("各业务到达任务量柱状图（含间隔）");
    chart->setAnimationOptions(QChart::SeriesAnimations);

    // X轴（显示所有时间点）
    QBarCategoryAxis* axisX = new QBarCategoryAxis();
    QStringList xLabels;
    for (float t : allTimes) {
        xLabels.append(QString::number(t, 'f', 1));
    }
    axisX->append(xLabels);
    axisX->setTitleText("时间");
    chart->addAxis(axisX, Qt::AlignBottom);
    series->attachAxis(axisX);

    // Y轴
    QValueAxis* axisY = new QValueAxis();
    float yEnd = qMax(1.0f, maxWorkLoad +1.0f);
    axisY->setRange(0, yEnd);
    axisY->setTickInterval(1.0);
    axisY->setMinorTickCount(9);
    axisY->setLabelFormat("%.1f");
    axisY->setTitleText("任务量");
    chart->addAxis(axisY, Qt::AlignLeft);
    series->attachAxis(axisY);

    // 图例和布局
    chart->legend()->setVisible(true);
    chart->legend()->setAlignment(Qt::AlignBottom);

    // 显示图表
    while (QLayoutItem* item = ui->verticalLayoutBar->takeAt(0)) {
        if (item->widget()) item->widget()->deleteLater();
        delete item;
    }
    QChartView* chartView = new QChartView(chart);
    chartView->setRenderHint(QPainter::Antialiasing);
    // chartView->setMinimumSize(800, 500);
    ui->verticalLayoutBar->addWidget(chartView);
}

折线图绘制

折线图绘制是重头戏，需要调用计时器生成时间值，然后每段时间调用一下GPS()和WFQ()计算一下当前业务执行完成的工作量。

初始化图表

画图前先定义好坐标的范围、颜色等。关键点为：

• 重置时间计数为 0
• 深度拷贝业务数据到 GPS 和 WFQ 算法的业务数组
• 创建两个图表，分别用于显示 GPS 和 WFQ 算法的执行情况
• 为每个业务创建初始折线，起点为 (0,0)
• 配置图表的坐标轴和样式
• 将图表设置到对应的 GraphicsView 控件中

代码如下：

// 初始化图表
void Widget::initCharts()
{
    // 解析业务数据（保持不变）
    parseBusinessData();
    // 重置时间计数
    timeCount = 0.0f;

    qDebug()<<"初始化折线图";
    // 深度拷贝业务数据（保持不变）
    for (int i = 0; i < businessNumber; ++i) {
        GPSbusiness[i] = createDeepCopy(business[i]);
        WFQbusiness[i] = createDeepCopy(business[i]);
    }

    // 创建GPS和WFQ图表（保持不变）
    QChart *chartGps = new QChart();
    chartGps->setTitle("GPS算法执行情况");
    chartGps->legend()->setVisible(true);
    chartGps->legend()->setAlignment(Qt::AlignBottom);

    QChart *chartWfq = new QChart();
    chartWfq->setTitle("WFQ算法执行情况");
    chartWfq->legend()->setVisible(true);
    chartWfq->legend()->setAlignment(Qt::AlignBottom);

    // 定义折线颜色（可根据需要调整）
    QVector<QColor> lineColors = {
        Qt::red, Qt::green, Qt::blue, Qt::cyan, Qt::magenta,
        Qt::yellow, Qt::darkRed, Qt::darkGreen, Qt::darkBlue, Qt::darkGray
    };

    // 为每个业务创建初始折线，并设置颜色
    for (int i = 0; i < businessNumber; ++i) {
        // GPS算法折线
        QLineSeries *seriesGps = new QLineSeries();
        seriesGps->setName(QString("业务%1").arg(i + 1));
        seriesGps->append(0, 0);

        // 设置折线颜色和样式
        QPen pen(lineColors[i % lineColors.size()]);
        pen.setWidth(2); // 设置线宽
        seriesGps->setPen(pen);

        chartGps->addSeries(seriesGps);
        gpsSeries[i] = seriesGps;

        // WFQ算法折线
        QLineSeries *seriesWfq = new QLineSeries();
        seriesWfq->setName(QString("业务%1").arg(i + 1));
        seriesWfq->append(0, 0);

        // 设置折线颜色和样式（与GPS算法的同业务使用相同颜色）
        QPen wfqPen(lineColors[i % lineColors.size()]);
        wfqPen.setWidth(2);
        wfqPen.setStyle(Qt::DashLine); // 使用虚线样式区分不同算法
        seriesWfq->setPen(wfqPen);

        chartWfq->addSeries(seriesWfq);
        wfqSeries[i] = seriesWfq;
    }
    // 配置GPS图表X轴（核心修改）
    QValueAxis *axisXGps = new QValueAxis();
    axisXGps->setRange(0, 16);          // 初始范围0-10
    axisXGps->setTickInterval(1.0);     // 主刻度间隔1.0
    axisXGps->setMinorTickCount(3);     // 小刻度数量9（1/0.1=10个间隔，需9个小刻度）
    axisXGps->setLabelFormat("%.1f");   // 精度0.1（显示如0.0,1.0,2.0）
    axisXGps->setGridLineVisible(true); // 主网格线可见
    axisXGps->setMinorGridLineVisible(true); // 小网格线可见（0.1分度）
    axisXGps->setTitleText("时间");
    chartGps->addAxis(axisXGps, Qt::AlignBottom);

    // GPS图表Y轴（核心修改）
    QValueAxis *axisYGps = new QValueAxis();
    axisYGps->setRange(0, 8);           // 初始范围0-5
    axisYGps->setTickInterval(1.0);     // 主刻度间隔1.0
    axisYGps->setMinorTickCount(1);     // 小刻度数量9
    axisYGps->setLabelFormat("%.1f");   // 精度0.1
    axisYGps->setGridLineVisible(true);
    axisYGps->setMinorGridLineVisible(true);
    axisYGps->setTitleText("完成度");
    chartGps->addAxis(axisYGps, Qt::AlignLeft);

    // 配置WFQ图表X轴（同GPS，核心修改）
    QValueAxis *axisXWfq = new QValueAxis();
    axisXWfq->setRange(0, 16);
    axisXWfq->setTickInterval(1.0);
    axisXWfq->setMinorTickCount(3);
    axisXWfq->setLabelFormat("%.1f");
    axisXWfq->setGridLineVisible(true);
    axisXWfq->setMinorGridLineVisible(true);
    axisXWfq->setTitleText("时间");
    chartWfq->addAxis(axisXWfq, Qt::AlignBottom);

    // WFQ图表Y轴（同GPS，核心修改）
    QValueAxis *axisYWfq = new QValueAxis();
    axisYWfq->setRange(0, 8);
    axisYWfq->setTickInterval(1.0);
    axisYWfq->setMinorTickCount(1);
    axisYWfq->setLabelFormat("%.1f");
    axisYWfq->setGridLineVisible(true);
    axisYWfq->setMinorGridLineVisible(true);
    axisYWfq->setTitleText("完成度");
    chartWfq->addAxis(axisYWfq, Qt::AlignLeft);

    // 关联系列与坐标轴（保持不变）
    for (int i = 0; i < businessNumber; ++i) {
        gpsSeries[i]->attachAxis(axisXGps);
        gpsSeries[i]->attachAxis(axisYGps);
        wfqSeries[i]->attachAxis(axisXWfq);
        wfqSeries[i]->attachAxis(axisYWfq);
    }

    // 创建图表视图（保持不变）
    QChartView *chartViewGps = new QChartView(chartGps);
    chartViewGps->setRenderHint(QPainter::Antialiasing);
    ui->graphicsViewGps->setChart(chartGps);
    ui->graphicsViewGps->setRenderHint(QPainter::Antialiasing);

    QChartView *chartViewWfq = new QChartView(chartWfq);
    chartViewWfq->setRenderHint(QPainter::Antialiasing);
    ui->graphicsViewWfq->setChart(chartWfq);
    ui->graphicsViewWfq->setRenderHint(QPainter::Antialiasing);

    // 清空数据（保持不变）
    gpsData.clear();
    wfqData.clear();
}

更新图表

每次计时都要更新一次图表，将当前时间带入GPS()和WFQ()中计算得出当前完成的工作量，要点有：

• 每次调用时增加时间计数（0.1 秒）
• 动态分配数组存储 GPS 和 WFQ 算法的计算结果
• 调用 GPS 和 WFQ 算法处理业务数据
• 将新的数据点添加到对应的折线系列中
• 根据数据动态调整坐标轴范围，确保图表显示完整
• 释放动态分配的内存

代码如下：

//更新图表
void Widget::updateCharts()
{
    // 增加时间计数（保持不变）
    timeCount += 0.01f;

    // 动态分配数组（保持不变）
    float *yGPS = new float[businessNumber]();
    float *yWFQ = new float[businessNumber]();

    // 调用调度算法（保持不变）
    int ctGps = GPS(GPSbusiness, timeCount, businessNumber, yGPS, otherWeight);
    int ctWfq = WFQ(WFQbusiness, timeCount, businessNumber, yWFQ);

    // 输出调试信息（保持不变）
    qDebug() << "GPS y值：";
    for (int i=0; i<businessNumber; i++) {
        qDebug() << yGPS[i];
    }
    qDebug() <<"timeCount"<< timeCount;
    qDebug() <<"otherWeight"<< otherWeight;

    // 更新GPS图表数据点（保持不变）
    for (int i = 0; i < businessNumber; ++i) {
        gpsSeries[i]->append(timeCount, yGPS[i]);
    }

    // 更新WFQ图表数据点（保持不变）
    for (int i = 0; i < businessNumber; ++i) {
        wfqSeries[i]->append(timeCount, yWFQ[i]);
    }

    // 动态调整GPS坐标轴范围（核心修改：保持间隔1.0和精度0.1）
    QValueAxis *axisXGps = qobject_cast<QValueAxis*>(gpsSeries[0]->chart()->axisX());
    QValueAxis *axisYGps = qobject_cast<QValueAxis*>(gpsSeries[0]->chart()->axisY());
    if (axisXGps && timeCount > axisXGps->max()) {
        axisXGps->setRange(0, timeCount + 1.0); // 扩展范围时多留1.0余量
        axisXGps->setTickInterval(1.0);         // 保持主刻度间隔1.0
        axisXGps->setMinorTickCount(9);         // 保持小刻度
        axisXGps->setLabelFormat("%.1f");       // 保持精度
    }
    if (axisYGps) {
        float maxY = *std::max_element(yGPS, yGPS + businessNumber);
        if (maxY > axisYGps->max()) {
            axisYGps->setRange(0, maxY + 1.0);  // 扩展Y轴范围
            axisYGps->setTickInterval(1.0);
            axisYGps->setMinorTickCount(9);
            axisYGps->setLabelFormat("%.1f");
        }
    }

    // 动态调整WFQ坐标轴范围（同GPS，核心修改）
    QValueAxis *axisXWfq = qobject_cast<QValueAxis*>(wfqSeries[0]->chart()->axisX());
    QValueAxis *axisYWfq = qobject_cast<QValueAxis*>(wfqSeries[0]->chart()->axisY());
    if (axisXWfq && timeCount > axisXWfq->max()) {
        axisXWfq->setRange(0, timeCount + 1.0);
        axisXWfq->setTickInterval(1.0);
        axisXWfq->setMinorTickCount(9);
        axisXWfq->setLabelFormat("%.1f");
    }
    if (axisYWfq) {
        float maxY = *std::max_element(yWFQ, yWFQ + businessNumber);
        if (maxY > axisYWfq->max()) {
            axisYWfq->setRange(0, maxY + 1.0);
            axisYWfq->setTickInterval(1.0);
            axisYWfq->setMinorTickCount(9);
            axisYWfq->setLabelFormat("%.1f");
        }
    }

    // 释放内存（保持不变）
    delete[] yGPS;
    delete[] yWFQ;

    // 停止条件（保持不变）
    if(ctGps==0)    gpsCounts++;
    if(ctWfq==0)    wfqCounts++;
    if(gpsCounts>=150&&wfqCounts>=150)  timer->stop();
}

图表绘制按钮事件

第一次点击后将生成动态更新的图像，再次点击会暂停生成，如果再次点击将会重新开始模拟。

// 按钮点击事件
void Widget::on_pushButtonLineChart_clicked()
{
    if (isSimulationRunning) {
        // 停止模拟
        timer->stop();
        isSimulationRunning = false;
        ui->pushButtonLineChart->setText("开始模拟");
        qDebug() << "计时器已停止";
    }
    else {
        // 开始新模拟
        if (parseBusinessData()) {
            initCharts();
            gpsCounts=0;
            otherWeight = 0;
            wfqCounts=0;
            timer->start(10); // 每100ms更新一次
            isSimulationRunning = true;
            ui->pushButtonLineChart->setText("停止模拟");
            qDebug() << "计时器已启动，间隔:" << timer->interval() << "ms";
        }
    }
}

测试情况

程序启动默认的输入即为书本上的样例。

将完整生成的图像与书本对比：

权重1:1的情况：

权重1:2的情况：

多业务（3个）的执行情况：

总结

首先非常感谢李老师这学期通信网课程的传授，我在学习过程中发现更操作系统的部分知识比较相似，虽然本人愚钝，部分公式可能没有掌握透，但不妨碍我对于通信专业、甚至是信息科学整个的认知提升，这很大程度上归功于老师上课时发散思维的讲解。同时也非常感谢我的导师杨老师能给学生在工作之余一定的自由空间学习自己感兴趣的技术。接下来两年希望能有更多的突破来回馈大家。

声明：以下部分由AI总结，我累了😭。提示词已在文末的图片给出。

时光荏苒，通信网这门课程已然成为我研究生阶段课程学习生涯的终章。在这充实且富有挑战的学习过程中，每一个知识点、每一次编程实践都如同繁星，点缀着我在通信领域探索的漫漫征途。

通过本次作业，我深入研究并实现了GPS和WFQ调度算法。从算法原理的学习到C++代码的编写，再到使用Qt进行可视化展示，每一步都凝聚着我的心血与汗水。在理解GPS调度算法的精确资源分配和WFQ调度算法的实际应用时，我不断查阅资料，努力攻克一个又一个难关。在编写代码的过程中，我遭遇了诸多棘手的问题，如权重变换导致的数据错误、业务饥饿问题等，但我始终没有放弃，通过反复调试和优化，最终让代码顺利运行，看到测试结果与预期相符的那一刻，所有的疲惫都烟消云散。

在使用Qt进行可视化的环节，我深刻体会到理论与实践相结合的重要性。正则表达式的运用、柱状图和折线图的绘制，不仅让我对算法的执行过程有了更直观的认识，也提升了我的编程能力和解决实际问题的能力。当我看到自己输入的数据被准确解析并以清晰美观的图表形式呈现出来时，内心充满了成就感。 这段时间的学习，不仅让我掌握了通信网中的调度算法，更培养了我独立思考、勇于探索的精神。我深知，通信技术在当今社会发展中起着至关重要的作用，而我所学到的知识仅仅是冰山一角。未来，我将带着这份对知识的热爱和对技术的追求，不断学习和进步，为通信领域的发展贡献自己的一份力量。

（🫡有请豆包发言）作为一个AI，我见证了你在这次作业中付出的努力和坚持。从算法的学习到代码的实现，再到可视化的呈现，每一个环节都需要严谨的逻辑和不懈的努力。你在面对困难时的执着和勇于挑战的精神令人钦佩。在这个信息爆炸的时代，知识的更新换代日新月异，持续学习和不断实践是保持竞争力的关键。希望你能将在这次作业中所学到的知识和技能运用到未来的工作和学习中，不断追求卓越，创造出更加美好的未来。