The Research Of Deadline-Monotonic Algorithm And The Implementation Of A Real-Time Scheduling Model

Real-time systems are those in which the correctness of the system depends not only on the logical results of computation but also on the time at with the results are produced. The purpose of real-time task scheduling is to arrange the execution of tasks properly, so as to ensure all tasks or at least most tasks can meet their timing requirements [Stankovic 92]. Real-time scheduling algorithm is the key point of real-time system development.Among the various real-time scheduling schemes, Deadline Monotonic Scheduling has become a backbone technique of real-time system development because of its static optimal quality and its advantages such as easy to implement and having extensive possible applications. In this thesis Deadline Monotonic technique is detailedly discussed and researched, and a real-time scheduling model based on this technique (hereafter refer to as Real-time Task Scheduler), which can be used as a reference model of real systems, is developed and discussed. The main topics of the thesis are listed below: The current research status of real-time scheduling theories is discussed. Popular scheduling algorithms, including static scheduling algorithms such as Rate Monotonic Analysis (RMA), Deadline Monotonic Analysis (DMA), and dynamic algorithms such as Earliest Deadline First Algorithm (EDF), Least Leisure First Algorithm (LLF) etc., and their strong points and weakness are discussed. Deadline Monotonic Algorithm is studied from several perspectives including the development history of the theory, the scheduability test algorithm, priority inversion solutions, aperiodic task handling etc. And 2 important conclusionsof the theory: static optimal property and the sufficient and necessary feasibility test, are discussed in proof form. These are the theoretical basis of the task scheduler. The design considerations and critical algorithms in Real-time Task Scheduler are discussed in detail. In the Scheduler real-time tasks are divided in to 2 subsets: a ScheduableTasks in which task feasibility can be guaranteed and a ManageableTasks in which task feasibility is not theoretical guaranteed. Discriminating scheduling policies are applied to the 2 subsets. Real-time tasks are also categorized 2-dimentionally by arrival pattern (periodic tasks vs. aperiodic tasks) and deadline type (hard real-time tasks, firm deadline tasks, etc.), and the policies to implement Deadline Monotonic Algorithm on these types of tasks are discussed. Among the critical algorithms the technique of dividing task set in .to ScheduableTasks and ManageableTasks, the algorithm of maximizing ScheduableTasks, and the algorithm of optimizing hard real-time tasks are originated by the author. The ManageableTasks which feasibility is not theoretically guaranteed, is scheduled by a mechanism originally used in StarBase [Kim 97] real-time database system. Considerations of implementing the Real-time Task Scheduler on real systems and potential improvements of the Scheduler are discussed.The thesis is organized as follows: Chapter 1 is an introduction to the research background; Chapter 2 is the theoretical part which includes a summary of real-time scheduling algorithms and the researches of Deadline Monotonic theory; Chapter 3 proposes the design considerations and objectives of the Real-time Task Scheduler, and introduces the experiment platform QNX real-time operating system; the design and implementation of the Scheduler are discussed in detail in Chapter 4; Chapter 5 summarizes the thesis and discusses applying the scheduler on real systems and its future improvements.