• <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>

            每天早晨叫醒你的不是鬧鐘,而是夢(mèng)想

              C++博客 :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              62 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(1)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            #

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

            個(gè)人感覺對(duì)于類的成員函數(shù)指針這塊講解的比較深入詳細(xì)

            推薦閱讀

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

            先看這樣一段代碼

            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();
            }

             

            結(jié)果是:

            hello

            hello

            為何

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

            我們第一反應(yīng)一定是覺得類的實(shí)例的成員函數(shù),不同于成員變量,成員函數(shù)全部都存在同一個(gè)地方,所以的類的實(shí)例來調(diào)用的時(shí)候,一定是調(diào)用相同的函數(shù)指針。(想想也是有道理的,成員函數(shù)都是一樣的功能,根本不需要實(shí)例化多個(gè))

            于是我們把代碼改成這樣

             

            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();
            }

             

            結(jié)果是:

            hello
            00401005
            00401005
            00401005
            00401005
            hello
            Press any key to continue

             

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

            調(diào)用的地址都是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);
            }
            行報(bào)錯(cuò):invalid conversion from 'void (*)(void*)' to 'void* (*)(void*)'

            pthread_create我就不解釋了,第3個(gè)參數(shù)是線程函數(shù)的指針,為何這里報(bào)錯(cuò)呢?

             

            說明普通的類成員函數(shù)的指針(如果它有函數(shù)指針的話),不同于一般的函數(shù)指針。

             

            看看下面這篇文章關(guān)于這個(gè)問題的分析:

            前言:在CSDN論壇經(jīng)常會(huì)看到一些關(guān)于類成員函數(shù)指針的問題,起初我并不在意,以為成員函數(shù)指針和普通的函數(shù)指針是一樣的,沒有什么太多需要討論的。當(dāng)我找來相關(guān)書籍查閱了一番以后,突然意識(shí)到我以前對(duì)成員函數(shù)指針的理解太過于幼稚和膚淺了,它即不像我以前認(rèn)為的那樣簡(jiǎn)單,它也不像我以前認(rèn)為的那樣"默默無聞"。強(qiáng)烈的求知欲促使我對(duì)成員函數(shù)進(jìn)行進(jìn)一步的學(xué)習(xí)并有了這篇文章。

            一。理論篇
            在進(jìn)行深入學(xué)習(xí)和分析之前,還是先看看書中是怎么介紹成員函數(shù)的??偨Y(jié)一下類成員函數(shù)指針的內(nèi)容,應(yīng)該包含以下幾個(gè)知識(shí)點(diǎn):
            1。成員函數(shù)指針并不是普通的函數(shù)指針。
            2。編譯器提供了幾個(gè)新的操作符來支持成員函數(shù)指針操作:

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


            3。成員函數(shù)指針是強(qiáng)類型的。

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


            4。由于成員函數(shù)指針并不是真真意義上的指針,所以成員函數(shù)指針的轉(zhuǎn)化就受限制。具體的轉(zhuǎn)化細(xì)節(jié)依賴于不同的編譯器,甚至是同一個(gè)編譯器的不同版本。不過,處于同一個(gè)繼承鏈中的不同類之間override的不同函數(shù)和虛函數(shù)還是可以轉(zhuǎn)化的。

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


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

             

             ”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。成員函數(shù)指針的轉(zhuǎn)化。本文所采用的代碼是想比較普通成員函數(shù)指針和虛函數(shù)指針在轉(zhuǎn)化的過程中存在那些差異:
            對(duì)于符號(hào)”??_9@$B3AE“,我又找到了這樣的匯編代碼: 由此可以看出,對(duì)于虛函數(shù),即使是用過成員函數(shù)指針間接調(diào)用,仍然具有和直接調(diào)用一樣的特性。

             

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

             

            ; PVVBASEMEMFUNC      pVVBaseMemFunc   = &Base::foobar;
            mov    DWORD PTR _pVVBaseMemFunc$[ebp], OFFSET FLAT:??_9@$B3AE ; `vcall'
            取出符號(hào)”??_9@$B3AE“的值,存放于變量pVVBaseMemFunc所占內(nèi)存的前4個(gè)字節(jié)(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
            符號(hào)”??_9@$B3AE“代表的應(yīng)該是一個(gè)存根函數(shù),這個(gè)函數(shù)首先根據(jù)this指針獲得虛函數(shù)表的指針,然后將指令再跳轉(zhuǎn)到相應(yīng)的虛函數(shù)的地址。

             

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

             

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

            由此可以看出,基類的成員函數(shù)指針轉(zhuǎn)化到相應(yīng)的派生類的成員函數(shù)指針,值保持不變。當(dāng)然這里的例子繼承關(guān)系相對(duì)來說比較簡(jiǎn)單,如果存在多繼承和虛繼承的情況下,結(jié)果可能會(huì)復(fù)雜的多。

            3。函數(shù)調(diào)用
            下面的函數(shù)調(diào)用都大同小異,這里是列出其中的一個(gè): 這里的匯編代碼并沒有給我們太多新鮮的內(nèi)容:將對(duì)象的首地址(this指針)存放于寄存器ECX中,接著就將指令轉(zhuǎn)到變量_pVIBaseMemFunc所占內(nèi)存的前4個(gè)字節(jié)所表示的地址。

            到了這里,我們應(yīng)該對(duì)成員函數(shù)指針有了進(jìn)一步的了解。

                ; (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個(gè)字節(jié)。這12個(gè)字節(jié)中應(yīng)該可以包含三個(gè)指針,其中的一個(gè)指針應(yīng)該指向函數(shù)的地址,那另外兩個(gè)指針又指向那里呢?在《C++ Common Knowledge: Essential Intermediate Programming》(中文譯名:

            C++必知必會(huì))這本書的第16章對(duì)這部分的內(nèi)容做了說明,這個(gè)12個(gè)字節(jié)的偏移量正好印證了書中的內(nèi)容:

            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博客,轉(zhuǎn)載請(qǐng)標(biāo)明出處:http://blog.csdn.net/eroswang/archive/2009/05/06/4153356.aspx

            posted @ 2011-04-27 17:14 沛沛 閱讀(388) | 評(píng)論 (0)編輯 收藏

            邏輯地址(Logical Address) 是指由程序產(chǎn)生的與段相關(guān)的偏移地址部分。例如,你在進(jìn)行C語言指針編程中,可以讀取指針變量本身值(&操作),實(shí)際上這個(gè)值就是邏輯地址,它是相對(duì)于你當(dāng)前進(jìn)程數(shù)據(jù)段的地址,不和絕對(duì)物理地址相干。只有在Intel實(shí)模式下,邏輯地址才和物理地址相等(因?yàn)閷?shí)模式?jīng)]有分段或分頁機(jī)制,Cpu不進(jìn)行自動(dòng)地址轉(zhuǎn)換);邏輯也就是在Intel 保護(hù)模式下程序執(zhí)行代碼段限長(zhǎng)內(nèi)的偏移地址(假定代碼段、數(shù)據(jù)段如果完全一樣)。應(yīng)用程序員僅需與邏輯地址打交道,而分段和分頁機(jī)制對(duì)您來說是完全透明的,僅由系統(tǒng)編程人員涉及。應(yīng)用程序員雖然自己可以直接操作內(nèi)存,那也只能在操作系統(tǒng)給你分配的內(nèi)存段操作。

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

            物理地址(Physical Address) 是指出現(xiàn)在CPU外部地址總線上的尋址物理內(nèi)存的地址信號(hào),是地址變換的最終結(jié)果地址。如果啟用了分頁機(jī)制,那么線性地址會(huì)使用頁目錄和頁表中的項(xiàng)變換成物理地址。如果沒有啟用分頁機(jī)制,那么線性地址就直接成為物理地址了。

            虛擬內(nèi)存(Virtual Memory) 是指計(jì)算機(jī)呈現(xiàn)出要比實(shí)際擁有的內(nèi)存大得多的內(nèi)存量。因此它允許程序員編制并運(yùn)行比實(shí)際系統(tǒng)擁有的內(nèi)存大得多的程序。這使得許多大型項(xiàng)目也能夠在具有有限內(nèi)存資源的系統(tǒng)上實(shí)現(xiàn)。一個(gè)很恰當(dāng)?shù)谋扔魇牵耗悴恍枰荛L(zhǎng)的軌道就可以讓一列火車從上海開到北京。你只需要足夠長(zhǎng)的鐵軌(比如說3公里)就可以完成這個(gè)任務(wù)。采取的方法是把后面的鐵軌立刻鋪到火車的前面,只要你的操作足夠快并能滿足要求,列車就能象在一條完整的軌道上運(yùn)行。這也就是虛擬內(nèi)存管理需要完成的任務(wù)。在Linux 0.11內(nèi)核中,給每個(gè)程序(進(jìn)程)都劃分了總?cè)萘繛?4MB的虛擬內(nèi)存空間。因此程序的邏輯地址范圍是0x0000000到0x4000000。

            有時(shí)我們也把邏輯地址稱為虛擬地址。因?yàn)榕c虛擬內(nèi)存空間的概念類似,邏輯地址也是與實(shí)際物理內(nèi)存容量無關(guān)的。
            邏輯地址與物理地址的“差距”是0xC0000000,是由于虛擬地址->線性地址->物理地址映射正好差這個(gè)值。這個(gè)值是由操作系統(tǒng)指定的。

             

            虛擬地址到物理地址的轉(zhuǎn)化方法是與體系結(jié)構(gòu)相關(guān)的。一般來說有分段、分頁兩種方式。以現(xiàn)在的x86 cpu為例,分段分頁都是支持的。Memory Mangement Unit負(fù)責(zé)從虛擬地址到物理地址的轉(zhuǎn)化。邏輯地址是段標(biāo)識(shí)+段內(nèi)偏移量的形式,MMU通過查詢段表,可以把邏輯地址轉(zhuǎn)化為線性地址。如果cpu沒有開啟分頁功能,那么線性地址就是物理地址;如果cpu開啟了分頁功能,MMU還需要查詢頁表來將線性地址轉(zhuǎn)化為物理地址:
            邏輯地址 ----(段表)---> 線性地址 — (頁表)—> 物理地址
            不同的邏輯地址可以映射到同一個(gè)線性地址上;不同的線性地址也可以映射到同一個(gè)物理地址上;所以是多對(duì)一的關(guān)系。另外,同一個(gè)線性地址,在發(fā)生換頁以后,也可能被重新裝載到另外一個(gè)物理地址上。所以這種多對(duì)一的映射關(guān)系也會(huì)隨時(shí)間發(fā)生變化。


            本文來自CSDN博客,轉(zhuǎn)載請(qǐng)標(biāo)明出處:http://blog.csdn.net/leves1989/archive/2008/11/15/3305402.aspx

            posted @ 2011-04-25 14:03 沛沛 閱讀(518) | 評(píng)論 (0)編輯 收藏

            原文標(biāo)題:Cache: a place for concealment and safekeeping

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

             

            [注:本人水平有限,只好挑一些國(guó)外高手的精彩文章翻譯一下。一來自己復(fù)習(xí),二來與大家分享。]

             

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

             

            L1 cache – 32KB,8路組相聯(lián),64字節(jié)緩存線

            1.       由索引揀選緩存組(行)

             

            在cache中的數(shù)據(jù)是以緩存線(line)為單位組織的,一條緩存線對(duì)應(yīng)于內(nèi)存中一個(gè)連續(xù)的字節(jié)塊。這個(gè)cache使用了64字節(jié)的緩存線。這些線被保存在cache bank中,也叫路(way)。每一路都有一個(gè)專門的目錄(directory)用來保存一些登記信息。你可以把每一路連同它的目錄想象成電子表格中的一列,而表的一行構(gòu)成了cache的一組(set)。列中的每一個(gè)單元(cell)都含有一條緩存線,由與之對(duì)應(yīng)的目錄單元跟蹤管理。圖中的cache有64 組、每組8路,因此有512個(gè)含有緩存線的單元,合計(jì)32KB的存儲(chǔ)空間。

             

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

             

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

             

            取而代之的是圖中的組相聯(lián)緩存(set associative cache)。意思是,內(nèi)存中一條給定的緩存線只能被保存在一個(gè)特定的組(或行)中。所以,任意物理內(nèi)存頁的第0條緩存線(頁內(nèi)第0到63字節(jié))必須存儲(chǔ)到第0組,第1條緩存線存儲(chǔ)到第1組,以此類推。每一組有8個(gè)單元可用于存儲(chǔ)它所關(guān)聯(lián)的緩存線(譯注:就是那些需要存儲(chǔ)到這一組的緩存線),從而形成一個(gè)8路關(guān)聯(lián)的組(8-way associative set)。當(dāng)訪問一個(gè)內(nèi)存地址時(shí),地址的第6到11位(譯注:組索引)指出了在4KB內(nèi)存頁中緩存線的編號(hào),從而決定了即將使用的緩存組。舉例來說,物理地址0x800010a0的組索引是000010,所以此地址的內(nèi)容一定是在第2組中緩存的。

             

            但是還有一個(gè)問題,就是要找出一組中哪個(gè)單元包含了想要的信息,如果有的話。這就到了緩存目錄登場(chǎng)的時(shí)刻。每一個(gè)緩存線都被其對(duì)應(yīng)的目錄單元做了標(biāo)記(tag);這個(gè)標(biāo)記就是一個(gè)簡(jiǎn)單的內(nèi)存頁編號(hào),指出緩存線來自于哪一頁。由于處理器可以尋址64GB的物理RAM,所以總共有64GB / 4KB == 224個(gè)內(nèi)存頁,需要24位來保存標(biāo)記。前例中的物理地址0x800010a0對(duì)應(yīng)的頁號(hào)為524,289。下面是故事的后一半:

             


            在組中搜索匹配標(biāo)記

             

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

             

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

             

            一個(gè)內(nèi)存訪問經(jīng)常由一個(gè)線性(或虛擬)地址發(fā)起,所以L1 cache需要依賴分頁單元(paging unit)來求出物理內(nèi)存頁的地址,以便用于緩存標(biāo)記。與此相反,組索引來自于線性地址的低位,所以不需要轉(zhuǎn)換就可以使用了(在我們的例子中為第6到11位)。因此L1 cache是物理標(biāo)記但虛擬索引的(physically tagged but virtually indexed),從而幫助CPU進(jìn)行并行的查找操作。因?yàn)長(zhǎng)1 cache的一路絕不會(huì)比MMU的一頁還大,所以可以保證一個(gè)給定的物理地址位置總是關(guān)聯(lián)到同一組,即使組索引是虛擬的。在另一方面L2 cache必須是物理標(biāo)記和物理索引的,因?yàn)樗囊宦繁萂MU的一頁要大。但是,當(dāng)一個(gè)請(qǐng)求到達(dá)L2 cache時(shí),物理地址已經(jīng)被L1 cache準(zhǔn)備(resolved)完畢了,所以L2 cache會(huì)工作得很好。

             

            最后,目錄單元還存儲(chǔ)了對(duì)應(yīng)緩存線的狀態(tài)(state)。在L1代碼緩存中的一條緩存線要么是無效的(invalid)要么是共享的(shared,意思是有效的,真的J)。在L1數(shù)據(jù)緩存和L2緩存中,一條緩存線可以為4個(gè)MESI狀態(tài)之一:被修改的(modified),獨(dú)占的(exclusive),共享的(shared),無效的(invalid)。Intel緩存是包容式的(inclusive):L1緩存的內(nèi)容會(huì)被復(fù)制到L2緩存中。在下一篇討論線程(threading),鎖定(locking)等內(nèi)容的文章中,這些緩存線狀態(tài)將發(fā)揮作用。下一次,我們將看看前端總線以及內(nèi)存訪問到底是怎么工作的。這將成為一個(gè)內(nèi)存研討周。

             

            (在回復(fù)中Dave提到了直接映射緩存(direct-mapped cache)。它們基本上是一種特殊的組相聯(lián)緩存,只是只有一路而已。在各種折中方案中,它與全相聯(lián)緩存正好相反:訪問非??旖?,但因組沖突而導(dǎo)致的緩存缺失也非常多。)

             

            [譯者小結(jié):

             

            1.         內(nèi)存層次結(jié)構(gòu)的意義在于利用引用的空間局部性和時(shí)間局部性原理,將經(jīng)常被訪問的數(shù)據(jù)放到快速的存儲(chǔ)器中,而將不經(jīng)常訪問的數(shù)據(jù)留在較慢的存儲(chǔ)器中。

            2.         一般情況下,除了寄存器和L1緩存可以操作指定字長(zhǎng)的數(shù)據(jù),下層的內(nèi)存子系統(tǒng)就不會(huì)再使用這么小的單位了,而是直接移動(dòng)數(shù)據(jù)塊,比如以緩存線為單位訪問數(shù)據(jù)。

            3.         對(duì)于組沖突,可以這么理解:與上文相似,假設(shè)一個(gè)緩存,由512條緩存線組成,每條線64字節(jié),容量32KB。

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

            b)        如果是全相聯(lián)緩存,那么每條緩存線都是獨(dú)立的,可以對(duì)應(yīng)于內(nèi)存中的任意緩存線。只有當(dāng)所有的512條緩存線都被占滿后才會(huì)出現(xiàn)沖突。

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

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

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

            ]

             

            本文來自CSDN博客,轉(zhuǎn)載請(qǐng)標(biāo)明出處:http://blog.csdn.net/drshenlei/archive/2009/06/17/4277959.aspx

            posted @ 2011-04-25 14:01 沛沛 閱讀(1305) | 評(píng)論 (1)編輯 收藏

            我們經(jīng)常會(huì)發(fā)現(xiàn)有兩種內(nèi)存轉(zhuǎn)儲(chǔ)(core dump)  
              一種是段故障(segment fault)通常是在一個(gè)非法的地址上進(jìn)行取值賦值操作造成。  
              一種是總線錯(cuò)誤(bus error)通常是指針強(qiáng)制轉(zhuǎn)換,導(dǎo)致CPU讀取數(shù)據(jù)違反了一定的總線規(guī)則。

            首先,core就是內(nèi)存的意思,在半導(dǎo)體應(yīng)用之前,內(nèi)存是由鐵氧化物圓環(huán)制造的(core),但一直沿用至今。

            而這兩種錯(cuò)誤,都是有硬件告知操作系統(tǒng)一個(gè)有問題的內(nèi)存引用。操作系統(tǒng)通過信號(hào),再將錯(cuò)誤信息告知進(jìn)程。缺省情況下,進(jìn)程收到“總線錯(cuò)誤”或“段錯(cuò)誤”信號(hào)后,將信息轉(zhuǎn)儲(chǔ)并終止。當(dāng)然也可以為這些信號(hào)設(shè)置一個(gè)信號(hào)處理程序(signal handler)。

            總線錯(cuò)誤(bus error),幾乎都是有內(nèi)存未對(duì)齊讀引起的。內(nèi)存對(duì)齊,就是內(nèi)存變量的地址只能是其大小的整數(shù)倍,這樣存儲(chǔ)的目的就是為了方便并快速存取內(nèi)存。一般情況下,編譯器都會(huì)做好內(nèi)存對(duì)齊工作,為什么又會(huì)引發(fā)段故障呢?很多情況就是由指針和強(qiáng)制類型轉(zhuǎn)換引起的,如:

            union{

                char a[10];

                int i;

            }u;

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

            *p = 17;

            當(dāng)然,還有一些其它原因會(huì)引起“總線錯(cuò)誤”,如奇偶校驗(yàn)碼錯(cuò)誤,所引用的內(nèi)存塊不存在。但是現(xiàn)在,內(nèi)存都有硬件電路檢測(cè)和修正,一般不會(huì)再傳到軟件層了;除了驅(qū)動(dòng)程序,一般也不會(huì)引用不存在的內(nèi)存塊。

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

            段錯(cuò)誤一般是由硬件段表轉(zhuǎn)換機(jī)構(gòu)的錯(cuò)誤引發(fā),如Sun硬件中的內(nèi)存管理單元(MMU)。

            還有一個(gè)微妙之處是,如果未初始化的指針恰好具有未對(duì)齊的值,它將產(chǎn)生總線錯(cuò)誤,而不是段錯(cuò)誤。

            posted @ 2011-04-25 14:00 沛沛 閱讀(5994) | 評(píng)論 (0)編輯 收藏

             void error(int severity...)
            {
               va_list ap;
               va_start(ap,severity);
               for(;;)
               {
                  char* p=va_arg(ap,char*);
                  if(p==0) break;
                  cerr<<p<<' ';
               }
               va_end(ap);
               cerr<<'\n';
               if(severity) exit(severity);
            }
                首先,通過調(diào)用va_start定義并初始化一個(gè)va_list,宏va_start以一個(gè)va_list的名字和函數(shù)的最后一個(gè)有名形參的名字作為參數(shù)。宏va_arg用戶按順序取出各個(gè)無名參數(shù)。在每次調(diào)用va_arg時(shí),程序員都必須提供一個(gè)類型,va_arg假定這就是被傳遞的實(shí)際參數(shù)的類型,但一般說它并沒有辦法保證這一點(diǎn)。從一個(gè)使用過va_start的函數(shù)退出之前,必須調(diào)用一次va_end,這是因?yàn)関a_start可能以某種形式修改了堆棧,這種修改可能導(dǎo)致返回?zé)o法完成,va_end能將有關(guān)的修改復(fù)原。
            posted @ 2011-04-14 22:39 沛沛 閱讀(221) | 評(píng)論 (0)編輯 收藏

             new有三種使用方式:plain new,nothrow new和placement new。
            (1)plain new顧名思義就是普通的new,就是我們慣常使用的new。在C++中是這樣定義的:
                void* operator new(std::size_t) throw(std::bad_alloc);
                void operator delete(void *) throw();
            提示:plain new在分配失敗的情況下,拋出異常std::bad_alloc而不是返回NULL,因此通過判斷返回值是否為NULL是徒勞的。
            (2)nothrow new是不拋出異常的運(yùn)算符new的形式。nothrow new在失敗時(shí),返回NULL。定義如下:
                void * operator new(std::size_t,const std::nothrow_t&) throw();
                void operator delete(void*) throw();
            (3)placement new意即“放置”,這種new允許在一塊已經(jīng)分配成功的內(nèi)存上重新構(gòu)造對(duì)象或?qū)ο髷?shù)組。placement new不用擔(dān)心內(nèi)存分配失敗,因?yàn)樗静环峙鋬?nèi)存,它做的唯一一件事情就是調(diào)用對(duì)象的構(gòu)造函數(shù)。定義如下:
                void* operator new(size_t,void*);
                void operator delete(void*,void*);
            提示1:palcement new的主要用途就是反復(fù)使用一塊較大的動(dòng)態(tài)分配的內(nèi)存來構(gòu)造不同類型的對(duì)象或者他們的數(shù)組。
            提示2:placement new構(gòu)造起來的對(duì)象或其數(shù)組,要顯示的調(diào)用他們的析構(gòu)函數(shù)來銷毀,千萬不要使用delete。
            char* p = new(nothrow) char[100];
            long *q1 = new(p) long(100);
            int *q2 = new(p) int[100/sizeof(int)];
            posted @ 2011-04-14 22:38 沛沛 閱讀(309) | 評(píng)論 (0)編輯 收藏

                 摘要: 摘要: 多線程同步技術(shù)是計(jì)算機(jī)軟件開發(fā)的重要技術(shù),本文對(duì)多線程的各種同步技術(shù)的原理和實(shí)現(xiàn)進(jìn)行了初步探討?! £P(guān)鍵詞: VC++6.0; 線程同步;臨界區(qū);事件;互斥;信號(hào)量;   閱讀目錄:   使線程同步   臨界區(qū)  管理事件內(nèi)核對(duì)象   信號(hào)量?jī)?nèi)核對(duì)象  互斥內(nèi)核對(duì)象   小結(jié)   正文   使線程同步  在程序中使用多線程時(shí),一般很少有多個(gè)線程能在其生命期內(nèi)進(jìn)行完全獨(dú)立的操作。更多的情...  閱讀全文
            posted @ 2011-04-14 22:36 沛沛 閱讀(427) | 評(píng)論 (1)編輯 收藏

            [源] :http://hi.baidu.com/firebird/blog/item/f592b3193a02814542a9adeb.html

                 一:select模型
                二:WSAAsyncSelect模型
                三:WSAEventSelect模型
                四:Overlapped I/O 事件通知模型
                五:Overlapped I/O 完成例程模型
                六:IOCP模型


            原文名:《基于Delphi的Socket I/O模型全接觸 》
            老陳有一個(gè)在外地工作的女兒,不能經(jīng)?;貋?,老陳和她通過信件聯(lián)系。他們的信會(huì)被郵遞員投遞到他們的信箱里。 

            這和Socket模型非常類似。下面我就以老陳接收信件為例講解Socket I/O模型。 

            一:select模型 

            老陳非常想看到女兒的信。以至于他每隔10分鐘就下樓檢查信箱,看是否有女兒的信,在這種情況下,“下樓檢查信箱”然后回到樓上耽誤了老陳太多的時(shí)間,以至于老陳無法做其他工作。 

            select模型和老陳的這種情況非常相似:周而復(fù)始地去檢查......如果有數(shù)據(jù)......接收/發(fā)送....... 

            使用線程來select應(yīng)該是通用的做法: 

            procedure TListenThread.Execute; 
            var 
              addr : TSockAddrIn; 
              fd_read : TFDSet; 
              timeout : TTimeVal; 
              ASock, 
              MainSock : TSocket; 
              len, i : Integer; 
            begin 
              MainSock := socket( AF_INET, SOCK_STREAM, IPPROTO_TCP ); 
              addr.sin_family := AF_INET; 
              addr.sin_port := htons(5678); 
              addr.sin_addr.S_addr := htonl(INADDR_ANY); 
              bind( MainSock, @addr, sizeof(addr) ); 
              listen( MainSock, 5 ); 

              while (not Terminated) do 
              begin 
               FD_ZERO( fd_read ); 
               FD_SET( MainSock, fd_read ); 
               timeout.tv_sec := 0; 
               timeout.tv_usec := 500; 
               if select( 0, @fd_read, nil, nil, @timeout ) > 0 then //至少有1個(gè)等待Accept的connection 
               begin 
                if FD_ISSET( MainSock, fd_read ) then 
                begin 
                for i:=0 to fd_read.fd_count-1 do //注意,fd_count <= 64,
               也就是說select只能同時(shí)管理最多64個(gè)連接 
                begin 
                 len := sizeof(addr); 
                 ASock := accept( MainSock, addr, len ); 
                 if ASock <> INVALID_SOCKET then 
                  ....//為ASock創(chuàng)建一個(gè)新的線程,在新的線程中再不停地select 
                 end; 
                end;    
               end; 
              end; //while (not self.Terminated) 

              shutdown( MainSock, SD_BOTH ); 
              closesocket( MainSock ); 
            end;
             


            二:WSAAsyncSelect模型 

            后來,老陳使用了微軟公司的新式信箱。這種信箱非常先進(jìn),一旦信箱里有新的信件,蓋茨就會(huì)給老陳打電話:喂,大爺,你有新的信件了!從此,老陳再也不必頻繁上下樓檢查信箱了,牙也不疼了,你瞅準(zhǔn)了,藍(lán)天......不是,微軟...... 

            微軟提供的WSAAsyncSelect模型就是這個(gè)意思。 

            WSAAsyncSelect模型是Windows下最簡(jiǎn)單易用的一種Socket I/O模型。使用這種模型時(shí),Windows會(huì)把網(wǎng)絡(luò)事件以消息的形勢(shì)通知應(yīng)用程序。 

            首先定義一個(gè)消息標(biāo)示常量: 

            const WM_SOCKET = WM_USER + 55;
             


            再在主Form的private域添加一個(gè)處理此消息的函數(shù)聲明: 

            private 
            procedure WMSocket(var Msg: TMessage); message WM_SOCKET;
             
              

            然后就可以使用WSAAsyncSelect了: 

            var 
              addr : TSockAddr; 
              sock : TSocket; 

              sock := socket( AF_INET, SOCK_STREAM, IPPROTO_TCP ); 
              addr.sin_family := AF_INET; 
              addr.sin_port := htons(5678); 
              addr.sin_addr.S_addr := htonl(INADDR_ANY); 
              bind( m_sock, @addr, sizeof(SOCKADDR) ); 

              WSAAsyncSelect( m_sock, Handle, WM_SOCKET, FD_ACCEPT or FD_CLOSE ); 

              listen( m_sock, 5 ); 
              ....
             


            應(yīng)用程序可以對(duì)收到WM_SOCKET消息進(jìn)行分析,判斷是哪一個(gè)socket產(chǎn)生了網(wǎng)絡(luò)事件以及事件類型: 

            procedure TfmMain.WMSocket(var Msg: TMessage); 
            var 
              sock : TSocket; 
              addr : TSockAddrIn; 
              addrlen : Integer; 
              buf : Array [0..4095] of Char; 
            begin 
              //Msg的WParam是產(chǎn)生了網(wǎng)絡(luò)事件的socket句柄,LParam則包含了事件類型 
              case WSAGetSelectEvent( Msg.LParam ) of 
              FD_ACCEPT : 
               begin 
                addrlen := sizeof(addr); 
                sock := accept( Msg.WParam, addr, addrlen ); 
                if sock <> INVALID_SOCKET then 
                 WSAAsyncSelect( sock, Handle, WM_SOCKET, FD_READ or FD_WRITE or FD_CLOSE ); 
               end; 

               FD_CLOSE : closesocket( Msg.WParam ); 
               FD_READ : recv( Msg.WParam, buf[0], 4096, 0 ); 
               FD_WRITE : ; 
              end; 
            end;
             


            三:WSAEventSelect模型 

            后來,微軟的信箱非常暢銷,購買微軟信箱的人以百萬計(jì)數(shù)......以至于蓋茨每天24小時(shí)給客戶打電話,累得腰酸背痛,喝蟻力神都不好使。微軟改進(jìn)了他們的信箱:在客戶的家中添加一個(gè)附加裝置,這個(gè)裝置會(huì)監(jiān)視客戶的信箱,每當(dāng)新的信件來臨,此裝置會(huì)發(fā)出“新信件到達(dá)”聲,提醒老陳去收信。蓋茨終于可以睡覺了。 

            同樣要使用線程: 

            procedure TListenThread.Execute; 
            var 
              hEvent : WSAEvent; 
              ret : Integer; 
              ne : TWSANetworkEvents; 
              sock : TSocket; 
              adr : TSockAddrIn; 
              sMsg : String; 
              Index, 
              EventTotal : DWORD; 
              EventArray : Array [0..WSA_MAXIMUM_WAIT_EVENTS-1] of WSAEVENT; 
            begin 
              ...socket...bind... 
              hEvent := WSACreateEvent(); 
              WSAEventSelect( ListenSock, hEvent, FD_ACCEPT or FD_CLOSE ); 
              ...listen... 

              while ( not Terminated ) do 
              begin 
               Index := WSAWaitForMultipleEvents( EventTotal, @EventArray[0], FALSE, 
              WSA_INFINITE, FALSE ); 
               FillChar( ne, sizeof(ne), 0 ); 
               WSAEnumNetworkEvents( SockArray[Index-WSA_WAIT_EVENT_0], 
                EventArray
              [Index-WSA_WAIT_EVENT_0], @ne ); 

               if ( ne.lNetworkEvents and FD_ACCEPT ) > 0 then 
               begin 
                if ne.iErrorCode[FD_ACCEPT_BIT] <> 0 then 
                 continue; 

                ret := sizeof(adr); 
                sock := accept( SockArray[Index-WSA_WAIT_EVENT_0], adr, ret ); 
                if EventTotal > WSA_MAXIMUM_WAIT_EVENTS-1 then
                  //這里WSA_MAXIMUM_WAIT_EVENTS同樣是64 
                begin 
                 closesocket( sock ); 
                 continue; 
                end; 

                hEvent := WSACreateEvent(); 
                WSAEventSelect( sock, hEvent, FD_READ or FD_WRITE or FD_CLOSE ); 
                SockArray[EventTotal] := sock; 
                EventArray[EventTotal] := hEvent; 
                Inc( EventTotal ); 
               end; 

               if ( ne.lNetworkEvents and FD_READ ) > 0 then 
               begin 
                if ne.iErrorCode[FD_READ_BIT] <> 0 then 
                 continue; 
                 FillChar( RecvBuf[0], PACK_SIZE_RECEIVE, 0 ); 
                 ret := recv( SockArray[Index-WSA_WAIT_EVENT_0], RecvBuf[0], 
                PACK_SIZE_RECEIVE, 0 ); 
                 ...... 
                end; 
               end; 
            end;
             



            四:Overlapped I/O 事件通知模型 

            后來,微軟通過調(diào)查發(fā)現(xiàn),老陳不喜歡上下樓收發(fā)信件,因?yàn)樯舷聵瞧鋵?shí)很浪費(fèi)時(shí)間。于是微軟再次改進(jìn)他們的信箱。新式的信箱采用了更為先進(jìn)的技術(shù),只要用戶告訴微軟自己的家在幾樓幾號(hào),新式信箱會(huì)把信件直接傳送到用戶的家中,然后告訴用戶,你的信件已經(jīng)放到你的家中了!老陳很高興,因?yàn)樗槐卦儆H自收發(fā)信件了! 

            Overlapped I/O 事件通知模型和WSAEventSelect模型在實(shí)現(xiàn)上非常相似,主要區(qū)別在"Overlapped”,Overlapped模型是讓應(yīng)用程序使用重疊數(shù)據(jù)結(jié)構(gòu)(WSAOVERLAPPED),一次投遞一個(gè)或多個(gè)Winsock I/O請(qǐng)求。這些提交的請(qǐng)求完成后,應(yīng)用程序會(huì)收到通知。什么意思呢?就是說,如果你想從socket上接收數(shù)據(jù),只需要告訴系統(tǒng),由系統(tǒng)為你接收數(shù)據(jù),而你需要做的只是為系統(tǒng)提供一個(gè)緩沖區(qū)~~~~~ 

            Listen線程和WSAEventSelect模型一模一樣,Recv/Send線程則完全不同: 

            procedure TOverlapThread.Execute; 
            var 
              dwTemp : DWORD; 
              ret : Integer; 
              Index : DWORD; 
            begin 
              ...... 

              while ( not Terminated ) do 
              begin 
               Index := WSAWaitForMultipleEvents
               ( FLinks.Count, @FLinks.Events[0], FALSE, 
                RECV_TIME_OUT, FALSE ); 
               Dec( Index, WSA_WAIT_EVENT_0 ); 
               if Index > WSA_MAXIMUM_WAIT_EVENTS-1 then 
                //超時(shí)或者其他錯(cuò)誤 
                continue; 

               WSAResetEvent
               ( FLinks.Events[Index] ); 
               WSAGetOverlappedResult( FLinks.Sockets[Index], 
                  FLinks.pOverlaps[Index], @dwTemp, FALSE,FLinks.
                 pdwFlags[Index]^ ); 

               if dwTemp = 0 then //連接已經(jīng)關(guān)閉 
               begin 
                ...... 
                continue; 
               end else 
              begin 
               fmMain.ListBox1.Items.Add( FLinks.pBufs[Index]^.buf ); 
              end; 

              //初始化緩沖區(qū) 
              FLinks.pdwFlags[Index]^ := 0; 
              FillChar( FLinks.pOverlaps[Index]^, 
                sizeof(WSAOVERLAPPED), 0 ); 
              FLinks.pOverlaps[Index]^.
               hEvent := FLinks.Events[Index]; 
              FillChar( FLinks.pBufs[Index]^.buf^, 
               BUFFER_SIZE, 0 ); 

              //遞一個(gè)接收數(shù)據(jù)請(qǐng)求 
              WSARecv( FLinks.Sockets[Index], FLinks.pBufs[Index], 1,
                   FLinks.pdwRecvd[Index]^, FLinks.pdwFlags[Index]^, 
                  FLinks.pOverlaps[Index], nil ); 
            end; 
            end;
             


            五:Overlapped I/O 完成例程模型 

            老陳接收到新的信件后,一般的程序是:打開信封----掏出信紙----閱讀信件----回復(fù)信件......為了進(jìn)一步減輕用戶負(fù)擔(dān),微軟又開發(fā)了一種新的技術(shù):用戶只要告訴微軟對(duì)信件的操作步驟,微軟信箱將按照這些步驟去處理信件,不再需要用戶親自拆信/閱讀/回復(fù)了!老陳終于過上了小資生活! 

            Overlapped I/O 完成例程要求用戶提供一個(gè)回調(diào)函數(shù),發(fā)生新的網(wǎng)絡(luò)事件的時(shí)候系統(tǒng)將執(zhí)行這個(gè)函數(shù): 

            procedure WorkerRoutine( const dwError, cbTransferred : DWORD; 
            const 
            lpOverlapped : LPWSAOVERLAPPED; const dwFlags : DWORD ); stdcall;
             


            然后告訴系統(tǒng)用WorkerRoutine函數(shù)處理接收到的數(shù)據(jù): 

            WSARecv( m_socket, @FBuf, 1, dwTemp, dwFlag, @m_overlap, WorkerRoutine ); 
               然后......沒有什么然后了,系統(tǒng)什么都給你做了!微軟真實(shí)體貼! 

            while ( not Terminated ) do//這就是一個(gè)Recv/Send線程要做的事情......什么都不用做?。。?! 
            begin 
              if SleepEx( RECV_TIME_OUT, True ) = WAIT_IO_COMPLETION then // 
              begin 
               ; 
              end else 
              begin 
               continue; 
              end; 
            end;
             


            六:IOCP模型 

            微軟信箱似乎很完美,老陳也很滿意。但是在一些大公司情況卻完全不同!這些大公司有數(shù)以萬計(jì)的信箱,每秒鐘都有數(shù)以百計(jì)的信件需要處理,以至于微軟信箱經(jīng)常因超負(fù)荷運(yùn)轉(zhuǎn)而崩潰!需要重新啟動(dòng)!微軟不得不使出殺手锏...... 

            微軟給每個(gè)大公司派了一名名叫“Completion Port”的超級(jí)機(jī)器人,讓這個(gè)機(jī)器人去處理那些信件! 

            “Windows NT小組注意到這些應(yīng)用程序的性能沒有預(yù)料的那么高。特別的,處理很多同時(shí)的客戶請(qǐng)求意味著很多線程并發(fā)地運(yùn)行在系統(tǒng)中。因?yàn)樗羞@些線程都是可運(yùn)行的[沒有被掛起和等待發(fā)生什么事],Microsoft意識(shí)到NT內(nèi)核花費(fèi)了太多的時(shí)間來轉(zhuǎn)換運(yùn)行線程的上下文[Context],線程就沒有得到很多CPU時(shí)間來做它們的工作。大家可能也都感覺到并行模型的瓶頸在于它為每一個(gè)客戶請(qǐng)求都創(chuàng)建了一個(gè)新線程。創(chuàng)建線程比起創(chuàng)建進(jìn)程開銷要小,但也遠(yuǎn)不是沒有開銷的。我們不妨設(shè)想一下:如果事先開好N個(gè)線程,讓它們?cè)谀莌old[堵塞],然后可以將所有用戶的請(qǐng)求都投遞到一個(gè)消息隊(duì)列中去。然后那N個(gè)線程逐一從消息隊(duì)列中去取出消息并加以處理。就可以避免針對(duì)每一個(gè)用戶請(qǐng)求都開線程。不僅減少了線程的資源,也提高了線程的利用率。理論上很不錯(cuò),你想我等泛泛之輩都能想出來的問題,Microsoft又怎會(huì)沒有考慮到呢?”-----摘自nonocast的《理解I/O Completion Port》 

            先看一下IOCP模型的實(shí)現(xiàn): 

            //創(chuàng)建一個(gè)完成端口 
            FCompletPort := CreateIoCompletionPort( INVALID_HANDLE_VALUE, 0,0,0 ); 

            //接受遠(yuǎn)程連接,并把這個(gè)連接的socket句柄綁定到剛才創(chuàng)建的IOCP上 
            AConnect := accept( FListenSock, addr, len); 
            CreateIoCompletionPort( AConnect, FCompletPort, nil, 0 ); 

            //創(chuàng)建CPU數(shù)*2 + 2個(gè)線程 
            for i:=1 to si.dwNumberOfProcessors*2+2 do 
            begin 
              AThread := TRecvSendThread.Create( false ); 
              AThread.CompletPort := FCompletPort;//告訴這個(gè)線程,你要去這個(gè)IOCP去訪問數(shù)據(jù) 
            end;
             


            就這么簡(jiǎn)單,我們要做的就是建立一個(gè)IOCP,把遠(yuǎn)程連接的socket句柄綁定到剛才創(chuàng)建的IOCP上,最后創(chuàng)建n個(gè)線程,并告訴這n個(gè)線程到這個(gè)IOCP上去訪問數(shù)據(jù)就可以了。 

            再看一下TRecvSendThread線程都干些什么: 

            procedure TRecvSendThread.Execute; 
            var 
              ...... 
            begin 
              while (not self.Terminated) do 
              begin 
               //查詢IOCP狀態(tài)(數(shù)據(jù)讀寫操作是否完成) 
               GetQueuedCompletionStatus( CompletPort, BytesTransd, 
                CompletKey, POVERLAPPED(pPerIoDat), TIME_OUT ); 

               if BytesTransd <> 0 then 
                ....;//數(shù)據(jù)讀寫操作完成 
               
                //再投遞一個(gè)讀數(shù)據(jù)請(qǐng)求 
                WSARecv( CompletKey, @(pPerIoDat^.BufData), 1, 
                BytesRecv, Flags, @(pPerIoDat^.Overlap), nil ); 
               end; 
            end;
             


            讀寫線程只是簡(jiǎn)單地檢查IOCP是否完成了我們投遞的讀寫操作,如果完成了則再投遞一個(gè)新的讀寫請(qǐng)求。 

            應(yīng)該注意到,我們創(chuàng)建的所有TRecvSendThread都在訪問同一個(gè)IOCP(因?yàn)槲覀冎粍?chuàng)建了一個(gè)IOCP),并且我們沒有使用臨界區(qū)!難道不會(huì)產(chǎn)生沖突嗎?不用考慮同步問題嗎? 

            這正是IOCP的奧妙所在。IOCP不是一個(gè)普通的對(duì)象,不需要考慮線程安全問題。它會(huì)自動(dòng)調(diào)配訪問它的線程:如果某個(gè)socket上有一個(gè)線程A正在訪問,那么線程B的訪問請(qǐng)求會(huì)被分配到另外一個(gè)socket。這一切都是由系統(tǒng)自動(dòng)調(diào)配的,我們無需過問。
            posted @ 2011-04-14 22:33 沛沛 閱讀(318) | 評(píng)論 (0)編輯 收藏

            遺傳算法

            遺傳算法(Genetic Algorithm, GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想,它借用了仿真生物遺傳學(xué)和自然選擇機(jī)理,通過自然選擇、遺傳、變異等作用機(jī)制,實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。從某種程度上說遺傳算法是對(duì)生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。

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

            遺傳算法已用于求解帶有應(yīng)用前景的一些問題,例如遺傳程序設(shè)計(jì)、函數(shù)優(yōu)化、排序問題、人工神經(jīng)網(wǎng)絡(luò)、分類系統(tǒng)、計(jì)算機(jī)圖像處理和機(jī)器人運(yùn)動(dòng)規(guī)劃等。

            術(shù)語說明

            由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法,所以在這個(gè)算法中會(huì)用到很多生物遺傳學(xué)知識(shí),下面是我們將會(huì)用來的一些術(shù)語說明:

            一、染色體(Chronmosome)

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

            二、基因(Gene)

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

            三、基因地點(diǎn)(Locus)

            基因地點(diǎn)在算法中表示一個(gè)基因在串中的位置稱為基因位置(Gene Position),有時(shí)也簡(jiǎn)稱基因位?;蛭恢糜纱淖笙蛴矣?jì)算,例如在串 S=1101 中,0的基因位置是3。

            四、基因特征值(Gene Feature)

            在用串表示整數(shù)時(shí),基因的特征值與二進(jìn)制數(shù)的權(quán)一致;例如在串 S=1011 中,基因位置3中的1,它的基因特征值為2;基因位置1中的1,它的基因特征值為8。

            五、適應(yīng)度(Fitness)

            各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力,引入了對(duì)問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù),叫適應(yīng)度函數(shù). 這個(gè)函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。

            操作算法

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

            1.選擇(selection)

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


            圖1. 輪盤賭模型
             
            Fitness 值: 2200 1800 1200 950 400 100
            選擇概率: 3331 0.271 0.18 0.143 0.06 0.015
             

            2.交叉(Crossover)

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

            單點(diǎn)交叉操作的簡(jiǎn)單方式是將被選擇出的兩個(gè)個(gè)體S1和S2作為父母?jìng)€(gè)體,將兩者的部分基因碼值進(jìn)行交換。假設(shè)如下兩個(gè)8位的個(gè)體:

            S1 1000  1111 S2 1110  1100

            產(chǎn)生一個(gè)在1到7之間的隨機(jī)數(shù)c,假如現(xiàn)在產(chǎn)生的是2,將S1和S2的低二位交換:S1的高六位與S2的低六位組成數(shù)串10001100,這就是S1和S2 的一個(gè)后代P1個(gè)體;S2的高六位與S1的低二位組成數(shù)串11101111,這就是S1和S2的一個(gè)后代P2個(gè)體。其交換過程如下圖所示:

            Crossover 11110000 Crossover 11110000
            S1 1000 1111 S2 1110 1100
            P1 1000 1100 P2 1110 1111

            3.變異(Mutation)

            這是在選中的個(gè)體中,將新個(gè)體的基因鏈的各位按概率pm進(jìn)行異向轉(zhuǎn)化,最簡(jiǎn)單方式是改變串上某個(gè)位置數(shù)值。對(duì)二進(jìn)制編碼來說將0與1互換:0變異為1,1變異為0。

            如下8位二進(jìn)制編碼:

            1 1 1 0 1 1 0 0

            隨機(jī)產(chǎn)生一個(gè)1至8之間的數(shù)i,假如現(xiàn)在k=6,對(duì)從右往左的第6位進(jìn)行變異操作,將原來的1變?yōu)?,得到如下串:

            1 1 0 0 1 1 0 0

            整個(gè)交叉變異過程如下圖:


            圖2. 交叉變異過程

             

            4.精英主義 (Elitism)

            僅僅從產(chǎn)生的子代中選擇基因去構(gòu)造新的種群可能會(huì)丟失掉上一代種群中的很多信息。也就是說當(dāng)利用交叉和變異產(chǎn)生新的一代時(shí),我們有很大的可能把在某個(gè)中間步驟中得到的最優(yōu)解丟失。在此我們使用精英主義(Elitism)方法,在每一次產(chǎn)生新的一代時(shí),我們首先把當(dāng)前最優(yōu)解原封不動(dòng)的復(fù)制到新的一代中,其他步驟不變。這樣任何時(shí)刻產(chǎn)生的一個(gè)最優(yōu)解都可以存活到遺傳算法結(jié)束。

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

            遺傳算法的所需參數(shù)

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

            Fitness函數(shù):見上文介紹。

            Fitnessthreshold(適應(yīng)度閥值):適合度中的設(shè)定的閥值,當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值,或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)(變化率為零),則算法的迭代過程收斂、算法結(jié)束。否則,用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體,并返回到選擇操作處繼續(xù)循環(huán)執(zhí)行。

            P:種群的染色體總數(shù)叫種群規(guī)模,它對(duì)算法的效率有明顯的影響,其長(zhǎng)度等于它包含的個(gè)體數(shù)量。太小時(shí)難以求出最優(yōu)解,太大則增長(zhǎng)收斂時(shí)間導(dǎo)致程序運(yùn)行時(shí)間長(zhǎng)。對(duì)不同的問題可能有各自適合的種群規(guī)模,通常種群規(guī)模為 30 至 160。

            pc:在循環(huán)中進(jìn)行交叉操作所用到的概率。交叉概率(Pc)一般取0.6至0.95之間的值,Pc太小時(shí)難以向前搜索,太大則容易破壞高適應(yīng)值的結(jié)構(gòu)。

            Pm:變異概率,從個(gè)體群中產(chǎn)生變異的概率,變異概率一般取0.01至0.03之間的值變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu),太大使遺傳算法成了單純的隨機(jī)搜索。

            另一個(gè)系統(tǒng)參數(shù)是個(gè)體的長(zhǎng)度,有定長(zhǎng)和變長(zhǎng)兩種。它對(duì)算法的性能也有影響。由于GA是一個(gè)概率過程,所以每次迭代的情況是不一樣的,系統(tǒng)參數(shù)不同,迭代情況也不同。

            遺傳步驟

            了解了上面的基本參數(shù),下面我們來看看遺傳算法的基本步驟。

            基本過程為:

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

            程序的停止條件最簡(jiǎn)單的有如下二種:完成了預(yù)先給定的進(jìn)化代數(shù)則停止;種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。

            根據(jù)遺傳算法思想可以畫出如右圖所示的簡(jiǎn)單遺傳算法框圖:


            圖3. 簡(jiǎn)單遺傳算法框圖
             

            下面?zhèn)未a簡(jiǎn)單說明了遺傳算法操作過程:

            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 說明

            能有效實(shí)現(xiàn)遺傳算法的應(yīng)用例子有很多,像西洋雙陸棋、國(guó)際名模等等都是遺傳程序設(shè)計(jì)學(xué)習(xí)的工具,但是 Robocode 有著其他幾個(gè)無可比擬的優(yōu)勢(shì):

            1. 它是基于面向?qū)ο笳Z言 Java 開發(fā),而遺傳算法本身的思想也是存在繼承等面向?qū)ο蟾拍睿?
            2. Robocode 是一種基于游戲與編程語言之間的平臺(tái),有一個(gè)充滿競(jìng)技與樂趣的坦克戰(zhàn)斗平臺(tái),你能很快的通過與其他坦克機(jī)器比賽而測(cè)試自己的遺傳算法;
            3. Robocode 社群有 4000 個(gè)左右各種策略的例子機(jī)器人可供你選擇,這些機(jī)器人足以讓我們模擬真實(shí)的遺傳環(huán)境。而且很多代碼可直接開放源代碼供我們借鑒 ;
            4. Robocode 是一個(gè)開源軟件,你可直接上Robocode控制器上加入自己的遺傳特點(diǎn),而加快遺傳過程的收斂時(shí)間;
            5. Robocoe 是一個(gè)很容易使用的機(jī)器人戰(zhàn)斗仿真器,您在此平臺(tái)上創(chuàng)建自己的坦克機(jī)器人,并與其它開發(fā)者開發(fā)的機(jī)器人競(jìng)技。以得分排名的方式判定優(yōu)勝者。每個(gè) Robocode 參加者都要利用 Java 語言元素創(chuàng)建他或她的機(jī)器人,這樣就使從初學(xué)者到高級(jí)黑客的廣大開發(fā)者都可以參與這一娛樂活動(dòng)。如果您對(duì)Robocode不是很了解,請(qǐng)參考 developerWorks 網(wǎng)站 Java 技術(shù)專區(qū)文章:“重錘痛擊 Robocode”;

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








            預(yù)設(shè)策略進(jìn)化機(jī)器人

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

            MS BPS RS TS
            random distance-based always-turn HeadOn
            Linear light-fast target-focus Linear
            circular Powerful-slow target-scope-focus Circular
            Perpendicular Medium   nearest robot
            arbitary hit-rate based   Log
            anti gravity     Statistic
            Stop     Angular
            Bullet avoid     wave
            wall avoid      
            track      
            Oscillators      

            下面是基本移動(dòng)策略的說明:

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

            瞄準(zhǔn)策略說明如下:

            • Headon:正對(duì)瞄準(zhǔn)
            • Linear:直線瞄準(zhǔn)
            • circular:圓周瞄準(zhǔn)
            • nearest robot:接近機(jī)器人瞄準(zhǔn)
            • Log:保存每次開火記錄
            • Statistic:統(tǒng)計(jì)學(xué)瞄準(zhǔn),分析所有打中及未打中的次數(shù),以其中找出最高打中敵人的概率為準(zhǔn)則
            • Angular:找到最佳角度瞄準(zhǔn)
            • Wave:波形瞄準(zhǔn),子彈以波的方式進(jìn)行探測(cè)

            Robocode 行為事件

            坦克的主要都定義在一個(gè)主循環(huán)中,我們?cè)诔绦蛑卸x為上面四個(gè)策略定義四種戰(zhàn)略如Move,Radar,Power,Target,當(dāng)某一事件發(fā)生,基于這個(gè)事件而定的行為就會(huì)觸發(fā)。而每個(gè)戰(zhàn)略中都有不同的行為處理方式。這些行為通過遺傳算法觸發(fā),遺傳算法將調(diào)用這些基本動(dòng)作并搜索這些策略的最佳組合?;谶@些基本動(dòng)作將有4224 (=4*11*4*3*8)種可能發(fā)生。在Robocode AdvancedRobot 類下有如下的移動(dòng)函數(shù):

            • setAhead和ahead:讓機(jī)器人向前移動(dòng)一定距離.
            • setBack和back:讓機(jī)器人向后移動(dòng)一定距離
            • setMaxTurnRate:設(shè)置機(jī)器人最大的旋轉(zhuǎn)速度
            • setMaxVelocity:設(shè)置機(jī)器人最大的運(yùn)動(dòng)速度
            • setStop和stop:停止移動(dòng)或暫停機(jī)器人,并記住停止的位置
            • setResume和resume:重新開始移動(dòng)停止的機(jī)器人
            • setTurnLeft和turnLeft:向左旋轉(zhuǎn)機(jī)器人
            • setTurnRight和turnRight:向右旋轉(zhuǎn)機(jī)器人

            下面是 doMove 移動(dòng)方法中使用部分程序代碼:

            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

            這里我們用遺傳算法來控制機(jī)器人移動(dòng)位置。這些策略是基于下面幾點(diǎn):機(jī)器人人自己的位置、速度和方位;對(duì)手的位置(x,y坐標(biāo))、速度、方位以及相對(duì)角;所有機(jī)器人和子彈位置,方位及速度;場(chǎng)地大小等參數(shù)。

            當(dāng)上面的信息在下一回移動(dòng)中使用時(shí),出輸出一對(duì)坐標(biāo)值,根據(jù)這對(duì)坐標(biāo)在Robocode就能得到距離和角度。要想讓移動(dòng)實(shí)現(xiàn)遺傳必須要讓它實(shí)現(xiàn)在線學(xué)習(xí):所以我們的代碼必須做下面幾件事:要有一個(gè)函數(shù)收集適應(yīng)度值,在Robocode運(yùn)行過程中要運(yùn)用到遺傳操作,遺傳后代要在Robocode運(yùn)行中產(chǎn)生,而不是事后由手寫入代碼。

            遺傳操作

            本例中遺傳算法為實(shí)現(xiàn)移動(dòng)用到兩個(gè)類GA和MovePattern。此處的GA比較簡(jiǎn)單主要完成數(shù)據(jù)和群體的定義,以及這些定義的讀寫文件操作?;邪ㄈ缦聟?shù):群體大小、交叉概率、變異概率、精英概率(既告訴從當(dāng)前群體到下一代中有多少移動(dòng)不需要改變)、方程式中使用的加權(quán)系數(shù)大小,它通過一個(gè)主循環(huán)完成MovePattern的封裝。MovePattern類中實(shí)現(xiàn)交叉、變異方法等方法,完成移動(dòng)模式操作。而所有的輸出保存在一個(gè)vector函數(shù)當(dāng)中。Vector函數(shù)擁有一對(duì)實(shí)數(shù)數(shù)組,一個(gè)用于計(jì)算x坐標(biāo),另一個(gè)用于計(jì)算y坐標(biāo)。通過對(duì)x,y坐標(biāo)的計(jì)算,從而得到距離、角度等值,并產(chǎn)生相就在移動(dòng)策略。如下,MovePattern包含三個(gè)參數(shù),grad表示vector函數(shù)排列順序,input即表示算法給出的輸入編號(hào),rang是加權(quán)的范圍。

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

            交叉操作:每一個(gè)交叉操作執(zhí)行如下步驟,先在交叉操作中產(chǎn)生一個(gè)特征碼。這個(gè)特征碼是個(gè)0到1之間的變量數(shù)組。有關(guān)交叉的基本原理可參考上面部分。最后通過遍歷vector函數(shù),把相應(yīng)的加權(quán)值進(jìn)行交叉操作。

            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

            這里的變異操作比較簡(jiǎn)單。把加權(quán)范圍內(nèi)的隨機(jī)數(shù)值去代替0到數(shù)組長(zhǎng)之間的隨機(jī)數(shù)并保存到移動(dòng)模式中。則完成整個(gè)數(shù)組的變異過程:

            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;
            }

            從上面的例子我們知道了遺傳算法的大概實(shí)現(xiàn),但并沒有告訴我們這些組件是如何一起工作的。當(dāng)Robocode開始時(shí),如果文件中沒有數(shù)據(jù),所以系統(tǒng)會(huì)依照輸入的策略隨機(jī)生成一個(gè)移動(dòng)模式,如果文件中有數(shù)據(jù),則加載這些數(shù)據(jù)。每一個(gè)移動(dòng)模式在開始都會(huì)給出了一個(gè)適應(yīng)度值。當(dāng)所有的移動(dòng)模式都接收到適應(yīng)度值,并完成各自的編號(hào)后,下面的操作將開始執(zhí)行:

            1. 對(duì)所有的移動(dòng)模式依據(jù)它們的適應(yīng)度值進(jìn)行分級(jí)處理
            2. 執(zhí)行精英操作
            3. 執(zhí)行交叉操作
            4. 應(yīng)用變異操作
            5. 保存加權(quán)
            6. 算法重新開始

            適應(yīng)度值在進(jìn)行運(yùn)算過程中由機(jī)器人程序不斷調(diào)整,以找到最優(yōu)適應(yīng)度。

            限于篇副其他的一些策略本文不與詳細(xì)說明,上面所有提到的策略和行為程序都可在網(wǎng)上或IBM的開發(fā)雜志上找到成熟的講解和例子機(jī)器人。有興趣的朋友可以把這些策略都加入到自己的遺傳算法中來。我們?nèi)∪后w大小為50,選擇概率為0.7,交叉概率為0.6,變異概率為0.3,與Robocode部分例子機(jī)器人測(cè)試,經(jīng)過150代后你會(huì)發(fā)現(xiàn)系統(tǒng)產(chǎn)生了很多有趣的策略。比如撞擊策略,這些策略都不在我們定義的策略之中。








            中間解釋程序進(jìn)化機(jī)器人

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

            編碼

            下表中顯示了TableRex編碼結(jié)構(gòu),它由一個(gè)行動(dòng)作函數(shù),二個(gè)輸入和一個(gè)輸出組成。如行6的值 ,這是個(gè)布爾型的表達(dá)式“值 line4 小于 90”,這個(gè)結(jié)果會(huì)在最后一行輸出布爾為1的值。

            Function Input 1 Input 2 Output
            1. Random ignore ignore 0,87
            2. Divide Const_1 Const_2 0,5
            3. Greater Than Line 1 Line 2 1
            4. Normalize Angle Enemy bearing ignore -50
            5. Absolute Value Line 4 ignore 50
            6. Less Than Line 4 Const_90 1
            7. And Line 6 Line 3 1
            8. Multiply Const_10 Const_10 100
            9. Less Than Enemy distance Line 8 0
            10. And Line 9 Line 7 0
            11. Multiply Line 10 Line 4 0
            12 Output Turn gun left Line 11 0
            posted @ 2011-04-14 22:27 沛沛 閱讀(454) | 評(píng)論 (0)編輯 收藏

            #include <stdio.h>
            #include 
            <stdlib.h>

            int strcmp(char *source, char *dest)
            {
            while(*source == *dest && *source != '\0' && *dest != '\0')
            {
              source
            ++;
              dest
            ++;
            }

            if (*source =='\0' && *dest == '\0')
              
            return 0;
            else
              
            return -1;


            }

            int main()
            {
            char *str1 = "abcde";
            char *str2 = "abcde";
            printf(
            "ret = %d", mystrcmp(str1, str2));

            return 0;
            }
            posted @ 2011-04-14 22:26 沛沛 閱讀(1419) | 評(píng)論 (2)編輯 收藏

            僅列出標(biāo)題
            共7頁: 1 2 3 4 5 6 7 
            2021久久精品国产99国产精品| 久久精品国产男包| 久久精品成人一区二区三区| AA级片免费看视频久久| 亚洲精品乱码久久久久久蜜桃 | 狠狠色噜噜狠狠狠狠狠色综合久久 | 久久99免费视频| 久久久这里有精品中文字幕| 国产欧美久久久精品影院| 99久久久精品| 久久精品国产乱子伦| 伊人久久综在合线亚洲2019| 中文字幕人妻色偷偷久久| 久久精品国产72国产精福利| 伊人久久综合成人网| 国产精品久久久99| 99精品国产在热久久| 狠狠精品久久久无码中文字幕| 日韩欧美亚洲综合久久影院d3| 香蕉久久av一区二区三区| 久久青青草原亚洲av无码| 狠狠干狠狠久久| 欧美午夜精品久久久久免费视 | 国产精品青草久久久久婷婷| 久久久久久精品免费免费自慰| 久久精品国产亚洲Aⅴ蜜臀色欲| 国产精品久久久久久福利69堂| 久久久久久久久久久久久久| 亚洲国产成人久久综合野外| 久久99精品国产麻豆不卡| 色综合久久中文综合网| 99久久精品影院老鸭窝| 久久99精品久久久久子伦| 九九久久自然熟的香蕉图片| 欧美精品久久久久久久自慰| 无码伊人66久久大杳蕉网站谷歌| 久久无码中文字幕东京热| 成人综合久久精品色婷婷| 久久人人爽人人爽人人片av麻烦| 一极黄色视频久久网站| 亚洲综合熟女久久久30p|