9. Guarded Suspension Pattern -- 要等到我準備好喔

   當光靠synchronized已經沒有辦法保護shared resource的時候，通常表示存取shared resource的時候需要條件，這時候就要設計Guarded Suspension Pattern。

   最常見的例子是client端以及server端的溝通，client端會不斷地送request給server，而server會不停地去收request，假設我們用queue去儲存request，那麼server就不能在queue為empty的時候去接收request，這個就是存取的條件---queue不能是empty。

   Request.java

   public class Request {
       private final String name;
       public Request(String name) {
           this.name = name;
       }
       public String getName() {
           return name;
       }
       public String toString() {
           return "[ Request " + name + " ]";
       }
   }
   

   RequestQueue.java，採用LinkedList來存放Request

   import java.util.LinkedList;
   public ...

   Read more...

   ---

10. Mutex

    如果可以不要用synchronized來做到thread-safe，那麼可以考慮使用mutex。

    現在來修改在Single Threaded Execution Pattern所用到的Gate類別。

    public class Gate {
        private int counter = 0;
        private String name = "Nobody";
        private String address = "Nowhere";
        private final Mutex mutex = new Mutex();
        public void pass(String name, String address) { // 並非synchronized
            mutex.lock();
            try {
                this.counter++;
                this.name = name;
                this.address = address;
                check();
            } finally ...

    Read more...

    ---

11. Producer-Consumer Pattern -- 我來做，你來用

    Producer-Consumer Pattern是架構在之前的Guarded Suspension Pattern上，例如Producer就是Client，負責發出request，而Consumer就是Server，負責接收request。 而重要的的地方在於存放Data的資料結構在Producer-Consumer Pattern會有Capacity的限制，如果Capacity是無限大的話，若是Producer速度很快，但是Consumer速度很慢，則Data會不斷地產生出來，那麼記憶體就會很快耗盡。

    以下舉一個廚師（Producer）跟客人（Consumer)的例子，廚師會不停地做蛋糕放到桌上（Table)，而客人會不停地拿蛋糕起來吃。桌子最多可以放三個蛋糕，若滿了，廚師就要等，若空了，客人就要等，Capacity大小可以調整兩邊的速度。

    廚師，MakerThread.java

    import java.util.Random;
    public class MakerThread extends Thread {
        private final Random random;
        private final Table table;
        private ...

    Read more...

    ---

12. Read-Write Lock Pattern -- 大家想看就看吧，不過看的時候不能寫喔

    Read-Write Lock Pattern 主要是分成讀跟寫的執行緒，當讀跟讀之間的執行緒不需要共用互斥時，而且讀的頻率很高的時候，使用這個 Pattern 效率會很好。這個 Pattern 的重點在於，他沒有 read-read conflict，但是其他三種組合會有 conflict，例如 read-write conflict，因此需要做共用互斥。

    在範例程式碼中，preferWriter 欄位就是用來讓 ReaderThread 以及 WriterThread 可以輪流執行。

    所有參與者

    Reader

    Reader 會對 SharedResource 進行 read。例如 ReaderThread 類別。

    Writer

    Writer 會對 SharedResource 進行 write。例如 WriterThread 類別。

    SharedResource

    SharedResource 代表 ...

    Read more...

    ---

13. Single Threaded Execution Pattern

    Single Threaded Execution Pattern

    是指我們的方法限定一次只能由一個執行緒所執行。

    假設我們有一個Gate，一次只能夠限定一個人通過，現在我們有多個人（多個thread)要通過這個門，每次通過之後Gate會顯示通過的人的name以及address，同時Gate會用一個counter來紀錄目前有多少人通過。

    Gate.java

        public class Gate {
        private int counter = 0;
        private String name = "Nobody";
        private String address = "Nowhere";
        //加入synchronized限制一次只能由一個thread來執行這個pass
        public synchronized void pass(String name, String address) {
            this.counter ...

    Read more...

    ---

14. Two-Phase Termination Pattern -- 快把玩具收拾好，去睡覺吧

    Two-Phase Termination Pattern 是用來確實地進行結束的動作後，再結束掉執行緒。

    我們將執行緒進行平常的處理的狀態稱為作業中。當希望結束這個執行緒時，則送出中止請求。接著這個執行緒，並不會馬上結束，而會開始進行必要的善後工作。這個狀態稱為終止處理中。從作業中改變成終止處理中是第一階段。

    終止處理中的狀態並不會進行平常的動作。雖然執行緒還在運行，但進行的是終止處理。直到終止處理中結束後，才真正結束執行緒。終止處理中的動作結束，是第二階段。

    先從作業中進入終止處理中狀態，再真正結束掉執行緒。主要考慮的關鍵如下：

    • 安全地結束(安全性)
    • 一定會進行終止處理(生命性)
    • 收到終止請求後，要盡快開始終止處理(回應性)

    範例程式

    有一條執行緒會在每隔約 500 毫秒將計數遞增 1 ...

    Read more...

    ---

15. ACM UVA-10020

    這題是greedy。

    首先以左端點排序所有線段，一開始邊界的左端為0，所以找所有線段的左端點小於等於0的，然後右端點是最長的，接著把右端點設成邊界的左端，接著又是解決同樣的子問題。

    //ignore header files
    struct line{
        int left,right;
        line(int a,int b){
            left = a;
            right = b;
        }
        bool operator<(const line & lvalue) const{
            return left<lvalue.left;
        }
    };
    int main(int argc, char const* argv[])
    {
        int n;
        while(scanf("%d",&n) != EOF){
        for(int ...

    Read more...

    ---

16. ACM UVA-10034

    這題是典型的Minimum Spanning Tree，我用Prims Algorithm。

    //ignore header files
    #define dis(p1,p2) sqrt(((p1.x-p2.x)*(p1.x-p2.x))+((p1.y-p2.y)*(p1.y-p2.y)))
    struct point{
        double x,y;
        int num;
        point(double a,double b,int c){
            x = a;
            y = b;
            num = c;
        }
    };
    struct Edge{
        int n;
        double ...

    Read more...

    ---

17. ACM UVA-10057

    中位數問題。

    //ignore header files
    int main(int argc, char const* argv[])
    {
        int n;
        int input[1000000];
        while(scanf("%d",&n) != EOF){
            map<int,int> t;
            for(int i = 0;i<n;i++){
                int m;
                scanf("%d",&m);
                input[i] = m;
                if(t[m] == false){
                    t[m] = 1;
                }else{
                    t[m ...

    Read more...

    ---

18. ACM UVA-10104

    題目

    用gcd解。

    //ignore header files
    void gcd(long long a,long  long b,int &i,int &j,int &d){
        if(b == 0){
            d = a;
            i = 1;
            j = 0;
        }else{
            gcd(b,a%b,j,i,d);
            j = j-(a/b)*i;
        }
    }
    int main(int argc, char const* argv[])
    {
        long long ...

    Read more...

    ---

« Page 8 / 13 »