Memory Thrashing compiled by Chirag Patel December 27, 2008
(Ref: Embedded Systems Design June 2008)
Memory threshing is a typical problem that goes unnotices while programming time-critical systems. Translation Look-aside Buffers (TLB) are used for data and instruction cache. There are two main cache-replacement schemes: 1) Least Frequently Used (LFU) and 2) Least Recently Used (LRU). Memory accesses require address translations in modern systems. So, when a page table is is found in an on-chip TLB (a TLB hit), the lookup normally does not do translation. On TLB miss, the processor must look again and must calculate offset to find a byte physically.
When a system has multiple concurrent accesses, operating system schedules time slices for those processes. If we consider 32-entry LRU TLB and 6 processes each using different page memory, at least 12 pages are active at any given time (instruction + data). If every process uses double nested procedures (or jumps between 3 pages) in each time slice, there are 36 active pages. If operating system time slices sequentially, by the time 6th process is reached, 30 pages are accessed. By the end of 6th process time slice, 36 page accesses should have passed. So, the cache manager will discard first 4 accesses (LRU algorithm). When the time comes for the first process, it will have TLB misses for those first 4 page accesses. As the processor continues, it keeps discarding the pages that the next process in sequence will need. This memory thrashing greatly degrades system performance.
To avoid thrashing:
– Long unused variables should be declared absolutely rather than relatively.
– Macros should be expanded.
– Avoid nesting procedure calls whenever possible.
– Minimize number of concurrent tasks.
– Don’t use jumps larger than page size unless absolutely necessary.