[轉(zhuǎn)]《深度探索C++對象模型》讀書筆記[一]

《深度探索C++對象模型》讀書筆記                                                                              

前 言 Stanley B.Lippman
1．   任何對象模型都需要的三種轉(zhuǎn)換風(fēng)味：

ü        與編譯器息息相關(guān)的轉(zhuǎn)換

ü        語言語義轉(zhuǎn)換

ü        程序代碼和對象模型的轉(zhuǎn)換

2．   C++對象模型的兩種解釋

ü        語言中直接支持面向?qū)ο蟪绦蛟O(shè)計(jì)的部分

ü        對于各種支持的底層實(shí)現(xiàn)機(jī)制

3．   C++ class的完整virtual functions在編譯時(shí)期就固定下來了，程序員沒有辦法在執(zhí)行期動(dòng)態(tài)增加或取代其中某一個(gè)。這使得虛擬函數(shù)調(diào)用操作得以有快速的派送結(jié)果，付出的卻是執(zhí)行期的彈性。

4．   目前所有編譯器對于virtual function的實(shí)現(xiàn)都是使用各個(gè)class專屬的virtual table，大小固定，并且在程序執(zhí)行前就構(gòu)造好了。

5．   C++對象模型的底層機(jī)制并未標(biāo)準(zhǔn)化，它會(huì)因?qū)崿F(xiàn)品（編譯器）和時(shí)間的變動(dòng)而不同。

2002-6-23

關(guān)于對象 Object Lessons
1.1 C++對象模式
1．   C++在布局以及存取時(shí)間上主要的額外負(fù)擔(dān)是由virtual引起的，包括virtual function機(jī)制和virtual base class 機(jī)制，還有一些發(fā)生在“一個(gè)derived class和其第二或后繼之base class的轉(zhuǎn)換”上的多重繼承。

2．   在C++對象模型中，nonstatic data members被配置于每一個(gè)class object之內(nèi)，static data members則被存放在所有的class object之外，static和nonstatic function members也被放在所有的class object之外，virtual functions則以兩個(gè)步驟支持：每個(gè)class產(chǎn)生一堆指向virtual functions的指針，放在virtual table (vtbl)中；每個(gè)class object被添加一個(gè)指針vptr，指向相關(guān)的virtual table。每個(gè)class所關(guān)聯(lián)的type_info object也經(jīng)由vtbl指出，通常是放在vtbl的第一個(gè)slot處。vptr由每一個(gè)class的construtor、destructor以及copy assignment operator自動(dòng)完成。以上模型的主要優(yōu)點(diǎn)在于空間和存取時(shí)間的效率，主要缺點(diǎn)是，只要應(yīng)用程序所用到的class object的nonstatic data members有所修改，那么應(yīng)用程序代碼就必須重新編譯。

3．   C++最初所采用的繼承模型并不運(yùn)用任何間接性，base class subobject的data members直接放置于derived class object中。優(yōu)點(diǎn)是提供對base class members緊湊且高效的存取，缺點(diǎn)是base class members的任何改變，都將導(dǎo)致使用其derived class 的object的應(yīng)用程序代碼必須重新編譯。

4．   virtual base class的原始模型是在class object中為每一個(gè)有關(guān)聯(lián)的virtual base class加上一個(gè)指針，其他演化出來的模型不是導(dǎo)入一個(gè)virtual base class table，就是擴(kuò)充原已存在的vtbl，用以維護(hù)每一個(gè)virtual base class的位置。

1.2關(guān)鍵詞所帶來的差異
1．   可以說關(guān)鍵詞struct的使用伴隨著一個(gè)public接口的聲明，也可以說它的用途只是為了方便C程序員遷徙至C++部落。

2．   C++中凡處于同一個(gè)access section的數(shù)據(jù)，必定保證以聲明次序出現(xiàn)在內(nèi)存布局中，然而被放在多個(gè)access sections中的各筆數(shù)據(jù)排列次序就不一定了。同樣，base classes和derived classes的data members的布局也沒有誰先誰后的強(qiáng)制規(guī)定。

3．   組合composition而非繼承才是把C和C++結(jié)合在一起的唯一可行方法。

1.3對象的差異
1．   C++程序設(shè)計(jì)模型支持三種程序設(shè)計(jì)典范programming paradigms：

ü          程序模型procedural model

ü          抽象數(shù)據(jù)類型模型abstract data type model， ADT

ü          面向?qū)ο髷?shù)據(jù)模型object-oriented model，OO

2．   雖然可以直接或間接處理繼承體系中的一個(gè)base class object，但只有通過pointer或reference的間接處理，才能支持OO程序設(shè)計(jì)所需的多態(tài)性質(zhì)。

3．   C++中，多態(tài)只存在于public class體系中，nonpublic的派生行為以及類型為void*的指針可以說是多態(tài)，但它們沒有被語言明白地支持，必須由程序員通過顯示的轉(zhuǎn)型操作來管理。

4．   C++以下列方法支持多態(tài)：

ü          經(jīng)由一組隱含的轉(zhuǎn)化操作，如把一個(gè)derived class指針轉(zhuǎn)化為一個(gè)指向其public base type的指針；

ü          經(jīng)由虛擬機(jī)制；

ü          經(jīng)由dynamic_cast和typeid運(yùn)算符。

5．   多態(tài)的主要用途是經(jīng)由一個(gè)共同的接口來影響類型的封裝，這個(gè)接口通常被定義在一個(gè)抽象的base class中。這個(gè)接口是以virtual function機(jī)制引發(fā)的，它可以在執(zhí)行期根據(jù)object的真正類型解析出到底是哪一個(gè)函數(shù)實(shí)體被調(diào)用。

6．   一個(gè)class object所需的內(nèi)存，一般而言由以下部分組成：

ü          nonstatic data members的總和大小；

ü          任何由于alignment需求而填補(bǔ)上去的空間；

ü          為支持virtual而由內(nèi)部產(chǎn)生的任何額外負(fù)擔(dān)。

7．   一個(gè)pointer或reference，不管它指向哪一種數(shù)據(jù)類型，指針本身所需的內(nèi)存大小是固定的。本質(zhì)上，一個(gè)reference通常是以一個(gè)指針來實(shí)現(xiàn)，而object語法如果轉(zhuǎn)換為間接手法，就需要一個(gè)指針。

8．   指向不同類型之指針的差異，既不在其指針表示法不同，也不在其內(nèi)容不同，而是在其所尋址出來的object類型不同，亦即指針類型會(huì)教導(dǎo)編譯器如何解釋某個(gè)特定地址中的內(nèi)存內(nèi)容及大小。它們之所以支持多態(tài)，是因?yàn)樗鼈儾⒉灰l(fā)內(nèi)存中任何與類型有關(guān)的內(nèi)存委托操作，會(huì)受到改變的只是它們所指向的內(nèi)存的大小和內(nèi)容的解釋方式。

9．   轉(zhuǎn)型cast操作其實(shí)是一種編譯指令，大部分情況下它并不改變一個(gè)指針?biāo)恼嬲刂罚皇怯绊懕恢赶蛑畠?nèi)存的大小和內(nèi)容的解釋方式。

10．一個(gè)base class object被直接初始化或指定為一個(gè)derived object時(shí)，derived object就會(huì)被切割sliced，以塞入較小的base type內(nèi)存中，多態(tài)于是不再呈現(xiàn)。一個(gè)嚴(yán)格的編譯器可以在編譯時(shí)期解析一個(gè)通過該object而觸發(fā)的virtual function調(diào)用操作，從而回避virtual機(jī)制。這時(shí)，如果virtual function被定義為inline，則會(huì)有效率上的收獲。

11．C++通過class的pointer和reference來支持多態(tài)，這種程序設(shè)計(jì)風(fēng)格就是所謂的OO；C++也支持具體的ADT程序風(fēng)格，如今被稱為object-based OB，不支持多態(tài)，不支持類型的擴(kuò)充。

2002-6-25

構(gòu)造函數(shù)語意學(xué)The Semantics of Constructors
1．   Jerry Schwarz，iostream函數(shù)庫建構(gòu)師，曾為了讓cin能夠求得一個(gè)真假值，于是他為它定義了一個(gè)conversion運(yùn)算符operator int()。但在語句cin << intVal中，其行為出乎意料：程序原本要的是cout而不是cin！但是編譯器卻找到一個(gè)正確的詮釋：將cin轉(zhuǎn)型為整型，現(xiàn)在left shift operator <<就可以工作了！這就是所謂的“Schwarz Error”。Jerry最后以operator void *()取代operator int()。

2．   引入關(guān)鍵詞explicit的目的，就是為了提供程序員一種方法，使他們能夠制止單一參數(shù)的constructor被當(dāng)作一個(gè)conversion運(yùn)算符。其引入是明智的，但其測試應(yīng)該是殘酷的！

2.1 Default Constructor的建構(gòu)操作
1．   global objects的內(nèi)存保證會(huì)在程序激活的時(shí)候被清為0。local objects配置于程序的堆棧中，heap objects配置于自由空間中，都不一定會(huì)被清為0，它們的內(nèi)容將是內(nèi)存上次被使用后的遺跡。

2．   在各個(gè)不同的版本模塊中，編譯器避免合成出多個(gè)default constructor的方法：把合成的default constructor、copy constructor、assignment copy operator都以inline方式完成。一個(gè)inline函數(shù)有靜態(tài)鏈接，不會(huì)被檔案以外者看到。如果函數(shù)過于復(fù)雜，不適合做成inline，就會(huì)合成一個(gè)explicit non-inline static實(shí)體。

3．   以下四種情況，編譯器必須為未聲明constructor的classes合成一個(gè)implicit nontrivial default constructor：帶有default constructor的member class object，帶有default constructor的base class，帶有virtual function，帶有virtual base class。其它各種情況且沒有聲明任何constructor的classes，它們擁有的是implicit trival default constructors，它們實(shí)際上并不會(huì)被合成出來。

4．   編譯器合成implicit nontrivial default constructor，不過是暗地里作了一些重要的事情以保證程序正確合理地運(yùn)行。如果程序員提供了多個(gè)constructors，但其中都沒有default constructor，編譯器同樣會(huì)在這些constructors中插入一些相同功能的代碼，這些代碼都將被安插在explicit user code之前。

2002-6-26

2.2 Copy Constructor的建構(gòu)操作
1．   有三種情況，會(huì)以一個(gè)class的內(nèi)容作為另一個(gè)class object的初值：

ü          對一個(gè)object作明確的初始化操作，如：someClass obt = obtb;

ü          一個(gè)object被當(dāng)作參數(shù)交給某個(gè)函數(shù)時(shí)，如：foo(obt);

ü          當(dāng)函數(shù)返回一個(gè)class object時(shí)。

若class設(shè)計(jì)者明確定義了一個(gè)copy constructor，大部分情況下，該constructor會(huì)被調(diào)用。這可能導(dǎo)致一個(gè)暫時(shí)性的class object的產(chǎn)生或程序代碼的蛻變，或者兩者皆有。

2．   如果class沒有提供一個(gè)explicit copy constructor，當(dāng)class object以相同class的另一個(gè)object作為初值時(shí)，其內(nèi)部是以所謂的default memberwise initialization手法完成的，即把每一個(gè)內(nèi)建的或派生的data member的值，從一個(gè)object拷貝到另一個(gè)object。不過，它并不會(huì)拷貝其中的member class object，而是以遞歸的方式施行memberwise initialization。

3．   一個(gè)class object可以從兩種方式復(fù)制得到：初始化和指定，從概念上而言，這兩個(gè)操作分別是以copy constructor和copy assignment operator完成的。

4．   如果class沒有聲明一個(gè)copy constructor，就會(huì)有隱含的聲明implicitly declared或隱含的定義implicitly defined出現(xiàn)。C++把copy constructor分為trivial和nontrivial兩種。只有nontrivial的實(shí)體才會(huì)被合成出來。決定一個(gè)copy constructor是否為trivial的標(biāo)準(zhǔn)在于class是否展現(xiàn)出所謂的“bitwise copy semantics”。

5．   以下四種情況，一個(gè)class不展現(xiàn)bitwise copy semantics：

ü          class內(nèi)含一個(gè)member object而后者的class聲明有或被編譯器合成有一個(gè)copy constructor時(shí)；

ü          class繼承自一個(gè)base class而后者存在或被編譯器合成有一個(gè)copy constructor時(shí)；

ü          當(dāng)class聲明了一個(gè)或多個(gè)virtual functions時(shí)；

ü          當(dāng)class派生自一個(gè)繼承串鏈，其中有一個(gè)或多個(gè)virtual base classes時(shí)。

前兩種情況中，編譯器必須將member或base class的copy constructors調(diào)用操作安插到被合成的copy constructor中。

6．   一旦一個(gè)class object中必須引入vptr，編譯器就必須為它的vptr正確地設(shè)置好初值。此時(shí)，該class就不再展現(xiàn)bitwise semantics。

7．   當(dāng)一個(gè)base class object以其derived class object內(nèi)容作初始化操作時(shí)，其vptr復(fù)制操作必須保證安全。

8．   每一個(gè)編譯器對于虛擬繼承的承諾，都表示必須讓derived class object中的virtual base class subobject的位置在執(zhí)行期準(zhǔn)備妥當(dāng)。維護(hù)位置的完整性是編譯器的責(zé)任。

2002-6-27

2.3 程序轉(zhuǎn)化語意學(xué)
1．   每一個(gè)明確的初始化操作都會(huì)有兩個(gè)必要的程序轉(zhuǎn)化階段：先重寫每一個(gè)定義，剝除其中的初始化操作，然后安插class的copy constructor調(diào)用操作。

2．   把一個(gè)class object當(dāng)作參數(shù)傳給一個(gè)函數(shù)或是作為一個(gè)函數(shù)的返回值，相當(dāng)于以下形式的初始化操作：

X xx = arg; 其中xx代表形式參數(shù)或返回值，而arg代表真正的參數(shù)值。

3．   函數(shù)定義如下：X bar(){X xx; return xx;}，bar()的返回值通過一個(gè)雙階轉(zhuǎn)化從局部對象xx中拷貝出來：

ü          首先為bar添加一個(gè)額外參數(shù)，類型是class object的一個(gè)reference，這個(gè)參數(shù)用來放置被拷貝構(gòu)建而得的返回值。

ü          然后在return指令之前安插一個(gè)copy constructor調(diào)用操作，以便將欲傳回之object的內(nèi)容當(dāng)作上述新增參數(shù)的初值，同時(shí)重寫函數(shù)使它不返回任何值。

4．   Named Return Value(NRV)優(yōu)化如今被視為是標(biāo)準(zhǔn)C++編譯器的一個(gè)義不容辭的優(yōu)化操作，它的特點(diǎn)是直接操作新添加的額外參數(shù)。注意只有copy constructor的出現(xiàn)才會(huì)激活C++編譯器的NRV優(yōu)化！NRV優(yōu)化雖然極大地改善了效率，但還是飽受批評：一是優(yōu)化由編譯器默默完成，而是否完成以及其完成程度完全透明；二是一旦函數(shù)變得比較復(fù)雜，優(yōu)化就變得較難施行；三是優(yōu)化由可能使程序產(chǎn)生錯(cuò)誤——有時(shí)并不是對稱地調(diào)用constructor和destructor，而是copy constructor未被調(diào)用！

5．   在編譯器提供NRV優(yōu)化的前提下，如果可以預(yù)見class需要大量的memberwise初始化操作，比如以by value的方式傳回objects，那么提供一個(gè)explicit inline copy constructor的函數(shù)實(shí)體就非常合理。此種情況下，沒有必要同時(shí)提供explicit assignment operator定義。

6．   copy constructor的應(yīng)用迫使編譯器多多少少對程序代碼作部分優(yōu)化，尤其是當(dāng)一個(gè)函數(shù)以by value的方式傳回一個(gè)class object，而該class有一個(gè)copy constructor（或定義或合成）時(shí)，無論在函數(shù)的定義還是在使用上將導(dǎo)致深?yuàn)W的程序轉(zhuǎn)化。此外，編譯器將實(shí)施NRV優(yōu)化。

7．   注意正確使用memset()和memcpy()，它們都只有在classes不含任何由編譯器產(chǎn)生的內(nèi)部members如vptr時(shí)才能有效運(yùn)行！

2002-6-30

2.4 成員初始化列表
1．   當(dāng)寫下一個(gè)constructor時(shí)，就有機(jī)會(huì)設(shè)定class members的初值。不是經(jīng)由member initialization list，就是在constructor函數(shù)本身之內(nèi)。

2．   下列情況，為了讓程序能被順利編譯，必須使用member initialization list：

ü          初始化一個(gè)reference member時(shí)；

ü          初始化一個(gè)const member時(shí)；

ü          調(diào)用一個(gè)base class的constructor，而它擁有一組參數(shù)時(shí)；

ü          調(diào)用一個(gè)member class的constructor，而它擁有一組參數(shù)時(shí)。

3．   編譯器會(huì)對initialization list一一處理并可能重新排序，以反映出members的聲明次序，它會(huì)安插一些代碼到constructor內(nèi)，并置于任何explicit user code之前。

4．   一個(gè)忠告：請使用“存在于constructor體內(nèi)的一個(gè)member”，而不是“存在于member initialization list中的一個(gè)member”，來為另一個(gè)member設(shè)定初值。

2002-7-1

Data語意學(xué)    The Semantics of Data
討論如下繼承體系：

         class X{};

         class Y : public virtual X{};

         class Z : public virtual X{};

         class A: public Y, public Z{};

1．   一個(gè)empty class如class X{}，它有一個(gè)隱晦的1 byte，那是被編譯器安插進(jìn)去的一個(gè)char，使得這個(gè)class的兩個(gè)objects得以在內(nèi)存中配置獨(dú)一無二的地址。

2．    Y和Z的大小受到三個(gè)因素的影響：

ü          語言本身所造成的額外負(fù)擔(dān)overhead。語言支持virtual base classes時(shí)導(dǎo)致的額外負(fù)擔(dān)反映在某種形式的指針身上，它要么指向virtual base class subobject，要么指向一個(gè)存放virtual base class subobject地址或者其偏移量offset的表格。

ü          編譯器對于特殊情況所提供的優(yōu)化處理。virtual base class X 1 byte大小的subobject也出現(xiàn)在class Y和Z身上。傳統(tǒng)上它被放在derived class的固定部分的尾端。某些編譯器對empty virtual base提供特殊處理，將它視為derived class object最開頭的一部分，它不用會(huì)任何的額外空間，也就是前面提到的1 byte。

ü          Alignment的限制。Alignment就是將數(shù)值調(diào)整到某數(shù)的整數(shù)倍，在32位計(jì)算機(jī)上，通常該數(shù)為4 bytes(32位)，以使bus的運(yùn)輸量達(dá)到最高效率。

3．   一個(gè)virtual base class subobject只會(huì)在derived class中存在一份實(shí)體，不管它在class繼承體系中出現(xiàn)了多少次，class A的大小由下列幾點(diǎn)決定：

ü              被大家共享的唯一一個(gè)class X實(shí)體，大小為1 byte；

ü              Base Y、Z的大小減去因virual base class而配置的大小；

ü              class A自己的大小；

ü              class A的alignment數(shù)量。

4．   C++ standard并不強(qiáng)制規(guī)定base class subobjects、不同存取級別的data members的排列次序這種瑣碎細(xì)節(jié)，它也不規(guī)定virtual function以及virtual base classes的實(shí)現(xiàn)細(xì)節(jié)。

5．   C++對象模型盡量以空間優(yōu)化和存取速度優(yōu)化來表現(xiàn)nonstatic data members，并且保持和C語言struct數(shù)據(jù)配置的兼容性。它把數(shù)據(jù)直接存放在每一個(gè)class object中，對于繼承而來的nonstatic data members，不管是virtual或nonvirtual base class也是如此。至于static data members則被放置在程序的一個(gè)global data segment中，不會(huì)影響個(gè)別class object的大小。static data member永遠(yuǎn)只存在一份實(shí)體，但是一個(gè)template class的static data member的行為稍有不同。

3.1 Data Member的綁定
inline member function軀體內(nèi)的data member綁定操作，會(huì)在整個(gè)class聲明完成后才發(fā)生，而argument list中的名稱還是會(huì)在它們第一次遭遇時(shí)被適當(dāng)?shù)貨Q議resolved完成。基于這種狀況，請始終把nested type聲明放在class的起始處。

                                                                                                                2002-7-2

3.2 Data Member的布局
1．   每一個(gè)private、protected、public區(qū)段就是一個(gè)access section。C++ Standard要求，在同一個(gè)access section中，members的排列只需滿足“較晚出現(xiàn)的members在class object中有較高的地址”這一條件即可。也就是說各個(gè)members并不一定的連續(xù)排列，alignment可能需要的bytes以及編譯器可能合成供內(nèi)部使用的data members都可能介于被聲明的members之間。

2．   C++ Standard也允許編譯器將多個(gè)access sections之中的data members自由排列，不必在乎它們出現(xiàn)在class聲明中的次序。當(dāng)前各家編譯器都是把一個(gè)以上的access sections連鎖在一起，依照聲明的次序成為一個(gè)連續(xù)區(qū)塊。access sections的多寡不會(huì)導(dǎo)致額外負(fù)擔(dān)。

3．   vptr傳統(tǒng)上會(huì)被放在所有明確聲明的members的最后，不過如今也有一些編譯器把vptr放在class object的最前端。

4．   一個(gè)用來判斷哪一個(gè)section先出現(xiàn)的template function：

template <class class_type, class data_type1, class data_type2>

char* access_order(data_type1 class_type::*mem1,     data_type2 class_type::*mem2)

{

           assert(mem1 != mem2);

           return mem1 < mem2 ? “member 1 occurs first” : “member 2 occurs first”;

}

本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/xjtuse_mal/archive/2007/03/01/1517806.aspx

posted @ 2010-10-14 10:13 Vincent 閱讀(376) | 評論 (0) | 編輯 收藏

【轉(zhuǎn)】線程同步-自旋鎖與Mutex/信號量的區(qū)別和聯(lián)系

POSIX threads(簡稱Pthreads)是在多核平臺(tái)上進(jìn)行并行編程的一套常用的API。線程同步(Thread Synchronization)是并行編程中非常重要的通訊手段，其中最典型的應(yīng)用就是用Pthreads提供的鎖機(jī)制(lock)來對多個(gè)線程之間共 享的臨界區(qū)(Critical Section)進(jìn)行保護(hù)(另一種常用的同步機(jī)制是barrier)。

Pthreads提供了多種鎖機(jī)制：
(1) Mutex（互斥量）：pthread_mutex_***
(2) Spin lock（自旋鎖）：pthread_spin_***
(3) Condition Variable（條件變量）：pthread_con_***
(4) Read/Write lock（讀寫鎖）：pthread_rwlock_***

Pthreads提供的Mutex鎖操作相關(guān)的API主要有：
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的與Spin Lock鎖操作相關(guān)的API主要有：
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

從實(shí)現(xiàn)原理上來講，Mutex屬于sleep-waiting類型的鎖。例如在一個(gè)雙核的機(jī)器上有兩個(gè)線程(線程A和線程B)，它們分別運(yùn)行在Core0和Core1上。假設(shè)線程A想要通過pthread_mutex_lock操作去得到一個(gè)臨界區(qū)的鎖，而此時(shí)這個(gè)鎖正被線程B所持有，那么線程A就會(huì)被阻塞(blocking)，Core0 會(huì)在此時(shí)進(jìn)行上下文切換(Context Switch)將線程A置于等待隊(duì)列中，此時(shí)Core0就可以運(yùn)行其他的任務(wù)(例如另一個(gè)線程C)而不必進(jìn)行忙等待。而Spin lock則不然，它屬于busy-waiting類型的鎖，如果線程A是使用pthread_spin_lock操作去請求鎖，那么線程A就會(huì)一直在 Core0上進(jìn)行忙等待并不停的進(jìn)行鎖請求，直到得到這個(gè)鎖為止。

如果大家去查閱Linux glibc中對pthreads API的實(shí)現(xiàn)NPTL(Native POSIX Thread Library) 的源碼的話(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我們系統(tǒng)中NPTL的版本號)，就會(huì)發(fā)現(xiàn)pthread_mutex_lock()操作如果沒有鎖成功的話就會(huì)調(diào)用system_wait()的系統(tǒng)調(diào)用并將當(dāng)前線程加入該mutex的等待隊(duì)列里。而spin lock則可以理解為在一個(gè)while(1)循環(huán)中用內(nèi)嵌的匯編代碼實(shí)現(xiàn)的鎖操作(印象中看過一篇論文介紹說在linux內(nèi)核中spin lock操作只需要兩條CPU指令，解鎖操作只用一條指令就可以完成)。有興趣的朋友可以參考另一個(gè)名為sanos的微內(nèi)核中pthreds API的實(shí)現(xiàn)：mutex.c spinlock.c，盡管與NPTL中的代碼實(shí)現(xiàn)不盡相同，但是因?yàn)樗膶?shí)現(xiàn)非常簡單易懂，對我們理解spin lock和mutex的特性還是很有幫助的。

那么在實(shí)際編程中mutex和spin lcok哪個(gè)的性能更好呢？我們知道spin lock在Linux內(nèi)核中有非常廣泛的利用，那么這是不是說明spin lock的性能更好呢？下面讓我們來用實(shí)際的代碼測試一下（請確保你的系統(tǒng)中已經(jīng)安裝了最近的g++）。

查看源代碼打印幫助001 // Name: spinlockvsmutex1.cc  

002 // Source: [url]http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock[/url]  

003 // Compiler(<FONT style="BACKGROUND-COLOR: #00ffff">spin lock</FONT> version): g++ -o spin_version -DUSE_SPINLOCK spinlockvsmutex1.cc -lpthread  

004 // Compiler(mutex version): g++ -o mutex_version spinlockvsmutex1.cc -lpthread  

005 #include <stdio.h>  

006 #include <unistd.h>  

007 #include <sys/syscall.h>  

008 #include <errno.h>  

009 #include <sys/time.h>  

010 #include <list>  

011 #include <pthread.h>  

012   

013 #define LOOPS 50000000  

014   

015 using namespace std;  

016   

017 list<int> the_list;  

018   

019 #ifdef USE_SPINLOCK  

020 pthread_spinlock_t spinlock;  

021 #else  

022 pthread_mutex_t mutex;  

023 #endif  

024   

025 //Get the thread id  

026 pid_t gettid() { return syscall( __NR_gettid ); }  

027   

028 void *consumer(void *ptr)  

029 {  

030     int i;  

031   

032     printf("Consumer TID %lun", (unsigned long)gettid());  

033   

034     while (1)  

035     {  

036 #ifdef USE_SPINLOCK  

037         pthread_spin_lock(&spinlock);  

038 #else  

039         pthread_mutex_lock(&mutex);  

040 #endif  

041   

042         if (the_list.empty())  

043         {  

044 #ifdef USE_SPINLOCK  

045             pthread_spin_unlock(&spinlock);  

046 #else  

047             pthread_mutex_unlock(&mutex);  

048 #endif  

049             break;  

050         }  

051   

052         i = the_list.front();  

053         the_list.pop_front();  

054   

055 #ifdef USE_SPINLOCK  

056         pthread_spin_unlock(&spinlock);  

057 #else  

058         pthread_mutex_unlock(&mutex);  

059 #endif  

060     }  

061   

062     return NULL;  

063 }  

064   

065 int main()  

066 {  

067     int i;  

068     pthread_t thr1, thr2;  

069     struct timeval tv1, tv2;  

070   

071 #ifdef USE_SPINLOCK  

072     pthread_spin_init(&spinlock, 0);  

073 #else  

074     pthread_mutex_init(&mutex, NULL);  

075 #endif  

076   

077     // Creating the list content...  

078     for (i = 0; i < LOOPS; i++)  

079         the_list.push_back(i);  

080   

081     // Measuring time before starting the threads...  

082     gettimeofday(&tv1, NULL);  

083   

084     pthread_create(&thr1, NULL, consumer, NULL);  

085     pthread_create(&thr2, NULL, consumer, NULL);  

086   

087     pthread_join(thr1, NULL);  

088     pthread_join(thr2, NULL);  

089   

090     // Measuring time after threads finished...  

091     gettimeofday(&tv2, NULL);  

092   

093     if (tv1.tv_usec > tv2.tv_usec)  

094     {  

095         tv2.tv_sec--;  

096         tv2.tv_usec += 1000000;  

097     }  

098   

099     printf("Result - %ld.%ldn", tv2.tv_sec - tv1.tv_sec,  

100         tv2.tv_usec - tv1.tv_usec);  

101   

102 #ifdef USE_SPINLOCK  

103     pthread_spin_destroy(&spinlock);  

104 #else  

105     pthread_mutex_destroy(&mutex);  

106 #endif  

107   

108     return 0;  

109 }

該程序運(yùn)行過程如下：主線程先初始化一個(gè)list結(jié)構(gòu)，并根據(jù)LOOPS的值將對應(yīng)數(shù)量的entry插入該list，之后創(chuàng)建兩個(gè)新線程，它們都執(zhí)行consumer()這個(gè)任務(wù)。兩個(gè)被創(chuàng)建的新線程同時(shí)對這個(gè)list進(jìn)行pop操作。主線程會(huì)計(jì)算從創(chuàng)建兩個(gè)新線程到兩個(gè)新線程結(jié)束之間所用的時(shí)間，輸出為下文中的”Result “。

測試機(jī)器參數(shù)：
Ubuntu 9.04 X86_64
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz
4.0 GB Memory

從下面是測試結(jié)果：

查看源代碼打印幫助01 pxcwan@pxcwan-desktop:~/Workspace/mutex$ g++ -o spin_version -DUSE_SPINLOCK spinvsmutex1.cc -lpthread  

02 pxcwan@pxcwan-desktop:~/Workspace/mutex$ g++ -o mutex_version spinvsmutex1.cc -lpthread  

03 pxcwan@pxcwan-desktop:~/Workspace/mutex$ time ./spin_version  

04 Consumer TID 5520  

05 Consumer TID 5521  

06 Result - 5.888750  

07   

08 real    0m10.918s  

09 user    0m15.601s  

10 sys    0m0.804s  

11   

12 pxcwan@pxcwan-desktop:~/Workspace/mutex$ time ./mutex_version  

13 Consumer TID 5691  

14 Consumer TID 5692  

15 Result - 9.116376  

16   

17 real    0m14.031s  

18 user    0m12.245s  

19 sys    0m4.368s

可以看見spin lock的版本在該程序中表現(xiàn)出來的性能更好。另外值得注意的是sys時(shí)間，mutex版本花費(fèi)了更多的系統(tǒng)調(diào)用時(shí)間，這就是因?yàn)閙utex會(huì)在鎖沖突時(shí)調(diào)用system wait造成的。

但是，是不是說spin lock就一定更好了呢？讓我們再來看一個(gè)鎖沖突程度非常劇烈的實(shí)例程序：

查看源代碼打印幫助01 //Name: svm2.c  

02 //Source: [url]http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks[/url]  

03 //Compile(<FONT style="BACKGROUND-COLOR: #00ffff">spin lock</FONT> version): gcc -o spin -DUSE_SPINLOCK svm2.c -lpthread  

04 //Compile(mutex version): gcc -o mutex svm2.c -lpthread  

05 #include <stdio.h>  

06 #include <stdlib.h>  

07 #include <pthread.h>  

08 #include <sys/syscall.h>  

09   

10 #define        THREAD_NUM     2  

11   

12 pthread_t g_thread[THREAD_NUM];  

13 #ifdef USE_SPINLOCK  

14 pthread_spinlock_t g_spin;  

15 #else  

16 pthread_mutex_t g_mutex;  

17 #endif  

18 __uint64_t g_count;  

19   

20 pid_t gettid()  

21 {  

22     return syscall(SYS_gettid);  

23 }  

24   

25 void *run_amuck(void *arg)  

26 {  

27        int i, j;  

28   

29        printf("Thread %lu started.n", (unsigned long)gettid());  

30   

31        for (i = 0; i < 10000; i++) {  

32 #ifdef USE_SPINLOCK  

33            pthread_spin_lock(&g_spin);  

34 #else  

35                pthread_mutex_lock(&g_mutex);  

36 #endif  

37                for (j = 0; j < 100000; j++) {  

38                        if (g_count++ == 123456789)  

39                                printf("Thread %lu wins!n", (unsigned long)gettid());  

40                }  

41 #ifdef USE_SPINLOCK  

42            pthread_spin_unlock(&g_spin);  

43 #else  

44                pthread_mutex_unlock(&g_mutex);  

45 #endif  

46        }  

47   

48        printf("Thread %lu finished!n", (unsigned long)gettid());  

49   

50        return (NULL);  

51 }  

52   

53 int main(int argc, char *argv[])  

54 {  

55        int i, threads = THREAD_NUM;  

56   

57        printf("Creating %d threads...n", threads);  

58 #ifdef USE_SPINLOCK  

59        pthread_spin_init(&g_spin, 0);  

60 #else  

61        pthread_mutex_init(&g_mutex, NULL);  

62 #endif  

63        for (i = 0; i < threads; i++)  

64                pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);  

65   

66        for (i = 0; i < threads; i++)  

67                pthread_join(g_thread[i], NULL);  

68   

69        printf("Done.n");  

70   

71        return (0);  

72 }

這個(gè)程序的特征就是臨界區(qū)非常大，這樣兩個(gè)線程的鎖競爭會(huì)非常的劇烈。當(dāng)然這個(gè)是一個(gè)極端情況，實(shí)際應(yīng)用程序中臨界區(qū)不會(huì)如此大，鎖競爭也不會(huì)如此激烈。測試結(jié)果顯示mutex版本性能更好：

查看源代碼打印幫助01 pxcwan@pxcwan-desktop:~/Workspace/mutex$ time ./spin  

02 Creating 2 threads...  

03 Thread 31796 started.  

04 Thread 31797 started.  

05 Thread 31797 wins!  

06 Thread 31797 finished!  

07 Thread 31796 finished!  

08 Done.  

09   

10 real    0m5.748s  

11 user    0m10.257s  

12 sys    0m0.004s  

13   

14 pxcwan@pxcwan-desktop:~/Workspace/mutex$ time ./mutex  

15 Creating 2 threads...  

16 Thread 31801 started.  

17 Thread 31802 started.  

18 Thread 31802 wins!  

19 Thread 31802 finished!  

20 Thread 31801 finished!  

21 Done.  

22   

23 real    0m4.823s  

24 user    0m4.772s  

25 sys    0m0.032s

另外一個(gè)值得注意的細(xì)節(jié)是spin lock耗費(fèi)了更多的user time。這就是因?yàn)閮蓚€(gè)線程分別運(yùn)行在兩個(gè)核上，大部分時(shí)間只有一個(gè)線程能拿到鎖，所以另一個(gè)線程就一直在它運(yùn)行的core上進(jìn)行忙等待，CPU占用率一直是100%；而mutex則不同，當(dāng)對鎖的請求失敗后上下文切換就會(huì)發(fā)生，這樣就能空出一個(gè)核來進(jìn)行別的運(yùn)算任務(wù)了。（其實(shí)這種上下文切換對已經(jīng)拿著鎖的那個(gè)線程性能也是有影響的，因?yàn)楫?dāng)該線程釋放該鎖時(shí)它需要通知操作系統(tǒng)去喚醒那些被阻塞的線程，這也是額外的開銷）

總結(jié)
（1）Mutex適合對鎖操作非常頻繁的場景，并且具有更好的適應(yīng)性。盡管相比spin lock它會(huì)花費(fèi)更多的開銷（主要是上下文切換），但是它能適合實(shí)際開發(fā)中復(fù)雜的應(yīng)用場景，在保證一定性能的前提下提供更大的靈活度。

（2）spin lock的lock/unlock性能更好(花費(fèi)更少的cpu指令)，但是它只適應(yīng)用于臨界區(qū)運(yùn)行時(shí)間很短的場景。而在實(shí)際軟件開發(fā)中，除非程序員對自己的程序的鎖操作行為非常的了解，否則使用spin lock不是一個(gè)好主意(通常一個(gè)多線程程序中對鎖的操作有數(shù)以萬次，如果失敗的鎖操作(contended lock requests)過多的話就會(huì)浪費(fèi)很多的時(shí)間進(jìn)行空等待)。

（3）更保險(xiǎn)的方法或許是先（保守的）使用 Mutex，然后如果對性能還有進(jìn)一步的需求，可以嘗試使用spin lock進(jìn)行調(diào)優(yōu)。畢竟我們的程序不像Linux kernel那樣對性能需求那么高(Linux Kernel最常用的鎖操作是spin lock和rw lock)。

2010年3月3日補(bǔ)記：這個(gè)觀點(diǎn)在Oracle的文檔中得到了支持：

During configuration, Berkeley DB selects a mutex implementation for the architecture. Berkeley DB normally prefers blocking-mutex implementations over non-blocking ones. For example, Berkeley DB will select POSIX pthread mutex interfaces rather than assembly-code test-and-set spin mutexes because pthread mutexes are usually more efficient and less likely to waste CPU cycles spinning without getting any work accomplished.

p.s.調(diào)用syscall(SYS_gettid)和syscall( __NR_gettid )都可以得到當(dāng)前線程的id:)

轉(zhuǎn)載請注明來自: [url]www.parallellabs.com[/url]
------------------------------------------------------------------------------

spinlock與linux內(nèi)核調(diào)度的關(guān)系


　　作者：劉洪濤，華清遠(yuǎn)見嵌入式培訓(xùn)中心高級講師，ARM公司授權(quán)ATC講師。

廣告插播信息
維庫最新熱賣芯片：

　　關(guān)于自旋鎖用法介紹的文章，已經(jīng)有很多，但有些細(xì)節(jié)的地方點(diǎn)的還不夠透。我這里就把我個(gè)人認(rèn)為大家容易有疑問的地方拿出來討論一下。

　　一、自旋鎖（spinlock）簡介

　　自旋鎖在同一時(shí)刻只能被最多一個(gè)內(nèi)核任務(wù)持有，所以一個(gè)時(shí)刻只有一個(gè)線程允許存在于臨界區(qū)中。這點(diǎn)可以應(yīng)用在多處理機(jī)器、或運(yùn)行在單處理器上的搶占式內(nèi)核中需要的鎖定服務(wù)。

　　二、信號量簡介

　　這里也介紹下信號量的概念，因?yàn)樗挠梅ê妥孕i有相似的地方。

　　Linux中的信號量是一種睡眠鎖。如果有一個(gè)任務(wù)試圖獲得一個(gè)已被持有的信號量時(shí)，信號量會(huì)將其推入等待隊(duì)列，然后讓其睡眠。這時(shí)處理器獲得自由去執(zhí)行其它代碼。當(dāng)持有信號量的進(jìn)程將信號量釋放后，在等待隊(duì)列中的一個(gè)任務(wù)將被喚醒，從而便可以獲得這個(gè)信號量。

　　三、自旋鎖和信號量對比

　　在很多地方自旋鎖和信號量可以選擇任何一個(gè)使用，但也有一些地方只能選擇某一種。下面對比一些兩者的用法。

　　表1-1自旋鎖和信號量對比










　　四、自旋鎖與linux內(nèi)核進(jìn)程調(diào)度關(guān)系

　　我們討論下表1-1中的第3種情況（其它幾種情況比較好理解），如果臨界區(qū)可能包含引起睡眠的代碼則不能使用自旋鎖，否則可能引起死鎖。

　　那么為什么信號量保護(hù)的代碼可以睡眠而自旋鎖就不能呢？

　　先看下自旋鎖的實(shí)現(xiàn)方法吧，自旋鎖的基本形式如下：

　　spin_lock(&mr_lock);

　　//臨界區(qū)

　　spin_unlock(&mr_lock);

　　跟蹤一下spin_lock(&mr_lock)的實(shí)現(xiàn)

　　#define spin_lock(lock) _spin_lock(lock)

　　#define _spin_lock(lock) __LOCK(lock)

　　#define __LOCK(lock) \

　　do { preempt_disable(); __acquire(lock); (void)(lock); } while (0)

　　注意到“preempt_disable()”，這個(gè)調(diào)用的功能是“關(guān)搶占”（在spin_unlock中會(huì)重新開啟搶占功能）。從中可以看出，使用自旋鎖保護(hù)的區(qū)域是工作在非搶占的狀態(tài)；即使獲取不到鎖，在“自旋”狀態(tài)也是禁止搶占的。了解到這，我想咱們應(yīng)該能夠理解為何自旋鎖保護(hù)的代碼不能睡眠了。試想一下，如果在自旋鎖保護(hù)的代碼中間睡眠，此時(shí)發(fā)生進(jìn)程調(diào)度，則可能另外一個(gè)進(jìn)程會(huì)再次調(diào)用spinlock保護(hù)的這段代碼。而我們現(xiàn)在知道了即使在獲取不到鎖的“自旋”狀態(tài)，也是禁止搶占的，而“自旋”又是動(dòng)態(tài)的，不會(huì)再睡眠了，也就是說在這個(gè)處理器上不會(huì)再有進(jìn)程調(diào)度發(fā)生了，那么死鎖自然就發(fā)生了。

　　咱們可以總結(jié)下自旋鎖的特點(diǎn)：

　　● 單處理器非搶占內(nèi)核下：自旋鎖會(huì)在編譯時(shí)被忽略；

　　● 單處理器搶占內(nèi)核下：自旋鎖僅僅當(dāng)作一個(gè)設(shè)置內(nèi)核搶占的開關(guān)；

　　● 多處理器下：此時(shí)才能完全發(fā)揮出自旋鎖的作用，自旋鎖在內(nèi)核中主要用來防止多處理器中并發(fā)訪問臨界區(qū)，防止內(nèi)核搶占造成的競爭。

　　五、linux搶占發(fā)生的時(shí)間

　　最后在了解下linux搶占發(fā)生的時(shí)間，搶占分為用戶搶占和內(nèi)核搶占。

　　用戶搶占在以下情況下產(chǎn)生：

　　● 從系統(tǒng)調(diào)用返回用戶空間

　　● 從中斷處理程序返回用戶空間

　　內(nèi)核搶占會(huì)發(fā)生在：

　　● 當(dāng)從中斷處理程序返回內(nèi)核空間的時(shí)候，且當(dāng)時(shí)內(nèi)核具有可搶占性；

　　● 當(dāng)內(nèi)核代碼再一次具有可搶占性的時(shí)候。（如:spin_unlock時(shí)）

　　● 如果內(nèi)核中的任務(wù)顯式的調(diào)用schedule()

　　● 如果內(nèi)核中的任務(wù)阻塞。

　　基本的進(jìn)程調(diào)度就是發(fā)生在時(shí)鐘中斷后，并且發(fā)現(xiàn)進(jìn)程的時(shí)間片已經(jīng)使用完了，則發(fā)生進(jìn)程搶占。通常我們會(huì)利用中斷處理程序返回內(nèi)核空間的時(shí)候可以進(jìn)行內(nèi)核搶占這個(gè)特性來提高一些I/O操作的實(shí)時(shí)性，如：當(dāng)I/O事件發(fā)生的是時(shí)候，對應(yīng)的中斷處理程序被激活，當(dāng)它發(fā)現(xiàn)有進(jìn)程在等待這個(gè)I/O事件的時(shí)候，它會(huì)激活等待進(jìn)程，并且設(shè)置當(dāng)前正在執(zhí)行進(jìn)程的need_resched標(biāo)志，這樣在中斷處理程序返回的時(shí)候，調(diào)度程序被激活，原來在等待I/O事件的進(jìn)程（很可能）獲得執(zhí)行權(quán)，從而保證了對I/O事件的相對快速響應(yīng)（毫秒級）。可以看出，在I/O事件發(fā)生的時(shí)候，I/O事件的處理進(jìn)程會(huì)搶占當(dāng)前進(jìn)程，系統(tǒng)的響應(yīng)速度與調(diào)度時(shí)間片的長度無關(guān)。

posted @ 2010-09-21 15:15 Vincent 閱讀(3062) | 評論 (0) | 編輯 收藏

iocp(我所見過講的最通俗易懂的……）

理解I/O Completion Port
摘自:http://gzlyb.cnblogs.com/archive/2005/09/30/247049.aspx
      歡迎閱讀此篇IOCP教程。我將先給出IOCP的定義然后給出它的實(shí)現(xiàn)方法，最后剖析一個(gè)Echo程序來為您撥開IOCP的謎云，除去你心中對IOCP的煩惱。OK，但我不能保證你明白IOCP的一切，但我會(huì)盡我最大的努力。以下是我會(huì)在這篇文章中提到的相關(guān)技術(shù)：
　　I/O端口
　　同步/異步
　　堵塞/非堵塞
　　服務(wù)端/客戶端
　　多線程程序設(shè)計(jì)
　　Winsock API 2.0
　　在這之前，我曾經(jīng)開發(fā)過一個(gè)項(xiàng)目，其中一塊需要網(wǎng)絡(luò)支持，當(dāng)時(shí)還考慮到了代碼的可移植性，只要使用select,connect,accept,listen,send還有recv,再加上幾個(gè)#ifdef的封裝以用來處理Winsock和BSD套接字[socket]中間的不兼容性，一個(gè)網(wǎng)絡(luò)子系統(tǒng)只用了幾個(gè)小時(shí)很少的代碼就寫出來了，至今還讓我很回味。那以后很長時(shí)間也就沒再碰了。
　　前些日子，我們策劃做一個(gè)網(wǎng)絡(luò)游戲，我主動(dòng)承擔(dān)下網(wǎng)絡(luò)這一塊，想想這還不是小case,心里偷著樂啊。網(wǎng)絡(luò)游戲好啊，網(wǎng)絡(luò)游戲?yàn)槌砂偕锨У耐婕姨峁┝藰啡ず土钊酥氐挠螒蝮w驗(yàn)，他們在線上互相戰(zhàn)斗或是加入隊(duì)伍去戰(zhàn)勝共同的敵人。我信心滿滿的準(zhǔn)備開寫我的網(wǎng)絡(luò)，于是乎，發(fā)現(xiàn)過去的阻塞同步模式模式根本不能拿到一個(gè)巨量多玩家[MMP]的架構(gòu)中去，直接被否定掉了。于是乎，就有了IOCP，如果能過很輕易而舉的搞掂IOCP，也就不會(huì)有這篇教程了。下面請諸位跟隨我進(jìn)入正題。

什么是IOCP？
先讓我們看看對IOCP的評價(jià)
I/O完成端口可能是Win32提供的最復(fù)雜的內(nèi)核對象。
[Advanced Windows 3rd] Jeffrey Richter
這是[IOCP]實(shí)現(xiàn)高容量網(wǎng)絡(luò)服務(wù)器的最佳方法。
[Windows Sockets2.0:Write Scalable Winsock Apps Using Completion Ports]
Microsoft Corporation
完成端口模型提供了最好的伸縮性。這個(gè)模型非常適用來處理數(shù)百乃至上千個(gè)套接字。
[Windows網(wǎng)絡(luò)編程2nd] Anthony Jones & Jim Ohlund
I/O completion ports特別顯得重要，因?yàn)樗鼈兪俏ㄒ贿m用于高負(fù)載服務(wù)器[必須同時(shí)維護(hù)許多連接線路]的一個(gè)技術(shù)。Completion ports利用一些線程，幫助平衡由I/O請求所引起的負(fù)載。這樣的架構(gòu)特別適合用在SMP系統(tǒng)中產(chǎn)生的”scalable”服務(wù)器。
[Win32多線程程序設(shè)計(jì)] Jim Beveridge & Robert Wiener
 
看來我們完全有理由相信IOCP是大型網(wǎng)絡(luò)架構(gòu)的首選。
那IOCP到底是什么呢？
　　微軟在Winsock2中引入了IOCP這一概念 。IOCP全稱I/O Completion Port，中文譯為I/O完成端口。IOCP是一個(gè)異步I/O的API，它可以高效地將I/O事件通知給應(yīng)用程序。與使用select()或是其它異步方法不同的是，一個(gè)套接字[socket]與一個(gè)完成端口關(guān)聯(lián)了起來，然后就可繼續(xù)進(jìn)行正常的Winsock操作了。然而，當(dāng)一個(gè)事件發(fā)生的時(shí)候，此完成端口就將被操作系統(tǒng)加入一個(gè)隊(duì)列中。然后應(yīng)用程序可以對核心層進(jìn)行查詢以得到此完成端口。
　　這里我要對上面的一些概念略作補(bǔ)充，在解釋[完成]兩字之前，我想先簡單的提一下同步和異步這兩個(gè)概念，邏輯上來講做完一件事后再去做另一件事就是同步，而同時(shí)一起做兩件或兩件以上事的話就是異步了。你也可以拿單線程和多線程來作比喻。但是我們一定要將同步和堵塞，異步和非堵塞區(qū)分開來，所謂的堵塞函數(shù)諸如accept(…)，當(dāng)調(diào)用此函數(shù)后，此時(shí)線程將掛起，直到操作系統(tǒng)來通知它，”HEY兄弟，有人連進(jìn)來了”，那個(gè)掛起的線程將繼續(xù)進(jìn)行工作，也就符合”生產(chǎn)者-消費(fèi)者”模型。堵塞和同步看上去有兩分相似，但卻是完全不同的概念。大家都知道I/O設(shè)備是個(gè)相對慢速的設(shè)備，不論打印機(jī)，調(diào)制解調(diào)器，甚至硬盤，與CPU相比都是奇慢無比的，坐下來等I/O的完成是一件不甚明智的事情，有時(shí)候數(shù)據(jù)的流動(dòng)率非常驚人，把數(shù)據(jù)從你的文件服務(wù)器中以Ethernet速度搬走，其速度可能高達(dá)每秒一百萬字節(jié)，如果你嘗試從文件服務(wù)器中讀取100KB，在用戶的眼光來看幾乎是瞬間完成，但是，要知道，你的線程執(zhí)行這個(gè)命令，已經(jīng)浪費(fèi)了10個(gè)一百萬次CPU周期。所以說，我們一般使用另一個(gè)線程來進(jìn)行I/O。重疊IO[overlapped I/O]是Win32的一項(xiàng)技術(shù)，你可以要求操作系統(tǒng)為你傳送數(shù)據(jù)，并且在傳送完畢時(shí)通知你。這也就是[完成]的含義。這項(xiàng)技術(shù)使你的程序在I/O進(jìn)行過程中仍然能夠繼續(xù)處理事務(wù)。事實(shí)上，操作系統(tǒng)內(nèi)部正是以線程來完成overlapped I/O。你可以獲得線程所有利益，而不需要付出什么痛苦的代價(jià)。
　　完成端口中所謂的[端口]并不是我們在TCP/IP中所提到的端口，可以說是完全沒有關(guān)系。我到現(xiàn)在也沒想通一個(gè)I/O設(shè)備[I/O Device]和端口[IOCP中的Port]有什么關(guān)系。估計(jì)這個(gè)端口也迷惑了不少人。IOCP只不過是用來進(jìn)行讀寫操作，和文件I/O倒是有些類似。既然是一個(gè)讀寫設(shè)備，我們所能要求它的只是在處理讀與寫上的高效。在文章的第三部分你會(huì)輕而易舉的發(fā)現(xiàn)IOCP設(shè)計(jì)的真正用意。

IOCP和網(wǎng)絡(luò)又有什么關(guān)系？
int main()
{
    WSAStartup(MAKEWORD(2, 2), &wsaData);
    ListeningSocket = socket(AF_INET, SOCK_STREAM, 0);
    bind(ListeningSocket, (SOCKADDR*)&ServerAddr, sizeof(ServerAddr));
    listen(ListeningSocket, 5);
    int nlistenAddrLen = sizeof(ClientAddr);
    while(TRUE)
    {
        NewConnection = accept(ListeningSocket, (SOCKADDR*)&ClientAddr, &nlistenAddrLen);
        HANDLE hThread = CreateThread(NULL, 0, ThreadFunc, (void*) NewConnection, 0, &dwTreadId);
        CloseHandle(hThread);
    }
    return 0;
}
　　相信只要寫過網(wǎng)絡(luò)的朋友，應(yīng)該對這樣的結(jié)構(gòu)在熟悉不過了。accept后線程被掛起，等待一個(gè)客戶發(fā)出請求，而后創(chuàng)建新線程來處理請求。當(dāng)新線程處理客戶請求時(shí)，起初的線程循環(huán)回去等待另一個(gè)客戶請求。處理客戶請求的線程處理完畢后終結(jié)。
　　在上述的并發(fā)模型中，對每個(gè)客戶請求都創(chuàng)建了一個(gè)線程。其優(yōu)點(diǎn)在于等待請求的線程只需做很少的工作。大多數(shù)時(shí)間中，該線程在休眠[因?yàn)閞ecv處于堵塞狀態(tài)]。
　　但是當(dāng)并發(fā)模型應(yīng)用在服務(wù)器端[基于Windows NT]，Windows NT小組注意到這些應(yīng)用程序的性能沒有預(yù)料的那么高。特別的，處理很多同時(shí)的客戶請求意味著很多線程并發(fā)地運(yùn)行在系統(tǒng)中。因?yàn)樗羞@些線程都是可運(yùn)行的[沒有被掛起和等待發(fā)生什么事]，Microsoft意識到NT內(nèi)核花費(fèi)了太多的時(shí)間來轉(zhuǎn)換運(yùn)行線程的上下文[Context]，線程就沒有得到很多CPU時(shí)間來做它們的工作。
　　大家可能也都感覺到并行模型的瓶頸在于它為每一個(gè)客戶請求都創(chuàng)建了一個(gè)新線程。創(chuàng)建線程比起創(chuàng)建進(jìn)程開銷要小，但也遠(yuǎn)不是沒有開銷的。
　　我們不妨設(shè)想一下：如果事先開好N個(gè)線程，讓它們在那hold[堵塞]，然后可以將所有用戶的請求都投遞到一個(gè)消息隊(duì)列中去。然后那N個(gè)線程逐一從消息隊(duì)列中去取出消息并加以處理。就可以避免針對每一個(gè)用戶請求都開線程。不僅減少了線程的資源，也提高了線程的利用率。理論上很不錯(cuò)，你想我等泛泛之輩都能想出來的問題，Microsoft又怎會(huì)沒有考慮到呢 !
　　這個(gè)問題的解決方法就是一個(gè)稱為I/O完成端口的內(nèi)核對象，他首次在Windows NT3.5中被引入。
　　其實(shí)我們上面的構(gòu)想應(yīng)該就差不多是IOCP的設(shè)計(jì)機(jī)理。其實(shí)說穿了IOCP不就是一個(gè)消息隊(duì)列嘛！你說這和[端口]這兩字有何聯(lián)系。我的理解就是IOCP最多是應(yīng)用程序和操作系統(tǒng)溝通的一個(gè)接口罷了。
　　至于IOCP的具體設(shè)計(jì)那我也很難說得上來，畢竟我沒看過實(shí)現(xiàn)的代碼，但你完全可以進(jìn)行模擬，只不過性能可能…，如果想深入理解IOCP， Jeffrey Ritchter的Advanced Windows 3rd其中第13章和第14張有很多寶貴的內(nèi)容，你可以拿來窺視一下系統(tǒng)是如何完成這一切的。
 
實(shí)現(xiàn)方法
Microsoft為IOCP提供了相應(yīng)的API函數(shù)，主要的就兩個(gè)，我們逐一的來看一下：
HANDLE CreateIoCompletionPort (
    HANDLE FileHandle,                            // handle to file
    HANDLE ExistingCompletionPort,          // handle to I/O completion port
    ULONG_PTR CompletionKey,               // completion key
    DWORD NumberOfConcurrentThreads  // number of threads to execute concurrently
);
在討論各參數(shù)之前，首先要注意該函數(shù)實(shí)際用于兩個(gè)截然不同的目的：
1．用于創(chuàng)建一個(gè)完成端口對象
2．將一個(gè)句柄[HANDLE]和完成端口關(guān)聯(lián)到一起
　　在創(chuàng)建一個(gè)完成一個(gè)端口的時(shí)候，我們只需要填寫一下NumberOfConcurrentThreads這個(gè)參數(shù)就可以了。它告訴系統(tǒng)一個(gè)完成端口上同時(shí)允許運(yùn)行的線程最大數(shù)。在默認(rèn)情況下，所開線程數(shù)和CPU數(shù)量相同，但經(jīng)驗(yàn)給我們一個(gè)公式：
　　線程數(shù) = CPU數(shù) * 2 + 2
要使完成端口有用，你必須把它同一個(gè)或多個(gè)設(shè)備相關(guān)聯(lián)。這也是調(diào)用CreateIoCompletionPort完成的。你要向該函數(shù)傳遞一個(gè)已有的完成端口的句柄，我們既然要處理網(wǎng)絡(luò)事件，那也就是將客戶的socket作為HANDLE傳進(jìn)去。和一個(gè)完成鍵[對你有意義的一個(gè)32位值，也就是一個(gè)指針，操作系統(tǒng)并不關(guān)心你傳什么]。每當(dāng)你向端口關(guān)聯(lián)一個(gè)設(shè)備時(shí)，系統(tǒng)向該完成端口的設(shè)備列表中加入一條信息紀(jì)錄。
另一個(gè)API就是
BOOL GetQueuedCompletionStatus(
    HANDLE CompletionPort,            // handle to completion port
    LPDWORD lpNumberOfBytes,      // bytes transferred
    PULONG_PTR lpCompletionKey,   // file completion key
    LPOVERLAPPED *lpOverlapped,   // buffer
    DWORD dwMilliseconds       　     // optional timeout value
);
第一個(gè)參數(shù)指出了線程要監(jiān)視哪一個(gè)完成端口。很多服務(wù)應(yīng)用程序只是使用一個(gè)I/O完成端口，所有的I/O請求完成以后的通知都將發(fā)給該端口。簡單的說，GetQueuedCompletionStatus使調(diào)用線程掛起，直到指定的端口的I/O完成隊(duì)列中出現(xiàn)了一項(xiàng)或直到超時(shí)。同I/O完成端口相關(guān)聯(lián)的第3個(gè)數(shù)據(jù)結(jié)構(gòu)是使線程得到完成I/O項(xiàng)中的信息：傳輸?shù)淖止?jié)數(shù)，完成鍵和OVERLAPPED結(jié)構(gòu)的地址。該信息是通過傳遞給GetQueuedCompletionSatatus的lpdwNumberOfBytesTransferred，lpdwCompletionKey和lpOverlapped參數(shù)返回給線程的。
根據(jù)到目前為止已經(jīng)講到的東西，首先來構(gòu)建一個(gè)frame。下面為您說明了如何使用完成端口來開發(fā)一個(gè)echo服務(wù)器。大致如下：
　　1.初始化Winsock
　　2.創(chuàng)建一個(gè)完成端口
　　3.根據(jù)服務(wù)器線程數(shù)創(chuàng)建一定量的線程數(shù)
　　4.準(zhǔn)備好一個(gè)socket進(jìn)行bind然后listen
　　5.進(jìn)入循環(huán)accept等待客戶請求
　　6.創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)容納socket和其他相關(guān)信息
　　7.將連進(jìn)來的socket同完成端口相關(guān)聯(lián)
　　8.投遞一個(gè)準(zhǔn)備接受的請求
以后就不斷的重復(fù)5至8的過程
那好，我們用具體的代碼來展示一下細(xì)節(jié)的操作。
　　至此文章也該告一段落了,我?guī)е隽艘惶诵L(fēng)般的旅游,游覽了所謂的完成端口。
 

posted @ 2010-03-29 21:05 Vincent 閱讀(807) | 評論 (0) | 編輯 收藏

<轉(zhuǎn)>c++智能指針的創(chuàng)建(個(gè)人覺得講的超贊&清晰)

zero 坐在餐桌前，機(jī)械的重復(fù)“夾菜 -> 咀嚼 -> 吞咽”的動(dòng)作序列，臉上用無形的大字寫著：我心不在焉。在他的對面坐著 Solmyr ，慢條斯理的吃著他那份午餐，維持著他一貫很有修養(yǎng)的形象 ——— 或者按照 zero 這些熟悉他本質(zhì)的人的說法：假象。

“怎么了 zero ？胃口不好么？”，基本填飽肚子之后，Solmyr 覺得似乎應(yīng)該關(guān)心一下他的學(xué)徒了。

“呃，沒什么，只是 …… Solmyr ，C++ 為什么不支持垃圾收集呢？（注：垃圾收集是一種機(jī)制，保證動(dòng)態(tài)分配了的內(nèi)存塊會(huì)自動(dòng)釋放，Java 等語言支持這一機(jī)制。）”

Solmyr 嘆了口氣，用一種平靜的眼神盯著 zero ：“是不是在 BBS 上和人吵 C++ 和 Java 哪個(gè)更好？而且吵輸了？我早告訴過你，這種爭論再無聊不過了。”

“呃 …… 是”，zero 不得不承認(rèn) ——— Solmyr 的眼神雖然一點(diǎn)也不銳利，但是卻莫名其妙的讓 zero 產(chǎn)生了微微的恐懼感。

“而且，誰告訴你 C++ 不支持垃圾收集的？”

“啊！Solmyr 你不是開玩笑吧？！”

“zero 你得轉(zhuǎn)變一下觀念。我問你，C++ 支不支持可以動(dòng)態(tài)改變大小的數(shù)組？”

“這 …… 好象也沒有吧？”

“那 vector 是什么東西？”

“呃 ……”

“支持一種特性，并不是說非得把這個(gè)特性加到語法里去，我們也可以選擇用現(xiàn)有的語言機(jī)制實(shí)現(xiàn)一個(gè)庫來支持這個(gè)特征。以垃圾收集為例，這里我們的任務(wù)是要保證每一個(gè)被動(dòng)態(tài)分配的內(nèi)存塊都能夠被釋放，也就是說 ……”，Solmyr 不知從哪里找出了一張紙、一支筆，寫到：

 

int* p = new int; // 1
delete p; // 2

 

“也就是說，對于每一個(gè) 1 ，我們要保證有一個(gè) 2 被調(diào)用，1 和 2 必須成對出現(xiàn)。我來問你，C++ 中有什么東西是由語言本身保證一定成對出現(xiàn)的？”

“……”，zero 露出了努力搜索記憶的表情，不過很明顯一無所獲。

“提示一下，和類的創(chuàng)建有關(guān)。”

“哦！構(gòu)造函數(shù)與析構(gòu)函數(shù)！”

“正確。可惜普通指針沒有構(gòu)造函數(shù)與析構(gòu)函數(shù)，所以我們必須要寫一個(gè)類來加一層包裝，最簡單的就象這樣：”

 

class my_intptr
{
    public:
    int* m_p;

    my_intptr(int* p){ m_p = p; }
    ~my_intptr(){ delete m_p; }
};

…………

my_intptr pi(new int);
*(pi.m_p) = 10;

…………

 

“這里我們可以放心的使用 my_intptr ，不用擔(dān)心內(nèi)存泄漏的問題：一旦 pi 這個(gè)變量被銷毀，我們知道 pi.p 指向的內(nèi)存塊一定會(huì)被釋放。不過如果每次使用 my_intptr 都得去訪問它的成員未免太麻煩了。為此，可以給這個(gè)類加上重載的 * 運(yùn)算符：”

 

class my_intptr
{
    private:
        int* m_p;

    public:
        my_intptr(int* p){ m_p = p; }
        ~my_intptr(){ delete m_p; }

        int& operator*(){ return *m_p; }
};

…………

my_intptr pi;
*pi = 10;
int a = *pi;

…………

 

“現(xiàn)在是不是看起來 my_intptr 就像是一個(gè)真正的指針了？正因?yàn)槿绱耍@種技術(shù)被稱為智能指針。現(xiàn)在我問你，這個(gè)類還缺少哪些東西？”

zero 皺著眉頭，眼睛一眨一眨，看上去就像一臺(tái)慢速電腦正在辛苦的往它的硬盤上拷貝文件。良久，zero 抬起頭來，不太確定的說：“是不是還缺少一個(gè)拷貝構(gòu)造函數(shù)和一個(gè)賦值運(yùn)算符？”

“說說為什么。”，Solmyr 顯然不打算就這樣放過 zero。

“因?yàn)?…… 我記得沒錯(cuò)的話 …… 《50 誡 》（注：指《Effective C++ 2/e》一書）中提到過，如果你的類里面有指針指向動(dòng)態(tài)分配的內(nèi)存，那么一定要為它寫一個(gè)拷貝構(gòu)造函數(shù)和一個(gè)賦值運(yùn)算符 …… 因?yàn)?…… 否則的話，一旦你做了賦值，會(huì)導(dǎo)致兩個(gè)對象的指針指向同一塊內(nèi)存。對了！如果是上面的類，這樣一來會(huì)導(dǎo)致同一個(gè)指針被 delete 兩次！”

“正確。那么我們應(yīng)該怎樣來實(shí)現(xiàn)呢？”

“這簡單，我們用 memcpy 把目標(biāo)指針指向的內(nèi)存中的內(nèi)容拷貝過來。”

“如果我們的智能指針指向一個(gè)類的對象怎么辦？注意，類的對象中可能有指針，不能用 memcpy。”

“那 …… 我們用拷貝構(gòu)造的辦法。”

“如果我們的智能指針指向的對象不能拷貝構(gòu)造怎么辦？它可能有一個(gè)私有的拷貝構(gòu)造函數(shù)。”

“那 ……”，zero 頓了一頓，決定老實(shí)承認(rèn)，“我不知道。”

“問題在哪你知道么？在于你沒有把智能指針看作指針。想象一下，如果我們對一個(gè)指針做賦值，它的含義是什么？”

“呃，我明白了，在這種情況下，應(yīng)該想辦法讓兩個(gè)智能指針指向同一個(gè)對象 …… 可是 Solmyr ，這樣以來豈不是仍然要對同一個(gè)對象刪除兩遍？”

“是的，我們得想辦法解決這個(gè)問題，辦法不只一種。比較好的一種是為每個(gè)指針維護(hù)一個(gè)引用計(jì)數(shù)值，每次賦值或者拷貝構(gòu)造，就讓計(jì)數(shù)值加一，這意味著指向這個(gè)內(nèi)存塊的智能指針又多了一個(gè)；而每有一個(gè)智能指針被銷毀，就讓計(jì)數(shù)值減一，這意味著指向這個(gè)內(nèi)存塊的智能指針少了一個(gè)；一旦計(jì)數(shù)值為 0 ，就釋放內(nèi)存塊。象這樣：”

 

class my_intptr
{
    private:
        int* m_p;
        int* m_count;

    public:
        my_intptr(int* p)
        {
             m_p = p;
             m_count = new int;

            // 初始化計(jì)數(shù)值為 1
            *m_count = 1;
        }
        my_intptr(const my_intptr& rhs) // 拷貝構(gòu)造函數(shù)
       {
            m_p = rhs.m_p; // 指向同一塊內(nèi)存
            m_count = rhs.m_count; // 使用同一個(gè)計(jì)數(shù)值
           (*m_count)++; // 計(jì)數(shù)值加 1
       }
       ~my_intptr()
      {
           (*m_count)--; // 計(jì)數(shù)值減 1
          if( *m_count == 0 ) // 已經(jīng)沒有別的指針指向該內(nèi)存塊了
         {
              delete m_p;
              delete m_count;
         }
      }

      my_intptr& operator=(const my_intptr& rhs)
     {
          if( m_p == rhs.m_p ) // 首先判斷是否本來就指向同一內(nèi)存塊
                return *this; // 是則直接返回

          (*m_count)--; // 計(jì)數(shù)值減 1 ，因?yàn)樵撝羔槻辉僦赶蛟瓉韮?nèi)存塊了
         if( *m_count == 0 ) // 已經(jīng)沒有別的指針指向原來內(nèi)存塊了
         {
              delete m_p;
              delete m_count;
          }

          m_p = rhs.m_p; // 指向同一塊內(nèi)存
          m_count = rhs.m_count; // 使用同一個(gè)計(jì)數(shù)值
         (*m_count)++; // 計(jì)數(shù)值加 1
    }

…………
};

 

“其他部分沒有什么太大變化，我不費(fèi)事了。現(xiàn)在想象一下我們怎樣使用這種智能指針？”，Solmyr 放下了筆，再次拿起了筷子，有些惋惜的發(fā)現(xiàn)他愛吃的肉丸子已經(jīng)冷了。

zero 想象著，有些遲疑。“我們 …… 可以用 new int 表達(dá)式作為構(gòu)造函數(shù)的參數(shù)來構(gòu)造一個(gè)智能指針，然后 …… 然后我們可以任意的賦值，”，他開始抓住了思路，越說越快，“任意的用已經(jīng)存在的智能指針來構(gòu)造新的智能指針，智能指針的賦值運(yùn)算符、拷貝構(gòu)造函數(shù)和析構(gòu)會(huì)保證計(jì)數(shù)值始終等于指向該內(nèi)存塊的智能指針數(shù)。”zero 似乎明白了他看到了怎樣的功能，開始激動(dòng)起來：“然后一旦計(jì)數(shù)值為 0 被分配的內(nèi)存塊就會(huì)釋放！也就是說 …… 有指針指向內(nèi)存塊，它就不釋放，一旦沒有，它就自動(dòng)釋放！太棒了！我們只要一開始正確的初始化智能指針，就可以象普通指針那樣使用它，而且完全不用擔(dān)心內(nèi)存釋放的問題！太棒了！”zero 激動(dòng)的大叫：“這就是垃圾收集！Solmyr ！我們在飯桌上實(shí)現(xiàn)了一個(gè)垃圾收集器！”

Solmyr 很明顯沒有分享 zero 的激動(dòng)：“我在吃飯，你能不能不要大叫‘飯桌上實(shí)現(xiàn)了一個(gè)垃圾收集器’這種倒胃口的話？”頓了一頓，Solmyr 帶著他招牌式的壞笑，以一種可惡的口吻說道：“而且請注意一下自己的形象。”

“嗯？”，zero 回過神來，發(fā)現(xiàn)自己不知什么時(shí)候站了起來，而整個(gè)餐廳里的人都在看著他嘿嘿偷笑，這讓他感覺自己像個(gè)傻瓜。

zero 紅著臉坐下，壓低了聲音問 Solmyr ：“不過 Solmyr ，這確實(shí)是一個(gè)的垃圾收集機(jī)制啊，只要我們把這個(gè)類改成 …… 嗯 …… 改成模板類，象這樣：”zero 抓過了紙筆，寫到：

 

template <typename T>
class my_ptr
{
    private:
    T* m_p;
    int* m_count;
    …………
};

 

“它不就能支持任意類型的指針了嗎？我們就可以把它用在任何地方。”

Solmyr 搖了搖頭：“不，你把問題想的太簡單了。對于簡單的類型，這個(gè)類確實(shí)可以處理的很好，但實(shí)際情況是很復(fù)雜的。考慮一個(gè)典型情況：類 Derived 是類 Base 的派生類，我們希望這樣賦值：”

Base* pb;
Derived pd;
…………
pb = pd;

“你倒說說看，這種情況，怎樣改用上面這個(gè)智能指針來處理？”

“……”，zero 沉默了。

“要實(shí)現(xiàn)一個(gè)完整的垃圾收集機(jī)制并不容易，因?yàn)橛性S多細(xì)節(jié)要考慮。”，Solmyr 開始總結(jié)了，“不過，基本思路就是上面說的這些。值得慶幸的是，目前已經(jīng)有了一個(gè)相當(dāng)成熟的‘引用計(jì)數(shù)’智能指針，boost::shared_ptr。大多數(shù)情況下，我們都可以使用它。另外，除了智能指針之外，還有一些技術(shù)也能夠幫助我們避開釋放內(nèi)存的問題，比如內(nèi)存池。但是，關(guān)鍵在于 ——— ”

Solmyr 再度用那種平靜的眼神盯著 zero ：

“身為 C/C++ 程序員，必須有創(chuàng)造力。那種躺在語言機(jī)制上不思進(jìn)取的人，那種必須要靠語法強(qiáng)制才知道怎樣編程的人，那種沒有別人告訴他該干什么就無所適從的人，不適合這門語言。”

 

 

歡迎訪問夢斷酒醒的博客：http://www.yanzhijun.com

 

本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/ishallwin/archive/2009/09/08/4533145.aspx

posted @ 2010-03-18 13:08 Vincent 閱讀(402) | 評論 (0) | 編輯 收藏

php,include_path

初學(xué)php,用php寫個(gè)小程序
其中寫了一個(gè)connection.php,里面放了一個(gè)class connection.
在這個(gè)文件被include或require的時(shí)候就會(huì)報(bào)錯(cuò)了

然后百度，google許久,用了n種辦法也沒有解決。
不過收獲還是有的，了解了一下include_path
然后無意中隨便寫了個(gè)php,可以被include。
于是我開始懷疑難道我的connection.php不可以被載入？
于是修改connection.php的名稱為conn.php.
發(fā)現(xiàn)沒有問題了。

莫名其妙……
難不成connection是個(gè)關(guān)鍵字什么的？

posted @ 2010-02-21 22:45 Vincent 閱讀(355) | 評論 (0) | 編輯 收藏

<轉(zhuǎn)>兩個(gè)有意思的javascript

     摘要: <html><head><title>盒子游戲</title><style type="text/css">body{font-size:10pt;}.table_back{width:300px;height:300px;}.floor{border:1px solid black;cursor:point...  閱讀全文

posted @ 2009-12-07 11:57 Vincent 閱讀(292) | 評論 (0) | 編輯 收藏

P3368

線段樹..
有個(gè)小地方寫次了..wa了好幾次..
寫了這道題..才感覺自己終于知道線段樹是個(gè)什么東西了..囧

posted @ 2009-11-12 17:49 Vincent 閱讀(200) | 評論 (0) | 編輯 收藏

P2352

這次是用樹狀數(shù)組過的..

posted @ 2009-11-11 21:30 Vincent 閱讀(134) | 評論 (0) | 編輯 收藏

dinic

     摘要: bfs構(gòu)建層次圖dfs找增廣路線形規(guī)劃與網(wǎng)絡(luò)流24則-24.騎士共存問題 在一個(gè)n*n個(gè)方各的國際象棋棋盤上,馬可以攻擊的范圍如圖所示.棋盤上某些方各設(shè)置了障礙,騎士不得進(jìn)入.求,棋盤上最多可以放置多少個(gè)騎士,使得他們彼此互不攻擊.數(shù)據(jù)范圍:1<=n<=200,0<=m<n^2解:對棋盤染色,騎士的跳躍不同色,構(gòu)成2分圖,求最大獨(dú)立集.最大獨(dú)立集=格子數(shù)(參與匹配)-最大...  閱讀全文

posted @ 2009-11-10 21:34 Vincent 閱讀(702) | 評論 (0) | 編輯 收藏

P3273

 

練2分- -

posted @ 2009-11-09 22:00 Vincent 閱讀(118) | 評論 (0) | 編輯 收藏