メモリ管理・スタック領域とヒープ領域
ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のようなデータを保存するためのスタック領域と、new 命令で確保されるヒープ領域についてその使われ方などについて理解する。
C言語やJavaでのメモリ領域(静的領域とスタック領域)
C言語では、データ領域は、定数領域、静的変数領域、スタック領域、ヒープ領域 で構成される。また、変数にはスコープという変数が使える範囲がある。
定数領域は、値が変化しないデータが保存される。
静的変数領域は、プログラムが起動したときに確保され、プログラム終了と共にデータが消される。
スタック領域は、関数が呼び出される時に確保され、関数を抜ける時にデータが消される。関数の引数や関数の局所変数などは、この領域に保存される。
#include <stdio.h>
int x = 123 ; // 静的大域変数
const int y = 234 ; // 静的大域変数(定数) 再代入不可
void foo() {
int b = 345 ; // 動的局所変数
b++ ;
printf( "%d %d\n" , x , b ) ;
}
void bar( int a ) {
int b = 456 ; // 動的局所変数
static int c = 789 ; // 静的局所変数
x++ ; b++ ; c++ ;
printf( "%d %d %d\n" , x , b , c ) ;
foo() ;
}
int main() {
int z = 890 ; // 動的局所変数
bar( z ) ;
bar( z ) ;
printf( "%d\n" , z ) ;
return 0 ;
}
// 実行結果
// 124 457 790
// 124 346
// 125 457 791
// 125 346
// 890
大域変数は混乱の元
以下のようなプログラムでは、foo() を実行すると”0 1 2″ と表示され、main の中で foo() を3回呼び出しているので、”012,012,012″と表示されると勘違いするかもしれない。しかし、xが大域変数(Javaでは大域変数は無いけど)であるため、foo() の処理の中で x=3 となっているため、mainの中では、2回目のループが動かないため、”0 1 2″と表示されるだけである。
こういったように、誰もが使える変数を、どこからでも呼び出せる状態にしておくとプログラムの間違いが発生しやすい。
// C言語での大域変数の問題
int x ;
void foo() { // 0 1 2 と出力
for( x = 0 ; x < 3 ; x++ )
printf( "%d\n" , x ) ;
}
int main() { // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される?
for( x = 0 ; x < 3 ; x++ )
foo() ;
return 0 ;
}
// Javaでの大域変数の問題
public class Main {
public static int x = 0 ; // 静的クラス変数
public static void foo() { // 0 1 2 と出力
for( x = 0 ; x < 3 ; x++ )
System.out.println( x ) ;
}
public static void main(String[] args) throws Exception {
for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返すと 0 1 2,0 1 2,0 1 2 と出力される?
foo() ;
}
}
こういう場合は、正しく局所変数を用いて、関数内でのみ使う変数 x を宣言すれば、上記のような間違いを防ぐことができる。関数内で宣言される変数は関数に入る度にメモリを確保し、関数を抜ける時にメモリ領域が消される。
// C言語での大域変数の解決のために局所変数を使う
void foo() { // 0 1 2 と出力
int x ;
for( x = 0 ; x < 3 ; x++ )
printf( "%d\n" , x ) ;
}
int main() { // 0 1 2 を出力する処理を 3回繰り返す
int x ;
for( x = 0 ; x < 3 ; x++ )
foo() ;
return 0 ;
}
// Javaでの大域変数の解決のために局所変数を使う
public class Main {
public static void foo() { // 0 1 2 と出力
int x ;
for( x = 0 ; x < 3 ; x++ )
System.out.println( x ) ;
}
public static void main(String[] args) throws Exception {
int x ;
for( x = 0 ; x < 3 ; x++ ) // 0 1 2 を出力する処理を 3回繰り返す
foo() ;
}
}
一方で、関数が呼び出された回数を確認したい…という用途であれば、下記のように大域変数を使うこともあるが、これだと x を間違って使われる可能性がある。
int x = 0 ;
void foo() {
x++ ;
printf( "%d\n" , x ) ;
}
int main() {
foo() ;
foo() ;
return 0 ;
}
このために、C言語では静的局所変数というのがある。関数内で static で宣言された変数は、その関数の中でしか使えないが、プログラムが起動した時に変数領域が作られ初期化され、プログラムが終了した時にデータ領域が消される。
void foo() {
static int x = 0 ;
x++ ;
printf( "%d\n" , x ) ;
}
int main() {
foo() ;
foo() ;
}
Javaでは、プログラムの中でデータが間違ってアクセスされることを防ぐために、大域変数という考え方は存在しない。その代わりにクラス内で共通に利用できる変数ということで、静的なクラス変数が用いられる。static なクラス変数は、クラスがロードされた時点でメモリに確保され、プログラム終了まで保持される。
public class MyClass {
public static int count = 0; // クラス変数
public static void main(String[] args) {
MyClass.count++; // インスタンスを作らずにアクセス
System.out.println(MyClass.count);
}
}
スタック領域
スタック領域は、ここまでに述べた様に「関数を呼び出す際にメモリ領域が確保・初期化され、関数が終わるとメモリ領域は消される。
以下のような main から bar() , foo() が呼び出される処理では、
- 関数呼び出し時には、戻り番地の保存、実引数の確保が行われ、
- 関数に入った時点で局所変数の領域が確保される。
- 関数が終わると、実引数・局所変数の領域が消され、スタックから取り出された戻り番地に処理を移行する。
このような関数呼び出しでは、最後(Last)に確保した変数が最初(First)に忘れればいいというデータなので、Last In First Out の スタック構造が使われる。
ヒープ領域
リスト処理のようなプログラムでは、データを覚える領域は、関数が終わった後も使われる領域なので、局所変数のように「関数が終わったらそのデータの場所が不要になる」といったLast In First Out のようなスタックで管理することは難しい。
データを確保したメモリがどの時点まで使われるのか解らない場合、スタック構造を使うことはできない。こういったデータは、ヒープメモリ(ヒープ領域)を用いる。
C言語であれば、ヒープメモリの場所の確保には malloc() 関数が用いられ、不要となった時に free() 関数でメモリの開放が必要である。free() を忘れたプログラムが、ずっと動いた状態になると再利用されないメモリ領域が発生(メモリリーク)し、その領域が大量になると、他のプログラムに悪影響がでてくる。(最悪、仮想メモリの利用でスワッピングが多発するかもしれない)
#include <stdio.h>
#include <stdlib.h>
struct A { // class A {
int data ; // int data ;
} ; // }
int main() {
struct A * ptr = (struct A*)malloc( sizeof( struct A ) ) ;
// ptr = new A ;
ptr->data = 123 ;
// ptr.data = 123 ;
free( ptr ) ;
// Javaでは free() は不要
return 0 ;
}
共有の発生したデータの扱い
C言語では、ヒープメモリの管理するには色々と複雑なことが発生する。
例えば、以下のようなリストの和集合のプログラムをC言語とJavaで示す。
このプログラムでは、リスト a, b の和集合を c に代入している。また、不要となったリストを捨てるために list_free() という関数を作成している。ただし Java では、不要となったメモリ領域の開放は不要だが、C言語との対比のために next に null を代入する処理で代用してある。
#include <stdio.h>
#include <stdlib.h>
struct List {
int data ;
struct List* next ;
} ;
struct List* newListNode( int x , struct List* p ) {
struct List* ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = p ;
}
return ans ;
}
void list_print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "\n" ) ;
}
int find( struct List* p , int key ) {
for( ; p != NULL ; p = p->next )
if ( p->data == key )
return 1 ;
return 0 ;
}
struct List* list_union( struct List* a , struct List* b ) {
struct List* ans = a ;
for( ; b != NULL ; b = b->next )
if ( !find( a , b->data ) )
ans = newListNode( b->data , ans ) ;
return ans ;
}
void list_free( struct List* p ) {
if ( p != NULL ) {
list_free( p->next ) ;
printf( "*%d " , p->data ) ;
free( p ) ;
}
}
int main(void){
struct List* a = newListNode( 11 , newListNode( 22 , NULL ) ) ;
struct List* b = newListNode( 11 , newListNode( 33 , NULL ) ) ;
struct List* c = list_union( a , b ) ;
list_print( a ) ;
list_print( b ) ;
list_print( c ) ;
list_free( c ) ;
list_free( b ) ;
list_free( a ) ;
return 0 ; // free(): double free detected in tcache 2
// Aborted (core dumped)
}
import java.util.*;
class ListNode {
int data ;
ListNode next ;
ListNode( int x , ListNode p ) {
this.data = x ;
this.next = p ;
}
}
public class Main {
public static void list_print( ListNode p ) {
for( ; p != null ; p = p.next )
System.out.print( p.data + " " ) ;
System.out.println() ;
}
public static boolean find( ListNode p , int key ) {
for( ; p != null ; p = p.next )
if ( p.data == key )
return true ;
return false ;
}
public static ListNode list_union( ListNode a , ListNode b ) {
ListNode ans = a ;
for( ; b != null ; b = b.next )
if ( !find( a , b.data ) )
ans = new ListNode( b.data , ans ) ;
return ans ;
}
public static void list_free( ListNode p ) {
if ( p != null ) {
list_free( p.next ) ;
System.out.print( "*" + p.data + " " ) ;
p.next = null ;
}
}
public static void main(String[] args) throws Exception {
ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ;
ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ;
ListNode c = list_union( a , b ) ; // 33,11,22
list_print( a ) ;
list_print( b ) ;
list_print( c ) ;
list_free( c ) ; System.out.println() ;
list_free( b ) ; System.out.println() ;
list_free( a ) ;
}
}
このプログラムを実行すると、c には和集合のリストが出来上がるが、33の先のデータは a とデータの一部を共有している。
この状態で、リスト全体を消すための list_free(c); list_free(b); list_free(a); を実行すると、list_free(c) の時点で a の先のリストは解放されている。このため、list_free(a) を実行すると、解放済みのデータ領域をさらに解放する処理が行われるが、すでに存在していないデータを消す処理が実行できない。
C言語のプログラムを動かすと、プログラム実行時にエラーが発生する。しかし、Java で書かれた「ほぼ同様」のプログラムは問題なく動作する。
参照カウンタ法
上記の問題は、a の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。
参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。
- データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
- 処理の中で共有が発生すると、参照カウンタをカウントアップする。
- データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
// 参照カウンタの説明用プログラム
class ListNode {
int refc ; // 参照カウンタ
int data ; // データ
ListNode next ; // 次のポインタ
ListNode( int x , ListNode p ) {
this.refc = 0 ;
this.data = x ;
this.next = p ;
}
} ;
public class Main {
public static ListNode copy( ListNode p ) {
p.refc++ ; // 共有が発生したら参照カウンタを増やす。
return p ;
}
// 集合和を求める処理
public static ListNode list_union( ListNode a , ListNode b )
{
ListNode ans = copy( a ) ;
// ~~~~~~~~~共有が発生するのでrefc++
for( ; b != null ; b = b.next )
if ( !find( ans , b.data ) )
ans = new ListNode( b.data , ans ) ;
return ans ;
}
public static void list_del( ListNode p ) { // 再帰で全廃棄
if ( p != null
&& --(p.refc) <= 0 ) { // 参照カウンタを減らし
// ~~~~~~~~~~
list_del( p.next ) ; // 0ならば本当に消す
free( p ) ;
}//~~~~~~~~~ Javaでは存在しない関数(説明用)
}
public static void main(String[] args) throws Exception {
ListNode a = new ListNode( 11 , new ListNode( 22 , null ) ) ;
ListNode b = new ListNode( 11 , new ListNode( 33 , null ) ) ;
ListNode c = list_union( a , b ) ;
// a,b,cを使った処理
// 処理が終わったのでa,b,cを捨てる
list_del( c ) ;
list_del( b ) ;
list_del( a ) ;
}
ただし、Java ではこういった処理を記述しなくても、内部で参照カウンタ法を実行しているため、このような処理を書く必要はない。
unix i-nodeで使われている参照カウンタ
unixのファイルシステムの基本的構造 i-node では、1つのファイルを別の名前で参照するハードリンクという機能がある。このため、ファイルの実体には参照カウンタが付けられている。unix では、ファイルを生成する時に参照カウンタを1にする。ハードリンクを生成すると参照カウンタをカウントアップ”+1″する。ファイルを消す場合は、基本的に参照カウンタのカウントダウン”-1″が行われ、参照カウンタが”0″になるとファイルの実体を消去する。
以下に、unix 環境で 参照カウンタがどのように使われているのか、コマンドで説明していく。
$ echo a > a.txt
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
~~~ # ここが参照カウンタの値
$ ln a.txt b.txt # ハードリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 a.txt
-rw-r--r-- 2 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
~~~ # 参照カウンタが増えているのが分かる
$ rm a.txt # 元ファイルを消す
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
~~~ # 参照カウンタが減っている
$ ln -s b.txt c.txt # シンボリックリンクでコピーを作る
$ ls -al *.txt
-rw-r--r-- 1 t-saitoh t-saitoh 2 12月 21 10:07 b.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ rm b.txt # 元ファイルを消す
$ ls -al *.txt
lrwxrwxrwx 1 t-saitoh t-saitoh 5 12月 21 10:10 c.txt -> b.txt
$ cat c.txt # c.txt は存在するけどその先の実体 b.txt は存在しない
cat: c.txt: そのようなファイルやディレクトリはありません