每天早晨叫醒你的不是鬧鐘,而是夢想

From:http://blog.csdn.net/hairetz/archive/2009/05/06/4153252.aspx

個人感覺對于類的成員函數指針這塊講解的比較深入詳細

推薦閱讀

/////////////////////////////////////////////////

先看這樣一段代碼

class test
{
   public:
      test(int i){ m_i=i;}
      test(){}

      void hello()
      {
           printf("hello\n");
      }
   private:
       int m_i;
};

int main()
{
     test *p=new test();
     p->hello();
     p=NULL;
     p->hello();
}

結果是:

hello

hello

為何

p=NULL;
     p->hello();   這樣之后，NULL->hello()也依然有效呢？

我們第一反應一定是覺得類的實例的成員函數，不同于成員變量，成員函數全部都存在同一個地方，所以的類的實例來調用的時候，一定是調用相同的函數指針。（想想也是有道理的，成員函數都是一樣的功能，根本不需要實例化多個）

于是我們把代碼改成這樣

class test
{
    public:
        test(int i){ m_i=i;}
        test(){}

        void hello()
        {
            printf("hello\n");
        }

    private:
        int m_i;
};

typedef void (test::*HELLO_FUNC)();

int main()
{
     test *p=new test();
      test q;
      p->hello();
      HELLO_FUNC phello_fun=&test::hello;
      printf("%p\n",phello_fun);
      p=NULL;
      phello_fun=&test::hello;
      printf("%p\n",phello_fun);
      phello_fun=p->hello;
      printf("%p\n",phello_fun);
      phello_fun=q.hello;
      printf("%p\n",phello_fun);
      p->hello();
}

結果是：

hello
00401005
00401005
00401005
00401005
hello
Press any key to continue

也就是說不管是&test::hello,還是p->hello，或者q.hello,甚至于NULL->hello.

調用的地址都是0x00401005,也基本印證了我們的猜想。

事情到這里算是完了么？沒有。

有人問道這樣一段代碼：

SSVector& SSVector::assign2product4setup(const SVSet& A, const SSVector& x)
{
    int    ret_val= 

pthread_create(&pt,NULL,(void(*)(void*))SSVector::prefun,x);
}

void* SSVector::prefun (void* arg){
         const SSVector &tx =*((SSVector*) arg);
}
行報錯：invalid conversion from 'void (*)(void*)' to 'void* (*)(void*)'

pthread_create我就不解釋了，第3個參數是線程函數的指針，為何這里報錯呢？

說明普通的類成員函數的指針（如果它有函數指針的話），不同于一般的函數指針。

看看下面這篇文章關于這個問題的分析：

前言：在CSDN論壇經常會看到一些關于類成員函數指針的問題，起初我并不在意，以為成員函數指針和普通的函數指針是一樣的，沒有什么太多需要討論的。當我找來相關書籍查閱了一番以后，突然意識到我以前對成員函數指針的理解太過于幼稚和膚淺了，它即不像我以前認為的那樣簡單,它也不像我以前認為的那樣"默默無聞"。強烈的求知欲促使我對成員函數進行進一步的學習并有了這篇文章。

一。理論篇
在進行深入學習和分析之前，還是先看看書中是怎么介紹成員函數的。總結一下類成員函數指針的內容，應該包含以下幾個知識點：
1。成員函數指針并不是普通的函數指針。
2。編譯器提供了幾個新的操作符來支持成員函數指針操作：

1) 操作符"::*"用來聲明一個類成員函數指針，例如：
    typedef void (Base::*PVVBASEMEMFUNC)(void);        //Base is a class
2) 操作符"->*"用來通過對象指針調用類成員函數指針，例如：
    //pBase is a Base pointer and well initialized
    //pVIBaseMemFunc is a member function pointer and well initialized
    (pBase->*pVIBaseMemFunc)();
3) 操作符".*"用來通過對象調用類成員函數指針，例如：
    //baseObj is a Base object
    //pVIBaseMemFunc is a member function pointer and well initialized
    (baseObj.*pVIBaseMemFunc)();

3。成員函數指針是強類型的。

    typedef void (Base::*PVVBASEMEMFUNC)(void);
    typedef void (Derived::*PVVDERIVEMEMFUNC)(void);
PVVBASEMEMFUNC和PVVDERIVEMEMFUNC是兩個不同類型的成員函數指針類型。

4。由于成員函數指針并不是真真意義上的指針，所以成員函數指針的轉化就受限制。具體的轉化細節依賴于不同的編譯器，甚至是同一個編譯器的不同版本。不過，處于同一個繼承鏈中的不同類之間override的不同函數和虛函數還是可以轉化的。

    void* pVoid = reinterpret_cast<void*>(pVIBaseMemFunc);            //error
    int*  pInt  = reinterpret_cast<int*>(pVIBaseMemFunc);             //error
  pVIDeriveMemFunc = static_cast<PVIDERIVEMEMFUNC>(pVIBaseMemFunc);   //OK

二。實踐篇
有了上面的理論知識，我們對類成員函數指針有了大概的了解，但是我們對成員函數指針還存在太多的疑惑。既然說成員函數指針不是指針，那它到底是什么東東? 編譯器為什么要限制成員函數指針轉化？老辦法，我們還是分析匯編代碼揭示其中的秘密。首先，我寫了這樣兩個具有繼承關系的類：
接著，我又定義了一些成員函數指針類型：
最后，在main函數寫了一些測試代碼：
成功編譯后生成匯編代碼。老規矩，在分析匯編代碼的過程中還是只分析對解決問題有意義的匯編代碼，其他的就暫時忽略。
1。成員函數指針不是指針。從代碼看出，在main函數的調用棧(calling stack)中首先依次壓入四個成員函數指針，如果它們是普通指針的話，它們之間的偏移量應該是4個字節,可是實際的情況卻是這樣的：

 ”The implementation of the pointer to member function must store within itself information as to whether the member function to which it refers is virtual or nonvirtual, information about where to find the appropriate virtual function table pointer (see The Compiler Puts Stuff in Classes [11, 37]), an offset to be added to or subtracted from the function's this pointer (see Meaning of Pointer Comparison [28, 97]), and possibly other information. A pointer to member function is commonly implemented as a small structure that contains this information, although many other implementations are also in use. Dereferencing and calling a pointer to member function usually involves examining the stored information and conditionally executing the appropriate virtual or nonvirtual function calling sequence.“

2。成員函數指針的轉化。本文所采用的代碼是想比較普通成員函數指針和虛函數指針在轉化的過程中存在那些差異：
對于符號”??_9@$B3AE“，我又找到了這樣的匯編代碼： 由此可以看出，對于虛函數，即使是用過成員函數指針間接調用，仍然具有和直接調用一樣的特性。

    ; PVIBASEMEMFUNC pVIBaseMemFunc = &Base::setValue;
    mov    DWORD PTR _pVIBaseMemFunc$[ebp], OFFSET FLAT:?setValue@Base@@QAEXH@Z ;
    取出Base::setValue函數的地址，存放于變量pVIBaseMemFunc所占內存的前4個字節(DWORD)中。

; PVVBASEMEMFUNC      pVVBaseMemFunc   = &Base::foobar;
mov    DWORD PTR _pVVBaseMemFunc$[ebp], OFFSET FLAT:??_9@$B3AE ; `vcall'
取出符號”??_9@$B3AE“的值，存放于變量pVVBaseMemFunc所占內存的前4個字節(DWORD)中。

    _TEXT    SEGMENT
    ??_9@$B3AE PROC NEAR                    ; `vcall', COMDAT
    mov    eax, DWORD PTR [ecx]
    jmp    DWORD PTR [eax+4]
    ??_9@$B3AE ENDP                        ; `vcall'
    _TEXT    ENDS
符號”??_9@$B3AE“代表的應該是一個存根函數，這個函數首先根據this指針獲得虛函數表的指針，然后將指令再跳轉到相應的虛函數的地址。

    ; PVIDERIVEMEMFUNC pVIDeriveMemFunc = static_cast<PVIDERIVEMEMFUNC>(pVIBaseMemFunc);
    mov    eax, DWORD PTR _pVIBaseMemFunc$[ebp]
    mov    DWORD PTR _pVIDeriveMemFunc$[ebp], eax
直接將變量pVIBaseMemFunc所占內存的前4個字節(DWORD)的值付給了變量_pVIDeriveMemFunc所占內存的前4個字節中。

    ; PVVDERIVEMEMFUNC    pVVDeriveMemFunc = static_cast<PVVDERIVEMEMFUNC>(pVVBaseMemFunc);
    mov    eax, DWORD PTR _pVVBaseMemFunc$[ebp]
    mov    DWORD PTR _pVVDeriveMemFunc$[ebp], eax
直接將變量pVVBaseMemFunc所占內存的前4個字節(DWORD)的值付給了變量pVVDeriveMemFunc所占內存的前4個字節中。

由此可以看出，基類的成員函數指針轉化到相應的派生類的成員函數指針，值保持不變。當然這里的例子繼承關系相對來說比較簡單，如果存在多繼承和虛繼承的情況下，結果可能會復雜的多。

3。函數調用
下面的函數調用都大同小異，這里是列出其中的一個： 這里的匯編代碼并沒有給我們太多新鮮的內容：將對象的首地址(this指針)存放于寄存器ECX中，接著就將指令轉到變量_pVIBaseMemFunc所占內存的前4個字節所表示的地址。

到了這里，我們應該對成員函數指針有了進一步的了解。

    ; (baseObj.*pVIBaseMemFunc)(10);
    mov    esi, esp
    push    10                    ; 0000000aH
    lea    ecx, DWORD PTR _baseObj$[ebp]
    call    DWORD PTR _pVIBaseMemFunc$[ebp]
    cmp    esi, esp
    call    __RTC_CheckEsp  

由此可以看出，他們之間的偏移量是12個字節。這12個字節中應該可以包含三個指針，其中的一個指針應該指向函數的地址，那另外兩個指針又指向那里呢？在《C++ Common Knowledge: Essential Intermediate Programming》(中文譯名：

C++必知必會)這本書的第16章對這部分的內容做了說明，這個12個字節的偏移量正好印證了書中的內容：

class Base {
public:
    //ordinary member function
    void setValue(int iValue);

    //virtual member function
    virtual void dumpMe();
    virtual void foobar();

protected:
    int m_iValue;
};

class Derived:public Base{
public:
    //ordinary member function
    void setValue(int iValue);

    //virtual member function
    virtual void dumpMe();
    virtual void foobar();
private:
    double m_fValue;
};

    typedef void (Base::*PVVBASEMEMFUNC)(void);
    typedef void (Derived::*PVVDERIVEMEMFUNC)(void);
    typedef void (Base::*PVIBASEMEMFUNC)(int);
    typedef void (Derived::*PVIDERIVEMEMFUNC)(int);

int _tmain(int argc, _TCHAR* argv[])
{
    PVIBASEMEMFUNC pVIBaseMemFunc = &Base::setValue;
    PVIDERIVEMEMFUNC pVIDeriveMemFunc = static_cast<PVIDERIVEMEMFUNC>(pVIBaseMemFunc);

    PVVBASEMEMFUNC      pVVBaseMemFunc   = &Base::foobar;
    PVVDERIVEMEMFUNC    pVVDeriveMemFunc = static_cast<PVVDERIVEMEMFUNC>(pVVBaseMemFunc);

    Base baseObj;
    (baseObj.*pVIBaseMemFunc)(10);
    (baseObj.*pVVBaseMemFunc)();

    Derived deriveObj;
    (deriveObj.*pVIDeriveMemFunc)(20);
    (deriveObj.*pVVDeriveMemFunc)();

    return 0;
}

_deriveObj$ = -88
_baseObj$ = -60
_pVVDeriveMemFunc$ = -44
_pVVBaseMemFunc$ = -32
_pVIDeriveMemFunc$ = -20
_pVIBaseMemFunc$ = -8
_argc$ = 8
_argv$ = 12

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/eroswang/archive/2009/05/06/4153356.aspx

邏輯地址（Logical Address） 是指由程序產生的與段相關的偏移地址部分。例如，你在進行C語言指針編程中，可以讀取指針變量本身值(&操作)，實際上這個值就是邏輯地址，它是相對于你當前進程數據段的地址，不和絕對物理地址相干。只有在Intel實模式下，邏輯地址才和物理地址相等（因為實模式沒有分段或分頁機制,Cpu不進行自動地址轉換）；邏輯也就是在Intel 保護模式下程序執行代碼段限長內的偏移地址（假定代碼段、數據段如果完全一樣）。應用程序員僅需與邏輯地址打交道，而分段和分頁機制對您來說是完全透明的，僅由系統編程人員涉及。應用程序員雖然自己可以直接操作內存，那也只能在操作系統給你分配的內存段操作。

線性地址（Linear Address） 是邏輯地址到物理地址變換之間的中間層。程序代碼會產生邏輯地址，或者說是段中的偏移地址，加上相應段的基地址就生成了一個線性地址。如果啟用了分頁機制，那么線性地址可以再經變換以產生一個物理地址。若沒有啟用分頁機制，那么線性地址直接就是物理地址。Intel 80386的線性地址空間容量為4G（2的32次方即32根地址總線尋址）。

物理地址（Physical Address） 是指出現在CPU外部地址總線上的尋址物理內存的地址信號，是地址變換的最終結果地址。如果啟用了分頁機制，那么線性地址會使用頁目錄和頁表中的項變換成物理地址。如果沒有啟用分頁機制，那么線性地址就直接成為物理地址了。

虛擬內存（Virtual Memory） 是指計算機呈現出要比實際擁有的內存大得多的內存量。因此它允許程序員編制并運行比實際系統擁有的內存大得多的程序。這使得許多大型項目也能夠在具有有限內存資源的系統上實現。一個很恰當的比喻是：你不需要很長的軌道就可以讓一列火車從上海開到北京。你只需要足夠長的鐵軌（比如說3公里）就可以完成這個任務。采取的方法是把后面的鐵軌立刻鋪到火車的前面，只要你的操作足夠快并能滿足要求，列車就能象在一條完整的軌道上運行。這也就是虛擬內存管理需要完成的任務。在Linux 0.11內核中，給每個程序（進程）都劃分了總容量為64MB的虛擬內存空間。因此程序的邏輯地址范圍是0x0000000到0x4000000。

有時我們也把邏輯地址稱為虛擬地址。因為與虛擬內存空間的概念類似，邏輯地址也是與實際物理內存容量無關的。
邏輯地址與物理地址的“差距”是0xC0000000，是由于虛擬地址->線性地址->物理地址映射正好差這個值。這個值是由操作系統指定的。

虛擬地址到物理地址的轉化方法是與體系結構相關的。一般來說有分段、分頁兩種方式。以現在的x86 cpu為例，分段分頁都是支持的。Memory Mangement Unit負責從虛擬地址到物理地址的轉化。邏輯地址是段標識+段內偏移量的形式，MMU通過查詢段表，可以把邏輯地址轉化為線性地址。如果cpu沒有開啟分頁功能，那么線性地址就是物理地址；如果cpu開啟了分頁功能，MMU還需要查詢頁表來將線性地址轉化為物理地址：
邏輯地址 ----（段表）---> 線性地址 — （頁表）—> 物理地址
不同的邏輯地址可以映射到同一個線性地址上；不同的線性地址也可以映射到同一個物理地址上；所以是多對一的關系。另外，同一個線性地址，在發生換頁以后，也可能被重新裝載到另外一個物理地址上。所以這種多對一的映射關系也會隨時間發生變化。

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/leves1989/archive/2008/11/15/3305402.aspx

原文標題：Cache: a place for concealment and safekeeping

原文地址：http://duartes.org/gustavo/blog/

[注：本人水平有限，只好挑一些國外高手的精彩文章翻譯一下。一來自己復習，二來與大家分享。]

本文簡要的展示了現代Intel處理器的CPU cache是如何組織的。有關cache的討論往往缺乏具體的實例，使得一些簡單的概念變得撲朔迷離。也許是我可愛的小腦瓜有點遲鈍吧，但不管怎樣，至少下面講述了故事的前一半，即Core 2的 L1 cache是如何被訪問的：

L1 cache – 32KB，8路組相聯，64字節緩存線

1.       由索引揀選緩存組（行）

在cache中的數據是以緩存線（line）為單位組織的，一條緩存線對應于內存中一個連續的字節塊。這個cache使用了64字節的緩存線。這些線被保存在cache bank中，也叫路（way）。每一路都有一個專門的目錄（directory）用來保存一些登記信息。你可以把每一路連同它的目錄想象成電子表格中的一列，而表的一行構成了cache的一組（set）。列中的每一個單元（cell）都含有一條緩存線，由與之對應的目錄單元跟蹤管理。圖中的cache有64 組、每組8路，因此有512個含有緩存線的單元，合計32KB的存儲空間。

在cache眼中，物理內存被分割成了許多4KB大小的物理內存頁（page）。每一頁都含有4KB / 64 bytes == 64條緩存線。在一個4KB的頁中，第0到63字節是第一條緩存線，第64到127字節是第二條緩存線，以此類推。每一頁都重復著這種劃分，所以第0頁第3條緩存線與第1頁第3條緩存線是不同的。

在全相聯緩存（fully associative cache）中，內存中的任意一條緩存線都可以被存儲到任意的緩存單元中。這種存儲方式十分靈活，但也使得要訪問它們時，檢索緩存單元的工作變得復雜、昂貴。由于L1和L2 cache工作在很強的約束之下，包括功耗，芯片物理空間，存取速度等，所以在多數情況下，使用全相聯緩存并不是一個很好的折中。

取而代之的是圖中的組相聯緩存（set associative cache）。意思是，內存中一條給定的緩存線只能被保存在一個特定的組（或行）中。所以，任意物理內存頁的第0條緩存線（頁內第0到63字節）必須存儲到第0組，第1條緩存線存儲到第1組，以此類推。每一組有8個單元可用于存儲它所關聯的緩存線（譯注：就是那些需要存儲到這一組的緩存線），從而形成一個8路關聯的組（8-way associative set）。當訪問一個內存地址時，地址的第6到11位（譯注：組索引）指出了在4KB內存頁中緩存線的編號，從而決定了即將使用的緩存組。舉例來說，物理地址0x800010a0的組索引是000010，所以此地址的內容一定是在第2組中緩存的。

但是還有一個問題，就是要找出一組中哪個單元包含了想要的信息，如果有的話。這就到了緩存目錄登場的時刻。每一個緩存線都被其對應的目錄單元做了標記（tag）；這個標記就是一個簡單的內存頁編號，指出緩存線來自于哪一頁。由于處理器可以尋址64GB的物理RAM，所以總共有64GB / 4KB == 224個內存頁，需要24位來保存標記。前例中的物理地址0x800010a0對應的頁號為524,289。下面是故事的后一半：

在組中搜索匹配標記

由于我們只需要去查看某一組中的8路，所以查找匹配標記是非常迅速的；事實上，從電學角度講，所有的標記是同時進行比對的，我用箭頭來表示這一點。如果此時正好有一條具有匹配標簽的有效緩存線，我們就獲得一次緩存命中（cache hit）。否則，這個請求就會被轉發的L2 cache，如果還沒匹配上就再轉發給主系統內存。通過應用各種調節尺寸和容量的技術，Intel給CPU配置了較大的L2 cache，但其基本的設計都是相同的。比如，你可以將原先的緩存增加8路而獲得一個64KB的緩存；再將組數增加到4096，每路可以存儲256KB。經過這兩次修改，就得到了一個4MB的L2 cache。在此情況下，需要18位來保存標記，12位保存組索引；緩存所使用的物理內存頁的大小與其一路的大小相等。（譯注：有4096組，就需要lg(4096)==12位的組索引，緩存線依然是64字節，所以一路有4096*64B==256KB字節；在L2 cache眼中，內存被分割為許多256KB的塊，所以需要lg(64GB/256KB)==18位來保存標記。）

如果有一組已經被放滿了，那么在另一條緩存線被存儲進來之前，已有的某一條則必須被騰空（evict）。為了避免這種情況，對運算速度要求較高的程序就要嘗試仔細組織它的數據，使得內存訪問均勻的分布在已有的緩存線上。舉例來說，假設程序中有一個數組，元素的大小是512字節，其中一些對象在內存中相距4KB。這些對象的各個字段都落在同一緩存線上，并競爭同一緩存組。如果程序頻繁的訪問一個給定的字段（比如，通過虛函數表vtable調用虛函數），那么這個組看起來就好像一直是被填滿的，緩存開始變得毫無意義，因為緩存線一直在重復著騰空與重新載入的步驟。在我們的例子中，由于組數的限制，L1 cache僅能保存8個這類對象的虛函數表。這就是組相聯策略的折中所付出的代價：即使在整體緩存的使用率并不高的情況下，由于組沖突，我們還是會遇到緩存缺失的情況。然而，鑒于計算機中各個存儲層次的相對速度，不管怎么說，大部分的應用程序并不必為此而擔心。

一個內存訪問經常由一個線性（或虛擬）地址發起，所以L1 cache需要依賴分頁單元（paging unit）來求出物理內存頁的地址，以便用于緩存標記。與此相反，組索引來自于線性地址的低位，所以不需要轉換就可以使用了（在我們的例子中為第6到11位）。因此L1 cache是物理標記但虛擬索引的（physically tagged but virtually indexed），從而幫助CPU進行并行的查找操作。因為L1 cache的一路絕不會比MMU的一頁還大，所以可以保證一個給定的物理地址位置總是關聯到同一組，即使組索引是虛擬的。在另一方面L2 cache必須是物理標記和物理索引的，因為它的一路比MMU的一頁要大。但是，當一個請求到達L2 cache時，物理地址已經被L1 cache準備（resolved）完畢了，所以L2 cache會工作得很好。

最后，目錄單元還存儲了對應緩存線的狀態（state）。在L1代碼緩存中的一條緩存線要么是無效的（invalid）要么是共享的（shared，意思是有效的，真的J）。在L1數據緩存和L2緩存中，一條緩存線可以為4個MESI狀態之一：被修改的（modified），獨占的（exclusive），共享的（shared），無效的（invalid）。Intel緩存是包容式的（inclusive）：L1緩存的內容會被復制到L2緩存中。在下一篇討論線程（threading），鎖定（locking）等內容的文章中，這些緩存線狀態將發揮作用。下一次，我們將看看前端總線以及內存訪問到底是怎么工作的。這將成為一個內存研討周。

（在回復中Dave提到了直接映射緩存（direct-mapped cache）。它們基本上是一種特殊的組相聯緩存，只是只有一路而已。在各種折中方案中，它與全相聯緩存正好相反：訪問非常快捷，但因組沖突而導致的緩存缺失也非常多。）

[譯者小結：

1.         內存層次結構的意義在于利用引用的空間局部性和時間局部性原理，將經常被訪問的數據放到快速的存儲器中，而將不經常訪問的數據留在較慢的存儲器中。

2.         一般情況下，除了寄存器和L1緩存可以操作指定字長的數據，下層的內存子系統就不會再使用這么小的單位了，而是直接移動數據塊，比如以緩存線為單位訪問數據。

3.         對于組沖突，可以這么理解：與上文相似，假設一個緩存，由512條緩存線組成，每條線64字節，容量32KB。

a)         假如它是直接映射緩存，由于它往往使用地址的低位直接映射緩存線編號，所以所有的32K倍數的地址（32K，64K，96K等）都會映射到同一條線上（即第0線）。假如程序的內存組織不當，交替的去訪問布置在這些地址的數據，則會導致沖突。從外表看來就好像緩存只有1條線了，盡管其他緩存線一直是空閑著的。

b)        如果是全相聯緩存，那么每條緩存線都是獨立的，可以對應于內存中的任意緩存線。只有當所有的512條緩存線都被占滿后才會出現沖突。

c)        組相聯是前兩者的折中，每一路中的緩存線采用直接映射方式，而在路與路之間，緩存控制器使用全相聯映射算法，決定選擇一組中的哪一條線。

d)        如果是2路組相聯緩存，那么這512條緩存線就被分為了2路，每路256條線，一路16KB。此時所有為16K整數倍的地址（16K，32K，48K等）都會映射到第0線，但由于2路是關聯的，所以可以同時有2個這種地址的內容被緩存，不會發生沖突。當然了，如果要訪問第三個這種地址，還是要先騰空已有的一條才行。所以極端情況下，從外表看來就好像緩存只有2條線了，盡管其他緩存線一直是空閑著的。

e)         如果是8路組相聯緩存（與文中示例相同），那么這512條緩存線就被分為了8路，每路64條線，一路4KB。所以如果數組中元素地址是4K對齊的，并且程序交替的訪問這些元素，就會出現組沖突。從外表看來就好像緩存只有8條線了，盡管其他緩存線一直是空閑著的。

]

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/drshenlei/archive/2009/06/17/4277959.aspx

我們經常會發現有兩種內存轉儲(core dump)  
  一種是段故障（segment fault）通常是在一個非法的地址上進行取值賦值操作造成。  
  一種是總線錯誤（bus error）通常是指針強制轉換，導致CPU讀取數據違反了一定的總線規則。

首先，core就是內存的意思，在半導體應用之前，內存是由鐵氧化物圓環制造的（core），但一直沿用至今。

而這兩種錯誤，都是有硬件告知操作系統一個有問題的內存引用。操作系統通過信號，再將錯誤信息告知進程。缺省情況下，進程收到“總線錯誤”或“段錯誤”信號后，將信息轉儲并終止。當然也可以為這些信號設置一個信號處理程序（signal handler）。

總線錯誤（bus error），幾乎都是有內存未對齊讀引起的。內存對齊，就是內存變量的地址只能是其大小的整數倍，這樣存儲的目的就是為了方便并快速存取內存。一般情況下，編譯器都會做好內存對齊工作，為什么又會引發段故障呢？很多情況就是由指針和強制類型轉換引起的，如：

union{

    char a[10];

    int i;

}u;

int *p = (int *)&(u.a[1]);

*p = 17;

當然，還有一些其它原因會引起“總線錯誤”，如奇偶校驗碼錯誤，所引用的內存塊不存在。但是現在，內存都有硬件電路檢測和修正，一般不會再傳到軟件層了；除了驅動程序，一般也不會引用不存在的內存塊。

段錯誤，一般是由于引用不位于自己的地址空間的地址引起的。最常見的就是通過一個未初始化，或者有非法值的指針引起的，如：int *p = 0; *p = 7; 而導致指針的非法值可能是由于不同的編程錯誤引起的，比起“總線錯誤”更加間接。

段錯誤一般是由硬件段表轉換機構的錯誤引發，如Sun硬件中的內存管理單元(MMU)。

還有一個微妙之處是，如果未初始化的指針恰好具有未對齊的值，它將產生總線錯誤，而不是段錯誤。

遺傳算法

遺傳算法（Genetic Algorithm, GA）是近幾年發展起來的一種嶄新的全局優化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遺傳學和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，實現各個個體的適應性的提高。從某種程度上說遺傳算法是對生物進化過程進行的數學方式仿真。

這一點體現了自然界中"物競天擇、適者生存"進化過程。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價,把問題的解表示成染色體，并基于適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。在算法中也即是以二進制編碼的串。并且，在執行遺傳算法之前，給出一群染色體，也即是假設解。然后，把這些假設解置于問題的“環境”中，也即一個適應度函數中來評價。并按適者生存的原則，從中選擇出較適應環境的染色體進行復制, 淘汰低適應度的個體，再通過交叉，變異過程產生更適應環境的新一代染色體群。對這個新種群進行下一輪進化，至到最適合環境的值。

遺傳算法已用于求解帶有應用前景的一些問題，例如遺傳程序設計、函數優化、排序問題、人工神經網絡、分類系統、計算機圖像處理和機器人運動規劃等。

術語說明

由于遺傳算法是由進化論和遺傳學機理而產生的搜索算法，所以在這個算法中會用到很多生物遺傳學知識，下面是我們將會用來的一些術語說明：

一、染色體(Chronmosome)

染色體又可以叫做基因型個體(individuals),一定數量的個體組成了群體(population),群體中個體的數量叫做群體大小。

二、基因(Gene)

基因是串中的元素，基因用于表示個體的特征。例如有一個串S＝1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。

三、基因地點(Locus)

基因地點在算法中表示一個基因在串中的位置稱為基因位置(Gene Position)，有時也簡稱基因位。基因位置由串的左向右計算，例如在串 S＝1101 中，0的基因位置是3。

四、基因特征值(Gene Feature)

在用串表示整數時，基因的特征值與二進制數的權一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。

五、適應度(Fitness)

各個個體對環境的適應程度叫做適應度(fitness)。為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數. 這個函數是計算個體在群體中被使用的概率。

操作算法

霍蘭德(Holland)教授最初提出的算法也叫簡單遺傳算法，簡單遺傳算法的遺傳操作主要有三種：選擇(selection)、交叉(crossover)、變異(mutation)這也是遺傳算法中最常用的三種算法：

1．選擇(selection)

選擇操作也叫復制操作，從群體中按個體的適應度函數值選擇出較適應環境的個體。一般地說，選擇將使適應度高的個體繁殖下一代的數目較多，而適應度較小的個體，繁殖下一代的數目較少,甚至被淘汰。最通常的實現方法是輪盤賭(roulette wheel)模型。令Σfi表示群體的適應度值之總和，fi表示種群中第i個染色體的適應度值，它被選擇的概率正好為其適應度值所占份額fi／Σfi。如下圖表中的數據適應值總和Σfi=6650,適應度為2200變選擇的可能為fi／Σfi=2200/6650=0.394.

2．交叉(Crossover)

交叉算子將被選中的兩個個體的基因鏈按一定概率pc進行交叉，從而生成兩個新的個體，交叉位置pc是隨機的。其中Pc是一個系統參數。根據問題的不同，交叉又為了單點交叉算子（Single Point Crossover）、雙點交叉算子（Two Point Crossover）、均勻交叉算子 (Uniform Crossover)，在此我們只討論單點交叉的情況。

單點交叉操作的簡單方式是將被選擇出的兩個個體S1和S2作為父母個體，將兩者的部分基因碼值進行交換。假設如下兩個8位的個體：

S1 1000  1111 S2 1110  1100

產生一個在1到7之間的隨機數c，假如現在產生的是2，將S1和S2的低二位交換：S1的高六位與S2的低六位組成數串10001100，這就是S1和S2 的一個后代P1個體；S2的高六位與S1的低二位組成數串11101111，這就是S1和S2的一個后代P2個體。其交換過程如下圖所示：

3．變異(Mutation)

這是在選中的個體中，將新個體的基因鏈的各位按概率pm進行異向轉化，最簡單方式是改變串上某個位置數值。對二進制編碼來說將0與1互換：0變異為1，1變異為0。

如下8位二進制編碼：

1 1 1 0 1 1 0 0

隨機產生一個1至8之間的數i，假如現在k=6，對從右往左的第6位進行變異操作，將原來的1變為0，得到如下串：

1 1 0 0 1 1 0 0

整個交叉變異過程如下圖：

 

4．精英主義 （Elitism）

僅僅從產生的子代中選擇基因去構造新的種群可能會丟失掉上一代種群中的很多信息。也就是說當利用交叉和變異產生新的一代時，我們有很大的可能把在某個中間步驟中得到的最優解丟失。在此我們使用精英主義（Elitism）方法，在每一次產生新的一代時，我們首先把當前最優解原封不動的復制到新的一代中，其他步驟不變。這樣任何時刻產生的一個最優解都可以存活到遺傳算法結束。

上述各種算子的實現是多種多樣的，而且許多新的算子正在不斷地提出，以改進GA某些性能。比如選擇算法還有分級均衡選擇等等。

遺傳算法的所需參數

說簡單點遺傳算法就是遍歷搜索空間或連接池，從中找出最優的解。搜索空間中全部都是個體，而群體為搜索空間的一個子集。并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定的概率進行，一般在程序設計中交叉發生的概率要比變異發生的概率選取得大若干個數量級。大部分遺傳算法的步驟都很類似，常使用如下參數：

Fitness函數：見上文介紹。

Fitnessthreshold（適應度閥值）：適合度中的設定的閥值，當最優個體的適應度達到給定的閥值，或者最優個體的適應度和群體適應度不再上升時(變化率為零)，則算法的迭代過程收斂、算法結束。否則，用經過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到選擇操作處繼續循環執行。

P：種群的染色體總數叫種群規模，它對算法的效率有明顯的影響，其長度等于它包含的個體數量。太小時難以求出最優解，太大則增長收斂時間導致程序運行時間長。對不同的問題可能有各自適合的種群規模，通常種群規模為 30 至 160。

pc：在循環中進行交叉操作所用到的概率。交叉概率（Pc）一般取0.6至0.95之間的值，Pc太小時難以向前搜索，太大則容易破壞高適應值的結構。

Pm：變異概率，從個體群中產生變異的概率，變異概率一般取0.01至0.03之間的值變異概率Pm太小時難以產生新的基因結構，太大使遺傳算法成了單純的隨機搜索。

另一個系統參數是個體的長度，有定長和變長兩種。它對算法的性能也有影響。由于GA是一個概率過程，所以每次迭代的情況是不一樣的,系統參數不同，迭代情況也不同。

遺傳步驟

了解了上面的基本參數，下面我們來看看遺傳算法的基本步驟。

基本過程為：

1. 對待解決問題進行編碼,我們將問題結構變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結構的過程叫譯碼。
2. 隨機初始化群體P(0)：=(p1, p2, … pn)；
3. 計算群體上每個個體的適應度值(Fitness)
4. 評估適應度,對當前群體P(t)中每個個體Pi計算其適應度F(Pi)，適應度表示了該個體的性能好壞
5. 按由個體適應度值所決定的某個規則應用選擇算子產生中間代Pr(t)
6. 依照Pc選擇個體進行交叉操作
7. 仿照Pm對繁殖個體進行變異操作
8. 沒有滿足某種停止條件，則轉第3步，否則進入9
9. 輸出種群中適應度值最優的個體

程序的停止條件最簡單的有如下二種：完成了預先給定的進化代數則停止；種群中的最優個體在連續若干代沒有改進或平均適應度在連續若干代基本沒有改進時停止。

根據遺傳算法思想可以畫出如右圖所示的簡單遺傳算法框圖：

下面偽代碼簡單說明了遺傳算法操作過程：

choose an intial population
For each h in population,compute Fitness(h)
While(max Fitness(h) < Fitnessthreshold)
do selection
    do crossover
do mutation  
 update population
For each h in population,compute Fitness(h)
Return best Fitness

Robocode 說明

能有效實現遺傳算法的應用例子有很多，像西洋雙陸棋、國際名模等等都是遺傳程序設計學習的工具，但是 Robocode 有著其他幾個無可比擬的優勢：

1. 它是基于面向對象語言 Java 開發，而遺傳算法本身的思想也是存在繼承等面向對象概念；
2. Robocode 是一種基于游戲與編程語言之間的平臺，有一個充滿競技與樂趣的坦克戰斗平臺，你能很快的通過與其他坦克機器比賽而測試自己的遺傳算法；
3. Robocode 社群有 4000 個左右各種策略的例子機器人可供你選擇，這些機器人足以讓我們模擬真實的遺傳環境。而且很多代碼可直接開放源代碼供我們借鑒 ；
4. Robocode 是一個開源軟件，你可直接上Robocode控制器上加入自己的遺傳特點，而加快遺傳過程的收斂時間；
5. Robocoe 是一個很容易使用的機器人戰斗仿真器，您在此平臺上創建自己的坦克機器人，并與其它開發者開發的機器人競技。以得分排名的方式判定優勝者。每個 Robocode 參加者都要利用 Java 語言元素創建他或她的機器人，這樣就使從初學者到高級黑客的廣大開發者都可以參與這一娛樂活動。如果您對Robocode不是很了解，請參考 developerWorks 網站 Java 技術專區文章：“重錘痛擊 Robocode”；

在 Robocode 中其實有很多種遺傳算法方法來實現進化機器人，從全世界的 Robocode 流派中也發展幾種比較成熟的方法，比如預設策略遺傳、自開發解釋語言遺傳、遺傳移動我們就這幾種方法分別加以介紹。由于遺傳算法操作過程都類似，所以前面二部分都是一些方法的介紹和部分例子講解，后面部分會給出使用了遺傳算法的移動機器人人例子。在附錄中，也提供了機器人倉庫中有關遺傳算法機器人的下載，大家可參考。

預設策略進化機器人

Robocode 坦克機器人所有行為都離不開如移動、射擊、掃描等基本操作。所以在此把這些基本操作所用到的策略分別進化如下編碼：移動策略move-strategy (MS), 子彈能量bullet-power-strategy (BPS), 雷達掃描radar-strategy (RS), 和瞄準選擇策略target- strategy (TS)。由于Robocode愛好者社群的發展，每一種基本操作都發展了很多比較成熟的策略，所有在此我們直接在下面預先定義的這些策略如下表：

下面是基本移動策略的說明：

• Random：隨機移動主要用來混亂敵人的預測，其最大的一個缺點是有可能撞擊到其他機器人
• Linear：直線移動,機器人做單一的直線行走
• circular：圓周移動，這種移動是以某一點為圓心，不停的繞圈
• Perpendicular：正對敵人移動，這是很多人采用的一種移動方式，這在敵人右邊， 以隨時調整與敵人的相對角
• Arbitrary：任意移動
• AntiGravity：假設場地有很多力點的反重力移動，本方法是模擬在重力場作用下，物體總是遠離重力勢高的點，滑向重力勢低的點，開始戰場是一個平面然后生成一些勢點重力勢大的勢點的作用就像是一個山(起排斥作用），其衰減系數與山的坡度對應。重力勢小的勢點的作用就像是一個低谷（起吸引作用），其衰減系數與谷的坡度對應。這樣使本來的平面變得不平了，從來物體沿著最陡的方向向下滑動
• Track：跟蹤敵人，敵人移動到哪，機器人也移動到哪，但是總與敵人保持一定最佳躲避子彈距離和角度
• Oscillators：重復做一振蕩移動
• Bullet avoid：每當雷達覺察到敵人時有所動作。機器人保持與敵人成30度傾向角。自身成 90 度角靜止并逐漸接近目標。如果機器人覺察到能量下降介于 0.1 和 3.0 之間（火力范圍），那么機器人就立即切換方向，向左或向右移動。
• wall avoid：這是一種使自己的機器人不會被困在角落里或者不會撞墻的移動方式

瞄準策略說明如下：

• Headon：正對瞄準
• Linear：直線瞄準
• circular：圓周瞄準
• nearest robot：接近機器人瞄準
• Log：保存每次開火記錄
• Statistic：統計學瞄準，分析所有打中及未打中的次數，以其中找出最高打中敵人的概率為準則
• Angular：找到最佳角度瞄準
• Wave：波形瞄準，子彈以波的方式進行探測

Robocode 行為事件

坦克的主要都定義在一個主循環中，我們在程序中定義為上面四個策略定義四種戰略如Move,Radar,Power,Target，當某一事件發生，基于這個事件而定的行為就會觸發。而每個戰略中都有不同的行為處理方式。這些行為通過遺傳算法觸發，遺傳算法將調用這些基本動作并搜索這些策略的最佳組合。基于這些基本動作將有4224 (=4*11*4*3*8)種可能發生。在Robocode AdvancedRobot 類下有如下的移動函數：

• setAhead和ahead：讓機器人向前移動一定距離.
• setBack和back：讓機器人向后移動一定距離
• setMaxTurnRate：設置機器人最大的旋轉速度
• setMaxVelocity：設置機器人最大的運動速度
• setStop和stop：停止移動或暫停機器人，并記住停止的位置
• setResume和resume：重新開始移動停止的機器人
• setTurnLeft和turnLeft：向左旋轉機器人
• setTurnRight和turnRight：向右旋轉機器人

下面是 doMove 移動方法中使用部分程序代碼：

Random：

switch(Math.random()*2) {
 case 0： setTurnRight(Math.random()*90);
break;
case 1： setTurnLeft(Math.random()*90);
 break; }
 execute();

Linear：

ahead(200);
setBack(200);

Circular：

setTurnRight(1000);
setMaxVelocity(4);
ahead(1000);

anti gravity：

 double forceX = 0;
  double forceY = 0;
  for (int i=0; i   

這里我們用遺傳算法來控制機器人移動位置。這些策略是基于下面幾點：機器人人自己的位置、速度和方位;對手的位置（x,y坐標）、速度、方位以及相對角;所有機器人和子彈位置，方位及速度;場地大小等參數。

當上面的信息在下一回移動中使用時，出輸出一對坐標值，根據這對坐標在Robocode就能得到距離和角度。要想讓移動實現遺傳必須要讓它實現在線學習：所以我們的代碼必須做下面幾件事：要有一個函數收集適應度值，在Robocode運行過程中要運用到遺傳操作，遺傳后代要在Robocode運行中產生，而不是事后由手寫入代碼。

遺傳操作

本例中遺傳算法為實現移動用到兩個類GA和MovePattern。此處的GA比較簡單主要完成數據和群體的定義，以及這些定義的讀寫文件操作。基中包括如下參數：群體大小、交叉概率、變異概率、精英概率（既告訴從當前群體到下一代中有多少移動不需要改變）、方程式中使用的加權系數大小，它通過一個主循環完成MovePattern的封裝。MovePattern類中實現交叉、變異方法等方法，完成移動模式操作。而所有的輸出保存在一個vector函數當中。Vector函數擁有一對實數數組，一個用于計算x坐標，另一個用于計算y坐標。通過對x,y坐標的計算，從而得到距離、角度等值，并產生相就在移動策略。如下，MovePattern包含三個參數，grad表示vector函數排列順序，input即表示算法給出的輸入編號，rang是加權的范圍。

public class MovePatteren implements Comparable {
 private int grad, input;
 private double range;
 protected double fitness=0;
 protected double[] weightsX, weightsY;    
… }

交叉操作：每一個交叉操作執行如下步驟，先在交叉操作中產生一個特征碼。這個特征碼是個0到1之間的變量數組。有關交叉的基本原理可參考上面部分。最后通過遍歷vector函數，把相應的加權值進行交叉操作。

protected MovePatteren crossOver(MovePatteren mate, boolean[] maskx, boolean[] masky) {
  double[] wx= new double[weightsX.length];
  double[] wy= new double[weightsX.length];
  for(int mask=0; mask <="" pre="" mask++)="" for(int="" g="0;" g  

這里的變異操作比較簡單。把加權范圍內的隨機數值去代替0到數組長之間的隨機數并保存到移動模式中。則完成整個數組的變異過程：

protected void mutate() {
weightsX[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;
weightsY[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;
}

從上面的例子我們知道了遺傳算法的大概實現，但并沒有告訴我們這些組件是如何一起工作的。當Robocode開始時，如果文件中沒有數據，所以系統會依照輸入的策略隨機生成一個移動模式，如果文件中有數據，則加載這些數據。每一個移動模式在開始都會給出了一個適應度值。當所有的移動模式都接收到適應度值，并完成各自的編號后，下面的操作將開始執行：

1. 對所有的移動模式依據它們的適應度值進行分級處理
2. 執行精英操作
3. 執行交叉操作
4. 應用變異操作
5. 保存加權
6. 算法重新開始

適應度值在進行運算過程中由機器人程序不斷調整，以找到最優適應度。

限于篇副其他的一些策略本文不與詳細說明，上面所有提到的策略和行為程序都可在網上或IBM的開發雜志上找到成熟的講解和例子機器人。有興趣的朋友可以把這些策略都加入到自己的遺傳算法中來。我們取群體大小為50，選擇概率為0.7，交叉概率為0.6，變異概率為0.3，與Robocode部分例子機器人測試，經過150代后你會發現系統產生了很多有趣的策略。比如撞擊策略，這些策略都不在我們定義的策略之中。

中間解釋程序進化機器人

遺傳算法可被看做任意基因組字符串。但是你必須決定這些字符所代表的意義，也就是說如何解釋每一個基因組。最簡單的方法是把每一個基因組視為java代碼，編譯并運行它們。但是這些程序編譯都很困難，所以也就有可能不能工作。Jacob Eisenstein設計了一種機器翻譯語言TableRex來解決這個問題。在java中，TableRex被用于進化和解釋動行時的Robocode 機器人。通過測試，只要我把TableRex解釋程序作為文件放入Robocode控制器目錄中，這些控制器就會讀取文件并開始戰斗。TableRex是一些最適合遺傳算法的二進制編程。只要符合TableRex程序文法，每個程序都能被解釋。

編碼

下表中顯示了TableRex編碼結構，它由一個行動作函數，二個輸入和一個輸出組成。如行6的值 ，這是個布爾型的表達式“值 line4 小于 90”，這個結果會在最后一行輸出布爾為1的值。