[操作系统]多级队列调度算法

C++ 操作系统
操作系统
发布日期:   2021-04-15
文章字数:   2k
阅读时长:   8 分
阅读次数:  

题目描述

多级队列调度算法，设RQ分别为R1和RQ2，RQ1采用轮转法，时间片q=7。

RQ1>RQ2，RQ2采用短进程优先调度算法。

测试数据如下：RQ1：P1-P5，RQ2：P6-P10

进程 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
运行时间 16 11 14 13 15 21 18 10 7 14
已等待时间 6 5 4 3 2 1 2 3 4 5

程序功能及设计思路

程序功能：

这个程序主要由两部分组成，将这10个进程按照题目要求分成两组，第一组的5个进程使用轮转法(时间片q=7)调度进程，第二组的5个进程使用短进程优先调度算法调度进程。程序执行完毕后应按照进程完成的顺序输出各进程的名称及其完成的时间，最后还要计算出平均每个进程的周转时间。

设计思路：

轮转法：取链表的第一个进程运行一个时间片的时间，一共有2中情况:①这个时间片已经用完了但是进程还没没有执行完毕，这种情况下将这个进程还需要运行的时间减去一个时间片，系统时间增加一个时间片，在链表的队尾加上这个更新后的进程节点，最后在链表的头部删除这个进程节点。②进程在这个时间片的时间中已经完成了，这种情况下系统时间加上这个进程运行的时间，进程还需要的运行时间设置为0，进程的周转时间加上系统时间，在完成队列的队尾加上这个已完成的进程，最后从RQ1链表的头部取下这个进程节点。当等待链表中没有进程时结束执行。

短进程优先调度算法：只要等待队列不为空，就在等待队列中找到需要运行时间最短的节点，一次性把这个进程处理完毕，先把系统时间加上这个进程需要的运行时间，进程的运行时间加上系统时间，进程还需要的时间设置为0，在结束链表中加入这个完成的进程节点，最后在RQ2链表中删除这个进程节点。当等待链表中没有进程时结束执行。

程序功能及设计思路

数据结构：

struct PCB
{
    string name;    //进程名称
    int need;       //需要运行的时间
    int turn;        //周转时间
    PCB* next;      //下一个进程
    PCB() : name(""), need(0), turn(0), next(nullptr) {};
    PCB(string pName, int pNeed, int pTurn) : name(pName), need(pNeed), turn(pTurn), next(nullptr) {};
};

进程节点一共由四个成员元素构成，分别为进程的名称、进程还需要运行的时间、进程的周转时间以及有一个指向下一个进程的指针。

首先设置三个链表，链表的元素均为进程节点，链表1按进程进入系统的时间存储P1-P5这5个进程的信息，链表2按进程进入系统的时间存储P6-P10这5个进程的信息，第三个链表用于存储已经完成的进程。

算法设计：

//在队尾中插入节点
void PCB_insert(PCB* RQ,PCB* p)
{
    PCB* ptr = RQ;
    while (ptr->next != nullptr)
    {
        ptr = ptr->next;
    }
    ptr->next = p;
}

算法分析:找到链表的最后一个节点，最后一个节点的指针指向下一个节点。

//删除队列的第一个节点
void PCB_delete(PCB* RQ)
{
    PCB* ptr = RQ->next;      //ptr为需要删除的节点
    if (ptr == nullptr) return;
    RQ->next = ptr->next;       //删除节点
    ptr->next = nullptr;
}

算法分析:要删除的节点为附加头结点的下一个节点，附加头结点直接跳过删除节点，如果被删除节点后面还有节点，就指向删除节点的下一个节点，没有节点指向nullptr。

//将进程装入队列中
void getData(string fileName, PCB* RQ)
{
    fstream outFile;
    string line;
    string a,b,c;
    PCB* ptr=RQ;
    outFile.open(fileName, ios::in);        //打开文件
    if (!outFile.is_open())
    {    //判断文件能否打开
        cout << "文件无法打开！" << endl;
        return;
    }
    while (!outFile.eof())
    {
        getline(outFile, line);
        stringstream input(line);
        input >> a >> b >> c;

        PCB *temp=new PCB(a, stoi(b), stoi(c));
        PCB_insert(RQ, temp);
    }
    outFile.close();
}

算法分析:这个函数功能是将文件内容读入内存，逐行读取，一行的内容就是一个节点，第一个为进程名称，第二个为需要运行的时间，第三个为等待时间。每读取一个进程节点，就将这个节点链入链表中。

//轮转法
void Rotate(PCB* RQ, PCB* finsh)
{
    PCB* ptr;
    while (RQ->next != nullptr)
    {
        ptr = RQ->next;
        if (ptr->need > pai)
        {
            ptr->need -= pai;
            allclock += pai; 
            PCB_insert(RQ, ptr);
        }
        else
        {
            allclock += ptr->need;
            ptr->need = 0;
            ptr->turn += allclock;
            PCB_insert(finsh, ptr);
        }
        PCB_delete(RQ);
    }
}

算法分析：对链表的内容逐个读取，如果时间片内能完成就计算出时间后从链表删除加入结束链表尾部，不能完成的就减去时间片时间后从链表头部移到链表尾部，直到等待链表为空。

//找到时间要求最短的节点
PCB* findMin(PCB* RQ)
{
    PCB* ptr = RQ->next;
    PCB* result = RQ->next;
    if (RQ == nullptr) return nullptr;
    while (ptr != nullptr)
    {
        if (ptr->need < result->need)
        {
            result = ptr;
        }
        ptr = ptr->next;
    }
    return result;
}

算法分析： 遍历整个链表，找到运行所需时间最短的那个节点，返回这个节点的地址。

//短进程优先调度
void shortFirst(PCB* RQ, PCB* finsh)
{
    PCB* ptr;
    PCB* previous = RQ;
    while (RQ->next != nullptr)
    {
        ptr = findMin(RQ);
        previous = RQ;
        allclock += ptr->need;
        ptr->turn += allclock;
        ptr->need = 0;
        PCB_insert(finsh, ptr);

        while (previous->next != ptr && previous->next != nullptr)
        {
            previous = previous->next;
        }
        previous->next = ptr->next;
        ptr->next = nullptr;
    }
}

算法思想：当等待链表不为空时，找到所需时间最短的那个节点，处理完这个节点后，在链表中删除这个节点，最后加入完成链表。

源代码

stdfax.h

#ifndef STDAFX_H_INCLUDE
#define STDAFX_H_INCLUDE

#include <iostream>
#include <stdlib.h>
#include <string>
#include <fstream>
#include <sstream>

#define pai 7
using namespace std;

#endif // !STDAFX_H_INCLUDE

scheduling.h

#ifndef SCHEDULING_H_INCLUDE
#define SCHEDULING_H_INCLUDE

#include "stdafx.h"

int allclock = 0;
struct PCB
{
    string name;    //进程名称
    int need;       //需要运行的时间
    int turn;       //周转时间
    PCB* next;      //下一个进程

    PCB() : name(""), need(0), turn(0), next(nullptr) {};

    PCB(string pName, int pNeed, int pTurn) : name(pName), need(pNeed), turn(pTurn), next(nullptr) {};
};

//在队尾中插入节点
void PCB_insert(PCB* RQ,PCB* p)
{
    PCB* ptr = RQ;
    while (ptr->next != nullptr)
    {
        ptr = ptr->next;
    }
    ptr->next = p;
}

//删除队列的第一个节点
void PCB_delete(PCB* RQ)
{
    PCB* ptr = RQ->next;      //ptr为需要删除的节点
    if (ptr == nullptr) return;
    RQ->next = ptr->next;       //删除节点
    ptr->next = nullptr;
}

//将进程装入队列中
void getData(string fileName, PCB* RQ)
{
    fstream outFile;
    string line;
    string a,b,c;
    PCB* ptr=RQ;
    outFile.open(fileName, ios::in);        //打开文件
    if (!outFile.is_open())
    {    //判断文件能否打开
        cout << "文件无法打开！" << endl;
        return;
    }

    while (!outFile.eof())
    {
        getline(outFile, line);
        stringstream input(line);
        input >> a >> b >> c;

        PCB *temp=new PCB(a, stoi(b), stoi(c));
        PCB_insert(RQ, temp);
    }
    outFile.close();
}

//轮转法
void Rotate(PCB* RQ, PCB* finsh)
{
    PCB* ptr;
    while (RQ->next != nullptr)
    {
        ptr = RQ->next;
        if (ptr->need > pai)
        {
            ptr->need -= pai;
            allclock += pai; 
            PCB_insert(RQ, ptr);
        }
        else
        {
            allclock += ptr->need;
            ptr->need = 0;
            ptr->turn += allclock;
            PCB_insert(finsh, ptr);
        }
        PCB_delete(RQ);
    }
}

//找到时间要求最短的节点
PCB* findMin(PCB* RQ)
{
    PCB* ptr = RQ->next;
    PCB* result = RQ->next;
    if (RQ == nullptr) return nullptr;
    while (ptr != nullptr)
    {
        if (ptr->need < result->need)
        {
            result = ptr;
        }
        ptr = ptr->next;
    }
    return result;
}

//短进程优先调度
void shortFirst(PCB* RQ, PCB* finsh)
{
    PCB* ptr;
    PCB* previous = RQ;
    while (RQ->next != nullptr)
    {
        ptr = findMin(RQ);
        previous = RQ;
        allclock += ptr->need;
        ptr->turn += allclock;
        ptr->need = 0;
        PCB_insert(finsh, ptr);

        while (previous->next != ptr && previous->next != nullptr)
        {
            previous = previous->next;
        }
        previous->next = ptr->next;
        ptr->next = nullptr;
    }
}
#endif // !SCHEDULING_H_INCLUDE

main.cpp

#include "scheduling.h"
#include <iomanip>
int main()
{
    int count = 0;
    float result = 0;
    PCB* RQ1=new PCB;
    PCB* RQ2 = new PCB;
    PCB* finished = new PCB;
    getData("RQ1.txt", RQ1);        //将队列1装载进链表RQ1
    getData("RQ2.txt", RQ2);        //将队列2装载进链表RQ2
    Rotate(RQ1, finished);            //RQ1使用轮转法
    shortFirst(RQ2, finished);        //RQ2使用短进程优先调度算法

    //按完成顺序输出每个进程名称及其运行时间
    while (finished->next != nullptr)
    {
        finished = finished->next;
        cout << finished->name << " " << finished->turn << endl;
        result += finished->turn;
        count++;
    }

    cout << setprecision(4); //精度
    cout << "平均每个进程的周转时间为" << result / count << endl;
    delete RQ1;
    delete RQ2;
    delete finished;
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/04/15/cao-zuo-xi-tong-duo-ji-dui-lie-diao-du-suan-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 操作系统
赏
评论
 上一篇
[操作系统]银行家算法 [操作系统]银行家算法
题目描述用程序实现银行家算法，为进程请求资源。 已分配资源数量 资源需求量 A B C A B C P1 2 1 2 3 4 7 P2 4 0 2 1 3 4 P3 3 0 5 0 0 3 P4 2
2021-04-21 操作系统
C++ 操作系统
下一篇 
[每日算法]关路灯 [每日算法]关路灯
题目描述某一村庄在一条路线上安装了 n 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置
2021-04-11 每日算法
C++ 算法
  目录