#
《深度探索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分图,求最大独立集.最大独立集=格子数(参与匹配)-最大...
阅读全文