Font Size: a A A

Research On Scheduling Algorithms Of Soft Real-Time System Tasks

Posted on:2005-09-01Degree:DoctorType:Dissertation
Country:ChinaCandidate:G TuFull Text:PDF
GTID:1118360152969125Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
The real-time system has characters such as response in time, high dependability, dedication and less artificial interference, it is widely applied in the industrial control, military defense, information communication, network delivering and multimedia processing. The wide applications of real-time technology urge the research direction developing much deeper. Presently, research of soft real-time system is gradually becoming one of the most important parts of the real-time system research work. The category of the soft real-time system research is numerous, which bring new challenges upon the research of real-time theories. Moreover, new applications bring challenges upon tradition frame of real-time theories. For this reason, the researches of real-time theories need to be enlarged to adapt to the new challenges.The hard periodic task and soft aperiodic task are two basic types of real-time task; their hybrid scheduling is an important part of real-time research. To efficiently schedule hard periodic task and soft aperiodic task, the scheduling characters of hard periodic task set scheduled by Earliest Deadline First algorithm is analysised, and then two definitions of "scheduling" and "converse scheduling" with their operating rules are given out. These two definitions and the operating rules are used to describe the process of Earliest Deadline First scheduling and can be used to compute the max idle time. Using the definitions and operating rules, an algorithm is presented for scheduling soft aperiodic tasks in a real-time system in which hard periodic tasks are scheduled by Earliest Deadline First algorithm. The algorithm based on the max idle time that can be moved from periodic tasks which is inferred from the definitions of "scheduling" and "converse scheduling" using their operating rules. To guarantee deadlines, hard real-time systems usually over-provide system resources and adopt various scheduling algorithms, this will waste much resources and cause complex system structure. However, in soft real-time systems, the over-provide resources and complex system structure is not necessary. Flexible real-time scheduling model is use to reduce over-provide resources and simplify system structure. A flexible real-time scheduling algorithm that can make full use of resources and decrease system complexity is presented. This flexible scheduling algorithm integrates the feedback control theory and the spring scheduling theory, and can adjust the parameters of tasks to ensure the schedulability of tasks and keep the CPU load at high degree. Experiment result show than the flexible real-time scheduling algorithm can efficiently decrease the fluctuation of system CPU load and keep CPU load at high degree.To accurate describe the real-time characteristic of soft tasks, the concept and analysis method of weakly hard real-time is introduced. The concept and analysis method of weakly hard real-time can be used to quantitative analysis the properties of soft real-time tasks. Its advantage is that it can accurately define the degree of the "soft" property of soft real-time tasks.To scheduling soft tasks with weakly hard real-time constraint, firstly, the characters of μ-pattern and weakly hard real-time constraints are analysised, then two dynamic scheduling algorithms Meet Any Algorithm and Meet Row Algorithm based on the analysis of weakly hard real-time constraints are presented. These two algorithms try to find out the probabilities of tasks breaking constraints, then increase task's priority in advance. The algorithms can increase task's priority even if there are not (m-1) finished invocations; therefore, tasks have more chances to increase priority and avoid breaking constraints. These scheduling algorithms are different from traditional real-time scheduling algorithms. Traditional real-time scheduling algorithms are used to guarantee single deadline, while scheduling algorithms based on weakly hard real-time constraint are used to guarantee not only single deadlines but also co...
Keywords/Search Tags:scheduling, soft real-time, hard real-time, hybrid scheduling, flexible scheduling, weakly hard real-time scheduling
PDF Full Text Request
Related items