トランザクション処理

トランザクション処理とは、相互に依存関係にある複数の処理を矛盾なく処理することであり、データベースでは、ACID特性(原子性,一貫性,隔離性,耐久性)がもとめられる。この時、直列化可能(様々な順序で処理できるかもしれないけど、矛盾しない結果となる処理順序が存在すること)であることが求められる。

例えば、以下のように、50万円のデータがあった時、入金処理と出金処理がほぼ同じタイミングで開始された場合、入金処理が終わらないうちに、出金処理が開始されると、以下の例では入金処理が無視されてしまう。

上記のような問題が発生しないようにするには、以下のように、入金処理の時点で他の更新処理を排除するLOCK処理を行い、入金データの書き込みを終えた時点でUNLOCK処理を行う、排他処理が重要となる。(ロックされている間は、アクセスを禁止する。)

排他処理の実装方法

排他処理を実現する方法としては、ロック(Lock)、セマフォ(Semaphore)、ミューテックス(Mutex)が使われる。

ロックの例としては、C言語では flock() 関数が有名。(後述のロッキング方式/悲観的制御を参照)

• C言語でのファイルロック(共有ロック,排他ロックの機能あり)
• 共有ロック：他のプロセスの読み込みは許可するけど、書き込みは禁止。
• 排他(占有)ロック：他のプロセスの読み込みも書き込みも禁止する。
• 使い終わったらアンロック。

セマフォの例としては、カウンタセマフォが使われる。

• 対象資源を使用中のプロセスの数を表す、カウンタを使う。
• 初期値0の状態は、だれも使っていない状態。
• 対象資源を使う時にカウントアップ、使い終わったらカウントダウンする。

ミューテックスは、セマフォの使用中/開放状態を 0,1 で管理するようなもの。

ロックはファイルに対して使うもので、セマフォやミューテックスは、プロセスやスレッド間の同期に使うことが多い。

同時実行制御

複数のトランザクションによるデータアクセスで、トランザクション処理を直列化可能にすることを、同時実行制御と呼ぶ。この方式には、2つの方法がある。

1. ロッキング方式(悲観的制御)
   先行するトランザクションは、データにロックをかけ、他のトランザクションを一時的に排除する方式。後発の処理はアンロックされるまで待たされることことから、これが処理効率の低下となる。
   • ロッキング方式では、ロックをかける大きさ(粒度)が大きいと、待ち処理が発生する可能性が高い。一方で、粒度を小さくしようとすると、ロックの判定が難しくなり効率が低下する可能性も出てくる。
     
   • ロックの種類
     ロックには、読み出し中心のデータと書き込みで更新のかかるデータでは、ロックのかけ方が異なる。例えば、読み出し中のデータは値が変化しないことから、同じタイミングで読み出し処理が発生しても、待たせる必要は無い。
     この時、データを読み出す際にかける共有ロック(Read Lock)と、書き込みの際にかけるロック占有ロック(Write Lock)がある。
   • 2相ロッキングプロトコル
     トランザクションのロックの操作は、ロックをかける操作が続く成長相と、ロックを解除する操作が続く縮退相に分けて行うことが多い。これを2相ロッキングプロトコルと言う。
2. 時刻印方式/タイムスタンプ方式(楽観的制御)
   データの競合の発生頻度が低い場合には、ロッキング方式は待ち処理時間が無駄となるため、同時アクセスを許す方式。ただし、あとで処理の発生した時間(タイムスタンプ)を確認し不都合が判明した場合は、処理の記録をもとにロールバックしてやり直す方式。

デッドロック

複数のトランザクションの実行時には、相互の関係から、処理がうまく進まない場合も発生する。(お互いが相手の処理をロックする状態で、ロック解除が発生しない。)

このような状態をデッドロックと呼び、この状態が発生すると処理が停止してしまうこともある。このような状態は、避けられない場合もあるが、どの処理が何を使うのか、どのデータはどの処理の終了を待っているのかといった資源の状態をグラフ理論で表現したもの資源グラフをで表現し、グラフが巡回するようであれば、デッドロックが発生する可能性がある。

グラフ理論(Wikipedia)

前述の資源グラフをコンピュータで扱う場合には、グラフ理論が用いられる。グラフ理論では、ノード間の接続に方向の概念が無い物は無向グラフと呼ぶ。また、ノードの接続関係は隣接行列で表現する。行と列がそれぞれノードに対応付け経路が存在する場所を1で表す。データベースの資源グラフのような方向性がある場合は有向グラフと呼び、始点(行)と終点(列)の経路がある所を1で表す。

ここまでの授業では、プログラムを動かすうえでアルゴリズムとデータ構造を中心に話をしてきた。しかしプログラムの中で利用しているデータがどういったメモリで管理されているのかを正しく理解する必要がある。そこで、局所変数のようなデータを保存するためのスタック領域と、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() が呼び出される処理では、

1. 関数呼び出し時には、戻り番地の保存、実引数の確保が行われ、
2. 関数に入った時点で局所変数の領域が確保される。
3. 関数が終わると、実引数・局所変数の領域が消され、スタックから取り出された戻り番地に処理を移行する。

このような関数呼び出しでは、最後(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)
}

• C言語でリストの和集合

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 ) ;
    }
}

• Javaでリストの和集合

このプログラムを実行すると、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: そのようなファイルやディレクトリはありません