投稿
  1. 极客之音首页
  2. 技术随笔

多级反馈队列调度算法

小半 • • 技术随笔 • 阅读 310

导读：本篇文章讲解 多级反馈队列调度算法，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

1 多级反馈队列调度算法

1.1 作用

如果有很多任务排队等着被处理，哪个任务先被处理，哪个任务后处理，这个需要由操作系统决定，这就是调度。

多级反馈队列调度算法 是目前操作系统调度算法中被公认的一种较好的调度算法。它可以满足各种类型进程的需要，既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。

1.2 应用范围

此算法应用于同一个资源的多个使用者可分优先级使用资源的情况

1.3 基本概念

多级反馈队列调度算法是一种根据先来先服务原则给就绪队列排序，为就绪队列赋予不同的优先级数，不同的时间片，按照优先级抢占CPU的调度算法。算法的实施过程如下：

  1. 按照先来先服务原则排序，设置N个就绪队列为Q1，Q2…QN，每个队列中都可以放很多作业；

  2. 为这N个就绪队列赋予不同的优先级，第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低；

  3. 设置每个就绪队列的时间片，优先权越高，算法赋予队列的时间片越小。时间片大小的设定按照实际作业（进程）的需要调整；

  4. 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。

  5. 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。

  6. ***对于同一个队列中的各个进程，按照 ( 时间片轮转法调度 )***。比如Q1队列的时间片为N，那么Q1中的作业在经历了时间片为N的时间后，若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。

  7. 在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业即抢占式调度CPU。

1.4 使用方法及步骤

假设系统中有3个就绪队列Q1,Q2,Q3，时间片分别为2，4，8。

现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。

而它们所需要的CPU时间分别是3，2，1个时间片。

  1. 时刻0： J1到达。于是进入到队列1 ， 运行1个时间片 ， 时间片还未到，此时J2到达。

  2. 时刻1： J2到达。 由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给J2。

  3. 时刻2： J1进入Q2等待调度，J2获得CPU开始运行。

  4. 时刻3：J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。

  5. 时刻4：J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。

  6. 时刻5：J3经过1个时间片，完成。

  7. 时刻6：由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。

  8. 时刻7：J1再经过一个时间片，完成了任务。于是整个调度过程结束。
    BF5A3j.png

1.5 源码

编写并调试一个模拟的进程调度程序，采用“多级反馈队列轮转法”调度算法对五个进程进行调度。

注意：linux 平台下的 unistd.h 头文件相当于 windows平台的 windows.h 头文件

#include <iostream>
#include <queue>
#include <list>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>

using namespace std;

unsigned int q_id = 0;                // 队列进程号的全局变量
unsigned int stime = 0;               // 进程开始执行的时间
const unsigned int Q_NUM = 3;         // 总就绪队列数
const unsigned int TOTAL_PRO_NUM = 5; // 总进程数
const unsigned int INIT_PRO_NUM = 3;  // 初始就绪进程数
unsigned int pro_num = 3;             // 当前进程个数

// 进程信息
struct Pro
{
    unsigned int pid;        // 进程ID
    unsigned int start_time; // 开始执行时间
    unsigned int need_time;  // 预计执行时间
    unsigned int end_time;   // 完成时间
    unsigned int run_time;   // 已经运行时间
    unsigned int count;      // 计数器
};

// 多级就绪队列节点信息
struct Node
{
    queue<Pro> q;          // 就绪队列
    unsigned int priority; // 队列优先级
    unsigned int cap;      // 时间片
};

// 进程调度类
class Scheduling
{
private:
    queue<Pro> qp;    // 队列
    list<Pro> lp;     // 链表
    list<Node> ln;    // 链表队列
    unsigned int cap; // 时间片
public:
    Scheduling(/* args */);
    ~Scheduling();
    void create_q_pro(); // 创建进程queue的函数
    void create_l_pro(); // 创建进程list的函数
    void create_node();  // 创建node队列
    void fcfs();         // FCFS ： 先来先服务调度算法
    void rr();           // RR : 轮转调度算法
    void mfq();          // MFQ : 多级反馈队列调度算法
};

Scheduling::Scheduling(/* args */)
{
    cap = 10; // 初始化时间片
}

Scheduling::~Scheduling()
{
}

void Scheduling::create_q_pro()
{
    Pro item;
    item.pid = (++q_id);
    item.count = 0;
    item.need_time = rand() % 100 + 10; // 预计需求时间 在 10 ～ 100 之间
    item.run_time = 0;
    //
    qp.push(item);
    printf("创建进程 PID= %d:  执行所需时间= %d\n", item.pid, item.need_time);
}

void Scheduling::create_l_pro()
{
    Pro item;
    item.pid = ++q_id;
    item.count = 0;
    item.need_time = rand() % 200 + 10; // 预计需求时间 在 10 ～ 100 之间
    item.run_time = 0;
    //
    lp.push_back(item);
    printf("创建进程 PID = %d:   执行所需时间 = %d\n", item.pid, item.need_time);
}

void Scheduling::create_node()
{
    for (int j = 0; j < Q_NUM; j++)
    {
        Node node;
        node.priority = 1 + j;     // 初始队列最高优先级1
        node.cap = 20 * pow(2, j); // 初始化时间片 20
        int i;
        // 在最高优先队列中创建 3 个进程
        for (i = 0; j == 0 && i < INIT_PRO_NUM; i++)
        {
            Pro item;
            item.pid = (++q_id);
            item.count = 0;
            item.need_time = rand() % 100 + 10; // 预计需求时间 在 10 ～ 100 之间
            item.run_time = 0;
            //
            node.q.push(item);
            printf("创建进程 PID= %d:  执行所需时间 = %d\n", item.pid, item.need_time);
            printf("\n");
        }
        //
        ln.push_back(node);
    }
}

// 先来先服务调度算法
void Scheduling::fcfs()
{
    int i, rd;
    printf("-------先来先服务调度算法-------\n");
    for (i = 0; i < 5; i++)
    {
        create_q_pro();
        printf("\n");
    }
    while (!qp.empty())
    {
        Pro *p = &qp.front();
        p->start_time = stime;
        printf("创建进程 PID= %d:  执行所需时间 = %d\n", p->pid, p->need_time);
        sleep(p->end_time);
        p->end_time = p->start_time + stime;
        printf("结束时间%d\n", p->end_time);
        printf("\n");
        qp.pop();
        stime = p->end_time;
        //
        // rd = rand() % 10;
        // if (rd > 6)
        // {
        //     create_q_pro();
        //     printf("\n");
        // }
    }
}

// 轮转调度算法
void Scheduling::rr()
{
    int i, rd;
    stime = 0;
    printf("-------时间片轮转法(时间片 = %d)-------\n", cap);
    for (i = 0; i < 5; i++)
    {
        create_q_pro();
        printf("\n");
    }
    while (!qp.empty())
    {
        Pro *p = &qp.front();
        p->start_time = stime;
        printf("进程PID=%d: 执行还需时间%d 开始执行时间%d ", p->pid, p->need_time, p->start_time);
        if (p->need_time > cap)
        {
            sleep(cap);
            // sleep(3);
            p->need_time = p->need_time - cap;
            p->end_time = cap;
            p->run_time = p->run_time + cap;
            stime = stime + cap;
            ++(p->count);
            printf("第 %d 次执行，已执行时间 = %d\n", p->count, p->run_time);
            qp.push(qp.front());
            qp.pop();
        }
        else
        {
            sleep(p->end_time);
            // sleep(3);
            stime = stime + p->end_time;
            p->end_time = stime;
            p->run_time = p->run_time + p->need_time;
            ++(p->count);
            printf("第 %d 次执行，已执行时间 = %d 结束时间 = %d 执行完毕\n", p->count, p->run_time, p->end_time);
            p->end_time = 0;
            qp.pop();
        }
        printf("\n");
        // rd = rand() % 10;
        // if (rd > 6)
        // {
        //     create_q_pro();
        //     printf("\n");
        // }
    }
}

// 多级反馈队列调度算法
void Scheduling::mfq()
{
    int rd;  // 随机数，随机产生新进程
    int flag = 0; // flag标志是否有新进程进入初级队列
    stime = 0; // 系统的时间
    printf("-------多级反馈队列调度(时间片 = %d)-------\n\n", cap);
    create_node();
    // 遍历每个就绪队列
    for (list<Node>::iterator iter = ln.begin(); iter != ln.end();)
    {
        printf("队列优先级 = %d 队列时间片 = %d\n", iter->priority, iter->cap);
        // 遍历每个就绪队列的每个进程
        while (!iter->q.empty())
        {
            // iter 指向当前队列; iter1 指向下一队列
            list<Node>::iterator iter1 = iter;
            Pro *p = &iter->q.front();
            p->start_time = stime;
            printf("进程PID=%d: 执行还需时间%d 开始执行时间%d ", p->pid, p->need_time, p->start_time);
            // 进程无法在此队列一次完成
            if (p->need_time > iter->cap)
            {
                // sleep(cap);
                sleep(1);
                p->need_time = p->need_time - cap;
                p->end_time = cap;
                p->run_time = p->run_time + cap;
                stime = stime + cap;
                ++(p->count);
                printf("第 %d 次执行，已执行时间 = %d\n", p->count, p->run_time);
                if (++iter1 == ln.end()) // 如果当前进程正在最后一个队列
                {
                    iter->q.push(iter->q.front());
                    iter->q.pop();
                }
                else // 把当前进程放到下一队列队尾
                {
                    iter1->q.push(iter->q.front());
                }
                // 从当前队列移除
                iter->q.pop();
            }
            else // 进程可以在此队列完成
            {
                // sleep(p->need_time);
                sleep(1);
                stime = stime + p->need_time;
                p->end_time = stime;
                p->run_time = p->run_time + p->need_time;
                ++(p->count);
                printf("第 %d 次执行，已执行时间 = %d 结束时间 = %d 执行完毕\n", p->count, p->run_time, p->end_time);
                p->end_time = 0;
                iter->q.pop();
            }
            printf("\n");
            rd = rand() % 10;
            if (rd > 7 && pro_num < TOTAL_PRO_NUM) //有新进程进入高优先级队列
            {
                list<Node>::iterator iter2 = ln.begin();
                Pro item;
                item.pid = ++q_id;
                item.count = 0;
                item.need_time = rand() % 200 + 10; // 预计需求时间 在 10 ～ 100 之间
                item.run_time = 0;
                iter2->q.push(item);
                pro_num++;
                printf("创建进程 PID= %d:  执行所需时间 = %d\n", item.pid, item.need_time);
                printf("\n");
                if (iter2->priority < iter->priority) // 若当前队列优先级不是最高优先级
                {
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 1)
        {
            iter = ln.begin();
        }
        else
        {
            ++iter;
        }
        flag = 0;
    }
}

int main(int argc, char const *argv[])
{
    Scheduling sc;
    sc.mfq();
    return 0;
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69751.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！