Performance Evaluations and Estimations of Workload of On-Demand Updatesin Soft Real-Time Systems∗Thomas Gustafssona,band J¨orgen Hanssonb,caSchool of Engineering, J¨onk¨oping University, SwedenbDepartment of Information and Computer Science, Link¨oping University, SwedencSoftware Engineering Institute, Carnegie Mellon University, USAE-mail: [email protected], [email protected] being used in real-time systems must be up-to-dateto produce correct results. The use of outdated data canhave catastrophic consequences since calculated controlsignals are based on stale data. Two distinct methods to up-date data exist: (i) dedicated tasks (DT) update data items,and (ii) on-demand (OD) updating being a conditioned partof the execution flow of tasks. On-demand updating hasnot been studied in terms of CPU utilization analysis forreal-time systems. This paper studies on-demand updatingin terms of (i) imposed workload and compares the work-load to Deferrable Scheduling (DS), and (ii) analytical for-mula for estimating workload to be used in CPU utiliza-tion based schedulability tests. It is found that on-demandupdating uses less workload for updates compared to DS,which suggests on-demand updating should be used for re-source constrained systems. However, using on-demand up-dating makes the execution times of updates unpredictable,which currently gives two possibilities (i) be pessimistic andassume all updates always execute or (ii) be less pessimisticbut estimate the times between executions of updates. Thispaper devises a formula for such estimates and comparestheir result to approach (i). Evaluations show the formulacan be useful for soft real-time systems.1 IntroductionMany applications, but not limited to only real-time sys-tems, need up-to-date data items. Data reflects values of en-tities where physical limitations, e.g., that the speed changeof piston movement in an engine is bounded, indicate howlong time data values can be considered to be up-to-date.∗This work was funded by ISIS (Information Systems for IndustrialControl and Supervision) and CENIIT (Center for Industrial InformationTechnology) under contract 01.07.Thus, a data item dican be associated with an absolute va-lidity interval, AV I(di), stating how old values are allowedto be [12]. Now, a straightforward method to ensure a dataitem is up-to-date is to use a periodic dedicated task updat-ing the data item and set the task’s period time to half its ab-solute validity interval. Using this approach, the maximumdistance between two updates is AV I(di) since the updatecan occur at the beginning of one period and at the end ofthe following period [12, 15]. This method is denoted Half-Half (HH). There are two important questions now: (Q1) Isthe system, including dedicated tasks performing updates,schedulable? (Q2) What is the imposed workload of theupdates?There is a correlation between the two questions above.If the workload of updates is high it might render the sys-tem unschedulable. In the context of a hard real-time sys-tem, the first question is the most important. The secondquestion is of interest for soft real-time systems or general-purpose systems since an under/overloaded classification issometimes allowed to be wrong because deadline missescan be tolerated. The workload approach might be bothcomputationally cheaper to calculate compared to checkingschedulability and less pessimistic. One way to calculateworkload is to use an estimation technique. If estimationtechniques are fast and accurate enough they could be usedin on-line CPU utilization based schedulability tests. Thispaper investigates possible estimation techniques and theiraccuracy.Performance evaluations in this paper show that on-demand updating imposes less workload compared to De-ferrable Scheduling (DS), which is the, to date, algorithmreducing workload imposed by dedicated updating tasks themost [13, 14]. This finding suggests that on-demand up-dating of data items is a strategy suitable for resource con-strained embedded systems. However, on-demand updatingin periodic tasks makes the updating activity event-based,because when updates occur depends on (i) the period times13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications(RTCSA 2007)0-7695-2975-5/07 $25.00 © 2007and phasings of tasks issuing on-demand updating and (ii)the condition that must be fulfilled in order to execute theupdate. This affects the possibility to answer questions Q1and Q2. This paper presents methods—in the context of on-demand updates in periodic tasks—to give fast estimates ofQ2. The contributions are:• A formula that answers Q2 by estimating the mean in-terarrival times of executions of an on-demand updatethat uses AVI to measure data freshness. The formulacalculates the estimation by using a probability densityfunction of distances between arrival times of a set oftasks. The formula looks as follows and it is presentedin Section 4:MIT(y, P) =E[P] − Q(y, P)Ry0q(x, P)xdx1 − Q(y, P).The probability density function (pdf), q(y, P), de-scribes the distances between arrival times of a set Pof tasks. The pdf, in the case of periodic tasks, can bedescribed by a result of Cox and Smith [4].• Performance evaluations show that the estimationgiven above is fast and give accurate values. Further,the evaluations show that the workload imposed by up-dates is lower when using on-demand updates com-pared to using dedicated tasks scheduled by DeferrableScheduling.The outline of this paper is as follows: Section 2 givesrelated work. Section 3 presents the data and task modelused in this paper and gives some background on schedula-bility tests. Section 4 gives an analytical formula for meaninterarrival time of execution of on-demand updates. Sec-tion 5 presents evaluations of the accuracy of the derivedformula. Finally, Section 6 concludes the paper.2 Related Work and MotivationIn the area of real-time systems, keeping data values up-to-date has previously been studied. As discussed in the in-troduction, there are two ways to determine when to updatea data item: either by a dedicated task (DT) executed oftenenough, or on-demand (OD). Also, two ways to measuredata freshness have been devised, namely (i) time domain(TD), e.g., AVIs, and (ii) value domain (VD), e.g., similar-ity. Thus, there are four ways to configure a system withrespect to updating data items: DT+TD, DT+VD, OD+TD,and OD+VD. We now describe