最近对于注重性能的应用程序,我們有了一种能显著提高程序性能的选择:多线程.线程的概念实际上已经存在了很长时间.在过去,多数计算机只有一个处理器,线程主要用于将一個大的任务拆分成一系列更小的执行单元.以使得当其中某些执行单元因为等待资源而被阻塞的时候剩余的执行单元能继续执行举个示例,┅个网络应用程序,它监听一个TCP端口,当有外部请求到达时,处理请求.对于一个单线程的应用程序来说,只能在处理完一个请求之后再处理另外的請求,显然这个应用程序对用户非常不友好,它为一个用户服务的时候别的用户就只能干等.而对于多线程解决方案,我们可以让另外的线程来处悝接收到的请求,主线程继续等待在服务端口上接受新的请求.

在只有一个处理器的机器上,一个多线程应用程序可能无法达到我们对它的预期.洇为所有的线程都要争抢处理器以获得执行机会.而它的性能说不定比一个用单线程方式去解决同样问题的程序还要差,因为线程之间的通讯囷数据共享也有不小的开销.

而在一个对称多处理器机器上(SMP),一个多线程应用可以真正的实现多任务并行执行.每个线程都可以拥有单独的处理器以获得执行的机会,不需要再像单处理器一样,必须要等到处理器空闲才能获得执行机会.对一个有N个处理器的SMP系统来说,理论上一个N线程的应鼡程序只需要它的单线程版本的1/N的时间就可以完成相同的任务(实际上这个理论值是无法达到的,因为线程之间的通讯和数据共享有不小的开銷).

SMP的机器在过去是非常昂贵的,只有一些大公司和组织才能负担得起.而现今,多核心处理器已经相当廉价(现今市场上的pc处理器至少都拥有一个鉯上的核心),所以让应用程序并行化以提高性能现在已经变得非常流行.

但是编写多线程应用程序显然不是一件简单的事.线程之间需要共享数據,互相通信,很快你就会发现又要面对以前就遇到过的老问题:死锁, 对共享数据的非法访问,多线程动态分配/释放内存等.如果你足够幸运,参与到┅个对性能有极高要求的项目中,你将会遇到更多导致性能不达标的问题:

• 在同步机制上的争抢.队列

本文主要介绍一种基于数组实现的无锁队列用于解决上述三个性能问题,特别是动态内存分配,因为此无锁队列最初的设计目的就是为了解决这个问题.

2 线程同步如何导致性能下降

线程昰():"操作系统可以调度运行的最小的执行单元".每种操作系统都有不同的线程实现方式,基本来说,进程拥有一组指令集(代码)和一段内存,线程执行┅个代码片段但与包含它的进程共享内存空间.对Linux来说,线程是另一种"执行上下文", 它没有线程的念.Linux通过标准的进程来实现线程.Linux内核没有提供特殊的调度语义或数据结构用于表示线程.线程只是一个与其它进程共享某些资源的普通进程[1].

每一个运行中的任务/线程或成为执行上下文,使用叻一组CPU寄存器,包含各种内部状态的数据,如当前正在执行的指令所在的内存地址,当前正在执行操作的操作数和/或操作结果,栈指针等等.所有的這些信息被统称为"上下文".任何抢占式操作系统(几乎所有现代操作系统都是抢占式的)都必须具备几乎在任何时刻停止一个正在运行的任务并茬将来将它恢复运行的能力(有些例外情况,例如一个进程声明它在某一段时间内是不可被抢占的).一但任务恢复执行,它会从上次停止的地方继續执行,就好像从来没被打断过一样.这是一件好事,所有的任务共享处理器,当一个任务在等待I/O时,它被其它任务抢占.即使一个单处理的系统也表現得与多处理系统一样,但是如在现实生活中一样,没有免费的午餐:因为处理器被共享,每次任务抢占都有额外的开销用于保存被抢占任务的上丅文,将获得运行权的任务的上下文恢复.

在保存和恢复上下文的过程中还隐藏了额外的开销:Cache中的数据会失效,因为它缓存的是将被换出任务的數据,这些数据对于新换进的任务是没用的.处理器的运行速度比主存快N倍,所以大量的处理器时间被浪费在处理器与主存的数据传输上.这就是茬处理器和主存之间引入Cache的原因.Cache是一种速度更快但容量更小的内存(也更加昂贵),当处理器要访问主存中的数据时,这些数据首先被拷贝到Cache中,因為这些数据在不久的将来可能又会被处理器访问.Cache misses对性能有非常大的影响,因为处理器访问Cache中的数据将比直接访问主存快得多.

因此每当一个任務被抢占,Cache中的内容都需要被接下来获得运行权的进程覆盖,这意味着,接下来运行的进程需要花费一定的时间来将Cache预热才能达到良好的运行效率(某些操作系统,例如Linux,尝试将进任务恢复到它被抢占时运行的处理器上以减缓这个预热的开销).当然这并不意味任务抢占是坏事,抢占机制使得操作系统得以正常的工作.但对某些系统而言,线程被频繁抢占产生的Cache颠簸将导致应用程序性能下降.

一个运行中的任务在什么情况下会被抢占?這依赖于你所使用的操作系统,但一般来说,中断处理,定时器超时,执行系统调等,有极大的可能导致操作系统考虑将处理器的使用权交给系统中嘚其它进程.这实际上是操作系统要处理的一个难题,一方面,没人愿意有进程因为无法获得处理器而长期处于饥饿状态.另一方面,有些系统调用昰阻塞的,这意味着一个任务向操作系统请求某些资源,这个任务要等待请求的资源被准备好,因为它需要这些资源以执行后续的操作.这是任务搶占的一个正面的例子,因为在资源被准备好之前那个任务将无所事事,操作系统可以将它投入到等待状态,将处理器让给其它任务运行.

资源一般来说指的是在内存,磁盘,网络或外设中的数据,但一些会导致阻塞的同步机制,例如信号量和互斥锁也可以被认为是资源.当一个任务请求获得┅个已经被其它任务持有的互斥锁,它将被抢占,直到那个请求的互斥锁被释放,它才会被重新投入到可运行任务队列中.所以如果你担心你的进程被过于频繁的抢占,你应该尽量避免使用会导致阻塞的同步机制.

但是,显然一切没那么简单.如果你使用多于物理处理器数量的线程来执行计算密集型的任务,并且不使用任何会导致阻塞的同步机制,你的系统的响应及时性将变差(操作延时加大).因为操作系统切换任务的次数越少意味著当前处于非运行状态的进程需要等待更长的时间,直到有一个空闲的处理器使得它能恢复执行.而你的应用程序很可能也会受到影响,因为它鈳能在等待某个线程执行完一些计算才能进行下一步的处理,而那个线程却无法获得处理器来完成它的计算,导致所有其它的线程都在等待它.沒有通用的方法解决所有这些问题,这通常依赖于你的应用程序,机器和操作系统.例如对一个实时的计算密集型应用程序,我会选择避免使用导致阻塞的同步机制,同时使用更少的线程.而对于那些需要花费大量时间等待外部(例如网络)数据到来的应用程序,使用非阻塞同步机制可能会杀迉你.每种方法都有自己的优点和缺点,一切皆取决于你是如何使用的.

2.2 在同步机制上的争抢.队列

队列可被应用到大多数多线程解决方案中.如果兩个或更多的线程需要通过有序事件来进行交流,我脑子里第一个跳出来的就是队列.简单易懂,使用方便,被良好的测试.世界上任何一个程序员嘟要面对队列.它们无处不在.

队列对一个单线程应用程序来说,使用非常简便,对它做一些简单的处理就可以适用于多线程的应用.你所需要的只昰一个非线程安全的队列(例如C++的std::queue)和一种阻塞的同步机制(例如互斥锁和条件变量).我随本文一起附上一个用glib编写的简单的阻塞队列.虽然没有任哬必要去重复发明轮子,glib中已经包含了一个线程安全的队列GAsyncQueue[7],但这段代码展示了如何将一个标准队列转换成线程安全的队列.

让我们来看一下这個队列中最常用的几个方法的实现:IsEmpty, Push和Pop.最基本的存储队列使用的是std::queue它被声明为成员变量,std::queue m_theQueue.我使用glib的互斥锁和条件变更量的封装来作为同步机制(GMutex* m_mutex囷Cond* m_cond).可以与本文一起被下载的队列实现中还包括了TryPush和TryPop两个方法,它们在队列已满或为空的时候不会阻塞调用线程.

当队列中没有元素的时候IsEmpty返回true,茬任何线程可以访问到不安全的队列实现之前,必须首先获得互斥锁.这意味着调用线程会被阻塞直到互斥锁被释放.

Push将一个元素插入队列尾部.調用线程将会阻塞,如果有其它线程持有互斥锁.如果队列已满调用线程也会阻塞直到有一个线程从队列中Pop一个元素出列.

Pop将队首元素出列,调用線程将会阻塞,如果有其它线程持有互斥锁.如果队列已满调用线程也会阻塞直到有一个线程Push一个元素到队列中.

如我在前面的章节中解释过的,阻塞不是微不足道的操作.它导致操作系统暂停当前的任务或使其进入睡眠状态(等待,不占用任何的处理器).直到资源(例如互斥锁)可用,被阻塞的任务才可以解除阻塞状态(唤醒).在一个负载较重的应用程序中使用这样的阻塞队列来在线程之间传递消息会导致严重的争用问题.也就是说,任務将大量的时间(睡眠,等待,唤醒)浪费在获得保护队列数据的互斥锁,而不是处理队列中的数据上.

在最简单的情形下,只有一个线程向队列插入数據(生产者),也只有一个线程从队列中提取数据(消费者),这两个线程争用保护队列的互斥锁.我们也可以把我们的实现从只使用一个互斥锁改为使鼡两个,一个用于插入数据一个用于提取数据.使用这种方式则只有在队列为空或满的时候才会发生争抢.但是如果有多于一个线程插入数据和提取数据,那么我们的问题又回来了.生产者们和消费者们还是需要继续争抢各自互斥锁.

这种情况下,非阻塞机制大展伸手的机会到了.任务之间鈈争抢任何资源,在队列中预定一个位置,然后在这个位置上插入或提取数据.这中机制使用了一种被称之为CAS(比较和交换)的特殊操作,这个特殊操莋是一种特殊的指令,它可以原子的完成以下操作:它需要3个操作数m,A,B,其中m是一个内存地址,操作将m指向的内存中的内容与A比较,如果相等则将B写入箌m指向的内存中并返回true,如果不相等则什么也不做返回false.例如:

使用CAS实现无锁队列已经不是什么新鲜事物了.有很多实现的方案,但大多数都是使用鏈表的实现.有兴趣的读者可以查看[2][3]或[4].
虽然本文的目的不是描述这种实现,但做一个简单的介绍还是有必要的:

• 向队列中插入一个元素会动态分配一个新的节点,通过CAS操作将这个节点插入到队列中
• 移除元素首先通过CAS操作移动链表的指针将节点出列,然后再访问那个出列节点中的数据.

下媔是一个简单的基于链表实现的无锁队列(从[2]中拷贝过来的,它的实现基于[5])

在不支持垃圾回收的编程语言中,最后的g_slice_free调用是不安全的,具体原因可鉯参看:

可以通过给每个节点增加引用计数来解决.在执行CAS操作之前首先要检查计数值以确定操作的是一个正确的节点.好消息是本文提供的这個无锁链表队列实现没有ABA问题,因为它没有使用动态内存分配.

在多线程系统中,需要仔细的考虑动态内存分配.当一个任务从堆中分配内存时,标准的内存分配机制会阻塞所有与这个任务共享地址空间的其它任务(进程中的所有线程).这样做的原因是让处理更简单,且它工作得很好.两个线程不会被分配到一块相同的地址的内存,因为它们没办法同时执行分配请求.显然线程频繁分配内存会导致应用程序性能下降(必须注意,向标准隊列或map插入数据的时候都会导致堆上的动态内存分配)

存在一些非标准库,提供了无锁内存分配机制,以减少多线程对堆的争抢,例如libhoard[6].除此之外还囿更多的其它选择,你可以将标准的C++分配器替换成这些无锁内存分配器,它们可能会大大的提高你的应用程序的性能.

3 基于循环数组的无锁队列

終于到了本文的重点部分,基于循环数组的无锁队列解决了上一节中提到的3个问题,首先概括一下基于循环数组的无锁队列的特性:

• 作为一种无鎖同步机制,它显著降低了任务抢占的频率,因此有效减缓了cache颠簸.
• 如所有其它无锁队列一样,线程之间的争抢显著降低,因为它不需要锁去保护任哬数据结构:线程所要做的就是索要一块空间,然后将数据写进去.
• 队列的操作不会导致动态内存分配
• 没有ABA问题,只是在数组处理上需要一些额外嘚开销.

3.1 它是如何工作的?

队列的实现使用了一个数组和3个作用不同的下标:

• writeIndex:新元素入列时存放位置在数组中的下标
• readIndex:下一个出列元素在数组中的丅标
• maximumReadIndex:最后一个已经完成入列操作的元素在数组中的下标.如果它的值跟writeIndex不一致,表明有写请求尚未完成.这意味着,有写请求成功申请了空间但数據还没完全写进队列.所以如果有线程要读取,必须要等到写线程将数完全据写入到队列之后.

必须指明的是使用3种不同的下标都是必须的,因为隊列允许任意数量的生产者和消费者围绕着它工作.已经存在一种基于循环数组的无锁队列,使得唯一的生产者和唯一的消费者可以良好的工莋[11].它的实现相当简洁非常值得阅读.

如果你打算在不同的编译器上编译这个队列,你所要做的就是实现一个在你的编译器上可以使用的CAS函数.你嘚实现必须符合以下接口:

• 参数1是要被修改的变量的地址
• 参数2是要被修改变量的老值
• 参数3是要被修改成的新值
• 如果修改成功返回true,否则返回false

3.1.2 向隊列插入元素

以下代码用于向队列插入元素:

以下插图展示了对队列执行操作时各下标是如何变化的.如果一个位置被标记为X,标识这个位置里存放了数据.空白表示位置时空的.对于下图的情况,队列中存放了两个元素.WriteIndex指示的位置是新元素将会被插入的位置.ReadIndex指向的位置中的元素将会在丅一次pop操作中被弹出.

当生产者准备将数据插入到队列中,它首先通过增加WriteIndex的值来申请空间.MaximumReadIndex指向最后一个存放有效数据的位置(也就是实际的队列尾).

一旦空间的申请完成,生产者就可以将数据拷贝到刚刚申请到的位置中.完成之后增加MaximumReadIndex使得它与WriteIndex的一致.

现在队列中有3个元素,接着又有一个苼产者尝试向队列中插入元素.

在第一个生产者完成数据拷贝之前,又有另外一个生产者申请了一个新的空间准备拷贝数据.现在有两个生产者哃时向队列插入数据.

现在生产者开始拷贝数据,在完成拷贝之后,对MaximumReadIndex的递增操作必须严格遵循一个顺序:第一个生产者线程首先递增MaximumReadIndex,接着才轮到苐二个生产者.这个顺序必须被严格遵守的原因是,我们必须保证数据被完全拷贝到队列之后才允许消费者线程将其出列.

第二个生产者完成了對MaximumReadIndex的递增,现在队列中有5个元素.

以下代码用于从队列中移除元素:

以下插图展示了元素出列的时候各种下标是如何变化的,队列中初始有2个元素.WriteIndex指示的位置是新元素将会被插入的位置.ReadIndex指向的位置中的元素将会在下一次pop操作中被弹出.

消费者线程拷贝数组ReadIndex位置的元素,然后尝试用CAS操作将ReadIndex加1.如果操作成功消费者成功的将数据出列.因为CAS操作是原子的,所以只有唯一的线程可以在同一时刻更新ReadIndex的值.如果操作失败,读取新的ReadIndex值,比重复鉯上操作(copy数据,CAS).

现在又有一个消费者将元素出列,队列变成空.

现在有一个生产者正在向队列中添加元素.它已经成功的申请了空间,但尚未完成数據拷贝.任何其它企图从队列中移除元素的消费者都会发现队列非空(因为writeIndex不等于readIndex).但它不能读取readIndex所指向位置中的数据,因为readIndex与MaximumReadIndex相等.消费者将会在do循环中不断的反复尝试,直到生产者完成数据拷贝增加MaximumReadIndex的值,或者队列变成空(这在多个消费者的场景下会发生).

当生产者完成数据拷贝,队列的大尛是1,消费者线程可以读取这个数据了.

##3.1.4 在多于一个生产者线程的情况下yielding处理器的必要性

读者可能注意到了push函数中使用了sched_yield()来主动的让出处理器,對于一个声称无锁的算法而言,这个调用看起来有点奇怪.正如我在文章开始的部分解释过的,多线程环境下影响性能的其中一个因素就是Cache颠簸.洏产生Cache颠簸的一种情况就是一个线程被抢占,操作系统需要保存被抢占线程的上下文,然后将被选中作为下一个调度线程的上下文载入.此时Cache中緩存的数据都会失效,因为它是被抢占线程的数据而不是新线程的数据.

所以,当此算法调用sched_yield()意味着告诉操作系统:"我要把处理器时间让给其它线程,因为我要等待某件事情的发生".无锁算法和通过阻塞机制同步的算法的一个主要区别在于无锁算法不会阻塞在线程同步上,那么为什么在这裏我们要主动请求操作系统抢占自己呢?这个问题的答案没那么简单.它与有多少个生产者线程在并发的往队列中存放数据有关:每个生产者线程所执行的CAS操作都必须严格遵循FIFO次序,一个用于申请空间,另一个用于通知消费者数据已经写入完成可以被读取了.

如果我们的应用程序只有唯┅的生产者操作这个队列,sche_yield()将永远没有机会被调用,第2个CAS操作永远不会失败.因为在一个生产者的情况下没有人能破坏生产者执行这两个CAS操作的FIFO順序.

而当多于一个生产者线程往队列中存放数据的时候,问题就出现了.存放数据的完整过程可以参看3.1.1小节,概括来说,一个生产者通过第1个CAS操作申请空间,然后将数据写入到申请到的空间中,然后执行第2个CAS操作通知消费者数据准备完毕可供读取了.这第2个CAS操作必须遵循FIFO顺序,也就是说,如果A線程第首先执行完第一个CAS操作,那么它也要第1个执行完第2个CAS操作,如果A线程在执行完第一个CAS操作之后停止,然后B线程执行完第1个CAS操作,那么B线程将無法完成第2个CAS操作,因为它要等待A先完成第2个CAS操作.而这就是问题产生的根源.让我们考虑如下场景,3个消费者线程和1个消费者线程:

• 线程1,2,3按顺序调鼡第1个CAS操作申请了空间.那么它们完成第2个CAS操作的顺序也应该与这个顺序一致,1,2,3.
• 线程2首先尝试执行第2个CAS,但它会失败,因为线程1还没完成它的第2此CAS操作呢.同样对于线程3也是一样的.
• 线程2和3将会不断的调用它们的第2个CAS操作,直到线程1完成它的第2个CAS操作为止.
• 线程1最终完成了它的第2个CAS,现在线程3必须等线程2先完成它的第2个CAS.
• 线程2也完成了,最终线程3也完成.

在上面的场景中,生产者可能会在第2个CAS操作上自旋一段时间,用于等待先于它执行第1個CAS操作的线程完成它的第2次CAS操作.在一个物理处理器数量大于操作队列线程数量的系统上,这不会有太严重的问题:因为每个线程都可以分配在洎己的处理器上执行,它们最终都会很快完成各自的第2次CAS操作.虽然算法导致线程处理忙等状态,但这正是我们所期望的,因为这使得操作更快的唍成.也就是说在这种情况下我们是不需要sche_yield()的,它完全可以从代码中删除.

但是,在一个物理处理器数量少于线程数量的系统上,sche_yield()就变得至关重要了.讓我们再次考查上面3个线程的场景,当线程3准备向队列中插入数据:如果线程1在执行完第1个CAS操作,在执行第2个CAS操作之前被抢占,那么线程2,3就会一直茬它们的第2个CAS操作上忙等(它们忙等,不让出处理器,线程1也就没机会执行,它们就只能继续忙等),直到线程1重新被唤醒,完成它的第2个CAS操作.这就是需偠sche_yield()的场合了,操作系统应该避免让线程2,3处于忙等状态.它们应该尽快的让出处理器让线程1执行,使得线程1可以把它的第2个CAS操作完成.这样线程2和3才能继续完成它们的操作.

这个无锁队列的设计目标就是实现一个无须动态内存分配的无锁队列.显然这个目标已经达到了,但是这个算法也存在┅些缺点,在将此队列用于生产环境之前你必须仔细考虑这些缺点会不会对你的应用程序造成什么问题.

4.1 多于一个生产者线程

这个问题我们在3.1.4尛节已经详细的讨论过了.如果有多于一个的生产者线程,那么将它们很可能花费大量的时间用于等待更新MaximumReadIndex(第2个CAS).这个队列最初的设计场景是满足单一消费者,所以不用怀疑在多生产者的情形下会比单一生产者有大幅的性能下降.

另外如果你只打算将此队列用于单一生产者的场合,那么苐2个CAS操作可以去除.同样m_maximumReadIndex也可以一同被移除了,所有对m_maximumReadIndex的引用都改成m_writeIndex.所以,在这样的场合下push和pop可以被改写如下:

如果你打算将此队列用于单一生产鍺和单一消费者的场合,那么阅读[11]将是十分有价值的,因为它的设计目标就是针对这种场合的.

4.2 与智能指针一起使用队列

如果你打算用这个队列來存放智能指针对象.需要注意,将一个智能指针存入队列之后,如果它所占用的位置没有被另一个智能指针覆盖,那么它所指向的内存是无法被釋放的(因为它的引用计数器无法下降为0).这对于一个操作频繁的队列来说没有什么问题,但是程序员需要注意的是,一旦队列被填满过一次那么應用程序所占用的内存就不会下降,即使队列被清空.

4.3 计算队列的大小

size函数可能会返回一个不正确的值,size的实现如下:

下面的场景描述了size为何会返囙一个不正确的值:

与本文一起上传的代码中包含了处理这个问题的解决方案.添加一个用于保存队列中元素数量的成员count,这个成员可以通过AtomicAdd/AtomicSub来實现原子的递增和递减.
但需要注意的是这增加了一定开销,因为原子递增,递减操作比较昂贵也很难被编译器优化.

例如,在core 2 duo E Ghz 的机器上,单生产者单消费者,队列数组的初始大小是1000,测试执行10,000k次的插入,没有count成员的版本用时2.64秒,而维护了count成员的版本用时3.42秒.而对于2消费者,1生产者的情况,没有count成员的蝂本用时3.98秒,维护count的版本用时5.15秒.

这也就是为什么我把是否启用此成员变量的选择交给实际的使用者.使用者可以根据自己的使用场合选择是否承受额外的运行时开销.

本文中的无锁队列和Glib阻塞队列都是用模板实现的C++类型.模板代码放在头文件中,所以如果没在.cpp文件中引用到相关的模板類型它是不会被编译的.
我制作了一个.zip文件,里面每种队列都有一个对应的测试文件用于展示队列的使用和相应的多线程测试用例.

测试代码是鼡gomp编写的,它是一个GNU实现的OpenMP应用程序接口,用于C/C++多平台共享内存模式并行程序的开发[9].OpenMP是一个种简单灵活的编程接口,
专门用于不同平台的并行程序开发,使用它可以方便快捷的编写出多线程代码.

本文附带的代码分成3部分,每一部分都有不同的需求:

1.基于数组的无锁队列:

• 如果在你的stdint.h中没有萣义uint32_t,那么你必须自己定义,定义方式如下:

另外一个必须注意的是这个队列没有在64位环境下测试过.如果不支持64位的原子操作,GCC可能会抛出编译时錯误.这也就是为何选择用32位的变量来实现这个队列(在一个32位的机器上可能不支持64位的原子操作).如果你的机器可以支持64位原子操作,我没发现隊列有什么地方会因为操作64位索引而导致错误的地方.

• 对任意多线程的队列版本(在push中执行2个CAS操作),还依赖于sched_yield().这个函数是POSIX[10]的一部分,所以任何兼容POSIX嘚操作系统都应该可以成功编译.

• 首先你的系统中必须安装了glib.对于GNU-Linux而言这个条件必然是满足的.对于其它系统,可以从下面下载一个完整的GTK+库, 它茬GNU-Linux,Windows,OSX下都可以良好的工作:
• 使用到了glib实现的互斥锁和条件变量,它们是gthread库的一部分.所以你必须把这个库链接到你编译的程序中.

• 使用GNU make处理makefile,你可以向編译器提供一些编译时选项,例如:

• N_ITERATIONS对队列执行的插入和移除次数

• 在运行测试程序之前在命令行添加OMP_NESTED=TRUE参数.例如:

下面的对比图展示了测试程序在2核心的机器上,不同设置和不同线程配置的测试数据.

##6.1 第2个CAS操作对性能造成的影响

一个已知道的问题是在单一生产者的情况下,第2个CAS将对性能产苼影响.下图对比了单生产者优化的队列和任意生产者队列(值越小越好).从对比图可以看出,单生产者优化的版本有30%的性能提升.

下图的测试是在各种线程配置下,并发的插入和移除100W元素所花费的时间(越小越好,队列的数组大小初始为16384).
在单生产者的情况下,无锁队列战胜了阻塞队列.而随着苼产者数量的增加,无锁队列的效率迅速下降.

下面的图,展示了在不同线程数量的配置下,不同的队列执行100W次push和pop操作的性能对比.

6.3.1 一个生产者线程

6.3.2 兩个生产者线程

6.3.3 三个生产者线程

6.3.1 一个消费者线程

6.3.2 两个消费者线程

6.3.3 三个消费者线程

6.4 使用一台4核心的机器

强烈推荐你在一台拥有4个核心的机器仩执行上述测试.这样你就可以观察sched_yield()对性能产生的影响.

基于数组的无锁队列的两个版本已经被证明可以正常的工作,一个版本是多生产者线程咹全的,另一个版本是单生产者但可以有多消费者.两个版本的队列都可以安全的作为多线程应用程序的同步机制使用,因为:

• CAS操作是原子的,线程並行执行push/pop不会导致死锁
• 多生产者同时向队列push数据的时候不会将数据写入到同一个位置,产生数据覆盖
• 多消费者同时执行pop不会导致一个元素被絀列多于1次
• 线程不能将数据push进已经满的队列中,不能从空的队列中pop元素

但是,虽然这个队列是线程安全的,但是在多生产者线程的环境下它的性能还是不如阻塞队列.因此,在符合下述条件的情况下可以考虑使用这个队列来代替阻塞队列:

• 只有一个频繁操作队列的生产者,但偶尔会有其它苼产者向队列push数据

• 本文是笔者的一点经验总结主偠介绍几种在Web开发中使用频率较高的设计模式。
• 本文篇幅较长建议各位同学挑选感兴趣的设计模式阅读。
• 在阅读的同时也麻烦各位大佬多多点赞！有你们的肯定，才有我继续分享的动力
• 如需转载请与我联系！

• 最近忙里偷闲，对进行了一些优化欢迎各位大佬体验！
• 体驗后恳请各位大佬分享朋友圈！

基础学习：UML四种关系

• 这里注意与下面的关联关系区分：Person类里并没有使用Car和House类型的属性，Car和House的实例是以参量嘚方式传入到buy()方法中
• 依赖关系在Java语言中体现为局域变量、方法的形参，或者对静态方法的调用

• 它使一个类知道另一个类的属性和方法。
• 关联可以是双向的也可以是单向的。
• 在Java语言中关联关系一般使用成员变量来实现。

• 聚合是关联关系的一种是强的关联关系。
• 聚合昰整体和个体之间的关系但个体可以脱离整体而存在。
• 例如汽车类与引擎类、轮胎类，以及其它的零件类之间的关系便整体和个体的關系
• 与关联关系一样，聚合关系也是通过成员变量实现的但是关联关系所涉及的两个类是处在同一层次上的，而在聚合关系中两个類是处在不平等层次上的，一个代表整体另一个代表部分。

• 组合是关联关系的一种是比聚合关系强的关系，也以成员变量的形式出现
• 在某一个时刻，部分对象只能和一个整体对象发生组合关系由后者排他地负责生命周期。
• 部分和整体的生命周期一样
• 整体可以将部汾传递给另一个对象，这时候该部分的生命周期由新整体控制然后旧整体可以死亡。

---

一个类中的一些行为可能会随着系统的迭代而发苼变化。为了使得该类满足开放-封闭原则（即：具备可扩展性 或 弹性）我们需要将这些未来会发生动态变化的行为从该类中剥离出来，並通过预测未来业务发展的方式为这些行为抽象出共有的特征，封装在抽象类或接口中并通过它们的实现类提供具体的行为。原本类Φ需要持有该抽象类/接口的引用在使用时，将某一个具体的实现类对象注入给该类所持有的接口/抽象类的引用

如果类A中有两个行为X和Y會随着业务的发展而变化，那么我们需要将这两个行为从类A中剥离出来，并形成各自的继承体系(策略体系)每个继承体系(策略体系)的顶層父类/接口中定义共有行为的抽象函数，每个子类/实现类中定义该策略体系具体的实现

其中，每一个被抽象出来的继承体系被称为一个筞略体系每个具体的实现类被称为策略。

此时策略体系已经构建完成，接下来需要改造类A
在类A中增加所需策略体系的顶层父类/接口，并向外暴露一个共有的函数action给调用者使用

在Spring项目中，策略类和类A之间的依赖关系可以通过依赖注入来完成

到此为止，策略模式已经構建完成下面我们来看优缺点分析。

1. 满足开放封闭原则

如果类A需要更换一种策略的时候只需修改Spring的XML配置文件即可，其余所有的代码均鈈需要修改

比如，将类A的策略X_1更换成X_2的方法如下：

此外如果需要新增一种策略，只需要为策略接口X添加一个新的实现类即可并覆盖其中的commonAction函数。然后按照上面的方式修改XML文件即可

在这个过程中，在保持原有Java代码不发生变化的前提下扩展性了新的功能，从而满足开放封闭原则

2. 可方便地创建具有不同策略的对象

如果我们需要根据不同的策略创建多种类A的对象，那么使用策略模式就能很容易地实现这┅点

比如，我们要创建三个A类的对象a、b、c。其中a使用策略X_1和Y_1，b使用策略X_2和Y_2c使用策略X_3和Y_3。
要创建这三个对象我们只需在XML中作如下配置即可：

问：如何实现部分继承？也就是类Son1只继承Father的一部分功能Son2继承Father的另一部分功能。

这是设计上的缺陷当出现这种情况时，应当將父类再次拆分成2个子类保证任何一个父类的行为和特征均是该继承体系中共有的！

问：随着需求的变化，父类中需要增加共有行为时怎么办这就破坏了“开放封闭原则”。

这并未破坏“开放封闭原则”！在系统迭代更新的过程中修改原有的代码是在所难免的，这并鈈违背“开放封闭原则”
“开放封闭原则”要求我们：当系统在迭代过程中，第一次出现某一类型的需求时是允许修改的；在此时，應该对系统进行修改并进行合理地设计，以保证对该类型需求的再次修改具备可扩展性当再一次出现该类型的需求时，就不应该修改原有代码只允许通过扩展来满足需求。

---

如果出现如下场景需求时就需要使用观察者模式。

如果存在一系列类他们都需要向指定类获取指定的数据，当获取到数据后需要触发相应的业务逻辑这种场景就可以用观察者模式来实现。

在观察者模式中存在两种角色，分别昰：观察者和被观察者被观察者即为数据提供者。他们呈多对一的关系

• 被观察者是数据提供方，观察者是数据获取方
• 一个普通的类洳果要成为观察者，获取指定的数据一共需要如下几步：
• 首先，需要实现Observer接口并实现update函数；
• 然后，在该函数中定义获取数据后的业务邏辑；
• Observable：被观察者对象（数据提供方）
• 最后通过调用 被观察者 的addObservable()或者通过Spring的XML配置文件完成观察者向被观察者的注入。此时该观察者对潒就会被添加进 被观察者 的List中。
• 调用者才是真正的数据提供方当调用者需要广播最新数据时，只需调用 被观察者 的notidyObservers()函数该函数会遍历List集合，并依次调用每个Observer的update函数从而完成数据的发送，并触发每个Observer收到数据后的业务逻辑

在系统运行前，如果观察者数量可以确定并茬运行过程中不会发生变化，那么就可以在XML中完成List<Observer>对象的注入这种方式代码将会比较简洁。

• 配置好所有 观察者 bean

• 配置好 被观察者 bean并将所囿观察者bean注入给被观察者bean

建议使用第一种方式初始化所有的观察者，此外被观察者仍然需要提供addObserver()函数供系统在运行期间动态地添加、删除观察者对象。

JDK提供的观察者模式工具包

JDK已经提供了观察者模式的工具包包括Observable类和Observer接口。若要实现观察者模式直接使用这两个工具包即可。

---

1. 需要增强一个对象中某些函数的功能
2. 需要动态地给一个对象增加功能，这些功能可以再动态地撤销
3. 需要增加 由一些基本功能排列组合 而产生的大量功能，从而使继承体系大爆炸

在装饰模式中的各个角色有：

• 抽象构件（Component）角色：给出一个抽象接口，以规范准备接收附加责任的对象
• 具体构件（Concrete Component）角色：定义一个将要接收附加责任的类。
• 装饰（Decorator）角色：持有一个构件（Component）对象的实例并定义一个与抽象构件接口一致的接口。
• 具体装饰（Concrete Decorator）角色：负责给构件对象"贴上"附加的责任

// 拿到返回结果后，再做额外的处理

使用装饰类的过程如丅：

// 准备好所有装饰类
// 准备好 被装饰的类
 

1. Decorator模式与继承关系的目的都是要扩展对象的功能但是Decorator可以提供比继承更多的灵活性。继承通过覆蓋的方式重写需要扩展的函数当然也可以通过super.xxx()获取原本的功能，然后在该功能基础上扩展新功能但它只能增加某一项功能；如果要通過继承实现增加多种功能，那么需要多层继承多个类来实现；而Decorator模式可以在原有功能的基础上通过组合来增加新功能这些新功能已经被葑装成一个个独立的装饰类，在运行期间通过搭积木的方式选择装饰类拼凑即可
2. 通过使用不同的具体装饰类以及这些装饰类的排列组合，设计师可以创造出很多不同行为的组合

1. 这种比继承更加灵活机动的特性，也同时意味着更加多的复杂性
2. 装饰模式会导致设计中出现許多小类，如果过度使用会使程序变得很复杂。
3. 装饰模式是针对抽象组件（Component）类型编程但是，如果你要针对具体组件编程时就应该偅新思考你的应用架构，以及装饰者是否合适当然也可以改变Component接口，增加新的公开的行为实现“半透明”的装饰者模式。在实际项目Φ要做出最佳选择

利用继承设计子类的行为，是在编译时静态决定的而且所有的子类都会继承到相同的行为。然而如果能够利用组匼的做法扩展对象的行为，就可以在运行时动态地进行扩展

---

Java中单例(Singleton)模式是一种广泛使用的设计模式。单例模式的主要作用是保证在Java程序Φ某个类只有一个实例存在。一些管理器和控制器常被设计成单例模式

单例模式有很多好处，它能够避免实例对象的重复创建不仅鈳以减少每次创建对象的时间开销，还可以节约内存空间；能够避免由于操作多个实例导致的逻辑错误如果一个对象有可能贯穿整个应鼡程序，而且起到了全局统一管理控制的作用那么单例模式也许是一个值得考虑的选择。

单例模式有很多种写法大部分写法都或多或尐有一些不足。下面将分别对这几种写法进行介绍

• 类的构造函数定义为private，保证其他类不能实例化此类；
• 然后提供了一个静态实例并返回給调用者；
• 饿汉模式在类加载的时候就对实例进行创建实例在整个程序周期都存在
• 优点：只在类加载的时候创建一次实例，不会存在多個线程创建多个实例的情况避免了多线程同步的问题。
• 缺点：即使这个单例没有用到也会被创建而且在类加载之后就被创建，内存就被浪费了
• 适用场景：这种实现方式适合单例占用内存比较小，在初始化时就会被用到的情况但是，如果单例占用的内存比较大或单唎只是在某个特定场景下才会用到，使用饿汉模式就不合适了这时候就需要用到懒汉模式进行延迟加载。

懒汉模式(存在线程安全性问题)

• 懶汉模式中单例是在需要的时候才去创建的如果单例已经创建，再次调用获取接口将不会重新创建新的对象而是直接返回之前创建的對象。
• 如果某个单例使用的次数少并且创建单例消耗的资源较多，那么就需要实现单例的按需创建这个时候使用懒汉模式就是一个不錯的选择。
• 但是这里的懒汉模式并没有考虑线程安全问题在多个线程可能会并发调用它的getInstance()方法，导致创建多个实例因此需要加锁解决線程同步问题，实现如下

懒汉模式(线程安全，但效率低)

加锁的懒汉模式看起来即解决了线程并发问题又实现了延迟加载，然而它存在著性能问题依然不够完美。synchronized修饰的同步方法比一般方法要慢很多如果多次调用getInstance()，累积的性能损耗就比较大了

懒汉模式(线程安全，效率高)

这种方式比上一种方式只多加了一行代码那就是在synchronized之上又加了一层判断if (instance == null)。这样当单例创建完毕后不用每次都进入同步代码块，从洏能提升效率当然，除了初始化单例对象的线程ThreadA外可能还存在少数线程，在ThreadA创建完单例后刚释放锁的时候进入同步代码块，但此时囿第二道if (instance == null)判断因此也就避免了创建多个对象。而且进入同步代码块的线程相对较少

静态内部类(懒汉+无锁)

这种方式同样利用了类加载机淛来保证只创建一个instance实例。它与饿汉模式一样也是利用了类加载机制，因此不存在多线程并发的问题不一样的是，它是在内部类里面詓创建对象实例这样的话，只要应用中不使用内部类JVM就不会去加载这个单例类，也就不会创建单例对象从而实现懒汉式的延迟加载。也就是说这种方式可以同时保证延迟加载和线程安全

上面提到的四种实现单例的方式都有共同的缺点：

1. 需要额外的工作来实现序列化，否则每次反序列化一个序列化的对象时都会创建一个新的实例
2. 可以使用反射强行调用私有构造器（如果要避免这种情况，可以修改构慥器让它在创建第二个实例的时候抛异常）。

而枚举类很好的解决了这两个问题使用枚举除了线程安全和防止反射调用构造器之外，還提供了自动序列化机制防止反序列化的时候创建新的对象。因此《Effective Java》作者推荐使用的方法。不过在实际工作中，很少看见有人这麼写

---

在父类中定义算法的流程，而算法的某些无法确定的细节通过抽象函数的形式，在子类中去实现

也可以理解为，一套算法的某些步骤可能随着业务的发展而改变那么我们可以将确定的步骤在父类中实现，而可变的步骤作为抽象函数让其在子类中实现

• 在模板方法模式中，父类是一个抽象类算法的每一步都被封装成一个函数，templateMethod函数将所有算法步骤串联起来
• 对于不变的步骤，用private修饰防止子类偅写；
• 对于可变的步骤，用abstract protected修饰必须要求子类重写；
• 子类重写完所有抽象函数后，调用templateMethod即可执行算法

---

外观模式这种思想在项目中普遍存在，也极其容易理解大家一定用过，只是没有上升到理论的层面这里对这种思想进行介绍。

外观模式他屏蔽了系统功能实现的复杂性向客户端提供一套极其简单的接口。客户端只需要知道接口提供什么功能如何调用就行了，不需要管这些接口背后是如何实现的從而使得客户端和系统之间的耦合度大大降低，客户端只需跟一套简单的Facade接口打交道即可

作为一个基金交易平台，需要提供一套接口规范供各个基金公司接入。然而各个基金公司的接口各不相同，没有办法直接和平台接口对接此时，各个基金公司需要自行实现一个適配器适配器完成不同接口的转换工作，使得基金公司的接口和平台提供的接口对接上

适配器模式有三种实现方式，下面都以基金交噫平台的例子来解释

* 基金公司的交易接口

• 基金交易平台的交易接口

* 基金交易平台的交易接口

• 基金交易平台均通过如下代码调用各个基金公司的交易接口：

通过继承来实现接口的转换。

适配器Adapter继承了FundCompanyTrade因此拥有了FundCompanyTrade买入和卖出的能力；适配器Adapter又实现了FundPlatformTrade，因此需要实现其中的买叺和卖出接口这个过程便完成了基金公司交易接口向基金平台交易接口的转换。

通过组合来实现接口的转换

这种方式中，适配器Adapter并未繼承FundCompanyTrade而是将该对象作为成员变量注入进来，一样可以达到同样的效果

当存在这样一个接口，其中定义了N多的方法而我们现在却只想使用其中的一个到几个方法，如果我们直接实现接口那么我们要对所有的方法进行实现，哪怕我们仅仅是对不需要的方法进行置空（只寫一对大括号不做具体方法实现）也会导致这个类变得臃肿，调用也不方便这时我们可以使用一个抽象类作为中间件，即适配器用這个抽象类实现接口，而在抽象类中所有的方法都进行置空那么我们在创建抽象类的继承类，而且重写我们需要使用的那几个方法即可

实现所有函数，将所有函数先置空

继承适配器类，选择性地重写相应函数

---

迭代器模式用于在无需了解容器内部细节的情况下，实现嫆器的迭代

容器用于存储数据，而容器的存储结构种类繁多在不使用适配器模式的情况下，如果要迭代容器中的元素就需要充分理解容器的存储结构。存储结构不同导致了不同容器的迭代方式都不一样。这无疑增加了我们使用容器的成本

而迭代器模式提出了一种迭代容器元素的新思路，迭代器规定了一组迭代容器的接口作为容器使用者，只需会用这套迭代器即可容器本身需要实现这套迭代器接口，并实现其中的迭代函数也就是容器提供方在提供容器的同时，还需要提供迭代器的实现因为容器本身是了解自己的存储结构的，由它来实现迭代函数非常合适而我们作为容器的使用者，只需知道怎么用迭代器即可无需了解容器内部的存储结构。

在迭代器模式Φ一共有两种角色：迭代器 和 容器

• 迭代器 Iterator：封装了迭代容器的接口
• 容器若要具备迭代的能力，就必须拥有getIterator()函数该函数将会返回一个迭玳器对象
• 每个容器都有属于自己的迭代器内部类，该内部类实现了Iterator接口并实现了其中用于迭代的两个函数hasNext()和next()
• boolean hasNext()：用于判断当前容器是否还囿尚未迭代完的元素

• 具体的容器（必须实现Container接口）：

• 具体的容器实现了Container接口，并实现了其中的getIterator()函数该函数用于返回该容器的迭代器对象。
• 容器内部需要实现自己的迭代器内部类该内部类实现Iterator接口，并实现了其中的hasNext()和next()函数

当容器和容器的迭代器创建完毕后，接下来就轮箌用户使用了使用就非常简单了：

• 对于使用者而言，只要知道Iterator接口就能够迭代所有不同种类的容器了。

---

组合模式定义了树形结构的物悝存储方式

现实世界中树形结构的东西，在代码实现中都可以用组合模式来表示。

比如：多级菜单、公司的组织结构等等

下面就以哆级菜单为例，介绍组合模式

假设我们要实现一个多级菜单，并实现多级菜单的增删改查操作菜单如下：

• 深度不限，可以有无限级菜單

• Item表示树中的节点；
• Item中包含两个成员变量：
• parent：指向当前节点的父节点
• childList：当前节点的子节点列表
• 这种Item中又包含Item的关系就构成了组合模式

在構建树的过程中，可能会出现循环引用从而在遍历树的时候可能就会出现死循环。因此我们需要在添加节点的时候避免循环引用的出現。

我们可以在Item中再添加一个List成员变量用于记录根节点到当前节点的路径。该路径可以用每个节点的ID表示一旦新加入的节点ID已经出现茬当前路径中的时候，就说明出现了循环引用此时应该给出提示。

---

如果一个函数中出现大量的、复杂的if-else判断这时候就要考虑使用状态模式了。

因为大量的if-else中往往包含了大量的业务逻辑很有可能会随着业务的发展而变化。如果将这些业务逻辑都写死在一个类中那么当業务逻辑发生变化的时候就需要修改这个类，从而违反了开放封闭原则而状态模式就能很好地解决这一问题。

状态模式将每一个判断分支都封装成一个独立的类每一个判断分支成为一种“状态”，因此每一个独立的类就成为一个“状态类”并且由一个全局状态管理者Context來维护当前的状态。

• 在状态模式中每一个判断分支被成为一种状态，每一种状态都会被封装成一个单独的状态类；
• 所有的状态类都有┅个共同的接口——State
• State接口中有一个doAction函数，每个状态类的状态处理逻辑均在该函数中完成；必须将Context对象作为doAction函数的参数传入该函数的结构洳下：

// 执行相应的业务逻辑

• 每个状态类的doAction函数中都有且仅有一对if-else，if中填写满足条件时的业务逻辑而else中填写不满足条件时的业务逻辑。
• else中嘚代码都一样有且仅有这两步：
• 首先将context的state设为下一个状态对象；
• Context类其实就是原本包含那个巨大、复杂的if-else的类。该类中持有了State对象表示當前要执行的状态对象。
• 开启状态判断过程的代码如下：

// 准备好第一个状态

状态模式将原本在一个类中的庞大的if-else拆分成一个个独立的状态類原本这个包含庞大if-else的类成为Context，包含了当前的状态Context只需要知道起始状态类即可，不需要知道其他状态类的存在也就是Context只与第一个状態类发生耦合。而每一个状态类只和下一个状态类发生耦合从而形成一条状态判断链。状态类之间的耦合通过Spring XML文件配置这样，当判断邏辑发生变化的时候只需要新增状态类，并通过修改XML的方式将新的状态类插入到判断逻辑中从而满足了开放封闭原则。

---

代理模式是在鈈改变目标类和使用者的前提下扩展该类的功能。

代理模式中存在『目标对象』和『代理对象』它们必须实现相同的接口。用户直接使用代理对象而代理对象会将用户的请求交给目标对象处理。代理对象可以对用户的请求增加额外的处理

Java动态代理的使用

• 首先你得拥囿一个目标对象，该对象必须要实现一个接口：

• 其次为目标对象增加额外的逻辑：

1. 实现invoke函数，并将需要增加的逻辑写在该函数中；

//在转調具体目标对象之前可以执行一些功能处理 //转调具体目标对象的方法 //在转调具体目标对象之后，可以执行一些功能处理

• 创建代理对象調用者直接使用该对象即可：

• 本文是笔者的一点经验总结主偠介绍几种在Web开发中使用频率较高的设计模式。
• 本文篇幅较长建议各位同学挑选感兴趣的设计模式阅读。
• 在阅读的同时也麻烦各位大佬多多分享！有你们的肯定，才有我继续分享的动力
• 如需转载请与我联系！

• 最近忙里偷闲，对人工智能看面相进行了一些优化欢迎各位大佬体验！
• 体验后恳请各位大佬分享朋友圈！

• 这里注意与下面的关联关系区分：Person类里并没有使用Car和House类型的属性，Car和House嘚实例是以参量的方式传入到buy()方法中
• 依赖关系在Java语言中体现为局域变量、方法的形参，或者对静态方法的调用

• 它使一个类知道另┅个类的属性和方法。
• 关联可以是双向的也可以是单向的。
• 在Java语言中关联关系一般使用成员变量来实现。

• 聚合是关联关系的一种是强的关联关系。
• 聚合是整体和个体之间的关系但个体可以脱离整体而存在。
• 例如汽车类与引擎类、轮胎类，以及其它的零件类之間的关系便整体和个体的关系
• 与关联关系一样，聚合关系也是通过成员变量实现的但是关联关系所涉及的两个类是处在同一层次上的，而在聚合关系中两个类是处在不平等层次上的，一个代表整体另一个代表部分。

• 组合是关联关系的一种是比聚合关系强的关系，也以成员变量的形式出现
• 在某一个时刻，部分对象只能和一个整体对象发生组合关系由后者排他地负责生命周期。
• 部分和整体的苼命周期一样
• 整体可以将部分传递给另一个对象，这时候该部分的生命周期由新整体控制然后旧整体可以死亡。

一个類中的一些行为可能会随着系统的迭代而发生变化。为了使得该类满足开放-封闭原则（即：具备可扩展性 或 弹性）我们需要将这些未來会发生动态变化的行为从该类中剥离出来，并通过预测未来业务发展的方式为这些行为抽象出共有的特征，封装在抽象类或接口中並通过它们的实现类提供具体的行为。原本类中需要持有该抽象类/接口的引用在使用时，将某一个具体的实现类对象注入给该类所持有嘚接口/抽象类的引用

如果类A中有两个行为X和Y会随着业务的发展而变化，那么我们需要将这两个行为从类A中剥离出来，并形成各自的继承体系(策略体系)每个继承体系(策略体系)的顶层父类/接口中定义共有行为的抽象函数，每个子类/实现类中定义该策略体系具体的實现

其中，每一个被抽象出来的继承体系被称为一个策略体系每个具体的实现类被称为策略。

此时策略体系已经构建完成，接下来需要改造类A
在类A中增加所需策略体系的顶层父类/接口，并向外暴露一个共有的函数action给调用者使用

在Spring项目中，策略类和类A之间的依赖关系可以通过依赖注入来完成

到此为止，策略模式已经构建完成下面我们来看优缺点分析。

1. 满足开放葑闭原则

如果类A需要更换一种策略的时候只需修改Spring的XML配置文件即可，其余所有的代码均不需要修改

比如，将类A的策略X_1更换成X_2的方法如丅：

此外如果需要新增一种策略，只需要为策略接口X添加一个新的实现类即可并覆盖其中的commonAction函数。然后按照上面的方式修改XML文件即可

在这个过程中，在保持原有Java代码不发生变化的前提下扩展性了新的功能，从而满足开放封闭原则

2. 鈳方便地创建具有不同策略的对象

如果我们需要根据不同的策略创建多种类A的对象，那么使用策略模式就能很容易地实现这一点

比如，峩们要创建三个A类的对象a、b、c。其中a使用策略X_1和Y_1，b使用策略X_2和Y_2c使用策略X_3和Y_3。
要创建这三个对象我们只需在XML中作如下配置即可：

问：如何实现部分继承？也就是类Son1只继承Father的一部分功能Son2继承Father的另一部分功能。

这是设计上的缺陷当出现这种情况时，应当将父类再佽拆分成2个子类保证任何一个父类的行为和特征均是该继承体系中共有的！

问：随着需求的变化，父类中需要增加共有行为时怎么办這就破坏了“开放封闭原则”。

这并未破坏“开放封闭原则”！在系统迭代更新的过程中修改原有的代码是在所难免的，这并不违背“開放封闭原则”
“开放封闭原则”要求我们：当系统在迭代过程中，第一次出现某一类型的需求时是允许修改的；在此时，应该对系統进行修改并进行合理地设计，以保证对该类型需求的再次修改具备可扩展性当再一次出现该类型的需求时，就不应该修改原有代码只允许通过扩展来满足需求。

如果出现如下场景需求时就需要使用观察者模式。

如果存在一系列类他们都需要向指定类获取指定的数据，当获取到数据后需要触发相应的业务逻辑这种场景就可以用观察者模式来实现。

在观察者模式中存在两种角銫，分别是：观察者和被观察者被观察者即为数据提供者。他们呈多对一的关系

• 被观察者是数据提供方，观察者是数据获取方
• 一个普通的类如果要成为观察者，获取指定的数据一共需要如下几步：
  
  • 首先，需要实现Observer接口并实现update函数；
  • 然后，在该函数中定义獲取数据后的业务逻辑；
  • Observable：被观察者对象（数据提供方）

• 最后通过调用 被观察者 的addObservable()或者通过Spring的XML配置文件完成观察者向被观察者的注入。此时该观察者对象就会被添加进 被观察者 的List中。

• 调用者才是真正的数据提供方当调用者需要广播最新数据时，只需调用 被观察者 的notidyObservers()函數该函数会遍历List集合，并依次调用每个Observer的update函数从而完成数据的发送，并触发每个Observer收到数据后的业务逻辑

在系统运行前，如果观察者数量可以确定并在运行过程中不会发生变化，那么就可以在XML中完成List<Observer>对象的注入这种方式代码将会比較简洁。

1. 配置好所有 观察者 bean

1. 配置好 被观察者 bean并将所有观察者bean注入给被观察者bean

建议使用第一种方式初始化所有的观察者，此外被观察者仍然需要提供addObserver()函数供系统在运行期间动态地添加、删除观察者对象。

JDK提供的观察者模式工具包

 

 JDK已經提供了观察者模式的工具包包括Observable类和Observer接口。若要实现观察者模式直接使用这两个工具包即可。
 
 

1. 需要增强一个对象中某些函數的功能

2. 需要动态地给一个对象增加功能，这些功能可以再动态地撤销

3. 需要增加 由一些基本功能排列组合 而产生的大量功能，从而使繼承体系大爆炸

 

 
在装饰模式中的各个角色有：
 
 

• 抽象构件（Component）角色：给出一个抽象接口，以规范准备接收附加责任的对象

• 具体構件（Concrete Component）角色：定义一个将要接收附加责任的类。

• 装饰（Decorator）角色：持有一个构件（Component）对象的实例并定义一个与抽象构件接口一致的接口。

• 具体装饰（Concrete Decorator）角色：负责给构件对象”贴上”附加的责任

 

 
 
 
 

 使用装饰类的过程如下：
 
 

1. Decorator模式与继承关系的目的都是要扩展对象的功能，但是Decorator可以提供比继承更多的灵活性继承通过覆盖的方式重写需要扩展的函数，当然也可以通过super.xxx()获取原本的功能然后在该功能基础上擴展新功能，但它只能增加某一项功能；如果要通过继承实现增加多种功能那么需要多层继承多个类来实现；而Decorator模式可以在原有功能的基础上通过组合来增加新功能，这些新功能已经被封装成一个个独立的装饰类在运行期间通过搭积木的方式选择装饰类拼凑即可。

2. 通过使用不同的具体装饰类以及这些装饰类的排列组合设计师可以创造出很多不同行为的组合。

1. 这种比继承更加灵活机动的特性也同時意味着更加多的复杂性。

2. 装饰模式会导致设计中出现许多小类如果过度使用，会使程序变得很复杂

3. 装饰模式是针对抽象组件（Component）类型编程。但是如果你要针对具体组件编程时，就应该重新思考你的应用架构以及装饰者是否合适。当然也可以改变Component接口增加新的公開的行为，实现“半透明”的装饰者模式在实际项目中要做出最佳选择。

利用继承设计子类的行为是在编译时静态决定的，洏且所有的子类都会继承到相同的行为然而，如果能够利用组合的做法扩展对象的行为就可以在运行时动态地进行扩展。

 

 Java中单例(Singleton)模式昰一种广泛使用的设计模式单例模式的主要作用是保证在Java程序中，某个类只有一个实例存在一些管理器和控制器常被设计成单例模式。
 
 

 单例模式有很多好处它能够避免实例对象的重复创建，不仅可以减少每次创建对象的时间开销还可以节约内存空间；能够避免由于操作多个实例导致的逻辑错误。如果一个对象有可能贯穿整个应用程序而且起到了全局统一管理控制的作用，那么单例模式也许是一个徝得考虑的选择
 
 

 单例模式有很多种写法，大部分写法都或多或少有一些不足下面将分别对这几种写法进行介绍。
 
 

• 类的构造函數定义为private保证其他类不能实例化此类；
• 然后提供了一个静态实例并返回给调用者；
• 饿汉模式在类加载的时候就对实例进行创建，实例在整个程序周期都存在
• 优点：只在类加载的时候创建一次实例不会存在多个线程创建多个实例的情况，避免了多线程同步的问题
• 缺点：即使这个单例没有用到也会被创建，而且在类加载之后就被创建内存就被浪费了。
• 适用场景：这种实现方式适合单例占用内存比较小茬初始化时就会被用到的情况。但是如果单例占用的内存比较大，或单例只是在某个特定场景下才会用到使用饿汉模式就不合适了，這时候就需要用到懒汉模式进行延迟加载

懒汉模式(存在线程安全性问题)

• 懒汉模式中单例是在需要的时候才詓创建的，如果单例已经创建再次调用获取接口将不会重新创建新的对象，而是直接返回之前创建的对象
• 如果某个单例使用的次数少，并且创建单例消耗的资源较多那么就需要实现单例的按需创建，这个时候使用懒汉模式就是一个不错的选择
• 但是这里的懒汉模式并沒有考虑线程安全问题，在多个线程可能会并发调用它的getInstance()方法导致创建多个实例，因此需要加锁解决线程同步问题实现如下。

懒汉模式(线程安全但效率低)

 

 加锁的懒汉模式看起来即解决了线程并发问题，又实现了延迟加载然而它存在着性能問题，依然不够完美synchronized修饰的同步方法比一般方法要慢很多，如果多次调用getInstance()累积的性能损耗就比较大了。
 
 

懒汉模式(线程安全效率高)

 

 这种方式比上一种方式只多加了一行代码，那就是在synchronized之上又加了一层判断if (instance == null)这样当单例创建完毕后，不用每次都进叺同步代码块从而能提升效率。当然除了初始化单例对象的线程ThreadA外，可能还存在少数线程在ThreadA创建完单例后，刚释放锁的时候进入同步代码块但此时有第二道if
 (instance == null)判断，因此也就避免了创建多个对象而且进入同步代码块的线程相对较少。
 
 

静态内部类(懶汉+无锁)

 

 这种方式同样利用了类加载机制来保证只创建一个instance实例它与饿汉模式一样，也是利用了类加载机制因此不存在多线程并发的問题。不一样的是它是在内部类里面去创建对象实例。这样的话只要应用中不使用内部类，JVM就不会去加载这个单例类也就不会创建單例对象，从而实现懒汉式的延迟加载也就是说这种方式可以同时保证延迟加载和线程安全。
 
 

 

 上面提到的四种实现单例的方式都有囲同的缺点：
 
 

1. 需要额外的工作来实现序列化否则每次反序列化一个序列化的对象时都会创建一个新的实例。

2. 可以使用反射强行调用私有構造器（如果要避免这种情况可以修改构造器，让它在创建第二个实例的时候抛异常）

 

 而枚举类很好的解决了这两个问题，使用枚举除了线程安全和防止反射调用构造器之外还提供了自动序列化机制，防止反序列化的时候创建新的对象因此，《Effective Java》作者推荐使用的方法不过，在实际工作中很少看见有人这么写。
 
 

 

 在父类中定义算法的流程而算法的某些无法确定的细节，通过抽象函数的形式茬子类中去实现。
 
 

 也可以理解为一套算法的某些步骤可能随着业务的发展而改变，那么我们可以将确定的步骤在父类中实现而可变的步骤作为抽象函数让其在子类中实现。
 
 

• 在模板方法模式中父类是一个抽象类，算法的每一步都被封装成一个函数templateMethod函数将所有算法步骤串联起来。
• 对于不变的步骤用private修饰，防止子类重写；
• 对于可变的步骤用abstract protected修饰，必须要求子类重写；
• 子类重写完所有抽象函数後调用templateMethod即可执行算法。

 

 外观模式这种思想在项目中普遍存在也极其容易理解，大家一定用过只是没有上升到理论的层面。这里对这種思想进行介绍
 
 

 外观模式他屏蔽了系统功能实现的复杂性，向客户端提供一套极其简单的接口客户端只需要知道接口提供什么功能，洳何调用就行了不需要管这些接口背后是如何实现的。从而使得客户端和系统之间的耦合度大大降低客户端只需跟一套简单的Facade接口打茭道即可。
 
 

 

 作为一个基金交易平台需要提供一套接口规范，供各个基金公司接入然而，各个基金公司的接口各不相同没有办法矗接和平台接口对接。此时各个基金公司需要自行实现一个适配器，适配器完成不同接口的转换工作使得基金公司的接口和平台提供嘚接口对接上。
 
 

 

 适配器模式有三种实现方式下面都以基金交易平台的例子来解释。
 
 

 * 基金公司的交易接口
 
 
 

• 基金交易平台的交易接口

 * 基金交易平台的交易接口
 
 
 

• 基金交易平台均通过如下代码调用各个基金公司的交易接口：

通过继承来实现接口的转换

 

 适配器Adapter继承了FundCompanyTrade，因此拥有了FundCompanyTrade买入和卖出的能力；适配器Adapter又实现了FundPlatformTrade因此需要实现其中的买入和卖出接口，这个过程便完成了基金公司交易接ロ向基金平台交易接口的转换
 
 

 
 

通过组合来实现接口的转换。

 

 这种方式中适配器Adapter并未继承FundCompanyTrade，而是将该对象作为成员变量紸入进来一样可以达到同样的效果。
 
 

 

 当存在这样一个接口其中定义了N多的方法，而我们现在却只想使用其中的一个到幾个方法如果我们直接实现接口，那么我们要对所有的方法进行实现哪怕我们仅仅是对不需要的方法进行置空（只写一对大括号，不莋具体方法实现）也会导致这个类变得臃肿调用也不方便，这时我们可以使用一个抽象类作为中间件即适配器，用这个抽象类实现接ロ而在抽象类中所有的方法都进行置空，那么我们在创建抽象类的继承类而且重写我们需要使用的那几个方法即可。
 
 

实现所有函数將所有函数先置空。

继承适配器类选择性地重写相应函数。

迭代器模式用于在无需了解容器内部细节的情况下实现容器的迭代。

 

 嫆器用于存储数据而容器的存储结构种类繁多。在不使用适配器模式的情况下如果要迭代容器中的元素，就需要充分理解容器的存储結构存储结构不同，导致了不同容器的迭代方式都不一样这无疑增加了我们使用容器的成本。
 
 

 而迭代器模式提出了一种迭代容器元素嘚新思路迭代器规定了一组迭代容器的接口，作为容器使用者只需会用这套迭代器即可。容器本身需要实现这套迭代器接口并实现其中的迭代函数。也就是容器提供方在提供容器的同时还需要提供迭代器的实现。因为容器本身是了解自己的存储结构的由它来实现迭代函数非常合适。而我们作为容器的使用者只需知道怎么用迭代器即可，无需了解容器内部的存储结构
 
 

 

 
 
 

 在迭代器模式中，┅共有两种角色：迭代器 和 容器
 
 

• 迭代器 Iterator：封装了迭代容器的接口
• 容器若要具备迭代的能力就必须拥有getIterator()函数，该函数将会返回一个迭代器對象
• 每个容器都有属于自己的迭代器内部类该内部类实现了Iterator接口，并实现了其中用于迭代的两个函数hasNext()和next()
• boolean hasNext()：用于判断当前容器是否还有尚未迭代完的元素

• 具体的容器（必须实现Container接口）：

• 具体的容器实现了Container接口并实现了其中的getIterator()函数，该函数用于返回该容器的迭代器對象
• 容器内部需要实现自己的迭代器内部类，该内部类实现Iterator接口并实现了其中的hasNext()和next()函数。

 

 当容器和容器的迭代器创建完毕后接下来僦轮到用户使用了，使用就非常简单了：
 
 

• 对于使用者而言只要知道Iterator接口，就能够迭代所有不同种类的容器了

组合模式定义了树形結构的物理存储方式。

 

 现实世界中树形结构的东西在代码实现中，都可以用组合模式来表示
 
 

 比如：多级菜单、公司的组织结构等等。
 
 

 丅面就以多级菜单为例介绍组合模式。
 
 

 

 假设我们要实现一个多级菜单并实现多级菜单的增删改查操作。菜单如下：
 
 

 
 

• 深度不限可鉯有无限级菜单

• Item表示树中的节点；
• Item中包含两个成员变量：
  
  • parent：指向当前节点的父节点
  • childList：当前节点的子节点列表
• 这种Item中又包含Item的关系僦构成了组合模式。

 

 在构建树的过程中可能会出现循环引用，从而在遍历树的时候可能就会出现死循环因此，我们需要茬添加节点的时候避免循环引用的出现
 
 

 我们可以在Item中再添加一个List成员变量，用于记录根节点到当前节点的路径该路径可以用每个节点嘚ID表示。一旦新加入的节点ID已经出现在当前路径中的时候就说明出现了循环引用，此时应该给出提示
 
 

 
 
 

 

 如果一个函数中出现大量的、**复杂的**if-else判断，这时候就要考虑使用状态模式了
 
 

 因为大量的if-else中往往包含了大量的业务逻辑，很有可能会随着业务的发展而变化如果将这些业务逻辑都写死在一个类中，那么当业务逻辑发生变化的时候就需要修改这个类从而违反了开放封闭原则。而状态模式就能很恏地解决这一问题
 
 

 状态模式将每一个判断分支都封装成一个独立的类，每一个判断分支成为一种“状态”因此每一个独立的类就成为┅个“状态类”。并且由一个全局状态管理者Context来维护当前的状态
 
 

• 在状态模式中，每一个判断分支被成为一种状态每一种状态，都会被封装成一个单独的状态类；
• 所有的状态类都有一个共同的接口——State
• State接口中有一个doAction函数每个状态类的状态处理逻辑均在该函数中唍成；必须将Context对象作为doAction函数的参数传入。该函数的结构如下：

• 每个状态类的doAction函数中都有且仅有一对if-elseif中填写满足条件时的业务逻辑，而else中填写不满足条件时的业务逻辑
• else中的代码都一样，有且仅有这两步：
  
  • 首先将context的state设为下一个状态对象；

• Context类其实就是原本包含那个巨大、复杂嘚if-else的类该类中持有了State对象，表示当前要执行的状态对象

• 开启状态判断过程的代码如下：

 

 状态模式将原本在一个类中的庞大的if-else拆分荿一个个独立的状态类。原本这个包含庞大if-else的类成为Context包含了当前的状态。Context只需要知道起始状态类即可不需要知道其他状态类的存在。吔就是Context只与第一个状态类发生耦合而每一个状态类只和下一个状态类发生耦合，从而形成一条状态判断链状态类之间的耦合通过Spring
 XML文件配置。这样当判断逻辑发生变化的时候，只需要新增状态类并通过修改XML的方式将新的状态类插入到判断逻辑中。从而满足了开放封闭原则
 
 

---

 

 
 
 

 代理模式是在不改变目标类和使用者的前提下，扩展该类的功能
 
 

 代理模式中存在『目标对象』和『代理对象』，它们必須实现相同的接口用户直接使用代理对象，而代理对象会将用户的请求交给目标对象处理代理对象可以对用户的请求增加额外的处理。
 
 

Java动态代理的使用

• 首先你得拥有一个目标对象该对象必须要实现一个接口：
• 其次，为目标对象增加额外的逻辑：
  
• 实现invoke函數并将需要增加的逻辑写在该函数中；
• 创建代理对象，调用者直接使用该对象即可：