并行模式与算法——第一部分

并行模式与算法

仅作为笔记

文章目录

并行模式与算法
前言
一、探讨单例模式
二、不变模式
三、生产者-消费者模式
四、高性能的生产者-消费者：无锁的实现
- 4.1、无锁的缓存框架：Disruptor
- 4.2、提高消费者的响应时间：选择合适的策略
- 4.3、CPU Cache的优化：解决伪共享问题
五、Future模式
- 5.1、Future模式的主要角色
- 5.2、JDK中的Future模式

前言

仅作为笔记

一、探讨单例模式

作用：用于生产一个对象的具体实例，可以确保系统中一个类只产生一个实例。
优点：1.对于频繁使用的对象，可以省略new操作花费的时间。2.new操作减少GC压力，缩短GC停顿时间。

单例模式分为饿汉式（立即创建）和懒汉式（延时创建）两种。

饿汉式（立即创建）：我们知道，类的加载过程，在初始化这一步最先初始化的是静态变量静态代码块，在有的时候一个类里面有其他静态变量，如果此时调用了任何的静态成员，都会导致其他变量被加载，这意味着会在不需要创建实例对象的时候创建了对象。但是这是线程安全的（jvm类加载机制）其代码如下：

public class Singleton{
	private Singleton(){};
	private static Singleton instance = new Singleton();
	public static Singleton getInstance(){
		return instance;
	}
}

懒汉式（延时创建）：实际上是一个实例化创建可控的，不会出现上面饿汉式那样在不需要的时候也创建实例对象。但是他是线程不安全的,主要原因是其初始化时并没有创建实例对象，而是在调用时才创建，而获取实例的方法可能被其他线程调用。代码实现如下：

public class LazySingleton{
	private LazySingleton(){};
	private static LazySingleton instance = null;
	public static LazySingleton getInstance(){
		if(instance==null){
			instance = new LazySingleton();
		}
		return instance;
	}
}

解决方法1：自然而然的，既然获取实例对象的方法是会让线程导致冲突的，那么可以加锁啊，如下：

public class LazySingleton{
	private LazySingleton(){};
	private static LazySingleton instance = null;
	public static synchronized LazySingleton getInstance(){
		if(instance==null){
			instance = new LazySingleton();
		}
		return instance;
	}
}

显而易见的，这样是可以解决线程间的冲突的，但是锁粒度过大，如果线程多，竞争激烈的情况下是非常影响性能的。
解决方法2：静态内部类方法，首先他是线程安全的，并且没有使用加锁的方式来保障线程安全，有利于提高性能。其代码实现如下：

public class StaticSingleton{
	private StaticSingleton(){};
	private static class SingletonHolder{
		private static StaticSingleton instance = new StaticSingleton();
	}
	public static StaticSingleton getInstance(){
		return SingletonHolder.instance;
	}
}

这是一个充分利用了静态内部类特点的实现方法，首先静态内部类有如下特点：1）外部类装载的时候，静态内部类不会装载。2）静态类所在的外部类使用内部类时，静态内部类会装载。3）静态内部类在装载时是线程安全的（在类进行初始化时其他线程无法进入），只会装载一次。

二、不变模式

应用需要满足的条件：对象创建后就一点也不改变了，以及对象需要被共享。
实现：1.去除所有能够改变对象值得的方法。2.将所有属性设置为私有，并为final标记，确保其不可修改。3.确保没有子类。4.构造器可以完全创建完整的对象。
代码如下：

主要最典型的就是JDK中的java.lang.String类。

三、生产者-消费者模式

回顾一个东西：BlockingQueue，在之前的文章里我提到了：BlockingQueue能方便构建松散耦合的高性能消息队列，这是一个接口，下面包含了一些实现，主要是ArrayBlockingQueue和linkedBlockingQueue两种实现。而这个东西也就是作为数据共享通道，作为可以作为生产者与消费者模式的数据共享的方法，实际上就是下面提到的PCData的共享的内存缓存区。
整个生产者消费者模式包含以下五个部分：1）生产者，用于提交用户请求，提取用户任务，并装入到内存缓存区。2）消费者，在内存缓存区中提取并处理任务。3）内存缓存区，缓存生产者提交的任务或者数据，供消费者使用。4）任务，生产者向内存缓存区提交的数据结构。5）Main，使用生产者和消费者的客户端。
打个比方：Main好比一个饭店，生产者好比厨师，消费者好比端菜的，而内存缓存区（也就是BlockingQueue的实现类）好比是做好的菜放的平台，任务就是端菜的把菜端过去。而保证同步的地方仅仅是那个放菜的平台，保证菜不被其他端菜的端走发生抢菜事件。。。。。

四、高性能的生产者-消费者：无锁的实现

前面提到了内存缓存区使用BlockingQueue，但是这个是用锁和阻塞实现的，在竞争激烈的情况下这样非常影响性能。所以可以像ConcurrentlinkedQueue那样使用CAS来实现同步，也就是无锁。而Disruptor就是这样一个现成的框架。

4.1、无锁的缓存框架：Disruptor

采用消费者-生产者模型进行读写的分离。
用循环缓存（实际是一个循环队列）实现了数据的暂存和读写速度的匹配。
用内存屏障加序列号的方式实现了无锁的并发机制。

注意：循环队列的大小必须是事前确定的，不可以再扩容，必须是2的整数次幂。

4.2、提高消费者的响应时间：选择合适的策略

消费者监控缓存区的信息的几种策略。

BlockingWaitStrategy：这是默认的策略，使用BlockingWaitStrategy和BlockingQueue是非常类似的，都使用锁和条件（Condition）进行数据的监控，但是在高并发情况下性能不好。
SleepingWaitStrategy：适用于对延时要求不太高的场合，典型的是异步日志。
YieldingWaitStrategy：用于低延时场合。
BusySpinWaitStrategy：这是个最疯狂的等待策略…

4.3、CPU Cache的优化：解决伪共享问题

为了提高CPU速度，CPU有一个高速缓存Cache，在高速缓存中，读写数据的最小单位缓存行，它是从主存复制到缓存的最小单位，一般为32到128字节，如果两个变量存放在一个缓存行中，在多线程访问中可能会相互影响彼此的性能，如下图：

运行在CPU1上的线程更新了x那么cpu2上的缓存行就会失效，同一行的y即使没有修改也会变成无效，导致cache无法命中。接着，如果在cpu2上的线程更行了Y，则导致x无效，如果经常CPU无法命中就会导致系统的吞吐量急剧下降。

优化：采用在x变量前后空间都占据一定位置，用来填充，让x和y位于不同的缓存行，这样的话就不会出现以上问题了，如下图：

五、Future模式

核心思想：异步调用。
广义的Future模式原理如图：

调用者在发出调用命令后并不会在原地等待接收数据，而是先收到一个凭证，一个到时候拿取真实结果的凭证。然后去做其他的事情。最后在依赖凭证拿到结果。

5.1、Future模式的主要角色

Main：系统启动，调用Client发出的请求。
Client：返回Data对象，立即返回FutureData，并开启ClientThread线程装配RealData。
Data：返回数据的接口
FutureData：Future数据，构造很快，但是是一个虚拟的数据，需要装配RealData
RealData：真实数据，其构造是比较慢的。

5.2、JDK中的Future模式

如下图：

RunnableFuture继承了Future和Runnable两个接口，其中run（）方法用于构造真实的数据，他有一个具体的实现FutureTask类，FutureTask有一个内部类Sync，一些实质性的工作交给Sync类实现，而Sync类最终会调用Callable接口，完成实际数据的组装工作。
重点：Callable接口只有一个call（）方法，它会返回需要构造的真实数据，这个接口也是Future框架和应用程序之间的重要接口，构造自己的业务时也需要实现自己的Cabble对象。

并行模式与算法——第一部分

Java相关栏目本月热门文章