Research On Compression And Insertion Of Real-Time Multitasks

The real-time scheduling algorithm is the main part of the real-time system.The pros and cons of the scheduling algorithm are directly related to the performance of the real-time system.This is also a topic that has been the focus of scholars for many years.Liu and Layland proposed the classic EDF(Earliest Deadline First)real-time scheduling algorithm in1973,but this model assumes that the number of tasks is fixed.In order to apply real-time load changes,Buttazzo proposed an elastic scheduling model based on EDF scheduling algorithm in 2002.Although the emergence of this model makes task scheduling more flexible,it also greatly increases the difficulty of research.In addition,Buttazzo claimed to give a formula for the earliest smooth insertion time of the new task(the earliest release time of the new task that will not cause the deadline to be lost).Qian revised the formula in 2009.In fact,the above formula only gives the smooth insertion time of the new task,which is not guaranteed to be the earliest.Moreover,the above and subsequent related documents prove that most research is focused on the case of compressing a single task.The research in this paper is based on compressing multiple real-time tasks simultaneously.First of all,multitasks'compression has been strictly and comprehensively defined,pointing out that is a process of mode-change.The process is divided into three stages:the old mode,the transition process and the new mode.Based on such definitions and patterns,the various stages of new task insertion during the compression of multitasks have been discussed and studied in detail,then given the calculation of the processor demands for multitasks'compression.In particular,the transition process is studied in detail.It is found that the interval is(?)in which deadline possibly missing for multitasks'compression,and proved according to the processor demands criterion.(?)and(?)are respectively the minimum and maximum values of the current deadline of multitasks'compression when the compression ends.This conclusion narrows the research space for the study of smooth insertion time.Finally,the relevant conclusions are supported through the simulation platform.Based on multitasks'compression,this paper also studies the smooth insertion time of new tasks.The processor demands of each task in the task sets are discussed in stages,and based on this,an algorithm for calculating the smooth time is proposed and rigorously proved,analyzing its time complexity.At the same time,the application of the algorithm is also shown in detail through simulation examples.