このテキストは、運営している韓国のブログを日本語に翻訳したものです。
韓国のブログ：https://yunsuu.notion.site/e379eccd32c545419f0651f743c12c13?v=35310b282de24cc5a292fe45cc498a32&pvs=74
この記事は「Operating Systems: Three Easy Pieces」を読んでまとめた本です。
著者が無料で公開しているので、興味のある方はぜひ読んでみてください。
本にある良い問題は解いてgithubにアップロードしています。
github：https://github.com/yunsuu/ostep-homework-solution
本のリンク：https://pages.cs.wisc.edu/~remzi/OSTEP/
空きスペースの管理はどうするか?
ページを固定サイズの単位にすると問題は単純で、配列のようにするだけでよい。
しかし、メモリを可変長で割り当てるときに頭が痛くなる。この場合、mallocとfreeでユーザーレベルで動的に割り当てが行われたり、セグメンテーションを用いて物理メモリを管理するOSでこのようなことが発生する。
連続した領域が存在しない場合、空きスペースが大きくてもメモリの割り当てに失敗する。
空きスペースはマージする。空きスペースをリンクリストにマージして、分割された場所を管理する。
連続性が発生する場合には、マージが行われる。
1のメモリを割り当てを要求した場合、2番目のリスト要素を活用して割り当てることにした場合、次のような図が出てくるだろう。
図の中でusedとなっていた部分が解放されると、リストはこの図のようになり、リスト内の要素同士がマージされて最終的には大きな一つの空きスペースがOSによって利用可能になる。
割り当てられた空間のサイズの把握
freeの仕様を見ると、次の図のようにメモリのサイズを変数として受け取っていない。だから、割り当てられたスペースはそのptrポインタを通じて知る必要があるが、これを可能にするために、メモリを割り当てるときにはヘッダを設けて割り当てられたサイズも保存する方法を使っている。
このとき、maigcという値もサイズと一緒に保存する。今は、メモリ解放速度の向上、整合性チェックを提供するためのものであるということだけ覚えておきましょう。
空のリストの実装
実際にOS内部ではどのように動作しているのかを見てみましょう。
最初にヒープに4KBの空間があるとし、ヘッダのサイズは8としましょう。それならば、現在の4KBのメモリのsizeは、ヘッダのサイズ8を引いた4088になります。ここでmallocを通じてプロセスが100バイト追加割り当てを要求すると、
ヘッダは100 + 8(header)カ所だけ下がり、sizeは4088 - 108 = 3980になる。
このような規則的な動作により、ヒープの要素はリンクリストの原理に基づいて追加される。
それでは、解放するときはどうだろうか?
sptr変数を使って中間にあるメモリを解放しようとすると、この図のような結果が出る。
物理的には離れているが、論理的には連続した配列とみなす。
この図は、すべての要素をfreeしてマージされていないヒープメモリを示している。すべて解放されると、連続したリストはマージされ、次のプロセスが使用できるようにOSに通知する。
空のリストに、メモリ割り当て戦略
Best fit
割り当て可能な候補者の中で最も小さい候補にメモリを割り当てる。
Worst Fit
単純に最も大きな要素にメモリを割り当てる。
Next Fit
最後に割り当てた要素を指しているポインタを維持する。順序に従って探索しながら適切な要素にメモリを割り当てる。First fitと動作原理が似ている。
