ヒープ領域のメモリ管理・再配置はどのように行われているのか


今回は、OSがメモリのヒープ領域をどのように管理しているか、主に図を用いて解説します。

# なぜメモリの管理が必要なのか

メモリの管理が必要な理由は、主に
* プログラムの安定性向上
* セキュリティの向上
* 効率的なリソース利用
* プログラムのパフォーマンス最適化
が挙げられます。

メモリを管理することで、以下の図のように、複数のスレッドが同じメモリにアクセスするのを防げます。これにより、メモリ管理はプログラムの安定性とセキュリティの向上につながります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/63ada175-c9db-5ce7-688d-080934274c84.png)

メモリ管理を適切に行うことで、メモリの断片化を防ぎ、メモリアクセスの効率を高めることができます。これにより、プログラムの実行速度が向上します。また、キャッシュメモリの効率的な利用にも寄与し、全体的なシステム性能を向上させることができます。

また、メモリは有限です。プログラムが効率的にメモリを利用しないと、メモリが不足します。メモリ管理によって、必要なときに必要な量だけのメモリを割り当て、不要になったメモリを解放することで、リソースの有効活用が図れます。

# メモリ管理の方法
OSのメモリ管理は、以下の2つの処理によって行われます

* メモリの獲得
* メモリの開放

メモリの管理方法には、静的 (static)な方法と、動的(dynamic) な方法があります。

#### 静的な管理方法
プログラムが実行される前に、リンカスクリプトを使って必要なメモリ領域を固定で割り当てます。これにより、プログラムが開始する時点でメモリが確保されます。この方法では、必要になったら確保したり不要になったら開放するような動作はできません。

#### 動的な管理方法
動的なメモリ管理では、**スタック**と**ヒープ**と呼ばれる2種類の領域を用います。

スタック領域ではある決められた手順に従ってメモリの確保と開放をしなければならないため、プログラマが自由にメモリを獲得もしくは開放できないという欠点があります。一方で決められた手順にさえ従えば非常に高速かつ厳密にメモリを管理することができるという利点があります。

ヒープ領域では、プログラマが好きなサイズのメモリを好きなタイミングで獲得あるいは開放できます。自由度が高い一方で、プログラマ自身が厳密なメモリ管理を行わなければならないため、コード内部にバグや脆弱性を作り込んでしまう原因になります。

ヒープ領域でのメモリ管理では **malloc** と **free** という関数を主に用います。malloc は使いたいメモリ領域をヒープ内に確保するための関数で、free はヒープ内の使い終わったメモリ領域を開放するための関数です。

今回は malloc や free 関数がヒープ領域においてどのようにメモリを獲得あるいは開放しているのか解説します。
## mallocがメモリ領域を確保する方法

mallocは自由にメモリ上の領域をどこでも確保できるわけではありません。まず、malloc関数を使うことでメモリを確保することができる領域を静的なメモリ領域として作成します。
```
char memory_area[128*1024];
```
上記のように作成した領域をmallocで必要な分だけを確保して使います。最初に切り出したメモリ領域のことを**メモリ・プール**といいます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/a329077c-6ecd-499f-0aca-ad6437918b68.png)

malloc関数がメモリ領域を可変的に使用する際は、メモリ・プール中の未使用領域の先頭から使用していきます。未使用領域の先頭はmalloc関数で領域が使用される毎に更新されます。

```
malloc(10),malloc(15),malloc(10),malloc(20),
```
上記のように、malloc関数で10,15,10,20バイトの領域確保があったあとのメモリ・プールの状態は以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/d8c3bb2b-1405-2738-cb44-78e5760406ca.png)


しかし、この状態で不要になったメモリ領域を開放しても、どこが、どのぐらいの大きさで空いたのかがわかりません。これでは効率的なリソース利用ができていない状態です。

そのため、ヘッダ情報を付与する領域を付けることで、どれぐらいのサイズが空いたのかを確認してメモリ領域を再利用できるようになっています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/a5332edc-8dc9-f87b-6d11-4a9602714d67.png)

ヘッダにはメモリサイズの他に、次のヘッダ位置を示すnextポインタが含まれています。これにより、確保したメモリ領域と解放したメモリ領域がそれぞれリンクリスト構造になります。

このリンクリスト構造により、使用中のメモリ領域と解放されたメモリ領域を簡単に検索できます。その結果、解放したメモリを効率よく再利用することができます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/49100eb3-21de-1523-99a6-cfc35c09df72.png)


mallocを行う際、まず開放済み領域のリンクリストを検索し、使用したい領域と同等かそれ以上のサイズの開放済み領域があるかを確認します。適した領域があればそれを割り当て、適した領域がなければメモリ・プールの未使用領域を割り当てます。

図では後方のnextポインタのみが示されていますが、前方のポインタも持たせるとリンクリスト構造の途中からの領域を素早く取り出すことができます。このように前後の情報を持つリスト構造を双方向リンクリストと呼びます。

双方向リンクリストによって管理される可変サイズのメモリ領域を、一般にヒープ領域と呼びます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/1a5a0484-9c3e-0843-4735-61d823dccd76.png)


しかし、この方法では獲得と開放を繰り返すうちにメモリ領域が細分化されてしまいます。
このような状態をフラグメンテーション（断片化）と呼びます。
フラグメンテーションが起こっている状態のメモリは、効率的なリソース利用ができておらず、プログラムのパフォーマンスが低下している状態です。
このような状態を防ぐため、ある程度使用したメモリにはメモリの再配置 (Memory Compaction)が求められます。

# メモリの再配置

メモリの再配置方法のうちLinuxで使用されているメモリの再配置方法を紹介します。

この方法では、メモリの断片化を解消するために2つの探索を行います。

メモリの低位から高位へ使用されている領域の探索と、メモリの高位から低位へ空いている領域の探索を走らせて、2つの探索がぶつかった地点で探索をやめます。その後、使用されている領域と空いている領域を入れ替えるることで、メモリの断片化を解消します。これにより、メモリが効率的に利用されるようになり、プログラムのパフォーマンスが向上します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/f4466fd0-2448-002c-5cd1-47b2535f491a.png)

![memory_compaction.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3092001/48c3518f-366b-08ab-e30b-996064ec2cb3.gif)


[Lunixのメモリの再配置についてのわかりやすい解説(外部サイト)](https://logmi.jp/tech/articles/324602)


## まとめ
メモリ管理は、プログラムの安定性およびセキュリティの向上、効率的なリソース利用、プログラムのパフォーマンス最適化に不可欠です。OSは、動的なメモリや静的なメモリ管理、メモリの再配置などの手法を用いてメモリを効率的に管理します。これにより、効率的なリソース利用とプログラムのパフォーマンス向上が図られています。