2
O(1)（つまり一定の時間）にLRU（過去に使用された）ページ置換アルゴリズムを取得できますか？O（1）でLRU（least recently used）ページ置換アルゴリズムを取得できますか？
可能であれば、アルゴリズムを与えてください。
A
答えて
2
二重リンクリストは、O（1）操作でLRUキューを実装できます。使用されたノードは、元の位置からリンク解除され、一定時間内にキューの先頭に再リンクすることができます。
ページ置換方法として使用する場合は、MMUの統計情報を使用してキューを効率的に更新する方法を理解する必要があります。
+0
良い答えですが、質問者には、このメソッドが実際にどのOSでも使用されていないということを指摘したかったのです。 –
+0
ええ、実際にページが使用された順序は気にしません。あなたが望むものは、「最近使用されたことのない」ページのリストであり、必要に応じて追い出すことができます。実際には、MMUのページアクセスフラグを使用してページ置換統計をバッチスタイルで更新しますが、二重リンクLRUキュー*はこの目的のための実用的なデータ構造です。 – comingstorm
+0
しかし、使用されたノード私たちは好きなリストをたどる必要があります... O（n）時間がかかります.....間違っていれば私を修正してください。 – Amnesiac
0
ウィキペディアには、実装とのリンクを含む、references〜いくつかのLRUページアルゴリズムがあります。オプションは次のとおりです。
- リンクリスト
- LRU-K
- ARC
- ハードウェアサポート
関連する問題
- 1. ページ置換アルゴリズム：FIFO、LRU最適化
- 2. mysql random number least used
- 3. プログラムでVS2017 MRU（Most Recently Used）ソリューションとプロジェクトを見つける
- 4. Pythonは1ページ目でHrefリンクを取得し、2ページ目から段落を取得できますか？
- 5. ここでLRUとFIFOのページ置換が正しく行われていますか？
- 6. このO（n^4）アルゴリズムは回避できますか？
- 7. WSclockのページ置き換えアルゴリズムと時計のチック
- 8. Java置換アルゴリズムのアルゴリズム？
- 9. O（1）時間にテーブルから行数を取得できますか？ SQL Serverで
- 10. FIFOのページ置換戦略がLRUを上回る可能性はありますか？
- 11. O（N）で置き換えのないk個のランダム置換の例
- 12. Codeigniterのページ設定でgetパラメータを置き換えますか？
- 13. JavascriptのアルゴリズムでO（nlogn）
- 14. O（1）、O（n log n）、O（log n）の複雑さを持つアルゴリズムの例
- 15. Sympy：式で "-1"を置き換えますか？
- 16. 複数行の1行をPythonで置き換えますか？
- 17. 1つのwebviewをlistviewで置き換えますか？
- 18. Python I/Oは、行内の単語を置き換えます
- 19. Mvc3を取得するAjax.ActionLinkはJqueryでデータを置き換えましたか？
- 20. このアルゴリズムのbig-O表記法とは何ですか？
- 21. ViewPagerでフラグメントを置き換える - NPEを取得する
- 22. 次の字句の「置換」アルゴリズム
- 23. アルゴリズムのbig O
- 24. ドライバがI/O DMAアダプタを取得できません
- 25. TiffBitmapDecoderからTIFFページを取得できません。フレーム - すべてのフレームが1ページです。
- 26. 別のポートで動作するホットモジュール置換を取得できません
- 27. SendGridのAPI V3で機能する置換を取得できません
- 28. neo4jのノードのO（1）時間内にノードの入出力度を取得できますか？
- 29. このアルゴリズムを1行で実行できますか？
- 30. onListItemClick、 'id'から絶対位置を取得できますか？
宿題を？これまでに何を試しましたか？ –