部内向けスキルアップ研修
「組込みOS自作入門」
2014年2月
目次
• はじめに
• OSの役割
• メモリ管理
• メモリ管理実装
• プログラムの実行
• まとめ
はじめに
前回やったこと
• OSの原型を作成
今回やること
• 9thステップでは「CPU時間」という資源管理。
本ステップでは「メモリ」という資源管理。
10.1 OSの役割
10.1.1 コンピュータの3大要素 • ノイマン型コンピュータ プログラムをメモリ上に配置し、CPUがメモリ 上のプログラムを逐次実行することで処理を進 めていくコンピュータ • CPUとメモリは必須の要素であり、処理の結果 を出力したり入力を得るためにはI/Oが必要 • 「CPU」「メモリ」「I/O」の3つを管理して いくのがOSであると言える10.1 OSの役割
○CPU時間 ・CPUを管理するというのは、複数のタスクに対し てCPUを割り当てる時間配分すること。 ・CPUをタスクに割り当てて処理している実行時間 をCPU時間と呼ぶ ・スレッドの目的は、このCPU時間を複数のタスク に自動で配分するため10.1 OSの役割
10.1.２ メモリ管理の必要性 ○メモリの衝突 • 動作しているプログラムによってメモリを使い 分けないと、複数のスレッドで同じアドレス位 置のメモリを使ってしまう可能性が出てくる → メモリの値が衝突して正しく処理できない • そこでメモリのアドレスを管理しなければなら ない • メモリの管理には静的なメモリ管理(static)と 動的なメモリ管理(dynamic)がある10.1 OSの役割
○静的なメモリ管理(static) • メモリ領域を固定で割り当て、実行ファイルの 作成時に配置を決めてしまうこと • たとえばリンカ・スクリプトを利用することで、 そのようにメモリ領域を固定で割り当てること ができる。 • この方法では、必要な時に獲得するとか不要に なったら解放するとか、開放された領域を使い まわすといったことができない10.1 OSの役割
○動的なメモリ管理(dynamic) • プログラムの動作中にメモリの獲得と解放を行 うようなメモリ管理の仕方 • メモリの獲得動作をアロケート(allocate)、解 放処理をフリー(free)と呼ぶ • 動的なメモリ管理としては他にスタックがある が、階層的な構造で自由に獲得・解放は行えな い10.1 OSの役割
○メモリ保護 • C言語の標準ライブラリにはmalloc()やfree()と いう関数があって、動的にメモリを獲得・解放す ることができる • メモリを勝手に使うのではなく、このようなサー ビス関数を利用すれば衝突の問題はない →関数内部でメモリ管理が行われるため • 汎用OSでは複数のプログラムが互いに利用して いるメモリを破壊しないよう、それぞれメモリ保 護する機能が必須10.2 メモリ管理の概要
• メモリ管理には大きく次の2つに分けられる -可変サイズのメモリ管理 -固定サイズのメモリ管理 • 可変サイズのメモリ管理はmalloc()で実装されて いるメモリ管理方法 -自由なサイズのメモリを獲得することが可能 • C言語でメモリを動的に利用するならmalloc()や free()を利用するのが一般的である p = malloc(1024); 1kBの領域を動的に獲得してそのアドレスをpに代入10.2 メモリ管理の概要
10.2.1 malloc()でのメモリ管理 • 独自にmalloc()を実装するにはどうすべきか →malloc()と似た方法で可変サイズの領域を切り売りする方 法を考えてみる • まず固定サイズの領域を確保 -char memory_area[128*1024] • 固定サイズの領域を確保して、これを静的変数とし て可変サイズで利用する →大きな枠を固定しておき、その中を可変で利用する感じ • malloc()で可変サイズのメモリ領域を獲得する時は、 memory_area[]から切り出す • 切り出し用のメモリ領域をメモリ・プールと呼ぶ10.2 メモリ管理の概要
○可変サイズでのメモリ管理 • メモリ管理の方法として、小さいアドレスから順に 切り出していく方法を考えてみる • このような管理方法だと各領域 をfree()で解放しても再利用で きない →そもそも領域のサイズデータを 持っていないのでfree()は使えない • メモリ領域を単に切り出して 分け与えるような方法ではう まくいかない 10 15 10 20 メモリ・プール 未使用領域の先頭→10.2 メモリ管理の概要
• そこで、領域のサイズや獲得済み・ 解放済みなどの情報をヘッダとして 領域の先頭に付加させる • 領域の獲得時は、ヘッダにサイズな どの情報を書き込み、ヘッダの直後 にある実際の利用領域の先頭アドレ スを返す • 開放時には、free()の引数として与 えられた領域から逆算すれば、ヘッ ダの位置を知ることができる • だが、これだとまだ小さいアドレス から順に切り出すしか方法がない 10 15 10 20 未使用領域の先頭 → ヘッダ ヘッダ ヘッダ ヘッダ10.2 メモリ管理の概要
• そこで、nextポインタをヘッダ に持たせて獲得した領域と解放 した領域をリンクリスト管理す る →解放後の領域の検索が可能と なるため、再利用することがで きる • malloc()するときには、まず解 放済みのリンクリストを検索し て、空きが無ければメモリ・ プールから切り出すといったこ とができるようになる 10 15 10 20 ヘッダ ヘッダ ヘッダ ヘッダ NULL NULL10.2 メモリ管理の概要
• 今回の例はnextポインタによる片方向リンクだった が、実際にはnextポインタとは逆方向の前方ポイン タ（prevポインタ）も持たせる →リンクリストの途中から抜き出しなどのため • nextとprevの両方を持つリンクリストを双方向リ ンクと呼ぶ • 双方向リンクで管理された可変サイズのメモリ領域 を一般にヒープ領域(heap)と呼ぶ10.2 メモリ管理の概要
• 実際には、この他に解放済み領域を再割当てする際 にも必要サイズを切り出したり、隣接する解放済み 領域の統合や、メモリ・プールも解放済みのリンク リストにつなげたりする • リンクリスト管理の欠点としては、獲得と開放を繰 り返すうちにメモリが細分化されすぎてしまう →フラグメンテーションと呼ぶ • とりあえず、今のところは「リンクリスト管理する ことで、可変サイズのメモリの割り当てと開放がで きる」と理解しておけばよい10.2 メモリ管理の概要
10.2.2 可変サイズでの管理の欠点 • リンクリスト管理する場合、メモリ獲得時に検索処 理が必要となる • 検索で見つかるまでの時間がどれくらいかかるか、 保証できない →リアルタイムOSだと、これは致命的！ • たとえリアルタイム性を求めなくても、組込み処理 では検索のような時間のかかる処理は適切ではない • 動的にメモリ管理をする場合、可変サイズは使用効 率は良いが向いていない10.2 メモリ管理の概要
10.2.3 固定サイズでのメモリ管理 • そこで固定サイズでのメモリ管理 を行う • 最初から、いくつかのサイズに分 けたメモリ領域を確保し、メモリ 領域の獲得時には必要とされるサ イズが入りきる固定領域を与える ようにする -10バイトの領域が必要なら16バイ ト領域、40バイトの領域が必要な ら128バイトを与える形式 16バイト領域 …. 32バイト領域 ・ ・ ・ ・ 64バイト領域10.2 メモリ管理の概要
10.2.3 固定サイズでのメモリ管理 • メモリ・プールの未獲得領域は、サイズごとにリン クリストにして管理する • メモリ獲得時にはリンクリストの先頭の領域を割り 当て、開放された領域はリンクリストに接続する • 実際に必要なサイズよりも大きめのメモリ領域が割 り当てられるため、メモリ使用効率は悪いが、検索 などが必要なく、高速処理が行えるため、リアルタ イム性は確保できる10.3 メモリ管理の実装
• 自由に使っていいメモリの領域（メモリ・プール） を準備して、必要になったらそこから切り出して使 えるようにしている • 再利用しやすいように、メモリ管理はリンクリスト 管理で行う • 事前に、16バイト8個、32バイト8個、64バイト４ 個のメモリ・プールを用意し、それぞれにヘッダを 作成して片方向リンクでつなげる10.3 メモリ管理の実装
○もくもく会 • 追加ファイル -memory.h, memory.c メモリ管理ライブラリ -test10_1.c メモリ管理サンプル • 修正ファイル -ld.scr メモリ・プール追加 -syscall.h, syscall.c システム・コール追加 -kozos.h, kozos.c システム・コール追加 -main.c 起動するスレッド修正 -Makefaile10.3 メモリ管理の実装
○メモリ・プール初期化の流れ • mp = (kzmem_block *)area kzmem_block構造体をarea番地に作成し、mpに 代入 • mpp = &p->free freeポインタはメモリ・プールの先頭にあたる。メ モリを獲得するときは、ここからバイト別に合わせ て取得するようになる。mppにはその先頭アドレ スを代入10.3 メモリ管理の実装
• for (i = 0; i < p->num; i++){・・・・
ここはメモリブロックを作成しつつnextポインタを つなげている処理 -mppは「ポインタのポインタ」 • *mpp =mp nextポインタが次のブロックのアドレスに設定 • mpp = &(mp->next); 一つ先のメモリ・ブロックのnextポインタへ • mp =(kzmem_block*)((char*)mp+p->size); mpを一つ先のブロックへすすめる
