練習問題(2) オペレーティング・システムと木構造

共通科目情報処理(講義)、社会学類対象、1997年05月30日

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/ipe/shakai-kougi-1997//1997-05-30 /exercise-2.html
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/ipe/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html
http://www.ipe.tsukuba.ac.jp/

■オペレーティング・システム

◆もの(object)

◆ファイル

物理的にフォーマットを行い、１Ｍバイトのデータを保存することができるフ ロッピがあったと仮定する。実際にデータを保存する場合、単純にデータだけ をフロッピに書き込むのではなく、フロッピ上に「ファイル」と呼ばれる抽象 （もの）を作製し、ファイルにデータを保存することになる。そうすると、実 際にデータを保存するために使える空間が１Ｍバイトよりも減ってしまう。

　なぜ、１Ｍバイトよりも減ってしまうのか答えなさい。減った部分は、何に 使われるのか。また、保存できるデータ容量が減ってしまうのに、なぜファイ ルと呼ばれる抽象を作製するのか。ファイルを使わずにフロッピに直接データ を保存することと比較して論じなさい。

（１９９７年２月情報処理(講義)国際総合対象試験問題（改））

◆ファイル/木構造

(1) /var/mail/yshinjo 
(2) /var/mail/s991001 
(3) /home1/yshinjo/mbox 
(4) /home1/s991001/mbox
(5) /usr/bin/csh

◆木構造の利点と問題点の解消

◆プロセス

• プロセスを作る
• プロセスを普通に終了させる
• プロセスを強制的に終了させる
• キーボードから打ち込んだデータを受け取るプロセスを切り替える

◆プロセス間通信

◆仮想記憶

◆ページ置き換えアルゴリズム

• OPTアルゴリズム。最も遠い将来まで利用されないページを２次記憶へ。
• FIFOアルゴリズム。最も早い時刻に読み込まれたページを２次記憶へ。
• Randomアルゴリズム。ランダムに選んで２次記憶へ。
• LRU((Least Recentry Used))アルゴリズム。最も長い時間参照されて いないページを２次記憶へ。

超整理法で述べられている「押し出しファイル」は、LRUアルゴリズムと類似 点がある。押し出しファイルでは、参照したファイルをもとの位置にもどすの ではなく、右端にもどす。結果としてLeast Recentry Used なファイルが左端 に移動する。ファイルを検索する時には、右から探せば速く見つかる。

超整理法では、LRUと同じ順序でファイルを並べているが、実際にはファイル を探す時には、ページ置き換えアルゴリズムと同様に、LRU が最もよい方法で はない。最もよい方法は、どのような順番で並べることか？

■言語

◆実行方式