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