Java Semaphore 동작 원리 deep dive

✅ 개요

목적

• Jetty의 VirtualThreadPool에서 성능 이슈가 있을지 확인.
• 내부에서 Semaphore를 사용 중인데, 자원 획득을 기다리는 스레드들이 모두 busy waiting인지 점검.
• 공정성 정책인 경우만 고려함.

Jetty의 VirtualThreadPool.execute의 기본적인 동작 과정

1. Jetty의 VirtualThreadPool에 task를 제출합니다.
2. 가상스레드가 실행 된 후 제출된 task를 실행하기 전에 Semaphore 획득을 시도합니다.
3. Semaphore 획득에 성공하면 task를 실행합니다.
4. task 실행을 마치거나 task 실행 중 예외가 발생한 경우에 Semaphore 자원을 반환합니다.

https://github.com/jetty/jetty.project/blob/jetty-12.0.x/jetty-core/jetty-util/src/main/java/org/eclipse/jetty/util/thread/VirtualThreadPool.java

jetty.project/jetty-core/jetty-util/src/main/java/org/eclipse/jetty/util/thread/VirtualThreadPool.java at jetty-12.0.x · jetty/

package org.eclipse.jetty.util.thread;

public class VirtualThreadPool .. {
...
		@Override
		public void execute(Runnable task)
		{
		    Runnable job = task;
		    Semaphore semaphore = _semaphore;
		    if (semaphore != null)
		    {
		        job = () ->
		        {
		            try
		            {
		                // The caller of execute(Runnable) cannot be blocked,
		                // as it is unknown whether it is a virtual thread.
		                // But this is a virtual thread, so acquiring a permit here
		                // blocks the virtual thread, but does not pin the carrier.
		                semaphore.acquire();
		                task.run();
		            }
		            catch (InterruptedException x)
		            {
		                // Likely stopping this component, exit.
		                if (LOG.isDebugEnabled())
		                    LOG.debug("interrupted while waiting for permit {}", task, x);
		            }
		            finally
		            {
		                semaphore.release();
		            }
		        };
		    }
		    _virtualExecutor.execute(job);
		}
}

 

 

용어 정리

1. permit : Semaphore에 남은 자원 수.
2. acquire : Semaphore에 접근하기 위한 권한을 획득한 행위.
3. release : Semaphore에 자원을 반환하는 행위.
4. park : 스레드 스케줄링의 대상이 되지 않고, 휴면 상태(dormant)로 변함.
5. unpark : park로 인해 blocking 돼있다면, unblock 상태로 바꿈. permit을 얻을 수 있는 상태로 변경.
6. barge : unfair 획득 요청이 들어와서 큐에 들어가지 않고 바로 permit을 획득하는 경우
7. spins : 스레드 blocking 되기 전까지 busy waiting을 반복할 횟수.

 

Java Semaphore, 공정성 정책의 경우, 동작 방식

/*
* Semaphore 내 양방향 Linked list 형태
* - head: 큐에 들어갔던 노드 중 자원을 마지막으로 획득한 노드
* - first: 자원 획득을 시도할 자격이 있는 노드
* - tail: Linked list 꼬리
* 
*  +------+  prev +-------+       +------+
*  | head | <---- | first | <---- | tail |
*  +------+       +-------+       +------+
*
*/

• Semaphore는 내부에서 양방향 Linked list를 이용하여 자원 획득 순서를 관리함.
• 스레드가 semaphore.acquire()를 실행하면 자원 획득 시도를 한 후 실패 시 tail에 들어간채 park됨.
• 자원을 반환하는 스레드가 semaphore.release()를 실행하면 자원 반환 후 first를 unpark
• first가 자원 획득에 성공한다면 자신을 head로 바꾸고 자신의 다음 노드를 unpark.
• first는 spins(busy waiting을 반복할 횟수) 만큼 for 문에서 acquire를 시도하지만 spins==0이 되면 다시 park됨.

---

✅ Semaphore에 1개의 자원을 요청하는 경우

조건

• Semaphore의 permit이 2임.
• 스레드 4개(T1, T2, T3, T4)가 순서대로 Semaphore에 자원 획득 요청(acquire)하는 상황
• 단순화 하기 위해 자원은 1개만 획득 요청함. acquire(1) 연산과 같음.
• Semaphore 내부의 양방향 Linked list를 구성하는 Node는 prev, next, thread, state로 구성됨.

https://github.com/openjdk/jdk/blob/890adb6410dab4606a4f26a942aed02fb2f55387/src/java.base/share/classes/java/util/concurrent/locks/AbstractQueuedSynchronizer.java#L467

 

1. T1이 자원 한개를 요청함

1. 성공함
   • 큐에 들어가지 않음. 자원을 바로 획득할 수 있는데 park되는 것은 비효율적이기 때문
   • 실제로 AbstractQueuedSynchronizer.acquireSharedInterruptibly 함수에서 tryAcquireShared(arg)를 먼저 실행 후 성공하면 acquire(..)를 실행하지 않음.
   • tryAcquireShared : Semaphore를 공정성 정책(FairSync)으로 실행할 경우, 큐에 데이터가 없다면 바로 자원 획득을 시도함.
   • acquire(..) : 스레드를 queue에 넣음(정확히 말하면 양방향 Linked list). 이후 해당 스레드는 blocking과 unblocking을 반복함. 정확히 말하면 first가 되기 전까지는 park(block)되고, first가 되면(unblock 상태) spins 값이 0이 될때 까지 busy wait를 함. spins=0이 되면 park됨.
2. permit은 1개로 줄어듬.
3. T1은 자원을 획득한 가장 최근 노드이지만 큐에 들어간 적은 없었기 때문에 head로 설정되지 않음.

 

2. T2가 자원 한개를 요청함

1. 성공함
2. permit은 1개로 줄어듬.
3. T2는 자원을 획득한 가장 최근 노드이지만 큐에 들어간 적은 없었기 때문에 head로 설정되지 않음.

 

 

3. T3가 자원 한개를 요청함

1. permits가 0이기 때문에 실패함.
2. Queue에 들어가고, 큐 크기가 1이기에 first로 설정됨.
3. first는 ‘자원 획득을 시도할 자격이 있는 노드’임. 따라서 busy wait을 spins 값만큼 실행(초기 값은 1임)
4. spin 횟수 만큼 실패 후, T3은 park됨.

 

4. T4가 자원 한개를 요청함

1. permits가 0이기 때문에 실패함.
2. Queue에 들어가 tail로 설정됨. 물론 park됨.
3. first는 ‘자원 획득을 시도할 자격이 있는 노드’임. 따라서 busy wait을 spins 값만큼 실행(초기 값은 1임)
4. spin 횟수 만큼 실패 후, T3은 park됨.

 

5. T1이 자원을 반환함.

1. T1은 자원을 반환하며 first에게 ‘혹시 blocking이면 일어나’라고 unpark 호출(Ref).
2. unblocking된 first는 자원 획득에 성공함.
3. 이후 자신 뒤에 있는 노드를 깨움(T4). ‘이제 너가 자원 획득할 차례일 수도’라는 의미.
4. T3는 ‘큐에 들어갔던 노드 중 자원을 마지막으로 획득한 노드’이기 때문에 head가 됨.
5. T4는 first로 바뀜.
6. T4는 자원 획득을 spins 만큼 시도후 다시 block됨 by park.

 

---

✅ Semaphore에 n개의 자원을 요청하는 경우

📣 새로운 가정: T2,T4가 자원을 2개 요구한 상황이라 가정하자. permits 초기값은 3이다.

1. 초기 상황

 

2. T3가 자원을 반환한다.

1. permits 값을 1 증가 시킨다.
2. head의 바로 뒤 노드를 깨운다.
3. T4는 일어난 뒤 자신이 first인 것을 확인한다.
4. 하지만 permits가 1이라 자원 획득에 실패한다.
5. spins 만큼 busy waiting을 한 뒤 blocking된다.

 

3. T2가 자원을 반환한다.

1. permits 값을 2 증가 시킨다.
2. head의 바로 뒤 노드(T4)를 깨운다.
3. T4는 일어난 뒤 자신이 first인 것을 확인한다.
4. permits이 2 이상이므로 T4는 자원을 획득한다.

 

5. T4가 자원 획득 시 head로 바뀐다.

6. 이후 자신 다음 노드인 T5를 깨운다.

7. T5는 자원을 획득할 수 있으니 획득한다.

 

---

✅ Starvation 문제

왜 spin wait를 하나?

• first는 한번 시도하고 자원을 획득할 수 없다면 바로 block(park) 되도 문제 없지 않나?
• 왜 spin wait를 몇번씩 시도하는 것일까?
• 공정성 정책의 경우, 이는 barge(용어, 코드) 때문.
• first가 자원 획득을 시도하려고 하는데 다른 스레드가 세마포어의 tryAcquire() 메소드를 실행하면 first는 자원 획득에 실패함.
• 자원 획득 시도를 처음에는 2회 진행함. 두번째에도 실패하면 thread는 block(park)됨.
  • spin이 0인 경우(Ref) && node.state==WAITING으로 바뀐 경우(Ref)에 thread block 실행(Ref)

 

first가 starvation을 겪을 수 있지 않나?

• tryAcquire이 여러번 일어나면 first는 starvation을 겪는다.
• 따라서 first는 한번 자고 일어나면 자원 획득 시도를 4번 할 수 있게 된다. 기존(2) 보다 2배 더 한다.
• 두번 자고 일어나면 8배 하게 된다. 즉 exponential하게 spin wait 횟수가 증가하여 starvation 문제에 대응한다.
• acquire(..) 로직에서 postSpin은 retry를 할 총 횟수를 의미하고 spins는 남은 retry 횟수를 뜻한다.

✅ first가 park하러 갈 때 마다 retry 가능 횟수를 2배씩 증가시켜 starvation에 대응한다.

---

✅ 결론

성능 상 문제가 없는 이유

• 양방향 Linked list이기 때문에 first 노드 이외엔 모두 sleep.
• 항상 자원 1개만 요구하고 1개만 반환하기 때문에 first는 깨어나면 무조건 자원을 획득함.
• first가 깨어나더라도 barge(비공정하게 자원을 획득하는 행위)가 일어나면 spin wait 할 수 있음.
• semaphore.tryAcquire() 메소드를 실행하면 nonfairTryAcquireShared(1)을 실행함. 이때 barge 발생.
• 하지만 FixedVirtualThreadExecutor의 execute 메소드에서는 semaphore.acquire()만 사용하기 때문에 barge 문제 없음.