基于EDF的Linux2.6系统多核调度研究

发布时间：2018-06-04 00:50

本文选题：多核处理器 + 调度策略　；参考：《成都理工大学》2012年硕士论文

【摘要】：微处理器从诞生到现在的短短六十多年，有着飞速的发展。从通过提高主频速度，在芯片上集成越来越多晶体管的“纵向”发展，到近几年研究人员“横向”的对处理器体系结构进行多核研发，伴随而来的要求是必须有更加出色的上层系统来适应其卓越的硬件并行性能，使上层系统也具备并发运行的处理模式。基于此原因，内核开源的Linux系统的发展前景是不错的，但由于Linux系统设计之初是没有定义为实时系统的，所以为了适应当前对现代化操作系统的要求，我们需要对Linux系统的内核调度进行改进来增强它的实时性能。本文正是基于上述原因，提出了一个解决方案，其思路是：采用在单核系统上使用较为成熟的时间截止优先级算法，即EDF算法，将此算法代码以一个完整的结构体，通过Linux2.6系统内核调度块能够以模块扩展方式移植新算法的原理，使得EDF算法能够应用在多核处理器平台下的Linux2.6系统上，进行任务的分配和调度。本研究方案中，在多核处理器上先用单核进行利用率计算，然后对等待任务序列进行分配到其它核运行是一个新的尝试，成功实施后可以使Linux2.6系统具备一定的实时功能。本文研究任务来源于企业项目中关于Linux内核调度的一个问题，主要的研究工作和取得的成果如下所示：第一，介绍Linux调度相关技术的进程，线程，，性能调度指标和调度算法等相关内容。然后提出研究方案，对整体工作流程进行分析与说明；第二，对EDF算法中关于处理周期性任务与不定期任务的利用率计算，任务截止时间临近时优先级的反转，和任务队列中优先级排序变化这三个关键技术详细分析；第三，从多核处理器的体系结构，和它的调度思想寻找出多核调度的脉络和关键点，进而分析出多核调度策略和具体管理方式；第四，将研究方案中EDF算法移植到Linux2.6系统内核的过程进行具体的分析与讲解；第五，为了进一步验证相关理论，在EDF算法成功移植到多处理平台的Linux系统内核后进行测试实验，分析结果；第六，通过实验得出与一个任务池（单核）上分配后运行任务的方式相比，我们通过在多核处理器平台下，用一核分配任务，其它核进行数据计算的思想，使得Linux2.6系统在多核处理器上实时性能得到加强。通过本方案的应用，对在多核处理器平台下的Linux2.6系统的调度延迟时间进一步缩小，且随着多核处理器上CPU数量的不断增多，我们预测这种延迟会大大减少，具有巨大经济效益。
[Abstract]:Microprocessor from the birth to the present short 60 years, has a rapid development. From the "vertical" development of integrating more and more transistors on chips by increasing the speed of the main frequency, to the "horizontal" development of processor architecture by researchers in recent years, The accompanying requirement is that there must be a more excellent upper system to adapt to its excellent hardware parallel performance, so that the upper system also has the processing mode of concurrent operation. For this reason, the development prospect of Linux system with open source kernel is good, but because Linux system was not defined as real-time system at the beginning of design, so in order to adapt to the requirement of modern operating system, We need to improve the kernel scheduling of Linux system to enhance its real-time performance. Based on the above reasons, a solution is proposed in this paper. The idea is to use the mature time cut-off priority algorithm (EDF algorithm) on a single core system, and make the code of this algorithm a complete structure. Through the principle that the kernel scheduling block of Linux2.6 system can transplant the new algorithm in the mode of module extension, the EDF algorithm can be applied to the Linux2.6 system under the multi-core processor platform for task allocation and scheduling. In this scheme, it is a new attempt to calculate the utilization rate with single core on the multi-core processor, and then assign the waiting task sequence to other cores. After successful implementation, the Linux2.6 system can have certain real-time function. The research task in this paper comes from a problem about Linux kernel scheduling in enterprise projects. The main research work and the results obtained are as follows: Firstly, the process, thread, performance scheduling index and scheduling algorithm of Linux scheduling technology are introduced. Then put forward the research program, analyze and explain the whole workflow; Secondly, the three key technologies of EDF algorithm, such as computing the utilization ratio of processing periodic and indefinite tasks, reversing the priority when the deadline of the task approaches, and changing the priority ranking in the task queue, are analyzed in detail. Thirdly, we find out the context and key points of multi-core scheduling from the architecture of multi-core processor and its scheduling thought, and then analyze the multi-core scheduling policy and specific management methods. Fourthly, the process of transplanting EDF algorithm to the kernel of Linux2.6 system is analyzed and explained. Fifth, in order to further verify the relevant theory, the EDF algorithm was successfully transplanted to the multi-processing platform of the Linux system kernel test experiment, analysis of the results; Sixthly, compared with the way the task is allocated on one task pool (single core), we use one core to allocate tasks and other cores to calculate the data on the platform of multi-core processor. The real-time performance of Linux2.6 system is enhanced on multi-core processor. Through the application of this scheme, the scheduling delay time of Linux2.6 system on multi-core processor platform is further reduced, and with the increasing number of CPU on multi-core processor, we predict that this delay will be greatly reduced and has great economic benefit.
【学位授予单位】：成都理工大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP316.81;TP332

【参考文献】