Improvement And Application Of A Scheduling Algorithm For Embedded Linux Kernel

With embedded systems being used in many areas, embedded market is getting moreopen and freer, these days. Competitions between embedded application providers are moreand more intense and users' functional requirements of embedded application are increasing.As the limits of hardware resources, a key point in competition among embedded systemproducers is how to make embedded application being much functional and havingfavorable real-time behaviors so as to reduce production cost and satisfy customers.Real-time operating systems become the mainstream in development of embeddedapplication with increasing of embedded applications' scale. The reason is that real-timeoperating systems can not only provide real-time guarantee to application software, but alsoachieve system function modularization. Therefore application software are reusable andproduction cost is reduced. In embedded market, embedded real-time operating systemsemerge in an endless stream, such as Windows CE, VxWorks. But they are better used inspecific areas and most embedded operating systems are not free but expensive. Linuxoperating system is becoming the most influential operating system in embedded world,because it is an open-source operation system with its low cost, properties of supportingmulti-architectures and having plentiful drivers to support hardware. But general Linuxsystem is a time-sharing desktop operating system. Therefore, how to improve the real-timeperformance for general Linux systems so as to make them fulfilling the real-timerequirement of embedded systems is an important subject for research. Since theperformance of Linux schedulers is a pivotal factor for real-time performance of Linux, thisthesis improves the performance of Embedded Linux systems by improving theperformance of Linux kernel scheduling algorithm.Linux kernel has been updated to version 2.6 and has been introduced many newfeatures for embedded platform. By researching O (1) scheduler and CFS scheduler ingeneral Linux 2.6 kernel I found that they aim at the design target which can besummarized as:1). Ensure fairness of scheduling processes so as to make sure tasks with low prioritycan not be starved to death.2). schedule interactive tasks first to improve respondence capacity of whole operationsystem.Desktop operation systems are used in PC which has better performance than embedded computer. And desktop operating system mainly achieves human-computerinteraction which has low request on real-time. So the design principle of embedded Linuxschedulers should also include:1). Guarantee Real-timeness of system to make sure every task can be completed intime.2). Increase CPU throughput so every task can maximize the use of CPU resources.Based on these design targets, my thesis proposes a new dynamic real-time schedulingalgorithm. This thesis introduces the EEVDF algorithm to make sure fairness of taskscheduling under satisfaction of system real-timeness. EEVDF is an algorithm which hascertain real-time capability for proportional share resource allocation, so it can not onlyensure fair task scheduling of CPU, but also improve every task's respondence capacity.This algorithm sets a priority for each task. Resource proportion of task is calculatedaccording to the task's priority. This algorithm is used to schedule tasks by two parameters:virtual time and virtual deadline. But the algorithm is unfavorable to scheduling delay timeif calculation of the two parameters is relatively difficult. As the feature of tasks inembedded operation system is small quantity and high numeric stability. The number oftasks changes severely only when system is booting and shutting down. According to thefeature, I revised the classical EEVDF algorithm to make it satisfies the requirement ofreal-timing in embedded system. The revised EEVDF can compute deadline by only onemultiplication and one addition so that it satisfies the need of real-timeness of embeddedsystem. The revised EEVDF chooses failed tasks by FIFO to guarantees fairness of taskscheduling, because scheduling failure often occurs in practice when current time exceeddeadline of tasks.By default, task is classified into two types: real-time tasks and common tasks in Linux.Kernel can schedule the two kinds of tasks by different scheduling algorithm. Application isalways set to common task, therefore Linux can not meet real-time requirements of specificapplications well. But if application's attribute is set to real-time task, it may cause systemload is too high, even lead to system instability. Aiming on the inadequate real-timing, thisthesis includes a new task type called "sub-real-time". Sub-real-time task is the task whichhas soft-real-time requirement or is important to users but little impact on system stability.the priority of almost-real-time tasks is between real-time tasks and common tasks.Improved scheduler uses dynamic scheduling strategy. It still uses FIFO algorithm toschedule real-time tasks in order to ensure the real-timeness of system. It uses improvedEEVDF algorithm to schedule common tasks in order to ensure scheduling fairness andCPU throughput. In case of almost-real-time tasks, it depends on CPU usage. That is, FIFOalgorithm for low CPU usage and Improved EEVDF algorithm for high. The scheme can improve real-timeness of almost-real-time tasks as real-time tasks when CPU usage is lowand it also let real-time tasks have as much CPU resource as possible to remain the wholesystem steady. In order to achieve the improved scheduler in general Linux kernel, I havedesigned new data structure like wait queue of tasks, CPU run queue with improveddynamic scheduling strategy. It has also been achieved preemptive scheduling strategy bypreemptive mechanism of Linux 2.6.At last, I used stress test to CFS scheduler and the dynamic real-time scheduler by atool called HackBench in Linux kernel 2.6.32, and then I compared the differences betweentheir performances. I have taken experiments in the true environment. According to therequirement of GB/T19056-2003《auto recorder》National standard, The results ofexperiment confirmed it is necessary to use dynamic real-time scheduler on auto recorder.