改善并发程序的可扩展性--JCIP C11读书笔记

[本文是我对Java Concurrency In Practice C11的归纳和总结.  转载请注明作者和出处,  如有谬误, 欢迎在评论中指正. ] 

可扩展性和Amdahl's law--阿姆达尔定律

Scalability describes the ability to improve throughput or capacity when additional resources are added. When tuning for performance, the goal is usually to do the same work with less effort. But for scalability, the goal is to do more work with more resources.

Amdahl's law描述随着CPU核心数的增加, 并发程序所能到达的理论上的最大速度. 大多数并发程序包含并发和串行2个部分, 假设某个并发程序串行部分所占的比例为F, CPU核心数为N, 则其最大运行速度为: speedup = 1 / (F + (1 - F) / N), CPU利用率utilization = speedup / N. 由Amdahl's law可知, 假设CPU核心数趋近于无穷, 并发程序理论上的最大速度为1/F.  

如果一个并发程序串行部分比例F = 10%, 那么当CPU数N = 10时, 其speedup为5.3, CPU利用率为53%. 当CPU数N增加到100时, speedup为9.2, CPU利用率为9.2%. 

Amdahl's law表明, 应用的可扩展性由程序中串行部分所占的比例决定. 在java中, 串行的主要来源为排它锁, 因此, 为增加可扩展性, 可以考虑从以下方面着手:

1. 减少持有锁的时间.

2. 减少锁粒度.

3. 降低申请锁的频率.

4. 以非排它型锁代替排它锁.

 

减少持有锁的时间

将不必要持有锁的操作从同步代码块中移出可以有效减少持有锁的时间, 尤其是那些需要长时间运行的或者是阻塞的操作. 例如:

public class AttributeStore {
	private final Map<String, String> attributes = new HashMap<String, String>();

	/**
	 * 如果Map中存在name所对应的location, 且location匹配给定的正则表达式时, 返回true. 否则返回false.
	 */
	public synchronized boolean userLocationMatches(String name, String regexp) {
		String key = "users." + name + ".location";
		String location = attributes.get(key);
		if (location == null)
			return false;
		else
			return Pattern.matches(regexp, location);
	}
}

userLocationMatches方法访问了共享变量attributes, 所以需要同步. 但是同步整个userLocationMatches方法是没有必要的, 只需要同步get操作即可:

public boolean userLocationMatches(String name, String regexp) {
	String key = "users." + name + ".location";
	String location = null;
	synchronized(this) {
		location = attributes.get(key);
	}
	if (location == null)
		return false;
	else
		return Pattern.matches(regexp, location);
}

当然, 我们也可以将线程安全的责任委托为Map对象, 这样在AttributeStore类中就不需要做同步了:

public class AttributeStore {
	/**
	 * 将线程安全的责任委托给ConcurrentHashMap
	 */
	private final Map<String, String> attributes = new ConcurrentHashMap<String, String>();

	/**
	 * 如果Map中存在name所对应的location, 且location匹配给定的正则表达式时, 返回true. 否则返回false.
	 */
	public boolean userLocationMatches(String name, String regexp) {
		String key = "users." + name + ".location";
		String location = attributes.get(key);
		if (location == null)
			return false;
		else
			return Pattern.matches(regexp, location);
	}
}

使用线程安全委托是最好的, 这样我们就不必担心对AttributeStore类的后续修改忘记了加上同步.

 

减少锁粒度

通过锁的拆分或者分离, 可以减少锁竞争的发生. 例如:

public class ServerStatus {
	public final Set<String> users = new HashSet<String>();
	public final Set<String> queries = new HashSet<String>();

	public synchronized void addUser(String u) {
		users.add(u);
	}

	public synchronized void addQuery(String q) {
		queries.add(q);
	}

	public synchronized void removeUser(String u) {
		users.remove(u);
	}

	public synchronized void removeQuery(String q) {
		queries.remove(q);
	}
}

ServerStatus类中所以方法都使用this作为锁. ServerStatus类中存在2个成员users和queries, 使用同一把锁(this)确保2个变量的线程安全意味着增加了锁竞争的发生. 可以将锁拆分为粒度更小的2个锁, 分别保证一个变量的线程安全:

public class ServerStatus {
	public final Set<String> users = new HashSet<String>();
	public final Set<String> queries = new HashSet<String>();

	public void addUser(String u) {
		synchronized (users) {
			users.add(u);
		}
	}

	public void addQuery(String q) {
		synchronized (queries) {
			queries.add(q);
		}
	}
	//...
} 

一个锁保证一个变量的线程安全可以有效的降低锁竞争的发生. 为了更好的并发性能, 有时甚至使用粒度更小的锁: 使用多个锁保证同一个变量的线程安全. 熟悉ConcurrentHashMap的开发者可能知道, ConcurrentHashMap中使用16个锁保证其线程安全, 这样的机制使得ConcurrentHashMap具有极好的并发性能. 以下的StripedMap是对ConcurrentHashMap的简化:

public class StripedMap {
	// 使用16个锁保证 StripedMap的线程安全
	private static final int N_LOCKS = 16;
	private final Node[] buckets;
	private final Object[] locks;

	private static class Node {
		// ... 
	}

	public StripedMap(int numBuckets) {
		buckets = new Node[numBuckets];
		locks = new Object[N_LOCKS];
		for (int i = 0; i < N_LOCKS; i++)
			locks[i] = new Object();
	}

	private final int hash(Object key) {
		return Math.abs(key.hashCode() % buckets.length);
	}

	public Object get(Object key) {
		int hash = hash(key);
		// 使用不同的锁同步不同的bucket
		synchronized (locks[hash % N_LOCKS]) {
			for (Node m = buckets[hash]; m != null; m = m.next)
				if (m.key.equals(key))
					return m.value;
		}
		return null;
	}

	public void clear() {
		for (int i = 0; i < buckets.length; i++) {
			synchronized (locks[i % N_LOCKS]) {
				buckets[i] = null;
			}
		}
	}
	// ... 
}

 

以非排它型锁代替排它锁

例如使用读写锁, 不可变对象或者原子量等.

读写锁(ReadWriteLock)支持并发的读操作. 对于读操作频率远大于写操作频率的应用, 读写锁的使用可以带来并发性能的改善.

不可变对象天然具有线程安全, 不需要使用额外的同步.

原子量(如AtomicInteger, AtomicLong等)经常用作计数器, 序列号生成器等.