多线程之Semaphore原理

1 加锁解锁

Semaphore 有点像一个停车场，permits 就好像停车位数量，当线程获得了 permits 就像是获得了停车位，然后 停车场显示空余车位减一,刚开始，permits（state）为 3，这时 5 个线程来获取资源.

如其中 Thread-1，Thread-2，Thread-4 cas 竞争成功，而 Thread-0 和 Thread-3 竞争失败，进入 AQS 队列 park 阻塞.

此时 Thread-4 释放了 permits，状态如下:

Thread-0 竞争成功，permits 再次设置为 0，设置自己为 head 节点，断开原来的 head 节点，unpark 接 下来的 Thread-3 节点，但由于 permits 是 0，因此 Thread-3 在尝试不成功后再次进入 park 状态

2 代码说明

NonfairSync 源码说明

static final class NonfairSync extends Sync {
 private static final long serialVersionUID = -2694183684443567898L;
    
 NonfairSync(int permits) {
     // permits 即 state
     super(permits);
 }
 
 // Semaphore 方法
 public void acquire() throws InterruptedException {
     sync.acquireSharedInterruptibly(1);
 }
    
 // AQS 继承过来的方法
 public final void acquireSharedInterruptibly(int arg)
 throws InterruptedException {
     if (Thread.interrupted())
     throw new InterruptedException();
     
     if (tryAcquireShared(arg) < 0)
     doAcquireSharedInterruptibly(arg);
}
 
 // 尝试获得共享锁
 protected int tryAcquireShared(int acquires) {
     return nonfairTryAcquireShared(acquires);
 }
 
 // Sync 继承过来的方法
 final int nonfairTryAcquireShared(int acquires) {
     for (;;) {
         int available = getState();
         int remaining = available - acquires; 
         if (
         // 如果许可已经用完, 返回负数, 表示获取失败, 进入 doAcquireSharedInterruptibly
         remaining < 0 ||
         // 如果 cas 重试成功, 返回正数, 表示获取成功
         compareAndSetState(available, remaining)

         ) {
             return remaining;
         }
     }
 }
 
 // AQS 继承过来的方法
 private void doAcquireSharedInterruptibly(int arg) throws InterruptedException {
     final Node node = addWaiter(Node.SHARED);
     boolean failed = true;
     try {
         for (;;) {
             final Node p = node.predecessor();
             if (p == head) {
                 // 再次尝试获取许可
                 int r = tryAcquireShared(arg);
                 if (r >= 0) {
                     // 成功后本线程出队（AQS）, 所在 Node设置为 head
                     // 如果 head.waitStatus == Node.SIGNAL ==> 0 成功, 下一个节点 unpark
                     // 如果 head.waitStatus == 0 ==> Node.PROPAGATE 
                    // r 表示可用资源数, 为 0 则不会继续传播
                     setHeadAndPropagate(node, r);
                     p.next = null; // help GC
                     failed = false;
                     return;
                 }
             }

             // 不成功, 设置上一个节点 waitStatus = Node.SIGNAL, 下轮进入 park 阻塞
             if (shouldParkAfterFailedAcquire(p, node) &&
             parkAndCheckInterrupt())
             throw new InterruptedException();
         }
     } finally {
         if (failed)
             cancelAcquire(node);
         }
     }
 
     // Semaphore 方法
     public void release() {
         sync.releaseShared(1);
     }
 
     // AQS 继承过来的方法
     public final boolean releaseShared(int arg) {
         if (tryReleaseShared(arg)) {
             doReleaseShared();
             return true;
         }
         return false;
     }
 
     // Sync 继承过来的方法
     protected final boolean tryReleaseShared(int releases) {
         for (;;) {
         int current = getState();
         int next = current + releases;
         if (next < current) // overflow
         throw new Error("Maximum permit count exceeded");
         if (compareAndSetState(current, next))
         return true;
         }
     }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

3 扩展

为啥有PROPAGATE

最早存在bug. 如:

• releaseShared 方法

public final boolean releaseShared(int arg) {
     if (tryReleaseShared(arg)) {
         Node h = head;
         if (h != null && h.waitStatus != 0)
         unparkSuccessor(h);
         return true;
     }
     return false;
}

1
2
3
4
5
6
7
8
9
10

• doAcquireShared 方法

private void doAcquireShared(int arg) {
     final Node node = addWaiter(Node.SHARED);
     boolean failed = true;
    
     try {
         boolean interrupted = false;
         for (;;) {
             final Node p = node.predecessor();
             if (p == head) {
                 int r = tryAcquireShared(arg);
                 if (r >= 0) {
                     // 这里会有空档
                     setHeadAndPropagate(node, r);
                     p.next = null; // help GC
                     if (interrupted)
                     selfInterrupt();
                     failed = false;
                     return;
                 }
             }
             if (shouldParkAfterFailedAcquire(p, node) &&
             parkAndCheckInterrupt())
             interrupted = true;
         }
     } finally {
         if (failed)
         cancelAcquire(node);
     }
}
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

• setHeadAndPropagate 方法

private void setHeadAndPropagate(Node node, int propagate) {
     setHead(node);
     // 有空闲资源
     if (propagate > 0 && node.waitStatus != 0) {
         Node s = node.next;
         // 下一个
         if (s == null || s.isShared())
         unparkSuccessor(node);
     }
}

1
2
3
4
5
6
7
8
9
10
11

假设存在某次循环中队列里排队的结点情况为 head(-1)->t1(-1)->t2(-1)

假设存在将要信号量释放的 T3 和 T4，释放顺序为先 T3 后 T4

可能产生bug情况

• 1 T3 调用 releaseShared(1)，直接调用了 unparkSuccessor(head)，head 的等待状态从 -1 变为 0

• 2 T1 由于 T3 释放信号量被唤醒，调用 tryAcquireShared，假设返回值为 0（获取锁成功，但没有剩余资源量）

• 3 T4 调用 releaseShared(1)，此时 head.waitStatus 为 0（此时读到的 head 和 1 中为同一个head），不满足条件，因此不调用 unparkSuccessor(head)

• 4 T1 获取信号量成功，调用 setHeadAndPropagate 时，因为不满足 propagate > 0（2 的返回值也就是 propagate（剩余资源量） == 0），从而不会唤醒后继结点， T2 线程得不到唤醒

修复bug处理

private void setHeadAndPropagate(Node node, int propagate) {
     Node h = head; // Record old head for check below
     // 设置自己为 head
     setHead(node);
     // propagate 表示有共享资源（例如共享读锁或信号量）
     // 原 head waitStatus == Node.SIGNAL 或 Node.PROPAGATE
     // 现在 head waitStatus == Node.SIGNAL 或 Node.PROPAGATE
     if (propagate > 0 || h == null || h.waitStatus < 0 ||
     (h = head) == null || h.waitStatus < 0) {
         Node s = node.next;
         // 如果是最后一个节点或者是等待共享读锁的节点
         if (s == null || s.isShared()) {
             doReleaseShared();
         }
     }
}


private void doReleaseShared() {
     // 如果 head.waitStatus == Node.SIGNAL ==> 0 成功, 下一个节点 unpark
     // 如果 head.waitStatus == 0 ==> Node.PROPAGATE 
     for (;;) {
         Node h = head;
         if (h != null && h != tail) {
             int ws = h.waitStatus;
             if (ws == Node.SIGNAL) {
                 if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                 continue; // loop to recheck cases
                 unparkSuccessor(h);
             }
             else if (ws == 0 &&
             !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
             continue; // loop on failed CAS
         }
         if (h == head) // loop if head changed
         break;
     }
}
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

说明:

• 1 T3 调用 releaseShared()，直接调用了 unparkSuccessor(head)，head 的等待状态从 -1 变为 0

• 2 T1 由于 T3 释放信号量被唤醒，调用 tryAcquireShared，假设返回值为 0（获取锁成功，但没有剩余资源 量）

• 3 T4 调用 releaseShared()，此时 head.waitStatus 为 0（此时读到的 head 和 1 中为同一个 head），调用 doReleaseShared() 将等待状态置为 PROPAGATE（-3）

• 4 T1 获取信号量成功，调用 setHeadAndPropagate 时，读到 h.waitStatus < 0，从而调用 doReleaseShared() 唤醒 T2