当前位置: 首页 > news >正文

基于优先级的时间片轮转调度算法(C语言实现)

已剪辑自: http://www.demodashi.com/demo/15341.html

基于优先级的时间片轮转调度算法

1. PCB结构(Block)

pcb

由此定义如下结构体:

typedef struct Block
{
    int processID; // 进程号
    int priority; // 优先级
    int status; // 状态
    double arrivalTime; // 到达时间
    double serviceTime; // 服务时间
    double runTime; // 已运行时间
    struct Block *next; // Next Block
} Block;

2. 数据结构(队列)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pvXuaPmI-1669459048842)(/contentImages/image/jianshu/13373683-fc06e9117b622d3e.png)] ](http://www.demodashi.com/contentImages/image/jianshu/13373683-ad1ac427688c2f40.png)

typedef struct Link
{
    struct Block *first;  // 指向队头
    struct Block *last;   // 指向队尾
} Link;

队列操作函数:

  • initLink:初始化队列
void initLink(Link *l)
{
    // 分配空间并检测是否成功
    l->first = l->last = (Block *)malloc(sizeof(Block));
    if (!l->first)
    {
        fprintf(stderr, "Malloc Error!\n");
        exit(-1);
    }
    // 空队列
    l->first->next = NULL;
    l->last->next = NULL;
}
  • isEmpty:判断队列是否为空
int isEmpty(Link *l)
{
    return l->first->next == NULL? 1: 0;
}
  • printLInk:输出队列中所有元素的信息
void printLink(Link *l)
{
    Block *p = l->first->next;
    // 遍历队列并输出
    printf ("\nProcess ID\tPriority\tArrival Time\tService Time\tRun Time\tStatus\n");
    while (p != NULL)
    {
        printf("\t%d\t%d\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%s\n", \
            p->processID, p->priority, p->arrivalTime, \
            p->serviceTime, p->runTime, p->status == 0? "ready": "finished");
        p = p->next;
    }
}
  • removeFirst:将队列中第一个元素中的数据复制到给定参数中(用于返回),并删除
void removeFirst(Link *l, Block *b)
{
    Block *t;
    // 空队列则直接返回
    if (isEmpty(l))
    {
        return ;
    }
    // t指向第二个Block,用于之后将队列接上
    t = l->first->next->next;
    // 将第一个Block中的内容复制到b中,用于返回
    b->processID = l->first->next->processID;
    b->priority = l->first->next->priority;
    b->arrivalTime = l->first->next->arrivalTime;
    b->serviceTime = l->first->next->serviceTime;
    b->runTime = l->first->next->runTime;
    b->status = l->first->next->status;
    // 释放第一个Block,并把队列接上
    free (l->first->next);
    l->first->next = t;
}
  • append:将新的元素添加到队尾
void append(Link *l, Block *b)
{
    Block *t;
    // 分配空间,并检测是否成功
    t = (Block *)malloc(sizeof(Block));
    if (t == NULL)
    {
        fprintf(stderr, "Malloc Error!\n");
        exit(-1);
    }
    // 将b中的内容复制到t中
    t->processID = b->processID;
    t->priority = b->priority;
    t->arrivalTime = b->arrivalTime;
    t->serviceTime = b->serviceTime;
    t->runTime = b->runTime;
    t->status = b->status;
    // 将t接到队尾
    t->next = NULL;
    l->last->next = t;
    l->last = t;
}
  • deleteLinkItem:删除队列中指定的元素
void deleteLinkItem(Link *l, Block *target)
{
    Block *p, *t;
    // 遍历队列,寻找目标Block
    p = l->first;
    while (p != NULL && p != target)
    {
        t = p;
        p = p->next;
    }
    // 若存在,则释放
    if (p != NULL)
    {
        t->next = p->next;
        free(p);
    }
}
  • sortByArrivalTime:根据进程到达时间将队列排序(从小到大)
void sortByArrivalTime(Link *l, int order)
{
    Block *p, *q, *tp, *tq;
    Block *temp, *min, *tmin;
    int minArrivalTime;
    // 这里使用了选择排序
    tp = tq = l->first;
    p = q = l->first->next;
    while (p != NULL)
    {
        // 这个数字可以修改的大一点。。。
        minArrivalTime = 9999;
        while (q != NULL)
        {
            // 寻找最小到达时间的Block
            if (q->arrivalTime < minArrivalTime)
            {
                minArrivalTime = q->arrivalTime;
                tmin = tq;
                min = q;
            }
            tq = q;
            q = q->next;
        }
        // 若寻找的Block与当前Block不是同一个则交换
        if (p != min)
        {
            tp->next = min;
            tmin->next = p;
            temp = min->next;
            min->next = p->next;
            p->next = temp;
        }
        tp = tq = p;
        p = q = p->next;
    }
}

3. 基于优先级的时间片轮转调度算法

  • 流程图

流程图

  • 算法
void RR(Link *l, Link *r)
{
    Block *p, *t;
    double maxPriority;
    double currentTime = 0;
    int selected, timeSlice;
    // 种下随机种子
    srand((unsigned)time(NULL));
    // 遍历队列
    t = p = l->first->next;
    while (p != NULL)
    {
        // 输出在当前时间已到达的进程Block信息
        printf ("\nProcess ID\tPriority\tArrival Time\tService Time\tRun Time\tStatus\n");
        selected = 0;
        maxPriority = 9999;
        while (p != NULL && currentTime >= p->arrivalTime)
        {
            selected = 1;
            printf("\t%d\t%d\t\t%.2lf\t\t%.2lf\t\t%.2lf\t\t%s\n", \
                p->processID, p->priority, p->arrivalTime, \
                p->serviceTime, p->runTime, p->status == 0? "ready": "finished");
            // 寻找优先级最高的进程
            if (p->priority < maxPriority)
            {
                maxPriority = p->priority;
                t = p;
            }
            p = p->next;
        }
        // 生成随机时间片
        timeSlice = rand() % 10;
        if (selected)
        {
            // 运行进程(模拟)
            printf("Current time: %.0lf, Selected process: %d\n", currentTime, t->processID);
            t->runTime += timeSlice;
            t->priority += 2;
            // 若进程已经结束,则将该进程添加到完成队列,并从当前队列中删除
            if (t->runTime >= t->serviceTime)
            {
                t->status = 1;
                currentTime += t->serviceTime - (t->runTime - timeSlice);
                t->runTime = t->serviceTime;
                append(r, t);
                deleteLinkItem(l, t);
            }
        }
        else
        {
            currentTime += timeSlice;
        }
        // 打印完成队列
        printLink(r);
        t = p = l->first->next;
    }
}

4. 测试与结果

  • 测试数据

测试数据

  • 测试结果

1

2

3

4

5

5.项目结构图

项目结构图
img

相关文章:

  • 43特征01——特征值特征向量: 特征多项式、特殊矩阵 的特征值与特征向量、Hamilton-Cayley 定理
  • [毕业设计]机器学习的运动目标跟踪-opencv
  • Ubuntu 软件管理学习笔记
  • python中pytest库用法详解
  • CSRF漏洞简介
  • C/C++航空客运订票系统
  • 编译原理之词法分析器随笔和简单实现
  • 47 - 父子间的冲突
  • 单片机和ARM A的区别
  • STC 51单片机40——汇编语言 串口 接收与发送
  • python破解wifi教程
  • Android App开发即时通信中通过SocketIO在客户端与服务端间传输文本和图片的讲解及实战(超详细 附源码)
  • 【网络安全】文件上传之安全狗bypass
  • MATLAB | 世界杯来用MATLAB画个足球玩叭~
  • LeetCode | 循环队列的爱情【恋爱法则——环游世界】
  • php的引用
  • 30秒的PHP代码片段(1)数组 - Array
  • canvas 绘制双线技巧
  • iOS动画编程-View动画[ 1 ] 基础View动画
  • Java新版本的开发已正式进入轨道,版本号18.3
  • opencv python Meanshift 和 Camshift
  • PAT A1050
  • php面试题 汇集2
  • python大佬养成计划----difflib模块
  • tensorflow学习笔记3——MNIST应用篇
  • TiDB 源码阅读系列文章(十)Chunk 和执行框架简介
  • Wamp集成环境 添加PHP的新版本
  • 关于 Cirru Editor 存储格式
  • 力扣(LeetCode)21
  • 免费小说阅读小程序
  • 使用SAX解析XML
  • [地铁译]使用SSD缓存应用数据——Moneta项目: 低成本优化的下一代EVCache ...
  • ​DB-Engines 11月数据库排名:PostgreSQL坐稳同期涨幅榜冠军宝座
  • #图像处理
  • (最优化理论与方法)第二章最优化所需基础知识-第三节:重要凸集举例
  • .Net Attribute详解(上)-Attribute本质以及一个简单示例
  • .NET 使用 JustAssembly 比较两个不同版本程序集的 API 变化
  • .NET/C# 使用反射调用含 ref 或 out 参数的方法
  • .net程序集学习心得
  • .net反编译工具
  • .net和php怎么连接,php和apache之间如何连接
  • .NET性能优化(文摘)
  • ::什么意思
  • @angular/cli项目构建--Dynamic.Form
  • @Resource和@Autowired的区别
  • @serverendpoint注解_SpringBoot 使用WebSocket打造在线聊天室(基于注解)
  • [1204 寻找子串位置] 解题报告
  • [16/N]论得趣
  • [ANT] 项目中应用ANT
  • [C]整形提升(转载)
  • [CF]Codeforces Round #551 (Div. 2)
  • [ICCV2017]Neural Person Search Machines
  • [IMX6DL] CPU频率调节模式以及降频方法
  • [one_demo_4]不使用第3个变量交换两个变量的值
  • [Oracle][Metadata]如何查找与某一个功能相关的数据字典名
  • Eclipse安装WindowBuilder
  • ibatis调用存储过程例子
  • ibatis调用存储过程例子
  • Mysql NDB and InnoDB 存储引擎区别
  • Eclipse完美汉化教程
  • MySQL NDB Cluster 集群简介
  • Android 仿PhotoShop调色板应用(二) 透明度绘制之AlphaPatternDrawable
  • MySQL NDB集群安装配置(mysql cluster 9.4.13 installation)
  • Cydia崩溃错误修复
  • Mysql 高可用方案 InnoDB Cluster