Research On Task Scheduling Based On The Improved Multi-layer Feedback Queue Algorithm

In recent years, some new emerging technologies, such as big data and cloud computing, bring new challenges to the method of task scheduling. Task scheduling, which distributes the tasks to processors according to certain rules, can make the tasks completed by the shortest possible time. The effective task-scheduling method will greatly improve the computational performance of the processor and reduce extra expenses.Multi-layer feedback queue scheduling algorithm is a combination of first-come-first-service scheduling algorithm, short process first scheduling algorithm, priority scheduling algorithm and round-robin scheduling method. The multi-layer feedback queue scheduling algorithm, when compared with the other above mentioned scheduling algorithms, not only does not need to know the execution time of various processes, but also can meet the needs of all types of process. Especially in the solution to the massive task, multi-layer feedback queue scheduling algorithm has more advantages.Taking independent task as the research object, this thesis discussed the traditional basic task scheduling methods. Besides, faster task completion time and lower overhead are obtained by improving multi-layer feedback queue scheduling algorithm. The main works are showed in the following:(1) The basic scheduling and scheduling algorithm of the operating system are investigated. Furthermore, through comparing six basic scheduling methods based on the specific instances, their performance differences in the user-oriented and system-oriented are analyzed, and their advantages and disadvantages are presented. The characteristics and common structures of neural network are introduced, and the advantages of neural network used in multi-level feedback queue are proved.(2) A further research is made by basing on multi-level feedback queue, in view of the key factors in the selection time slice, which is long time slice bad for the short processes and short time slice bad for long processes, and an improved BT-MLFQ algorithm is put forward. BT-MLFQ algorithm adopts the method of dynamic time slice. Firstly, the process of the first entering into the system is executed by using the current queue slice to estimate the process execution time according to the timer. Secondly, according to the execution of process, the number of queue is created until all the processes are completed. The experimental results show that, compared with other MLFQ algorithm, BT-MLFQ algorithm has obvious improvement in the task average turnaround time, average waiting time and the number of context switches. Therefore, this improved algorithm is a highly efficient and intelligent task scheduling algorithm.(3) Considering the correlation of massive tasks, in order to make the BT-MLFQ algorithm more adaptive, neural network is used through learning the tasks to determine the time slice and the number of queue, thus, a self-adaption BT-MLFQ algorithm model is constructed.