今回は、コンピュータの以下の部分について、どのように管理するかについて 説明する．
CPU から直接，しかも高速にアクセスしなければならないハードウエアは， 主記憶装置(main memory)(以下，メモリという) である． 通常，メモリといえば，主記憶装置を指す． CPU の計算は，このメモリとのデータのやりとりにより行われる．メモリは， 1 バイトのデータを格納することができる箱の集まりとして表すことができる． 各箱には，番地(address) がふられており， 以下のようなメモリマップとして表現することができる．
最近の PCでは，数 M 個の箱を持っている．一つの箱には， 1 バイトのデータを格納することができるため，数 M バイトのメモリとなる． 1 M = 1024×1024 は，約 100 万であるため 何百万もの箱があることになる．
OS でのメモリ管理の問題は，この広大なメモリをどのように管理するかである． メモリは，このように広大な一つのマップとして表現されることが多いが， 階層構造で表現されることもある．CPU がメモリに値を格納する場合は，1 度に 1 バイトとは限らない． 2 バイト以上のデータを同時に格納することが多い． 例えば，C 言語の int 型の値は，4 バイト(4 つの箱) のメモリを必要とし， short int 型の値は，2 バイト(2 つの箱) のメモリを必要とする． 例えば，short int 型の値 0x457F という値を 600 番地に格納しようとすると， 以下のようになる．
このように、通常は、上位、下位ビットの順番に格納されるが、CPU によっては、 以下のように、下位、上位の順番に格納する場合もある。
下位、上位のように格納する CPU では、メモリマップを以下のようにさかさまに して表現すると分かりやすい。
このようなメモリへのアクセス方法の違いは、CPU 毎に異なる。 上位、下位の順にメモリに格納する CPU を ビックエンディアン(big endian)という。 逆に、下位、上位の順にアクセスし、メモリマップをさかさまにした方が分かりやすい CPU を リトルエンディアン(little endian) という。 多くの PC に使われている i80X86，Pentium は、リトルエンディアンである。 モトローラ社が設計した 680X0 は、ビックエンディアンである。 もともと、以下のように卵の部分の名前である。
この講義では、ビックエンディアンを前提として説明する。
CPU毎に、メモリの位置でどのような情報を格納するかが決められている。
この「動的割当て領域」に、プログラムを割当てる。通常，複数の プログラムが，実行時に プロセス(process) または， スレッド(thread) としてメモリに割当てられる。 「割り込みベクタ」は、割り込み処理をするとき、どこ(番地)に割り込むかを テーブル(通常は、4バイトで一つの割り込み)として格納されている。 「画像情報(フレームバッファ)」は、 ディスプレイ情報がメモリに張りついている部分である。 このメモリに情報を書き込むと、ディスプレイに情報が表示される(詳しくは、 ウインドウシステムで説明する)。「システム領域」は、最低限コンピュータに必要な プログラム、データが ROM として格納されている。
システム領域をさらに詳しく表すと上図のようになる。 「ブートプログラム」は、OS の起動時に一番最初に実行するプログラムを示す。 通常、512 バイトか、1K バイト程度で、ブートデバイス(フロッピディスク、 ハードディスク) の決められた位置に格納されている一定長のプログラムを この領域に読み込んで実行する。その後、カーネルを動的メモリ割当て領域 に読み込んで、さらに実行を進める。「メモリマップド I/O」は、 メモリに貼り付けられた、デバイスの窓にあたるメモリで、この場所にデータを 書き込む(通常、ひとつのデバイスに、1バイトか、数バイト程度割当てられる) ことにより、デバイスに情報を送ることができる。メモリマップド I/O を持たない CPU もある。「ベーシックインプット・アウトプットシステム」は、 BIOS(basic input/output system) といい、その名のとおり、デバイスに 対する基本的な、入出力を制御するプログラムが格納されている。このプログラムは、 OS よりもさらに、細かな情報をやり取りする基本的なプログラムを示す。 第 0 世代のOS は、この BIOS 程度のプログラムを指している。 このプログラムは、全て機械語の形でメモリに格納されているので、2 進数で 表現されていると考えればよい。
各プロセスは、C 言語で生成した実行形式 a.out が大体そのまま(実際には、 再配置可能な形式に変換して)メモリに格納されていると思えばよい。 各実行形式のプログラム(a.out)は、以下のような構造をしている。
C 言語などのプログラミング言語で書かれたプログラムは，必ず上図のような形式を している。「プログラムヘッダ」は、プログラムを実行する際に必要なデータが 格納されている。「プログラム」は、各プログラムを実行形式に変換した後の プログラム(機械語) である。メモリ上に読み込む際にさらに、再配置可能形式 (reallocatable format)に変換されている。 OS は、この「ひとかたまり」の情報をプロセスまたは、スレッドとして、 動的割当て領域に、メモリを割当て、この「ひとかたまり」を読み込んだ後、 実行する（以下、プロセスまたは、スレッドを、プロセスに統一する)。
メモリ管理は、この動的メモリ割当て領域に、いかにして システマティックに割当てるかを問う問題である。以下では、簡単に一つの 動的割当て領域があるとする。
各プログラムをプロセスとして実行させるためには、 まず、動的割当て領域からメモリを割当てなければならない。さらに、 終了後には、メモリを解放する。例えば、以下のようにメモリを割当てると する。開始番地を $end、終了番地を $maxaddrとする。
次に、複数のプロセスを起動し、 メモリを以下のように動的に割当てたとする。
各プロセスは、独立に実行し、独立に終了するので、たとえば、 領域1 と、領域3 を解放したとすると、以下のような虫食い状態になることが 考えられる。
このような単純な例の場合は、深刻ではないが、実際の数十、数百のプロセス が同時に実行している場合は、この虫食い状態は、深刻である。 このようなメモリ割当て状態を断片化または、 フラグメンテーション(fragmentation)という。 メモリ管理では、このようなフラグメンテーションが できるだけ起こらないように工夫しなければならない。
フラグメンテーションの解決策として以下の 2つが考えられる。
1. の方法は、一見最も、わかりやすい方法であると考えることができるが、 以下の二つを解決しなければならない。
2番目の移動可能な形式が、上で紹介した再配置可能形式 である。 現在の OS は、上の2 つを可能とする形式でプロセスとして実行するので、 可能ではあるが、効率が悪くなるので他の工夫が必要である。 Xinu は、簡単のため、2. の方法を採用している。 つぎに、Xinu のコードを紹介する。
Xinu は、低レベルメモリ管理として、getmem 関数、freemem 関数、freestck 関数 を用意している。これらの関数に必要な定数などを定義する mem.h というヘッダファイルがある。
Xinu は、上で説明した開始番地 end(OS がこれより前に格納されている ため、OS の最後という意味のend)、終了番地maxaddr とし、 未割り当ての領域の連なり(フリーリストという) を管理する。
上で紹介した例の状態を詳しく描くと以下のようになる。
memlistというポインタが、フリーリストの先頭を指し、 次のフリーリストへのポインタをその最後に持つ。メモリ割り当て関数 getmem は、フリーリストをたどり、必要な領域を確保できるフリーリストを探す。 もし、見つかれば、必要な大きさだけ割当てる。メモリ解放関数 freemem は、 解放したいメモリ領域のポインタを受け渡され、近傍のフリーリストに接する形 で(つまり、他の未割り当ての領域と合体させて、大きな未割り当て領域とする。
getstk 関数、freestk 関数は、各々 getmem 関数、freemem 関数に対応する関数で、 領域の最後へのポインタを受け渡され、メモリの割当て、解放を行う。Pentium を始めとして、最近の CPU は、自身でメモリ管理を専門に処理する ハードウエア(メモリ管理ユニット，MMU(memory management unit)を持っている ことが多い。その機構は、仮想記憶という、2次記憶装置までを含んだ 大規模なメモリ管理をサポートする。詳しくは、仮想記憶で説明する。