マルコフ連鎖プログラムに対するページ置換アルゴリズムの研究

概要

論文の詳細を見る
ネットワーク環境の拡大やマルチメデイアに代表される膨大データを用いる応用分野の増大に伴い、ページ置換アルゴリズムの再評価が求められている。ページ置換アルゴリズムとその振る舞いについては、仮想記憶の概念の導入初期に活発な議論が行われたが、その後TSSの普及に伴い、研究の主眼はワーキングセット法などに移行し、個々のページ置換アルゴリズムに関する議論は注目されなかった。一方、近年になり個人使用のための計算機でも多量のデータを管理する必要が増大している。この様な環境下では、TSSで想定された使用法とは異なり、同時に動作するプログラムの内、二次記憶などの資源を占有的に使用する応用プログラムは少数であり、他のプログラムは、補助的な役割を担っている場合が多い。従って、ワーキングセット法などによる性能向上はあまり期待できない。むしろ、主要な応用プログラムに対して、二次記憶への参照の起こり方の特徴を調べ、それに適したページ置換アルゴリズムを採用するのが望ましい。マルコフ連鎖、特に一次元酔歩は比較的単純なモデルでありながらも、WWWなどのネットワークアプリケーションや、道路地図データベースシステムなどの高度応用分野における外部記憶への参照のパターンをよく近似したモデルであるといえる。本研究では、マルコフ連鎖に従うプログラムにおける最適ページ置換アルゴリズムのコストについて議論する。
一般社団法人情報処理学会の論文
1996-09-04

マルコフ連鎖プログラムに対するページ置換アルゴリズムの研究

スポンサーリンク

概要

著者

関連論文

スポンサーリンク