1. 關不掉的 Vista UAC !?

    不知道是更新了啥 PATCH,還是那次沒正常關機,我公司 VISTA 的 UAC 突然莫名奇妙的被打開了。怪的是控制台裡看到的還是關掉的,不管怎麼改狀態也不會改變 (一直都是關的) ...。

    直覺告訴我一定是控制台的 AP 那邊出問題,設定值寫不進去造成的...,於是我就開使找其它可以修改 UAC 設定的方法...,最後找到這個,還真的成功了 :D,看來沒機會動用 ProcessMonitor 追追看問題了..

    找到的方法是: msconfig.exe

    在開始 --> 執行裡輸入 msconfig.exe 後,可以看到這一項:

    image

     

    看來是直接修改 registry, 果然有效,直接執行後 REBOOT 就一切正常了 -_-, 如果有人也碰過一樣的問題可以試看看!

    2008/10/31 Tips

  2. 該如何學好 "寫程式" #4. 你的程式夠 "可靠" 嗎?

    撐了很久,續篇來了。這次要進階一點,直接從 software engineer (軟體工程師) 的階段開始。   所謂的軟體工程師,我對它的定義是在這個領域已經算是資深人員了。programmer 該作的是把程式寫好,要挑正確的方式及技術寫好你的程式 (如之前幾篇介紹的演算法及資料結構等等)。而軟體工程師呢? 之前介紹的那些已經不夠了,你該好好的安排你的 code 及工具,要能把你的 solution (如會用到的演算法及資料結構),跟你手上能運用的資源 (如程式語言、開發工具及函式庫) 作最佳化的搭配及整合。因此我認為在這階段的重點有幾個:

    1. 先成為一個好的 programmer (廢話)
    2. 程式要有足夠的可靠性 (穩定、沒有BUG、易讀、對於未知問題的防禦能力)
    3. 要有足夠的系統知識 (比如作業系統/API/系統服務/記憶體管理等等 OS 提供的環境及功能)
    4. 程式要有好的結構 (正確/優秀的類別設計、好維護、有足夠的擴充及應變能力)
    5. 要有解決未知問題或是未知 BUG 的能力,有自行學習新知的能力。
    這些能力,跟 programmer 需要俱備的剛好是另一個角度的要求。某種程度上是各自發展的,不會互相衝突。有心的 programmer 應該要及早作好準備。如果 programmer 是要把程式寫對,那 software engineer 就是要把程式寫好,用專業的方式來寫,而不是用業餘的方式。 什麼叫作 "專業" 的程式? 我舉幾個例子,你的程式防呆嗎? 你的程式面對未知的問題或狀況的免疫力夠不夠強? 面對問題時你的程式有沒有比其它人的程式還容易抓出 BUG ? 你有能力有系統的找出未知的問題嗎? 還是只能看著程式碼發呆? 面對上面的問題有沒有有效的預防措施? 設計階段可以怎樣預防? ... etc 實在太多了。不過這些看起來又是教條,實際上這幾點會影響的到底是什麼? 後面幾篇就一項一項來看吧!   [程式要有足夠的可靠性] 老實說,我很怕光是這一段,就會拖到好幾篇了 ... @_@,我會盡量挑出重點來寫。開始之前先問一下,不知道有多少人看過馬奎爾 (Steve Maguire) 寫的這本書? 有的話記得留個回應 :D "完美程式設計指南" (Writing Solid Code) 這本書真是經典。不過它真的也很 "經典",是 1993 年就出版的書。以講程式設計來說,這個年代的書真的可以扔了,裡面的範例現在沒幾個人用的到了。不過它提到的作法真的是很實際,只是書上的範例大半都過時了,下面碰到的例子我都會用 C# 重新表達一次作者的理念。在這個主題我就舉幾個例子,各位讀者可以自己回顧一下你的程式碼,到底藏了多少地雷在裡面?   [要讓問題浮現出來: 善用 DEBUG / RELEASE 模式] 專不專業就看這裡了。如果你想當個稱職的軟體工程師,除了讓程式跑的快之外,第一點就是要降低 BUG 數。如果你面對 BUG 的態度是 "找到再改就好",或是 BUG 一堆你也沒方法去預防,也沒辦法降低 BUG 出現的頻率,那麼你跟半路出家的人差別在那? 大家都知道 Visual Studio 正上方就有個切換 Release / Debug 模式的選單吧? 你確切瞭解它是幹嘛的嗎? 先從一個簡單的範例開始吧! 我工作上常碰到線上測驗之類的應用軟體開發,因此線上考試算分是個很常用的功能。因此我把這個重責大任交給工程師來處理。先來看看我要求工程師寫什麼 CODE ? 我用 XML 定義了一份考卷 (QUIZ.xml,含正確答案),也定義了答案卷的格式 (PAPER-XXXX.xml),程式很簡單,就是拿到題目跟答案卷後,要算出正確的總分。 不難吧? 先看看 XML 檔長啥樣子:
    試卷 (QUIZ.xml)[copy code]
    <?xml version="1.0" encoding="utf-8" ?>
    <quiz>
      <question score="20">
        <body>那一隻熊最勵害?</body>
        <item correct="false">白熊</item>
        <item correct="false">黑熊</item>
        <item correct="false">棕熊</item>
        <item correct="true">灰熊</item>
      </question>
     
      <question score="40">
        <body>誰發現萬有引力?</body>
        <item correct="false">鼠頓</item>
        <item correct="true">牛頓</item>
        <item correct="false">虎頓</item>
        <item correct="false">兔頓</item>
      </question>
     
      <question score="40">
        <body>下列那些東西是可以吃的?</body>
        <item correct="false">東瓜</item>
        <item correct="true">西瓜</item>
        <item correct="true">南瓜</item>
        <item correct="false">北瓜</item>
      </question>
    </quiz>
        再來代表答案卷的檔案 (PAPER-PERFECT.xml),這份看來是天才寫的,每一題都答對了... @_@
    答案卷 (都是正確答案,PAPER-PERFECT.xml)[copy code]
    <?xml version="1.0" encoding="utf-8" ?>
    <quiz>
      <question>
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
        <item checked="true" />
      </question>
      <question>
        <item checked="false" />
        <item checked="true" />
        <item checked="false" />
        <item checked="false" />
      </question>
      <question>
        <item checked="false" />
        <item checked="true" />
        <item checked="true" />
        <item checked="false" />
      </question>
    </quiz>
        而我交待的算分規則也很簡單,就一般考試的計算方式: 每題有自己的配分,以複選題來算,答對幾個選項就照比例給分,答錯會倒扣。新人工程師果然好用耐操,不一會就交給我這份 Library 的程式碼:
    第一版計分程式[copy code]
    public static int ComputeQuizScore(XmlDocument quizDoc, XmlDocument paperDoc)
    {
        int questionCount = quizDoc.SelectNodes("/quiz/question").Count;
        int totalScore = 0;
        for (int questionPos = 0; questionPos < questionCount; questionPos++)
        {
            XmlElement quiz_question = quizDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement;
            XmlElement paper_question = paperDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement;
            totalScore += ComputeQuestionScore(quiz_question, paper_question);
        }
        return totalScore;
    }
    public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question)
    {
        int totalScore = 0;
        int itemCount = quiz_question.SelectNodes("item").Count;
        //
        //  題目的配分
        //
        int quiz_score = int.Parse(quiz_question.GetAttribute("score"));
        //
        //  答對一個選項的分數
        //
        int item_score = quiz_score / itemCount;
        for (int itemPos = 0; itemPos < itemCount; itemPos++)
        {
            XmlElement quiz_item = quiz_question.SelectNodes("item")[itemPos] as XmlElement;
            XmlElement paper_item = paper_question.SelectNodes("item")[itemPos] as XmlElement;
            //
            //  算成積
            //
            if (quiz_item.GetAttribute("correct") == paper_item.GetAttribute("checked"))
            {
                totalScore += item_score;
            }
            else
            {
                totalScore -= item_score;
            }
        }
        return totalScore;
    }
      很中規中舉的程式,把天才寫的答案卷 (paper-perfect.xml) 套進去算,也真的拿到滿分,於是工程師就很高興的把程式 shelve 給我... 各位回頭想想上面的問題。這段程式以作業的標準來說勉強及格了。但是以實際系統運作的角度來說有那些缺陷? 原則上程式只要是人寫的都會有 BUG,不過我也是人,沒辦法一眼看穿所有程式的問題... 只能事事抱著懷疑的態度,試一試再說。我不是天才,所以寫不出滿分的答案,我另外準備了一份答案卷 (PAPER-NORMAL1.xml):
    只答對第一題的答案卷 (PAPER-NORMAL1.xml)[copy code]
    <?xml version="1.0" encoding="utf-8" ?>
    <quiz>
      <question>
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
        <item checked="true" />
      </question>
      <question>
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
      </question>
      <question>
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
      </question>
    </quiz>
      見鬼了,算出來是 40 分... 蠢才也是有尊嚴的,不用平白無故送我 20 分吧... @_@,我把 BUG 丟回去給工程師,最後他抓出 BUG 在那裡了,第二題第三題我完全沒作答,應該視為放棄才對,結果程式也照規則給我算分... 運氣好多賺了 20 分.. 工程師又改了一版給我,這次加上了放棄此題的判斷 (第八行):
    修正後的程式 #2: 放棄的話不算分[copy code]
    public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question)
    {
        int totalScore = 0;
        int itemCount = quiz_question.SelectNodes("item").Count;
        //
        //  如果都沒作答, 此題放棄
        //
        if (paper_question.SelectNodes("item[@checked='true']").Count == 0) return 0;
        //
        //  題目的配分
        //
        int quiz_score = int.Parse(quiz_question.GetAttribute("score"));
     
      有了上一次經驗,直覺告訴我我還得再測一測,搞不好還有其它 BUG ... 這次找了丁丁來考試,丁丁果真是個人才,交了一份全都錯的答案卷給我,前兩題放棄,第三題全選錯 (PAPER-NATIVE.xml):
    丁丁的答案卷: 倒扣 (PAPER-NATIVE.xml)[copy code]
    <?xml version="1.0" encoding="utf-8" ?>
    <quiz>
      <question>
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
      </question>
      <question>
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
        <item checked="false" />
      </question>
      <question>
        <item checked="true" />
        <item checked="false" />
        <item checked="false" />
        <item checked="true" />
      </question>
    </quiz>
      果然有柯南的地方就有密室殺人事件... @_@,又被我抓到一個問題。這次得到的總分是 -40,那有人扣到負的? 工程師又被我叫來唸了一頓,這次改了這版程式給我 (第十一行,最低是0分):
     
    修正後的程式 #3: 倒扣到0分為止[copy code]
    public static int ComputeQuizScore(XmlDocument quizDoc, XmlDocument paperDoc)
    {
        int questionCount = quizDoc.SelectNodes("/quiz/question").Count;
        int totalScore = 0;
        for (int questionPos = 0; questionPos < questionCount; questionPos++)
        {
            XmlElement quiz_question = quizDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement;
            XmlElement paper_question = paperDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement;
            totalScore += ComputeQuestionScore(quiz_question, paper_question);
        }
        return Math.Max(0, totalScore);
    }
        金融業最重視的就是錢了,銀行的程式連一毛錢都不能算錯,而在線上考試的系統也一樣,連一分都不能算錯。只是當你的老闆這樣要求你的時後,你是謹記在心,還是照一般方式寫程式嗎? 還是你有什麼有效的措施可以預防這些問題? 這時才是顯示你專業的地方啊... 套句鄉民的慣用語:
      "閃開! 讓專業的來..."   哈哈,來看看鄉民... 不,專家該怎麼解決這種問題。怕程式錯就加上一堆檢查就好了。上面舉的例子真的只是 BUG 而以,其它還有更多不可預測的問題,像是題目跟答案卷跟本搭不起來,或是沒有答案卷等等鳥問題都有可能發生。那怎辦? 可憐的工程師被我訓了一頓,只好摸摸鼻子加了一堆令人哭笑不得的 check code, 像這樣:
    多了一堆 CHECK 及印出 DEBUG MESSAGE 的程式碼[copy code]
    public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question)
    {
        int totalScore = 0;
        int itemCount = quiz_question.SelectNodes("item").Count;
        if (quiz_question == null)
        {
            throw new Exception("沒有題目卷");
        }
        if (paper_question == null)
        {
            throw new Exception("沒有答案卷");
        }
        //
        //  如果都沒作答, 此題放棄
        //
        if (paper_question.SelectNodes("item[@checked='true']").Count == 0)
        {
            Console.WriteLine("偵測到沒作答的答案,此題放棄");
            return 0;
        }
        //
        //  確認題目跟答案的選項數目一致
        //
        if (paper_question.SelectNodes("item").Count != quiz_question.SelectNodes("item").Count)
        {
            throw new Exception("此題的選項跟題目定義不符合");
        }
        老實說這範例我也寫不下去了,加這麼多 check 是好事,不過事情都有黑暗面,我覺的不妥的地方有幾個:
    1. 可讀性變差 太多的 check / debug code, 完全把正常流程的 code 淹沒了,一眼看去看不出什麼邏輯...
    2. 效能變差 對我來說,有些問題是輸入造成的 (如沒有給答案卷),有些是鳥程式自己沒寫好 (如前面的例子)。並不是所有的 check 都需要寫在程式裡。
    3. 花在寫 check 程式的時間太多 沒錯,寫個程式五分鐘就搞定,寫 check 要多花廿分鐘...
    即使這樣,我還是贊成要這樣做。只是要做的聰明一點,要消掉上面的疑慮,還要達成一樣的效果。不需要什麼新技術,十幾年前馬奎爾這本 "Write Solid Code" 就講的很清楚了,要同時維護 RELEASE / DEBUG 兩種版本的程式! 在 C 的年代,只靠兩個巨集就解決了,分別是 TRACE 跟 ASSERT。一個就相當於 printf,可以印出 MESSAGE,另一個 ASSERT 則什麼都不做,只要你傳給它當參數是 TRUE 的話。否則就會印出錯誤訊息同時中止程式。而這兩個巨集都有個特點,就是只在 DEBUG MODE 發生作用,如果是在 RELEASE MODE,則一點用都沒有,就像你沒寫這段 CODE 一樣。 細節我就不多說了,這本書講的很清楚,我直接來用。老實說這種應用太經典了,經典到每種程式語言跟開發工具都有支援,連 Microsoft 在 JavaScript 都有實作,甚至跟 debugger 也有整合,不過不曉得有多少人知道? 在 .NET 當然也有 (System.Diagnoistics)。來看看我改版過的 code:
    套用 TRACE / ASSERT 的程式碼[copy code]
    public static int ComputeQuizScore(XmlDocument quizDoc, XmlDocument paperDoc)
    {
        Trace.Assert(quizDoc != null);
        Trace.Assert(paperDoc != null);
        Trace.Assert(quizDoc.SelectNodes("/quiz/question").Count == paperDoc.SelectNodes("/quiz/question").Count);
        int questionCount = quizDoc.SelectNodes("/quiz/question").Count;
        int totalScore = 0;
        for (int questionPos = 0; questionPos < questionCount; questionPos++)
        {
            XmlElement quiz_question = quizDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement;
            XmlElement paper_question = paperDoc.SelectNodes("/quiz/question")[questionPos] as XmlElement;
            totalScore += ComputeQuestionScore(quiz_question, paper_question);
        }
        totalScore = Math.Max(0, totalScore);
        Trace.Assert(totalScore >= 0);
        return totalScore;
    }
    public static int ComputeQuestionScore(XmlElement quiz_question, XmlElement paper_question)
    {
        int totalScore = 0;
        int itemCount = quiz_question.SelectNodes("item").Count;
        //if (quiz_question == null)
        //{
        //    throw new Exception("沒有題目卷");
        //}
        //if (paper_question == null)
        //{
        //    throw new Exception("沒有答案卷");
        //}
        ////
        ////  確認題目跟答案的選項數目一致
        ////
        //if (paper_question.SelectNodes("item").Count != quiz_question.SelectNodes("item").Count)
        //{
        //    throw new Exception("此題的選項跟題目定義不符合");
        //}
        Trace.Assert(quiz_question != null);
        Trace.Assert(paper_question != null);
        Trace.Assert(paper_question.SelectNodes("item").Count == quiz_question.SelectNodes("item").Count);
        //
        //  如果都沒作答, 此題放棄
        //
        if (paper_question.SelectNodes("item[@checked='true']").Count == 0)
        {
            //Console.WriteLine("偵測到沒作答的答案,此題放棄");
            Trace.WriteLine("偵測到沒作答的答案,此題放棄");
            return 0;
        }
        //
        //  題目的配分
        //
        int quiz_score = int.Parse(quiz_question.GetAttribute("score"));
        //
        //  答對一個選項的分數
        //
        int item_score = quiz_score / itemCount;
        for (int itemPos = 0; itemPos < itemCount; itemPos++)
        {
            XmlElement quiz_item = quiz_question.SelectNodes("item")[itemPos] as XmlElement;
            XmlElement paper_item = paper_question.SelectNodes("item")[itemPos] as XmlElement;
            //
            //  算成積
            //
            if (quiz_item.GetAttribute("correct") == paper_item.GetAttribute("checked"))
            {
                totalScore += item_score;
            }
            else
            {
                totalScore -= item_score;
            }
        }
        Trace.Assert(totalScore >= (0 - quiz_score));
        Trace.Assert(totalScore <= quiz_score);
        return totalScore;
    }
      我特地把之前加的亂七八糟的 check code 用註解留下來,各位可以看看用 TRACE / ASSERT 前後的差別有多少。ASSERT是其中的精華。你可以到處都加上 ASSERT ,來說明你對於程式執行到某個地方的 "假設"。舉例來說,你 "假設" 呼叫你 FUNC 的人一定會傳 quizDoc 跟 paperDoc 給你,你又不想為了它寫一堆 IF ....,你就可以簡單的加上這一行 ASSERT( quizDoc != null), 代表只有 quizDoc 不是 NULL 時才是 "正常" 的。
    那真的不正常的話會怎樣? 我特地拿掉倒扣扣到 0 分為止的 check, 用新版的 code 執行看看。 image 在 .NET 裡 ASSERT 觸動後就是這個樣子。那 TRACE 呢? 我們進 DEBUG MODE 來看看: image TRACE Message 直接被收到 Visual Studio 的 Output 視窗內。不過在 .NET 環境下,這兩者的行為已經跟書上講的廿年前作法有很多不同了。這些機制仍然可以開關,不過已經不是靠 DEBUG / RELEASE MODE 來切換,而是在 .NET configuration 裡用設定檔的方式來切換。       ------------------------------------ 果然寫到一半寫不完 @_@,先做個小結。這些技巧都是一般人寫程式不會注意的,然而這些才是你寫的程式品質有沒有比別人好的關鍵,要讓你的程式可靠,做好預防措施是很重要的。你沒有辦法在所有地方都派警衛防守,但是你至少可以張貼警告標示,ASSERT 就是這樣的東西。下一篇會更進一步的以這例子為延申,ASSERT 還有更強大的應用。也許有人看到這裡會想說: "怎麼跟單元測試有點像? 我們直接用 UnitTest 就好了啊" 沒錯,單元測試其實就是從最基本的 Trace / Assert 衍生出來的,一直到這幾年才成為顯學。後續幾篇也會再對這些議題做討論,敬請期待 :D

    2008/10/20 系列文章: 如何學好寫程式 .NET C# Tips 作品集 專欄 技術隨筆 有的沒的

  3. 生產者 vs 消費者 - BlockQueue 實作

    過去寫了好幾篇跟執行緒相關的文章,講的都是如何精確控制執行緒的問題。不過實際上有在寫的人就知道,那些只是 "工具",最重要的還是你該怎樣安排你的程式,讓它能有效率的用到執行緒的好處,那才是重點。大部份能有效利用到多執行緒的程式,大都是大量且獨立的小動作,可以很簡單的撒下去給ThreadPool處理,不過當你的程式沒辦法這樣切,就要想點別的辦法了。

     

    開始看 code 前先講講簡單的概念。這篇要講的是另一種模式: "生產者 v.s. 消費者"。這是個很典型的供需問題,唸過作業系統 (Operation System) 的人應該都被考過這個課題吧 @_@。簡單的說如果你的程式要處理的動作可以分為 "生產者" (產生資料,載入檔案,或是第一階段的運算等等) 及消費者 (匯出資料,或是第二階段的運算等等) 這種模式,而前後兩個階段各自又適合用執行緒來加速的話,那你就值得來研究一下這種模式。第一手資料就是去看看作業系統的書,恐龍書足足有一整章在講,足夠你研究了。本篇重點會擺在怎樣用 C# / .NET 實作的部份。

     

    舉個具體一點的例子,如果你想寫個程式,從網站下載幾百個檔案,同時要把它們壓縮成一個 ZIP 檔,在過去你大概只能全部下載完之後,再開始ZIP的壓縮動作。第一階段都是 IO (網路) bound 的程式,第二階段則是 CPU bound。如果是完全獨立的兩個程式,很適合擺在一起執行,因為它們需要的資源不一樣,不會搶來搶去。但是就敗在他們要處理的資料是卡在一起的。

     

    把這個動作想像成我們有兩組人分別負責下載及壓縮的動作,下載的部份可以多執行緒同時進行沒問題,但是下載好一個檔案,就可以先丟給後面的那組人開始壓縮了,不用等期它人下載完成。如果下載的暫存目錄空間有限,我們甚至可以這樣調整: 當 TEMP 滿了的話,下載動作就暫停,等到 TEMP 裡的東西壓縮好清掉一部份後再繼續。而壓縮的部份則相反,如果 TEMP 已經空了就暫停,等到有東西進來再繼續,直到完成為止。

     

    image

    前後兩階段該如何利用多執行緒,我就跳過去了,過去那幾篇就足以應付。這種模式的關鍵在於前後兩階段的進度該如何平衡。有些範例是有照規矩的把這模式實作出來,不過... 你也知道,看起來就是像作業的那種,完全不像是可以拿來正規的用途。

     

    我認定 "好" 的實作,是像 System.Collections.Generics 之於 DataStructure 那樣,能很漂亮的把細節封裝起來,很容易重複利用的才是我認為好的實作。不能容易的使用,那就只能像作業一樣寫完就丟...。這個問題看過有人用 Semaphore 來做,也是作的很棒,不過我比較推薦的是 QUEUE 的作法。

     

    從上圖來看,生產者跟消費者都很簡單,就是過去講的多執行緒或是執行緒集區就搞定,關鍵在於中間的控制。我的想法是把庫存管理的東西實作成佇列 (QUEUE),生產者產出的東西就放到 QUEUE,而消費者就去 QUEUE 把東西拿出來。不過現成的 QUEUE 不會告訴你 QUEUE 滿了,QUEUE 空了也只會丟 EXCEPTION 而以。這次我做了個 BlockQueue 就是希望解決這個問題。

     

    我期望這個 QUEUE 能跟一般的 QUEUE 一樣使用,但是要有三個地方不一樣:

    1. 要設定大小限制,當 QUEUE 達到容量上限時 EnQueue 的動作會被暫停 (Block),而不是丟出例外。
    2. QUEUE 已經空了的時後,DeQueue 的動作會被暫停 (Block),而不是丟出例外。
    3. 要多個 QUEUE 關機的動作 (SHUTDOWN),以免生產者都不出貨了,消費者還苦苦的等下去的窘況。

     

    先看看這樣的 QUEUE 我希望它怎麼被使用。看一下簡單的範例程式 (主程式,不包含 BlockQueue):

    使用 BlockQueue 來實作的生產者/消費者範例[copy code]
            public static BlockQueue<string> queue = new BlockQueue<string>(10);        public static void Main(string[] args)        {            List<Thread> ps = new List<Thread>();            List<Thread> cs = new List<Thread>();            for (int index = 0; index < 5; index++)            {                Thread t = new Thread(Producer);                ps.Add(t);                t.Start();            }            for (int index = 0; index < 10; index++)            {                Thread t = new Thread(Consumer);                cs.Add(t);                t.Start();            }            foreach (Thread t in ps)            {                t.Join();            }            WriteLine("Producer shutdown.");            queue.Shutdown();            foreach (Thread t in cs)            {                t.Join();            }        }        public static long sn = 0;        public static void Producer()        {            for (int count = 0; count < 30; count++)            {                RandomWait();                string item = string.Format("item:{0}", Interlocked.Increment(ref sn));                WriteLine("Produce Item: {0}", item);                queue.EnQueue(item);            }            WriteLine("Producer Exit");        }        public static void Consumer()        {            try            {                while (true)                {                    RandomWait();                    string item = queue.DeQueue();                    WriteLine("Cust Item: {0}", item);                }            }            catch            {                WriteLine("Consumer Exit");            }        }        private static void RandomWait()        {            Random rnd = new Random();            Thread.Sleep((int)(rnd.NextDouble() * 300));        }        private static void WriteLine(string patterns, params object[] arguments)        {            Console.WriteLine(string.Format("[#{0:D02}] ", Thread.CurrentThread.ManagedThreadId) + patterns, arguments);        }
    
       1:  public static BlockQueue<string> queue = new BlockQueue<string>(10);
    
       2:  public static void Main(string[] args)
    
       3:  {
    
       4:      List<Thread> ps = new List<Thread>();
    
       5:      List<Thread> cs = new List<Thread>();
    
       6:      for (int index = 0; index < 5; index++)
    
       7:      {
    
       8:          Thread t = new Thread(Producer);
    
       9:          ps.Add(t);
    
      10:          t.Start();
    
      11:      }
    
      12:      for (int index = 0; index < 10; index++)
    
      13:      {
    
      14:          Thread t = new Thread(Consumer);
    
      15:          cs.Add(t);
    
      16:          t.Start();
    
      17:      }
    
      18:      foreach (Thread t in ps)
    
      19:      {
    
      20:          t.Join();
    
      21:      }
    
      22:      WriteLine("Producer shutdown.");
    
      23:      queue.Shutdown();
    
      24:      foreach (Thread t in cs)
    
      25:      {
    
      26:          t.Join();
    
      27:      }
    
      28:  }
    
      29:  public static long sn = 0;
    
      30:  public static void Producer()
    
      31:  {
    
      32:      for (int count = 0; count < 30; count++)
    
      33:      {
    
      34:          RandomWait();
    
      35:          string item = string.Format("item:{0}", Interlocked.Increment(ref sn));
    
      36:          WriteLine("Produce Item: {0}", item);
    
      37:          queue.EnQueue(item);
    
      38:      }
    
      39:      WriteLine("Producer Exit");
    
      40:  }
    
      41:  public static void Consumer()
    
      42:  {
    
      43:      try
    
      44:      {
    
      45:          while (true)
    
      46:          {
    
      47:              RandomWait();
    
      48:              string item = queue.DeQueue();
    
      49:              WriteLine("Cust Item: {0}", item);
    
      50:          }
    
      51:      }
    
      52:      catch
    
      53:      {
    
      54:          WriteLine("Consumer Exit");
    
      55:      }
    
      56:  }
    
      57:  private static void RandomWait()
    
      58:  {
    
      59:      Random rnd = new Random();
    
      60:      Thread.Sleep((int)(rnd.NextDouble() * 300));
    
      61:  }
    
      62:  private static void WriteLine(string patterns, params object[] arguments)
    
      63:  {
    
      64:      Console.WriteLine(string.Format("[#{0:D02}] ", Thread.CurrentThread.ManagedThreadId) + patterns, arguments);
    
      65:  }
    

     

     

     

     

     

    主程式很簡單,你知道怎麼寫多執行緒程式的話那麼一看就懂了。一開始替 Producer / Consumer 各建立三個執行續,而每個 Producer 只作很簡單的事,就是連續生產 30 個字串放到 BlockQueue, 當所有的 Producer thread 都執行完後,會呼叫 queue.Shutdown( ); 通知 QUEUE 已經全部生產完畢。

    Consumer 也很簡單,每個 Consumer 只是去 Queue 拿東西出來,顯示在 Console 上。直到 Dequeue 動作失敗,接到 Exception 之後就結束。

    要試試生產者/消費者模式的各種狀況,可以試著調整兩者的執行緒數量。舉例來說,調大 Producer 執行緒數量時 (P: 10 / C:5),結果是這樣:

    image

    Producer 的進度大約就是領先 Consumer 的進度 10 筆資料左右,領先的幅度就暫停了,不會無止境的成長下去。證明卡在 QUEUE 內的數量受到控制。接下來再來看看調高 Consumer 的執行緒數量的結果:

    image

    好像 iPhone 上市搶購熱潮一樣 @_@,供不應求,Producer 提供的資料馬上被搶走了...。

     

    效果不錯,看來這樣的實作有達成它的目的。最後來看的是 BlockQueue 的程式碼:

     

    BlockQueue<T> 實作的完整程式碼[copy code]
        public class BlockQueue<T>    {        public readonly int SizeLimit = 0;        private Queue<T> _inner_queue = null;        private ManualResetEvent _enqueue_wait = null;        private ManualResetEvent _dequeue_wait = null;        public BlockQueue(int sizeLimit)        {            this.SizeLimit = sizeLimit;            this._inner_queue = new Queue<T>(this.SizeLimit);            this._enqueue_wait = new ManualResetEvent(false);            this._dequeue_wait = new ManualResetEvent(false);        }        public void EnQueue(T item)        {            if (this._IsShutdown == true) throw new InvalidCastException("Queue was shutdown. Enqueue was not allowed.");            while (true)            {                lock (this._inner_queue)                {                    if (this._inner_queue.Count < this.SizeLimit)                    {                        this._inner_queue.Enqueue(item);                        this._enqueue_wait.Reset();                        this._dequeue_wait.Set();                        break;                    }                }                this._enqueue_wait.WaitOne();            }        }        public T DeQueue()        {            while (true)            {                if (this._IsShutdown == true)                {                    lock (this._inner_queue) return this._inner_queue.Dequeue();                }                lock (this._inner_queue)                {                    if (this._inner_queue.Count > 0)                    {                        T item = this._inner_queue.Dequeue();                        this._dequeue_wait.Reset();                        this._enqueue_wait.Set();                        return item;                    }                }                this._dequeue_wait.WaitOne();            }        }        private bool _IsShutdown = false;        public void Shutdown()        {            this._IsShutdown = true;            this._dequeue_wait.Set();        }    }
    
       1:  public class BlockQueue<T>
    
       2:  {
    
       3:      public readonly int SizeLimit = 0;
    
       4:      private Queue<T> _inner_queue = null;
    
       5:      private ManualResetEvent _enqueue_wait = null;
    
       6:      private ManualResetEvent _dequeue_wait = null;
    
       7:      public BlockQueue(int sizeLimit)
    
       8:      {
    
       9:          this.SizeLimit = sizeLimit;
    
      10:          this._inner_queue = new Queue<T>(this.SizeLimit);
    
      11:          this._enqueue_wait = new ManualResetEvent(false);
    
      12:          this._dequeue_wait = new ManualResetEvent(false);
    
      13:      }
    
      14:      public void EnQueue(T item)
    
      15:      {
    
      16:          if (this._IsShutdown == true) throw new InvalidCastException("Queue was shutdown. Enqueue was not allowed.");
    
      17:          while (true)
    
      18:          {
    
      19:              lock (this._inner_queue)
    
      20:              {
    
      21:                  if (this._inner_queue.Count < this.SizeLimit)
    
      22:                  {
    
      23:                      this._inner_queue.Enqueue(item);
    
      24:                      this._enqueue_wait.Reset();
    
      25:                      this._dequeue_wait.Set();
    
      26:                      break;
    
      27:                  }
    
      28:              }
    
      29:              this._enqueue_wait.WaitOne();
    
      30:          }
    
      31:      }
    
      32:      public T DeQueue()
    
      33:      {
    
      34:          while (true)
    
      35:          {
    
      36:              if (this._IsShutdown == true)
    
      37:              {
    
      38:                  lock (this._inner_queue) return this._inner_queue.Dequeue();
    
      39:              }
    
      40:              lock (this._inner_queue)
    
      41:              {
    
      42:                  if (this._inner_queue.Count > 0)
    
      43:                  {
    
      44:                      T item = this._inner_queue.Dequeue();
    
      45:                      this._dequeue_wait.Reset();
    
      46:                      this._enqueue_wait.Set();
    
      47:                      return item;
    
      48:                  }
    
      49:              }
    
      50:              this._dequeue_wait.WaitOne();
    
      51:          }
    
      52:      }
    
      53:      private bool _IsShutdown = false;
    
      54:      public void Shutdown()
    
      55:      {
    
      56:          this._IsShutdown = true;
    
      57:          this._dequeue_wait.Set();
    
      58:      }
    
      59:  }
    

     

    重點只在重新包裝 Queue 的 Enqueue / Dequeue ,及追加的 Shutdown( ) 裡做的執行緒同步機制。在 BlockQueue 尚未 Shutdown 之前,Enqueue / Dequeue 都不會引發 Exception, 取代的是用 ManualResetEvent 的 WaitOne( ) 來暫停這個動作,直到另一端資料準備好為止。

    然而當 Shutdown 被呼叫過之後,Queue 就不再接受新的東西被塞進來了,而東西拿光因為不再補貨,所以就維持原本 Queue 的設計扔出 Exception。

     

    其實真的要挖的話,這個 Queue 可以進一步的改善,以資料結構來看,這種有固定 SIZE 上限的 QUEUE,最適合用 CircleQueue 來實作了。有興趣的朋友們可以換上回介紹過的 NGenerics 改看看,我就不再示範了。其實還有其它變型,像是 Priority Queue, 進去跟出來的順序不一定一樣,意思是你地位比較高的話是可以 "插隊" 的,後加入 QUEUE 的物件,可以優先被拿出來。這些機制都是可以進一步改善 "生產者/消費者" 模式的方法,有需要的讀者們可以朝這個方向思考看看!

     

    這篇只是個開始,運用這種機制,可以進一步延伸出 Pipeline 模式 (生產線),甚至更進一步運用到串流 (Stream) 的應用。運氣好的話下個月應該看的到完整的探討跟解說吧 ...,敬請期待 :D

    2008/10/18 系列文章: 多執行緒的處理技巧 .NET C# 作品集 作業系統 多執行緒 專欄 技術隨筆 有的沒的 物件導向

  4. NGenerics - DataStructure / Algorithm Library

    其實本來沒打算寫這篇的,不過之前在寫第二篇: [該如何學好 "寫程式" #2. 為什麼 programmer 該學資料結構 ??] 時,寫的太高興,忘了查 System.Collections.Generics.SortedList 的 KEY 能不能重複... 結果貼出來後同事才提醒我,SortedList 的 KEY 一樣得是唯一的... Orz

     

    實在是不想自己再去寫這種資料結構的作業... 一來我寫不會比較好,二來自己寫的沒支援那堆 ICollection, IEnumerable 等 interface 的話,用起來也是很難用... 就到 www.codeplex.com 找了找,沒想到還真的找到一個: NGenerics :D 找到之後才發現挖到寶了,裡面實作的資料結構還真完整,Heap, BinaryTree, CircularQueue, PriorityQueue...  啥的一應俱全,好像看到資料結構課本的解答本一樣 @_@,有興趣研究的人可以抓它的 Source Code 來看..

     

    這套 LIB 的實作範圍很廣,除了我前兩篇介紹很基本的那幾個之外,其它連一些數學的跟圖型,甚至是各種排序法的實作都包含在內。要看介紹就到它的官方網站看吧! 很可惜的是它的文件不像 MSDN 一般,有明確的標示時間複雜度... 不過它有附 Source Code, 拼一點的話還是可以自己看程式... 哈哈 :D

     

    我就拿 NGenerics 來改寫之前我提供的範例程式吧,那個查通訊錄的程式就不用再改寫了,看不大出來效果差在那。我們來改寫複雜一點的,也就是高速公路的例子。

     

    先來看看有什麼東西可以用? NGenerics.DataStructures.General 這個 Namespace 下竟然有現成的 Graph 類別!! 而 NGenerics.Algorithms 下也有現成的 GraphAlgorithm 這演算法的實作... Orz, 裡面提供了三種演算法,光看名字還真搞不懂它是啥... 分別查了一下,是這三個... 找到的都是教授或是考古題之類的網站 ... 咳咳...

    1. Dijkstras Algorithm (代克思托演算法): ... 這種名字難怪我記不住 @_@,這演算法就是我在第三篇提過比較好的演算法,由起點一路擴散出去的作法。
    2. Kruskals Algorithm: 這名字大概太難翻了,沒人把它翻成中文的.. 哈哈,這演算法是找出 minimal spanning tree (最小生成樹),這篇不講教條了,跳過跳過,有興趣自己看 :D
    3. Prims Algorithm (普林演算法): 這名字好記多了... 一樣是找最短路逕 minimal spanning tree 的演算法

    來看看原本我寫了上百行的程式 (請參考上一篇),用這個 LIB 改寫有多簡單吧! 先來看看建地圖的部份。Graph<T> 的 T 是指圖的節點型別。暫時不管收費站的問題,因為 GRAPH 的模型裡,只有路逕是有成本的,點本身沒有。直接用 string 來識別點 (vertex),兩個點跟它的距離就當作路段 (edge)。建資料還真有點囉唆,打了不少字:

    利用 NGeneric 的 Graph 來建立高速公路的模型[copy code]
                Graph<string> highway = new Graph<string>(false);            highway.AddVertex("基金");            highway.AddVertex("七堵收費站");            highway.AddVertex("汐止系統");            // 以下略            highway.AddEdge(                highway.GetVertex("基金"),                 highway.GetVertex("七堵收費站"),                4.9 - 0);            highway.AddEdge(                highway.GetVertex("七堵收費站"),                 highway.GetVertex("汐止系統"),                 10.9 - 4.9);            // 以下略
    
       1:  Graph<string> highway = new Graph<string>(false);
    
       2:  highway.AddVertex("基金");
    
       3:  highway.AddVertex("七堵收費站");
    
       4:  highway.AddVertex("汐止系統");
    
       5:  // 以下略
    
       6:  highway.AddEdge(
    
       7:      highway.GetVertex("基金"), 
    
       8:      highway.GetVertex("七堵收費站"),
    
       9:      4.9 - 0);
    
      10:  highway.AddEdge(
    
      11:      highway.GetVertex("七堵收費站"), 
    
      12:      highway.GetVertex("汐止系統"), 
    
      13:      10.9 - 4.9);
    
      14:  // 以下略
    

     

    都是我一行一行慢慢打的 @_@... 地圖建完後,怎麼找出兩點之間的最短路逕? 只要這段...

    找出 [機場端] 到 [基金] 的最短路逕[copy code]
                Graph<string> result = GraphAlgorithms.DijkstrasAlgorithm<string>(                highway,                highway.GetVertex("機場端"));            Console.WriteLine(result.GetVertex("基金").Weight);
    
       1:  Graph<string> result = GraphAlgorithms.DijkstrasAlgorithm<string>(
    
       2:      highway,
    
       3:      highway.GetVertex("機場端"));
    
       4:  Console.WriteLine(result.GetVertex("基金").Weight);
    

     

    因為每個路段的 weight 我是填上油錢 (一公里兩塊錢),所以印出來的就是兩端要花的油錢。那麼被我們忽略掉的收費站怎麼算? 因為圖型的 MODEL 裡,點是沒有 weight 的,因此我們必需把路段改成有方向的,也就是南下及北上分別算不同的路段 (edge), 同時把過路費加到 weight 裡。

     

    這個演算法的實作有個小缺點,它只傳回結果,沒把過程傳回來...,所以我們只能算出要花多少錢,沒有很簡單的方法拿到該怎麼走。不過好在它有附原始碼,需要的人就拿來改一下吧 :D,多傳個 delegate 或是用它定義的 IVisitor 讓它走完所有的點,你就可以取得沿路的資訊了。

     

    這篇主要是介紹這個意外發現的LIB,就不深入的挖這些細節了,有興趣的讀者們可以自己試看看,不難的。見識到這類演算法函式庫的威力了嗎? 用起來一點都不難,不過要知道怎麼用還真的要好好研究一下...。整套 NGenerics 都是這類的東西,有興趣的讀者好好研究吧 :D

    2008/10/14 .NET C# MSDN Tips 技術隨筆 有的沒的

  5. 終於升速了!

    都什麼年代了,台北市宣稱光纖覆蓋率要達到八成,結果我家這邊到現在還是沒 FTTB 可以用... 決定把龜了很久的 ADSL 從 2M/256K 升級到 8M/640K ... 上傳速度提升了 2.5 倍,多少應該有快一點吧?

    雖然填單變更速率的過程碰到一堆鳥狀況,不過總算升速成功了 :D

    特此留念

    2008/10/10 敗家 有的沒的