计算机多内核平台上的并发锁优化(一)

1
2
3
4
5

​    boolean test_and_set(*lock){
​       boolean old=*lock;
​       *lock=true;
​       return old;
    }

1
2
3
4
5
6

  do{
       //当*lock为false是跳出该循环
       while(test_and_set(*lock));
       critical section;//访问临界区
      *lock=false;
}while(true)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void swap(boolean *a,boolean *b){
    boolean temp=*a;
    *a=*b;
    *b=temp;
}
do{
    key=true;
    do{
    swap(&lock,&key);
    }while(key)
    //上面初值为false
    cirtical section//访问临界资源
    lock=false;
}while(true)

1

while(test_and_set(*lock));

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class CLHLock {
    private final ThreadLocal<QNode> prev; 
    private final ThreadLocal<QNode> current; 
    private final AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());

    public CLHLock() {
        this.prev = new ThreadLocal<QNode>() {
            @Override
            protected QNode initialValue() {
                return null;
            }
        };
        this.current = new ThreadLocal<QNode>() {
            @Override
            protected QNode initialValue() {
                return new QNode();//线程本地缓存
            }
        };
    }

    public void lock() {
        QNode current = this.current.get(); 
        current.locked = true;
        QNode pred = this.tail.getAndSet(current); 
        this.prev.set(pred); 
        while (pred.locked) ;//自旋
    }

    public void unlock() {
        QNode current = this.current.get();
        current.locked = false;
        this.current.set(this.prev.get());
        current = null;//GC
    }

    private static class QNode {
        private volatile boolean locked = false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    /**
     * Wait queue node class.
     *
     * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
     * Hagersten) lock queue. CLH locks are normally used for
     * spinlocks.  We instead use them for blocking synchronizers, but
     * use the same basic tactic of holding some of the control
     * information about a thread in the predecessor of its node.  A
     * "status" field in each node keeps track of whether a thread
     * should block.  A node is signalled when its predecessor
     * releases.  Each node of the queue otherwise serves as a
     * specific-notification-style monitor holding a single waiting
     * thread. The status field does NOT control whether threads are
     * granted locks etc though.  A thread may try to acquire if it is
     * first in the queue. But being first does not guarantee success;
     * it only gives the right to contend.  So the currently released
     * contender thread may need to rewait.

1

  while (pred.lock) ;//自旋

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class MCSLock  {
    private AtomicReference<QNode> tail;
    private ThreadLocal<QNode> current;

    public void lock() {
        this.tail = new AtomicReference<QNode>(new QNode());  
        QNode current = this.current.get();
        QNode pred = this.tail.getAndSet(current);
        if (pred != null) {
            current.locked = true;
            pred.next = current;
            while (current.locked) ;//自旋
        }
    }

    public void unlock() {
        QNode current = this.current.get();
        if (current.next == null) {
            if (tail.compareAndSet(current, null)){
                return;
            }
            while (current.next == null) ;//自旋
        }
        current.next.locked = false;//通知下一个节点
        current.next = null;
    }

    private static class QNode {
       volatile boolean locked = false;
        QNode next = null;
    }
}