多处理器编程的艺术第3章并发对象

    未决调用，则必定存在一个响应使得 H·是可线性化的。

 3.7 演进条件(Progress Conditions)         
  -    Such an implementation is called blocking, because an unexpected delay by one
        thread can prevent others from making progress.

   - A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps.
     *  Being wait-free is an example of a nonblocking progress condition, meaning that an arbitrary and
       unexpected delay by one thread (say, the one holding a lock) does not necessarily prevent the
        others from making progress.

    Example of 'Wait Free'
     class WaitFreeQueue {
        volatile int head = 0, tail = 0;
        T[] items;
        public WaitFreeQueue(int capacity) {
          items = (T[])new Object[capacity];
          head = 0; tail = 0;
        }
        public void enq(T x) throws FullException {
          if (tail - head == items.length)
            throw new FullException();
          items[tail % items.length] = x;
          tail++;
        }
        public T deq() throws EmptyException {
          if (tail - head == 0)
            throw new EmptyException();
          T x = items[head % items.length];
          head++;
          return x;
        }
     }
Figure 3.3 A single-enqueuer/single-dequeuer FIFO queue.  

 Example of  'Not Wait Free'
   class LockBasedQueue {
     int head, tail;
     T[] items;
     Lock lock;
     public LockBasedQueue(int capacity) {
       head = 0; tail = 0;
       lock = new ReentrantLock();
       items = (T[])new Object[capacity];
     }
     public void enq(T x) throws FullException {
       lock.lock();
       try {
         if (tail - head == items.length)
           throw new FullException();
         items[tail % items.length] = x;
          tail++;
       } finally {
         lock.unlock();
       }
     }
     public T deq() throws EmptyException {
       lock.lock();
       try {
         if (tail == head)
           throw new EmptyException();
         T x = items[head % items.length];
         head++;
         return x;
       } finally {
         lock.unlock();
       }
     }
   }
 
-    A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number
     of steps.

Lock-free 算法的基础是 CAS (Compareand-Swap) 原子操作。当某个地址的原始值等于某个比较值时，把值改成新值，无论有否修改，返回这个地址的原始值。目前的cpu 支持最多64位的CAS。并且指针 p 必须对齐。

 注：原子操作指一个cpu时钟周期内就可以完成的操作，不会被其他线程干扰。

一般的 CAS 使用方式是：

假设有指针 p, 它指向一个 32 位或者64位数，

   1.
      复制p 的内容（*p）到比较量 cmp （原子操作）
   2.
      基于这个比较量计算一个新值 xchg (非原子操作）
   3.
      调用 CAS 比较当前 *p 和 cmp, 如果相等把 *p 替换成 xchg （原子操作）
   4.
      如果成功退出，否则回到第一步重新进行

第3步的 CAS 操作保证了写入的同时 p 没有被其他线程更改。如果*p已经被其他线程更改，那么第2步计算新值所使用的值(cmp)已经过期了，因此这个整个过程失败，重新来过。多线程环境下，由于 3 是一个原子操作，那么起码有一个线程（最快执行到3）的CAS 操作可以成功，这样整体上看，就保证了所有的线程上在“前进”，而不需要使用效率低下的锁来协调线程，更不会导致死锁之类的麻烦。//参考 http://blog.csdn.net/arau_sh/article/details/6636371
+  We say that a method call executes in isolation if no other threads take steps.
- Definition 3.7.1. A method is obstruction-free if, from any point after which it
   executes in isolation, it finishes in a finite number of steps.