分时EDF算法及其在多媒体操作系统中的应用

提出了一种新的CPU调度算法－－分时EDF（Earliest Deadine First)算法，该算法能保证硬实时任务不丢失死线，并易于在分时系统中实现。以分时EDF算法为基础，提出一种新的CPU层次调度算法－－HRFSFQ，该算法用于多媒体操作系统时能保证各类任务的QoS。最后通过大量实验证明了上述算法的有效性和正确性。

Time-Sharing EDF Algorithm and Its Application in Multimedia OS

Hard real time tasks, soft real time tasks and best effort tasks often exist in the multimedia operating system at the same time and require different QoS for system resources, such as CPU, memory and network. So how to allocate system resources reasonably such that every task could achieve its QoS becomes an urgent problem, especially for CPU scheduling.There are two approaches to realize CPU scheduling in multimedia operating system. One method is to make the time sharing operating system support real time tasks. This method is compatible with all applications in nowadays general OS, but it usually uses heuristic scheduling algorithms and it is difficult to realize task's admission control exactly. Another method is to use real time operating systems that adopt classical real time scheduling algorithms such as RM and EDF. The classical real time CPU scheduling algorithms are often used to guarantee hard real time tasks' QoS and not suitable for soft real time tasks and best effort tasks. Due to its generality, the former method is the direction in the near future.For scheduling different\|type tasks in multimedia OS, hierarchical scheduling is proposed. First, hierarchical scheduling allocates CPU bandwidth to every task class proportionally. Then, every task class is scheduled using algorithm suitable for it. The examples of hierarchical scheduling is WFQ, SFQ, EEVDF and so on. But a common flaw in these hierarchical scheduling algorithms is that they can not guarantee hard real time tasks' deadline.So, in this paper we propose a new CPU scheduling algorithm named time sharing EDF, which can be used to schedule hard real time tasks in general time sharing systems, and can be implemented easily. We also provide its schedulability test conditions. Based on time sharing EDF, we further propose HRFSFQ algorithm, a CPU hierarchical scheduling algorithm, which can be used in multimedia operating systems and guarantee tasks' QoS. Finally the efficiency and correctness of these algorithms are given by extensive simulation.