On The Scheduling Theory Of Real-time System With Space Restriction;陶胜达

As a model of mathematics,real-time multiprocessor system characterize lots of physical and social practical problems and have widely application in various fields.Accordingly, the task scheduling theory become a core question of real-time system.In the present, few literatures have considered the space factor of task scheduling theories.But it is indeed important and can not be avoided in practice.The space factor has been introduced into real-time multiprocessor system in the literature of [6-8] and the authors firstly constructed the task scheduling model of real-time multiprocessor system with space factor.The thesis,based on the model, mainly focus on the scheduling algorithms properties and time-space utilization of the real-time parallel model, LCM model,PCM model.The study in this thesis focus on the following areas:Because the scheduling algorithm about real-time parallel model of literatures [7] can not guarrantee that time priority of the key task and may cause low utilization for each Ci/Ti value, a new scheduling algorithm is proposed.The new algorithm is based on EDF and it has improved the algorithm in [7].On the basic of LCM in the literature of [6], the properties of Greedy Algorithm and Cyclic Algorithm are dicussed.We have obtained and proved a theorem:the time-space utilization of Greedy Algorithm and Cyclic Algorithm based on LCM can both reach (2k-1)/2k.This result is of theoretical significance.According to the diversity of space occupation di (t) about task pi and the typical case of parobolicly decrease of space occupation, the Parabolic Concurrent Model (PCM) is proposed.The properties and time-space utilization about PCM and Greedy Algorithm (GA) based on PCM are dicussed. We obtain the following theorems:Theorem 5.2.1 For the GA based on PCM and (?)k≥2, k∈N, the time-space utilization of system is eG=(2k-1)/2k.Theorem 5.2.2 For the GA based on PCM and (?)k≥2, k∈N, the average of executing task numbers is N_k=[3(2k-1)/4]. Theorem 5.2.3 For the GA based on PCM and (?)k≥2, k∈N, there exists an inverval t0, the system will cut a task at intervals of t0 when the system has stabilized, then the t0 isTheorem 5.3.1 (2k-1)/2k is its upper bound of time-space utilization for all the valid scheduling algorithm of PCM.