lock, lock-free programming에 관한 글들을 정리

"컴퓨터 밑바닥의 비밀"이라는 책에서 잠금 제어와 잠금 없는 프로그래밍을 보고 조사한 내용들을 정리

A Complete Guide to Lock Convoys #

https://davekilian.com/lock-convoys.html

lock convoy는 IBM 연구자들이 1970년대 후반 낸 메모에서 명명되었다.

IBM의 메모 - THE CONVOY PHENOMENON #

2차선 도로에선 차들이 무리지어 있을 때가 많음. 빨리 달리는 차도 그렇게 가다가 느리게 달리는 차에 막혀서 빨리 못 가기 때문. 이런 시스템이 평형을 이루면 가장 느린 차에 맞춰서 무리를 이루게 된다.

공유 자산을 위해 경합하는 트랜잭션들이 있을 때 이 충돌은 락을 두고 경쟁하는 형태로 나타남

일반적으로 공유 자원에 접근하는 패턴

LOCK <자원>;
<자원에 대한 작업 수행>;
UNLOCK <자원>;

LOCK이 점유중인 공유자원에 자원에 다른 프로세서가 접근시

이런 대기가 없을 때 락 설정/해제 -> 10개 정도 명령어. 대기가 있으면 약 50개의 명령어와 두 번의 프로세스 디스패치(즉, 수천 개의 명령어 수행에 해당하는 비용)가 추가로 필요

락에 대해 중요한 3가지 통계 수치

단일 프로세서 시스템에서 락의 충돌 단면적은 대기시간, 요청이 대기해야 할 시의 태스크 스위칭 시간(만약 요청이 대기할 필요가 없으면 스위칭이 필요 없으므로) 제외시 지속시간 / (지속시간 + 실행간격)

시스템 R(문서의 예시로 드는 시스템인데 IBM에서 만든 DB 시스템이었다고 한다 https://en.wikipedia.org/wiki/IBM_System_R)에는 3개의 high-traffic 락이 존재. 각각 버퍼 풀, 복구로그, 시스템 진입/종료에 대한 접근을 제어. 이들의 통계 측정치는 다음과 같다.

| Resource | Execution Interval | Duration | Collision Cross Section |
|----------|--------------------|----------|-------------------------|
| Buffer Pool | 1000 | 60 | 6% |
| Recovery Log | 1500 | 70 | 5% |
| System Entry/Exit | 20000 | 300(평균치) | 1.5% |

가상 락 L을 가정한다. 실행 간격은 1000, 지속 시간은 100. 그러니 충돌 단면적은 대략 10%이다.

프로세스 P1이 이 high-traffic 락 L을 점유한 채로 멈춘(대기 상태로 들어간) 상황을 가정한다면 이렇게 된다.

즉 P1은 sleep 상태이고 다른 모든 프로세스는 락을 기다리는 중

******
* PI *<---|P2|<---|P3|<---...<---|Pn|
******
holder     convoy of waiters ........

상황의 동적인 흐름

N개의 프로세스, M개의 프로세서가 있고 N>>M인 상태면 락 대기 큐에는 N-M개 프로세스가 쌓이고 각 프로세스는 1000개의 명령어 실행 간격을 가진다. 시스템은 lock thrashing 상태에 빠진다. 대부분의 CPU 자원이 태스크 스위칭에 소모되는 것.

새 프로세스는 convoy에 빨려들어가고 프로세스가 convoy를 떠났다가 돌아와도 여전히 convoy는 있을 가능성이 높다.

system R 사례 #

System R이 실행되는 VM/370 시스템에서는 프로세스가 다음 다섯 가지 유형의 대기를 겪을 수 있다:

프로세스가 대기를 마치면 해당 프로세스는 디스패치 가능 상태가 되고 디스패처가 이 프로세스를 선택해 실행하면 일정 퀀텀이 할당되고 해당 프로세스는 다음 중 하나가 발생까지 실행

이중 하나가 발생해 프로세스가 중단 시 디스패처가 소모된 시간만큼 프로세스의 타임 슬라이스 소진. 타임 슬라이스 다 썼으면 프로세스는 (CPU 자원이 부족할 경우)타임슬라이스 대기로 진입, 아니라면 일반 대기 상태 진입

근데 프로세스 전환은 비용이 크기 때문에 각 프로세스가 이런 high-traffic lock을 점유하는 시간은 최소화되어야 함. 따라서 system R도 다음과 같은 규칙을 둔다.

하지만 그럼에도 프로세스가 페이지 폴트 발생/퀀텀 소진으로 인해 종료되면(거의 안 일어나지만 스케줄러가 선점형일 경우 발생 가능성이 있다) convoy가 발생

즉 디스패처는 high-traffic lock을 점유하고 있는 프로세스를 절대 중단(interrupt)해서는 안 된다. 다르게 말하면, 선점형 스케줄링(pre-emptive scheduling)은 트랜잭션 기반 시스템에 좋지 않다는 뜻이다. 퀀텀이 소진되었다고 해서 프로세스를 뺏어 버리면 convoy가 생기기 쉬우니까.

하지만 가상 메모리를 사용하는 대부분의 범용 OS에선 선점형 스케줄링을 하므로 convoy는 일어난다. 따라서 convoy가 발생했을 때 그것이 오래 지속되지 않고 빠르게 해소되도록 만드는 것이 중요하다.

가능한 해결책들 #

  1. 한 번에 트랜잭션 하나만 실행하기

싱글스레드를 말하는 거 같다. 이러면 락이 필요없어짐. 하지만 lock convoy가 발생하더라도 멀티스레드 프로그래밍이 더 나은 성능을 보인다고 한다. 멀티프로그래밍을 사용하면 I/O와 연산이 동시에 수행될 수있고 또한 짧은 트랜잭션이 긴 트랜잭션 때문에 불필요하게 지연되지 않기 때문이다.

  1. 락을 아예 피하는 것.

원자적 명령(compare-and-swap)과 기타 프로그래밍 트릭을 잘 활용하면 락 없이도 꽤 많은 문제를 해결할 수 있다. system R에서 시스템 진입/종료 락의 경우 이런 트릭으로 해결했다고 한다. 그러나 high-traffic lock을 완전히 제거하는 데는 실패했다.

  1. 락 트래픽 줄이기

다음과 같은 개선 사항이 있다.

가령 버퍼 풀 전체를 제어하는 하나의 락이 있다면 버퍼 풀을 겹치지 않는 하위 풀 여러개로 나누고 각 하위 풀마다 락을 따로 두는 것. 이러면 실행 간격이 늘어나서 버퍼 풀 컨보이는 없어지기 쉽다. 하지만 이 결과 다른 락 사이에 컨보이가 생기게 되었다고 한다

공유 모드를 사용할 시 락 요청 시 대기 확률을 줄여 준다. 하지만 이런 걸로 컨보이를 완전히 없애기는 힘들다

다음과 같은 해결책도 고려했지만 큰 장점은 없다고 판단

컨보이는 First Come First Served 스케줄링으로 인해 발생하는데 스핀락은 이 전략을 따르지 않기 때문에 컨보이가 발생하지 않음. 하지만 IBM 실험 결과 스핀락을 사용하면 시스템 전체 실행 시간이 오히려 늘어났다고 한다. 스핀락이 CPU 자원을 쓰는 게 컨보이의 비용보다 더 컸다는 것이다.

디스패처를 락 관리에 개입시키는 것 그러니까 디스패처가 락 정보를 알고 태스크 스위칭 시점에 락 소유권을 조정하는 법도 있다. 그러나 부가 처리가 어렵고 관심사 분리에도 좋지 않고 일반화도 어렵다.

진짜 해결책 #

컨보이의 핵심 문제는 락의 부여를 선입선출 방식으로 하는 데 있다. 그러니 모든 락 요청을 무작위 순서로 부여하면?(모든 프로세스가 언젠가는 서비스를 받을 거라는 기대)

이론적으로는 어떤 프로세스는 락 요청이 절대 승인되지 않아서 starve될 수도 있지만 실제로는 각 프로세스가 결국은 락을 얻는다.

DO;
  CONVOY=LATCH.QUEUE; /* atomic pair */
  LATCH=FREE; /* atomic pair */
  DO WHILE(CONV0Y == NIL);
    WAKEUP FIRST OF CONVOY; /* CAR of list */
    CONVOY = REST OF CONVOY; /* CDR of list */
  END;
END;

DO WHILE (LATCH - MINE);
  IF LATCH = FREE THEN LATCH = MINE;
  ELSE
    ENQUEUE ON LATCH;
    SLEEP;
END;

단일 프로세서 환경이라면 P1이 락을 해제하는 상황에서 이렇게 작동한다

락을 해제한 프로세스 P1은 다시 계속 실행됨. 막 깨어났기 때문에 거의 100% 퀀텀 보유 중. 만약 P1이 다시 락이 필요하다면 락은 free 상태. I/O나 락 대기에 들어간다면 락 점유 상태는 아니게 된다. 아무튼 락을 점유한 채 종료될 가능성은 거의 없다. 그리고 컨보이에 있던 임의의 다른 프로세스 P2가 실행될 것. lock free 상태에서 P2가 시작하므로 락 즉시 획득.(락에는 이제 대기 큐가 없다) P2도 높은 확률로 lock 점유 안 한상태에서 종결. 컨보이에 N개 프로세스가 있다면 P**N 확률로 해소된다.

멀티프로세서 케이스. 논리는 똑같다. 하지만 다른 문제가 있음. 만약 락이 각 프로세스가 실행 시간의 10%씩을 락을 점유한다면 2개의 프로세스가 동시에 락에 접근해 충돌할 확률은 약 1%(0.1*0.1) 이런 충돌 발생 시 서로를 기다리는 convoy상태에 빠짐

해결책은 다음과 같다:
락 요청자가 잠시(spin) 몇 개의 명령어 동안 대기하면서 락이 해제되기를 기대한다.
만약 일정 시간 안에 락이 풀리지 않는다면,
프로세스는 대기열에 자신을 등록하고 수면 상태로 전환해야 한다.

이 때 적절한 **스핀 대기 시간(spin time)**은 다음 요소들에 영향을 받는다:

락이 점유된 확률, 프로세서 수, 태스크 전환 비용, 인터럽트 처리 시간, 컨보이의 예상 길이

최악의 경우는 락이 한 번에 여러 프로세스에게 브로드캐스트될 때 발생한다.
System R에서 2개의 CPU를 사용하는 환경이라면,
약 500개의 명령어 정도를 스핀하는 것이 적절한 대기 시간일 수 있다.
즉, 락을 요청할 때 500명령어 동안 락을 계속 확인하며 기다리는 것이다.

디터 가블릭(Dieter Gawlick)은 브로드캐스트 방식이
컨보이를 해제하는 순간에 락 쟁탈 경합(contention)을 유발할 가능성이 높다고 지적한다.

그는 IMS Fast Path에서 다음과 같은 상황을 예로 든다:
체크포인트 프로세스가 로그 락을 보유하고 있고, 다른 모든 프로세스가 그 락을 기다리는 상황.
체크포인트가 끝나는 순간, 모든 프로세스가 동시에 로그 락을 얻으려 하며 치열한 경합이 발생한다.

그래서 가블릭은 다음과 같은 대안을 제안한다:

브로드캐스트 대신, 락을 단순히 FREE로 표시한 후, 대기열의 첫 번째 프로세스만 깨운다. 이 방식에서는 현재 락 보유자와 첫 번째 대기자만이 락을 두고 경쟁하게 되며, 결과적으로 락 접근이 거의 선입선출(FCFS)에 가깝게 유지된다.

이 해결책은 실용 가능하며, 실제로 IMS에서의 컨보이 문제를 해결하는 데 사용된 적도 있다.

하지만 우리의 분석에 따르면 락의 실행 간격이 짧다면, 브로드캐스트 방식이라도 모든 대기자가 거의 즉시 깨어나게 된다. 그 이유는 락이 해제될 때마다 다음 대기자가 새롭게 깨어나기 때문이다. 결론적으로, 두 방식 모두 타당하며 실용적인 해결책이 될 수 있다.

Lock-Free 알고리즘 살펴보기(CAS, Volatile, Java Atomic Variables) #

https://dalichoi.tistory.com/entry/Lock-Free-알고리즘-살펴보기CAS-Volatile-Java-Atomic-Variables

Java같은 경우 Monitor가 Mutex 같은 역할을 한다. 또 synchronized 키워드를 사용하면 JVM이 뮤텍스를 이용한 동기화를 암묵적으로 처리

하지만 락을 사용할 때 경합이 발생하면 컨텍스트 스위칭 오버헤드도 발생하고 암튼 느림 -> lock free 알고리즘. 멀티스레드 환경에서도 정해진 단위시간마다 한 개의 명령어는 실행하게 하자! compare and swap으로 대표됨.

lock 획득 대기 시간도 없어지고 병렬 처리도 더 잘되지만 알고리즘 복잡도 up, 확장성 감소, 메모리 재사용 어렵고 ABA문제 발생

compare and swap #

말 그대로 비교하고 교환한다. 현재 메모리 위치에 저장된 값과 기대 값이 일치하는 경우에만 atomic하게 교환하는 것. 조회+비교+교환을 원자적 처리

만약 A를 1->2로 바꾸려고 하는 시도를 CAS로 하면

  1. A가 1인지 확인
  2. 1인 경우에만 2로 교환
  3. 아니라면 성공할 때까지 루프를 돌면서 재시도

CAS는 캐시 메모리에서 값을 읽어오는 대신 메인 메모리 데이터를 직접 읽어와 처리한다.

메모리 가시성은 한 스레드에서 변경한 데이터를 다른 스레드에서도 똑같이 볼 수 있게 하는 것. 모든 스레드에게 변수의 값이 일관되게 보이도록 한다. 가시성 문제라는 것도 있는데 CPU 캐시의 작업 결과가 메인 메모리에 즉시 반영되지 않는 경우 스레드 간에 데이터가 달리 보일 수 있는 현상.
synchronized 키워드도 가시성을 지원

CAS를 쓰면 lock 없이도 값 안전하게 업데이트 가능. 그러나 충돌이 많이 발생하는 경우 계속 업데이트를 루프로 시도하므로 성능 저하 발생
만약 DB 요청 대기 등 작업 시간이 긴 경우라면 락을 사용하는 등의 방식이 더 효율적

C++의 volatile 키워드를 쓰면 컴파일러 최적화를 방지하고 메모리 가시성을 보장할 수 있다. 변수 값을 읽을 때 CPU 캐시에 저장된 값이 아니라 메인 메모리 값을 읽어서 쓰기 때문이다. 또한 Java의 volatile 키워드는 명령어 순서 변경(Out of Order Execution)을 방지한다.

하지만 Lock, 동기화 기능 등이 동작하지 않으므로 직접 동기화한 코드보다 안정성이 좀 떨어지고 가독성이 떨어짐. 쓰기를 하는 스레드가 하나고 여러 개의 스레드가 읽는 상황에서는 volatile이 동시성을 보장하지만 여러 스레드가 쓰는 경우 동시성 보장 X

Locks Aren't Slow; Lock Contention Is

https://preshing.com/20111118/locks-arent-slow-lock-contention-is/