#
《深度探索C++對象模型》讀書筆記
前 言 Stanley B.Lippman
1． 任何對象模型都需要的三種轉(zhuǎn)換風味：
ü 與編譯器息息相關(guān)的轉(zhuǎn)換
ü 語言語義轉(zhuǎn)換
ü 程序代碼和對象模型的轉(zhuǎn)換
2． C++對象模型的兩種解釋
ü 語言中直接支持面向?qū)ο蟪绦蛟O(shè)計的部分
ü 對于各種支持的底層實現(xiàn)機制
3． C++ class的完整virtual functions在編譯時期就固定下來了，程序員沒有辦法在執(zhí)行期動態(tài)增加或取代其中某一個。這使得虛擬函數(shù)調(diào)用操作得以有快速的派送結(jié)果，付出的卻是執(zhí)行期的彈性。
4． 目前所有編譯器對于virtual function的實現(xiàn)都是使用各個class專屬的virtual table，大小固定，并且在程序執(zhí)行前就構(gòu)造好了。
5． C++對象模型的底層機制并未標準化，它會因?qū)崿F(xiàn)品（編譯器）和時間的變動而不同。
2002-6-23
關(guān)于對象 Object Lessons
1.1 C++對象模式
1． C++在布局以及存取時間上主要的額外負擔是由virtual引起的，包括virtual function機制和virtual base class 機制，還有一些發(fā)生在“一個derived class和其第二或后繼之base class的轉(zhuǎn)換”上的多重繼承。
2． 在C++對象模型中，nonstatic data members被配置于每一個class object之內(nèi)，static data members則被存放在所有的class object之外，static和nonstatic function members也被放在所有的class object之外，virtual functions則以兩個步驟支持：每個class產(chǎn)生一堆指向virtual functions的指針，放在virtual table (vtbl)中；每個class object被添加一個指針vptr，指向相關(guān)的virtual table。每個class所關(guān)聯(lián)的type_info object也經(jīng)由vtbl指出，通常是放在vtbl的第一個slot處。vptr由每一個class的construtor、destructor以及copy assignment operator自動完成。以上模型的主要優(yōu)點在于空間和存取時間的效率，主要缺點是，只要應(yīng)用程序所用到的class object的nonstatic data members有所修改，那么應(yīng)用程序代碼就必須重新編譯。
3． C++最初所采用的繼承模型并不運用任何間接性，base class subobject的data members直接放置于derived class object中。優(yōu)點是提供對base class members緊湊且高效的存取，缺點是base class members的任何改變，都將導(dǎo)致使用其derived class 的object的應(yīng)用程序代碼必須重新編譯。
4． virtual base class的原始模型是在class object中為每一個有關(guān)聯(lián)的virtual base class加上一個指針，其他演化出來的模型不是導(dǎo)入一個virtual base class table，就是擴充原已存在的vtbl，用以維護每一個virtual base class的位置。
1.2關(guān)鍵詞所帶來的差異
1． 可以說關(guān)鍵詞struct的使用伴隨著一個public接口的聲明，也可以說它的用途只是為了方便C程序員遷徙至C++部落。
2． C++中凡處于同一個access section的數(shù)據(jù)，必定保證以聲明次序出現(xiàn)在內(nèi)存布局中，然而被放在多個access sections中的各筆數(shù)據(jù)排列次序就不一定了。同樣，base classes和derived classes的data members的布局也沒有誰先誰后的強制規(guī)定。
3． 組合composition而非繼承才是把C和C++結(jié)合在一起的唯一可行方法。
1.3對象的差異
1． C++程序設(shè)計模型支持三種程序設(shè)計典范programming paradigms：
ü 程序模型procedural model
ü 抽象數(shù)據(jù)類型模型abstract data type model， ADT
ü 面向?qū)ο髷?shù)據(jù)模型object-oriented model，OO
2． 雖然可以直接或間接處理繼承體系中的一個base class object，但只有通過pointer或reference的間接處理，才能支持OO程序設(shè)計所需的多態(tài)性質(zhì)。
3． C++中，多態(tài)只存在于public class體系中，nonpublic的派生行為以及類型為void*的指針可以說是多態(tài)，但它們沒有被語言明白地支持，必須由程序員通過顯示的轉(zhuǎn)型操作來管理。
4． C++以下列方法支持多態(tài)：
ü 經(jīng)由一組隱含的轉(zhuǎn)化操作，如把一個derived class指針轉(zhuǎn)化為一個指向其public base type的指針；
ü 經(jīng)由虛擬機制；
ü 經(jīng)由dynamic_cast和typeid運算符。
5． 多態(tài)的主要用途是經(jīng)由一個共同的接口來影響類型的封裝，這個接口通常被定義在一個抽象的base class中。這個接口是以virtual function機制引發(fā)的，它可以在執(zhí)行期根據(jù)object的真正類型解析出到底是哪一個函數(shù)實體被調(diào)用。
6． 一個class object所需的內(nèi)存，一般而言由以下部分組成：
ü nonstatic data members的總和大小；
ü 任何由于alignment需求而填補上去的空間；
ü 為支持virtual而由內(nèi)部產(chǎn)生的任何額外負擔。
7． 一個pointer或reference，不管它指向哪一種數(shù)據(jù)類型，指針本身所需的內(nèi)存大小是固定的。本質(zhì)上，一個reference通常是以一個指針來實現(xiàn)，而object語法如果轉(zhuǎn)換為間接手法，就需要一個指針。
8． 指向不同類型之指針的差異，既不在其指針表示法不同，也不在其內(nèi)容不同，而是在其所尋址出來的object類型不同，亦即指針類型會教導(dǎo)編譯器如何解釋某個特定地址中的內(nèi)存內(nèi)容及大小。它們之所以支持多態(tài)，是因為它們并不引發(fā)內(nèi)存中任何與類型有關(guān)的內(nèi)存委托操作，會受到改變的只是它們所指向的內(nèi)存的大小和內(nèi)容的解釋方式。
9． 轉(zhuǎn)型cast操作其實是一種編譯指令，大部分情況下它并不改變一個指針所含的真正地址，它只是影響被指向之內(nèi)存的大小和內(nèi)容的解釋方式。
10．一個base class object被直接初始化或指定為一個derived object時，derived object就會被切割sliced，以塞入較小的base type內(nèi)存中，多態(tài)于是不再呈現(xiàn)。一個嚴格的編譯器可以在編譯時期解析一個通過該object而觸發(fā)的virtual function調(diào)用操作，從而回避virtual機制。這時，如果virtual function被定義為inline，則會有效率上的收獲。
11．C++通過class的pointer和reference來支持多態(tài)，這種程序設(shè)計風格就是所謂的OO；C++也支持具體的ADT程序風格，如今被稱為object-based OB，不支持多態(tài)，不支持類型的擴充。
2002-6-25
構(gòu)造函數(shù)語意學(xué)The Semantics of Constructors
1． Jerry Schwarz，iostream函數(shù)庫建構(gòu)師，曾為了讓cin能夠求得一個真假值，于是他為它定義了一個conversion運算符operator int()。但在語句cin << intVal中，其行為出乎意料：程序原本要的是cout而不是cin！但是編譯器卻找到一個正確的詮釋：將cin轉(zhuǎn)型為整型，現(xiàn)在left shift operator <<就可以工作了！這就是所謂的“Schwarz Error”。Jerry最后以operator void *()取代operator int()。
2． 引入關(guān)鍵詞explicit的目的，就是為了提供程序員一種方法，使他們能夠制止單一參數(shù)的constructor被當作一個conversion運算符。其引入是明智的，但其測試應(yīng)該是殘酷的！
2.1 Default Constructor的建構(gòu)操作
1． global objects的內(nèi)存保證會在程序激活的時候被清為0。local objects配置于程序的堆棧中，heap objects配置于自由空間中，都不一定會被清為0，它們的內(nèi)容將是內(nèi)存上次被使用后的遺跡。
2． 在各個不同的版本模塊中，編譯器避免合成出多個default constructor的方法：把合成的default constructor、copy constructor、assignment copy operator都以inline方式完成。一個inline函數(shù)有靜態(tài)鏈接，不會被檔案以外者看到。如果函數(shù)過于復(fù)雜，不適合做成inline，就會合成一個explicit non-inline static實體。
3． 以下四種情況，編譯器必須為未聲明constructor的classes合成一個implicit nontrivial default constructor：帶有default constructor的member class object，帶有default constructor的base class，帶有virtual function，帶有virtual base class。其它各種情況且沒有聲明任何constructor的classes，它們擁有的是implicit trival default constructors，它們實際上并不會被合成出來。
4． 編譯器合成implicit nontrivial default constructor，不過是暗地里作了一些重要的事情以保證程序正確合理地運行。如果程序員提供了多個constructors，但其中都沒有default constructor，編譯器同樣會在這些constructors中插入一些相同功能的代碼，這些代碼都將被安插在explicit user code之前。
2002-6-26
2.2 Copy Constructor的建構(gòu)操作
1． 有三種情況，會以一個class的內(nèi)容作為另一個class object的初值：
ü 對一個object作明確的初始化操作，如：someClass obt = obtb;
ü 一個object被當作參數(shù)交給某個函數(shù)時，如：foo(obt);
ü 當函數(shù)返回一個class object時。
若class設(shè)計者明確定義了一個copy constructor，大部分情況下，該constructor會被調(diào)用。這可能導(dǎo)致一個暫時性的class object的產(chǎn)生或程序代碼的蛻變，或者兩者皆有。
2． 如果class沒有提供一個explicit copy constructor，當class object以相同class的另一個object作為初值時，其內(nèi)部是以所謂的default memberwise initialization手法完成的，即把每一個內(nèi)建的或派生的data member的值，從一個object拷貝到另一個object。不過，它并不會拷貝其中的member class object，而是以遞歸的方式施行memberwise initialization。
3． 一個class object可以從兩種方式復(fù)制得到：初始化和指定，從概念上而言，這兩個操作分別是以copy constructor和copy assignment operator完成的。
4． 如果class沒有聲明一個copy constructor，就會有隱含的聲明implicitly declared或隱含的定義implicitly defined出現(xiàn)。C++把copy constructor分為trivial和nontrivial兩種。只有nontrivial的實體才會被合成出來。決定一個copy constructor是否為trivial的標準在于class是否展現(xiàn)出所謂的“bitwise copy semantics”。
5． 以下四種情況，一個class不展現(xiàn)bitwise copy semantics：
ü class內(nèi)含一個member object而后者的class聲明有或被編譯器合成有一個copy constructor時；
ü class繼承自一個base class而后者存在或被編譯器合成有一個copy constructor時；
ü 當class聲明了一個或多個virtual functions時；
ü 當class派生自一個繼承串鏈，其中有一個或多個virtual base classes時。
前兩種情況中，編譯器必須將member或base class的copy constructors調(diào)用操作安插到被合成的copy constructor中。
6． 一旦一個class object中必須引入vptr，編譯器就必須為它的vptr正確地設(shè)置好初值。此時，該class就不再展現(xiàn)bitwise semantics。
7． 當一個base class object以其derived class object內(nèi)容作初始化操作時，其vptr復(fù)制操作必須保證安全。
8． 每一個編譯器對于虛擬繼承的承諾，都表示必須讓derived class object中的virtual base class subobject的位置在執(zhí)行期準備妥當。維護位置的完整性是編譯器的責任。
2002-6-27
2.3 程序轉(zhuǎn)化語意學(xué)
1． 每一個明確的初始化操作都會有兩個必要的程序轉(zhuǎn)化階段：先重寫每一個定義，剝除其中的初始化操作，然后安插class的copy constructor調(diào)用操作。
2． 把一個class object當作參數(shù)傳給一個函數(shù)或是作為一個函數(shù)的返回值，相當于以下形式的初始化操作：
X xx = arg; 其中xx代表形式參數(shù)或返回值，而arg代表真正的參數(shù)值。
3． 函數(shù)定義如下：X bar(){X xx; return xx;}，bar()的返回值通過一個雙階轉(zhuǎn)化從局部對象xx中拷貝出來：
ü 首先為bar添加一個額外參數(shù)，類型是class object的一個reference，這個參數(shù)用來放置被拷貝構(gòu)建而得的返回值。
ü 然后在return指令之前安插一個copy constructor調(diào)用操作，以便將欲傳回之object的內(nèi)容當作上述新增參數(shù)的初值，同時重寫函數(shù)使它不返回任何值。
4． Named Return Value(NRV)優(yōu)化如今被視為是標準C++編譯器的一個義不容辭的優(yōu)化操作，它的特點是直接操作新添加的額外參數(shù)。注意只有copy constructor的出現(xiàn)才會激活C++編譯器的NRV優(yōu)化！NRV優(yōu)化雖然極大地改善了效率，但還是飽受批評：一是優(yōu)化由編譯器默默完成，而是否完成以及其完成程度完全透明；二是一旦函數(shù)變得比較復(fù)雜，優(yōu)化就變得較難施行；三是優(yōu)化由可能使程序產(chǎn)生錯誤——有時并不是對稱地調(diào)用constructor和destructor，而是copy constructor未被調(diào)用！
5． 在編譯器提供NRV優(yōu)化的前提下，如果可以預(yù)見class需要大量的memberwise初始化操作，比如以by value的方式傳回objects，那么提供一個explicit inline copy constructor的函數(shù)實體就非常合理。此種情況下，沒有必要同時提供explicit assignment operator定義。
6． copy constructor的應(yīng)用迫使編譯器多多少少對程序代碼作部分優(yōu)化，尤其是當一個函數(shù)以by value的方式傳回一個class object，而該class有一個copy constructor（或定義或合成）時，無論在函數(shù)的定義還是在使用上將導(dǎo)致深奧的程序轉(zhuǎn)化。此外，編譯器將實施NRV優(yōu)化。
7． 注意正確使用memset()和memcpy()，它們都只有在classes不含任何由編譯器產(chǎn)生的內(nèi)部members如vptr時才能有效運行！
2002-6-30
2.4 成員初始化列表
1． 當寫下一個constructor時，就有機會設(shè)定class members的初值。不是經(jīng)由member initialization list，就是在constructor函數(shù)本身之內(nèi)。
2． 下列情況，為了讓程序能被順利編譯，必須使用member initialization list：
ü 初始化一個reference member時；
ü 初始化一個const member時；
ü 調(diào)用一個base class的constructor，而它擁有一組參數(shù)時；
ü 調(diào)用一個member class的constructor，而它擁有一組參數(shù)時。
3． 編譯器會對initialization list一一處理并可能重新排序，以反映出members的聲明次序，它會安插一些代碼到constructor內(nèi)，并置于任何explicit user code之前。
4． 一個忠告：請使用“存在于constructor體內(nèi)的一個member”，而不是“存在于member initialization list中的一個member”，來為另一個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． 一個empty class如class X{}，它有一個隱晦的1 byte，那是被編譯器安插進去的一個char，使得這個class的兩個objects得以在內(nèi)存中配置獨一無二的地址。
2． Y和Z的大小受到三個因素的影響：
ü 語言本身所造成的額外負擔overhead。語言支持virtual base classes時導(dǎo)致的額外負擔反映在某種形式的指針身上，它要么指向virtual base class subobject，要么指向一個存放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最開頭的一部分，它不用會任何的額外空間，也就是前面提到的1 byte。
ü Alignment的限制。Alignment就是將數(shù)值調(diào)整到某數(shù)的整數(shù)倍，在32位計算機上，通常該數(shù)為4 bytes(32位)，以使bus的運輸量達到最高效率。
3． 一個virtual base class subobject只會在derived class中存在一份實體，不管它在class繼承體系中出現(xiàn)了多少次，class A的大小由下列幾點決定：
ü 被大家共享的唯一一個class X實體，大小為1 byte；
ü Base Y、Z的大小減去因virual base class而配置的大小；
ü class A自己的大小；
ü class A的alignment數(shù)量。
4． C++ standard并不強制規(guī)定base class subobjects、不同存取級別的data members的排列次序這種瑣碎細節(jié)，它也不規(guī)定virtual function以及virtual base classes的實現(xiàn)細節(jié)。
5． C++對象模型盡量以空間優(yōu)化和存取速度優(yōu)化來表現(xiàn)nonstatic data members，并且保持和C語言struct數(shù)據(jù)配置的兼容性。它把數(shù)據(jù)直接存放在每一個class object中，對于繼承而來的nonstatic data members，不管是virtual或nonvirtual base class也是如此。至于static data members則被放置在程序的一個global data segment中，不會影響個別class object的大小。static data member永遠只存在一份實體，但是一個template class的static data member的行為稍有不同。
3.1 Data Member的綁定
inline member function軀體內(nèi)的data member綁定操作，會在整個class聲明完成后才發(fā)生，而argument list中的名稱還是會在它們第一次遭遇時被適當?shù)貨Q議resolved完成。基于這種狀況，請始終把nested type聲明放在class的起始處。
2002-7-2
3.2 Data Member的布局
1． 每一個private、protected、public區(qū)段就是一個access section。C++ Standard要求，在同一個access section中，members的排列只需滿足“較晚出現(xiàn)的members在class object中有較高的地址”這一條件即可。也就是說各個members并不一定的連續(xù)排列，alignment可能需要的bytes以及編譯器可能合成供內(nèi)部使用的data members都可能介于被聲明的members之間。
2． C++ Standard也允許編譯器將多個access sections之中的data members自由排列，不必在乎它們出現(xiàn)在class聲明中的次序。當前各家編譯器都是把一個以上的access sections連鎖在一起，依照聲明的次序成為一個連續(xù)區(qū)塊。access sections的多寡不會導(dǎo)致額外負擔。
3． vptr傳統(tǒng)上會被放在所有明確聲明的members的最后，不過如今也有一些編譯器把vptr放在class object的最前端。
4． 一個用來判斷哪一個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)載請標明出處：http://blog.csdn.net/xjtuse_mal/archive/2007/03/01/1517806.aspx
POSIX threads(簡稱Pthreads)是在多核平臺上進行并行編程的一套常用的API。線程同步(Thread Synchronization)是并行編程中非常重要的通訊手段，其中最典型的應(yīng)用就是用Pthreads提供的鎖機制(lock)來對多個線程之間共 享的臨界區(qū)(Critical Section)進行保護(另一種常用的同步機制是barrier)。
Pthreads提供了多種鎖機制：
(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);
從實現(xiàn)原理上來講，Mutex屬于sleep-waiting類型的鎖。例如在一個雙核的機器上有兩個線程(線程A和線程B)，它們分別運行在Core0和Core1上。假設(shè)線程A想要通過pthread_mutex_lock操作去得到一個臨界區(qū)的鎖，而此時這個鎖正被線程B所持有，那么線程A就會被阻塞(blocking)，Core0 會在此時進行上下文切換(Context Switch)將線程A置于等待隊列中，此時Core0就可以運行其他的任務(wù)(例如另一個線程C)而不必進行忙等待。而Spin lock則不然，它屬于busy-waiting類型的鎖，如果線程A是使用pthread_spin_lock操作去請求鎖，那么線程A就會一直在 Core0上進行忙等待并不停的進行鎖請求，直到得到這個鎖為止。
如果大家去查閱Linux glibc中對pthreads API的實現(xiàn)NPTL(Native POSIX Thread Library) 的源碼的話(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我們系統(tǒng)中NPTL的版本號)，就會發(fā)現(xiàn)pthread_mutex_lock()操作如果沒有鎖成功的話就會調(diào)用system_wait()的系統(tǒng)調(diào)用并將當前線程加入該mutex的等待隊列里。而spin lock則可以理解為在一個while(1)循環(huán)中用內(nèi)嵌的匯編代碼實現(xiàn)的鎖操作(印象中看過一篇論文介紹說在linux內(nèi)核中spin lock操作只需要兩條CPU指令，解鎖操作只用一條指令就可以完成)。有興趣的朋友可以參考另一個名為sanos的微內(nèi)核中pthreds API的實現(xiàn)：mutex.c spinlock.c，盡管與NPTL中的代碼實現(xiàn)不盡相同，但是因為它的實現(xiàn)非常簡單易懂，對我們理解spin lock和mutex的特性還是很有幫助的。
那么在實際編程中mutex和spin lcok哪個的性能更好呢？我們知道spin lock在Linux內(nèi)核中有非常廣泛的利用，那么這是不是說明spin lock的性能更好呢？下面讓我們來用實際的代碼測試一下（請確保你的系統(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 }
該程序運行過程如下：主線程先初始化一個list結(jié)構(gòu)，并根據(jù)LOOPS的值將對應(yīng)數(shù)量的entry插入該list，之后創(chuàng)建兩個新線程，它們都執(zhí)行consumer()這個任務(wù)。兩個被創(chuàng)建的新線程同時對這個list進行pop操作。主線程會計算從創(chuàng)建兩個新線程到兩個新線程結(jié)束之間所用的時間，輸出為下文中的”Result “。
測試機器參數(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時間，mutex版本花費了更多的系統(tǒng)調(diào)用時間，這就是因為mutex會在鎖沖突時調(diào)用system wait造成的。
但是，是不是說spin lock就一定更好了呢？讓我們再來看一個鎖沖突程度非常劇烈的實例程序：
查看源代碼打印幫助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 }
這個程序的特征就是臨界區(qū)非常大，這樣兩個線程的鎖競爭會非常的劇烈。當然這個是一個極端情況，實際應(yīng)用程序中臨界區(qū)不會如此大，鎖競爭也不會如此激烈。測試結(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
另外一個值得注意的細節(jié)是spin lock耗費了更多的user time。這就是因為兩個線程分別運行在兩個核上，大部分時間只有一個線程能拿到鎖，所以另一個線程就一直在它運行的core上進行忙等待，CPU占用率一直是100%；而mutex則不同，當對鎖的請求失敗后上下文切換就會發(fā)生，這樣就能空出一個核來進行別的運算任務(wù)了。（其實這種上下文切換對已經(jīng)拿著鎖的那個線程性能也是有影響的，因為當該線程釋放該鎖時它需要通知操作系統(tǒng)去喚醒那些被阻塞的線程，這也是額外的開銷）
總結(jié)
（1）Mutex適合對鎖操作非常頻繁的場景，并且具有更好的適應(yīng)性。盡管相比spin lock它會花費更多的開銷（主要是上下文切換），但是它能適合實際開發(fā)中復(fù)雜的應(yīng)用場景，在保證一定性能的前提下提供更大的靈活度。
（2）spin lock的lock/unlock性能更好(花費更少的cpu指令)，但是它只適應(yīng)用于臨界區(qū)運行時間很短的場景。而在實際軟件開發(fā)中，除非程序員對自己的程序的鎖操作行為非常的了解，否則使用spin lock不是一個好主意(通常一個多線程程序中對鎖的操作有數(shù)以萬次，如果失敗的鎖操作(contended lock requests)過多的話就會浪費很多的時間進行空等待)。
（3）更保險的方法或許是先（保守的）使用 Mutex，然后如果對性能還有進一步的需求，可以嘗試使用spin lock進行調(diào)優(yōu)。畢竟我們的程序不像Linux kernel那樣對性能需求那么高(Linux Kernel最常用的鎖操作是spin lock和rw lock)。
2010年3月3日補記：這個觀點在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 )都可以得到當前線程的id:)
轉(zhuǎn)載請注明來自: [url]www.parallellabs.com[/url]
------------------------------------------------------------------------------
spinlock與linux內(nèi)核調(diào)度的關(guān)系
作者：劉洪濤，華清遠見嵌入式培訓(xùn)中心高級講師，ARM公司授權(quán)ATC講師。
廣告插播信息
維庫最新熱賣芯片：
關(guān)于自旋鎖用法介紹的文章，已經(jīng)有很多，但有些細節(jié)的地方點的還不夠透。我這里就把我個人認為大家容易有疑問的地方拿出來討論一下。
一、自旋鎖（spinlock）簡介
自旋鎖在同一時刻只能被最多一個內(nèi)核任務(wù)持有，所以一個時刻只有一個線程允許存在于臨界區(qū)中。這點可以應(yīng)用在多處理機器、或運行在單處理器上的搶占式內(nèi)核中需要的鎖定服務(wù)。
二、信號量簡介
這里也介紹下信號量的概念，因為它的用法和自旋鎖有相似的地方。
Linux中的信號量是一種睡眠鎖。如果有一個任務(wù)試圖獲得一個已被持有的信號量時，信號量會將其推入等待隊列，然后讓其睡眠。這時處理器獲得自由去執(zhí)行其它代碼。當持有信號量的進程將信號量釋放后，在等待隊列中的一個任務(wù)將被喚醒，從而便可以獲得這個信號量。
三、自旋鎖和信號量對比
在很多地方自旋鎖和信號量可以選擇任何一個使用，但也有一些地方只能選擇某一種。下面對比一些兩者的用法。
表1-1自旋鎖和信號量對比
四、自旋鎖與linux內(nèi)核進程調(diào)度關(guān)系
我們討論下表1-1中的第3種情況（其它幾種情況比較好理解），如果臨界區(qū)可能包含引起睡眠的代碼則不能使用自旋鎖，否則可能引起死鎖。
那么為什么信號量保護的代碼可以睡眠而自旋鎖就不能呢？
先看下自旋鎖的實現(xiàn)方法吧，自旋鎖的基本形式如下：
spin_lock(&mr_lock);
//臨界區(qū)
spin_unlock(&mr_lock);
跟蹤一下spin_lock(&mr_lock)的實現(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()”，這個調(diào)用的功能是“關(guān)搶占”（在spin_unlock中會重新開啟搶占功能）。從中可以看出，使用自旋鎖保護的區(qū)域是工作在非搶占的狀態(tài)；即使獲取不到鎖，在“自旋”狀態(tài)也是禁止搶占的。了解到這，我想咱們應(yīng)該能夠理解為何自旋鎖保護的代碼不能睡眠了。試想一下，如果在自旋鎖保護的代碼中間睡眠，此時發(fā)生進程調(diào)度，則可能另外一個進程會再次調(diào)用spinlock保護的這段代碼。而我們現(xiàn)在知道了即使在獲取不到鎖的“自旋”狀態(tài)，也是禁止搶占的，而“自旋”又是動態(tài)的，不會再睡眠了，也就是說在這個處理器上不會再有進程調(diào)度發(fā)生了，那么死鎖自然就發(fā)生了。
咱們可以總結(jié)下自旋鎖的特點：
● 單處理器非搶占內(nèi)核下：自旋鎖會在編譯時被忽略；
● 單處理器搶占內(nèi)核下：自旋鎖僅僅當作一個設(shè)置內(nèi)核搶占的開關(guān)；
● 多處理器下：此時才能完全發(fā)揮出自旋鎖的作用，自旋鎖在內(nèi)核中主要用來防止多處理器中并發(fā)訪問臨界區(qū)，防止內(nèi)核搶占造成的競爭。
五、linux搶占發(fā)生的時間
最后在了解下linux搶占發(fā)生的時間，搶占分為用戶搶占和內(nèi)核搶占。
用戶搶占在以下情況下產(chǎn)生：
● 從系統(tǒng)調(diào)用返回用戶空間
● 從中斷處理程序返回用戶空間
內(nèi)核搶占會發(fā)生在：
● 當從中斷處理程序返回內(nèi)核空間的時候，且當時內(nèi)核具有可搶占性；
● 當內(nèi)核代碼再一次具有可搶占性的時候。（如:spin_unlock時）
● 如果內(nèi)核中的任務(wù)顯式的調(diào)用schedule()
● 如果內(nèi)核中的任務(wù)阻塞。
基本的進程調(diào)度就是發(fā)生在時鐘中斷后，并且發(fā)現(xiàn)進程的時間片已經(jīng)使用完了，則發(fā)生進程搶占。通常我們會利用中斷處理程序返回內(nèi)核空間的時候可以進行內(nèi)核搶占這個特性來提高一些I/O操作的實時性，如：當I/O事件發(fā)生的是時候，對應(yīng)的中斷處理程序被激活，當它發(fā)現(xiàn)有進程在等待這個I/O事件的時候，它會激活等待進程，并且設(shè)置當前正在執(zhí)行進程的need_resched標志，這樣在中斷處理程序返回的時候，調(diào)度程序被激活，原來在等待I/O事件的進程（很可能）獲得執(zhí)行權(quán)，從而保證了對I/O事件的相對快速響應(yīng)（毫秒級）。可以看出，在I/O事件發(fā)生的時候，I/O事件的處理進程會搶占當前進程，系統(tǒng)的響應(yīng)速度與調(diào)度時間片的長度無關(guān)。
理解I/O Completion Port
摘自:http://gzlyb.cnblogs.com/archive/2005/09/30/247049.aspx
歡迎閱讀此篇IOCP教程。我將先給出IOCP的定義然后給出它的實現(xiàn)方法，最后剖析一個Echo程序來為您撥開IOCP的謎云，除去你心中對IOCP的煩惱。OK，但我不能保證你明白IOCP的一切，但我會盡我最大的努力。以下是我會在這篇文章中提到的相關(guān)技術(shù)：
I/O端口
同步/異步
堵塞/非堵塞
服務(wù)端/客戶端
多線程程序設(shè)計
Winsock API 2.0
在這之前，我曾經(jīng)開發(fā)過一個項目，其中一塊需要網(wǎng)絡(luò)支持，當時還考慮到了代碼的可移植性，只要使用select,connect,accept,listen,send還有recv,再加上幾個#ifdef的封裝以用來處理Winsock和BSD套接字[socket]中間的不兼容性，一個網(wǎng)絡(luò)子系統(tǒng)只用了幾個小時很少的代碼就寫出來了，至今還讓我很回味。那以后很長時間也就沒再碰了。
前些日子，我們策劃做一個網(wǎng)絡(luò)游戲，我主動承擔下網(wǎng)絡(luò)這一塊，想想這還不是小case,心里偷著樂啊。網(wǎng)絡(luò)游戲好啊，網(wǎng)絡(luò)游戲為成百上千的玩家提供了樂趣和令人著秘的游戲體驗，他們在線上互相戰(zhàn)斗或是加入隊伍去戰(zhàn)勝共同的敵人。我信心滿滿的準備開寫我的網(wǎng)絡(luò)，于是乎，發(fā)現(xiàn)過去的阻塞同步模式模式根本不能拿到一個巨量多玩家[MMP]的架構(gòu)中去，直接被否定掉了。于是乎，就有了IOCP，如果能過很輕易而舉的搞掂IOCP，也就不會有這篇教程了。下面請諸位跟隨我進入正題。
什么是IOCP？
先讓我們看看對IOCP的評價
I/O完成端口可能是Win32提供的最復(fù)雜的內(nèi)核對象。
[Advanced Windows 3rd] Jeffrey Richter
這是[IOCP]實現(xiàn)高容量網(wǎng)絡(luò)服務(wù)器的最佳方法。
[Windows Sockets2.0:Write Scalable Winsock Apps Using Completion Ports]
Microsoft Corporation
完成端口模型提供了最好的伸縮性。這個模型非常適用來處理數(shù)百乃至上千個套接字。
[Windows網(wǎng)絡(luò)編程2nd] Anthony Jones & Jim Ohlund
I/O completion ports特別顯得重要，因為它們是唯一適用于高負載服務(wù)器[必須同時維護許多連接線路]的一個技術(shù)。Completion ports利用一些線程，幫助平衡由I/O請求所引起的負載。這樣的架構(gòu)特別適合用在SMP系統(tǒng)中產(chǎn)生的”scalable”服務(wù)器。
[Win32多線程程序設(shè)計] Jim Beveridge & Robert Wiener
看來我們完全有理由相信IOCP是大型網(wǎng)絡(luò)架構(gòu)的首選。
那IOCP到底是什么呢？
微軟在Winsock2中引入了IOCP這一概念 。IOCP全稱I/O Completion Port，中文譯為I/O完成端口。IOCP是一個異步I/O的API，它可以高效地將I/O事件通知給應(yīng)用程序。與使用select()或是其它異步方法不同的是，一個套接字[socket]與一個完成端口關(guān)聯(lián)了起來，然后就可繼續(xù)進行正常的Winsock操作了。然而，當一個事件發(fā)生的時候，此完成端口就將被操作系統(tǒng)加入一個隊列中。然后應(yīng)用程序可以對核心層進行查詢以得到此完成端口。
這里我要對上面的一些概念略作補充，在解釋[完成]兩字之前，我想先簡單的提一下同步和異步這兩個概念，邏輯上來講做完一件事后再去做另一件事就是同步，而同時一起做兩件或兩件以上事的話就是異步了。你也可以拿單線程和多線程來作比喻。但是我們一定要將同步和堵塞，異步和非堵塞區(qū)分開來，所謂的堵塞函數(shù)諸如accept(…)，當調(diào)用此函數(shù)后，此時線程將掛起，直到操作系統(tǒng)來通知它，”HEY兄弟，有人連進來了”，那個掛起的線程將繼續(xù)進行工作，也就符合”生產(chǎn)者-消費者”模型。堵塞和同步看上去有兩分相似，但卻是完全不同的概念。大家都知道I/O設(shè)備是個相對慢速的設(shè)備，不論打印機，調(diào)制解調(diào)器，甚至硬盤，與CPU相比都是奇慢無比的，坐下來等I/O的完成是一件不甚明智的事情，有時候數(shù)據(jù)的流動率非常驚人，把數(shù)據(jù)從你的文件服務(wù)器中以Ethernet速度搬走，其速度可能高達每秒一百萬字節(jié)，如果你嘗試從文件服務(wù)器中讀取100KB，在用戶的眼光來看幾乎是瞬間完成，但是，要知道，你的線程執(zhí)行這個命令，已經(jīng)浪費了10個一百萬次CPU周期。所以說，我們一般使用另一個線程來進行I/O。重疊IO[overlapped I/O]是Win32的一項技術(shù)，你可以要求操作系統(tǒng)為你傳送數(shù)據(jù)，并且在傳送完畢時通知你。這也就是[完成]的含義。這項技術(shù)使你的程序在I/O進行過程中仍然能夠繼續(xù)處理事務(wù)。事實上，操作系統(tǒng)內(nèi)部正是以線程來完成overlapped I/O。你可以獲得線程所有利益，而不需要付出什么痛苦的代價。
完成端口中所謂的[端口]并不是我們在TCP/IP中所提到的端口，可以說是完全沒有關(guān)系。我到現(xiàn)在也沒想通一個I/O設(shè)備[I/O Device]和端口[IOCP中的Port]有什么關(guān)系。估計這個端口也迷惑了不少人。IOCP只不過是用來進行讀寫操作，和文件I/O倒是有些類似。既然是一個讀寫設(shè)備，我們所能要求它的只是在處理讀與寫上的高效。在文章的第三部分你會輕而易舉的發(fā)現(xiàn)IOCP設(shè)計的真正用意。
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后線程被掛起，等待一個客戶發(fā)出請求，而后創(chuàng)建新線程來處理請求。當新線程處理客戶請求時，起初的線程循環(huán)回去等待另一個客戶請求。處理客戶請求的線程處理完畢后終結(jié)。
在上述的并發(fā)模型中，對每個客戶請求都創(chuàng)建了一個線程。其優(yōu)點在于等待請求的線程只需做很少的工作。大多數(shù)時間中，該線程在休眠[因為recv處于堵塞狀態(tài)]。
但是當并發(fā)模型應(yīng)用在服務(wù)器端[基于Windows NT]，Windows NT小組注意到這些應(yīng)用程序的性能沒有預(yù)料的那么高。特別的，處理很多同時的客戶請求意味著很多線程并發(fā)地運行在系統(tǒng)中。因為所有這些線程都是可運行的[沒有被掛起和等待發(fā)生什么事]，Microsoft意識到NT內(nèi)核花費了太多的時間來轉(zhuǎn)換運行線程的上下文[Context]，線程就沒有得到很多CPU時間來做它們的工作。
大家可能也都感覺到并行模型的瓶頸在于它為每一個客戶請求都創(chuàng)建了一個新線程。創(chuàng)建線程比起創(chuàng)建進程開銷要小，但也遠不是沒有開銷的。
我們不妨設(shè)想一下：如果事先開好N個線程，讓它們在那hold[堵塞]，然后可以將所有用戶的請求都投遞到一個消息隊列中去。然后那N個線程逐一從消息隊列中去取出消息并加以處理。就可以避免針對每一個用戶請求都開線程。不僅減少了線程的資源，也提高了線程的利用率。理論上很不錯，你想我等泛泛之輩都能想出來的問題，Microsoft又怎會沒有考慮到呢 !
這個問題的解決方法就是一個稱為I/O完成端口的內(nèi)核對象，他首次在Windows NT3.5中被引入。
其實我們上面的構(gòu)想應(yīng)該就差不多是IOCP的設(shè)計機理。其實說穿了IOCP不就是一個消息隊列嘛！你說這和[端口]這兩字有何聯(lián)系。我的理解就是IOCP最多是應(yīng)用程序和操作系統(tǒng)溝通的一個接口罷了。
至于IOCP的具體設(shè)計那我也很難說得上來，畢竟我沒看過實現(xiàn)的代碼，但你完全可以進行模擬，只不過性能可能…，如果想深入理解IOCP， Jeffrey Ritchter的Advanced Windows 3rd其中第13章和第14張有很多寶貴的內(nèi)容，你可以拿來窺視一下系統(tǒng)是如何完成這一切的。
實現(xiàn)方法
Microsoft為IOCP提供了相應(yīng)的API函數(shù)，主要的就兩個，我們逐一的來看一下：
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ù)實際用于兩個截然不同的目的：
1．用于創(chuàng)建一個完成端口對象
2．將一個句柄[HANDLE]和完成端口關(guān)聯(lián)到一起
在創(chuàng)建一個完成一個端口的時候，我們只需要填寫一下NumberOfConcurrentThreads這個參數(shù)就可以了。它告訴系統(tǒng)一個完成端口上同時允許運行的線程最大數(shù)。在默認情況下，所開線程數(shù)和CPU數(shù)量相同，但經(jīng)驗給我們一個公式：
線程數(shù) = CPU數(shù) * 2 + 2
要使完成端口有用，你必須把它同一個或多個設(shè)備相關(guān)聯(lián)。這也是調(diào)用CreateIoCompletionPort完成的。你要向該函數(shù)傳遞一個已有的完成端口的句柄，我們既然要處理網(wǎng)絡(luò)事件，那也就是將客戶的socket作為HANDLE傳進去。和一個完成鍵[對你有意義的一個32位值，也就是一個指針，操作系統(tǒng)并不關(guān)心你傳什么]。每當你向端口關(guān)聯(lián)一個設(shè)備時，系統(tǒng)向該完成端口的設(shè)備列表中加入一條信息紀錄。
另一個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
);
第一個參數(shù)指出了線程要監(jiān)視哪一個完成端口。很多服務(wù)應(yīng)用程序只是使用一個I/O完成端口，所有的I/O請求完成以后的通知都將發(fā)給該端口。簡單的說，GetQueuedCompletionStatus使調(diào)用線程掛起，直到指定的端口的I/O完成隊列中出現(xiàn)了一項或直到超時。同I/O完成端口相關(guān)聯(lián)的第3個數(shù)據(jù)結(jié)構(gòu)是使線程得到完成I/O項中的信息：傳輸?shù)淖止?jié)數(shù)，完成鍵和OVERLAPPED結(jié)構(gòu)的地址。該信息是通過傳遞給GetQueuedCompletionSatatus的lpdwNumberOfBytesTransferred，lpdwCompletionKey和lpOverlapped參數(shù)返回給線程的。
根據(jù)到目前為止已經(jīng)講到的東西，首先來構(gòu)建一個frame。下面為您說明了如何使用完成端口來開發(fā)一個echo服務(wù)器。大致如下：
1.初始化Winsock
2.創(chuàng)建一個完成端口
3.根據(jù)服務(wù)器線程數(shù)創(chuàng)建一定量的線程數(shù)
4.準備好一個socket進行bind然后listen
5.進入循環(huán)accept等待客戶請求
6.創(chuàng)建一個數(shù)據(jù)結(jié)構(gòu)容納socket和其他相關(guān)信息
7.將連進來的socket同完成端口相關(guān)聯(lián)
8.投遞一個準備接受的請求
以后就不斷的重復(fù)5至8的過程
那好，我們用具體的代碼來展示一下細節(jié)的操作。
至此文章也該告一段落了,我?guī)е隽艘惶诵L般的旅游,游覽了所謂的完成端口。
zero 坐在餐桌前，機械的重復(fù)“夾菜 -> 咀嚼 -> 吞咽”的動作序列，臉上用無形的大字寫著：我心不在焉。在他的對面坐著 Solmyr ，慢條斯理的吃著他那份午餐，維持著他一貫很有修養(yǎng)的形象 ——— 或者按照 zero 這些熟悉他本質(zhì)的人的說法：假象。
“怎么了 zero ？胃口不好么？”，基本填飽肚子之后，Solmyr 覺得似乎應(yīng)該關(guān)心一下他的學(xué)徒了。
“呃，沒什么，只是 …… Solmyr ，C++ 為什么不支持垃圾收集呢？（注：垃圾收集是一種機制，保證動態(tài)分配了的內(nèi)存塊會自動釋放，Java 等語言支持這一機制。）”
Solmyr 嘆了口氣，用一種平靜的眼神盯著 zero ：“是不是在 BBS 上和人吵 C++ 和 Java 哪個更好？而且吵輸了？我早告訴過你，這種爭論再無聊不過了。”
“呃 …… 是”，zero 不得不承認 ——— Solmyr 的眼神雖然一點也不銳利，但是卻莫名其妙的讓 zero 產(chǎn)生了微微的恐懼感。
“而且，誰告訴你 C++ 不支持垃圾收集的？”
“啊！Solmyr 你不是開玩笑吧？！”
“zero 你得轉(zhuǎn)變一下觀念。我問你，C++ 支不支持可以動態(tài)改變大小的數(shù)組？”
“這 …… 好象也沒有吧？”
“那 vector 是什么東西？”
“呃 ……”
“支持一種特性，并不是說非得把這個特性加到語法里去，我們也可以選擇用現(xiàn)有的語言機制實現(xiàn)一個庫來支持這個特征。以垃圾收集為例，這里我們的任務(wù)是要保證每一個被動態(tài)分配的內(nèi)存塊都能夠被釋放，也就是說 ……”，Solmyr 不知從哪里找出了一張紙、一支筆，寫到：
int* p = new int; // 1
delete p; // 2
“也就是說，對于每一個 1 ，我們要保證有一個 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ù)，所以我們必須要寫一個類來加一層包裝，最簡單的就象這樣：”
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 ，不用擔心內(nèi)存泄漏的問題：一旦 pi 這個變量被銷毀，我們知道 pi.p 指向的內(nèi)存塊一定會被釋放。不過如果每次使用 my_intptr 都得去訪問它的成員未免太麻煩了。為此，可以給這個類加上重載的 * 運算符：”
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 就像是一個真正的指針了？正因為如此，這種技術(shù)被稱為智能指針。現(xiàn)在我問你，這個類還缺少哪些東西？”
zero 皺著眉頭，眼睛一眨一眨，看上去就像一臺慢速電腦正在辛苦的往它的硬盤上拷貝文件。良久，zero 抬起頭來，不太確定的說：“是不是還缺少一個拷貝構(gòu)造函數(shù)和一個賦值運算符？”
“說說為什么。”，Solmyr 顯然不打算就這樣放過 zero。
“因為 …… 我記得沒錯的話 …… 《50 誡 》（注：指《Effective C++ 2/e》一書）中提到過，如果你的類里面有指針指向動態(tài)分配的內(nèi)存，那么一定要為它寫一個拷貝構(gòu)造函數(shù)和一個賦值運算符 …… 因為 …… 否則的話，一旦你做了賦值，會導(dǎo)致兩個對象的指針指向同一塊內(nèi)存。對了！如果是上面的類，這樣一來會導(dǎo)致同一個指針被 delete 兩次！”
“正確。那么我們應(yīng)該怎樣來實現(xiàn)呢？”
“這簡單，我們用 memcpy 把目標指針指向的內(nèi)存中的內(nèi)容拷貝過來。”
“如果我們的智能指針指向一個類的對象怎么辦？注意，類的對象中可能有指針，不能用 memcpy。”
“那 …… 我們用拷貝構(gòu)造的辦法。”
“如果我們的智能指針指向的對象不能拷貝構(gòu)造怎么辦？它可能有一個私有的拷貝構(gòu)造函數(shù)。”
“那 ……”，zero 頓了一頓，決定老實承認，“我不知道。”
“問題在哪你知道么？在于你沒有把智能指針看作指針。想象一下，如果我們對一個指針做賦值，它的含義是什么？”
“呃，我明白了，在這種情況下，應(yīng)該想辦法讓兩個智能指針指向同一個對象 …… 可是 Solmyr ，這樣以來豈不是仍然要對同一個對象刪除兩遍？”
“是的，我們得想辦法解決這個問題，辦法不只一種。比較好的一種是為每個指針維護一個引用計數(shù)值，每次賦值或者拷貝構(gòu)造，就讓計數(shù)值加一，這意味著指向這個內(nèi)存塊的智能指針又多了一個；而每有一個智能指針被銷毀，就讓計數(shù)值減一，這意味著指向這個內(nèi)存塊的智能指針少了一個；一旦計數(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;
// 初始化計數(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; // 使用同一個計數(shù)值
(*m_count)++; // 計數(shù)值加 1
}
~my_intptr()
{
(*m_count)--; // 計數(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)--; // 計數(shù)值減 1 ，因為該指針不再指向原來內(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; // 使用同一個計數(shù)值
(*m_count)++; // 計數(shù)值加 1
}
…………
};
“其他部分沒有什么太大變化，我不費事了。現(xiàn)在想象一下我們怎樣使用這種智能指針？”，Solmyr 放下了筆，再次拿起了筷子，有些惋惜的發(fā)現(xiàn)他愛吃的肉丸子已經(jīng)冷了。
zero 想象著，有些遲疑。“我們 …… 可以用 new int 表達式作為構(gòu)造函數(shù)的參數(shù)來構(gòu)造一個智能指針，然后 …… 然后我們可以任意的賦值，”，他開始抓住了思路，越說越快，“任意的用已經(jīng)存在的智能指針來構(gòu)造新的智能指針，智能指針的賦值運算符、拷貝構(gòu)造函數(shù)和析構(gòu)會保證計數(shù)值始終等于指向該內(nèi)存塊的智能指針數(shù)。”zero 似乎明白了他看到了怎樣的功能，開始激動起來：“然后一旦計數(shù)值為 0 被分配的內(nèi)存塊就會釋放！也就是說 …… 有指針指向內(nèi)存塊，它就不釋放，一旦沒有，它就自動釋放！太棒了！我們只要一開始正確的初始化智能指針，就可以象普通指針那樣使用它，而且完全不用擔心內(nèi)存釋放的問題！太棒了！”zero 激動的大叫：“這就是垃圾收集！Solmyr ！我們在飯桌上實現(xiàn)了一個垃圾收集器！”
Solmyr 很明顯沒有分享 zero 的激動：“我在吃飯，你能不能不要大叫‘飯桌上實現(xiàn)了一個垃圾收集器’這種倒胃口的話？”頓了一頓，Solmyr 帶著他招牌式的壞笑，以一種可惡的口吻說道：“而且請注意一下自己的形象。”
“嗯？”，zero 回過神來，發(fā)現(xiàn)自己不知什么時候站了起來，而整個餐廳里的人都在看著他嘿嘿偷笑，這讓他感覺自己像個傻瓜。
zero 紅著臉坐下，壓低了聲音問 Solmyr ：“不過 Solmyr ，這確實是一個的垃圾收集機制啊，只要我們把這個類改成 …… 嗯 …… 改成模板類，象這樣：”zero 抓過了紙筆，寫到：
template <typename T>
class my_ptr
{
private:
T* m_p;
int* m_count;
…………
};
“它不就能支持任意類型的指針了嗎？我們就可以把它用在任何地方。”
Solmyr 搖了搖頭：“不，你把問題想的太簡單了。對于簡單的類型，這個類確實可以處理的很好，但實際情況是很復(fù)雜的。考慮一個典型情況：類 Derived 是類 Base 的派生類，我們希望這樣賦值：”
Base* pb;
Derived pd;
…………
pb = pd;
“你倒說說看，這種情況，怎樣改用上面這個智能指針來處理？”
“……”，zero 沉默了。
“要實現(xiàn)一個完整的垃圾收集機制并不容易，因為有許多細節(jié)要考慮。”，Solmyr 開始總結(jié)了，“不過，基本思路就是上面說的這些。值得慶幸的是，目前已經(jīng)有了一個相當成熟的‘引用計數(shù)’智能指針，boost::shared_ptr。大多數(shù)情況下，我們都可以使用它。另外，除了智能指針之外，還有一些技術(shù)也能夠幫助我們避開釋放內(nèi)存的問題，比如內(nèi)存池。但是，關(guān)鍵在于 ——— ”
Solmyr 再度用那種平靜的眼神盯著 zero ：
“身為 C/C++ 程序員，必須有創(chuàng)造力。那種躺在語言機制上不思進取的人，那種必須要靠語法強制才知道怎樣編程的人，那種沒有別人告訴他該干什么就無所適從的人，不適合這門語言。”
歡迎訪問夢斷酒醒的博客：http://www.yanzhijun.com
本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/ishallwin/archive/2009/09/08/4533145.aspx
初學(xué)php,用php寫個小程序
其中寫了一個connection.php,里面放了一個class connection.
在這個文件被include或require的時候就會報錯了
然后百度，google許久,用了n種辦法也沒有解決。
不過收獲還是有的，了解了一下include_path
然后無意中隨便寫了個php,可以被include。
于是我開始懷疑難道我的connection.php不可以被載入？
于是修改connection.php的名稱為conn.php.
發(fā)現(xiàn)沒有問題了。
莫名其妙……
難不成connection是個關(guān)鍵字什么的？
摘要: <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...
閱讀全文
線段樹..
有個小地方寫次了..wa了好幾次..
寫了這道題..才感覺自己終于知道線段樹是個什么東西了..囧
#include <iostream>
using namespace std;
const int MAXN=100002;
struct node
{
int l,r;
int lnum,rnum;
int t;
}tree[MAXN*3];
int N,M;
int C[MAXN];
void make_tree(int l,int r,int p)
{
if (l==r)
{
tree[p].l=l;
tree[p].r=r;
tree[p].lnum=1;
tree[p].rnum=1;
tree[p].t=1;
return;
}
int mid=(l+r)/2;
make_tree(l,mid,p*2);
make_tree(mid+1,r,p*2+1);
int ls=p*2,rs=p*2+1;
tree[p].l=l;
tree[p].r=r;
tree[p].lnum=tree[ls].lnum;
if (C[tree[ls].r]==C[tree[rs].l]&&tree[p].lnum==mid-l+1) tree[p].lnum+=tree[rs].lnum;
tree[p].rnum=tree[rs].rnum;
if (C[tree[rs].l]==C[tree[ls].r]&&tree[p].rnum==r-mid) tree[p].rnum+=tree[ls].rnum;
tree[p].t=max(tree[ls].t,tree[rs].t);
tree[p].t=max(tree[p].t,tree[p].rnum);
tree[p].t=max(tree[p].t,tree[p].lnum);
if (C[tree[ls].r]==C[tree[rs].l]) tree[p].t=max(tree[p].t,tree[ls].rnum+tree[rs].lnum);
}
bool nnew;
int nl,nr,nlnum,nrnum,nt;
void find(int l,int r,int p)
{
int count=0;
int ll=tree[p].l,rr=tree[p].r;
if (ll>=l&&rr<=r)
{
if (!nnew)
{
nl=tree[p].l;
nr=tree[p].r;
nlnum=tree[p].lnum;
nrnum=tree[p].rnum;
nt=tree[p].t;
nnew=true;
return;
}
else
{
if (C[nr]==C[tree[p].l]) nt=max(nt,nrnum+tree[p].lnum);
if (C[nr]==C[tree[p].l]&&nlnum==nr-nl+1) nlnum+=tree[p].lnum;
if (C[nr]==C[tree[p].l]&&tree[p].rnum==tree[p].r-tree[p].l+1) nrnum+=tree[p].rnum; else nrnum=tree[p].rnum;
nt=max(nt,tree[p].t);
nt=max(nt,nlnum);
nt=max(nt,nrnum);
nr=tree[p].r;
}
return;
}
int mid=(ll+rr)/2;
if (l<=mid) find(l,r,p*2);
if (r>mid) find(l,r,p*2+1);
}
int main()
{
while(1)
{
scanf("%d",&N);
if (N==0) break;
scanf("%d",&M);
for (int i=1;i<=N;i++)
scanf("%d",&C[i]);
make_tree(1,N,1);
for (int i=1;i<=M;i++)
{
int x,y;
scanf("%d%d",&x,&y);
nnew=false;
nt=0;
find(x,y,1);
printf("%d\n",nt);
}
}
return 0;
}
摘要: bfs構(gòu)建層次圖dfs找增廣路線形規(guī)劃與網(wǎng)絡(luò)流24則-24.騎士共存問題
在一個n*n個方各的國際象棋棋盤上,馬可以攻擊的范圍如圖所示.棋盤上某些方各設(shè)置了障礙,騎士不得進入.求,棋盤上最多可以放置多少個騎士,使得他們彼此互不攻擊.數(shù)據(jù)范圍:1<=n<=200,0<=m<n^2解:對棋盤染色,騎士的跳躍不同色,構(gòu)成2分圖,求最大獨立集.最大獨立集=格子數(shù)(參與匹配)-最大...
閱讀全文