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も最低限の動作は覚えてお...
続きを読む

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...
続きを読む

Elixir に入門したいので雑な 分散KVS を自作した

イメージ
長い連休を利用して、Elixir入門のために分散kVSを自作しました。 前書き 動機は以下の2点です。 Elixirに入門したかった 何か自分で手を動かしたかった Erlangが書けるので同じErlangVM上の言語であるElixirが前から気になっていました。 丁度いい機会だし、入門してみるかな、くらいの気持ちで始めました。 初めてだったので、株式会社gumiが連載している Elixir入門の連載を開始(Elixir入門もくじ) - DEV Community 👩‍💻👨‍💻 を参考にしました。単純な日本語翻訳ではなく、適宜加筆修正をしているようです。(後半に行くに連れて雑な文が増えているのが少しだけ残念でした。) 自分は集中力が無いので通読は苦手なのですが、23個の記事に全て目を通してから次を考えることにしました。Erlangと同じErlangVMで動くので、他の全く知らない言語よりは理解がしやすいだろうと思っていましたが、軽量プロセスやメッセージのやり取りといった基礎は共通していても、かなり機能が豊富、という印象を受けました。 なんとか全てを読み終わった後に、ErlangVMなので分散システムがいいな、と思い雑な分散KVSを作って見ることにしました。適当に検索したところ Building a Distributed Fault-Tolerant Key-Value Store - The Blog of Fourthbit という、Apache Cassandraの概要を紹介しつつ、KVSの大事な部分の実装ぽいものを説明する、という記事を今回の目的にぴったりの記事を発見しました。この記事は実装するためにかなり参考になりました。 目標 休みの間にそれっぽく動くところまで持っていく CRUD (Create/Read/Update/Delete) のインターフェースを持つ 1台は落ちても読み書きができる 耐障害性 出来たもの リポジトリはこちら mopp/brownie: Hobby Distributed Key-Value Store 機能の概要 N台1組のElixirクラスタを構築する 実行時のノード追加は不可 データはオンメモリで保持している ...
続きを読む