Java并發編程之同步互斥問題

作者：rommel1 2012-03-09 10:44:11

在操作系統中同步與互斥是一個重要問題，這里主要研究一下怎樣用Java來實現操作系統中的一些同步互斥算法。

1、軟件實現臨界區域問題

在《操作系統概念(第七版)》中，7.2討論了臨界區域問題，下面給出算法和Java實現代碼。

1.1 算法2

算法2的偽代碼如下：

do{  
 flag[i]=true;  
 while(flag[j]);  
 臨界區；  
 flag[i]=false;  
 剩余區；  
}while(1)

Java實現代碼如下：

package mutiple_thread;  
 
public class OS_SYN_A2{  
    public static  int flag[]=new int [3];  
    public static int cnt=0;  
    public static void main(String args[]){  
        class proo implements Runnable{  
            public proo(){  
                  
            }  
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                while(true){  
                    flag[1]=1;  
                    while(flag[2]==1){  
                          
                    }  
                    if(cnt==5){  
                        flag[1]=0;  
                    }else{  
                        cnt++;  
                        System.out.println("pro ++! now id"+cnt);  
                        flag[1]=0;  
                    }  
                }  
            }  
              
        }  
 
        class conn implements Runnable{  
 
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                while(true){  
                    flag[2]=1;  
                    while(flag[1]==1){  
                          
                    }  
                    //臨界區  
                    if(cnt==0){  
                        flag[2]=0;  
                    }else{  
                        cnt--;  
                        System.out.println("con --! now id"+cnt);  
                        //退出臨界區  
                        flag[2]=0;  
                    }  
                }  
            }  
        }  
        new Thread(new proo()).start();  
        new Thread(new conn()).start();  
    }  
      
}

這個算法的主要思路是通過設置flag來確定執行哪個線程，但是可能會造成饑餓，因此不行。

1.2 算法3

算法3通過共享兩個變量 flag 和turn來實現同步。

package mutiple_thread;  
 
public class OS_SYN_A3{  
    public static  int flag[]=new int [3];  
    public static int turn=0;  
    public static int cnt=0;  
    public static void main(String args[]){  
        class proo implements Runnable{  
            public proo(){  
                  
            }  
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                while(true){  
                    flag[1]=1;  
                    turn=2;  
                    while(flag[2]==1&&turn==2){  
                          
                    }  
                    if(cnt==5){  
                        flag[1]=0;  
                    }else{  
                        cnt++;  
                        System.out.println("pro ++! now id"+cnt);  
                        flag[1]=0;  
                    }  
                }  
            }  
              
        }  
 
        class conn implements Runnable{  
 
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                while(true){  
                    flag[2]=1;  
                    turn=1;  
                    while(flag[1]==1&&turn==1){  
                          
                    }  
                    //臨界區  
                    if(cnt==0){  
                        flag[2]=0;  
                    }else{  
                        cnt--;  
                        System.out.println("con --! now id"+cnt);  
                        //退出臨界區  
                        flag[2]=0;  
                    }  
                }  
            }  
        }  
        new Thread(new proo()).start();  
        new Thread(new conn()).start();  
    }  
      
}

這是一種正確的軟件實現方法。

2、經典同步問題的Java實現

2.1 讀者寫者問題

這里實現的讀者優先的算法，使用了Java并發包的信號量來實現。

實現的偽代碼如下：

讀者進程：

while（1）{  
 wait(mutex)  
   count++;  
   if(readercount==1){  
   wait(writer);   
 }  
signal(mutex);  
do reading;  
wait(mutex);  
cnt--;  
if(cnt==0){  
  signal(writer);  
}  
signal(mutex);  
}  
}

算法通過共享writer和mutex兩個信號量，來處理同步問題

package mutiple_thread;  
 
import java.util.concurrent.Semaphore;  
 
public class OS_Readerwriter{  
    static Semaphore sem=new Semaphore(1);  
    static Semaphore sem_wrt=new Semaphore(1);  
    static int readercount=0;  
    static String a="hahaha";  
    public static void main(String args[]){  
        class reader implements Runnable{  
            public reader(){  
                  
            }  
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                try {  
                    sem.acquire();  
                    readercount++;  
                } catch (InterruptedException e) {  
                    // TODO Auto-generated catch block  
                    e.printStackTrace();  
                }  
                if(readercount==1){  
                    try {  
                        sem_wrt.acquire();  
                    } catch (InterruptedException e) {  
                        // TODO Auto-generated catch block  
                        e.printStackTrace();  
                    }  
                }  
                sem.release();  
                  
                System.out.println("Reading "+a);  
                  
                try {  
                    sem.acquire();  
                } catch (InterruptedException e) {  
                    // TODO Auto-generated catch block  
                    e.printStackTrace();  
                }  
                readercount--;  
                if(readercount==0){  
                    sem_wrt.release();  
                }  
                sem.release();  
            }  
        }  
          
        class writer implements Runnable{  
            public writer(){  
                  
            }  
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                try {  
                    sem_wrt.acquire();  
                } catch (InterruptedException e) {  
                    // TODO Auto-generated catch block  
                    e.printStackTrace();  
                }  
                a=a+"abc";  
                System.out.println("Writing "+a);  
                sem_wrt.release();  
            }  
              
        }  
        for(int i=1;i<=10;i++){  
            new Thread(new writer()).start();  
            new Thread(new reader()).start();  
        }  
          
    }  
}

2.2 哲學家問題

算法思路：通過對每一只筷子設置信號量，來進行同步判斷。

Java實現代碼如下：

package mutiple_thread;  
 
import java.util.concurrent.Semaphore;  
 
public class OS_Philosopher{  
    static int chop[]=new int [7];  
    static Semaphore []sem=new Semaphore[7];  
      
    public static void main(String args[]) throws InterruptedException{  
        for(int i=0;i<=6;i++){  
            sem[i]=new Semaphore(1);  
        }  
        Thread.sleep(1000);  
        class philosopher implements Runnable{  
            int i;  
            public philosopher(int i){  
                this.i=i;  
            }  
 
            @Override 
            public void run() {  
                // TODO Auto-generated method stub  
                while(true){  
                    try {  
                        synchronized(this){  
                            sem[i].acquire();  
                            sem[(i+1)%5].acquire();  
                        }  
                          
                    } catch (InterruptedException e) {  
                        // TODO Auto-generated catch block  
                        e.printStackTrace();  
                    }  
                    System.out.println("Phi"+i+" is Eating");  
                    //sleep();  
                    try {  
                        Thread.sleep(1);  
                    } catch (InterruptedException e) {  
                        // TODO Auto-generated catch block  
                        e.printStackTrace();  
                    }  
                    sem[i].release();  
                    sem[(i+1)%5].release();  
                    System.out.println("Phi"+i+" is Thinking");  
                    //sleep();  
                    try {  
                        Thread.sleep(1);  
                    } catch (InterruptedException e) {  
                        // TODO Auto-generated catch block  
                        e.printStackTrace();  
                    }  
                }  
            }  
        }  
        philosopher t1=new philosopher(1);  
        philosopher t2=new philosopher(2);  
        philosopher t3=new philosopher(3);  
        philosopher t4=new philosopher(4);  
        philosopher t5=new philosopher(5);  
        new Thread(t1).start();  
        new Thread(t2).start();  
        new Thread(t3).start();  
        new Thread(t4).start();  
        new Thread(t5).start();  
          
    }  
}

2.3 理發店問題：

理發店理有一位理發師、一把理發椅和 5 把供等候理發的顧客坐的椅子。如果沒有顧客，理發師便在理發椅上睡覺。一個顧客到來時，它必須叫醒理發師。如果理發師正在理發時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開。

算法思路如下：采用信號量進行判斷。初始值為1，即是有一個理發師在服務。

實現代碼如下：

package mutiple_thread;  
 
import java.util.concurrent.Semaphore;  
 
public class OS_Barber1{  
    static int cnt = 0;  
    static int MAX = 5;  
    static int busy = 0;  
    static Semaphore sem=new Semaphore(1);  
    public static void main(String args[]) throws InterruptedException{  
        OS_Barber1 bar=new OS_Barber1();  
        for(int i=1;i<=20;i++){  
            new Thread(new Bar1(bar,i)).start();  
            Thread.sleep((int) (400 - Math.random() * 300));  
        }  
    }  
    public synchronized boolean isFull() {  
        if (cnt == MAX) {  
            return true;  
        }  
        return false;  
    }  
 
    public synchronized boolean isEmpty() {  
        if (cnt == 0) {  
            return true;  
        }  
        return false;  
    }  
 
    public synchronized boolean isBusy() {  
        if (busy == 1) {  
            return true;  
        }  
        return false;  
    }  
      
    public  void Gobar(int index) throws InterruptedException{  
          
          
        System.out.println("Con"+index+" is coming");  
        cnt++;  
        //判斷是否滿  
        if(isFull()){  
            System.out.println("Is full,"+"Con"+index+" is leaving");  
            cnt--;  
        }else{  
            if(busy==1){  
                System.out.println("Con"+index+" is waitting");  
            }  
            //sem.acquire();  
            synchronized (this){  
                while(busy==1){  
                    //若有人在理發，則等待  
                    wait();  
                }  
            }  
              
            if(cnt==1){  
                System.out.println("Con"+index+" is wake");  
            }  
            busy=1;  
            System.out.println("Con"+index+" is Serving");  
            Thread.sleep(1000);  
            System.out.println("Con"+index+" is leaving");  
            cnt--;  
            //sem.release();  
            synchronized (this){  
                busy=0;  
                //喚醒  
                notify();  
            }  
            if(cnt==0){  
                System.out.println("Bar is sleep");  
            }  
        }  
    }  
}  
class Bar1 implements Runnable {  
    OS_Barber1 ob;  
    int index;  
    public Bar1(OS_Barber1 ob,int i) {  
        this.ob = ob;  
        index=i;  
    }  
 
    @Override 
    public void run() {  
        // TODO Auto-generated method stub  
        try {  
            ob.Gobar(index);  
        } catch (InterruptedException e) {  
            // TODO Auto-generated catch block  
            e.printStackTrace();  
        }  
    }  
 
}

在算法中我使用了wait(),notify()來實現，也可以使用信號量來實現，注釋部分就是使用信號量的實現。

在實現過程中，我發現了一些問題，也就是下面要討論的wait() 和notify() 和notifyAll()

3、 wait() ，notify() 和notifyAll()

synchronized 方法控制對類成員變量的訪問：每個類實例對應一把鎖，每個 synchronized 方法都必須獲得調用該方法的類實例的鎖方能執行，否則所屬線程阻塞，方法一旦執行，就獨占該鎖，直到從該方法返回時才將鎖釋放，此后被阻塞的線程方能獲得該鎖，重新進入可執行狀態。

wait()/notify()：調用任意對象的 wait() 方法導致線程阻塞，并且該對象上的鎖被釋放。而調用任意對象的notify()方法則導致因調用該對象的 wait() 方法而阻塞的線程中隨機選擇的一個解除阻塞（但要等到獲得鎖后才真正可執行）。

synchronized和wait()、notify()的關系

1.有synchronized的地方不一定有wait,notify

2.有wait,notify的地方必有synchronized.這是因為wait和notify不是屬于線程類，而是每一個對象都具有的方法，而且，這兩個方法都和對象鎖有關，有鎖的地方，必有synchronized。

另外，請注意一點：如果要把notify和wait方法放在一起用的話，必須先調用notify后調用wait，因為如果調用完wait，該線程就已經不是current thread了。

注：調用wait()方法前的判斷***用while，而不用if；while可以實現被wakeup后thread再次作條件判斷；而if則只能判斷一次；

線程的四種狀態

新狀態：線程已被創建但尚未執行（start() 尚未被調用）。
可執行狀態：線程可以執行，雖然不一定正在執行。CPU 時間隨時可能被分配給該線程，從而使得它執行。
死亡狀態：正常情況下 run() 返回使得線程死亡。調用 stop()或 destroy() 亦有同樣效果，但是不被推薦，前者會產生異常，后者是強制終止，不會釋放鎖。
阻塞狀態：線程不會被分配 CPU 時間，無法執行。

首先，前面敘述的所有方法都隸屬于 Thread 類，但是這一對 (wait()/notify()) 卻直接隸屬于 Object 類，也就是說，所有對象都擁有這一對方法。初看起來這十分不可思議，但是實際上卻是很自然的，因為這一對方法阻塞時要釋放占用的鎖，而鎖是任何對象都具有的，調用任意對象的 wait() 方法導致線程阻塞，并且該對象上的鎖被釋放。而調用任意對象的notify()方法則導致因調用該對象的 wait() 方法而阻塞的線程中隨機選擇的一個解除阻塞（但要等到獲得鎖后才真正可執行）。

其次，前面敘述的所有方法都可在任何位置調用，但是這一對方法卻必須在 synchronized 方法或塊中調用，理由也很簡單，只有在synchronized 方法或塊中當前線程才占有鎖，才有鎖可以釋放。

同樣的道理，調用這一對方法的對象上的鎖必須為當前線程所擁有，這樣才有鎖可以釋放。因此，這一對方法調用必須放置在這樣的synchronized 方法或塊中，該方法或塊的上鎖對象就是調用這一對方法的對象。若不滿足這一條件，則程序雖然仍能編譯，但在運行時會出現IllegalMonitorStateException 異常。

wait() 和 notify() 方法的上述特性決定了它們經常和synchronized 方法或塊一起使用，將它們和操作系統的進程間通信機制作一個比較就會發現它們的相似性：synchronized方法或塊提供了類似于操作系統原語的功能，它們的執行不會受到多線程機制的干擾，而這一對方法則相當于 block 和wakeup 原語（這一對方法均聲明為 synchronized）。它們的結合使得我們可以實現操作系統上一系列精妙的進程間通信的算法（如信號量算法），并用于解決各種復雜的線程間通信問題。關于

wait() 和 notify() 方法***再說明兩點：

***：調用 notify() 方法導致解除阻塞的線程是從因調用該對象的 wait() 方法而阻塞的線程中隨機選取的，我們無法預料哪一個線程將會被選擇，所以編程時要特別小心，避免因這種不確定性而產生問題。

第二：除了 notify()，還有一個方法 notifyAll() 也可起到類似作用，唯一的區別在于，調用 notifyAll() 方法將把因調用該對象的wait() 方法而阻塞的所有線程一次性全部解除阻塞。當然，只有獲得鎖的那一個線程才能進入可執行狀態。

談到阻塞，就不能不談一談死鎖，略一分析就能發現，suspend() 方法和不指定超時期限的 wait() 方法的調用都可能產生死鎖。遺憾的是，Java 并不在語言級別上支持死鎖的避免，我們在編程中必須小心地避免死鎖。

以上我們對 Java 中實現線程阻塞的各種方法作了一番分析，我們重點分析了 wait() 和 notify()方法，因為它們的功能***大，使用也最靈活，但是這也導致了它們的效率較低，較容易出錯。實際使用中我們應該靈活使用各種方法，以便更好地達到我們的目的。

原文鏈接：http://blog.csdn.net/rommel1/article/details/7322327

【編輯推薦】

Java web應用中的常見字符編碼問題的解決方法
Java中String.format的用法
如何在Oracle中使用Java存儲過程(詳解)
郵件功能開發：JavaMail
關于讀寫鎖算法的Java實現及思考

責任編輯：林師授來源： rommel1的博客

Java