バックグラウンド面接の定番質問-手書きLRUアルゴリズム

LRU、Least Recently Usedは、最近最も長く使用されていません.ページ置換アルゴリズムでよく使用されます.仮想ページストレージ管理サービスです.
メモリに使用されないデータ・ブロックをLRUと呼び、オペレーティング・システムは、どのデータがLRUに属しているかに基づいてメモリから削除します.
 
オペレーティングシステムのメモリ管理では、容量の少ないメモリをどのように節約して最も多くのプロセスにリソースを提供するかが研究の焦点となっています.メモリの仮想ストレージ管理は、現在最も一般的な方法です.メモリが限られている場合、一部の外部メモリを仮想メモリとして拡張します.仮想ページストレージ管理は、プロセスに必要なスペースを複数のページに分割し、メモリに現在必要なページのみを格納し、残りのページを外部メモリに格納する管理方式です.ページ置換アルゴリズムでは、欠ページ割り込みが発生した場合、メモリから不要なブロックを見つけて(物理メモリの解放に対応)、ディスクの交換領域からページを交換する必要があります(仮想メモリの割り当て).
 
 
システムのすべてのファイルI/O要求に対して、オペレーティングシステムはpage cacheメカニズムによって実現され、オペレーティングシステムにとって、ディスクファイルは一連のデータブロックの順序から構成され、データブロックのサイズはシステムによって異なり、x 86 linuxシステムの下では4 KB(標準ページサイズ)である.カーネルは、ファイルI/O要求を処理する際に、まずpage cacheで検索し(page cacheの各データブロックにファイルおよびオフセット情報が設定されている)、ヒットしない場合はディスクI/Oを起動し、ディスクファイルのデータブロックをpage cacheの空きブロックにロードする.その後、ユーザーバッファにコピーします.
 
LRU実装:map+双方向チェーンテーブル

class LRUCache {
private:
    typedef list LI;
    typedef pair PII;
    typedef unordered_map HIPII;
    
    void touch(HIPII::iterator it) {
        int key = it->first;
        used.erase(it->second.second);
        used.push_front(key);
        it->second.second = used.begin();
    }
    
    HIPII cache;
    LI used;
    int _capacity;


public:
    LRUCache(int capacity) : _capacity(capacity) {}
    
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) return -1;
        touch(it);
        return it->second.first;
    }
    
    void put(int key, int value) {
        auto it = cache.find(key);
        if (it != cache.end()) touch(it);
        else {
			if (cache.size() == _capacity) {
				cache.erase(used.back());
				used.pop_back();
			}
            used.push_front(key);
        }
        cache[key] = { value, used.begin() };
    }
    
};