部内向けスキルアップ研修 組込み OS 自作入門 2014 年 2 月 10st ステップ担当 : 中村
目次 はじめに 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.2 メモリ管理の必要性 メモリの衝突 動作しているプログラムによってメモリを使い分けないと 複数のスレッドで同じアドレス位置のメモリを使ってしまう可能性が出てくる メモリの値が衝突して正しく処理できない そこでメモリのアドレスを管理しなければならない メモリの管理には静的なメモリ管理 (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() で解放しても再利用で 10 きない そもそも領域のサイズデータを 15 持っていないのでfree() は使えない 10 メモリ領域を単に切り出して分け与えるような方法ではう 20 まくいかない 未使用領域の先頭
10.2 メモリ管理の概要 そこで 領域のサイズや獲得済み 解放済みなどの情報をヘッダとして領域の先頭に付加させる 領域の獲得時は ヘッダにサイズなどの情報を書き込み ヘッダの直後にある実際の利用領域の先頭アドレスを返す 開放時には free() の引数として与えられた領域から逆算すれば ヘッダの位置を知ることができる だが これだとまだ小さいアドレスから順に切り出すしか方法がない 未使用領域の先頭 ヘッダ 10 ヘッダ 15 ヘッダ 10 ヘッダ 20
10.2 メモリ管理の概要 そこで next ポインタをヘッダに持たせて獲得した領域と解放した領域をリンクリスト管理する 解放後の領域の検索が可能となるため 再利用することができる malloc() するときには まず解放済みのリンクリストを検索して 空きが無ければメモリ プールから切り出すといったことができるようになる ヘッダ 10 ヘッダ 15 ヘッダ 10 ヘッダ 20 NULL NULL
10.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 バイト 4 個のメモリ プールを用意し それぞれにヘッダを作成して片方向リンクでつなげる
10.3 メモリ管理の実装 もくもく会 追加ファイル -memory.h, memory.c メモリ管理ライブラリ -test10_1.c メモリ管理サンプル 修正ファイル -ld.scr メモリ プール追加 -syscall.h, syscall.c システム コール追加 -kozos.h, kozos.c システム コール追加 -main.c 起動するスレッド修正 -Makefaile
10.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 を一つ先のブロックへすすめる
10.3 メモリ管理の実装 メモリ領域の獲得 必要なサイズに収まるメモリブロックを探して 先頭のブロックを使う mp に p->free を代入して p->free を一つ先へ進めて先頭ブロックをリンクリストから削除し 外したブロックの next ポインタを NULL クリアする return mp+1 で メモリヘッダの後続のデータ領域の先頭アドレスを渡す
10.3 メモリ管理の実装 メモリ領域の解放 解放するブロックのデータ領域の先頭アドレスが渡されるので -1 したヘッダ ( ブロック ) の先頭アドレスをリンクリストに戻す mp の next ポインタに解放済みリンクリストの先頭 (p->free) を代入してリンクリストに繋げて p- >free に mp を代入してメモリブロックを解放する
10.4 プログラムの実行 実行結果 最初の 4 行は 16 バイトブロックを使用して 4 バイト 8 バイトの文字列を表示している 最後の 1 文字はヌル ターミネータ ( 0 ) で埋めている アドレスを見ると交互にブロックを獲得している 獲得した順に解放し 後に開放された領域がメモリ プールの解放済みリンクリストの先頭になるため 後に解放されたブロックから再利用 データ領域の先頭アドレスが表示されているので メモリヘッダは 8 バイトなので 8 バイト前の値がメモリブロックの先頭アドレス
10.4 プログラムの実行 0x00ffd1a8 0x00ffd1b0 16 バイト領域 メモリ ヘッダ (8 バイト ) データ領域 (16 バイト ) 0x00ffd1b8 0x00ffd1c0 メモリ ヘッダ (8 バイト ) データ領域 (16 バイト ) 0x00ffd1c8 0x00ffd1d0 メモリ ヘッダ (8 バイト )
まとめ もうひとつの資源管理として メモリ管理機能を追加した C 言語をユーザレベルで使用する場合は mallco()/free() Java などの高級言語ならば 言語レベルで動的メモリの管理機能がある メモリ管理の方法は 今回の方法以外にも何通りもある
次回の開催予定 日時 3 月 10 日 ( 月 ) 13:00~ 場所 技術支援室 担当 山田さん