在操作系統(tǒng)中同步與互斥是一個(gè)重要問題，這里主要研究一下怎樣用Java來實(shí)現(xiàn)操作系統(tǒng)中的一些同步互斥算法。

1、軟件實(shí)現(xiàn)臨界區(qū)域問題

在《操作系統(tǒng)概念(第七版)》中，7.2討論了臨界區(qū)域問題，下面給出算法和Java實(shí)現(xiàn)代碼。

1.1 算法2

算法2的偽代碼如下：

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

Java實(shí)現(xiàn)代碼如下：

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){  
                          
                    }  
                    //臨界區(qū)  
                    if(cnt==0){  
                        flag[2]=0;  
                    }else{  
                        cnt--;  
                        System.out.println("con --! now id"+cnt);  
                        //退出臨界區(qū)  
                        flag[2]=0;  
                    }  
                }  
            }  
        }  
        new Thread(new proo()).start();  
        new Thread(new conn()).start();  
    }  
      
} 

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

1.2 算法3

算法3通過共享兩個(gè)變量 flag 和turn來實(shí)現(xiàn)同步。

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){  
                          
                    }  
                    //臨界區(qū)  
                    if(cnt==0){  
                        flag[2]=0;  
                    }else{  
                        cnt--;  
                        System.out.println("con --! now id"+cnt);  
                        //退出臨界區(qū)  
                        flag[2]=0;  
                    }  
                }  
            }  
        }  
        new Thread(new proo()).start();  
        new Thread(new conn()).start();  
    }  
      
} 

這是一種正確的軟件實(shí)現(xiàn)方法。

2、經(jīng)典同步問題的Java實(shí)現(xiàn)

2.1 讀者寫者問題

這里實(shí)現(xiàn)的讀者優(yōu)先的算法，使用了Java并發(fā)包的信號量來實(shí)現(xiàn)。

實(shí)現(xiàn)的偽代碼如下：

讀者進(jìn)程：

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兩個(gè)信號量，來處理同步問題

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 哲學(xué)家問題

算法思路：通過對每一只筷子設(shè)置信號量，來進(jìn)行同步判斷。

Java實(shí)現(xiàn)代碼如下：

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 理發(fā)店問題：

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

算法思路如下：采用信號量進(jìn)行判斷。初始值為1，即是有一個(gè)理發(fā)師在服務(wù)。

實(shí)現(xiàn)代碼如下：

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){  
                    //若有人在理發(fā)，則等待  
                    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()來實(shí)現(xiàn)，也可以使用信號量來實(shí)現(xiàn)，注釋部分就是使用信號量的實(shí)現(xiàn)。

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

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

synchronized 方法控制對類成員變量的訪問：每個(gè)類實(shí)例對應(yīng)一把鎖，每個(gè) synchronized 方法都必須獲得調(diào)用該方法的類實(shí)例的鎖方能執(zhí)行，否則所屬線程阻塞，方法一旦執(zhí)行，就獨(dú)占該鎖，直到從該方法返回時(shí)才將鎖釋放，此后被阻塞的線程方能獲得該鎖，重新進(jìn)入可執(zhí)行狀態(tài)。

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

synchronized和wait()、notify()的關(guān)系

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

2.有wait,notify的地方必有synchronized.這是因?yàn)閣ait和notify不是屬于線程類，而是每一個(gè)對象都具有的方法，而且，這兩個(gè)方法都和對象鎖有關(guān)，有鎖的地方，必有synchronized。

另外，請注意一點(diǎn)：如果要把notify和wait方法放在一起用的話，必須先調(diào)用notify后調(diào)用wait，因?yàn)槿绻{(diào)用完wait，該線程就已經(jīng)不是current thread了。

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

線程的四種狀態(tài)

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

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

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

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

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

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

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

第二：除了 notify()，還有一個(gè)方法 notifyAll() 也可起到類似作用，唯一的區(qū)別在于，調(diào)用 notifyAll() 方法將把因調(diào)用該對象的wait() 方法而阻塞的所有線程一次性全部解除阻塞。當(dāng)然，只有獲得鎖的那一個(gè)線程才能進(jìn)入可執(zhí)行狀態(tài)。

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

以上我們對 Java 中實(shí)現(xiàn)線程阻塞的各種方法作了一番分析，我們重點(diǎn)分析了 wait() 和 notify()方法，因?yàn)樗鼈兊墓δ?**大，使用也最靈活，但是這也導(dǎo)致了它們的效率較低，較容易出錯(cuò)。實(shí)際使用中我們應(yīng)該靈活使用各種方法，以便更好地達(dá)到我們的目的。

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

【編輯推薦】

1. Java web應(yīng)用中的常見字符編碼問題的解決方法
2. Java中String.format的用法
3. 如何在Oracle中使用Java存儲過程(詳解)
4. 郵件功能開發(fā)：JavaMail
5. 關(guān)于讀寫鎖算法的Java實(shí)現(xiàn)及思考