Predictable Paging in Real-Time Systems: A Compiler Approach
Authors:
- 1 July 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 19th Euromicro Conference on Real-Time Systems (ECRTS'07)
- No. 10683070,p. 169-178
Abstract
Conventionally, the use of virtual memory in real-time systems has been avoided, the main reason being the difficulties it provides to timing analysis. However, there is a trend towards systems where different functions are implemented by concurrent processes. Such systems need spatial separation between processes, which can be easily implemented via the use of the memory management unit (MMU) of commercial processors. In addition, some systems have a limited amount of physical memory available. So far, attempts to provide real-time address spaces have focused on the predictability of virtual to physical address translation and do not implement demand-paging. In this paper we propose a compiler approach to introduce a predictable form of paging, in which page-in and page-out points are selected at compile-time. The problem under study can be formulated as a graph coloring problem, as in register allocation within compilers. Since the graph coloring problem is NP-complete for more than three colors, we define a heuristic, which in contrast to those used for register allocation, aim at minimizing worst-case performance instead of average-case performance. Experimental results applied on tasks code show that predictability does not come at the price of performance loss as compared to standard (dynamic) demand paging.Keywords
This publication has 10 references indexed in Scilit:
- Approximating the optimal replacement algorithm2004
- The influence of processor architecture on the design and the results of WCET toolsProceedings of the IEEE, 2003
- A modular and retargetable framework for tree-based WCET analysis2002
- Predictable and efficient virtual addressing for safety-critical real-time systems2002
- Reliable and Precise WCET Determination for a Real-Life Processor2001
- Timing Analysis for Instruction CachesReal-Time Systems, 2000
- A dynamic programming algorithm for cache memory partitioning for real-time systemsIEEE Transactions on Computers, 1993
- Register allocation & spilling via graph coloring1982
- Operating Systems: Program overlay techniquesCommunications of the ACM, 1968
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966