Towards virtual memory support in real-time and memory-constrained embedded applications: the interval page table

A novel page table organisation for real-time and memory-constrained embedded system is presented. Increasingly many high-end embedded processors offer virtual memory support in the form of hardware memory management unit, which is responsible for caching and rapidly looking-up the address mapping required to access memory. However, to completely implement virtual memory support the system software needs to maintain a page table per task, which goal is to capture the virtual to physical page translation information for the entire address space. Page tables have been traditionally designed for general-purpose systems where their size and real-time performance have not been of primary importance; the average performance of page table traversal has been the major concern. Many embedded systems, however, impose strict real-time requirements coupled with limited memory resources. To address these problems, a novel page table organisation is proposed, which not only requires significantly less memory than the traditional page tables, but also enables a rapid and deterministic hardware-based page table traversal. This is achieved by exploiting application knowledge regarding the memory footprint of the program under execution and, in particular, the fact that often times large sequences of consecutive virtual pages are mapped to a non-fragmented region in physical memory comprising of consecutive physical memory frames.