排他制御

9-1. 排他制御

排他制御の考え方

並列処理において、共有資源を利用する場合、競合が発生します。あらゆる競合の完全な解決は未解決問題ですが、さまざまな定石やプログラミングテクニックで避けることができます。

Webができ始めたときにカウンターがしばしばクラッシュしてましたので、今回はこれを取り上げます。 Webで当時「ようこそあなたはxxx人目のお客様です」という表示が流行ったのですが、これは、人数を入れたファイルを用意しておいて、Webサーバがアクセスされるたびに読み込んでは数を増やし格納していました。

これがクラッシュする仕組みは次のとおりです。 Webサーバは並列処理を前提としていて、アクセスされるたびにプロセスが起動し、処理を行います。そのため、複数のアクセスがあると複数のプロセスが同時に起動します。そのため、一つのカウンター用のファイルを複数のプロセスがアクセスすることになり、そこで競合が発生します。ファイルを書き込むのは一瞬でできないので、複数のプロセスが同じファイルを微妙な時間差で同時に書き込むと、ファイルに何が書かれるかが確定できません。

例9-1

カウンターが競合することを体験してみましょう。 git://edu.net.c.dendai.ac.jp/git/spro/9/1

Constant.java


public class Constant {
	public static final int n = 100;
	public static final int k = 1000000;
}

Counter.java


public interface Counter {
	void increment();
	int get();
}

Counter1.java


public class Counter1 implements Counter {
	private int value;
	public Counter1() {
		value=0;
	}
	@Override
	public  void increment() {
		value++;
	}
	@Override
	public int get() {
		return value;
	}
}

CounterTester.java

package spro91;
public class CounterTester  {
	private Counter counter;
	private int freq;
	private Tester[] testerArray;
	private int n;
	public void setCounter(Counter c) {
		counter = c;
	}
	public void setFrequency(int k) {
		freq = k;
	}
	public CounterTester(int n) {
		this.n = n;
		testerArray = new Tester[n];
		for(int i=0; i<n; i++) {
			testerArray[i] = new Tester();
		}
	}
	public void start() throws InterruptedException {
		for(int i=0; i<n; i++) {
			testerArray[i].start();
		}
		for(int i=0; i<n; i++) {
			testerArray[i].join();
		}
	}
	public int get() {
		return counter.get();
	}
	class Tester extends Thread {
		@Override
		public void run() {
			for(int i=0; i<freq; i++) {
				counter.increment();
			}	
		}
	}
}

Counter1Test.java


package spro91;
import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;
class Counter1Test {
	@Test
	void testGet() {
		CounterTester ct = new CounterTester(Constant.n);
		ct.setCounter(new Counter1());
		ct.setFrequency(Constant.k);
		try {
			ct.start();
		} catch (InterruptedException e) {
			fail("Exception is occured");
		}
		assertEquals(Constant.n*Constant.k,ct.get());
	}
}

このように、単なる変数を1増やす value++ という処理だけで、競合が発生し、期待した動作ができないことがわかります。

アトミック

様々な競合において、本質的なのは、同時に処理が発生すると動作が保証できなくなることです。これは、データの更新において、「読み込んで、変更し、書き込む」という動作において必然です。つまり、特定の連続した動作を単一のプロセスのみが連続して処理することが保証できれば解決します。

これを抽象化すると、２つの考え方ができます。

一連の動作を単一のプロセスが必ず連続して処理する概念
アクセス権を一つの資源とし、それが同時にひとつのプロセスしか専有できないように処理をする

一連の動作を単一のプロセスが連続して処理することをアトミックという用語で呼びます。つまり、アトミックに処理するなどといいます。

Java では java.util.concurrent.atomic パッケージにアトミックに処理できる資源が登録されていて、これを使う限り、使えるメソッドに関してはアトミックに処理できることが保証されています。

演習9-1

java.util.concurrent.atomic パッケージ内のクラスを使い、正常に動作するカウンター Counter2 を作りなさい。なお、Counter1Test をコピーし、 Counter1 を Counter2 に書き換えただけの Counter2Test クラスを作り、正常に動作することを確認しなさい。

セマフォ

複数のデータベースに渡る処理など、そもそもアトミックにできない処理の競合を制御するには、競合の制御が必要になります。これは一つのプロセスが処理を行っている際に、他のプロセスを止めておく必要があります。

セマフォとは本来は腕木信号機のことですが、排他制御において、抽象化した利用権をアトミックに確保、解除するものです。歴史的にP(),V()で表現されます。

P()は資源がある場合はアトミックに資源を確保し、正常終了するが、資源が開放されてない場合はブロッキングされます。
そして、V()で資源を開放します。

つまり、排他制御するプロセスは次のように記述します。


P();    
排他制御が必要なプロセス
V();

Java でこれを実現するには synchronized や java.util.concurrent パッケージがあります。単純な処理は synchronized で可能ですが、データベースのように読むのと書くので排他処理の仕方を変えるような場合は java.util.concurrent.lock 内にふさわしいものがあるかも知れません。

synchronized の使い方は2種類ありますので、それを説明します。

資源の利用権を抽象化するため、任意の一つのオブジェクトを定めます。そして、 synchronized でブロックを作ることで排他処理を行うことができます。

  
synchronized(obj){
排他処理
}

もう一つの用法はメソッドの修飾子として synchronized を使うことで、メソッドそのものを排他処理とすることができます。

  
synchronized void f(){
排他処理
}

java.util.concurrent.Semaphore クラスでも排他処理できます。 aquire メソッドで資源を獲得し、release メソッドで資源を開放します。

  
s = new Semaphore(1);

s.aquire();    
排他処理
s.release();

演習9-2

synchronized または java.util.concurrent パッケージ内のクラスを使い、正常に動作するカウンター Counter3 を作りなさい。なお、Counter1Test をコピーし、 Counter1 を Counter3 に書き換えただけの Counter3Test クラスを作り、正常に動作することを確認しなさい。

9-2. 次回

Android Studio をインストールしておいて下さい。