哲学者アルゴリズム

哲学者アルゴリズム
 
 
オペレーティングシステムでは,反発リソースの使用によるデッドロック問題を回避するために,哲学者アルゴリズムという多くの解決方法がある.
まず哲学者のアルゴリズムとは何か、5人の哲学者がいて、彼らは思考と食事しかできませんが、丸いテーブルの上に箸が5本しかありません.これらの哲学者がいつ食べ物を食べに来るかは不確定です.つまり、同じ時間に5人が食事に来るかもしれません.一人もいないかもしれません.食事をするには、箸が2足必要なので、箸を取る方法を約束します.制約がない場合は、次の状況が発生する可能性があります.
1、哲学者が食事をするときにまず自分の左側の箸を取ると仮定すると、ある瞬間に5人が同時に食事をして同時に左の箸を取った可能性があり、もう1本の箸が得られないときに箸を置いて同時に自分の右側の箸を取って、このように繰り返している.プログラムが前に進まない.
2、哲学者が食事をするときにまず左側の箸を取って、右側の箸を検査し、右側の箸が使わなければ、自分が取った箸を置いて、しばらくしてからこの過程を繰り返すと仮定します.この方法は実行可能に見えますが、よく考えてみると1の中の状況とは差が少なく、ある瞬間、5人が同時にこの方法を有効にして、また1の中の状況が現れるかもしれません.のプログラムはまだ実行されません.
このような状況を避けるために、哲学者のアルゴリズムがあり、その一つの案は:
1、3、5(奇数)番哲学者はそれぞれ自分の一番近い奇数番の箸を取って、それから自分の一番近い右側の箸を取って、2、4(偶数)番はそれぞれ右側の一番近い奇数番の箸を取って、それから自分の一番近い偶数番の箸を競争します.哲学者はまず奇数位の箸を競争して、それから偶数位の箸を競争して、いつもご飯を食べることができて、しかもFIFOの列によって、他の待っている哲学者は順番に箸を手に入れて食事をするので、プログラムの正常な運行を実現することができます.具体的なコードは以下の通りです.
 
 

package Philosopher;

public class Semaphore {
	int count;//         。
	public Semaphore (int count){
		this.count=count;
	}
	//    p  
	public synchronized void P(){
		count--;
		if(count<0){//      0，        ，     。
			try {
				wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
	//    v  
	public synchronized void V(){
		count++;
		if(count<=0){//     0，        。
			notify();
		}
	}
}

 
上記のP操作とV操作は、実行中に停止できない元の操作のセットであり、コンピュータの原語に属します.具体的な知識はオペレーティングシステムの原理を参照してください.
 

public class Philosopher extends Thread{
	
	private int n;
	
	public Philosopher(int n){
		this.n=n;
	}
	
	//  run  
	public void run(){
		/**
		 *       ，  :
		 * Philosopher               ,               。
		 */
		while(true){
		if(n%2==0){
			System.out.println("Philosopher"+n+"    "+(n+1)%5+"    ");
			Starteat .chopsticks[(n+1)%5].P();
			System.out.println("Philosopher"+n+"    "+(n+1)%5+"   ");
			System.out.println("Philosopher"+n+"    "+(n)%5+"   ");
			Starteat .chopsticks[(n)%5].P();
			System.out.println("Philosopher"+n+"    "+(n)%5+"   ");
			System.out.println("Philosopher"+n+"     。。。。。。");
			try {
				Thread.sleep(1);//    。。
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			Starteat .chopsticks[(n+1)%5].V();
			Starteat .chopsticks[(n)%5].V();
			System.out.println("Philosopher"+n+"    "+n+" "+n+1);
			System.out.println("Philosopher"+n+"      。    。。。。");
		}
		else {
			System.out.println("Philosopher"+n+"    "+(n)%5+"   ");
			Starteat .chopsticks[(n)%5].P();
			System.out.println("Philosopher"+n+"    "+(n)%5+"   ");
			System.out.println("Philosopher"+n+"    "+(n+1)%5+"   ");
			Starteat .chopsticks[(n+1)%5].P();
			System.out.println("Philosopher"+n+"    "+(n+1)%5+"   ");
			System.out.println("Philosopher"+n+"     。。。。。。");
			try {
				Thread.sleep(1);//    。。
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			Starteat .chopsticks[(n+1)%5].V();
			Starteat .chopsticks[(n)%5].V();
			System.out.println("Philosopher"+n+"    "+n+" "+n+1);
			System.out.println("Philosopher"+n+"      。    。。。。");
			}
		}
	}
}

二人の間で箸を競うのでsemaphoreは1に設定します.

package Philosopher;

public class Starteat {
	
	static Semaphore [] chopsticks = new Semaphore [5];
	
	public static void main(String [] agrs){
		
		for(int i=0;i<5;i++){
			chopsticks[i] = new Semaphore(1);
		}
		for(int i=0;i<5;i++){
			new Philosopher(i).start();
		}
	}
}

 
コードの実現は比較的容易で、この方法は哲学者のアルゴリズムの一つにすぎず、同時に食事をする人数(最大4人が同時に食事をすることしか許されないなど)を制限して哲学者の食事飢え死にの問題を解決することもできます.ただ効率が違う.私のレベルは限られているので、足りないところは皆さん、ご容赦ください.