多级队列调度和多级反馈队列调度算法的实现_多级反馈队列调度算法实验代码-程序员宅基地

技术标签: 算法  c++  一些小程序  链表  操作系统  队列  

多级队列调度算法

操作系统实验导航
实验一:银行家算法 https://blog.csdn.net/weixin_46291251/article/details/115384510
实验二:多级队列调度和多级反馈队列调度算法 https://blog.csdn.net/weixin_46291251/article/details/115530582
实验三:动态分区式内存管理 https://blog.csdn.net/weixin_46291251/article/details/115772341
实验四:Linux下多进程通信 https://blog.csdn.net/weixin_46291251/article/details/116274665
实验五:进程通信的三种方式 https://blog.csdn.net/weixin_46291251/article/details/116301250
实验六:Linux文件系统实验 https://blog.csdn.net/weixin_46291251/article/details/116423798
实验七:自制简单U盘引导程序 https://blog.csdn.net/weixin_46291251/article/details/116427629
实验八:磁盘调度算法 https://blog.csdn.net/weixin_46291251/article/details/116431907
实验九:请求分页系统中的置换算法 https://blog.csdn.net/weixin_46291251/article/details/116443021
学习笔记:操作系统复习笔记 https://blog.csdn.net/weixin_46291251/article/details/117086851

  • 多级队列:该算法将系统中的进程就绪队列从一个拆分为若干个,将不同类型或性质的进程固定分配在不同的就绪队列,不同的就绪队列采用不同的调度算法,一个就绪队列中的进程可以设置不同的优先级,不同的就绪队列本身也可以设置不同的优先级。
    多级队列调度算法由于设置多个就绪队列,因此对每个就绪队列就可以实施不同的调度算法,因此,系统针对不同用户进程的需求,很容易提供多种调度策略。

题目描述:

  • 设RQ分为RQ1和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

程序功能

  • 对于给定的数据使用多级队列调度算法进行分析计算周转时间。其中多级队列分为RQ1和RQ2 ,RQ1采用的是时间片长度为7的时间片轮转算法,RQ2采用的是短进程优先算法。并且RQ1的优先级高于RQ2(即只有在RQ1内所有程序运行结束,RQ2才能开始运行)

设计思路

  • 时间片轮转:首先对RQ1按照等待时间长短排序,然后从头设置循环,只要队列不空就一直进行下去,每次取队头RQ1的下一个元素(RQ1仅用作标志,不存储数据)判断need是否小于等于时间片大小,小于等于则置为0后踢出队列进入finish队列,大于则将need减去时间片大小,然后将其移动至队尾。
  • 短进程优先:开始前需要对RQ2按照剩余执行时间大小进行排序,与时间片轮转法类似,不同的是这里一旦开始执行就直接执行完毕,然后下一个进程上处理机运行。

数据结构

  • 本程序每个进程用一个PCB表示,每个PCB内含有name(标识符)、need(当前仍然需要多长时间才能运行结束)、turn(周转时间(等于等待时间+运行时间))、next指针(指向等待队列的下一个进程)。两个队列的头节点分别为RQ1、RQ2还有一个结束队列Finish(运行结束后进程从原队列进入这里)
typedef struct tag_pcb {
    
    char name[8];
    int need = 0;//需要运行的时间
    int turn = 0;//周转时间=等待时间+运行时间
    struct tag_pcb* next = NULL;
}PCB;
PCB* RQ1=new PCB, * RQ2 = new PCB, * Finish = new PCB;

代码实现:

#include<iostream>
#include <fstream>
using namespace std;


typedef struct tag_pcb {
    
    char name[8];
    int need = 0;//需要运行的时间
    int turn = 0;//周转时间=等待时间+运行时间
    struct tag_pcb* next = NULL;
}PCB;
PCB* RQ1=new PCB, * RQ2 = new PCB, * Finish = new PCB;
const int TimePiece = 7;//时间片长度

void ReadFile(){
    

    ifstream In("RQ1.txt");
    PCB* Current = RQ1;

    while (!In.eof()) {
    
        PCB* Cur = new PCB;

        In >> Cur->name >> Cur->need>> Cur->turn;

        Current->next = Cur;
        Current = Current->next;
    }
    In.close();

    ifstream In1("RQ2.txt");
    PCB* Current1 = RQ2;

    while (!In1.eof()) {
    
        PCB* Cur1 = new PCB;

        In1 >> Cur1->name >> Cur1->need >> Cur1->turn;
        Current1->next = Cur1;
        Current1 = Current1->next;
    }
    In1.close();
}

void Q1_Insert(PCB a) {
     //时间片轮转算法队列的插入(插入尾部)

    PCB* Current = RQ1;
    while (Current->next != NULL)
        Current = Current->next;
    Current->next = new PCB;

    *Current->next = a;
    //Current->next = &a;

    Current->next->next = NULL;

}
void Q2_Insert(PCB b) {
     //短进程优先调度算法队列的插入

    
    PCB* Current = RQ2;
    while (Current->next != NULL)
        Current = Current->next;
    Current->next = new PCB;

    *Current->next = b;
    Current->next->next = NULL;
    
}
void Fin_Insert(PCB c) {
     //短进程优先调度算法队列的插入
    
    PCB* cc = new PCB;
    *cc = c;

    cc->next = Finish->next;
    Finish->next = cc;   
}
void Q2_sort(PCB *T) {
    

    PCB* X = new PCB;//用来保存排序后的链表
    PCB* p = new PCB;//用来保存当此最小值的前一位
    PCB* Current = T->next;
    PCB * PreCurrent = T;
    PCB* TailX = X;
    
    while (T->next != NULL) {
    
        int tem = 999999;

        Current = T->next;
        PreCurrent = T;
        while (Current != NULL) {
    
            if (Current->need < tem) {
    
                tem = Current->need;
                
                p = PreCurrent;
                //cout << "处理" << p->name << p->need << "\n";
            }
            Current = Current->next;
            PreCurrent = PreCurrent->next;
        }
     

        TailX->next = p->next;
        TailX = TailX->next;

        if (p->next->next != NULL)
            p->next = p->next->next;
        else
            p->next = NULL;      
    }
    *T = *X;
}

int main()
{
    
    ReadFile();

    int clock = 0; //时钟
    while (RQ1->next != NULL) {
    //表示RQ1还有元素
        int t = TimePiece;
        PCB* Current = RQ1->next;
        int fin = 0;

        if (Current->need <= t)
            t = Current->need, fin = 1;
           
        clock += t;//表示pi运行t

        //输出计算过程
        //cout << "\n" << Current->name << "_____" << Current->turn << "__+ ___" << clock << "__= ___" << Current->turn +clock << "\n";
       
        Current->need -= t;
  
        if (fin)
            Current->turn += clock, Fin_Insert(*Current);//运行结束    
        else
            Q1_Insert(*Current);//进入队尾等待运行

        if (Current->next == NULL)
            break;
        RQ1->next = Current->next;
    }


    clock = 0;//时钟要清空一次
    Q2_sort(RQ2);//先排序

    cout << "RQ2:__"; 
    for (PCB* Current2 = RQ2->next; Current2 != NULL; Current2 = Current2->next)
        cout << Current2->name << "--";

    while (RQ2->next != NULL) {
    //表示RQ2还有元素(到这一步默认RQ1已经为空)
        PCB* Current3 = RQ2->next;
        int t = Current3->need;

        clock += t;//表示pi运行t
        Current3->need -= t;//实质为清空
        Current3->turn += clock;

        Fin_Insert(*Current3);

        if (Current3->next == NULL)
            break;
        RQ2->next = Current3->next;
    }

    int SUM = 0;
    for (PCB* Current2 = Finish->next; Current2 != NULL; Current2 = Current2->next) {
    
        cout << "\n" << Current2->name <<"\t"<< Current2->turn ;
        SUM += Current2->turn;
    }

    cout << "\n总周转时间为:" << SUM << "\n";
}

  • 多级队列调度测试结果:
    在这里插入图片描述

附:

多级反馈队列调度算法如下原理:

  • 1、设有N个队列(Q1,Q2…QN),其中各个队列对于处理机的优先级是不一样的,也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说,优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。怎么讲,位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高(也就是说,Q1中的作业一定要比Q2中的作业先被处理机调度),依次类推其它的队列。
  • 2、对于优先级最低的队列来说,里面是遵循时间片轮转法。也就是说,位于队列QN中有M个作业,它们的运行时间是通过QN这个队列所设定的时间片来确定的;对于其他队列,遵循的是先来先服务算法,每一进程分配一定的时间片,若时间片运行完时进程未结束,则进入下一优先级队列的末尾。
  • 3、各个队列的时间片是一样的吗?
    不一样,这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的,也就是说,优先级越高的队列中它的时间片就越短。同时,为了便于那些超大作业的完成,最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。

上述程序在某一进程在一级队列运行一轮后没有运行完毕,若加入二级队列而不是加入原队列的尾部,则可以实现简单的多级反馈队列调度算法
两种算法的不同之处就在于:当一个RQ1中的进程在时间片结束之后是回到当前的队尾还是到RQ2队列之中。
在上述程序中也很容易实现:

		if (fin)
            Current->turn += clock, Fin_Insert(*Current);//运行结束    
        else
            Q1_Insert(*Current);//进入队尾等待运行

修改为:

		if (fin)
            Fin_Insert(*Current);//运行结束    
        else
            Q2_Insert(*Current);//进入二级队列等待运行
        Current->turn += clock, 

上述两种代码分别实现了上述两种功能,执行时只需选一种在相应位置即可。

  • 多级反馈队列调度测试结果:在这里插入图片描述

由分析上述数据容易发现:在该测试数据的情况下多级反馈队列调度算法是要优于多级队列调度的

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46291251/article/details/115530582

智能推荐

(模板题)sdut 3362 数据结构实验之图论六:村村通公路(prim求最小生成树)_现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使-程序员宅基地

文章浏览阅读530次。数据结构实验之图论六:村村通公路Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^题目描述当前农村公路建设正如火如荼的展开,某乡镇政府决定实现村村通公路,工程师现有各个村落之间的原始道路统计数据表,表中列出了各村之间可以建设公路的若干条道路的成本,你的任务是根据给出的数据表,求使得每个村都有公路_现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使

基于结巴分词的文本余弦相似度计算_.net jieba分词里的相似度算法-程序员宅基地

文章浏览阅读555次。多维空间余弦公式:举一个具体的例子,假如:句子 X 和句子 Y 对应向量分别是x1,x2,...,x64000 和y1,y2,...,y64000,那么它们夹角的余弦等于一二三冲鸭:使用余弦相似度算法计算文本相似度55 赞同 · 10 评论文章这篇文章个人觉得不太好理解,在研读之后,自己总结了一个通俗易懂的算法。import jiebaimport math s1 = '这只皮靴号码大了。那只号码合适's1_cut = [i for i in jieba.cut(s1, c_.net jieba分词里的相似度算法

html5 django游戏,html5、django上传文件-程序员宅基地

文章浏览阅读80次。使用简单的表单上传文件到django框架form表单需要指定 enctype="multipart/form-data"前端代码:uploadFile后端代码:def upload(request):##request.FILES 为类字典类型,健为前段name指定的值,字典值为UploadFile对象,前端form中需要指定enctype="multipart/form-data"##uploa..._django+h5 上传文件

机器学习经典算法详解及Python实现---朴素贝叶斯分类及其在文本分类、垃圾邮件检测中的应用_python 神经网络分类 贝叶斯算法-程序员宅基地

文章浏览阅读2.6k次。摘要:朴素贝叶斯分类是贝叶斯分类器的一种,贝叶斯分类算法是统计学的一种分类方法,利用概率统计知识进行分类,其分类原理就是利用贝叶斯公式根据某对象的先验概率计算出其后验概率(即该对象属于某一类的概率),然后选择具有最大后验概率的类作为该对象所属的类。总的来说:当样本特征个数较多或者特征之间相关性较大时,朴素贝叶斯分类效率比不上决策树模型;当各特征相关性较小时,朴素贝叶斯分类性能最为良好。另外_python 神经网络分类 贝叶斯算法

git push时报错error: failed to push some refs to ‘https://gitee.com/**.git‘的解决方案-程序员宅基地

文章浏览阅读4.4w次,点赞44次,收藏112次。将远程仓库同步到本地,然后再重新add、commit、push就行了。当然引发这种错误的原因可能不是这个,但大家可以尝试一下。小编经过这个方法成功解决了错位,大家也可以进行尝试哦!是因为在手动修改了远程仓库中的文件,导致一些文件在本地仓库和远程仓库上不一致,故而引发该错误。当然也有可能是别的原因哦,这个原因的可能性比较大!问题弄得小编很是烦恼。经过查阅资料找到了问题的解决方案,..._error: failed to push some refs to

freertos 创建互斥量_FreeRTOS学习笔记——互斥型信号量-程序员宅基地

文章浏览阅读479次。[FreeRTOS内核详解—-信号量 信号量主要用来保护共享资源、任务之间或者任务与中断之间用来同步等。FreeRTOS有二值信号量、计数信号量、互斥锁和递归互斥锁。 信号量实现总0.前言[在嵌入式操作系统中二值型信号量是任务间、任务与中断间同步的重要手段。FreeRTOS的二值型信号量简单易用,下面结合一个具体例子说明FreeRTOS中的二值型信号量如何使用。]在嵌入式操作系统中互斥型信号量是任..._freertos创建互斥信号量

随便推点

python运行报错 继续_解决Python3.8运行tornado项目报NotImplementedError错误-程序员宅基地

文章浏览阅读1.1k次。今天拉了一个使用了tornado的项目在本地跑,按照源码作者的步骤配置完,运行,直接报错了,要求环境Python3.6+,我装的是Python3.8,理论上应该直接正常运行的,报错信息:Traceback (most recent call last):File "ice_server.py", line 150, in RunServer.run_server(port=p, host=h)Fi..._notimplementederror: return_offset_mapping is not available when using pytho

图像视频超分辨率基本概念-程序员宅基地

文章浏览阅读3k次,点赞4次,收藏15次。视频超分是由图像超分发展而来的。基于深度学习的图像超分辨率(SISR)首次实现于2014年,推广到视频超分是在2017年,由此可见超分辨率还是一个比较新颖的课题方向。 超分类任务主要源自对图像视频信息的传输和恢复。在实际生活中,有很多情况下需要对图像或者视频进行传输,而由于视频图像的分辨率越来越高,体积越来越大,传输成本比如网络带宽等也在不断提升。因此对图像或者视频进行下采样(压缩)之后再进行传输,到达客户端以后在对图像视频进行恢复(restore)是很有必要的(比如微..._视频超分

核主成分分析方法(KPCA原理篇)_kpca核主成分分析-程序员宅基地

文章浏览阅读5.7k次。(1)方法的基本思想是:对样本进行非线性变换,在变换空间进行主成分分析来实现在原空间的非线性主成分分析;(2)算法步骤:① 通过核函数计算矩阵,其元素为。其中和为原空间的样本,是核函数。② 计算K的特征值,并从大到小进行排列。找出由特征值对应的特征向量(表示第个特征向量),并对进行归一化()。③ 原始样本在第个非主成分下的坐标为: 这里的是指第i个样本,的..._kpca核主成分分析

因sga或pga等参数设置过大,导致Oracle数据库起不来的解决方法_数据库sga+pga分配太大-程序员宅基地

文章浏览阅读529次。因sga或pga等参数设置过大,导致Oracle数据库起不来,可用如下方法解决:create spfile from pfile='/mnt/u01/app/oracle/init.ora';startup pfile=/mnt/u01/app/oracle/product/11.2.0/db_1/dbs/init.oraalter system set control_files='/m..._数据库sga+pga分配太大

如何成为一名黑客_esr 如何成为一名黑客-程序员宅基地

文章浏览阅读5.4k次。如何成为一名黑客埃里克· 史蒂芬 林峰Thyrsus企业 [email protected] > 2001埃里克雷蒙修订历史版本1.44二年五月二十日ESR更新Java的批判。版本1.432011年2月7日ESRPython的普及在2_esr 如何成为一名黑客

webpack自定义plugin实现编译时自动插入js和css_webpack通过plugin在css文件增加代码-程序员宅基地

文章浏览阅读4.1k次,点赞2次,收藏3次。有一些场景下需要这么个需求,在webpack编译运行时自动插入js或css代码到html模板中。例如要插入一段埋点插件或监控插件的js代码,当然你可以直接写在html模板中,但是对于一个项目中存在多个html模板的情况就不适合一个个手写添加了;本文讨论通过自定义封装一个webpack plugin的形式来实现自动插入js或css的功能。你可以直接使用我封装好的npm包:insert-html-webpack-plugin也可以按以下教程自己手写一个。一、分析本身webpack在运行时就会自动_webpack通过plugin在css文件增加代码

推荐文章

热门文章

相关标签