OSの超簡単なメモリ管理を実装するおはなし

この記事は Aizu Advent Calendar 2013 6日目の記事です。
前日は「Aizu Advent Calender 5日目（ダイエット成功したかも知れません）」でした。

おはようございます。
もぷりです。
最近すっかり寒いですが、皆様いかがお過ごしでしょうか。
私は今、胸部に痛みを感じつつキーを叩いております。

さてさて、今年もAdventな季節がやってまいりました。

今回は自分の作ってるOSでとりあえず実装した簡単なメモリ管理について書きます。
間違いなどの指摘があれば@Mopp_jpでもissuesでもなんでもよいのでぜひ言ってください。

リポジトリはこれです。

まず、メモリの管理とは
「OS内でハードウェアからのメモリ情報を使って
動的なメモリ確保を行えるようにする。」
ということです。

 もっと簡単に言うと使っているのか使っていないのかを自動で判断してメモリ割り当てをしてくれるって意味です。


順を追って説明をします。

まず、OSはブートローダというOSを起動するだけ+αのソフトウェアから起動されます。
具体的にはgrubとかLILOですね。
で、このブートローダはBIOSが起動します。

BIOS → ブートローダ → OS → ζ*'ヮ')ζ＜うっうー

このように起動していきます。
ちなみに、もぷりんOSでは色々とめんどかったのでgrubから起動されること前提で作っています。

先に言ったように、ブートローダはOSを起動するだけ+αです。
ですが、とても大切ですので簡単に説明します。

OSの実行ファイルをデバイスから探す
↓
OSの実行ファイルをメモリに読み込む
↓
ハードウェア情報、BIOSコールの戻り値などをメモリに置いておく
↓
読み込んだOSの実行ファイル先頭部分へジャンプ

この4ステップです。
シンプルですねー(※1ステップ目以外)

このOSが起動した時点で、メモリについて考えてみます。
はい、なにもないですね。
ですので、とりあえずOSはセグメントというものを設定します。
セグメントもメモリに関係するものでメモリの使用用途や権限を定めるものです。
(※セグメントも大事なことなのですが今回は説明しないですすいませんです。)

他にも割り込みなどいろいろと設定するものがあります。
どれもこれもコンピュータ上のデータであるからにはメモリ上に存在していなければなりません。
しかし、まだ、動的メモリ確保は行えませんので以下のようにします。


メモリを直書きしてキャストです。
変数をグローバルにおいても別にいいのですが、配列などの大きなデータを入れてしまうのはサイズ的に気が引けます。
出来れば、ポインタだけで済ませたいです。
場合によってサイズが変化する場合などなおさら動的に確保して無駄を減らしたいです。

そもそも、こういうことをたくさんやるのは良くないですし
いちいちアドレスを気にするのも面倒です。

 そこで、やっと本題のメモリ管理です。
メモリ管理の初期化は2ステップです。
メモリ情報取得
↓
それを元にメモリ空間をリスト構造化

使うときには普通のC言語と同様にmallocとfreeで扱えます。

1ステップ目
BIOSコールを使って、コンピュータのメモリ情報を取得します。
grubであれば取得データを渡してくれます。
この情報にはメモリの領域が使えるか使えないかという部分が入っています。

 使えない部分というのはブートローダに処理が渡った際、既にデータが置いてあって、書き込みされると困る部分です。
そこには割り込みベクタなどがあります。

 これは特に問題ないですね。

2ステップ目
メモリ管理には有名なものでビットマップを用いるものと連結リストを用いるものがあるようです。
簡単に説明をします。

 ビットマップ方式
    固定長(4KBくらい)でメモリを区切って、その一つを1bitに割り当てて、使っている、使っていないを判断します。
リスト方式
    可変長でメモリを区切って、ここからここまで使ってる、ここからここまで使っていない、という風に判断します。

 後々便利そうだったのでもぷりんOSでは連結リストを使用しました。
ファイルはこいつです。
https://github.com/mopp/Axel/blob/advent/src/doubly_linked_list.c

 さて、コードをさらーっと見ていきます。

ここでOS起動時の初期化で呼ばれる関数はinit_memory()です。
引数にはgrubのくれるメモリ情報、とそのサイズが渡されます。

L57のinit_memory_list()で、メモリ管理に使用するデータとリストのノードを初期化します。
> dlst_nodes = (struct dlinked_list_node*)(get_kernel_end_addr() + sizeof(Memory_manager));
> mem_info = (Memory_info*)(dlst_nodes + sizeof(struct dlinked_list_node) * MAX_MEM_NODE_NUM);

 > mem_manager = (Memory_manager*)get_kernel_end_addr();
これはカーネル(OS)の読み込まれた末尾のメモリを使用するためにアドレスの計算をしています。
get_kernel_*関数の中身を見ればわかりますが、メモリ直書きと大差ないです。

次にL60-L80でメモリ情報を元にリスト構造化します。
set_meminfo()関数を使って、ベースアドレスとそこからの長さをリストのデータに持たせます。

その後にL82-L117でカーネル部分のメモリを使用中にしておきます。
ここを忘れては元も個もありません(TODOは見なかったことにしてください)

初期化はこれだけです。

あとは使うだけですのでmallocとfreeを用意します。


mallocでは受け取ったサイズが入る領域を持つノードを探して行って、見つかったらその先頭部分から新たにノードを作り、使用中にします。
これをfirst-fit方式といいます。
手っ取り早くていいですね。

freeは確保時に返したアドレスを探していき、見つかったら空き領域とし
可能ならば前後のノードとまとめる、ということを行います。


はい、以上です。
OSのメモリ管理なんてもっと難しいのかと思っていたら案外そんなことはありません。
わかりにくかったらそれはきっとこの記事が悪いのでしょう。

といっても、はりぼてにすらならない穴だらけOSなのできちんと作っていきたいです。

明日、Aizu Advent Calendar 2013、7日目はmotiさんです。

コメント

コメントを投稿

このブログの人気の投稿

カーソルキーさん@つかわない インサートモード編

この記事は Vim Advent Calendar 2012   104日目の記事になります。 103日目は@ujihisaさんの unite-build でした。 Vimｯ!  使わずにはいられないｯ! カーソルキーでｴﾃﾞｨｯﾄ? 貧弱貧弱ｩ!! はい、すいません。 というわけで 以前、書いた記事にも似たようなことをチラッと書きましたが、改めてきちんと書きなおしてみます。 Vimmerであればノーマルモードにおいて、息をするよりも簡単にhjkl移動をすることだと思います しかし、インサートモードではどうでしょう？ 案外カーソルキーに手を伸ばしがちですね。 私もVimを使い始めたばかりの頃はそうでした。 そもそも、インサートモードにおいてカーソルキーを連打ってしまうくらいの移動ならば <ESC>してノーマルモードで移動すべきだと思います。 Vimは音ゲーでは無いので連打なんてするべきではないのです。 標準では以下のように与えられています。 下の行へ <C-G><C-J> <C-G>j 上の行へ <C-G><C-K> <C-G>k これでは物足りませんね(゜.゜) そこで、この上記に加えるといいであろう設定を列挙します。 <C-A> - 行頭 <C-E> - 行末 <C-F> -  右 <C-B> -  左 noremap! <C-A> <Home> noremap! <C-E> <End> noremap! <C-F> <Right> noremap! <C-B> <Left> noremap! <C-D> <Del> emacsライクに設定しています 私がこの設定にしている理由はMacを常用しているからです。 Macだと結構な割合でemacs移動バインドがテキストボックス内で使えるので案外役に立つのではないでしょうか。 あと、emacsも最低限の動作は覚えておきませんと。 emacsっぽいとか
続きを読む

Android で MIME Type 判別

ちょっとアプリを作っていてかなり悩んだのでメモとして残しておく MIME Typeというのは見たことはあるが、きちんと知らないので調べて見ました MIME 【Multipurpose Internet Mail Extension】 "マイム"と読むらしい 直訳してみれば、"多目的インターネットメール拡張機能"かな？ ネットワーク上で動画、音声、画像などのファイルを扱うための規格 RFC2045～2049で規定されている。  拡張子とファイルのデータを関連付けているものらしい " タイプ名/サブタイプ名"のように区切られて表現される 例としては、 text/html text/plain image/jpg application/pdf などなど さて、例えば、AndroidでSDカードにアクセスし適当なファイルを開いた際 どんなファイルか判別したいとする この時にMIMEを読み取り画像か音声かテキストか判別し 他のアプリにIntentを投げようと思います ※12/25追記:以下の方法だと動作しない場合があるので更に下に追記しました。 Android Developerの ここ を参考に //ファイル名からMIMEタイプ取得 public String GetMIMEType(String Path){ //拡張子を取得 String ext=MimeTypeMap.getFileExtensionFromUrl(Path); //小文字に変換 ext=ext.toLowerCase(); //MIME Typeを返す return MimeTypeMap.getSingleton().getMimeTypeFromExtension(ext); } 引数のパスは"/sdcard/Music/xxx.mp3"のように渡しています。 そこからgetFileExtensionFromUrlメソッドを使って、拡張子(mp3)を取得 それをgetMimeTypeFromExtensionメソッドに入れてMIME Typeを呼び出し元に返す getFileExtensionFromUrlとgetMimeTypeF
続きを読む

Erlang & Elixir Fest 2019 に参加してきた

Erlang & Elixir Fest 2019  に参加してきました。 来ました pic.twitter.com/dtShHONnzH — もぷり (@Mopp_jp) June 1, 2019 その感想をメモを兼ねて時系列順にざっと思うままに書いてみます。 開始前 Erlang & Elixir Festは過去に何度か開催されていたようですが、自分は今回が初参加でした。 場所は永田町で、10時開場、10:30セッション開始というスケジュールで、10:10くらいに入場しました。 会場は縦に長く、中央にプロジェクターのスクリーンが1枚という構成でした。 後ろの方に座るとスライドがよく見えないだろうと思ったので前の方の席を探すと中央の前から2番目というかなりのいい席に座ることができてセッション中に不自由しなかったのがとてもよかったです。 セッション 超並列高速実行処理系 Hastega 〜 Lonestar ElixirConf 凱旋帰国 本日の Erlang & Elixir Fest 2019 の発表資料を公開します。 #elixirfest https://t.co/OFdnRXZlaA — Susumu Yamazaki (@zacky1972) June 1, 2019 一つ目の発表はHastegaというElixirのコードをOpenCLに変換して分散処理をするライブラリ(でいいのだろうか)についての発表でした。名前の由来はFFの仲間を強化する魔法だそうです。現状はdefhastegaというマクロで囲んだ中にあるEnum.mapなどが変換され、並列処理されるようになるそうです。また、将来はdefhastegaマクロを使わずに、できそうなところは変換するようにしたいとも話していました。 スライドに性能評価はありましたが、コード生成の仕組みに悩んでいるとのことでリリースはされていないそうです。Hastegaを使ったコード例を見た限り、使う分にはシンプルそうでよさそうでした。 Erlang/OTP 22からはHiPEが非推奨になるのでそこも悩みどころ、と話しており、それについてツイートしたところ、記事を教えていただきました。 Joseから紹介された記事です。 https://t
続きを読む