一、能避免同步吗?
取得锁会因为以下原因导致成本很高:取得由竞争的锁需要在虚拟机的层面上运行更多的程序代码。
要取得有竞争锁的线程总是必须等到锁被释放后。
1. 寄存器的效应
计算机有一定数量的主寄存器用来存储与程序有关的数据。从逻辑上的观点来看,每个Thread都有自己的一组寄存器。当操作系统将某个Thread分配给CPU时,它会把该Thread特有的信息加载到CPU的寄存器中。在分配不同的Thread给CPU之前,它会将寄存器的信息存下来。所以Thread间绝不会共享保存在寄存器的数据。
当虚拟机进入synchronized方法或者块时,它必须重新加载本来已经缓存到自有寄存器上的数据。在虚拟机离开synchroized方法或者块之前,它必须把自有寄存器存入主寄存器中。
2. 重排语句的效应
在单独线程中,程序总是按照代码一行行的执行的,但是如果是多个线程并发,Java并不保证每个线程run方法的执行顺序,也就是可能其中一个线程执行到一半就会被暂时停止,执行其他线程,之后再切换回来。多个线程间调度执行的无序性就是重排语句的效应。
3. 双重检查的Locking
二、Atomic变量
1. Atomic Class的概述
AtomicInteger, AtomicLong, AtomicBoolean, AtomicRefrences。Atomic的功能实现时通过使用use-level的Java程序无法访问的固有方法来完成的。atomic package支持更复杂的变量类型吗?
一些不支持,例如字符或者浮点。
AtomicStampedReference能够让mark或stamp跟在任何对象的引用上。
AtomicMarkableReference提供一个包含对象引用结合boolean的数据结构。
2. 使用Atomic Class
import javax.swing.*; import java.awt.event.*; import java.util.concurrent.*; import java.util.concurrent.atomic.*; import javathreads.examples.ch05.*; public class ScoreLabel extends JLabel implements CharacterListener { private AtomicInteger score = new AtomicInteger(0); private AtomicInteger char2type = new AtomicInteger(-1); private AtomicReference<CharacterSource> generator = null; private AtomicReference<CharacterSource> typist = null; public ScoreLabel (CharacterSource generator, CharacterSource typist) { this.generator = new AtomicReference(generator); this.typist = new AtomicReference(typist); if (generator != null) generator.addCharacterListener(this); if (typist != null) typist.addCharacterListener(this); } public ScoreLabel () { this(null, null); } public void resetGenerator(CharacterSource newGenerator) { CharacterSource oldGenerator; if (newGenerator != null) newGenerator.addCharacterListener(this); oldGenerator = generator.getAndSet(newGenerator); if (oldGenerator != null) oldGenerator.removeCharacterListener(this); } public void resetTypist(CharacterSource newTypist) { CharacterSource oldTypist; if (newTypist != null) newTypist.addCharacterListener(this); oldTypist = typist.getAndSet(newTypist); if (oldTypist != null) oldTypist.removeCharacterListener(this); } public void resetScore() { score.set(0); char2type.set(-1); setScore(); } private void setScore() { // This method will be explained later in chapter 7 SwingUtilities.invokeLater(new Runnable() { public void run() { setText(Integer.toString(score.get())); } }); } public void newCharacter(CharacterEvent ce) { int oldChar2type; // Previous character not typed correctly - 1 point penalty if (ce.source == generator.get()) { oldChar2type = char2type.getAndSet(ce.character); if (oldChar2type != -1) { score.decrementAndGet(); setScore(); } } // If character is extraneous - 1 point penalty // If character does not match - 1 point penalty else if (ce.source == typist.get()) { while (true) { oldChar2type = char2type.get(); if (oldChar2type != ce.character) { score.decrementAndGet(); break; } else if (char2type.compareAndSet(oldChar2type, -1)) { score.incrementAndGet(); break; } } setScore(); } } }
变量替换
score与char2type变量已经改成atomic变量。
以上resetScroe方法中对两个变量进行修改,虽然使用atomic能保证每个变量的原子性,但是如果多个线程同时执行resetScore方法依然会出现竞态条件。
有可能一个线程执行resetScore的第一行代码score.set(0);还未执行第二行,而另外一个线程可能已经执行newCharacter方法获取char2type的值,但是之前的线程执行resetScore方法还未对char2type进行修改。因为resetScore整个方法并不是原子的。
变更算法
resetGenerator与resetTypist两个方法,以resetGenerator方法为例,将generator变量变成AtomicRerence同样引发上面描述的问题。
通知与Atomic变量
import java.awt.*; import javax.swing.*; import java.util.concurrent.*; import java.util.concurrent.atomic.*; import javathreads.examples.ch05.*; public class AnimatedCharacterDisplayCanvas extends CharacterDisplayCanvas implements CharacterListener, Runnable { private AtomicBoolean done = new AtomicBoolean(true); private AtomicInteger curX = new AtomicInteger(0); private AtomicInteger tempChar = new AtomicInteger(0); private Thread timer = null; public AnimatedCharacterDisplayCanvas() { startAnimationThread(); } public AnimatedCharacterDisplayCanvas(CharacterSource cs) { super(cs); startAnimationThread(); } private void startAnimationThread() { if (timer == null) { timer = new Thread(this); timer.start(); } } public void newCharacter(CharacterEvent ce) { curX.set(0); tempChar.set(ce.character); repaint(); } protected void paintComponent(Graphics gc) { char[] localTmpChar = new char[1]; localTmpChar[0] = (char) tempChar.get(); int localCurX = curX.get(); Dimension d = getSize(); int charWidth = fm.charWidth(localTmpChar[0]); gc.clearRect(0, 0, d.width, d.height); if (localTmpChar[0] == 0) return; gc.drawChars(localTmpChar, 0, 1, localCurX, fontHeight); curX.getAndIncrement(); } public void run() { while (true) { try { Thread.sleep(100); if (!done.get()) { repaint(); } } catch (InterruptedException ie) { return; } } } public void setDone(boolean b) { done.set(b); } }
使用Atomic变量的总结
乐观同步
程序代码抓住保护变量的值并作出此一瞬间没有其他修改的假设,然后程序代码就计算出该变量的新值并尝试更新该变量。
如果有其他的Thread同时修改了变量,这个更新就失败且程序必须重新执行这些步骤(使用变量的最新修改过的值)。
数据交换: getAndSet()
复杂的数据交换: get()与compareAndSet()
高级的atomic数据类型
import java.lang.*; import java.util.concurrent.atomic.*; public class AtomicDouble extends Number { private AtomicReference<Double> value; public AtomicDouble() { this(0.0); } public AtomicDouble(double initVal) { value = new AtomicReference<Double>(new Double(initVal)); } public double get() { return value.get().doubleValue(); } public void set(double newVal) { value.set(new Double(newVal)); } public boolean compareAndSet(double expect, double update) { Double origVal, newVal; newVal = new Double(update); while (true) { origVal = value.get(); if (Double.compare(origVal.doubleValue(), expect) == 0) { if (value.compareAndSet(origVal, newVal)) return true; } else { return false; } } } public boolean weakCompareAndSet(double expect, double update) { return compareAndSet(expect, update); } public double getAndSet(double setVal) { Double origVal, newVal; newVal = new Double(setVal); while (true) { origVal = value.get(); if (value.compareAndSet(origVal, newVal)) return origVal.doubleValue(); } } public double getAndAdd(double delta) { Double origVal, newVal; while (true) { origVal = value.get(); newVal = new Double(origVal.doubleValue() + delta); if (value.compareAndSet(origVal, newVal)) return origVal.doubleValue(); } } public double addAndGet(double delta) { Double origVal, newVal; while (true) { origVal = value.get(); newVal = new Double(origVal.doubleValue() + delta); if (value.compareAndSet(origVal, newVal)) return newVal.doubleValue(); } } public double getAndIncrement() { return getAndAdd((double) 1.0); } public double getAndDecrement() { return getAndAdd((double) -1.0); } public double incrementAndGet() { return addAndGet((double) 1.0); } public double decrementAndGet() { return addAndGet((double) -1.0); } public double getAndMultiply(double multiple) { Double origVal, newVal; while (true) { origVal = value.get(); newVal = new Double(origVal.doubleValue() * multiple); if (value.compareAndSet(origVal, newVal)) return origVal.doubleValue(); } } public double multiplyAndGet(double multiple) { Double origVal, newVal; while (true) { origVal = value.get(); newVal = new Double(origVal.doubleValue() * multiple); if (value.compareAndSet(origVal, newVal)) return newVal.doubleValue(); } } public int intValue() { return DoubleValue().intValue(); } public long longValue() { return DoubleValue().longValue(); } public float floatValue() { return DoubleValue().floatValue(); } public double doubleValue() { return DoubleValue().doubleValue(); } public byte byteValue() { return (byte)intValue(); } public short shortValue() { return (short)intValue(); } public Double DoubleValue() { return value.get(); } public boolean isNaN() { return DoubleValue().isNaN(); } public boolean isInfinite() { return DoubleValue().isInfinite(); } public String toString() { return DoubleValue().toString(); } public int hashCode() { return DoubleValue().hashCode(); } public boolean equals(Object obj) { Double origVal = DoubleValue(); return ((obj instanceof Double) && (origVal.equals((Double)obj))) || ((obj instanceof AtomicDouble) && (origVal.equals(((AtomicDouble)obj).DoubleValue()))); } public int compareTo(Double aValue) { return Double.compare(doubleValue(), aValue.doubleValue()); } public int compareTo(AtomicDouble aValue) { return Double.compare(doubleValue(), aValue.doubleValue()); } }
用两个变量的原子类:分数与字母变量。
import java.util.concurrent.atomic.*; public class AtomicScoreAndCharacter { public class ScoreAndCharacter { private int score, char2type; public ScoreAndCharacter(int score, int char2type) { this.score = score; this.char2type = char2type; } public int getScore() { return score; } public int getCharacter() { return char2type; } } private AtomicReference<ScoreAndCharacter> value; public AtomicScoreAndCharacter() { this(0, -1); } public AtomicScoreAndCharacter(int initScore, int initChar) { value = new AtomicReference<ScoreAndCharacter> (new ScoreAndCharacter(initScore, initChar)); } public int getScore() { return value.get().getScore(); } public int getCharacter() { return value.get().getCharacter(); } public void set(int newScore, int newChar) { value.set(new ScoreAndCharacter(newScore, newChar)); } public void setScore(int newScore) { ScoreAndCharacter origVal, newVal; while (true) { origVal = value.get(); newVal = new ScoreAndCharacter (newScore, origVal.getCharacter()); if (value.compareAndSet(origVal, newVal)) break; } } public void setCharacter(int newCharacter) { ScoreAndCharacter origVal, newVal; while (true) { origVal = value.get(); newVal = new ScoreAndCharacter (origVal.getScore(), newCharacter); if (value.compareAndSet(origVal, newVal)) break; } } public void setCharacterUpdateScore(int newCharacter) { ScoreAndCharacter origVal, newVal; int score; while (true) { origVal = value.get(); score = origVal.getScore(); score = (origVal.getCharacter() == -1) ? score : score-1; newVal = new ScoreAndCharacter (score, newCharacter); if (value.compareAndSet(origVal, newVal)) break; } } public boolean processCharacter(int typedChar) { ScoreAndCharacter origVal, newVal; int origScore, origCharacter; boolean retValue; while (true) { origVal = value.get(); origScore = origVal.getScore(); origCharacter = origVal.getCharacter(); if (typedChar == origCharacter) { origCharacter = -1; origScore++; retValue = true; } else { origScore--; retValue = false; } newVal = new ScoreAndCharacter(origScore, origCharacter); if (value.compareAndSet(origVal, newVal)) break; } return retValue; } }
被封装的值是以只读的方式处理。set方法必须创建新的对象来封装被保存的新值。
三、Thread局部变量
import java.util.*; public abstract class Calculator { private static ThreadLocal<HashMap> results = new ThreadLocal<HashMap>() { protected HashMap initialValue() { return new HashMap(); } }; public Object calculate(Object param) { HashMap hm = results.get(); Object o = hm.get(param); if (o != null) return o; o = doLocalCalculate(param); hm.put(param, o); return o; } protected abstract Object doLocalCalculate(Object param); }