A methodology to compute task remaining execution time

Scheduling can require analyzing not only the total computation time of a task, but also the remaining execution time, R(t)_Δt, after accumulated time Δt. Often a software program´s execution time is characterized by a single value (mean). When scheduling is based on partial execution (a common scenario in multimedia systems) a more accurate estimation of remaining time (R(t)_Δt) is desired than can be obtained from just the initial mean value, in order to have effective scheduling decisions. The remaining time approach can provide more accurate estimation, and therefore more effective scheduling, in time-sensitive situations. We developed an analytical model for computing expected remaining execution time, (R(t)_Δt)~ , of software programs from their execution time and probability distributions. To implement the equations, we further designed an algorithm that computes (R(t)_Δt)~ for operating system scheduling applications. We proved that the real time execution complexity of the algorithm is O(1) and is, therefore, independent of the size of the distribution. Our method of more accurate estimate of (R(t)_Δt)~ implies expect better scheduling performance in applications where remaining execution time is used, especially in CPU scheduling.