我的家園

[本文是我對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等)經常用作計數器, 序列號生成器等.

?