每天早晨叫醒你的不是闹钟,而是梦想

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的值。