我們先将演進條件分為四個主要類别，阻塞（blocking），無幹擾（obstruction-free），無鎖（lock-free），和無等待（wait-free）。詳細清單如下：
blocking 1. blocking 2. starvation-free obstruction-free 3. obstruction-free lock-free 4. lock-free (lf) wait-free 5. wait-free (wf) 6. wait-free bounded (wfb) 7. wait-free population oblivious (wfpo)
在我們開始解釋每一個術語的意義之前，讓我們先了解一些相關細節。
根據《the art of multiprocessor programming》一書3.6節中的相關描述，我們很難了解有界無等待（wait-free bounded，注：參考[1]）和集居數無關無等待（wait-free population oblivious，注：參考[1]）的概念是否相關。就我個人而言，我認為一個算法如果滿足集居數無關無等待，就意味着這個算法是有限界的，進而這個算法也滿足有界無等待。這代表一個方法（或者是一個算法，一個類）可以是無等待，或者有界無等待，或者集居數無關無等待，最後一個條件是所有演進條件中“最好”的。
在這篇文章中我們讨論的例子都是關于某個（一個算法中，或一個類中）的特定方法的演進條件，而不是完整的算法。我們這樣做的原因是一個算法中不同的方法可能會采用不同的演進保證（progress guarantees），舉個例子：（某個算法）寫操作可能是阻塞的，然而讀操作是滿足集居數無關無等待，這樣的情況在你第一次觀察某個無鎖和無等待資料結構的時候并不是顯而易見的。
是的，你的結論是正确的：一個資料結構中可能有某些操作是阻塞的，另外一些操作是無鎖的，剩下的甚至是無等待的。另一方面，當我們稱某個特定的資料結構是無鎖，這代表這個資料結構的所有操作都是無鎖，或者更好的狀态（無等待或者更好）。
事實上在著作中沒有嚴格對那種狀态更好有嚴格的定義，但是一般而言說是這樣的：
無等待>無鎖>阻塞
上述說法的理由是：現實中并沒有太多無鎖或者是無等待的（實用）資料結構，是以通常不會出現關于演進狀态合理分類的問題。andreia和我提出了很多不同種類的并發算法，其中混合了各種演進狀态。是以我們需要對這些演進狀态合理地命名，并且對他們排序，進而繼續對他們的處理，并且發現哪些算法值得研究。
我們提出的順序就是文章開頭描述的清單，表中阻塞是最差的，集居數無關無等待是可能達到的最好狀态。
另一個通常會導緻困惑的說法是“無等待意味着無鎖”（但是不能反過來說）。這意味着一個方法如果滿足無等待，那麼這個方法有着和一個無鎖方法同樣的演進保證。下圖是一張venn圖，可能能夠更好的解釋我們的意思。
這張圖展示了算法的集合，圖中無等待的算法也是無鎖算法的一部分。
阻塞是大家所熟知的。基本所有加鎖的算法都可以說是阻塞的。某個線程所引起的意外延遲會阻止其他線程繼續運作。在最壞的情況下，某個占有鎖的線程可能被睡眠，進而阻止其他等待鎖釋放的線程進行接下來的任何操作。
定義：
一個方法被稱為阻塞的，即這個方法在其演進過程中不能正常運作直到其他（占有鎖的）線程釋放。
例子：
循環中對擁有兩個狀态的變量的簡單cas操作
<code>01</code>
<code>atomicinteger lock =</code><code>new</code> <code>atomicinteger(</code><code>0</code><code>);</code>
<code>02</code>
<code>03</code>
<code>public</code> <code>void</code> <code>funcblocking() {</code>
<code>04</code>
<code>05</code>
<code> </code><code>while</code> <code>(!lock.compareandset(</code><code>0</code><code>,</code><code>1</code><code>)) {</code>
<code>06</code>
<code>07</code>
<code> </code><code>hread.yield();</code>
<code>08</code>
<code>09</code>
<code> </code><code>}</code>
<code>10</code>
<code>11</code>
<code>}</code>
（無饑餓）有的時候也被稱為無閉鎖。這是一個獨立的性質，隻有當底層平台/系統提供了明确的保障以後讨論這個性質才有意義。
隻要有一個線程在互斥區中，那麼一些希望進入互斥區域的線程最終都能夠進入互斥區域（即使之前在互斥區中的線程意外停止了）。
一個嚴格公平的互斥鎖通常是無饑餓的。
在jdk 8中的stampedlock有這樣的性質，因為它建立了一個線程隊列（連結清單）等待擷取鎖。這個隊列的插入操作是無鎖的，但是在插入之後，每個線程都會自旋或者讓步進而被目前占有鎖的線程鎖阻塞。釋放鎖的線程采用unsafe.park()/unpark()機制，夠喚醒下一個在隊列中等待的線程，進而執行了嚴格的優先級。這個機制的意義是，如果給予其他線程（占有鎖的線程）足夠的時間去完成他們的操作，那麼目前線程可以確定最終擷取鎖，然後完成自己的操作。
有關stampedlock的源碼詳見這裡：
<a href="http://grepcode.com/file/repo1.maven.org%[email protected]%[email protected]@jsr166e%24stampedlock.java">http://grepcode.com/file/[email protected][email protected]@jsr166e$stampedlock.java</a>
這是一個非阻塞性質。關于無幹擾和無饑餓的更多細節可以檢視《the art of multiprocessor programming》(revised edition)的第60頁。
如果一個方法滿足無幹擾性質，那麼這個方法從任意一點開始它的執行都是隔離的，并且能夠在有限步内完成。
我所知道的唯一例子就是maurice herlihy，mark moir和victor luchangco所提出的double-ended queue。
<a href="http://cs.brown.edu/~mph/herlihylm03/main.pdf">http://cs.brown.edu/~mph/herlihylm03/main.pdf</a>
無鎖的性質保證了至少有一個線程在正常運作。在理論上這代表了一個方法可能需要無限的操作才能完成，但是在實踐中隻需要消耗很短的時間，否則這個性質就沒有什麼價值了。
如果一個方法是lock-free的，它保證線程無限次調用這個方法都能夠在有限步内完成。
一個調用cas操作的循環增加原子整形變量。
<code>atomicinteger atomicvar =</code><code>new</code> <code>atomicinteger(</code><code>0</code><code>);</code>
<code>public</code> <code>void</code> <code>funclockfree() {</code>
<code> </code><code>int</code> <code>localvar = atomicvar.get();</code>
<code> </code><code>while</code> <code>(!atomicvar.compareandset(localvar, localvar+</code><code>1</code><code>)) {</code>
<code> </code><code>localvar = atomicvar.get();</code>
<code>12</code>
<code>13</code>
另外一個比較著名的例子是java.util.concurrent中的concurrentlinkedqueue，其中add()和remove()操作是無鎖的。
無等待性質保證了任何一個時間片内的線程可以運作，并且最後完成。這個性質保證步驟是有限的，但是在實踐中，這個數字可能是極大的，并且依賴活動的線程數目，是以目前沒有很多實用的無等待資料結構。
假如一個方法是無等待的，那麼它保證了每一次調用都可以在有限的步驟内結束。
這篇論文給出了一個無等待（有界無等待）算法的例子。
<a href="http://www.cs.technion.ac.il/~moran/r/ps/bm94.ps">http://www.cs.technion.ac.il/~moran/r/ps/bm94.ps</a>
任何一個有界無等待的算法，也是無等待的（但并不一定是集居數無關無等待的）。
如果一個方法是有界無等待的，那麼這個方法保證每次調用都能夠在有限，并且有界的步驟内完成。這個界限可能依賴于線程的數量。
一個掃描/寫入到長度和線程數目相關的數組的方法。如果數組中每個條目的操作數是常量，那麼顯然這個方法是有界無等待的，并且不是集居數無關無等待，因為數組的長度和線程的數目有關。
<code>atomicintegerarray intarray =</code><code>new</code> <code>atomicintegerarray(max_threads);</code>
<code>public</code> <code>void</code> <code>funcwaitfreebounded() {</code>
<code> </code><code>for</code> <code>(</code><code>int</code> <code>i =</code><code>0</code><code>; i < max_threads ; i++) {</code>
<code> </code><code>intarray.set(i,</code><code>1</code><code>);</code>
這個性質用來描述這些在一定數量步驟内完成一些指令，并且指令數目與活動線程數目無關的方法。任何一個集居數無關無等待的方法都是有界無等待的。
一個無等待的方法，如果其性能和活動線程數目無關，那麼被稱為集居數無關無等待的。
最簡單的例子是使用fetch-and-add原語(在x86 cpu上是xadd指令)增加一個原子變量。這個操作可以用c11/c++11中的fetch_add()原子方法完成。
<code>1</code>
<code>atomic counter;</code>
<code>2</code>
<code>3</code>
<code>void</code> <code>funcwaitfreeboundedpopulationoblivious() {</code>
<code>4</code>
<code>5</code>
<code> </code><code>counter.fetch_add(</code><code>1</code><code>);</code>
<code>6</code>
<code>7</code>
上述的這些并不是問題的全部。我們忽略了兩個了解全貌需要掌握的知識點：
第二點，關于演進條件的完整概念是用于将算法和方法按照時間保證分類，但是這些定義卻是基于操作數目。這基于一個操作的完成時間與活動線程數目無關這個假設的，這些假設在單線程代碼中是正确的，但是在多線程程式中将會失效。
總的來說，對于傾向于數學的讀者，這裡有我提出的定義：
設f為一個函數方法 設l為同時調用f的并發線程數目 設n為一個與l無關的變量 設opsf()代表一個指定線程完成f需要進行的操作數目。 設c(n,l)為一個依賴n和l的函數
當任何有限值l滿足以下條件時，f方法是對應的進行狀态：
lock-free： 如果至少有一個l線程在有限步驟内完成操作；opsf() < c(n,l) wait-free： 如果所有的l個線程在有限的步驟内完成操作：opsf() < c(n,l) wait-free bounded： 如果所有的l個線程消耗c(n,l)或者更少的時間完成操作：opsf() < c(n,l) wait-free population oblivious： 如果所有的l個線程在有限操作内完成f，并且和l無關：opsf() < c(n)
在實踐中，“無等待”和“有界無等待”的差別很小，這篇論文中有很好的解釋：
另一個細節是，并沒有“集居數無關無等待”（的資料結構，注：準确的話說是沒有一個所有方法都是集居數無關無等待的資料結構），因為達到集居數無關的狀态意味着，f方法有一個使其運作結束所需的最壞操作數目上限。
希望這篇文章可以幫助你了解lock-free和wait-free的差別。