Linux下的实时调度算法

Real-Time Scheduling Algorithm Based on Linux

Linux实现了实时进程的概念,但并没有提供有效的任务调度支持;另一方面,RM(Rate Monotonic)和EDF(Earliest Deadline First)等传统的优先级调度算法在实时系统中已经得到广泛应用,但它们对于确定优先级所采用的标准比较简单和片面,容易导致紧急型任务的截止期限不能被满足或系统资源不能被充分利用.文中基于RM和EDF提出了一种新的实时调度算法SBRD(Scheduler Based on Rate and Deadline),它的优先级根据重要性和紧急性两个重要因素共同确定.实验表明:与RM和EDF相比,SBRD兼具二者的优点,在保证重要任务顺利执行的前提下,优先执行紧急型任务,以满足更多任务的截止期限,更充分地利用CPU资源;与原Linux的实时调度相比,SBRD能更有效地调度实时任务.

Although Linux kernel supports the concept of real-time tasks, it does not provide effective scheduling policies. Besides, as for the classical priority-based scheduling algorithms such as Rate Monotonic （RM） and Earliest Deadline First （EDF） that have been widely applied to real-time systems, priorities are usually determined only by a simple or single factor. Thus, the deadlines of emergency tasks can not be guaranteed and the system resources can not be effectively utilized. In order to solve this problem, this paper proposes a new real-time scheduling algorithm named SBRD （Scheduler Based on RM and EDF）. In this algorithm, the priority is determined by both the importance and the urgency. Experimental results show that SBRD possesses the virtues of both RM and EDF. In SBRD, urgent tasks are given priority in the precondition of guaranteeing important tasks. Thus, the deadlines of more tasks can be guaranteed and the CPU resource can be used more effectively. As compared with the real-time scheduling provided by standard Linux, SBRD is more effective.