中等规模的并发程序设计1中等规模的并发程序设计多核时代来临硬件的多核时代已经来临2007年4核，2008年8核，2010年16核，2011年32核硬件促使软件发生变化更好的并发程序设计框架（executor、future、blockingqueue）更易用的算法、数据结构（lock-freedatastructure）并发程序设计将会变得简单而且逐步普及，按HerbSutter的预测，这个过程为2007年2012年我们幸运处于这个变革中旧时王谢堂前燕，飞入寻常百姓家2中等规模的并发程序设计3中等规模的并发程序设计4中等规模的并发程序设计线程（一）用户线程、内核线程、轻量级进程三种映射模型1:1、N:1、M:N三种映射模型Java线程在Windows和内核线程一对一影射（_beginthread）Java在Linux下使用pthread实现。Phtread在linux下有两种实现，linux2.6内核缺省使用NPTL。也是一对一影射。Java在Solaris下使用多对多映射。（Solaris、HP-UX、True64UNIX等操作系统本身支持M:N模型）5中等规模的并发程序设计线程（二）操作系统线程标准POSIXThread（PThread）这是应用最广泛的线程库，在各个版本的unix、linux下均有实现。Linux早期的版本并不完全符合PThread标准，Linux2.6内核缺省集成NPTL，完全符合PThread标准。Win32和OS/2ThreadsWin32Threads提供大量线程通讯API，功能强大。SolarisThreadsDCEThreads6中等规模的并发程序设计同步原语（一）线程特定存储ThreadLocal，又称为TLS、TSS、TSD等，在各文档中名称混乱。每个线程有唯一的标识，关联线程相关的特定数据，就是线程特定存储。Monitor中文翻译为管程。synchronized、Object.wait()、Object.notify()的底层实现。但是java原生提供的monitor不完整，因为没有提供Condition，Object本身隐含提供一个Condition。7中等规模的并发程序设计同步原语（二）条件变量（Condition）这是并发基本概念，在各种线程库中均有提供。Object对象隐含一个条件变量。条件变量都提供三个原子操作wait、signal、broadcast。在java.util.concurrent.Condition中，对应的是await、signal、signalAllwait必须在signal之前，否则会导致信号丢失的问题8中等规模的并发程序设计同步原语（三）上下文切换保存和恢复寄存器状态保存和恢复线程Cache状态的开销。各线程在运行时彼此淘汰对方的cache数据。（CPU的缓存）线程太多，会导致频繁的上下文切换，导致过多无谓的开销。在阻塞等待的线程不参与调度，不会导致上下文切换减少上下文开销的一个办法就是使用用户线程（纯java无法实现）。Oracle、MSSQLServer都是用用户线程，并宣称从用户线程中获得更好的性能。9中等规模的并发程序设计同步原语（四）死锁ABA问题容易导致死锁锁的粒度大，竞争严重，锁的粒度小，容易死锁，乃取舍问题注意锁的顺序需要考虑外部的锁，例如数据库的锁死锁的解决办法通过协议预防死锁的发生允许系统进入死锁状态，然后检测恢复忽视它的存在10中等规模的并发程序设计分解任务分解不同的程序行为采用不同的线程执行数据分解多个程序对不同的数据块执行相同的操作数据流分解一个线程的输出作为另外一个线程的输入11中等规模的并发程序设计Java传统的并发程序设计使用原生的Java并发支持，wait()、notify()、synchronized很难使用，容易导致程序结构混乱。这些都是太低级别的API，容易导致性能问题重新发明轮子太多。（经常需要发明类似BlockingQueue、ReadWriteLock之类的轮子）12中等规模的并发程序设计java.uti.concurrent的目标并发程序设计简单化提供基本的并发类包括Lock、Condition、Semaphore、Atomic等提供线程安全的数据结构ConcurrentLinkedQueue、ConcurrentHashMap提供了一些常用的工具类Threadpool、Scheduler、barrier、latch、blockingqueue等提供Atomic为专家提供用于开发高级的lock-free算法13中等规模的并发程序设计拜神DougLeaDougLea-Mr.concurrency，当今世界上并发程序设计领域的先驱，著名学者。他是util.concurrent包的作者，JSR166规范的制定。图书著作ConcurrentProgramminginJava:DesignPrinciplesandPatterns。其”AScalableElimination-basedExchangeChannel”和”ScalableSynchronousQueues”两篇论文列为非阻塞同步算法的经典文章14中等规模的并发程序设计Executors（一）这是一种任务分解。任务提供者和执行者在本线程内完成，或者交给专门的Executor去执行。Executor可以分为多种，或者允许指定运行策略任务提供者和执行者之间需要一种通讯机制，用于：等到任务执行结束（或者等待一段时间）取消任务等待时执行错误通知获取执行结果这种机制成为Future，这是一个很关键的概念，在并发程序中使用，能使程序清晰化，而且功能完备。在各种并发的库中均有提供类似的概念。15中等规模的并发程序设计Executors(二)Executor用于执行所提交的任务interfaceExecutorvoidexecute(Runnablecommand);ExecutorService生命周期管理，提供了Future返回和其他工具方法interfaceExecutorServiceextendsExecutorvoidshutdown();Futuresubmit(Runnabletask);Executors提供静态工厂方法class Executors ExecutorService newFixedThreadPool(int nThreads)ExecutorService newCachedThreadPool() / many more16中等规模的并发程序设计Future(一)一种很常用并发程序设计的手段便是任务分解。TaskProvider分解任务，提交给Executor执行。TaskProvider和Executor之间需要一种通讯手段，这种手段的具体实现，通常叫做Future。Future通常包括get（阻塞至任务完成），cancel，get(timeout)（等待一段时间）等等。Futue也用于异步变同步的场景。17中等规模的并发程序设计Future（二）Future的接口的接口classFuturebooleanisDone();Vget();Vget(longtimeout,TimeUnitunit);voidset(Vv);voidsetException(Throwablet);18中等规模的并发程序设计Future（三）Future已经是一个很流行的线程间通讯工具类，在很多网络并发的库中均有使用，例如C+网络库ACE，apache的nio框架mina，VisualC+内置future关键字直接使用。Future是一个很见的工具类，但他能够使得并发程序代码结构变动更清晰，使用灵活，可以以此发挥，创造高级的设计模式不会使用Future的人，有点土。19中等规模的并发程序设计BlockingQueue（一）常用的工具类，用于数据流分解读取阻塞，插入阻塞（可选）ArrayBlockingQueueFIFO，有上限LinkedBlockingQueueFIFO，可能有上限PriorityBlockingQueue按优先次序，无上限SynchronousQueueRendezvouschannel20中等规模的并发程序设计BlockingQueue（二）interfaceBlockingQueueextendsQueuebooleanadd(Ee);booleanoffer(Ee);Epeek();Etake()throwsInterruptedException;Epoll(longtimeout,TimeUnitunit)throwsInterruptedException;intdrainTo(Collectionc);21中等规模的并发程序设计BlockingQueue（三）注意add、offer、put的语义差别，养成使用offer的良好习惯注意peek、take、poll的语义差别，不要搞混了peek和take。必要时候使用drainTo提高性能22中等规模的并发程序设计定时器（一）传统的java.util.Timer每个Timer启动一个TimerThread没有直接和线程池或者Executor结合内部的TimerQueue性能不够好，也不适用于较大规模的Timer处理精度只能到达毫秒级23中等规模的并发程序设计定时器（二）ScheduledExecutorServiceextendsExecutorService，利用线程池执行调度任务内部使用DelayQueue实现（一个阻塞队列和优先队列的结合）interfaceScheduledExecutorServiceextendsExecutorServiceScheduledFutureschedule(Runnablecommand,);ScheduledFuturescheduleAtFixedRate(Runnablecommand,)ScheduledFuture scheduleWithFixedDelay(Runnable command更高的精度返回提供了ScheduledFuture，控制更灵活建议使用ScheduledExecutorService替代Timer24中等规模的并发程序设计定时器（三）使用DelayQueue使用于以下场景关闭空闲连接清空缓存中的Item任务超时处理替代笨笨的后台线程定时挨个检查的方式DelayQueue是一个使用优先队列（PriorityQueue）实现的BlockingQueue，优先队列的比较基准值是时间。BlockingQueue+PriorityQueue+DelayedinterfaceDelayedextendsComparablelonggetDelay(TimeUnitunit);classDelayQueueimplementsBlockingQueueprivatefinalPriorityQueueq;25中等规模的并发程序设计定时器（四）大规模定时器的实现在操作系统，网络应用，或者服务器端，可能存在大规模的定时器，提交的定时调度任务上万个，中途随时取消已提交的任务。Java内置的两个定时器实现Timer和ScheduledThreadPoolExecutor都不能满足大规模定时器的性能需求。Timer在操作时需要锁住整个TimerQueue，ScheduledThreadPoolExecutor内部使用DelayQueue，操作时也需要锁住整个优先队列，插入时还需要排序。存在一种算法TimerWheel，适用于大规模的定时器实现。这个算法最早是被设计用来实现BSD内核中定时器的，后来被广泛移植到诸如ACE等框架中，堪称BSD中经典算法之一，能针对定时器的各类常见操作提供接近常数时间的响应，且能根据需要很容易进行扩展。（TimerWheel在Java5中实现很简单）26中等规模的并发程序设计锁（一）使用synchronized关键字同步publicsynchronizedvoidf()synchronized(this)使用简单性能低下。比使用ReentrantLock性能要低得多调试监控不方便，无法得知“锁”拥有者线程27中等规模的并发程序设计锁（二）Lock更加灵活，性能更好interfaceLockvoidlock();voidlockInterruptibly()throwsInterruptedException;booleantryLock();booleantryLock(longtimeout,TimeUnitunit)throwsInterruptedException;voidunlock();ConditionnewCondition();支持多个Condition可以不以代码块的方式上锁可以使用tryLock，并指定等待上锁的超时时间调试时可以看到内部的ownerthread，方便排除死锁RenntrantLock支持fair和unfair两种模式28中等规模的并发程序设计锁（三）ReadWriteLock允许多个读，一个写Spin-Lock29中等规模的并发程序设计Atomic（一）基于CPU硬件提供的TSL指令基本思想是compareandset（CAS）作为原子操作通常和一个忙等待结合使用，CAS操作时需要一个回退机制非阻塞算法的基础Lock-free数据结构以此作为基础，获得更好的并发性能。30中等规模的并发程序设计Atomic（二）classAtomicIntegerextendsNumberintget()intincrementAndGet()intdecrementAndGet()booleancompareAndSet(intexpect,intupdate)31中等规模的并发程序设计Atomic（三）AtomicInteger用于计数器非常恰当AtomicReference在lock-free的数据结构中非常有用32中等规模的并发程序设计Atomic（四）幕后的非阻塞算法如果深入JVM和操作系统，会发现非阻塞算法无处不在。垃圾收集器使用非阻塞算法加快并发和平行的垃圾搜集；调度器使用非阻塞算法有效地调度线程和进程，实现内在锁。在Mustang（Java6.0）中，基于锁的SynchronousQueue算法被新的非阻塞版本代替。33中等规模的并发程序设计性能比较（一）8-wayUltrasparc3中同步、ReentrantLock、公平Lock和AtomicLong的基准吞吐量34中等规模的并发程序设计性能比较（二）单处理器Pentium4中的同步、ReentrantLock、公平Lock和AtomicLong的基准吞吐量35中等规模的并发程序设计性能比较（三）结论直接使用Atomic在单CPU下性能最好在多CPU情况下，ReentrantLock性能最好Synchronized和fairReentrantLock性能都较差36中等规模的并发程序设计Lock-free数据结构（一）提供compareandset操作使用者不需要锁并发性能更好在并发情况下，更容易使用，不容易出错37中等规模的并发程序设计Lock-free数据结构（二）classConcurrentHashMapVputIfAbsent(Kkey,Vvalue)booleanremove(Kkey,Vvalue);booleanreplace(Kkey,VoldValue,VnewValue);classConcurrentLinkedQueueextendsAbstractQueue38中等规模的并发程序设计CopyOnWriteArrayListCOW是一个很古老的算法常用于eventlistener的管理39中等规模的并发程序设计Exchanger是结合数据分解和数据流分解的一种技巧JavaSE只支持parities，Java6支持Nparities。40中等规模的并发程序设计并发流程控制SemaphoreLatchCountDownLatchBarrierCyclicBarrier这些工具类都很简单，属于并发流程控制的典型手段41中等规模的并发程序设计参考资料JavaSE6.0源码操作系统概念第六版现代操作系统多核程序设计技术pthreadprimer姚继锋的文章“Linux下的多线程编程”Flier_Lu的博客温少的博客42中等规模的并发程序设计一些资源NPTL(NativePosixThreadLibrary)ThreadsNewsgrouphttp:/46中等规模的并发程序设计Q&A47中等规模的并发程序设计