理解并發(fā)編程的一些基本概念很重要，給我們思考問題指明一個(gè)基本的方向。這篇說一說鎖的一些基本概念。
在通常情況下我們說的鎖都指的是“互斥”鎖，因?yàn)樵谶€存在一些特殊的鎖，比如“讀寫鎖”，不完全是互斥的。這篇文章說的鎖專指互斥鎖。
鎖是處理并發(fā)的一種同步手段。單線程程序和并發(fā)程序的最終目的都是要保證程序的正確性，但是最大的區(qū)別是：
單線程程序的正確性只關(guān)注程序的運(yùn)行結(jié)果和目標(biāo)是一致的
并發(fā)程序的正確性除了運(yùn)行結(jié)果正確外，還包含了活性的特性，所謂活性，指的就是程序無(wú)死鎖，無(wú)饑餓
所以考察一個(gè)鎖，也需要從三個(gè)方面考察：
互斥性
無(wú)死鎖
無(wú)饑餓
最簡(jiǎn)單的鎖只保證互斥性，而互斥性本質(zhì)上可以用一個(gè)布爾值表示，即一個(gè)二元狀態(tài)。
互斥是保證并發(fā)程序正確性的一種特性，和互斥相關(guān)的一個(gè)專用名詞就是臨界區(qū)
臨界區(qū)指的是“某個(gè)時(shí)刻僅能被一個(gè)線程執(zhí)行的代碼段”，也就是通常鎖的被鎖保護(hù)的代碼段。
一個(gè)互斥鎖的定義通常如下
interface Lock {
public void lock();
public void unlock();
}
線程必須用指定的方式使用鎖，lock動(dòng)作必須在try塊之前調(diào)用，如果lock在try里面執(zhí)行，可能會(huì)在取到鎖之前拋出異常，導(dǎo)致執(zhí)行了unlock動(dòng)作，從而發(fā)生錯(cuò)誤。
熟悉Java顯示鎖的同學(xué)肯定知道使用ReentryLock就是如下的用法。
mutex.lock();
try{
...臨界區(qū)
}finally{
mutex.unlock()
}
互斥意味著串行，也意味著等待。 這引出了著名的Amdahl定律
Amdahl定律: 即完成一個(gè)工作能獲得的加速比，受限于這個(gè)工作中必須被串行的部分。（通常串行部分都是因?yàn)楸换コ怄i保護(hù)了）
加速比的定義是一個(gè)處理器完成一個(gè)工作的時(shí)間和采用n個(gè)處理器并發(fā)完成該工作的時(shí)間比。
Amdahl定律給出的加速比如下
S = 1 / ( 1 - p + p/n)
S為加速比
1為完成工作的時(shí)間
p指可以并行的部分
n指處理器個(gè)數(shù)
從Amdahl定律可以看出，串行的工作越多，獲得的加速比就越小。
Amdahl給我們編程實(shí)際啟示有：
盡量減小互斥鎖的粒度，鎖粒度越小表示串行的部分越少
能不用鎖，就不要用鎖。不用鎖表示串行的部分越少
接下來說說活性相關(guān)的概念。
死鎖意味者系統(tǒng)凍結(jié)，最終相關(guān)的所有線程都永久地停滯等待。
饑餓則是總有一些線程能夠運(yùn)行，一小部分線程永久停滯等待
所以無(wú)饑餓意味著肯定無(wú)死鎖。但是無(wú)死鎖不意味著無(wú)饑餓。
《多處理器編程的藝術(shù)》一書中給出了幾種鎖的實(shí)現(xiàn)，其中Peterson算法可以保證兩個(gè)線程使用鎖的時(shí)候鎖具備互斥，無(wú)死鎖，無(wú)饑餓特性。
class Peterson implements Lock {
private boolean[] flag = new boolean[2];
private int victim;
public void lock(){
int i = ThreadID.get();
int j = 1 - i;
flag[i]= true; // 保證兩個(gè)線程先后運(yùn)行不死鎖，實(shí)現(xiàn)互斥
victim = i; // 保證兩個(gè)線程同時(shí)運(yùn)行時(shí)不死鎖，實(shí)現(xiàn)互斥
while(flag[j] && victim == i){} // 互斥意味著等待
}
public void unlock(){
int i = ThreadID.get();
flag[i] = false;
}
}
Bakery鎖支持n個(gè)線程的互斥協(xié)議。通過數(shù)學(xué)證明了：
n線程的無(wú)死鎖互斥算法需要n個(gè)不同的存儲(chǔ)單元（變量）來保存中間狀態(tài)。
