前節では、ユーザプログラムの実行時の状態は、 ＜pcの値, レジスタの値, メモリの値＞ というソフトウェアから見える計算機ハードウェアの状態であると考えていた。 しかし、近年の オペレーティングシステム(OS) ではプログラムを実行する プロセスを複数並行して走らせる ことができる。 プログラムが静的な実体であるのに対し、プロセスは実行時の 個々のインスタンスである。例えば、シェルのコマンドラインで:

        ./foo -a 100 & ./foo -a 200 & ./foo -a 300

OSは、各プロセスがそれぞれの ＜pcの値, レジスタの値, メモリの値＞ を持って処理を進めるようにする必要がある。各プロセスのプ ログラムから見て、それぞれが独自の、いわぱ 仮想計算機ハードウェアの 状態が持てるようにする。これを実現するための方式としては、各プロセスに処 理を進める機会を時間を区切って与える時分割方式がある。処理を進めるプロセ スを切り替える際には、 ＜pcの値, レジスタの値＞ を切り替える コンテキストスイッチを行う。(レジスタの値のほとんどはス タックに退避し、 ＜pcの値, spの値＞ だけを切り替えることも可能) また、通常、メモリの値については、そのすべてをどこか 別の場所に退避・復帰する形で切り替えることはせず、後述する 仮想記憶 を用いる。

有限の計算資源を複数のプロセスで分けるため、1プロセス当たりの計算速度は 当然低下する。最短の計算時間(最大の計算速度)を測定する際には、他に計算資 源を費やすプロセスが動いていない環境でプロセスを動かす必要がある。他に計 算資源を使うプロセスが動いていないか調べるにはシェルのコマンドプロンプト からtop というコマンドを用いると良い。

プロセス管理と同様に スレッド管理が可能なOSも多い。複数のスレッドが 一つのプロセスに属するようにする。スレッドはプロセスと似て、それぞれが ＜pcの値, レジスタの値＞ を持つことができるが、 メモリの値についてはスレッド間で共有する。プロセス中に複数スレッドが存在す る状況は、複数のプロセッサ（コア）がメモリを共有する状況とよく似ている。

計算機は通常、キーボード、ディスクドライブ、ネットワークカード、グラフィッ クスカード、といったデバイス(装置)を有している。仮に、これらのデバイスを 複数のプロセスが並行して直接利用できると考えてみる。すると、譲り合いがう まくできなければ思ったようには使えないことがわかる。そこでOS は、各装置 をデバイスドライバで駆動するようにして管理することにし、プロセスの資源利 用(入出力)を調整する役割を果たすことが多い。このため、ユーザプログラムは デバイスや他のプロセスへのアクセスが制限された ユーザモード で実行 することが多い。OSの機能を利用して入出力などを行いたい場合は、制限の少な い 特権モード(スーパバイザモード)への移行を伴う システムコール (スーパバイザコール)を用いる。システムコール完了後はユーザモードに戻さ れる。

システムコールにより、入出力、ファイル管理、ディスク管理、プロセスの生成・ 終了・待ち合わせ、シグナル、時刻管理、メモリマップなどをOSに依頼すること ができる。しかし、システムコールはしばしば時間がかかり、また、他のプロセ スにコンテキストスイッチしてしまう原因となるため、高速実行のためにはでき るだけ利用しないことが望ましい。例えば、プログラムの実行中にデータをログ ファイルや画面に逐一出力したりすると実行速度はかなり低下することが多い。 後から見直すようなログデータなどは、実行中はメモリに蓄えておき、最後にま とめて出力するほうがプログラムは高速に動作できる。 ちなみに、FILE * 型を用いた fgetc関数などのファイル入出力ルーチンには、ユーザプログ ラムレベルでできるだけバッファリングを行い、システムコールの回数を減らす 工夫がなされている。

システムコール以外にも、入出力デバイスやタイマなどからの 割り込みに よっても、特権モードに移行して( トラップして)OSが処理を進める。時分 割方式は、タイマ割り込みで現在のユーザプログラムをトラップし、他のプロセ スにコンテキストスイッチするというふうに実現できる。またユーザプログラム が 不正な命令を実行しようとしたときなどもOSにトラップされる。仮想記 憶について後回しにしたが、仮想記憶の効率よい実現にもトラップの仕組みが使 われている。

仮想記憶方式で、OSはプロセスの進行に必要なメモリを管理できる。ユーザプロ グラムでのメモリアクセスには 論理アドレスを利用させる。ユーザプログ ラムが論理アドレスでメモリアクセスしようとすると、OSが論理アドレスから 物理アドレスにアドレス変換して物理メモリのデータにアクセスするよう にする。アドレス変換は例えば8KBのページを単位として変換表( ページテー ブル)を用いればよい。論理アドレスをインデックスとして変換表を引けぱよい が、プロセス毎に変換表を用意し物理アドレスが重ならないようにする。そうす れば別プロセスで同じアドレスを用いていたとしても、異なる物理アドレスに変 換されるので干渉せずにデータを読み書きできるようになる。また、プロセス間 のコンテキストスイッチではメモリのすべての値を退避・復帰する必要はなくな り、どのページテーブルを用いるのかだけを切り替えればよくなる。

ここで、アドレス変換をトラップによりOSがいちいち処理したのでは時間がかか り過ぎてしまう。そこで普通はメモリ管理ユニット( MMU)というハードウェ アを使うことになる。OSはMMUに用いるべきページテーブルを指示しておき、ユー ザプログラムのメモリアクセスはMMUによりアドレス変換して行うことになる。 また、MMUのアドレス変換が順調にできるほとんどの場合にはトラップはしない ようにする。MMUはOSからは利用できるが、ユーザプログラムはMMUが見せる仮想 記憶のイメージが見えるのみである。

また、よく知られているように仮想記憶方式では物理メモリ容量より大きな仮想 アドレス空間を用いてよい。この場合、対応する物理アドレスを持たないページ のデータはディスクなどに保存しておき、そのページの論理アドレスに対するア クセスがあった場合はアドレス変換ができないとして、トラップ( ページ フォールト)する。ページフォールトが発生すると、OS は、空きがなければあ まり利用されていないページを決めて、その物理メモリのデータのディスクへの 書き出し(ページアウト)を行った後、必要なページのデータのディスクからの読 み込み(ページイン)と、ページテーブルの更新を行い、トラップからの復帰が可 能なようにする。さらにMMUでは、変換を高速化するために変換表のよく使う部 分をキャッシュしたような Translation Lookaside Buffer (TLB) を備えるのが 普通である。TLBで変換できなかった場合にはTLBミスとなるが、自動的にページ テーブルから更新するもののほかに、TLB ミスをOSがトラップするような計算機 もある。後者の場合は ページフォールトはトラップではなく、TLB ミスによる トラップの処理に含まれることになろう。

プログラムの高速化の点からいえば、ページフォールトが頻発するようなプログ ラムの実行速度は劇的に低下する。これは、(物理)メモリアクセスの速度とディ スクアクセスの速度差による。このため、物理メモリ容量を超えるページ数を必 要とするような ワーキングセット(プログラムのある時点でよくアクセス のアドレスの集合) とならないように工夫する必要がある。また、TLBミスのペ ナルティも実は大きいので、プログラムの高速化の点からはTLBミスができるだ け起きないようにするとよい。

TLBミスを少なくするには大雑把に言えばワーキングセットを小さくすればよい。 他の言い方では、メモリアクセスの 局所性をよくすればよい。メモリアク セスの局所性には、 時間的局所性(最近アドレス x にアクセスしているな ら、今、同じ x にアクセスする可能性は高い)と 空間的局所性( 最近アド レス x にアクセスしているなら、今、その近くの x' にアクセスする可能性は 高い) がある。もうすこし具体的な方法としては、プログラムの計算手順に順序 を入れ替えてよい操作(の集まり)があれば、同じページにできるだけ時間的に集 中してアクセスするような計算順序に修正すると良い。例えば、 S_k をアドレ スが ak+b 付近のメモリに多くアクセスする操作の集合として、 S_0 → S_1 → … S_n → S_0 → S_1 → … S_n のような計算順序でメモリにアクセスするプログラ ムがあった場合、計算順序を S_0 → S_0 → S_1 → S_1 → … S_n → S_n と入れ替えられ れば近くのメモリにアクセスする操作集合を時間的に隣り合わせることができ、 TLB ミスを減らすことができる。また、処理の時間的な順序ではなくデータの空 間的な配置を工夫する方法もある。例えば二次元配列a[1000][1000]に:

        for(j=0;j<1000;j++) for(i=0;i<1000;i++) a[i][j] += c;

        for(i=0;i<1000;i++) for(j=0;j<1000;j++) a[i][j] += c;

        for(i=0;i<1000;i++) for(j=0;j<1000;j++) b[j][i] = a[i][j];

        for(j=0;j<1000;j++) for(i=0;i<1000;i++) b[j][i] += c;

• 1. 概要
• 2. コンパイラについて
• 3. オペレーティングシステムについて
• 4. ハードウェアについて