• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-19  評(píng)論-21  文章-0  trackbacks-0
              置頂隨筆
            算法的過(guò)程很詳細(xì),美中不足的是最基本最常用的那些算法其實(shí)是比較少的,花點(diǎn)時(shí)間多想想為什么,知其然還要知其所以然(12),這樣才能活學(xué)活用。

            1. 書
            1.1 編程珠璣
                言簡(jiǎn)意賅,回味無(wú)窮。本書的網(wǎng)絡(luò)版在 http://netlib.bell-labs.com/cm/cs/pearls/ 上,附有源代碼。 這里有我的讀書總結(jié)。 受到此書的影響,我對(duì)代碼產(chǎn)生了很強(qiáng)的潔癖,堅(jiān)信代碼還可以寫得更優(yōu)美,更藝術(shù)。此外面對(duì)一個(gè)問(wèn)題時(shí)分析的角度更多了。

            1.2 編程之美
                 書上的每個(gè)題都會(huì)仔細(xì)地做,并完成代碼。思考的樂(lè)趣是無(wú)窮的,時(shí)常會(huì)有樂(lè)趣。

            1.3 算法導(dǎo)論
               經(jīng)典但是比較厚,適合系統(tǒng)地學(xué)習(xí)算法,而后每次遇到不懂的可以再查閱,
            算法的過(guò)程很詳細(xì),美中不足的是沒(méi)有知其所以然的感覺(jué)。看此書第一遍時(shí),是按照書的順序看的,對(duì)這些算法大致都有熟悉了。后來(lái)會(huì)偶爾查閱。現(xiàn)在為了準(zhǔn)備算法,會(huì)時(shí)常查閱此書。

            2. 文章
            2.1 Do We Teach the Right Algorithm Design Techniques ?
               把算法按其通用程度提出了4個(gè)最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer,  Transform & conquer。
               讀完后可以對(duì)算法的整體有更好的掌握。

            3. 網(wǎng)絡(luò)教程
            3.1 Top Coder的algorithm tutorial
            posted @ 2011-07-01 20:27 hex108 閱讀(642) | 評(píng)論 (0)編輯 收藏
              2011年8月24日
            為一個(gè)問(wèn)題尋找算法的過(guò)程,有點(diǎn)像一個(gè)窮舉過(guò)程:搜索已有知識(shí),并進(jìn)行重組的過(guò)程。所以把常用的算法記住,然后一個(gè)一個(gè)試用,看是否可行,不失為一個(gè)好方法。
            如果這個(gè)方法不行呢?不妨寫出最直觀的解答(即用“蠻力法”),然后從中看出可以優(yōu)化的地方在哪里,進(jìn)而進(jìn)行優(yōu)化。


            如何確定該問(wèn)題可以用哪類方法來(lái)解答呢?首先,需要對(duì)這些常用的算法的基本思想非常熟悉。
            常用的算法可以分為以下幾類:
            1. Divide & conquer
               分治算法:將問(wèn)題分為兩個(gè)1/2規(guī)模大小的子問(wèn)題,然后解決。如merge sort

            2. Decrease & conquer
               減治法 : 將問(wèn)題規(guī)模從 n 變?yōu)?n - 1,然后在規(guī)模n-1的基礎(chǔ)上解決此問(wèn)題。 如insertion sort  
               這不是遞歸么?

            3. Transform & conquer
               變治法 :變換結(jié)構(gòu)。如heap sort   

            4. Brute force
               蠻力算法,可以說(shuō)是必殺技吧,大部分問(wèn)題都可以用此方法解決。 如selection sort
               使用蠻力法的優(yōu)點(diǎn)是簡(jiǎn)單不容易出錯(cuò),缺點(diǎn)是復(fù)雜度有時(shí)很高,所以我們可以在窮舉法的基礎(chǔ)上進(jìn)行改進(jìn),這樣能達(dá)到一舉雙得的效果。
               Backtracking(回溯法) 是 Brute fore搜索算法的一種,它通常用最簡(jiǎn)單的遞歸方法來(lái)實(shí)現(xiàn),在最壞的情況下,回溯法會(huì)導(dǎo)致一次復(fù)雜度為指數(shù)時(shí)間的計(jì)算。其比較經(jīng)典的運(yùn)用是:N皇后問(wèn)題。

            其次,數(shù)據(jù)結(jié)構(gòu)有時(shí)候會(huì)決定算法,例 Transform & conquer。

            另外在TopLanguage上看到的一些有用的觀點(diǎn):
            1. 算法里面極大一部分內(nèi)容是如何有效地進(jìn)行搜索,這里的"有效"可以分為:避免不必要的計(jì)算(如A*尋路以及所有的啟發(fā)式剪枝),緩存重復(fù)計(jì)算(如所有的動(dòng) 態(tài)規(guī)劃)。
            2.本質(zhì)上,練習(xí)并不產(chǎn)生新能力。然而練習(xí)最重要的一個(gè)作用就是將外顯記憶轉(zhuǎn)化為內(nèi)隱記憶。用大白話來(lái)說(shuō)就是將平時(shí)需要用腦子去想(參與)的東西轉(zhuǎn)化為內(nèi)在的習(xí)慣。譬如我們一開(kāi)始學(xué)騎自行車的時(shí)候需要不斷提醒自己注意平衡,但隨著不斷的聯(lián)系,這種技能就內(nèi)化成了所謂的程序式記憶
               這就是熟能生巧吧。
            posted @ 2011-08-24 21:39 hex108 閱讀(605) | 評(píng)論 (0)編輯 收藏
            1. 動(dòng)態(tài)規(guī)劃
               Dynamic programming, like the divideand-conquer method, solves problems by combinging the solutions to subproblems.
               1) 動(dòng)態(tài)規(guī)劃適用于優(yōu)化問(wèn)題:從很多個(gè)解中找到最優(yōu)解。(Dynamic progrmming is typicall applied to optimization problems.)

               2) 適合用動(dòng)態(tài)規(guī)劃解決的問(wèn)題有兩個(gè)特征:
                  a. optimal substructure(http://en.wikipedia.org/wiki/Optimal_substructure)
                     用一個(gè)公式化的式子把它的solution表示出來(lái)會(huì)更清晰。
                  b. overlapping subproblems
                     如果不是overlapping subproblems,用分治法就可以解決了。動(dòng)態(tài)規(guī)劃正是利用了重復(fù)子問(wèn)題這個(gè)特性,將子問(wèn)題的解存起來(lái)以便重復(fù)利用。
               3) 如何劃分子問(wèn)題
                  以問(wèn)題 "An activity-selection problem"為例,CLRS劃分的方法和我的就不同。
                  注意:如果劃分的子問(wèn)題之間存在依賴,那么該問(wèn)題就不適合用動(dòng)態(tài)規(guī)劃解決。(見(jiàn)CLRS 15.3 subtlties小節(jié))

                4) reconsturcting an optimal solution     
                  用動(dòng)態(tài)規(guī)劃有個(gè)問(wèn)題就是在最后得到最優(yōu)解時(shí)不能知道選擇的過(guò)程,有如下兩種方法可以解決:
                  a. 可以根據(jù)我們存下來(lái)的信息推導(dǎo)出前一步的選擇是什么,如:diff.java
                  b. 記下選擇。
                   如果選擇較少可以采用方法a,否則選擇方法2比較好。這是一個(gè)時(shí)空權(quán)衡問(wèn)題。
                5)運(yùn)用動(dòng)態(tài)規(guī)劃有幾個(gè)需要注意的地方:
                   a.  We must ensure that when we search for the correct place to spilt the product, we have considered all possible places so that we are sure of         
                        having examined the optimal one.
                   b.  The subproblems are independent.
                   c.  不要形成困定思維: 一想到動(dòng)態(tài)規(guī)劃,馬上聯(lián)想到LCS,然后覺(jué)得動(dòng)態(tài)規(guī)劃的表結(jié)構(gòu)就是一個(gè)二維數(shù)組
                6)思考
                   子問(wèn)題有最優(yōu)解,那么該問(wèn)題得到的一定是最優(yōu)解嗎? 如果不是,那么什么情況下是全局最優(yōu)解,什么情況是局部最優(yōu)解?
                    以<編程之美>上的一個(gè)例子舉例說(shuō)明如下 :(有時(shí)間再補(bǔ)上)

            2. 貪心算法  
                  A greedy algorithm always makes the choice that looks best at the moment. That is , it makes a locally optimal choce in the hope that chis choce will lead to a globally optimal solution.

                 貪心法能解決的問(wèn)題,動(dòng)態(tài)規(guī)劃基本都能解決。(CLRS 16.2 Nevertheless, beneath every greedy algorithm, ther is almost always a more cumbersome dynamic-progrmming solution)。
                 但是:For many optimization problems, using dynamic programming to determine the best choices is overkill; Simpler, more effiiect algorithms will do. (eg: greedy algorithm)

                 1)適合用貪心法解決的問(wèn)題
                     必須要有Greedy-choice property : a globally optiaml solution can be arrivedat by making a locally optimal (greedy) choice.
                     如:Huffman編碼,最小生成樹
             
                  2)貪心法的一般步驟      
                      a. 將原問(wèn)題劃分為子2個(gè)子問(wèn)題(非overlap的),此時(shí)就能用動(dòng)態(tài)規(guī)劃求解了
                      b. 找到一個(gè)劃分點(diǎn),讓其中一個(gè)子問(wèn)題變?yōu)榭眨瑒t只剩下一個(gè)子問(wèn)題了,這就是貪心算法
             
                   3)使用貪心法時(shí)必須保證:
                       We must prove that a greedy choice at each step yields a golbally optimal solution, and this is where cleverness may be required.
                       這點(diǎn)也是最難的。所以有個(gè)問(wèn)題“什么情況下,局部最優(yōu)最終會(huì)產(chǎn)生全局最優(yōu)的結(jié)果?”

                   4)適用貪心算法的問(wèn)題有 greedy-choice propertty,需要找到一個(gè)貪心策略。

                   5)對(duì)于找不到全局最優(yōu)解的問(wèn)題(如NP問(wèn)題),可以考慮貪心算法。

            3. 動(dòng)態(tài)規(guī)劃與分治法的比較

                  分治法適合于那些能被分解為獨(dú)立子問(wèn)題的問(wèn)題;動(dòng)態(tài)規(guī)劃更適用于子問(wèn)題之間不是獨(dú)立的,而是會(huì)share subproblems。動(dòng)態(tài)規(guī)劃的這個(gè)特點(diǎn)得益于它把子問(wèn)題的結(jié)果都保存在一個(gè)表中了(動(dòng)態(tài)規(guī)劃的英文名字是Dynamic Programming,這里的Programming可理解為a tabular method(表格方法)),這樣就能少去重復(fù)子問(wèn)題的計(jì)算。 所以動(dòng)態(tài)規(guī)劃可以算作是分治法在overlapping 子問(wèn)題里的一個(gè)優(yōu)化(這個(gè)優(yōu)化在程序中是常見(jiàn)的優(yōu)化方法Memoization(http://en.wikipedia.org/wiki/Memoization))

            4. 動(dòng)態(tài)規(guī)劃與貪心法的比較
               1) 相同點(diǎn)
                 a. 問(wèn)題要有optimal substructure 
                    A problem exhibits optimalsubstructure if an optimal solution to the problem contains within it optimal solutions to subproblems.       
                    這是能用貪心法與動(dòng)態(tài)規(guī)劃解答的問(wèn)題的關(guān)鍵因素。
                 b. 都需要?jiǎng)澐肿訂?wèn)題,但是劃分子問(wèn)題的方式有些區(qū)別,見(jiàn)下面的不同點(diǎn)。
             
               2)不同點(diǎn)
                 a.  劃分子問(wèn)題
                    如果你把劃分的子問(wèn)題有交集(overloapping subproblem),這就很顯然地將你引入了動(dòng)態(tài)規(guī)劃的思維,以"An activity-selection problem"舉例說(shuō)明:
                    對(duì)于問(wèn)題 "An activity-selection problem",很容易就能想到動(dòng)態(tài)規(guī)劃的解法
            int select_activity(int *a, int n, int i)
            {
                if(i >=n )
                    return 0;
                for(j= i + 1; j < n; j ++){
                    if(a[j].start >= a[i].end)
                        break;
                }
                int sum1 = select_activity(a, n, j) + 1;   //select the ith activity
                int sum2 = select_activity(a, n, i + 1);   //not select the ith activity
                
                if(sum1 > sum2)
                    return sum1;
                else
                    return sum2;
            }
                但是如何將它轉(zhuǎn)化為貪心算法呢?
                  答案是:由這種方法是不易轉(zhuǎn)化為貪心法的。上面這種劃分子問(wèn)題的方式表明了它更適合于動(dòng)態(tài)規(guī)劃,就像在CLRS 383頁(yè)里說(shuō)到的0-1背包問(wèn)題:The problem formulated in this way gives rise to many over-lapping subproblems - a hallmark of dynamic programming.
             
                b.  貪心法: make whaterver choice seems best a the moment and then solve the subproblem arising after the choice is made.
                    動(dòng)態(tài)規(guī)劃:make a choice at each step, but the choice usually depends on the solutions to subproblems.

                c.  貪心法:top-down fashinon        
                    動(dòng)態(tài)規(guī)劃:bottom-up manner

               
             
            posted @ 2011-08-24 20:51 hex108 閱讀(1020) | 評(píng)論 (0)編輯 收藏
             要找工作了,終于覺(jué)得是時(shí)候總結(jié)一下數(shù)據(jù)結(jié)構(gòu)了(ps: 對(duì)于數(shù)組,鏈表這樣簡(jiǎn)單常用的結(jié)構(gòu)就不總結(jié)了,此文會(huì)持續(xù)更新),總結(jié)有助于更好地思考。

            1. 位圖
                位圖的威力可以在<編程珠璣>的開(kāi)頭就體會(huì)到。另外在Find an integer not among four billion given ones中的運(yùn)用也很精彩。

            2. 堆
               在<編程珠璣>里重點(diǎn)運(yùn)用了該結(jié)構(gòu),直接導(dǎo)致我以后經(jīng)常想到并使用該結(jié)構(gòu)。
               不得不說(shuō),它真的很有用,如:找N個(gè)數(shù)中最大/最小的k個(gè)數(shù)。
               實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列時(shí)也有用。

            3. 樹
                 二叉搜索樹:是一個(gè)很容易就能想到的結(jié)構(gòu),只要讓一棵二叉樹滿足以下一個(gè)特性就可以了:對(duì)于任一結(jié)點(diǎn)N,其左子樹結(jié)點(diǎn)left滿足key(x) <= key(N),其右子樹結(jié)點(diǎn)right滿足key(y) >= key(N),其優(yōu)點(diǎn)是操作簡(jiǎn)單,缺點(diǎn)是插入,刪除結(jié)點(diǎn)的復(fù)雜度高,為O(N)
                 二叉搜索樹復(fù)雜度高的原因?yàn)椋簶涞母叨炔淮_定/不穩(wěn)定,有可能為n,所以問(wèn)題的關(guān)鍵是:如何控制樹的高度
                 很多人靈機(jī)一動(dòng):產(chǎn)生了一系列平衡二叉樹,如:AVL樹,Red-Black樹,Treap
                 也產(chǎn)生了很多平衡二叉樹的變種,如:Weight balanced tree,k-neighbor tree等
                 Skip List 也是平衡二叉樹之外的另一種選擇
                 Trie樹 用來(lái)存儲(chǔ)一個(gè)字典,然后用來(lái)查找某個(gè)字符串還是很方便的(A trie can be seen as a deterministic finite automaton.) 另外可以看看Suffix_tree后綴樹。

            4. hash
                hash的兩個(gè)關(guān)鍵點(diǎn)在于:a. hash桶大小的設(shè)定(一般為一個(gè)素?cái)?shù)) b. 沖突處理機(jī)制,如可以用一個(gè)鏈表處理hash值相同的元素。
                我很少考慮hash,覺(jué)得復(fù)雜度不好把握。以后倒是可以考慮用用,如:在問(wèn)題“判斷兩個(gè)鏈表是否相交”有可以使用hash;“判斷鏈表有沒(méi)有環(huán)”用hash也很給力。
            posted @ 2011-08-24 20:15 hex108 閱讀(583) | 評(píng)論 (0)編輯 收藏
              2011年7月26日
            此文只簡(jiǎn)單分析發(fā)送信號(hào)給用戶程序后,用戶堆棧和內(nèi)核堆棧的變化。沒(méi)有分析實(shí)時(shí)信號(hào),當(dāng)然整個(gè)過(guò)程基本一致。很多參考了<情景分析>,所以有些代碼和現(xiàn)在的內(nèi)核可能不同,比如RESTORE_ALL,但大體的機(jī)制是類似的。

            1. 一個(gè)信號(hào)小例子

            hex@Gentoo ~/signal $ cat sigint.c
            #include <stdio.h>
            #include <stdlib.h>
            #include <signal.h>

            void sig_int(int signo)
            {
                printf("hello\n");
            }

            int main()
            {
                if(signal(SIGINT, sig_int) == SIG_ERR){
                    printf("can't catch SIGINT\n");
                    exit(-1);
                }

                for(;;)
                    ;

                return 0;
            }

            2. 用戶堆棧里發(fā)生的故事

            2.1 編譯運(yùn)行該程序,并設(shè)置斷點(diǎn)在sig_int函數(shù)開(kāi)頭(0x80482e8),并設(shè)置SIGINT信號(hào)的處理方式
            hex@Gentoo ~/signal $ gdb ./sigint
            (gdb) b *0x80482e8
            Breakpoint 1 at 0x80482e8: file sigint.c, line 6.
            (gdb) handle SIGINT noprint pass
            SIGINT is used by the debugger.
            Are you sure you want to change it? (y or n) y
            Signal        Stop    Print    Pass to program    Description
            SIGINT        No    No    Yes        Interrupt
            (gdb) r
            Starting program: /home/gj/signal/sigint

            2.2 向該程序發(fā)送信號(hào): kill -INT 此程序的pid號(hào)
            hex@Gentoo ~/signal $ kill -INT 4639

            2.3 該程序收到信號(hào)后停在斷點(diǎn)處
            Breakpoint 1, sig_int (signo=2) at sigint.c:6
            6    {
            (gdb) i r esp
            esp            0xbfffe7ec    0xbfffe7ec
            (gdb) x/40a 0xbfffe7ec
            0xbfffe7ec:    0xb7fff400    0x2    0x33    0x0
            0xbfffe7fc:    0x7b    0x7b    0x8048930 <__libc_csu_init>    0x80488f0 <__libc_csu_fini>
            0xbfffe80c:    0xbfffed58    0xbfffed40    0x0    0x0
            0xbfffe81c:    0xbfffec18    0x0    0x0    0x0
            0xbfffe82c:    0x8048336 <main+58>    0x73    0x213    0xbfffed40
            0xbfffe83c:    0x7b    0xbfffead0    0x0    0x0
            0xbfffe84c:    0x0    0x0    0x0    0x0
            0xbfffe85c:    0x0    0x0    0x0    0x0
            0xbfffe86c:    0x0    0x0    0x0    0x0
            0xbfffe87c:    0x0    0x0    0x0    0x0
            棧上的內(nèi)容為信號(hào)棧sigframe:
            根據(jù)此結(jié)構(gòu)可以知道:
            1). 返回地址0xb7fff400,它指向vdso里的sigreturn
            (gdb) x/10i 0xb7fff400
               0xb7fff400 <__kernel_sigreturn>:    pop    %eax
               0xb7fff401 <__kernel_sigreturn+1>:    mov    $0x77,%eax
               0xb7fff406 <__kernel_sigreturn+6>:    int    $0x80
            這個(gè)地址根據(jù)內(nèi)核的不同而不同,我的內(nèi)核版本是2.6.38。
            2). 信號(hào)處理程序完成后,會(huì)回到 eip = 0x8048336 的地址繼續(xù)執(zhí)行。


            2.4 執(zhí)行完sig_int函數(shù)后,進(jìn)入了__kernel_sigreturn,接著回到了代碼0x8048336處,一切恢復(fù)了正常。
            (gdb) x/5i $pc
            => 0x8048336 <main+58>:    jmp    0x8048336 <main+58>
            (gdb) i r esp
            esp            0xbfffed40    0xbfffed40

            在用戶層我們能看到的只有上面這么多信息了,可能有一個(gè)地方不能理解:在上面過(guò)程c中 從0xbfffe7ec起那一塊棧上的內(nèi)容從哪來(lái)的?(正常情況下堆棧esp應(yīng)該一直指向在過(guò)程d中顯示的esp值0xbfffed40)

            現(xiàn)在來(lái)看看在上面這些現(xiàn)象之下,內(nèi)核的堆棧發(fā)生了怎樣的變化。

            3. 內(nèi)核堆棧里發(fā)生的故事
            3.1 發(fā)信號(hào)時(shí)
            在 2.2 里當(dāng)執(zhí)行kill -INT 4639后,pid為4639的程序(也就是我們運(yùn)行的 ./sigint)會(huì)收到一個(gè)信號(hào),但是信號(hào)實(shí)際都是在內(nèi)核里實(shí)現(xiàn)的。每個(gè)進(jìn)程(這里只講進(jìn)程的情況,線程類似,線程有一個(gè)tid)都有一個(gè)pid,與此pid對(duì)應(yīng)有一個(gè)結(jié)構(gòu) task_struct ,在task_struct里有一個(gè)變量 struct sigpending pending,當(dāng)該進(jìn)程收到信號(hào)時(shí),并不會(huì)立即作出反應(yīng),只是讓內(nèi)核把這個(gè)信號(hào)記在了此變量里(它里面是一個(gè)鏈表結(jié)構(gòu))。當(dāng)然,此時(shí)與內(nèi)核堆棧還沒(méi)有多大關(guān)系。

            3.2 檢測(cè)信號(hào)
              如果只記錄了信號(hào),但沒(méi)有相應(yīng)反應(yīng),那有什么用啊。一個(gè)進(jìn)程在什么 情況下會(huì)檢測(cè)信號(hào)的存在呢?在<情景分析>里說(shuō)到了:“在中斷機(jī)制中,處理器的硬件在每條指令結(jié)束時(shí)都要檢測(cè)是否有中斷請(qǐng)求的存在。信號(hào)機(jī)制是純軟件的,當(dāng)然不能依靠硬件來(lái)檢測(cè)信號(hào)的到來(lái)。同時(shí),要在每條指令結(jié)束時(shí)都來(lái)檢測(cè)顯然是不現(xiàn)實(shí)的,甚至是不可能的。所以對(duì)信號(hào)的檢測(cè)機(jī)制是:每當(dāng)從系統(tǒng)調(diào)用,中斷處理或異常處理返回到用戶空間的前夕;還有就是當(dāng)進(jìn)程被從睡眠中喚醒(必定是在系統(tǒng)調(diào)用中)的時(shí)候,此時(shí)若發(fā)現(xiàn)有信號(hào)在等待就要提前從系統(tǒng)調(diào)用返回。總而言之,不管是正常返回還是提前返回,在返回到用戶空間的前夕總是要檢測(cè)信號(hào)的存在并作出反應(yīng)。”

              因此,對(duì)收到的信號(hào)做出反應(yīng)的時(shí)間是 從內(nèi)核返回用戶空間的前夕,那么有那些情況會(huì)讓程序進(jìn)入內(nèi)核呢?答案是中斷,異常和系統(tǒng)調(diào)用。簡(jiǎn)單了解一下它們發(fā)生時(shí)內(nèi)核堆棧的變化。
              //-----中斷,異常,系統(tǒng)調(diào)用 : 開(kāi)始
               1)在用戶空間發(fā)生中斷時(shí),CPU會(huì)自動(dòng)在內(nèi)核空間保存用戶堆棧的SS, 用戶堆棧的ESP, EFLAGS, 用戶空間的CS, EIP, 中斷號(hào) - 256
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 中斷號(hào) - 256
               進(jìn)入內(nèi)核后,會(huì)進(jìn)行一個(gè)SAVE_ALL,這樣內(nèi)核棧上的內(nèi)容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 中斷號(hào) - 256 | ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX

               好了,一切都處理完時(shí),內(nèi)核jmp到RESTORE_ALL(它是一個(gè)宏,例:在x86_32體系結(jié)構(gòu)下,/usr/src/kernel/arch/286/kernel/entry_32.S文件里包含該宏的定義)

               RESTORE做的工作,從它的代碼里就可以看出來(lái)了:   
               首先把棧上的 ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX pop到對(duì)應(yīng)的寄存器里
               然后將esp + 4 把 “中斷號(hào) - 256” pop掉
               此時(shí)內(nèi)核棧上的內(nèi)容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP
               最后執(zhí)行iret指令,此時(shí)CPU會(huì)從內(nèi)核棧上取出SS, ESP, ELFGAS, CS, EIP,然后接著運(yùn)行。

               2) 在用戶空間發(fā)生異常時(shí),CPU自動(dòng)保存在內(nèi)核棧的內(nèi)容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 出錯(cuò)代碼 error_code
               (注:CPU只是在進(jìn)入異常時(shí)才知道是否應(yīng)該把出錯(cuò)代碼壓入堆棧(為什么?),而從異常處理通過(guò)iret指令返回時(shí)已經(jīng)時(shí)過(guò)境遷,CPU已經(jīng)無(wú)從知當(dāng)初發(fā)生異常的原因,因此不會(huì)自動(dòng)跳過(guò)這一項(xiàng),而要靠相應(yīng)的異常處程序?qū)Χ褩<右哉{(diào)整,使得在CPU開(kāi)始執(zhí)行iret指令時(shí)堆棧頂部是返回地址)

               進(jìn)入內(nèi)核后,沒(méi)有進(jìn)行SAVE_ALL,而是進(jìn)入相應(yīng)的異常處理函數(shù)(這個(gè)函數(shù)是包裝后的,真正的處理函數(shù)在后面)(在此函數(shù)里會(huì)把真正的處理函數(shù)的地址push到棧上),然后jmp到各種異常處理所共用的程序入口error_code,它會(huì)像SAVE_ALL那樣保存相應(yīng)的寄存器(沒(méi)有保存ES),此時(shí)內(nèi)核空間上的內(nèi)容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 出錯(cuò)代碼 error_code | 相應(yīng)異常處理函數(shù)入口 | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX
               (注:如果沒(méi)有出錯(cuò)代碼,則此值為0)

               最后結(jié)束時(shí)與中斷類似(RESTORE_ALL)。

               3) 發(fā)生系統(tǒng)調(diào)用時(shí),CPU自動(dòng)保存在內(nèi)核棧的內(nèi)容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP
               為了與中斷和異常的棧一致,在進(jìn)入系統(tǒng)調(diào)用入口(ENTRY(system_call))后會(huì)首先push %eax,然后進(jìn)行SAVE_ALL,此時(shí)內(nèi)核棧上的內(nèi)容為
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | EAX | ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX
             
               最后結(jié)束時(shí)與中斷類似(RESTORE_ALL)。
               //-----中斷,異常,系統(tǒng)調(diào)用 : 結(jié)束

               中斷,異常,系統(tǒng)調(diào)用這部分有一點(diǎn)遺漏的地方:檢測(cè)信號(hào)的時(shí)機(jī)就是緊挨著RESTORE_ALL之前發(fā)生的。

            3.3 對(duì)檢測(cè)到的信號(hào)做出反應(yīng)
              如果檢測(cè)到有要處理的信號(hào)時(shí),就要開(kāi)始做一些準(zhǔn)備工作了,此時(shí)內(nèi)核里的內(nèi)容為(進(jìn)入內(nèi)核現(xiàn)場(chǎng)時(shí)的內(nèi)容)
              | 用戶堆棧的SS1 | 用戶堆棧的ESP1 | EFLAGS1 | 用戶空間的CS1 | EIP1 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1
              (注:?的值有三個(gè)選擇:中斷號(hào) - 256/出錯(cuò)代碼 error_code/出錯(cuò)代碼 error_code)
              假設(shè)將要處理的信號(hào)對(duì)應(yīng)的信號(hào)處理程序是用戶自己設(shè)置的,即本文中SIGINT對(duì)應(yīng)的信號(hào)處理程序sig_int。
              現(xiàn)在要做的事情是讓cpu去執(zhí)行信號(hào)處理程序sig_int,但是執(zhí)行前需要做好準(zhǔn)備工作:
              3.3.1  setup_frame
              在用戶空間設(shè)置好信號(hào)棧(struct sigframe)(假設(shè)設(shè)置好棧后esp的值為sigframe_esp,在本文中其值為0xbfffe7ec),即在2.3里看到的棧內(nèi)容。
              注:struct sigframe里至少包含以下內(nèi)容:
              用戶堆棧的SS1, 用戶堆棧的ESP1, EFLAGS1, 用戶空間的CS1, EIP1, ES1, DS1, EAX1, EBP1, EDI1, ESI1, EDX1, ECX1, EBX1

              3.3.2 設(shè)置即將運(yùn)行的eip的值為信號(hào)處理函數(shù)sig_int的地址(為0x80482e8),并設(shè)置用戶ESP的值為sigframe_esp(為0xbfffe7ec),這是通過(guò)修改內(nèi)核棧里的EIP和ESP的值實(shí)現(xiàn)的,因?yàn)樵趶南到y(tǒng)調(diào)用里iret時(shí),會(huì)從內(nèi)核棧里取EIP,ESP。
              這時(shí)內(nèi)核棧的內(nèi)核為:
              | 用戶堆棧的SS1 | 0xbfffe7ec | EFLAGS1 | 用戶空間的CS1 | 0x80482e8 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1
             
              最后,進(jìn)行RESTORE_ALL,內(nèi)核棧上的內(nèi)容為:
              | 用戶堆棧的SS1 | 0xbfffe7ec | EFLAGS1 | 用戶空間的CS1 | 0x80482e8
             
              RESTORE_ALL里執(zhí)行完iret后,寄存器內(nèi)容為: EIP為0x80482e8(即sig_int),esp為0xbfffe7ec 。 于是用戶空間到了步驟 2.3

            3.4 信號(hào)處理程序完成以后
              2.3 -> 2.4,進(jìn)入了sig_return系統(tǒng)調(diào)用,在sig_return里,內(nèi)核棧的內(nèi)容為(每個(gè)名字后面加一個(gè)2以便與前面的1區(qū)分)
              | 用戶堆棧的SS2 | 用戶堆棧的ESP2 | EFLAGS2 | 用戶空間的CS2 | EIP2 | ? | ES2 | DS2 | EAX2 | EBP2 | EDI2 | ESI2 | EDX2 | ECX2 | EBX2
              sig_return要做的主要工作就是根據(jù)用戶棧里sigframe的值修改內(nèi)核棧里的內(nèi)容,使內(nèi)核棧變?yōu)?
              | 用戶堆棧的SS1 | 用戶堆棧的ESP1 | EFLAGS1 | 用戶空間的CS1 | EIP1 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1
                                                              
              至此內(nèi)核棧里的內(nèi)容和進(jìn)行信號(hào)處理前一樣了。經(jīng)過(guò)RESTORE_ALL后,用戶堆棧里的內(nèi)容也和以前一樣(主要指ESP的值一樣)。

              "kill -INT 4639" 只是一段小插曲。程序從原處開(kāi)始運(yùn)行。
            posted @ 2011-07-26 18:27 hex108 閱讀(4060) | 評(píng)論 (0)編輯 收藏
              2011年7月7日
                 讀的過(guò)程真是一種享受。看到好的代碼,好的思想,總會(huì)忍不住默記幾遍。

                 看到覺(jué)得有點(diǎn)意味的地方最好多想想來(lái)龍去脈,想想為什么,因?yàn)榫o接著的會(huì)是令人驚喜的解說(shuō)。 多寫寫書上的代碼,感覺(jué)不錯(cuò)(寫完以后感覺(jué)忘了很久的算法又重新回來(lái)了)。 每章的“原理”部分是高度性的概括,"習(xí)題"是很好的,促使你去思考,做習(xí)題是很有必要的,不想“浪費(fèi)”時(shí)間去“做習(xí)題”了的結(jié)果可能是以后會(huì)用更多的時(shí)間才能想清這些問(wèn)題,還有不要只想著看答案,你會(huì)很失望,因?yàn)橛行╊}目是沒(méi)有答案的 :)  ps:有很多面試題來(lái)自其中的習(xí)題

                 對(duì)一些算法有了更好的理解,也許是看第二遍的原因,也許是從不同的角度看會(huì)有不同的效果(所以好書要多讀,每重讀一次會(huì)有新的收獲)。比如:在動(dòng)態(tài)規(guī)劃算法里,程序可以用遞歸算法和用表格化方法實(shí)現(xiàn)。遞歸算法的缺點(diǎn)是:有部分值會(huì)被重算,解決方法是用一個(gè)數(shù)組把已經(jīng)計(jì)算過(guò)的值存起來(lái),這樣就不會(huì)重復(fù)計(jì)算了。表格化的算法是:沒(méi)有遞歸算法好理解,解決辦法是:在代碼開(kāi)頭加個(gè)注釋,注釋就是那幾條遞歸規(guī)則,大不了再加上說(shuō)明“此代碼用的是動(dòng)態(tài)規(guī)劃”。 ps:linux里diff的基本算法就是動(dòng)態(tài)規(guī)劃吧,感覺(jué)和最長(zhǎng)公共子串類似,自己實(shí)現(xiàn)了一個(gè)(diff.pl)(更新:今天在網(wǎng)上看到了關(guān)于diff用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)的信息:Dynamic programming Creative Exercises 2 Unix diff, 其源碼為diff.java ,比我的好了N多倍,打印結(jié)果的那段代碼的思想相當(dāng)好!代碼簡(jiǎn)潔清淅。另外,我開(kāi)始覺(jué)得用表格化的方法實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃更帥了。  --2011.7.22 )。

                讀這本書收獲很多,列舉幾個(gè)吧:
                1. 書里的“程序驗(yàn)證” 技術(shù)很靠譜,讓程序看起來(lái)清晰易懂,還能從一定程度保證正確性。
                2. “哨兵”(Sentinel value )被幾次用到了,感覺(jué)還不錯(cuò),代碼看起來(lái)更簡(jiǎn)單了,還能帶來(lái)一點(diǎn)小小效率。
                3. 時(shí)空折中與雙贏。在原始設(shè)計(jì)的算法并非最佳方案時(shí),通過(guò)改善算法是可以達(dá)到雙贏的。
                4. 用只分配一個(gè)較大內(nèi)存塊的方案來(lái)替換通用內(nèi)存分配,這樣就消除了很多 開(kāi)銷較大的調(diào)用,而且也使用空間的利用更加有效。
                5. 數(shù)學(xué)模型的建立是很重要的。把數(shù)a想成用集合[a,a + 1)表示是第9章中二分查找代碼調(diào)優(yōu)的核心思想。數(shù)組旋轉(zhuǎn)那個(gè)算法也實(shí)在是太nb了。
                6. 一個(gè)寫得很好的代碼,在幾個(gè)地方看到過(guò),總會(huì)忘,這次記下:
              鏈表里有一個(gè)哨兵元素,初始時(shí): head = sentinel = new Node(value, 0);
              向鏈表插入元素:
              insert(v)
                  
            for(p = &head; (*p)->val < t; p = &((*p)->next))
                      ;
                 
            if  (*p)->val == v 
                     
            return
                 
            *= new node(v, *p)

              下面是我寫的:
              insert(v)
                    p 
            = head;
                    
            while(p->val < t)
                        p 
            = p->next
                    
            if(p-> val == v)
                        
            return
                    q 
            = node(t,p)
                    
            if(p == head)
                         head 
            = q;

                另外,注意到一本書<算法設(shè)計(jì)與分析基礎(chǔ)> ,用不同的方式講算法,把算法按其通用程度提出了4個(gè)最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer,  Transform & conquer。

                最后摘錄一下 第1版跋 里給的幾個(gè)建議:
                1. 解決正確的問(wèn)題。 首先徹底理解問(wèn)題
                2. 探索所有可能的解決方案
                3. 觀察數(shù)據(jù)
                4. 使用粗略估算
                5. 得用對(duì)稱性
                6. 利用組件做設(shè)計(jì)  
                7. 建立原型
                8. 必要時(shí)進(jìn)行權(quán)衡  
                9. 保持簡(jiǎn)單  
                10.追求優(yōu)美
            posted @ 2011-07-07 20:47 hex108 閱讀(574) | 評(píng)論 (0)編輯 收藏
              2011年7月1日
            算法的過(guò)程很詳細(xì),美中不足的是最基本最常用的那些算法其實(shí)是比較少的,花點(diǎn)時(shí)間多想想為什么,知其然還要知其所以然(12),這樣才能活學(xué)活用。

            1. 書
            1.1 編程珠璣
                言簡(jiǎn)意賅,回味無(wú)窮。本書的網(wǎng)絡(luò)版在 http://netlib.bell-labs.com/cm/cs/pearls/ 上,附有源代碼。 這里有我的讀書總結(jié)。 受到此書的影響,我對(duì)代碼產(chǎn)生了很強(qiáng)的潔癖,堅(jiān)信代碼還可以寫得更優(yōu)美,更藝術(shù)。此外面對(duì)一個(gè)問(wèn)題時(shí)分析的角度更多了。

            1.2 編程之美
                 書上的每個(gè)題都會(huì)仔細(xì)地做,并完成代碼。思考的樂(lè)趣是無(wú)窮的,時(shí)常會(huì)有樂(lè)趣。

            1.3 算法導(dǎo)論
               經(jīng)典但是比較厚,適合系統(tǒng)地學(xué)習(xí)算法,而后每次遇到不懂的可以再查閱,
            算法的過(guò)程很詳細(xì),美中不足的是沒(méi)有知其所以然的感覺(jué)。看此書第一遍時(shí),是按照書的順序看的,對(duì)這些算法大致都有熟悉了。后來(lái)會(huì)偶爾查閱。現(xiàn)在為了準(zhǔn)備算法,會(huì)時(shí)常查閱此書。

            2. 文章
            2.1 Do We Teach the Right Algorithm Design Techniques ?
               把算法按其通用程度提出了4個(gè)最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer,  Transform & conquer。
               讀完后可以對(duì)算法的整體有更好的掌握。

            3. 網(wǎng)絡(luò)教程
            3.1 Top Coder的algorithm tutorial
            posted @ 2011-07-01 20:27 hex108 閱讀(642) | 評(píng)論 (0)編輯 收藏
              2011年6月18日
                 二分查找法(Binary search algorithm)是一個(gè)很常見(jiàn)的算法,從<編程珠璣>里再次看到時(shí)又有新的收獲。
                 直接看代碼吧,下面是常見(jiàn)的實(shí)現(xiàn)代碼:
                
            int binary_search(int *a, int num, int t)
            {
                
            int start = 0, end = num - 1;
                
                
            while(end >= start){
                    
            int middle = (start + end) / 2;
                    
            int tmp = a[middle];
                    
            if(tmp < t){
                        start 
            = middle + 1;
                    }
            else if(tmp > t){
                        end 
            = middle - 1;
                    }
            else{
                        
            return middle;
                    }
                }

                
            return -1;
            }   

                  優(yōu)化后的代碼為(這個(gè)優(yōu)化的思想也挺好的,不知道有沒(méi)有一套系統(tǒng)的方法來(lái)思考出這個(gè)優(yōu)化思路):
                 
            int binary_search(int *a, int num, int t)
            {
                
            int low = -1, high = num - 1;
                
                
            while(low + 1 != high){
                    
            int middle = (low + high) / 2;
                    
            if(a[middle] < t){
                        low 
            = middle;
                    }
            else{
                        high 
            = middle;
                    }
                }
                
                
            if(a[high] != t)
                    
            return -1;
                
            else
                    
            return high;
            }
             
                 如果直接看這段代碼,有可能不知道是怎么回事。但是運(yùn)用書中提到的“程序驗(yàn)證”的方法后,原理就顯而易見(jiàn)了,修改后的代碼為:

             1 int binary_search(int *a, int num, int t)
             2 {
             3     int low = -1, high = num - 1;
             4     
             5     //invariant: low < high && a[low] < t && a[high] >= t
             6     while(low + 1 != high){
             7         int middle = (low + high) / 2==>  int middle = low + (high - low) / 2;   //防止溢出
             8         if(a[middle] < t){
             9             low = middle;
            10         }else{
            11             high = middle;
            12         }
            13     }   
            14    //assert: low +1 = high && a[low] < t && a[high] >= t
            15   
            16     if(a[high] != t)
            17         return -1;
            18     else
            19         return high;
            20 }
            21 

                  “程序驗(yàn)證” 的思想可以簡(jiǎn)述為:不管是驗(yàn)證一個(gè)函數(shù),還是一條語(yǔ)句,一個(gè)控制結(jié)構(gòu)(循環(huán),if分支等),都可以采用兩個(gè)斷言(前置條件和后置條件)來(lái)達(dá)到這個(gè)目的。前置條件是在執(zhí)行該處代碼之前就應(yīng)該成立的條件,后置條件的正確性在執(zhí)行完該處代碼后必須得到保證。(ps: 斷言也算是一種驗(yàn)證的手段)

              上面這段代碼的原理是給定一段區(qū)間 (low, high] ,如果満足 a[low] < t  && a[high] >=t && high = low + 1,那么有兩種情況存在:1. a[high] = t ; 2.與t相等的元素不存在。由于數(shù)組a 肯定滿足條件a[low] < t  && a[high] >=t,所以該算法要做的就是把區(qū)間 (-1, num -1] 縮小到(low, low+1]。  
                  1. 在執(zhí)行代碼6~17行時(shí),始終保證low < high && a[low] < t && a[high] >= t 成立。
              
            2. 在執(zhí)行完6~17行后,肯定滿足條件a[low] < t  && a[high] >=t && high = low + 1,因?yàn)檠h(huán)退出的條件是 high = low + 1,而該循環(huán)始終保證上面第1條。
              經(jīng)過(guò)這樣的分析后,我們能對(duì)程序的正確性有更好的掌握,同時(shí)程序也更易理解。

            參考:
              1. 基本上摘自<編程珠璣>,很不錯(cuò)的一本書,讓我對(duì)算法有了新的思考,以前只是看看算法導(dǎo)論如何實(shí)現(xiàn)的,沒(méi)有思考該算法是如何想出來(lái)的,有沒(méi)有更簡(jiǎn)單的算法(思考的過(guò)程類似劉未鵬的<知其所以然(續(xù))>),要堅(jiān)持這個(gè)思考過(guò)程需要很多功夫與時(shí)間,但效果也很明顯,能對(duì)算法有更好的掌握。
            posted @ 2011-06-18 15:02 hex108 閱讀(2852) | 評(píng)論 (3)編輯 收藏
              2011年5月17日
                 摘要: 主要想介紹一下.gdbinit文件。

            gdb運(yùn)行時(shí)會(huì)首先加載 ~/.gdbinit文件
            例如:我在debug時(shí),每次都需要進(jìn)行handle SIGBUS noprint pass來(lái)處理SIGBUS信號(hào),這種情況就可以把它寫入 .gdbinit文件。
            在.gdbinit里也可以定義函
            eg: 在.gdbinit里定義print_regs
            def print_regs
            i r eax ebx ecx edx
            end
            (gdb) print_regs
            eax 0xbffff4a4 -1073744732
            ebx 0x28bff4 2670580
            ecx 0x902c5562 -1876142750
            edx 0x1 1  閱讀全文
            posted @ 2011-05-17 21:14 hex108 閱讀(2662) | 評(píng)論 (3)編輯 收藏

                 debug可以幫助熟悉系統(tǒng),可是時(shí)間長(zhǎng)了會(huì)很疲卷,特別是機(jī)械的調(diào)試,如果還要面對(duì)雜亂的代碼,更是雪上加霜。所以要學(xué)著從debug中鉆探快樂(lè),在系統(tǒng)的調(diào)試過(guò)程中發(fā)揮想象,嘗試不同的debug方法。

                最近看了《軟件調(diào)試實(shí)戰(zhàn)》,結(jié)合自己的經(jīng)歷,總結(jié)了一下:

                1. 與測(cè)試用例相關(guān)

                   a. 如果不能達(dá)到“測(cè)試先行”,至少應(yīng)該在寫完代碼后有相對(duì)完整的測(cè)試用例。對(duì)于正確性的保證和以后重構(gòu)代碼都是有好處的。

                   b. 每次添加新功能或修復(fù)了一個(gè)bug時(shí),都應(yīng)該增加測(cè)試用例!A歷經(jīng)千辛萬(wàn)苦終于fix 了一個(gè)bug,很久很久以后,B覺(jué)得這段代碼需要改改,于是改了改,后來(lái)的結(jié)果還是改了,而且順利提交到了庫(kù)里(因?yàn)锳當(dāng)時(shí)遇到的bug 并沒(méi)有出現(xiàn)!)

                   c. 回歸測(cè)試

                     修改代碼后進(jìn)行回歸測(cè)試。每次提交一個(gè)版本后自動(dòng)進(jìn)行回歸測(cè)試,保證庫(kù)里的代碼的正確性。

                   d. 簡(jiǎn)化測(cè)試用例

                     好處:可以排除不起作用的因素;減少測(cè)試用例的運(yùn)行時(shí)間;最重要的是,使用測(cè)試用例更容易調(diào)試(誰(shuí)愿意處理那些填充了數(shù)百或數(shù)千項(xiàng)的數(shù)據(jù)容器呢?)

                     方法如: 如果測(cè)試?yán)颖容^好改,可以將其改小;將輸入集改小

                   e. 完成代碼,清理后重新運(yùn)行所有測(cè)試用例。

                2. 關(guān)于程序的編譯

                  a. 重視編譯期間的warning,最好把warning數(shù)減為0. 不要忽略編譯器警告,即使它們可能是無(wú)害的。

            eg:

            int add(int a,int b){

                    return a +b ;

            }

            結(jié)果頭文件里聲明成了 extern int add(long a,int b)

            會(huì)調(diào)試死人啊,調(diào)程序的時(shí)候一看程序定義是對(duì)的啊,怎么傳的參數(shù)一下就變了;

            b. 如果出現(xiàn)莫名其妙的錯(cuò)誤

                  如果是用Makefile組織工程時(shí),考慮make clean,有可能修改數(shù)據(jù)結(jié)構(gòu)或頭文件后改變了一些東西,但是由于一些未知原因該文件并未重新編譯。如果函數(shù)是C函數(shù),有可能調(diào)用者和被 調(diào)用者的參數(shù)的成員和類型不同。如果一個(gè)類方法,則訪問(wèn)任何類成員 都將發(fā)生錯(cuò)誤,因?yàn)檫@兩個(gè)類的內(nèi)存而已幾乎是完全不同的。這可能導(dǎo)致Segmentation falut,或是很久之后才能檢測(cè)到的內(nèi)存破壞。

            3. 關(guān)于鏈接

            a. 鏈接器的基本工作原理

                   編譯器或匯編程序?qū)⒃创a轉(zhuǎn)換為機(jī)器代碼,并輸出對(duì)象誰(shuí)的。對(duì)象文件中包含符號(hào)(函數(shù)或變量),這些符號(hào)有的在本模塊定義的,有的在其他模塊定義的,鏈接器就在鏈接對(duì)象文件時(shí)把這些未定義的符號(hào)與定義它的模塊對(duì)應(yīng)起來(lái)。

            b. 鏈接順序

                 有庫(kù)和歸檔文件時(shí) 鏈接算法是不一樣的。    

                 鏈接器參數(shù)順序很重要,對(duì)于編譯單元(如對(duì)象文件和庫(kù))和搜索路徑來(lái)說(shuō)都是如此。

            c. C++中使用C代碼時(shí),用extern c{} 把C代碼包裝一下。

                 關(guān)于 c++符號(hào)和名稱改編:C++允許重載函數(shù),為了生成C++代碼元素的唯一符號(hào),編譯器使一種稱為名稱改編(name mangling)的技術(shù),它將對(duì)象的準(zhǔn)確規(guī)格說(shuō)明(如會(huì)員名空間和函數(shù)參數(shù)的個(gè)數(shù)及類型)編碼到符號(hào)中。(可以用c++filt解析出來(lái)~ eg: c++filt _Z9factoriali的結(jié)果為factorial(int))

            d. 環(huán)境變量

               LD_LIBRARY_PATH會(huì)影響動(dòng)態(tài)加載的庫(kù),用LDD可以看到程序依賴哪個(gè)動(dòng)態(tài)庫(kù)

            4. 自動(dòng)化測(cè)試

               讓一切自動(dòng)化起來(lái)。如果重復(fù)的做一件事,就很有必要考慮自動(dòng)化了。

            5. 關(guān)于那些怪異的錯(cuò)誤

                在一些顯而易見(jiàn)有內(nèi)存問(wèn)題的情況下,如:間歇故障和無(wú)法解釋的隨機(jī)行為,這時(shí)考慮使用內(nèi)存調(diào)試器了!

                如valgrind,很好用,也很簡(jiǎn)單。

                valgrind –tool=massif your_program 進(jìn)行內(nèi)存剖析(檢測(cè)內(nèi)存分配情況,優(yōu)化內(nèi)存使用)

                valgrind –tool=memcheck your_program 進(jìn)行內(nèi)存檢查(檢測(cè)無(wú)效的寫訪問(wèn),檢測(cè)對(duì)未初始化的內(nèi)存的讀取操作,檢測(cè)內(nèi)存泄露等)

                valgrind –tool=helgrind your_program 查找競(jìng)爭(zhēng)條件,可以用來(lái)輔助調(diào)試多線程程序

                valgrid –-db-attac=yes的功能很好用,可以將內(nèi)存高度器和源代碼測(cè)試器(如gdb)結(jié)合起來(lái),這樣就可以即時(shí)查看當(dāng)時(shí)的變量的值,很好用!

            6. 靜態(tài)檢查器

               作為常規(guī)軟件構(gòu)建過(guò)程中的一部分運(yùn)行,用于查找一些可通過(guò)靜態(tài)源代碼分析發(fā)現(xiàn)的特定bug。

            7. 關(guān)于運(yùn)行時(shí)剖析工具

                 不要編寫自己的運(yùn)行時(shí)剖析時(shí)工具:自己霞友云朋一的剖析 工具通常使用系統(tǒng)調(diào)用time()或ctime()來(lái)測(cè)量時(shí)間。這些系統(tǒng)調(diào)用的問(wèn)題是開(kāi)銷很高,而且準(zhǔn)確度低。另處在剖析期間要收集大量數(shù)據(jù),可能會(huì)影響程序本身的行為。

            8. 環(huán)境變量

              如程序的行為可能 依賴于當(dāng)前工作目錄。在linux上,目錄被注冊(cè)到環(huán)境變量CWD上。這個(gè)bug碰到過(guò),還導(dǎo)致了死鎖。

            9. 讀取恰當(dāng)?shù)腻e(cuò)誤消息

              某個(gè)地方出錯(cuò)時(shí),滿屏都是錯(cuò)誤消息時(shí),應(yīng)該重點(diǎn)關(guān)注哪些消息?

              Answer: 首先出現(xiàn)的那些消息!因?yàn)楹竺娴南⒂锌赡苁乔懊鎸?dǎo)致的。這和編譯出錯(cuò)時(shí)的情景一致:編譯錯(cuò)誤有很多,我們肯定會(huì)直覺(jué)地去尋找第一個(gè)出錯(cuò)的 地方,誰(shuí)知道是不是少了個(gè)括號(hào)導(dǎo)致后面一連串的錯(cuò)誤。

            10. bug不會(huì)自動(dòng)消失

                  如果某個(gè)版本有bug,update后,bug消失了,“真好!”,一定要弄清楚bug出現(xiàn)的原因是什么。以前遇到過(guò)一個(gè)bug,增加一條printf語(yǔ)句后,bug消失了!最后發(fā)現(xiàn)問(wèn)題是數(shù)組越界了,而修改源代碼會(huì)導(dǎo)致代碼段,數(shù)據(jù)段的布局等改變,所以會(huì)導(dǎo)致偶爾對(duì)。(這種情況可以求助于內(nèi)存調(diào)試工具或者靜態(tài)檢查的工具)

            11. 學(xué)習(xí)使用gcc, gdb,strace 等工具。(熟悉以后可以再挖掘挖掘,可能有驚喜)

            12. cvs/svn commit之前一定要diff一下,看做了哪些修改,以避免不小心刪掉一些東西后,然后”被提交”了。

            最后,最強(qiáng)大的工具不在計(jì)算機(jī)中,而是調(diào)試者的判斷力和分析技巧。

               參考資料:

               1. 《軟件調(diào)試實(shí)戰(zhàn)》:http://book.douban.com/subject/4231293/

            posted @ 2011-05-17 20:26 hex108 閱讀(464) | 評(píng)論 (0)編輯 收藏
              2011年4月23日
                    對(duì)shell不熟,偶爾會(huì)現(xiàn)一些我無(wú)法理解的現(xiàn)象。此時(shí)該進(jìn)行debug了,可選的方法有:
                    a. echo變量的值 
                    b. shell –x
               
                    此外,Remember that the shell spends a lot of its life substituting text.(http://linuxcommand.org/wss0100.php)例如,對(duì)于下面的程序:
            hex108@Gentoo ~ $ cat test.sh 
            #!/bin/sh
            var=
            if [ $var = "y" ] ;then
                echo "yes"
            fi
                    if語(yǔ)句里的var變量經(jīng)替換后變?yōu)?if [ = "y" ],些時(shí)當(dāng)然會(huì)出錯(cuò)。
            hex108@Gentoo ~ $ ./test.sh 
            ./test.sh: line 3: [: =: unary operator expected

                      
                    ps:現(xiàn)在寫腳本的時(shí)候傾向于使用perl,而較少使用shell ,因?yàn)閷?duì)于經(jīng)常使用的腳本,可能會(huì)經(jīng)常需要對(duì)它不停地進(jìn)行改進(jìn),慢慢的,程序越來(lái)越大,該考慮重構(gòu)了,   此時(shí)才會(huì)發(fā)現(xiàn)perl(python等“真正的”腳本語(yǔ)言)比shell相對(duì)來(lái)說(shuō)更好重構(gòu)。

            posted @ 2011-04-23 00:23 hex108 閱讀(434) | 評(píng)論 (0)編輯 收藏
            僅列出標(biāo)題  下一頁(yè)
            久久精品国产免费观看| 亚洲精品高清国产一线久久| 国产精品久久一区二区三区| 久久人人爽人人爽人人AV东京热| 人人狠狠综合久久88成人| 久久99国产亚洲高清观看首页| 久久亚洲精品中文字幕三区| 久久亚洲高清综合| 久久99久久99精品免视看动漫| 99国产精品久久| 99久久综合国产精品免费| 狼狼综合久久久久综合网| 精品久久国产一区二区三区香蕉| 久久久久久亚洲精品影院| 九九99精品久久久久久| 一级a性色生活片久久无 | 久久99久久成人免费播放| 三级三级久久三级久久| 99久久精品费精品国产| 亚洲精品乱码久久久久66| 久久婷婷色综合一区二区| 久久97精品久久久久久久不卡| 亚洲国产成人久久综合碰| 精品国产91久久久久久久a| 久久精品国产亚洲av高清漫画| 看全色黄大色大片免费久久久| 93精91精品国产综合久久香蕉| 久久婷婷五月综合国产尤物app | 久久久久无码中| 91精品国产综合久久久久久| 亚洲精品乱码久久久久66| 国产亚洲成人久久| 91精品无码久久久久久五月天| 精品久久久久香蕉网| 伊人久久大香线蕉AV色婷婷色 | 国产伊人久久| 777久久精品一区二区三区无码| 成人妇女免费播放久久久| 久久精品国产亚洲AV大全| .精品久久久麻豆国产精品| 波多野结衣中文字幕久久|