Category: Chirag Patel

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.

Checking double precision value for limits is tricky.

Say,

double x = 1.0;
if ( x == 1.0 ) do_something();

This comparison can fail as double precision value when converted to hexadecimal (what computer can do only) representation, looses some least significant bits or positions beyond double precision digits. So, in above example if ( x == 0.9999999 ) might have worked depending on compiler and/or CPU. Therefore, in programming, we create functions to check such limits to approximate values.

// Used for double type comparasion
typedef union mydouble_ {
    double dbl_val;
    unsigned long un_u32_val[2];
    unsigned char un_u8_val[8];
} mydouble;

// Checks double value against close enough limits i.e. min <= val <= max
// Return: -1 => val < min
// Return: 0 => min <= val <= max
// Return: 1 => val > max
int my_double_limit_check( double val, double min, double max )
{
    mydouble dbl;
    mydouble cmp;
    int ret = 0;
 
    if ( val < min )
    {
        dbl.dbl_val = val;
        cmp.dbl_val = min;
        if ( dbl.un_u32_val[0] != cmp.un_u32_val[0] )
            ret = -1;
        else if ( dbl.un_u8_val[4] != cmp.un_u8_val[4] )
            ret = -1;
    }
 
    if ( val > max )
    {
        dbl.dbl_val = val;
        cmp.dbl_val = max;
        if ( dbl.un_u32_val[0] != cmp.un_u32_val[0] )
            ret = 1;
        else if ( dbl.un_u8_val[4] != cmp.un_u8_val[4] )
            ret = 1;
    }
 
    return ret;
}
 
// Checks double value against close enough less value i.e. val < min
// Return: -1 => val < min
// Return: 0 => val >= min
int my_double_less_check( double val, double min )
{
    mydouble dbl;
    mydouble cmp;
    int ret = 0;
 
    if ( val < min )
    {
        dbl.dbl_val = val;
        cmp.dbl_val = min;
        if ( dbl.un_u32_val[0] != cmp.un_u32_val[0] )
            ret = -1;
        else if ( dbl.un_u8_val[4] != cmp.un_u8_val[4] )
            ret = -1;
    }
 
    return ret;
}
 
// Checks double value against close enough greater value i.e. val > max
// Return: 1 => val > max
// Return: 0 => val <= max
int my_double_greater_check( double val, double max )
{
    myouble dbl;
    myouble cmp;
    int ret = 0;
 
    if ( val > max )
    {
        dbl.dbl_val = val;
        cmp.dbl_val = max;
        if ( dbl.un_u32_val[0] != cmp.un_u32_val[0] )
            ret = 1;
        else if ( dbl.un_u8_val[4] != cmp.un_u8_val[4] )
            ret = 1;
    }
 
    return ret;
}
 
// Checks double value against close enough equal value i.e. val == eql
// Return: 0 => val == eql
// Retrun: 1 => val != eql
int my_double_equal_check( double val, double eql )
{
    mydouble dbl;
    mydouble cmp;
    int ret = 0;
 
    if ( val != eql )
    {
        dbl.dbl_val = val;
        cmp.dbl_val = eql;
        if ( dbl.un_u32_val[0] != cmp.un_u32_val[0] )
            ret = 1;
        else if ( dbl.un_u8_val[4] != cmp.un_u8_val[4] )
            ret = 1;
    }
 
    return ret;
}

Uses my_double_greater_check from http://rutmandal.info/double-precision-comparison-in-cc/

double my_double_round( double val, int multiplier )
{
         double val_adj = val * multiplier;
         if ( my_double_greater_check( val_adj floor( val_adj ), 0.0 ) > 0 )
                      val = round( val_adj ) / multiplier;
         return val;
}

round and floor are C math library <math.h> functions.

E.g.

double rnd_val = my_double_round( 0.000998, 1000);

rnd_val will be 0.001