基于改进的多级反馈队列算法的任务调度研究

摘要

近年来，大数据、云计算等新兴技术的出现，给任务调度方法研究带来了新的挑战。任务调度问题是将任务进程按照一定的规则分配到处理器上，使得任务完成时间最短。有效的任务调度方法将会大大提高处理器系统的计算能力，降低不必要的能耗。
　　多级反馈队列调度算法结合了先来先服务调度算法、短作业优先调度算法、优先级调度算法和轮转调度法等多种方法。相比于这几种调度算法，它不必事先知道各种进程的执行时间，而且还可以满足各种类型进程的需要。尤其是在解决海量任务的时候，多级反馈队列调度算法的优势更为明显。
　　本文以独立任务为研究对象，对传统的基本任务调度方法进行了研究。通过对多级反馈队列任务调度算法的改进，获得了更快的任务完成时间和较小的开销。主要工作体现在如下几个方面：
　　（1）研究操作系统的基本调度方式和调度算法，通过具体的实例对比六种基本调度方法，分析了它们在面向用户和面向系统两个准则上的性能差异，给出了各个调度算法的优势和劣势；研究了神经网络技术的特征、常用的神经网络结构以及神经网络用于多级反馈队列的优点。
　　（2）对基于多级反馈队列(Multi-Layer Feedback Queue,MLFQ)的几种任务调度模型进行深入研究，多级反馈队列调度算法的关键因素是对时间片的选取，过长的时间片大小不利于短进程作业用户和过短的时间片大小不利于长进程作业用户，针对该问题提出一种改进的MLFQ算法(Multi-Layer Feedback Queue based on Burst Time of the running processes，BT-MLFQ)。BT-MLFQ算法采用动态时间片方法，首先采用队列当前的时间片大小来执行初次进入系统的进程，利用计时器预估该进程的执行时间；其次，根据队列中进程的执行情况，依次创建队列，直到所有进程都执行完毕。实验结果表明，相对于其他的MLFQ算法，BT-MLFQ算法在任务平均周转时间、平均等待时间和交换次数上有明显的提升，是一种高效的智能任务调度算法。
　　（3）考虑用户任务进程的相关性，为了让BT-MLFQ算法更具有适应性，利用神经网络通过学习任务进程来优化多级反馈队列算法时间片和队列的大小，从而完成了基于进程执行时间的多级反馈队列自适应(A Self-Adaption Multi-Layer Feedback QueueBased on the Burst Time，SA-BT-MLFQ)调度算法模型的设计。

目录

封面

声明

中文摘要

英文摘要

目录

缩略词

第一章 绪论

1.1研究背景和意义

1.2国内外研究现状

1.3论文的主要研究工作

1.4论文的组织结构

1.5小结

第二章 任务调度相关技术

2.1任务调度概念

2.2任务调度准则

2.3基本调度算法

2.4人工神经网络

2.5小结

第三章 基于多级反馈队列的任务调度算法

3.1时间片相等的多级反馈队列算法

3.2时间片增加的多级反馈队列算法

3.3基于进程执行时间的多级反馈队列算法策略设计

3.4小结

第四章 基于BT-MLFQ算法的自适应任务调度模型

4.1初始队列个数的确定

4.2递归神经网络优化时间片

4.3仿真实验与结果分析

4.4小结

第五章 总结与展望

参考文献

致谢

在学期间的研究成果及发表的学术论文