Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-24
2002-05-21
Jung, David (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C709S241000, C709S241000
Reexamination Certificate
active
06393433
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods and apparatus for evaluating software run-time schedulers and, more particularly, to quantifying the impact of software run-time schedulers on the performance of software applications running on embedded multimedia end-systems.
BACKGROUND OF THE INVENTION
Embedded multimedia end-systems, such as, for example, personal digital assistants (PDAs), set-top boxes, and Internet terminals, often need to support multiple concurrent tasks such as, for example, audio, speech, video, graphics, and modem. While such end-systems typically have limited processing capability, they are being used to support increasingly sophisticated multimedia applications.
Multimedia applications typically impose real-time processing constraints. In other words, such applications have to finish processing within a certain time deadline. However, such applications can tolerate a small number of misses when the processing takes longer than the prescribed deadline. A multimedia application may have a performance constraint such as, for example, “no more than 5% of deadlines may be missed.” Such a constraint is referred to as a soft deadline constraint. End-systems typically support multimedia applications with soft deadlines through sophisticated software run-time schedulers.
One way a run-time scheduler supports multiple applications is through first-come first-serve (FCFS) scheduling, where each application gets its turn in order of arrival of the application. However, such a scheduling discipline may not allow the end-system to support applications with distinct deadlines. Consequently, there is a trend toward use of more sophisticated schedulers which allow priorities to be specified for applications. Earliest deadline first (EDF) and rate monotonic (RM) scheduling are examples of priority-based scheduling.
Given a particular architecture of an embedded system and a set of applications, it is unclear whether a particular run-time scheduler can support the multimedia applications adequately. There is no known method or apparatus which analytically computes the impact of different priority-based run-time scheduling policies on the performance of multimedia applications in terms of the soft deadline performance. Further, it is often necessary to control these schedulers in order to support the multimedia applications efficiently.
It is known that simulation may be used as a tool for predicting the performance of end-systems. However, simulation is inherently computation-intensive and, thus, time consuming, especially when thousands of runs are required in gathering statistics such as how often a deadline is missed. Alternatively, other conventional methods such as rate-monotonic analysis (RMA) can not be used when applications have soft deadlines or variability, as is the case with multimedia applications.
SUMMARY OF THE INVENTION
The invention provides methodology and apparatus for calculating the performance of one or more applications running on an end-system which has been configured with a particular run-time scheduling policy.
In one aspect of the invention, a method of evaluating an effect of a run-time scheduling policy on a performance of an end-system, having associated resources, running one or more applications, each application having one or more tasks and the tasks being mapped to the associated resources of the end-system, is disclosed. The method includes generating a state process having a state space representative of an evolution of computation associated with the end-system, the evolution being representative of task transitions with respect to the applications, available resources and the run-time scheduling policy. Then, given the state space generated with respect to, among other things, the specified run-time scheduling policy, the method includes computing performance metrics from the state process, the performance metrics being representative of the effect of the run-time scheduling policy on the performance of the one or more applications running on the end-system. The invention preferably calculates the performance in terms of the probability distribution of the processing delay of each application and a deadline miss probability. Such performance metrics may be used to influence the behavior of the run-time scheduler in the system in order to ensure that all applications get their due share of the end-system resources.
Advantageously, the methodology and apparatus of the invention can be used to control the run-time scheduler on the end-system so that it can provide adequate support to applications running on the end-system. In a preferred embodiment, the applications are multimedia applications and the end-system is an embedded end-system. The run-time scheduling policies may be priority-based, e.g., RM and EDF, or nonpriority-based, e.g., FCFS.
REFERENCES:
patent: 6201996 (2001-03-01), Crater et al.
patent: 6263358 (2001-07-01), Lee et al.
C.L. Liu et al., “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” JACM, vol. 20, pp. 46-61, 1973.
K. Ramamritham et al., “Scheduling Algorithms and Operating Systems Support for Real-Time Systems,” Proc. of the IEEE, vol. 82, No. 1, pp. 55-66, Jan. 1994.
L. Sha et al., “Generalized Rate-Monotonic Scheduling Theory: A Framework for Developing Real-Time Systems,” Proc. of the IEEE, vol. 82, No. 1, pp. 68-82, Jan. 1994.
D.I. Katcher et al., “Engineering and Analysis of Fixed Priority Schedulers,” IEEE Trans. of Software Engg., pp. 1-16, Sep. 1993.
K. Jeffay et al., “On Non-Preemptive Scheduling of Periodic and Sporadic Tasks,” Proc. of Real-Time Systems Symposium, pp. 129-139, 1991.
J.V. Busquets-Matiax et al., “Adding Instruction Cache Effect to an Exact Schedulability Analysis of Preemptive Real-Time Systems,” 8th Euromicro Workshop on Real-Time Systems, Jun. 1996.
R. Yavatkar et al., “A CPU Scheduling Algorithm for Continuous Media Applications,” 5th Intl. Workshop on Network and OS Support for Digital Audio and Video (NOSS-DAV), pp. 223-226, Apr. 1995.
C.W. Mercer et al., “Processor Capacity Reserves: Operating System Support for Multimedia Applications,” IEEE Intl. Conf. on Multimedia Computing and Systems, pp. 90-99, May 1994.
R. Gopalakrishnan et al., “Bringing Real-time Scheduling Theory and Practice Closer for Multimedia Computing,” Proc. of 1996 ACM SIGMETRICS Intl. Conference on Measurement and Modeling of Computer Systems, Philadelphia, PA, USA, pp. 1-17, May 1996.
S. Chatterjee et al., “A Generalized Admissions Control Strategy for Heterogeneous, Distributed Multimedia Systems,” Proc. of ACM Multimedia, pp. 1-12, 1995.
H.M. Vin et al., “A Statistical Admission Control Algorithm for Multimedia Servers,” Proc. of ACM Multimedia, pp. 33-40, 1994.
J. Kim et al., “Execution Time Analysis of Communicating Tasks in Distributed Systems,” IEEE Trans. on Computers, vol. 45, No. 5, pp. 572-579, May 1996.
Y.A. Li et al., “Estimating the Execution Time Distribution for a Task Graph in a Heterogeneous Computing System,” Proc. Sixth Heterogeneous Computing Workshop (HCW) Geneva, Switzerland, pp. 172-184, 1997.
P. Moghe et al., “Terminal QoS of Adaptive Applications and its Analytical Computation,” Proc. of 5th Intl. Workshop on Quality of Service (IWQoS97), pp. 1-12, May 1997.
Y.S. Li et al., “Performance Estimation of Embedded Software with Instruction Cache Modeling,” ICCAD, 1995.
Kalavade Asawaree
Moghe Pratyush
Jung David
Lucent Technologies - Inc.
Ryan & Mason & Lewis, LLP
LandOfFree
Methods and apparatus for evaluating effect of run-time... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for evaluating effect of run-time..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for evaluating effect of run-time... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896253