アルゴリズムとデータ構造1

コンパイラ
2012年11月12日
酒居敬一@A468([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
1
コンパイラと実行環境の連携1
OS



プロセスやファイルシステムなど仮想化したハードウェアを提供
プログラミング言語に依存しない汎用的なインターフェース
実行環境


プログラミング言語固有のサービス



メモリ管理(たとえば、割り付け・自動開放)
スレッド管理(生成・消滅・同期・相互排除)
初期化処理


ライブラリ


2
C言語の場合、この初期化処理だけで、限定的に動かすことができる
明示的に利用するもの・暗黙的に利用されるもの
コンパイラと同時に開発する必要があるモノ
実行環境
ソースコード
コンパイラ
実行環境
オブジェクト
コード
リンク
ライブラリ
システムコール
OS
3
実行環境とコンパイラ
たとえば、lookUpReturnAddressInException()


例外検査コードを生成するとしても、いちいち表を調べる
コードをオブジェクトコードに入れておくことは無駄である。
通常はコンパイラが、そういったサブルーチンを呼ぶ。
たとえば、キャスト。


実行時の型検査、例外生成あるいは型変換、といった一連
の手続きを、いちいちコード生成しててはメモリを消費する。
こういったものも、コンパイラがサブルーチンを呼ぶ。
実行時に呼ばれる、そのような様々なサブルーチンも
実行環境であり、コンパイラとペアで開発する。

4
Garbage Collection (ごみ集め)
メモリ割り付けと開放の自動化・機械化


Lispでは、メモリは自動で割り付けられ自動で開放される



Javaでは、開放だけが機械化されている。


割り付けはオブジェクト生成時に行われる
使われていないオブジェクトのメモリは、ころあいを見て開放される
割り付けは new オペレータで、明示的に行う。
Cでは、メモリ割り付け・開放については機械化されていない。

malloc()/free() という、ライブラリ関数があるのみ。
メモリの開放に関する問題



開放忘れ:使用可能なメモリの不足による停止
二重開放:メモリ内容の意図せぬ変更によるプログラムの暴走。
不要メモリを機械的に回収し開放する。→ GC

5
Java実行環境
C言語の極端な例では、
スタックポインタを設定し
main()を呼ぶだけの初期化
処理でもいい。
実行環境として、機械語で
数命令書けば動くということ。
コンパイラ・アセンブラ・リン
ケージエディタ、といった
コマンドだけでよい例は、
学群実験でやった。
ソースコード
ソースコード
ソースコード
Javac (静的コンパイラ)
クラス
クラス
クラス
ファイル
ファイル
ファイル
標準クラスライブラリ
•java.lang.System クラス
•java.io.orintStream クラス
javaコマンド(Java VM Emulator)
クラスローダ
インタプリタ
動的コンパイラ
Javaは、C言語より楽だ。
でも実行環境は相応に
大きく複雑になる。
Java 実行環境
スレッド管理
•EnterSynchronizedBlock()
•ExitSynchronizedBlock()など
メモリ管理
•newInstance()など
その他
•is_instance_of()など
例外処理
•暗黙のnull検査、スタックバンギング用シグナルハンドラ
•lookUpReturnAddressInException()など
OS
6
静的コンパイラ
プログラムを実行する前にコンパイルするコンパイラ


普通のコンパイラ。
Javaでは、利用者の書いたプログラムをコンパイルして
得た、Java VM向けのバイトコードが出力される。


class ファイルが生成される。
javaコマンド実行により、次の処理が行われる。




Java VM の初期化。
引数の class ファイルを読み、main() を探す。
class loader により、外部参照を解決する。

7
class ファイルや、jar ファイルを決められた順で探す。
動的コンパイラ
Java VM はエミュレーションなので、やはり遅い




native code に静的コンパイルしないことで、class ファイル
(オブジェクトファイル)を機種非依存にできたことは利点。
そこで、必要に応じて、javac (Java VM emulator) で、
バイトコードを native code に翻訳する。
バイトコードと native code を切り替えながら実行する。
ちなみに、native code 実装したメソッドなどを、
java プログラムから呼び出す手段がある。


8
混ぜて実行できるくらいなので、当然といえば当然。
標準クラスライブラリ
実行環境が用意する標準的なライブラリ群










9
GUI
bean
Java 固有
数学
ネット
I/O
セキュリティ
text 処理
ユーティリティ
Write once, run anywhere にも例外がある

ずーっと前の情報工学実験


JavaからWebカメラを使って画像をキャプチャしていた。
もちろん標準クラスライブラリにはキャプチャ用クラスはない。


実はJavaにも、非標準的実装方法ある。


当然ながら、OS経由でカメラを直接操作するクラスがない。
もちろん方法は標準化してある。
JNI (Java Native Interface)

無いものは仕方ないという状況で、どうするか?

あきらめてもらう。


プログラマに非標準的実装方法を提供する。

10
Javaは使ってもらえなくなるかもしれない。
Java VMコードではなく、java VMが動作する環境のコードで「実装」。
public class WebCam {
public WebCam() {
if(initializeWebCam("/dev/video0", 640, 480)){
throw new java.lang.IllegalArgumentException();
}
}
public WebCam(String device) {
if(initializeWebCam(device, 640, 480)){
throw new java.lang.IllegalArgumentException();
}
}
public WebCam(int width, int height) {
if(initializeWebCam("/dev/video0", width, height)){
throw new java.lang.IllegalArgumentException();
}
}
public WebCam(String device, int width, int height) {
if(initializeWebCam(device, width, height)){
throw new java.lang.IllegalArgumentException();
}
}
private static native boolean initializeWebCam(String device, int width, int height);
public static native void finalizeWebCam();
public static native int getWidth();
public static native int getHeight();
public static native int[] grabPixels(int[] array);
public static native byte[] grabPixels(byte[] array);
static {
System.loadLibrary("WebCam");
11 }
}
#include <jni.h>
#include "WebCam.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/fcntl.h>
#include <sys/ioctl.h>
#include <time.h>
#include <linux/videodev.h>
#ifdef USE_MMX
#include <mmintrin.h>
#endif
#define SYNC_TIMEOUT 1
/* device stuff */
static int
bt848, gb_grab, gb_sync, even, start;
static char
*gb_frame;
static int
*gb_work;
static struct video_mbuf gb_buffers;
static struct video_mmap
gb_even, gb_odd;
/* geometry stuff */
static12int cols, rows, pxls;
メモリ管理

プログラムの実行に必要なメモリ領域の確保・管理・開放

OSの上で動く場合

OSへのメモリ要求



brk()・sbrk()やvalloc()やmmap()システムコール
獲得したメモリのJavaプログラムへの割り付け・回収
OSへのメモリ返却
メモリ管理
方式
自動
手動
実行時スタック
ごみ集め
広い
狭い
広い
除去困難なバグを生成する確率
大
なし
なし
オーバーヘッド
小
小
大
比較項目
適用範囲
13
実行時スタック

関数やメソッド内の局所変数領域として使われる


エントリー時に確保、return 時に開放。
スタックポインタだけでメモリ管理機構が実装できる

たいていは、プロセッサによるサポートがある。





特定のレジスタがスタックポインタになってる。
スタックフレームを形成・破棄する機械語命令がある。
スタックポインタの操作だけなのでオーバーヘッドが少ない。
コンパイラがスタック操作コードを生成するので
開放ミスはない
原理的に静的な割り付けができない

14
ポインタで参照してても、return 後には必ず消滅する。
メソッド呼び出し
空き領域
スタックポインタ (TOS)
メソッドからの返戻
newInstance()の
スタックフレーム
Example8_methos2()の
スタックフレーム
Example8_method1()の
スタックフレーム
変数objectの内容
を保存する場所
Example8_main()の
スタックフレーム
※ object変数はスタックフレームに置かれてますが、
object変数が指す本体はヒープに置かれている。
15
Heap (ヒープ)

静的データ・実行時スタック以外のメモリ領域


静的データの一部をあらかじめ割り付ける方法もある
たいていはOSから随時割り当てられた仮想記憶領域


OSからはページングサイズで割り当てられたりして使いにくい
ヒープを使う方法に3とおりある。

オブジェクトへの割り付けも開放も手動


オブジェクトへの割り付けは手動、開放は自動



Java のnew
開放はGCが安全に機械的に行う
割り付けも開放も自動

16
C言語のmalloc()/free()が典型例
LispやSchemeなど
手動によるメモリ管理

うまく書ければ最高の効率でメモリが管理できる?


必要なときに確保し、不要になった時点で即開放すれば、
メモリ領域は効率よく再利用されていいかもしれない。
現実には…

間違いなくfree()することはとても面倒



メモリ割り当てが成功したかどうかの検査も面倒


メモリ割り当て失敗はプログラマの責任じゃないでしょう。
オブジェクトの性質に応じたメモリの割り当ての区別が面倒



17
フローグラフ上で、free() する位置が異なるブロックに現れる
malloc()コードと対応するfree()を常に同時に記述・抹消する
スクラッチパッド用の細かなデータ領域
行列演算用領域
フレームバッファ用領域
Garbage Collection の必要性


割り付けはオブジェクトが生成されるとき、という明確な
タイミングがある。一方で開放には、そこまで明確な
タイミングがない。
free()に関する次の問題をGCが解決する

開放忘れ



誤開放


使用中のエリアを開放して、再利用されたら暴走しかねない
二重開放

18
(短期的には)ヒープを圧迫する
OSからメモリを一方的に獲得し続ける結果、システム不安定をきたす
開放済み領域を再び開放したら、ヒープ管理が破綻しかねない