ページ置換アルゴリズム、LRU

ページ置換アルゴリズム

もしこのプロセスがもっと具体的であればvalidbit 0に変えて、~FIFOはなぜ採用されないのか!
プロセスが特定のページを必要とする場合、ページングシステムはそのページを物理メモリにロードする必要があります.
メモリに必要なページがある場合はうまくいきますが、ない場合は問題が発生します.処理するページがない場合は、ページポーリング(ページ障害)が発生し、ハードディスク(HDD)で必要なページを検索して空のフレームにロードします.再ページできる空のフレームがない場合は、問題が発生する可能性があります.
このとき、更新するページと置換する犠牲フレームを検索するアルゴリズムがページ置換アルゴリズムである.

LRU(Least-Recently-Used)

最も長い間使用されていないページを直訳するアルゴリズム.
最適アルゴリズムは実際に実装できないため,採用した方法は最適アルゴリズムの方式に相当する.
最適なアルゴリズムは、ページの使用時間を事前に知ることです.事前に理解できない場合は、過去のデータに基づいてページの使用時間を予測して置き換えることができます.最も長く使用されていないページを予測メソッドで置き換えます.
LRUは最適アルゴリズムよりもページ交換率が高いが、FIFOアルゴリズムよりも効率的である.
LRUアルゴリズムは多くのオペレーティングシステムで採用されているアルゴリズムであり、良いアルゴリズムとされている.

(2,0,1)については、最長時間未使用の1を3に置き換えます.

の5番目(2,0,3)では、ページに長く滞在している0がなぜ置き換えられ、2が4に置き換えられるのか疑問に思うかもしれません.これは、0が現在のページポーリングではなく、実際に使用されているページであるためです.3までに0の意味を参考に

実際のエンコーディングテストケース

2018ココア公債初回キャッシュ

function solution(cacheSize, cities) {
    let answer = 0;
    const cache = [];
    
    while(cacheSize !== 0 && cities.length !== 0){
        const city = cities.shift().toLowerCase();
        const idx = cache.findIndex((x)=>(x === city));
        if(idx === -1){
            if(cache.length >= cacheSize)
                cache.shift();
            answer = answer + 5;
        }
        else{
            cache.splice(idx, 1);
            answer = answer + 1;
        }
        cache.push(city);
    }
    return cacheSize === 0 ? cities.length * 5 : answer;
}

参考資料

bruney.log