30日でできる！OS自作入門(Day 10)
メモリ管理の続き
確保するメモリのサイズを考える
Day 9で実装したセグメントによるメモリ管理では必要なバイト数ちょうどだけ確保して割り当てていました。しかし、これでは例えば数バイト程度のメモリ割り当てが頻繁に行われると、虫食いだらけでどんどん使えるメモリが減ってしまいます。
そこで、割り当てるメモリの最小単位を設定してしまえば、すくなくとも最小単位のサイズで空きができるため、一見すると無駄にメモリを割り当ててしまっているようにも見えますが、大局的にメモリの無駄がなくなります。
今回はそのサイズとして4KB単位、つまり0x1000バイト単位で管理することを考えます。必要なメモリのバイト数が4KB以下の場合は4KBを割り当てる。8KB以下なら8KBを・・・という風に必要量に対して最も近い4KBの倍数のメモリを割り当てることができればよさそうです。これには必要なメモリ量を4KB単位で切り上げてあげればよさそうです。
プログラミングを少しでもやったことがある人はきっとこの切り上げ方法についてすぐ思いつくと僕は思います。それは以下のようなコードです。
size = (size + 0xfff) & 0xfffff000;
右辺におけるsizeが必要なメモリ量を持っているとすると、その値に0xfff(=4095)を足してから下位のbitを強制的に0にしています。余談にはなりますが、このような計算は十進数での四捨五入などにも使われて、その場合は5を足してから切り捨てたりしますね。
話を戻すと、上記のおかげで見事4KBずつ割り当てることができるようになったので、あとは既存のセグメントで割り当てる際にメモリ量を変化させるだけです。
重ね合わせ処理
マウスの描画の続き
まだなおマウスの描画には問題が残っているのでした。
前に残っていた課題を確認すると、マウスが通った後の部分が再描画されていない問題のようです。
下敷きを考える
ここではマウスやウィンドウ、タスクバーなど全ての描画しているものはそれぞれ透明な下敷きに絵を描いて重ね合わせているようなイメージで進めるようです。下の方の下敷きに描画したウィンドウの上に別の下敷きに描画したウィンドウを載せて・・・を繰り返すということですね。当然、この中にはマウスも含まれます。
下敷きを扱うために、まず1枚の下敷きをそれぞれ構造体で表し、さらにそれらのたくさんの下敷き構造体を管理する母体を用意します。下敷き構造体には描画場所や高さ、幅などといった固有の情報を持たせ、管理にはそれらを配列で管理させればよさそうです。
下敷きにはきちんとそれぞれが何番目に描画されるかという情報が必要で、かつ選択や削除によってそれらを順番を守ったまま並べ替える必要があります。そこで、データそのものを持つ構造体と、それらの順番を保った状態で各構造体の番地に対するポインタを持った構造体の2種類を用意します。すると、中身はポインタの構造体から番地を辿れば見ることが可能で、また削除や移動はポインタの順番を全てずらすことで解決できそうです。結果的にデータそのものの構造体の順番はめちゃくちゃなままとなります。
ここで、自分で実装する場合どんなアルゴリズムを使うかをちょっと考えてみたのですが、ある程度大きな固定枚数で配列を作成しても、もしその枚数を超えたら怖いと考えるタイプなので、最大値は動的に増やしたい欲が出てきます。となると追加や順番の入れ替えが高速な双方向リストとかになるのでしょうか・・・まぁこの辺はおいおい再考しましょう。
順番さえ守られていれば、更新のたびに下の層から上の層に向けて描画することで重ね合わせを守ることができるようになります。
高速化
これだけでも重ね合わせ処理自体は完成しており、問題ないように見えますが、簡単な実装をした場合、更新する必要が出るたびに全ての画素を書き換えることになります。これがもしフルHDや4Kなんかの解像度だととんでもないことになりそうですね・・・
そこで、いろいろな高速化が提案されますが、最終的な部分だけ見てしまえば、次のような感じでしょうか。
1. 更新する範囲だけを描画
2. 重なっている部分だけを描画
一つ目に関しては移動前と移動後の座標を元にfor文を回して、あとは高さの低い下敷きから描画すれば達成できそうです。二つ目に関しては下敷きの中である一部だけ更新範囲に入った場合です。どの部分が更新されたかを丁寧に場合分けすれば問題なく達成できそうです。
これらの高速化のおかげでずいぶん快適なマウス操作を達成することができます。先人の努力はすごいですね・・・
Day 11へ
今回は結構学ぶ内容が多くて記事も長くなりましたね。Day 11はいつの間にかウィンドウが表示されていて、すごくOSっぽい見た目をしています。やっぱりGUIは直感的にOSっぽい！となれるのでいいですね。
