精华内容
下载资源
问答
  • 多级反馈队列调度算法实验
    2021-05-21 16:29:05

    This model paper was revised by LINDA on December 15, 2012.

    This model paper was revised by LINDA on December 15, 2012.

    多级反馈队列调度算法的实现

    学生实习报告

    课程名称_ 数据结构与数据处理应用训练

    题目名称 多级反馈队列调度算法的实现

    学生学院 计算机与计算科学

    专业班级

    学 号

    学生姓名

    指导教师

    2012 年 2

    多级反馈队列调度算法的实现

    【摘要】

    多级反馈队列调度算法是操作系统中CPU处理机调度算法之一,该算法既能使高优先级的进程(任务)得到响应又能使短进程(任务)迅速完成。UNIX操作系统便采取这种算法,而本次试验就是试用C语言模拟某多级反馈队列调度算法。本次试验中前三级就绪队列采用时间片轮转法,时间片大小分别为2、4和8,最后一级就绪队列采用FIFO调度,将任务进入多级队列进行模拟,任务从优先级高的队列到优先级地的队列的顺序逐一进入,还用了算法支持抢占式,最后完成模拟,得到各个任务先后完成的顺序,还有得到各个任务的响应时间、离开时间、周转时间。

    【关键词】 队列 优先级 任务 时间

    1 内容与要求

    【内容】

    多级反馈队列调度算法是操作系统中CPU处理机调度算法之一,该算法既能使高优先级的进程(任务)得到响应又能使短进程(任务)迅速完成。UNIX操作系统便采取这种算法,本次试验就是试用C语言模拟某多级反馈队列调度算法,通过输入任务号、到达时间、运行时间,求出任务完成的先后顺序以及各个任务的响应时间、离开时间、周转时间。

    【要求】

    多级反馈队列调度算法描述:

    1、该调度算法设置四级就绪队列:前三级就绪队列采用时间片轮转法,时间片大小分别为2、4和8;最后一级就绪队列采用FIFO调度。

    2、任务在进入待调度的队列等待时,首先进入优先级最高的队列等待。

    3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务,则调度次优先级队列中的任务,依次类推。

    4、对于同一个队列中的各个任务,按照队列指定调度方法调度。每次任务调度执行后,若没有完成任务,就被降到下一个低优先级队列中。

    5、在低优先级的队列中的任务在运行时,又有新到达的任务,CPU马上分配给新到达的任务。(注:与原来的题目不同,原题是在低优先级的队列中的任务在运行时,又有新到达的任务时,要在运行完这个时间片后,CPU马上分配给新到达的任务,而本题不需要在运行完这个时间片,即正在进行的任务立刻停止,CPU马上分配给新到达的任务)

    6、为方便实现,时间以1为单位,用整数数据表示;且每个时间点,最多只有一个任务请求服务(即输入)。

    2 总体设计

    算法总体思路:

    这是建立在一个时间轴上的,即时刻,一个一个时刻(时间点)进行。

    2.1.1 主函数思路:

    先初始化所有队列,再输入任务个数,如果输入个数为0,则重新输入,然后输入各个任务的信息,即任务号、到达时间、运行时间,再当时刻到任务的到达时间时,就创建任务,然后运行任务,时刻自动加1 ,创建任务与运行任务进行循环,直到所有任务进行完或所有队列为空才跳出循环,最后清空所有队列。

    2.1.2 功能函数思路:

    void create(LinkQueue* x,Job job):使任务的已运行时间为0,再使任务进入第一个队列。

    void function(LinkQueue* x, int timing):四个队列从第一个到第四个,即从最高优先级开始,任务在4个队列中逐个进行,根据任务是否为第一次执行,求出响应时间,任务完成时,求出离开时间和周转时间输出信息,在前3个队列,如果任务刚完成一个就绪队列的时间片,就降低优先级,使任务进入下一个队列。

    功能模块介绍:

    void main ()

    函数功能:主函数

    void InitQueue(LinkQueue& HQ):队列的初始化

    void EnQueue(LinkQueue& HQ,ElemType item)

    函数功能:向队列中插入一个元素

    ElemType OutQueue(LinkQueue& HQ)

    函数功能:从队列中删除一个元素

    ElemType *PeekQueue(LinkQueue& HQ)

    函数功能:读取队首元素

    bool Empty

    更多相关内容
  • C语言实现多级反馈队列调度算法-计算机操作系统实验。C语言实现多级反馈队列调度算法-计算机操作系统实验
  • 进程调度的设计与实现 目录 一、 实验的目的………………………………………………1 二、 实验的内容(任务)及要求……………………………1 三、 实验设备及环境…………………………………………1 四、 实验的原理...
  • 本文件是对操作系统进程多级反馈队列调度算法的设计与实现,算法以txt的形式输入输出,其中包含设计报告
  • 实验多级反馈队列调度算法 一. 主要实现方法和代码介绍 ​ 1.编写进程类,其只包含所需的运行时间和进程编号两个属性,还有一个运行方法,此方法就是将所需的运行时间属性减去.传入的运行时间. ​ 2.创建进程函数:...

    实验一 多级反馈队列调度算法

    在这里插入图片描述

    一. 主要实现方法和代码介绍

    ​ 1.编写进程类,其只包含所需的运行时间和进程编号两个属性,还有一个运行方法,此方法就是将所需的运行时间属性减去.传入的运行时间.

    ​ 2.创建进程函数:创建maxp个进程,(应该不超过10,在此创建九个,即暂时不进行进程队列越界处理),其运行时间符合均值为0,方差为20的高斯分布,并取整取绝对之后所得到的值, (此处是为了全自动创建进程),进程号自己自增. 在创建进程时,使用mutex库将每一个queue 加锁和解锁,以实现互斥访问.

    ​ 3.运行函数. 主要的算法函数. 首先判断队列非空,即进入运行,一级队列非空时,优先运行第一级队列,一级队列空后,才检差后几级队列. 但是后几级队列每一次执行后,都重新检查一级队列是否非空.具体实现是:if(一级队列非空) { while(一级队列非空){ 运行}} ;而高级别不执行while. 其次,当一次执行没有执行完,则立即放入下一级队列,每次写入都加锁.

    二. 程序流程图

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B8AyJRjO-1647856457764)(C:\Users\51330\AppData\Roaming\Typora\typora-user-images\image-20211009101816266.png)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S14kJ5Lg-1647856457765)(C:\Users\51330\AppData\Roaming\Typora\typora-user-images\image-20211009101923526.png)]

    三. 程序代码

    #include <iostream>
    #include <queue>
    //随机数
    #include <random>
    #include <chrono>
    #include <cmath>
    #include <thread>
    #include <mutex>
    
    #define T 10
    #define Qsize 10
    using namespace std;
    mutex mym1;
    mutex mym2;
    mutex mym3;
    mutex mym4;
    int ALLP = 0;
    int CPUTIME = 0;
    int information = 0;
    class Process
    {
    public:
        int RUNTIME;
        int PNUM;
        void run(int runt);
    };
    void Process::run(int rt)
    {
        cout << CPUTIME << ":" << ends;
        if (rt >= RUNTIME)
        {
            RUNTIME = 0;
            cout << "进程" << PNUM << "已运行完." << endl;
            CPUTIME += rt;
        }
        else
        {
            RUNTIME -= rt;
            cout << "进程" << PNUM << "已运行" << rt << "时,还需" << RUNTIME << "时即可运行完." << endl;
            CPUTIME += rt;
        }
    }
    queue<Process> q1, q2, q3, q4;
    void createProcess(int maxp)
    {
        // 从epoch(1970年1月1日00:00:00 UTC)开始经过的纳秒数,unsigned类型会截断这个值
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        std::default_random_engine generator(seed);
        // 第一个参数为高斯分布的平均值,第二个参数为标准差
        std::normal_distribution<double> distribution(0.0, 20.0);
        //   for (int i = 0; i < 10; ++i)
        //     std::cout << distribution(generator) << std::endl;
        for (int i = 1; i <= maxp; i++)
        {
            Process c1;
            c1.RUNTIME = std::abs((int)distribution(generator));
            c1.PNUM = ALLP++;
            mym1.lock();
            q1.push(c1);
            mym1.unlock();
            cout << "已创建" << ALLP - 1 << "号进程,需要" << c1.RUNTIME << "时来完成." << endl;
        }
        information++;
    }
    void running()
    {
        int performed = 0;
        while (true)
        {
            // if (!q1.empty() || !q2.empty() || !q3.empty() || !q4.empty())
            {
                if (!q1.empty())
                {
                    while (!q1.empty())
                    {
                        Process c1 = q1.front();
                        mym1.lock(); // lock
                        q1.pop();
                        mym1.unlock();
                        c1.run(T);
                        if (c1.RUNTIME != 0)
                        {
                            if (q2.size() < Qsize)
                            {
                                mym2.lock(); //加锁
                                q2.push(c1);
                                mym2.unlock();
                            }
                            else
                            {
                                暂时没管队列已满时的卡死状态
                            }
                        }
                    }
                }
                else if (!q2.empty())
                {
                    Process c2 = q2.front();
                    mym2.lock();
                    q2.pop();
                    mym2.unlock();
                    c2.run(2 * T);
                    if (c2.RUNTIME != 0)
                    {
                        if (q3.size() < Qsize)
                        {
                            mym3.lock();
                            q3.push(c2);
                            mym3.unlock();
                        }
                        else
                        {
                            暂时没管队列已满时的卡死状态
                        }
                    }
                    if (!performed)
                    {
                        createProcess(9);
                        performed = 1;
                    }
                }
                else if (!q3.empty())
                {
                    Process c3 = q3.front();
                    mym3.lock();
                    q3.pop();
                    mym3.unlock();
                    c3.run(4 * T);
                    if (c3.RUNTIME != 0)
                    {
                        if (q4.size() < Qsize)
                        {
                            mym4.lock();
                            q4.push(c3);
                            mym4.unlock();
                        }
                        else
                        {
                            暂时没管队列已满时的卡死状态
                        }
                    }
                }
                else if (!q4.empty())
                {
                    Process c4 = q4.front();
                    mym4.lock();
                    q4.pop();
                    mym4.unlock();
                    c4.run(8 * T);
                    if (c4.RUNTIME != 0)
                    {
                        if (q4.size() < Qsize)
                        {
                            mym4.lock();
                            q4.push(c4);
                            mym4.unlock();
                        }
                        else
                        {
                            暂时没管队列已满时的卡死状态
                        }
                    }
                }
                else
                {
                    cout << CPUTIME << ":当前时刻所有进程已运行完." << endl;
                    while (!q1.empty() || !q2.empty() || !q3.empty() || !q4.empty())
                    {
                        break;
                    }
                    if (information == 2)
                        break;
                }           // }
            }
        }
    }
    int main()
    {
        // thread t1(createProcess, 9);
        createProcess(9);
        thread t2(running);
        // t1.join();
        t2.join();
        return 0;
    }
    

    四. 运行结果

    在这里插入图片描述

    五.结果分析

    ​ 观察上方运行结果即可得到:

    1. 先进行创建进程,创建了九个进程. 而后当一级队列运行完成后,再次创建了九个进程,后面重新从一级队列开始运行. 运行完后,才运行下级队列的1~7号进程.

      故可以看出,一级队列最高优先级实现成功.

    2. 代码缺陷分析:

      • 创建进程和运行不能同步进行. 虽然尝试实现创建两个线程,让运行函数和创建进程的函数分开运行,通过对共享变量(共享内存通信)的修改通知不同的进程运行,但总是进入死循环,尝试失败
      • 没有按照老师上课讲得PCB的大部分信息来创建进程, 而是偷懒只考虑自己的模拟需求,只有运行时间和进程号两个属性.

    . 运行完后,才运行下级队列的1~7号进程.

    故可以看出,一级队列最高优先级实现成功.

    1. 代码缺陷分析:

      • 创建进程和运行不能同步进行. 虽然尝试实现创建两个线程,让运行函数和创建进程的函数分开运行,通过对共享变量(共享内存通信)的修改通知不同的进程运行,但总是进入死循环,尝试失败
      • 没有按照老师上课讲得PCB的大部分信息来创建进程, 而是偷懒只考虑自己的模拟需求,只有运行时间和进程号两个属性.
    展开全文
  • 多级反馈队列调度算法C语言源代码

    热门讨论 2012-10-03 00:56:55
    用C语言实现的多级反馈队列调度算法,操作系统课程作业。用VC6.0调试通过。
  • 多级队列调度和多级反馈队列调度算法的实现

    千次阅读 多人点赞 2021-04-08 20:28:29
    多级反馈队列调度算法可以如下原理: 1、设有N个队列(Q1,Q2…QN),其中各个队列对于处理机的优先级是不一样的,也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说,优先级Priority(Q1) > ...

    多级队列调度算法

    操作系统实验导航
    实验一:银行家算法 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 
      
    进程P1P2P3P4P5P6P7P8P9P10
    运行时间1611141315211810714
    已等待时间6543212345

    程序功能

    • 对于给定的数据使用多级队列调度算法进行分析计算周转时间。其中多级队列分为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, 
    

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

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

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

    展开全文
  • 下面我们首先介绍,多级反馈队列调度算法 然后对前面介绍的各种调度算法进行比较 之后呢,我们简单讨论一下 在设计多处理器调度算法时所要考虑的几个问题 多级反馈队列调度算法 是 UNIX 的一个分支,BSD 5.3 版所...

    下面我们首先介绍,多级反馈队列调度算法 然后对前面介绍的各种调度算法进行比较 之后呢,我们简单讨论一下 在设计多处理器调度算法时所要考虑的几个问题 多级反馈队列调度算法 是 UNIX 的一个分支,BSD 5.3 版所采用的调度算法 它是在前面各种调度算法的基础之上 提出的一个综合的调度算法,是在考虑了各种 因素之后进行折中权衡的一个结果 下面我们介绍 一下多级反馈队列调度算法的基本思想 就绪队列设置成多个 其中第一级队列的优先级最高 依次从高到低,系统 给不同的就绪队列分配了长度不同的时间片 第一级队列优先级最高 但分配给它的时间片最小 随着队列优先级的不断降低 分配给队列的时间片就越大 比如说第一级队列分配给它一个单位的话 第二级队列就可以分配成两倍的时间片 那么第三级可以分配四倍的时间片,这就是 级别越低,时间片越大 在进行调度的时候 首先从优先级高的队列进行调度 如果第一级队列没有进程了 那么系统会从第二级队列进行调度,以此类推 每一个队列都是按照时间片轮转的方式进行调度 新创建的进程 就绪的时候呢都进入第一级队列 如果一个被调度上 CPU 的进程用完了时间片 而放弃了 CPU,那么它就进入下一集就绪队列 也就是说,它被降级了 那么如果一个被调度上 CPU 的进程 由于等待 I/O 而被阻塞,进入了等待队列 当等待的事件发生后,这个进程从等待队列 回到原来一级就绪队列。 那么这里头 我们可以根据不同的情况来设计不同的方案 以体现系统对这一类进程的 偏好程度,比如说 这个进程是回到原来一级就绪队列的队首呢 还是队尾?如果回到队首,说明系统对这类进程更加友好 另外,当这个进程再度被调度上 CPU 之后 是让它运行完剩余的时间片呢 还是重新给它分配一个完整的时间片让它去运行? 也体现了系统对这类进程的偏好程度 那么我们现在所看到的 多级反馈队列调度算法呢是一个非抢占式的 如果允许抢占呢 也就是说当有一个更高优先级的进程就绪的时候 可以抢占正在运行进程的 CPU 那么被抢占的进程呢 会回到原来一级就绪队列的末尾 当然也可以有不同的设计方案 比如说回到原来一级就绪队列的队首 当这个进程再度被调度上 CPU 时呢 可以运行完它刚才剩余的时间片 也可以重新给它一个完整的新的时间片让它运行 因此呢又派生出不同的设计方案 下面我们来看一下这张图 它反映了一个进程在 队列里头的一些迁移活动 当创建一个新的进程时 所有的进程都进入第一级队列 如果是 I/O 型的进程,那么它可能 被调度上 CPU 之后很短时间就去等待 I/O 当它从等待队列又回到就绪队列的时候 由于我们让它回到原来一级就绪队列,所以它呢优先级没有降低 被调度上 CPU 的机会很多。 但是对于 CPU 型的进程 它被调度上 CPU,用完了一个时间片之后 它就会回到下一级队列 那么如果每次都用完了它的时间片,它就会降级 可能一个 CPU 型的进程就慢慢降到了 优先级最低的这个队列里头,因此我们可以看到 通过这样一个调度算法 就可以慢慢地区分出来哪些进程是 CPU 型进程 哪些进程是 I/O 型进程,很显然 多级反馈队列调度算法对 I/O 型进程更偏好一点 对 CPU 型进程呢不太有利 但是呢它也做了一些弥补,比如说 优先级高的队列时间片短 而优先级低的队列时间片会很大 所以当低优先级的 CPU 型进程被调度上 CPU 之后,它可以运行更长的时间 那这里呢也是一种平衡的结果。 下面 我们对前面介绍的各种调度算法 做一下小结。 在占用 CPU 的方式上 先来先服务,短作业优先 最高响应比优先调度算法是非抢占式的调度策略 最短剩余时间优先 则是一个抢占式的调度策略,而时间片轮转 多级反馈队列调度算法 则是允许在时间片到的时候可以进行抢占 在追求调度算法指标上 我们来看一下短作业优先 最短剩余时间优先和最高响应比优先 这三个调度算法都可以带来比较高的吞吐量 而 时间片轮转调度算法 如果时间片很小,那么它的吞吐量就很低 先来先服务调度算法 还有多级反馈队列调度算法对吞吐量这个指标 并不强调,在响应时间方面 时间片轮转,短作业优先两个调度算法 对短的作业可以提供很快的响应时间 最短剩余时间优先 和最高响应比优先调度算法呢,也可以提供很好的响应时间 而对于先来先服务调度算法 当不同的进程 它们的时间有很大差别的时候,对于某些进程 它的响应时间会很慢,下面我们来看一下 调度算法本身所带来的开销 先来先服务和时间片轮转调度算法 因为实现比较简单,所以开销比较小 而其它四种调度算法它们的开销可能很大 比如说最高响应比优先调度算法 它要计算每一个进程的响应比 才能选择响应比最高的那个进程。 所以计算响应比需要花时间 多级反馈队列调度算法需要维护多个就绪队列,这也需要花时间 接着我们来看一下不同的调度算法 对进程的影响。 时间片轮转调度算法 公平地对待每一个进程。 最高响应比优先调度算法 则是在先就绪的进程和短进程之间做了一个很好的平衡 而来先来先服务调度算法 对长进程之后的短进程,或者是 I/O 型进程 是不利的。 那么最短作业优先 和最短剩余时间优先的调度算法对长进程不利 会导致长进程产生饥饿现象 多级反馈队列调度算法 对于 I/O 型进程是偏好的,也就是说对 I/O 型进程有利 而对 CPU 型进程不利 会导致 CPU 型进程产生饥饿 所以没有一种调度策略是完美的 也不可能有一种调度策略对各种类型的进程都能够照顾到 因此在设计调度策略的时候,我们应该 考虑综合性的因素,下面 我们简要介绍一下在设计多处理器调度算法时 需要考虑的几个问题 在设计多处理器调度算法时 我们不仅要决定选择哪一个进程执行 而且还要确定这个被选中的进程在哪一个 CPU 上执行 另外我们必须要考虑 进程在多个 CPU 之间迁移时所带来的高速缓存 TLB 失效的开销 如果一个进程 之前在 CPU1 上执行,后来又被调度到了 CPU2 上执行 那么高速缓存 TLB 失效就会增加 而如果这个进程每次都被指定到 同一个 CPU 上执行,那么就会减少各种 失效。 因此 应该尽可能地使进程总在同一个 CPU 上执行 另外 呢,我们还应该考虑到一个负载均衡的问题 因为有多个 CPU,那么不可能让某些 CPU 非常地忙碌 而其它 CPU 很空闲,所以 我们要通过调度使得 所有的 CPU 都保持忙碌,那么这就 是一个负载均衡的问题

    展开全文
  • 包含各种多级反馈队列调度算法,C代码,尤其是抢占!
  • 多级反馈队列进程调度GUI实现,使用Swing编写的一个可视化界面,支持进程的动态创建,进程调度过程可视化。
  • 多级反馈队列调度算法

    千次阅读 2022-05-26 08:40:13
    在Linux下编程实现多级反馈队列调度算法,采用三级调度策略,所有进程先按到达顺序进入一级队列,按照时间片为2轮转一次,一个时间片内未完成的进程被依次移入二队列尾部。当一级队列中没有进程时,开始调度二级队列...
  • 通常在使用多级队列调度算法时,进程进入系统时被永久地分配到某个队列。例如,如果前台和后台进程分别具有单独队列,那么进程并不从一个队列移到另一个队列,这是因为进程不会改变前台或后台的性质。这种设置的优点...
  • 短学期课程设计 多级反馈队列调度算法的实现 可供参考
  • 请教多级反馈队列调度算法????????????在某一操作系统中对进程调度采用多级反馈队列调度算法。现设定采用三级分数给小编了,小编来 0时刻A到达,进入I队列,执行2个时间段后,转向队列II,再执行了3个时间段后,B...
  • 基本上实现处理机对进程的最主要的调度执行算法:包括先来先服务、短作业/进程优先、时间片轮转调度算法、优先权调度算法、高响应比优先调度算法、多级反馈队列调度算法等算法。
  • 操作系统中多级反馈队列调度算法 C语言模拟实现
  • 时间片轮转调度算法(RR)是十分简单的进程调度算法。 进程在执行时的情况 在该时间片内进程执行完毕,这种情况调度程序将立即把该进程弹出队列,并把CPU分配给新的队首进程 在该时间片内进程未执行完毕,调度程序...
  • package ...import java.util.*;/** * @Class MSFQS * @Description 多级反馈队列调度算法 * @Author Naren * @Date 2020/5/30 10:46 * @Version 1.0 */public class MSFQS {/*三个队列*/private st...
  • 假设系统中有3个反馈队列Q1,Q2,Q3,时间片分别为2,4,8。 设有3个作业J1,J2,J3分别在时间 0 ,1,3时刻到达。而它们所需要的CPU时间分别是3,2,1个时间片。 1、时刻0 J1到达。于是进入到队列1 , 运行1个时间片 ,...
  • 操作系统课程设计报告-多级反馈队列调度算法模拟,操作系统,多级就绪队列,进程调度,时间片轮转法,附带详细的文档说明和源代码
  • 多级反馈队列调度算法具体原理

    千次阅读 2021-05-29 18:55:45
    多级(假设为N级)反馈队列调度算法可以如下原理: 1、设有N个队列(Q1,Q2…QN),其中各个队列对于处理机的优先级是不一样的,也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说,优先级Priority(Q1...
  • 多级反馈队列调度算法(附Python3实现代码)

    万次阅读 多人点赞 2018-04-19 22:57:14
    一、多级反馈队列调度算法 多级反馈队列调度算法是进程调度的一种算法,该调度算法可以不用事先知道各种进程所需的执行时间,还可以较好的满足各种类型进程的需要,是目前共认的一种较好的进程调度算法。 那你可能...
  • 1、进程在进入待调度队列等待时,首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程,则调度次优先级队列中的进程。 3、对于同一个队列中的各个进程,按照...
  • 题目: 分析:
  • 操作系统_多级反馈队列调度算法

    千次阅读 2018-12-17 17:38:43
    1、设置 N 个就绪进程队列,即队列 0,队列 1,……,队列 N-1,用于存放就绪进程。每个队列 优先级不同,且从队列 0 到...3、在队列内部,进程之间采用先来先服务(FCFS)算法辅以时间片限时机制进行调度:位于队...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,194
精华内容 4,877
热门标签
关键字:

多级反馈队列调度算法实验