https://en.wikipedia.org/wiki/Locality_of_reference

程序局部性原理

程序的局部性原理是指程序在執(zhí)行時呈現出局部性規(guī)律，即在一段時間內古戴，整個程序的執(zhí)行僅限于程序中的某一部分欠橘。它們傾向于引用的數據項鄰近于其他最近引用過的數據項，或者鄰近于最近自我引用過的數據項现恼。

在現代計算機系統(tǒng)的各個層次肃续，從硬件到操作系統(tǒng)、應用程序等述暂，設計上都利用了局部性原理痹升。比如緩存機制，CPU指令順序處理等畦韭。

局部性通常有兩種形式：時間局部性和空間局部性

時間局部性（temporal locality）

時間局部性是指如果程序中的某條指令一旦執(zhí)行疼蛾，則不久之后該指令可能再次被執(zhí)行；如果某數據被訪問艺配，則不久之后該數據可能再次被訪問察郁。強調數據的重復訪問。

利用時間局部性转唉，緩存在現代程序系統(tǒng)中扮演著重要角色皮钠，數據緩存，磁盤緩存赠法，文件緩存等麦轰，極大提高數據的重復訪問性能。而在程序設計中，循環(huán)體則是時間局部性常見的一個場景

空間局部性（spatial locality）

空間局部性是指一旦程序訪問了某個存儲單元款侵，則不久之后末荐。其附近的存儲單元也將被訪問。強調連續(xù)空間數據的訪問新锈，一般順序訪問每個元素（步長為1）時具有最好的空間局部性甲脏，步長越大，空間局部性越差

在文件系統(tǒng)中的應用

以TinyOS中對文件系統(tǒng)的inode的處理為例
我們在內存中維護一個list妹笆，這個list記錄著所有被打開的inode的信息，如果有一個inode需要被打開拳缠，則優(yōu)先從這個list（內存中）查找墩新，這比從硬盤讀取的效率要高很多脊凰。
而我們新打開的一個inode抖棘，需要加到這個list的頭部茂腥。根據時間局部性狸涌，這個inode很有可能在不久就會再一次被訪問沼撕。這里就運用了程序局部性原理谢揪。
一個inode_open函數的實現

// return the inode according to the inode number
PINODE inode_open( PPARTITION part, uint32_t inode_no ) {
    // firstly find inode in the open_inodes list
    // store in memory in order to increase speed
    PLIST_NODE elem = part->open_inodes.head.next;
    PINODE inode_found;
    while ( elem != &part->open_inodes.tail ) {
        inode_found = elem2entry( INODE, inode_tag, elem );
        if ( inode_found->i_number == inode_no ) {
            inode_found->i_open_cnts++;
            return inode_found;
        }
        elem = elem->next;
    }

    // since cannot find inode in open_inodes list, we load it from disk and add to open_inodes list
    INODE_POSITION inode_pos;

    // get inode position
    inode_locate( part, inode_no, &inode_pos );

    // temporarily claer pgdir to malloc kernel memory for inode to share with all app
    // when we free this inode, we should clear pgdir as well.
    PTASK_STRUCT cur = running_thread();
    uint32_t* cur_pagedir_bak = cur->pgdir;
    cur->pgdir = NULL;
    inode_found = ( PINODE )sys_malloc( sizeof( INODE ) );
    // recover pgdir
    cur->pgdir = cur_pagedir_bak;

    char* inode_buf;
    if ( inode_pos.two_sec ) {
        // cope with two sectors
        inode_buf = ( char* )sys_malloc( 1024 );

        ide_read( part->my_disk, inode_pos.sec_lba, inode_buf, 2 );
    } else {
        // cope with one sector

        inode_buf = ( char* )sys_malloc( 512 );
        ide_read( part->my_disk, inode_pos.sec_lba, inode_buf, 1 );
    }
    memcpy( inode_found, inode_buf + inode_pos.off_size, sizeof( INODE ) );

    // according to the Locality_of_reference, we add this inode to the front of the open_cnts lists
    list_push( &part->open_inodes, &inode_found->inode_tag );
    inode_found->i_open_cnts = 1;

    sys_free( inode_buf );
    return inode_found;
}