杂记：有关线程的同步和互斥

线程的同步和互斥：

线程的同步：指多线程通过特定的手段（如互斥量）来控制线程之间的执行顺序。

线程的互斥：实指对共享资源的约束访问。多线程环境中，某些资源只允许一个线程使用，这类资源成为临界资源，线程之间的关系就表现为互斥的。

线程之间的同步和互斥是通过操作系统的信号量和PV操作原语来实现的。

 

互斥体（Mutex）：

表现互斥现象的数据结构，也被当作二元信号灯。一个互斥基本上是一个多任务敏感的二元信号，它能用作同步多任务的行为，它常用作保护从中断来的临界段代码并且在共享同步使用的资源。

 

信号量（Semaphore）：

是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用。在进入一个关键代码段之前，线程必须获取一个信号量；一旦该关键代码段完成了，那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。

JDK的Semaphore类对它自己的解释是：A counting semaphore.  Conceptually, a semaphore maintains a set of permits.  Each {@link #acquire} blocks if necessary until a permit is available, and then takes it.  Each {@link #release} adds a permit, potentially releasing a blocking acquirer.

 

PV原语：

PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语（P、V原语）来访问。初始化可指定一个非负整数，即空闲资源总数。

 

P原语：P是荷兰语Proberen（测试）的首字母。为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞；

V原语：V是荷兰语Verhogen（增加）的首字母。为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一个被占用的资源（把信号量加1），如果发现有被阻塞的进程，则选择一个唤醒之。

 

 

临界区：

不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。每个进程中访问临界资源的那段代码称为临界区（Critical Section）（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。

 

监视器：

在Java中，任何一个对象都有一个监视器，来排斥共享访问临界区域的代码。这些临界区可以是一个方法或者是一段代码块，这些临界区域作为同步块。线程只有获取该监视器才能执行同步块的代码。当一个线程到达这块代码是，首先等待来确定是否其他线程已经释放这个监视器。监视器除了排斥共享访问，还能通过Wait和Notify来协调线程之间的交互。

 

公平锁和非公平锁：

ReentrantLock有一个带布尔型参数的构造函数，接受可选的“公平”参数。公平锁使线程按照请求锁的顺序依次获得锁；而不公平锁则允许讨价还价，在这种情况下，线程有时可以比先请求锁的其他线程先得到锁。

性能开销：

4CPU情况下，吞吐量的比较：

单CPU情况下：

使用Lock比使用synchronize要注意的地方在：

1.使用Lock，你必须手动的在finally块中释放锁。锁的获得和释放是不受JVM控制的，如果造成语意级别的死锁，jstack等工具是无法自己识别出来的。

2.当 JVM 用 synchronized 管理锁定请求和释放时，JVM 在生成线程转储时能够包括锁定信息。这些对调试非常有价值，因为它们能标识死锁或者其他异常行为的来源。Lock 类只是普通的类，JVM 不知道具体哪个线程拥有 Lock 对象。

总之，Lock提供了在多线程争用的情况下更好的并发性，但这是以牺牲一定的可维护性为代价的。

ReentrantLock是“一个可重入的互斥锁 Lock，它具有与使用 synchronized  方法和语句所访问的隐式监视器锁相同的一些基本行为和语义，但功能更强大。

 

ReentrantLock将由最近成功获得锁，并且还没有释放该锁的线程所拥有。当锁没有被另一个线程所拥有时，调用lock的线程将成功获取该锁并返回。如果当前线程已经拥有该锁，此方法将立即返回。可以使用 isHeldByCurrentThread() 和 getHoldCount() 方法来检查此情况是否发生。

 

几种常用队列：

ArrayBlockingQueue：最常用

LinkedBlockingQueue：不会满的

SynchronousQueue：size==0的

PriorityBlockingQueue

CompletionService (BlockingQueue + Executor)

TransferQueue (JDK 7中更快的SynchronousQueue)

 

Queue接口：

remove()和poll()的比较：Method remove differs from {@link #poll poll} only in that it throws an exception if this queue is empty.

add()和offer()的比较：When using a capacity-restricted queue, method offer is generally preferable to {@link #add}, which can fail to insert an element only by throwing an exception.

 

BlockingQueue接口：

poll()和take()的比较：poll允许指定等待时间参数（specified wait time if necessary for an element to become available）。

offer()和put()比较：同上，offer允许指定等待时间参数。

 

使用BlockingQueue的时候，尽量不要使用从Queue继承下来的方法，否则就失去了Blocking的特性了。

 

Condition的await()/signal()/signalAll()提供了语义锁的等待和唤醒机制：

Condition xxxCondition = lock.newCondition();

不要在Lock和Condition上使用wait、notiffy、notifyAll方法。

 

CAS的lock-free算法：

class Counter {
	private AtomicInteger max = new AtomicInteger();

	public void set(int value) {
		for (;;) {
			int current = max.get();
			if (value > current) {
				if (max.compareAndSet(current, value)) {
					break;
				} else {
					continue;
				}
			} else {
				break;
			}
		}
	}

	public int getMax() {
		return max.get();
	}
}

通常由三个部分组成：

1、循环

2、CAS

3、回退

其中，对于compareAndSet(int expect, int update)方法的说明：Atomically sets the value to the given updated value if the current value {@code ==} the expected value.

关于非阻塞算法可以参看这里。