自作OSのメモリ管理をBuddy Systemで実装してみて学んだこと

自作OSのメモリ管理をBuddy Systemで実装してみて学んだこと 2023/09/23 junyaU

ざっくりとしたながれ 1. 自己紹介とかテーマについて 2. Buddy Systemの概要 3. 実装中に出会った疑問点 4. 実装してみて

自己紹介 - 名前: junyaU - 職歴: web系のバックエンドエンジニア （社会人2年目🐥） - 低レイヤに興味を持ったきっかけ: - 学生時代に「コンピューターシステムの理論と実装」を読み少し興味を持ち始める - 社会人1年目の時に「ゼロからのos自作入門」に出会いハマる - 現在楽しく勉強中（面白い書籍あれば教えていただきたいです🙏）

今回のテーマについて ・Buddy System（Buddy memory allocation）というメモリ管理アルゴリズムを自作OS に実装してみた ・実装してみて、疑問点や自分なりに勉強になった部分がたくさんあったのでまとめてみ ようと思いました

メモリ管理について OSのメモリ管理は大きく分けて二種類 ・物理メモリの管理 実際のメモリの確保や解放などを行う ・仮想メモリの管理 仮想メモリは、各プロセスに独立したメモリ空間を 提供するための抽象化されたメモリ領域。ページ テーブルで仮想→物理のマッピングを行ったりす る 今回は物理メモリの実装のおはなし

なぜBuddy Systemにしたのか 元々mikanosの実装をしていた時は本に従ってビットマップ方式を使っていた ↓ 本を読み終わり実装も一通り終えて余韻に浸りながら最終章を読んでたら、 そこでBuddy SystemとSlab Allocatorの存在を知る ↓ Linuxにも採用されているメモリ管理アルゴリズムらしい 面白そうだから、とりあえず新しく1から作る自作OSに実装してみよう！（安直）

Buddy Systemとはどういったアルゴリズムなのか ・外部フラグメンテーションの発生を最小限に抑えるために考え出されたメモリ割り当てアルゴリズム → ビットマップのような連続的な割り当て方式は外部フラグメンテーションが起きやすい 外部フラグメンテーションとは メモリの空きは十分あるのにも関わらず、連続している空き領域がなく小さな空き領域（断片）が点在して いてメモリを割り当てられない状態のこと

Buddy Systemとはどういったアルゴリズムなのか ・割り当て可能な最小のメモリサイズを決め、それを1メモリブロックとし、 メモリブロック単位で割り当て、解放を行っていく ・メモリブロックのサイズは2の冪乗である必要あり → なぜ2の冪乗なのかは後述します ※ここからこのスライドでの1メモリブロックサイズは4KiB(2^12)とします

割り当ての仕方 ・割り当て要求が発生したら、要求されたサイズ以上である最も近い2の冪乗のサイズのメモ リブロックが割り当てられる ex) 10KiBのメモリ割り当て要求の場合 2^2 *4KiB = 16KiBのメモリが割り当てられる この時の指数をorderという 今回であればorder2(2^2)のブロックとなる

割り当ての仕方 ・要求されたサイズ以上の最も近い2の冪乗のサイズのメモリブロックがない場合、より大きいブロックを分 割して適切なサイズのブロックを作る ex) 16KiBのメモリ割り当て要求が来たがorder2のブロックがない場合 order3のメモリブロックをorder2のブロック2つに分割し、片方を割り当てる ・分割した2つのブロックはバディと呼ぶ ・バディを利用するのはメモリ解放時

分割の例

解放の仕方 ・解放したブロックのバディが未割り当て状態であれば、ブロック同士を結合する ・分割と同様に再起的に結合が行われ、最大ブロックサイズになるまで結合する ex) 16KiBのメモリを解放する場合 該当するorder2のブロックを解放し、そのバディが未割り当てなら結合しorder3のブロックを作る

解放の例

実装中に出会った疑問点 - なぜ2の冪乗単位でブロックを割り当てるの？ - なぜ1メモリブロックのサイズは2の冪乗なの？ - なぜ外部フラグメンテーションが削減できるの？ - 1メモリブロックのサイズはどうする？

なぜ2の冪乗単位でブロックを割り当てるの？ orderの計算が高速になる ・割り当てや解放を行う際、要求されたサイズがどのorderのブロックなのかを正確に知 る必要がある → この計算は割り当て、解放のたびに発生するので計算コストは重要 ・2の冪乗単位でブロック割り当てる場合と3の冪乗単位で割り当てる場合で比べてみる

3の冪乗の場合 ・required_block_countが3^orderより大きい間はループ ・powを使っているが、浮動小数点の計算に最適化されているので、整数計算でも内部的に浮動小 数点の計算が行われる可能性が高い、整数計算よりコストが高い ・ループでこの計算を行うので計算コストが大きい

2の冪乗の場合 ・bit演算でrequire_block_countが2の冪乗であるかを判定 ・ビット幅からorderを求めている ・bit演算はハードウェアレベルで直接サポートされているので他の演算よりも高速

なぜ1メモリブロックのサイズは2の冪乗なの？ アドレス計算が単純&高速になる ・ブロックサイズを2の冪乗にすることでブロックのアドレスが2の冪乗でアラインされる ・4KiBの場合0x1000のメモリ境界でアラインされる ・order0のメモリブロックのアドレスが0x10000である場合、そのバディは 0x10000 + 0x1000 = 0x11000とアドレス計算が簡単になる ・xorを使って求めることができる（ bit演算なので高速な計算ができる） BuddyAddress = BlockAddress ⊕ BlockSize 0x10000 ⊕ 0x1000 = 0x11000 , 0x11000 ⊕ 0x1000 = 0x10000 互いにバディを求めることができる

（脱線）なぜXORは互いにバディを求めることができるのか 同値消去の性質 A⊕A=0 という性質があるから互いに求められる A 、Bは互いにバディのアドレス、Sはブロックサイズだとすると A⊕S=B B⊕S=A A=(A⊕S)⊕S 結合法則により A=A⊕(S⊕S) なので A=A⊕0 ∴ A=A

なぜ外部フラグメンテーションが削減できるの？ - 均一なブロックサイズを割り当てる 動的に結合、分割を繰り返す 要求されたサイズより大きなブロックを割り当てる可能性がある

均一なブロックサイズを割り当てる ・ビットマップなどの連続的な割り当て方式は、異なるサイズのメモリが連続的に割り当て、解放され る → 時間と共にさまざまなサイズの未使用領域が生じ、これが外部フラグメンテーションの要因になる ・Buddy Systemの場合、メモリブロックを必ず2の冪乗の均一なサイズで割り当てる → 解放された後のメモリも2の冪乗のブロックサイズであることが保証される。 未使用のメモリが一定サイズのブロックとして整理されたり、再利用されやすくなる

動的に結合、分割を繰り返す ・使用後のメモリが解放されると、未割り当てのバディと結合して大きなブロックを形成す る可能性がある → 長期間にわたって大量の小さな未使用ブロックが蓄積する可能性が低くなる

要求されたサイズより大きなサイズを割り当てる可能性がある ・要求されたサイズより大きなサイズを割り当てることで、その後の大きなメモリ要求に 柔軟に対応することができ、解放されたブロックが他の要求に再利用されやすくなる ・ビットマップ方式とBuddy System方式で比べてみる

ビットマップとバディシステムの比較 ビットマップ Buddy System

1メモリブロックのサイズはどうする？ ・1メモリブロックのサイズが小さいと内部フラグメンテーションが発生しにくくなるが、割り 当て状況を追跡するために必要メモリと計算オーバーヘッドが高くなる。 ・なので大きすぎず小さすぎずみたいなのが良いのだろうが、この辺の感覚わからな かったのでLinuxと同じように4KiBにした（パクりました） ・4KiBにすることで、ページングの最小ページサイズと同じ大きさになり、 マッピングが簡単になるというメリットもある

実装してみて ・外部フラグメンテーションが発生しにくくなるが、内部フラグメンテーションが発生しやす いという問題点もあった。 → Slab Allocatorと組み合わせるとこの問題を軽減できるらしいので次はこれを実装し てみたい ・メモリ管理のアルゴリズムを勉強するのが楽しかったのでもっといろんなアルゴリズム に触れて実装してみたいなと思いました！ ・XORっていろんな性質があって面白い！

おわり ご清聴ありがとうございました！