[OSTEP] 병행성 CH28 락 Lock

CH28 락 Lock 

여러 개의 명령어들을 원자적으로 실행하고 싶지만, 단일 프로세서의 인터럽트 등으로 인해 겪는 어려움을 락 Lock 을 이용해 해결해 보고자 한다, 프로그래머들은 소스 코드의 임계 영역을 락으로 감싸서 해당 영역이 하나의 원자 단위 명령어처럼 실행되도록 한다 

🐣 원자성 Atomicity - 원자적으로 실행된다는 것은 그 작업이 중단되지 않고 한 번에 완료된다는 의미, 즉, 작업이 진행되는 동안 다른 작업이 개입할 수 없고, 결과는 항상 일관성을 유지해야 한다는 말이다, 그리고 CH26 P315에 아래와 같은 말이 있다

연속된 동작들을 원자적으로 만든다는 개념은 간단하게 "전부 아니면 전무" 라고 표현할 수 있다
수행하려는 모든 동작이 모두 다 처리된 것처럼 보이거나 실행되다가 동작을 묶어 하나의 원자적 동작이 되도록 만든 것을 트랜잭션이라
고 부른다

++ 원자성 추가 설명 - 여러 명령어가 있다가, 중간에 한 명령어에서 에러가 나면 그 전의 명령어 실행도 취소가 된다 

++ 스터디 중에 나온 말

원자성(Atomicity): 어떤 것이 더 이상 쪼개질 수 없는 성질
코드에서의 원자성의 의미: 작업이 끝까지 실행되거나 아예 실행되지 않는 경우를 뜻한다.
 - 인터럽트가 발생해도 명령어 한 줄이 실행 중이라면 문맥 교환이 바로 일어나지 않는다. 프로세서는 항상 한 명령어가 실행이 완료가 되고 난 뒤에 인터럽트 신호를 확인한다.
 - 비결정적 결과가 나오는 이유는 명령어가 여러 줄로 되어있어서, 인터럽트(문맥교환)가 언제 발생하느냐에 따라 명령어의 실행 순서가 달라지기 때문이다.
명령어 한 줄에 모든 걸 담아서, 실행하는 동안 인터럽트의 방해를 받지 않겠다!!

또한 임계 영역은 P317에서, 임계 영역 Critical Section - 보통 변수나 자료 구조 같은 공유 자워을 접근하는 코드의 일부분이라고 한다

28.1 락 - 기본 개념 

balance = balance + 1 과 같은 임계 영역이 있다고 할 때, 아래와 같이 락으로 임계 영역을 감쌀 수 있다 

lock_t mutex; // 글로벌 변수로 선언된 락 
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

 

락은 일종의 변수이기 때문에, 락을 사용하기 위해서는 먼저 선언해야 한다 (lock_t mutex;)

락은 둘 중 하나의 상태를 가진다

1) 사용 가능 available 상태 (unlocked or free) - 어떤 쓰레드도 락을 소유하지 않은 상태 

2) 사용 중 acquired 상태 - 임계 영역에서 정확히 하나의 쓰레드가 락을 획득한 상태 

이 락 자료 구조에서 락을 보유한 쓰레드에 대한 정보나, 락을 대기하는 쓰레드들에 대한 정보를 저장할 수도 있다 

 

lock() 루틴 호출을 통해 락 획득을 시도하고, 락을 획득하면 임계 영역 내로 진입한다 (락 소유자 Onwer - 락을 획득한 쓰레드)

만약 다른 쓰레드가 lock()을 호출할 경우 (여기서 mutex에 해당), 락이 사용 중인 동안에는 lock() 함수는 리턴하지 않는다 

락을 소유한 쓰레드가 임계 영역에 존재하는 상태에서는 다른 쓰레드들이 임계 영역으로 진입할 수가 없다 

 

락 소유자가 unlock() 을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다

대기 중인 쓰레드가 없었다면 (어떤 쓰레드도 lock()을 호출하여 멈춰 있던 상태가 아니라면) 락의 상태는 사용 가능으로 유지된다 

만약 대기 중이던 쓰레드가 있었다면 (lock()으로 인해 멈춘), 락의 상태 변경을 인지하고 락을 획득하여 임계 영역 내로 진입한다 

 

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다, 락으로 코드를 감싸서 프로그래머는 그 코드 내에서는 하나의 쓰레드만 동작하도록 보장할 수 있다 

28.2 Pthread 락 

쓰레드 간에 상호 배제 Mutual Exclusion 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex 라고 부른다 

POSIX 에서는 (다른 함수를 보호하기 위해서) 다른 락을 사용할 수 있기 때문에, 락과 언락 함수에 락의 변수명을 인자로 전달한다

Coarse-grained 락 사용 전략 - 하나의 락으로 모든 임계 영역들을 보호

Fine-grained 락 사용 전략 - 다수의 쓰레드가 서로 다른 락으로 보호된 코드 실행 

28.3 락의 구현 

핵심 질문 - 락은 어떻게 만들까 
효율적인 락은 어떻게 만들어야 하는가? 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공하고 다음에 다룰 몇 가지 속성들을 추가로 가져야 한다, 어떤 하드웨어 지원이 필요한가? 어떤 운영체제 지원이 필요한가?

사용 가능한 락을 만들기 위해서는 하드웨어와 운영체제의 도움을 받아야 한다 

28.4 락의 평가 

락 설계 시, 락의 정상 동작 여부 판단을 위한 평가 기준은 아래와 같다 

1) 상호 배제를 제대로 지원하는가 

락이 도작하여 임계 영역 내로 다수의 쓰레드가 진입을 막을 수 있는지

2) 공정성 Fairness

쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가? 굶주리는 Starve 경우가 발생하는가? 

3) 성능 Performance 

락 사용 시간적 오버헤드 평가 - 경쟁이 전혀 없는 경우의 성능, 하나의 쓰레드가 락 획득/ 해제하는 데 걸리는 부하, 단일 CPU 상에서 여러 쓰레드가 락을 획득하려고 경쟁할 때의 성능, 멀티 CPU 상황에서 락 경쟁 시의 성능 등 

28.5 인터럽트 제어

초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했었다

void lock() {
	DisableInterrupts();
}
void unlock() {
	EnableInterrupts();
}

이 방법은 단순하다는 장점이 있지만, 심각한 문제를 가져올 수도 있고 매우 비효율적이기 때문에 제한된 범위에서만 사용해야 한다 

28.6 실패한 시도 - 오직 Load/ Store 명령어만 사용하기

아래와 같은 코드로 간단한 변수 flag 를 사용하여 쓰레드가 락을 획득하였는지를 확인하는 방법이다

typedef struct __lock_t{int flag;} lock_t;

void init (lock_t *mutex){
	// 0 -> 락 사용 가능, 1 -> 락 사용 중
    mutex->flag = 0;
}

void lock (lock_t *mutex){
	while (mutex->flag == 1) // flag 변수를 검사 (TEST) 함
    ; // spin-wait (do-nothing)
    mutex->flag = 1; // 설정 (SET) 한다 
    
void unlock(lock_t *mutex{
	mutex->flag = 0;
}

이 코드에는 두 가지 문제가 있다

1) 제대로 작동하는가 여부 Correctness

적시에 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 경우가 생길 수 있다 

2) 성능 

사용 중인 락을 대기하는 방법 (spin-wait) 에서 다른 쓰레드가 락을 해제할 때까지 시간을 낭비한다 

28.7 Test-And-Set 을 사용하여 작동하는 스핀 락 구현하기 

멀티프로세서에서 test-and-set 명령어 또는 원자적 교체 atomic exchange 명령어라는 하드웨어 기법을 도입하였다 

락의 값을 검사 Test 하고 새로운 값으로 설정 Set 하는 동작을 원자적 연산으로 만들어 오직 하나의 쓰레드만 락을 획득할 수 있도록 만들었다 🐣 코드는 책 참고!

스핀 락은 가장 기초적인 형태의 락으로서, 락을 획득할 때까지 CPU 사이클을 소모하면서 회전한다 

단일 프로세서에서는 이 방식을 사용하려면 선점형 스케줄러 Preemptive Scheduler 를 사용해야 한다

* 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있다 

28.8 스핀 락 평가 

락에서 중요한 측면	스핀 락의 효율
상호 배제의 정확성	스핀 락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다
공정성	스핀 락은 어떠한 공정성도 보장해 줄 수 없다
성능	단일 CPU 의 경우 성능 오버헤드가 상당히 클 수 있다 - N-1개의 다른 쓰레드가 있을 때, 스케줄러가 락을 획득하려고 시도하는 나머지 쓰레드들을 하나씩 깨울 수 있고, 쓰레드가 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기할 수 있다  CPU가 여러 개인 경우에는 (쓰레드의 개수가 CPU의 개수와 대충 같은 경우에) 꽤 합리적으로 동작한다

 

28.9 Compare-And-Swap

또 다른 하드웨어 기법 SPARC의 Compare-And-Swap, x86의 Compare-And-Exchange 가 있는다

대기 없는 동기화 Wait-free Synchronization 을 다룰 때 CompareAndSwap 루틴이 갖는 능력을 알게 될 것이다

28.10 Load-Linked  그리고 Store-Conditional

Load-Linked 와 Store-Conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다 

28.11 Fetch-And-Add

Fetch-And-Add 명령어는 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시킨다

int FetchAndAdd(int *ptr) {
	int old = *ptr;
    *ptr = old+1;
    return old;
}

이 해법에서는 티켓 Ticket 과 차례 Turn 조합을 사용하여 락을 만든다, 그리고 하나의 쓰레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행하고, 결과 값은 해당 쓰레드의 차례 myturn 을 나타낸다

이전까지의 접근 방법과의 중요한 차이는 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다 

+ flag 변수를 이용해서 락을 할당하고 반환받던 방식과 다르게, 락을 얻으려는 쓰레드들 은 번호표=ticket을 받는다 

그리고 unlock을 할 때 차례번호=turn가 1씩 증가하는데, 내 차례가 되면 락을 얻어서 임계 영역에 진입할 수 있다

이 방법의 장점은 모든 쓰레드들이 순서대로 락을 얻기에, 공정성이 보장된다.

28.12 요약 - 과도한 스핀 

하드웨어 기반의 락은 간단하고 제대로 동작하지만, 효율적이지 않은 경우도 있다

N개의 쓰레드가 하나의 락을 획득하기 위해 경쟁하게 되면 N-1개의 쓰레드에 할당된 CPU 시간 동안 리소스를 낭비하게 된다 

핵심 질문 - 회전을 피하는 방법
어떻게 하면 스핀에 CPU 시간을 낭비하지 않는 락을 만들 수 있을까?

28.13 간단한 접근법 - 조건 없는 양보

운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 yield() 기법에 있다고 가정한다

하나의 쓰레드는 실행 중 running, 준비 ready, 막힘 blocked 세 가지 상태가 있다 

양보 yield 시스템 콜은 호출 쓰레드를 실행 중 상태에서 준비 ready 상태로 변환하여 다른 쓰레드가 실행 중 상태로 전이하도록 한다 

결과적으로 양보 동작은 스케줄 대상에서 자신을 빼는 것 Deschedule 이나 마찬가지이다 

하지만 문맥 교환 비용이 상당하며 시간 간격을 많이 낭비하게 되고, 굶주림 문제는 전혀 해결하지 못하는 방식이다

28.14 큐의 사용 - 스핀 대신 잠자기

쓰레드가 락을 대기할 때, 명시적으로 다음 스레드를 선택하기 위해 운영체제의 지원과 큐를 활용해야 한다 

Solaris 의 방식은 park() 와 unpark(threadID) 함수를 사용하여 스레드를 잠재우고 깨우는 방식으로 락을 효율적으로 관리한다 

하지만 park() 가 호출되기 직전에 락을 해제한 경우와 같은 경쟁 조건이 발생할 수 있다, Solaris 는 이 문제를 setpark() 를 추가하여 쓰레드가 대기 상태에서 빠져나올 수 있게 했다 

+ 이전 방법들의 근본적인 문제는, 스케줄러가 다음 실행될 쓰레드를 잘못 선택하면 선택된 쓰레드는 락을 대기하면서 스핀하거나, CPU를 즉시 반납해야 하는 경우가 생길 수 있다는 것이다

다수의 쓰레드가 락을 대기하고 있을 경우, 다음으로 락을 획득할 쓰레드를 명시적으로 선택할 수 있어야 한다

++ lock 을 guard lock 으로 감싼다?

28.15 다른 운영체제, 다른 지원 

Linux 의 경우 futex 를 지원한다, futex 는 특정 물리 메모리 주소와 커널에 정의된 큐를 갖고 있다 

+ 하나의 정수를 사용해, 락의 사용 중 여부 (최상위 비트) 와 락 대기자 수 (나머지 비트) 를 표현한다

경쟁이 없는 경우에 빠르게 동작한다

★ 스핀락을 배제해야 하는 이유: 락이 사용 중일 경우에, 락을 얻지 못한 나머지 쓰레드들이 불필요하게 CPU 자원을 낭비한다.

• 해결방안: 락을 소유중인 쓰레드의 우선순위를 일시적으로 높여, 먼저 실행되게 해 작업을 마치고, 락을 빠르게 반환하게 하는 방식을 ‘우선순위 상속 Priority Heritage’ 라고 한다. 또다른 해결책으로, 모든 쓰레드의 우선순위를 같게 해줄 수도 있다.

28.16 2단계 락 

Linux의 락 시스템은 고전적 특성을 지니며, 현재는 2단계 락 two-phase lock 을 주로 사용한다 

이 방식은 락이 빠르게 해제될 것이라는 가정하에 첫번째 단계에서는 회전하며 대기하고,

(락이 곧 해제될 것 같으면, 회전 대기가 더 유용하다는 점에 착안했다고 하는데 이건 무슨 말인지 이해가 잘 안 감)

두번째 단계에서 호출자를 차단하고 락 해제 시 블럭된 쓰레드 중 하나를 잠에서 깨운다 

앞서 다른 Linux 락이 이러한 형태를 가지며, futex 가 일정 시간 동안 반복문 내에서 회전한 후 블럭한다

CH29 락 기반의 병행 자료 구조 

자료 구조에 락을 추가하면 해당 자료 구조를 경쟁 조건으로부터 안전한, 

쓰레드 사용에 안전 (쓰레드 안전, Thread Safe) 자료 구조로 만들 수 있다 

핵심 질문 - 자료 구조에 락을 추가하는 방법 
특정 자료 구조가 주어졋을 때, 어떤 방식으로 락을 추가해야 그 자료 구조가 정확하게 도작하게 만들 수 있을까?
다수의 쓰레드가 해당 자료 구조를 동시에 접근토록 해서 (병행성) 성능을 향상시키려면 어떤 일을 해야할까?

CH29.1 병행 카운터 

읽어야 할까,.....?