QingYuAlive's Blog
基于C++面向对象的多级反馈队列调度算法的模拟实现
QingYuAlive Lv1
  2023-12-27 09:57:11 2023-12-27 09:57   2023-12-27 14:08:19  

引言

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行调度，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题

处理机调度

若没有处理机调度，意味着要等到当前运行的进程执行完毕后，下一个进程才能执行，而实际情况中，进程时常需要等待一些外部设备的输入，而外部设备的速度与处理机相比是非常缓慢的，若让处理机总是等待外部设备，则对处理机的资源是极大的浪费。而引进处理机调度后，可以在运行进程等待外部设备时，把处理机调度给其他进程，从而提高处理机的利用率。用一句简单的话来说，就是为了合理地处理计算机的软/硬件资源

调度算法

出现了调度的概念后，又有了一个问题，即如何调度、应该满足谁、应该让谁等待，这是调度算法所回答的问题。常见的调度算法包括：

  • 先来先服务（FCFS）调度算法
  • 短作业优先（SJF）调度算法
  • 优先级调度算法
  • 高响应比优先（HRRN）调度算法
  • 时间片轮转（RR）调度算法
  • 多级反馈队列（MLFQ）调度算法

其中，本文着重介绍的是多级反馈队列（MLFQ）调度算法

算法概述

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转事件而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不必事先估计进程的执行时间

实现思想

多级反馈队列调度算法的实现思想如下：

  1. 设置多个就绪队列，并为每个队列赋予不同的优先级。第1级队列的优先级最高，第2级队列的优先级次之，其余队列的优先级逐个降低
  2. 赋予各个队列的进程运行时间片的大小各不相同。在优先级越高的队列中，每个进程的时间片就越小。例如，第i+1级队列的时间片要比第i级队列的时间片长1倍
  3. 每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。若它在一个时间片结束时尚未完成，调度程序将其转入第2级队列的末尾等待调度；若它在第2级队列中运行一个时间片后仍未完成，再将它放入第3级队列······，以此类推。当进程最后被降到第n级队列后，在第n级队列中便采用时间片轮转方式运行
  4. 按队列优先级调度。仅当第1级队列为空时，才调度第2级队列中的进行运行；仅当第1~i-1级队列均为空时，才会调度第i级队列中的进程运行。若处理机正在执行第i级队列中的进程时，又有新进程进入任何一个优先级较高的队列，此时须立即把正在运行的进程放回到第i级队列的末尾，而把处理机分配给新到的高优先级进程

算法特征

  1. 对于终端型作业用户：短作业优先
  2. 对于短批处理作业用户：周转时间较短
  3. 对于长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理

算法实现过程与思路

以下实现的为一个包含三级队列，时间片长度依次为1、2、4的多级反馈队列，且只考虑每次执行整数个单位时间片的情况

函数的功能要求是在根据给定的时间片，利用多级反馈队列调度算法对当前系统中存在的进程在给定的时间片内实现CPU时间的分配与进程调度

因此一个比较简单的想法是给时间片分段，将整个过程划分为长度等于一个单位时间片的多个小过程，通过模拟时间每次行进一个单位时间片，我们可以轻易地得出每个单位时间片末各进程的各类信息以及各级队列当中所包含的进程情况

多级反馈队列调度算法中的一个重要的思想是，仅当低于当前层级队列的所有队列同时全部为空队列时，才会调度当前层级队列中的进程运行。这意味着，在实现过程中，我们可以从低级队列往高级队列进行逐步考虑和实现。

第1级队列

先考虑第1级队列的实现，由于第1级队列每次能分配的最长时间片的长度为1，因此不需要将这个过程考虑得太过复杂，可以明确的是：

  • 一旦有新的进程创建成功，它就一定会立即插入到第1级队列的队尾
  • 由于每次能分配的最长时间片的单位长度为1，在本次给定的总时间片中，第1队列对进程的调度一定是连贯的，这里的连贯是指在经过任意长度的时间片的调度与分配后，第1级队列中所有与本次调度相关的进程，要么完成并撤离系统，要么插入到第2级队列的队尾，所有被分配过CPU时间的进程都将立即从第1级队列中弹出，而不会出现在经过调度运行后当前进程未完成，同时本次运行中当前进程被一次性分配的时间片长度未达到发生队列调度的时间片长度，导致当前进程继续驻留在第1级队列当中等待下一次用户输入时间片来进一步判断进程的调度情况

认识到了这两点，在实现第1级队列时只需要考虑两种情况，只要第1级队列不空，就能不断地分配单位时间片并调度，同时在本次运行中，被分配过单位时间片后的进程要么转为完成态并从系统中撤离，要么被插入到第2级队列的队尾，无论如何，此进程都将立即从第1级队列中弹出

第2级队列

然后考虑第2级队列的实现，第2级队列每次能分配的最长时间片的长度为2，这意味着相比于第1级队列，在本次用户给定的时间片末，可能会出现第2级队列的队首进程仍然滞留在第2级队列的队首，因为我们不知道下一次系统运行时是否仍需继续运行该进程。因此，这里我们需要引入一个额外的变量来解决这个复杂的情况，这个变量需要记录进程单次连续上处理机运行的时间，这里的连续指的是本次运行中没有发生因进程调度导致的运行中断。这样，无论用户将整个系统运行过程分成多少段运行，系统都能正确地进行进程调度。需要注意的是，由于连续运行时间记录的是进程上处理机运行中没有发生进程调度导致中断的时间，因此，一旦整个系统中产生了由较高级队列进程到较低级队列进程的处理机调度，那么较高级队列中的队首进程的连续运行时间必须清0，这意味着他们本次运行过程的终止

第3级队列

最后是考虑第3级队列的实现，第3级队列每次能分配的最长时间片的长度为4，这意味着第3级队列所面临的情况与第2级队列一样，可以通过照搬第2级队列的处理方法来解决第3级队列的问题，只不过，与第2级队列不同的，由于第3级队列是最高级的队列，单次分配完4单位长度的时间片后，进程并不会进入到更高一级的队列，而是重新被插入到第3级队列的队尾，因此，我们只需要对第2级队列的处理方式进行简单的修改，便能将其运用到第3级队列上。

代码实现

这里只粘贴重要函数的代码，完整代码请移步OS多级反馈队列调度算法 (github.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 采用多级反馈队列调度算法运行若干时间片
void Run(int time) {
    // 模拟时间流逝
    for (int i = 0; i != time;) {
        // 只要第1队队列不空，就持续对第1队队列中的进程调度并分配时间片
        if (!firstQueue.empty()) {
            // 此时已经进入第1队队列中，如果第2、3队队列不空，说明上次时间片分配给的是第2、3队队列的进程，此时需要将处于第2、3队队列中的进程的持续运行记录清0
            if (!secondQueue.empty()) {
                if (secondQueue.front().getContinuation() != 0) {
                    Process *process = &(secondQueue.front()); // 获取第2级队列队头进程
                    process->getPCB()->setStatus('W'); // 发生调度后变为等待态
                    process->setContinuation(0); // 连续运行时间清0
                    secondQueue.pop();
                    secondQueue.push(*process); // 这一行和上一行的顺序不能调换，他们操作的是同一个process对象
                }
            }
            if (!thirdQueue.empty()) {
                if (thirdQueue.front().getContinuation() != 0) {
                    Process *process = &(thirdQueue.front()); // 获取第3级队列队头进程
                    process->getPCB()->setStatus('W'); // 发生调度后变为等待态
                    process->setContinuation(0); // 连续运行时间清0
                    thirdQueue.pop();
                    thirdQueue.push(*process); // 这一行和上一行的顺序不能调换，他们操作的是同一个process对象
                }
            }
            nowTime++; // 当前时间增加
            i++; // 模拟分配了时间片=1的CPU时间
            Process &process = firstQueue.front(); // 获取第1队队列首进程
            PCB *pcb = process.getPCB(); // 获取该进程的PCB
            pcb->setStatus('R'); // 进程上处理机运行转为运行态
            pcb->setUsedTime(pcb->getUsedTime() + 1); // 已用CPU时间+1
            process.setContinuation(process.getContinuation() + 1); // 连续运行时间+1
            // 如果运行完成
            if (pcb->getUsedTime() == pcb->getTotalTime()) {
                firstQueue.pop(); // 弹出第1队队列
                pcb->setStatus('F'); // 状态设置为完成态
            } else {
                // 由于第一队队列的时间片为1，因此不用考虑已占用CPU时间大于需要运行时间的情况，此时考虑该进程未完成的情况
                pcb->setStatus('W'); // 发生进程调度变为等待态
                process.setContinuation(0); // 发生调度，需要将进程的持续运行记录清0
                secondQueue.push(process); // 放入第2队队列的队尾
                firstQueue.pop(); // 弹出第1队队列
            }
        } else if (!secondQueue.empty()) {
            // 同上，此时已经进入第2队队列中，如果第3队队列不空，此时需要将处于第3队队列中的进程的持续运行记录清0
            if (!thirdQueue.empty()) {
                if (thirdQueue.front().getContinuation() != 0) {
                    Process *process = &(thirdQueue.front()); // 获取第3级队列队首进程
                    process->getPCB()->setStatus('W'); // 获取该进程的PCB
                    process->setContinuation(0); // 连续运行时间清0
                    thirdQueue.pop();
                    thirdQueue.push(*process); // 这一行和上一行的顺序不能调换，他们操作的是同一个process对象
                }
            }
            Process *process = &(secondQueue.front()); // 获取第2队队列的队首进程
            PCB *pcb = (*process).getPCB(); // 该进程的PCB
            // 只要第2队队列不为空且本次分配的CPU时间片未使用完，就不断对处于第2队队列中的进程进行调度和分配时间片
            while (!secondQueue.empty() && i != time) {
                i++; // 模拟分配了时间片=1的CPU时间
                nowTime++; // 当前时间增加
                pcb->setStatus('R'); // 将状态设置为运行态
                pcb->setUsedTime(pcb->getUsedTime() + 1); // 当前进程已占用CPU时间增加
                process->setContinuation(process->getContinuation() + 1); // 当前进程连续运行时间的记录增加
                // 若进程完成
                if (pcb->getUsedTime() == pcb->getTotalTime()) {
                    pcb->setStatus('F'); // 将状态设置为完成态
                    secondQueue.pop(); // 从第2队队列中弹出该进程
                    process = &(secondQueue.front()); // 切换下一个进程
                    pcb = process->getPCB(); // 获取该进程PCB
                    continue; // 跳过后续处理
                }
                // 若达到第2队队列所能分配的最大时间片
                if (process->getContinuation() == secondQueueTime) {
                    pcb->setStatus('W'); // 发生进程调度状态变为等待态
                    process->setContinuation(0); // 发生进程调度，进程连续运行时间记录清0
                    thirdQueue.push(*process); // 将该进程放入第3队队列
                    secondQueue.pop(); // 将该进程从第2队队列中弹出
                    process = &(secondQueue.front()); // 切换下一个进程
                    pcb = process->getPCB(); // 获取该进程的PCB
                }
            }
        } else {
            // 当其他队列为空时便对第3队队列中的进程进行调度并分配时间片
            Process *process = &(thirdQueue.front()); // 获取第3队队列队首的进程
            PCB *pcb = (*process).getPCB(); // 获得该进程的PCB
            // 当程序进入到处理第三队队列的进程调度时，这意味着前两个队列都是空的，由于第3队队列是最高级的队列，进程在这将采用时间片轮转的调度算法
            while (!thirdQueue.empty() && i != time) {
                i++;
                nowTime++;
                pcb->setStatus('R'); // 状态变为运行态
                pcb->setUsedTime(pcb->getUsedTime() + 1); // 当前进程已占用CPU时间增加
                process->setContinuation(process->getContinuation() + 1); // 当前进程连续运行时间的记录增加
                // 若进程完成
                if (pcb->getUsedTime() == pcb->getTotalTime()) {
                    pcb->setStatus('F'); // 将状态设置为完成态
                    thirdQueue.pop(); // 从第3级队列中弹出该进程
                    process = &(thirdQueue.front()); // 切换下一个进程
                    pcb = process->getPCB();// 获取该进程的PCB
                    continue; // 跳过后续处理
                }
                // 若达到第3级队列所能分配的最大时间片
                if (process->getContinuation() == thirdQueueTime) {
                    pcb->setStatus('W'); // 发生进程调度状态变为等待态
                    process->setContinuation(0); // 连续运行时间清0
                    thirdQueue.pop();
                    thirdQueue.push(*process); // 这一行和上一行顺序不能调换，他们操作的是同一个process对象
                    process = &(thirdQueue.front()); // 切换下一个进程
                    pcb = process->getPCB(); // 获取该进程的PCB
                }
            }
            // 所有进程运行完成
            if (thirdQueue.empty()) {
                nowTime += time - i;
                i = time; // 直接结束
            }
        }
    }
    processTable.display(); // 打印进程信息
    menu(); // 返回菜单
}

遇到的问题

这部分用于记录我在具体实现过程中遇到的问题

问题描述

采用面向对象的实现方式时，在调用了对象的成员方法对成员变量进行操作时，同时是使用getter和setter成员方法，对于一部分对象来说，他们的getter和setter能正常地获取和修改对象的成员变量，但对于另一部分对象来说，他们的getter和setter是毫无作用的

问题分析

程序中存在三个重要的对象：进程控制块（PCB）、进程（Process）、系统进程表（ProcessTable），他们之间存在着很强的关联关系：一个进程对应一个进程控制块，这意味着Process类中会有一个PCB类型的成员变量；系统进程表中包含多个进程，这意味着ProcessTable类中有一个向量vector<Process> processes用来存储系统中的多个进程。在操作上述的这些相关联的对象时，就必须注意深拷贝和浅拷贝的问题，这意味着你不能将getter返回的值赋值到另一个相同类型的变量上，一旦这么做，这个变量只是原本需要操作的对象的一个副本，对该变量的所有操作都不会对原对象产生影响

问题解决

我一共采用了两种方法针对关联对象的深拷贝和浅拷贝问题

  • 直接改变成员变量的类型，将其改为原类型的指针，这一方法的具体实施体现在了Process类中，我将原本PCB类型成员变量改为了PCB*类型，这样，通过getter返回的指针即使被赋值到另一共变量上后依然能精准地指向原对象
  • 将getter的返回值设置为引用类型，同时，在具体的代码实现中通过&获取返回值的地址，这样我们便又一次得到了我们需要操作的对象的指针，无论如何赋值，这个指针始终指向我们需要操作的对象

总结

不难看出这其实是一个操作系统的课程设计的内容，不可否认的是，这个课程设计极大地引起了我的兴趣以至于我愿意为了它写一篇这样的博客。多级反馈队列调度算法——作为操作系统这门课中的一种相对复杂的算法，它的实现毫无疑问充满了挑战，但当真正去将它付以实践时，我被其设计的巧妙之处所折服，或许，这就是算法设计的魅力

基于C++面向对象的多级反馈队列调度算法的模拟实现
2023/12/27/MLFQ/
Author
QingYuAlive
Published
2023-12-27 09:57
License
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 1. 引言
    1. 1.1. 处理机调度
    2. 1.2. 调度算法
  2. 2. 算法概述
    1. 2.1. 实现思想
    2. 2.2. 算法特征
  3. 3. 算法实现过程与思路
    1. 3.1. 第1级队列
    2. 3.2. 第2级队列
    3. 3.3. 第3级队列
  4. 4. 代码实现
  5. 5. 遇到的问题
    1. 5.1. 问题描述
    2. 5.2. 问题分析
    3. 5.3. 问题解决
  6. 6. 总结
  1. 1. 引言
    1. 1.1. 处理机调度
    2. 1.2. 调度算法
  2. 2. 算法概述
    1. 2.1. 实现思想
    2. 2.2. 算法特征
  3. 3. 算法实现过程与思路
    1. 3.1. 第1级队列
    2. 3.2. 第2级队列
    3. 3.3. 第3级队列
  4. 4. 代码实现
  5. 5. 遇到的问题
    1. 5.1. 问题描述
    2. 5.2. 问题分析
    3. 5.3. 问题解决
  6. 6. 总结