Abstract
We propose a technique for finding the worst case response time (WCRT) of a DMA request that is needed in the schedulability analysis of a whole real-time system. The technique consists of three steps. In the first step, we find the worst case bus usage pattern of each CPU task. Then in the second step, we combine the worst case bus usage patterns of CPU tasks to construct the worst case bus usage pattern of the CPU. This second step considers not only the bus requests made by CPU tasks individually but also those due to preemptions among the CPU tasks. Finally, in the third step, we use the worst case bus usage pattern of the CPU to derive the WCRT of DMA requests assuming the fixed-priority bus arbitration protocol. Experimental results show that overestimation of the DMA response time by the proposed technique is within 20% for most DMA request sizes and that the percentage overestimation decreases as the DMA request size increases.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Sethi, R., and Ullman, J. D. 1988. Compilers Principles, Techniques, and Tools. Reading, MA: Addison-Wesley Publishing Company.
Burns, A., Tindell, K., and Wellings, A. 1995. Effective analysis for engineering real-time fixed priority schedulers. IEEE Transactions on Software Engineering 21(5): 475-480.
Fischer, C. N., and LeBlanc, R. J. 1991. Crafting a Compiler with C. Redwood City, CA: The Benjamin/Cummings Publishing Company, Inc.
Huang, T.-Y. 1997. Worst-case timing analysis of concurrently executing DMA I/O and programs. Ph.D. thesis, University of Illinois at Urbana-Champaign.
Joseph, M. and Pandya, P. 1986. Finding response times in a real-time system. The BCS Computer Journal 29(5): 390-395.
Kane, G., and Heinrich, J. 1992. MIPS RISC Architecture. Englewood Cliffs, NJ: Prentice Hall.
Katcher, D. I., Arakawa, H., and Strosnider, J. K. 1993. Engineering and analysis of fixed priority schedulers. IEEE Transactions on Software Engineering 19(9): 920-934.
Kim, S.-K., Min, S. L., and Ha, R. 1996. Efficient worst case timing analysis of data caching. In Proceedings of the Second Real-Time Technology and Applications Symposium, pp. 230-240.
Lam, M. S., and Wilson, R. P. 1992. Limits of control flow on parallelism. In Proceedings of the 19th Annual International Symposium on Computer Architecture, pp. 46-57.
Lee, C.-G., Hahn, J., Seo, Y.-M., Min, S. L., Ha, R., Hong, S., Park, C. Y., Lee, M., and Kim, C. S. 1996. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. In Proceedings of the 17th Real-Time Systems Symposium, pp. 264-274.
Lee, C.-G., Hahn, J., Seo, Y.-M., Min, S. L., Ha, R., Hong, S., Park, C. Y., Lee, M., and Kim, C. S. 1997. Enhanced analysis of cache-related preemption delay in fixed-priority preemptive scheduling. In Proceedings of the 18th Real-Time Systems Symposium, pp. 187-198.
Lehoczky, J. P., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm—exact chracterization and average case behavior. In Proceedings of the 10th Real-Time Systems Symposium, pp. 166-171.
Lim, S.-S., Bae, Y. H., Jang, G. T., Rhee, B.-D., Min, S. L., Park, C. Y., Shin, H., Park, K., Moon, S.-M., and Kim, C. S. 1995. An accurate worst case timing analysis for RISC processors. IEEE Transactions on Software Engineering 21(7): 593-604.
Liu, C. L., and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM 20(1): 46-61.
Park, C. Y. 1993. Predicting program execution times by analyzing static and dynamic program paths. Journal of Real-Time Systems 5(1): 31-62.
Puschner, P., and Koza, C. 1989. Calculating the maximum execution time of real-time programs. Journal of Real-Time Systems 1(2): 159-176.
Rogers, A., and Rosenberg, S. 1993. Cycle level SPIM. Technical Report, Dept. of Computer Science, Princeton University.
Tindell, K. 1994. Adding time-offsets to schedulability analysis. Technical Report YCS 221, Dept. of Computer Science, University of York.
Tindell, K., Burns, A., and Wellings, A. 1994. An extendible approach for analyzing fixed priority hard real-time tasks. Journal of Real-Time Systems 6(2): 133-151.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hahn, J., Ha, R., Min, S.L. et al. Analysis of Worst Case DMA Response Time in a Fixed-Priority Bus Arbitration Protocol. Real-Time Systems 23, 209–238 (2002). https://doi.org/10.1023/A:1020227912579
Issue Date:
DOI: https://doi.org/10.1023/A:1020227912579