进程调度算法之优先数法 C++ 简单实现

前言

其实是《操作系统》课程的一个实验，一开始花了些时间实现了基本功能，但是后面经同学提醒，发现还存在一些逻辑问题，于是又进行了一番“修补”，勉强修复了bug，当然它还有一些别的问题。

---

算法介绍

优先数法：进程就绪队列按优先数大小从高到低排列，队首进程首先投入运行。每过一个时间片，运行进程所需时间片减1，优先数减3，说明它已运行一个时间片，如果在一个时间片内完成不了，应降低其优先数。接着比较现行进程和就绪队列队首进程的优先数，如果仍是现行进程优先数高或者相同，就让现行进程继续运行，否则，调度就绪队列队首进程投入运行。原运行进程再按优先数大小插入就绪队列，且改变它们对应进程的状态，直至所有进程都运行完各自的时间片数。

---

实验设计

设计一个有6个进程并发运行的模拟进程调度程序，每个进程由一个进程控制块(PCB)标志（进程标识号、优先数、占用CPU时间片数、进程所需时间片数、进程状态），每个进程处于运行(run)、就绪(ready)、阻塞(blocked)和完成(finish)状态之一。显示打印进程状态参数变化情况。

---

代码说明

简单点说，其实就是维护一个按优先数从大到小排列的优先队列，实时更新每个线程的优先度。但是，更关键的是阻塞状态的处理，当进程由就绪状态进入阻塞状态时，它不会占用CPU时间片数，也不会降低优先数，所以可以随机产生一个“阻塞等待时间”，当该进程在阻塞状态的时间达到“阻塞等待时间”时，便由阻塞状态进入就绪状态等待执行。

程序分为初始化（输入数据）、算法模拟、输出三大模块，核心就是处理就绪队列readyQueue、运行队列runQueue、阻塞队列blockQueue、完成队列finishQueue四个队列的相互转化。

• PCB结构体

比较重要的就是构造函数和重载<按优先数从大到小输出。

• init()初始化

就是把队列清空以及需要使用的数组清零然后随机生成数据。

• Priority()算法

所有程序执行结束的条件是就绪队列和阻塞队列均为空。取出队首进程后，可能随机进入阻塞状态或者运行状态，常规处理即可。关键是每次出队入队的过程中，需要对阻塞队列进行遍历，判断每一个处于阻塞状态的进程 的blockTime，如果block.blockTime > randomBlockTime[block.processId]，那么进入就绪队列，否则时间加1后仍处于阻塞状态。

• display()显示输出

除了加setw()控制一下输出宽度外没啥好说的，其实可以在结构体里边重载>>。

---

具体实现

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <queue>
#define IsRun 1 // 运行
#define isFinish 0 // 完成
#define isReady 2 // 就绪
#define isBlock -1 // 阻塞
using namespace std;
const int processNum = 110; // 进程数量110以内

int randomBlockTime[processNum]; // 随机等待时间
bool visBlock[processNum]; // 记录当前是否为阻塞状态

struct PCB // 进程控制块
{
    int processId; // 进程标识号
    int priority; // 优先级
    int cpuTime; // 进程占用CPU时间
    int needTime; // 进程执行所需时间
    int blockTime; // 阻塞时间
    int processState; // 进程状态

    PCB() {}

    // 自定义构造函数
    PCB(int pi, int p, int ct, int nt, int ps): processId(pi), priority(p), cpuTime(ct), needTime(nt), processState(ps) {}

    // 自定义构造函数
    PCB(bool isRand, int id)
    {
        if (isRand) // 随机
        {
            this->cpuTime = 0;
            this->blockTime = 0;
            this->needTime = rand() % 10 + 1;
            this->priority = rand() % 30 + 1;
            this->processState = isReady;
            this->processId = id;
        }
        else // 手动输入
        {
            cout << "Process ID: ";
            cin >> this->processId;
            cout << "Need Time: ";
            cin >> this->needTime;
            this->cpuTime = 0;
            this->blockTime = 0;
            this->priority = rand() % 30 + 1;
            this->processState = isReady;
        }
    }

    // 重载<，按优先数从大到小输出
    bool operator < (const PCB & r) const
    {
        return priority < r.priority;
    }
}pcb[processNum];

string statue_to_str(int statue) //  将进程状态转化为字符
{
    string str;
    if (statue == 1) // 对应状态
        str = "run   ";
    else if (statue == 0)
        str = "finish";
    else if (statue == 2)
        str = "ready ";
    else if (statue == -1)
        str = "block ";
    return str;
}

priority_queue <PCB> runQueue, readyQueue, blockQueue, finishQueue; // 运行队列， 就绪队列， 阻塞队列， 完成队列

void init(int processCnt, bool isRandom) // 初始化进程, 默认为随机
{
    srand((unsigned)time(NULL)); // 设置随机数种子

    memset(randomBlockTime, 0, sizeof(randomBlockTime));
    memset(visBlock, false, sizeof(visBlock)); // 默认为flase

    while (!runQueue.empty()) // 清空队列
        runQueue.pop();
    while (!readyQueue.empty())
        readyQueue.pop();
    while (!blockQueue.empty())
        blockQueue.pop();
    while (!finishQueue.empty())
        finishQueue.pop();

    for (int i = 1; i <= processCnt; ++i) // 生成数据
        pcb[i] = PCB(isRandom, i);

    for (int i = 1; i <= processCnt; ++i) // 初始程序加入就绪队列
        readyQueue.push(pcb[i]);

}

void display() // 输出
{
    priority_queue <PCB> _readyQueue = readyQueue;
    priority_queue <PCB> _runQueue = runQueue;
    priority_queue <PCB> _blockQueue = blockQueue;
    priority_queue <PCB> _finishQueue = finishQueue;

    cout << "ProcessId    |    " << "Priority    |    " << "ProcessState    |    " << "CPUTime    |    " << "NeedTime    |    " << "BlockTime" <<  endl;

    while (!_runQueue.empty()) // 运行队列
    {
        PCB now = _runQueue.top();
        cout << setw(5) << now.processId  << setw(16) << now.priority << setw(20) << statue_to_str(now.processState) << setw(18) << now.cpuTime << setw(17) << now.needTime << setw(17) << now.blockTime << endl;
        _runQueue.pop();
    }

    while (!_blockQueue.empty()) // 阻塞队列
    {
        PCB now = _blockQueue.top();
        cout << setw(5) << now.processId  << setw(16) << now.priority << setw(20) << statue_to_str(now.processState) << setw(18) << now.cpuTime << setw(17) << now.needTime << setw(17) << now.blockTime << endl;
        _blockQueue.pop();
    }

    while (!_readyQueue.empty()) // 就绪队列
    {
        PCB now = _readyQueue.top();
        cout << setw(5) << now.processId  << setw(16) << now.priority << setw(20) << statue_to_str(now.processState) << setw(18) << now.cpuTime << setw(17) << now.needTime << setw(17) << now.blockTime << endl;
        _readyQueue.pop();
    }

    while (!_finishQueue.empty()) // 完成队列
    {
        PCB now = _finishQueue.top();
        cout << setw(5) << now.processId  << setw(16) << now.priority << setw(20) << statue_to_str(now.processState) << setw(18) << now.cpuTime << setw(17) << now.needTime << setw(17) << now.blockTime << endl;
        _finishQueue.pop();
    }

    cout << "---------------------------------------------------------------------------------------------------" << endl;
}

void Priority(int processCnt, bool isRandom) // 优先数法
{
    init(processCnt, isRandom);

    cout << "-------------------------------------------Initial State-------------------------------------------" << endl;
    display(); // 初始等待状态

    cout << endl;

    int totalTime = 0; // 程序运行总时间

    cout << "-------------------------------------------Running State-------------------------------------------" << endl;
    priority_queue <PCB> _tmpblockQueue; // 使用_tmpblockQueue临时储存就绪队列进程信息
    while (!readyQueue.empty() || !blockQueue.empty()) // 程序执行
    {
        totalTime++;

        while (!_tmpblockQueue.empty())
            _tmpblockQueue.pop();

        while (!blockQueue.empty()) // 依次判断阻塞队列中的所有进程
        {
            PCB block = blockQueue.top();
            blockQueue.pop();
            if (block.blockTime > randomBlockTime[block.processId]) // 达到阻塞等待时间，退出
            {
                block.processState = isReady;
                block.blockTime = 0;
                visBlock[block.processId] = false; // 退出阻塞状态
                readyQueue.push(block);
            }
            else // 阻塞时间更新
            {
                block.blockTime++;
                _tmpblockQueue.push(block);
            }
        }

        while (!_tmpblockQueue.empty()) // “恢复信息”
        {
            blockQueue.push(_tmpblockQueue.top());
            _tmpblockQueue.pop();
        }

        if (readyQueue.empty()) // 当前就绪队列已经为空，则单独处理阻塞队列
        {
            display();
            continue;
        }

        PCB now = readyQueue.top();
        readyQueue.pop();

        if (rand() % 2 == 0 && !visBlock[now.processId]) // 当前程序未处于阻塞状态，随机进入
        {
            now.processState = isBlock;
            visBlock[now.processId] = true; // 标记处于阻塞状态
            now.blockTime++; // 阻塞时间
            randomBlockTime[now.processId] = rand() % 2 + 1;
            blockQueue.push(now); // 进入阻塞队列
            display();
            continue;
        }

        now.processState = IsRun;
        now.priority -= 3; // 优先数减3
        now.needTime -= 1; // 需要时间减1
        now.cpuTime += 1; // 运行时间加1
        runQueue.push(now);

        display();

        if (now.needTime > 0) // 执行所需时间大于0，进入就绪队列
        {
            now.processState = isReady;
            readyQueue.push(now);
        }
        else //  程序执行完成
        {
            now.processState = isFinish;
            finishQueue.push(now);
        }

        runQueue.pop();
    }

    cout << endl;

    cout << "-------------------------------------------Finished State------------------------------------------" << endl;
    display(); // 完成状态

    cout << "The total running time of all programs is: " << totalTime <<  "." << endl;
}

int main()
{
    char ch;
    cout << "Please choose whether to randomly generate data(y for yes, n for no): "; // 是否创建随机进程
    cin >> ch;
    int processCnt;
    bool isRandom;
    if (ch == 'y') // 随机
    {
        cout << "Please enter the number of random processes(1~100): ";
        cin >> processCnt;
        isRandom = true;
        //freopen("out.txt","w",stdout); // 输出到文件
        Priority(processCnt, isRandom);
    }
    else if (ch == 'n') // 非随机
    {
        cout << "Please enter the number of threads you need to create(1~100): ";
        cin >> processCnt;
        isRandom = false;
        cout << "Please enter the process ID and the corresponding running time." << endl;
        //freopen("out.txt","w",stdout); // 输出到文件
        Priority(processCnt, isRandom);
    }
    else
        cout << "Input errors, please input again." << endl;
    return 0;
}

---

效果演示

• 随机产生6组数据

• 手动输入

---

bug解决

• 可以多个程序处于阻塞状态，也可以一个程序多次进入阻塞状态，但是当某个程序正处于阻塞状态时它不能再次进入阻塞状态。我之前就出现了这个逻辑错误，然后使用visBlock数组记录当前进程是否为阻塞，其实根本不需要visBlock数组，因为进程本身就有一个状态信息，直接判断即可。
• 程序执行条件是while (!readyQueue.empty() || !blockQueue.empty())，但是当readyQueue为空blockQueue.empty()不为空单独处理阻塞状态时，我没有加判断，还使用PCB now = readyQueue.top();，所以运行时报错std::bad_alloc，网上查是什么内存空间不足的问题，不会改，睡一觉醒来才找到bug。
• 在对阻塞队列进行遍历时，我是取出队首元素后直接pop掉，然后判断时间如果还没到就再加入队列，这样就导致了一个小的“恶性循环”，而且由于数据量小，发现不了，其实再加一个辅助的队列就好了。
• 其实还有很多逻辑问题，比如当前程序进入阻塞状态后，我就把处理阻塞队列的时间加1了，其实这应该是由问题的，比如说：某程序刚进入阻塞队列然后又进入就绪队列（时间判断）执行时又进入阻塞队列这种情况，输出的时候就可能出现同一个进程接连两次进入阻塞队列的假象。所以为了避免这种现象， 在判断阻塞进程达到阻塞等待时间时，我用的是>而不是==。
• 总之，大体上实现某些功能比较简单，但是那些小问题处理起来很麻烦，重要的是“程序的思想”。

---

知识清单

• 时间片（维基百科）

时间片（timeslice）又称为“量子（quantum）”或“处理器片（processor slice）”是分时操作系统分配给每个正在运行的进程微观上的一段CPU时间（在抢占内核中是：从进程开始运行直到被抢占的时间）。现代操作系统（如：Windows、Linux、Mac OS X等）允许同时运行多个进程 —— 例如，你可以在打开音乐播放器听音乐的同时用浏览器浏览网页并下载文件。事实上，由于一台计算机通常只有一个CPU，所以永远不可能真正地同时运行多个任务。这些进程“看起来像”同时运行的，实则是轮番穿插地运行，由于时间片通常很短（在Linux上为5ms－800ms），用户不会感觉到。

时间片由操作系统内核的调度程序分配给每个进程。首先，内核会给每个进程分配相等的初始时间片，然后每个进程轮番地执行相应的时间，当所有进程都处于时间片耗尽的状态时，内核会重新为每个进程计算并分配时间片，如此往复。

通常状况下，一个系统中所有的进程被分配到的时间片长短并不是相等的，尽管初始时间片基本相等（在Linux系统中，初始时间片也不相等，而是各自父进程的一半），系统通过测量进程处于“睡眠”和“正在运行”状态的时间长短来计算每个进程的交互性，交互性和每个进程预设的静态优先级（Nice值）的叠加即是动态优先级，动态优先级按比例缩放就是要分配给那个进程时间片的长短。一般地，为了获得较快的响应速度，交互性强的进程（即趋向于IO消耗型）被分配到的时间片要长于交互性弱的（趋向于处理器消耗型）进程。

• 进程的三种状态话（百度知道）

进程处于生存周期里，有三种状态：就绪、执行、阻塞。这三种状态之间的切换都由进程调度程序控制。

进程调度程序把处理机执行时间的划分成长短相同但很短的时间块，只要不是切换进程状态时，那么任一时刻所在时间块最多只允许执行一个进程。连续的时间块在各个进程中切换着执行，这样来实现多个进程同时执行。（简单地说，其实处理机同一时刻只能执行一个进程，但处理机每个进程都执行一点，轮流着执行，感觉上就是这些进程在同时执行。明白了这点，你的问题就简单了。）

当某一时刻正在执行的进程，它的时间块用完了，那么程序调试程序就会让其从“执行”状态转换成”就绪“状态，就绪状态里的某个进程会获得处理机，它就从“就绪”状态转换成“执行”状态。
如果正在处于“执行”状态的进程所申请资源被占用或者启动I/O传输未完成，此时处于“阻塞”状态(也可以说是等待状态，也就是说这个进程暂时不会去和其它进程争夺时间块)，当该进程申请资源被释放，或者I/O传输满足了。它就被切换到“就绪”状态，与其它进程共用时间块。

赏