[OSTEP] 병행성 CH31 - CH32

CH31 세마포어 Semaphore

다양한 범주의 병행성 문제 해결을 위해서는 락과 조건 변수가 모두 필요하다 (이 사실을 Dijkstra 가 발견함)

Dijkstra 와 동료들이 모든 다양한 동기화 관련 문제를 한번에 해결할 수 있는 기법을 개발해 보면서 세마포어가 탄생했다 

세마포어는 락과 컨디션 변수로 모두 사용할 수 있다 

🐣 세마포어는 자원의 사용 가능 여부를 숫자로 관리하여 여러 쓰레드가 안전하게 공유 자원에 접근할 수 있도록 제어하는 역할을 한다 

🐣 세마포어는 일종의 추상 자료형이고, 자원의 개수를 나타낼 수 있다, 공유 자원을 획득하고 반납하는 방식을 나타낼 수 있음 

핵심 질문 - 세마포어를 어떻게 사용하는가
락과 컨디션 변수 대신에 세마포어를 사용하는 방법은 무엇인가? 세마포어의 정의는 무엇인가? 이진 (Binary) 세마포어는 무엇인가? 락과 컨디션 변수를 사용하여 세마포어를 만드는 것이 가능한가? 그 반대로 세마포어를 사용하여 락과 조건 변수를 만드는 것이 가능한가?

31.1 세마포어 - 정의

세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다 - POSIX 표준의 sem_wait() 와 sem_post() 

세마포어는 초기값에 의해 동작이 결정되기 때문에, 사용하기 전에 "제일 먼저" 값을 초기화해야 한다

#include <semaphore.h>
sem_t s; 		// 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다 
sem_init (&s, 0, 1); // 세마포어의 값을 1로 초기화

초기화된 후에는 sem_wait() or wem_post() 함수를 호출하여 세마포어를 다룰 수 있고,

이 루틴들은 동시에 다수 쓰레드들에 의해 호출될 수 있기 때문에 임계 영역이 적절히 보호 되어야 한다 (임계 영역 보호 문제는 추후 다룸)

 

세마포어 함수 내에서의 임계 영역이 제대로 보호되고 있다고 가정하고, 두 함수의 핵심적인 성질은 아래와 같다

1) 세마포어의 값이 1 이상이면 sem_wait() 함수는 즉시 리턴하거나, 아니면 해당 세마포어 값이 1 이상이 될 때까지 호출자를 대기시킨다

🐣 세마포어의 값이 1이면 자원을 사용할 수 있다 - sem_wait 가 호출되면, 세마포어 값을 1 감소시키고 sem-- 즉시 리턴하여 다음 작업을 진행한다 (대기할 필요가 없다)

🐣 값이 0이면 자원을 사용할 수 없다 - 세마포어 값이 1 이상이 될 때까지 대기한다, 자원이 해제되면 세마포어 값이 1 이상이 되어 대기 중인 호출자 차례가 된다 

다수의 쓰레드들이 sem_wait() 를 호출할 수 있기 때문에 대기 큐에는 다수의 쓰레드가 존재할 수 있고

대기하는 법에는 회전 spin 과 재우기 sleep 의 두 가지가 있다

2) sem_post() 는 대기하지 않는다 🐣 그냥 깨우는 거임 

세마포어 값을 증가시키고 대기 중인 쓰레드 중 하나를 꺠운다 

3) 세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다 

그리고 이 두 개의 함수는 원자적으로 실행된다고 가정한다 

31.2 이진 세마포어 (락)

세마포어는 락으로 쓸 수 있고, 락은 두 개의 상태 (사용 가능, 사용 중) 만 존재하므로 이진 세마포어 Binary Semaphore 라고도 불린다 

31.3 순서 보장을 위한 세마포어

세마포어는 병행 프로그램에서 일어나는 사건들의 순서를 정하는데도 유용하다 (like 컨디션 변수)

1. 부모 프로세스는 자식 프로세스를 생성하고 sem_wait() 를 호출하여 자식의 종료를 대기한다 

2. 자식은 sem_post() 를 호출하여 종료되었음을 알린다 

 

이런 경우에 세마포어의 초기값은 0으로 설정한다, 이유는 아래 두 가지이다 

1) 자식 프로세스를 생성하고 아직 자식 프로세스가 실행을 시작하지 않은 경우 (준비 큐에만 있고 실행 중이 아닌 상태)

부모 프로세스가 자식이 실행될 때까지 대기해야 하기 때문에 wait() 호출 전에 세마포어 값이 0보다 작거나 같아야 한다 

자식이 실행되었을 때 sem_post()을 호출하여 세마포어의 값을 0으로 증가시키고 부모를 깨우면 << ????QnA 질문 올림 

부모는 sem_wait() 에서 리턴하여 프로그램을 종료시킨다 

2) 부모 프로세스가 sem_wait() 를 호출하기 전에 자식 프로세스의 실행이 종료된 경우이다 

이 경우, 자식이 먼저 sem_post() 를 호출하여 세마포어의 값을 0으로 1로 증가시키고, 부모가 실행할 수 있는 상황이 오면 sem_wait() 를 호출한다, 부모가 세마포어 값을 0으로 감소시키면서 sem_wait() 에서 대기 없이 리턴한다

31.4 생산자/ 소비자 (유한 버퍼) 문제 

교착 상태를 피하기 위해서는, mutex 를 획득하고 해제하는 코드를 임계 영역 바로 이전과 이후로 이동하고

full 이나 empty (세마포어 변수) 와 관련된 코드는 mutex 밖으로 배치하면 좋다

이것이 멀티 쓰레드 프로그램에서 사용 가능한 유한 버퍼이다

생산자 - 비어있어? 채워줄게! sem_wait(&empty) 

소비자 - 꽉 차있어? 비워줄게! sem_wait(&full) 

31.5 Reader-Writer 락

다수의 쓰레드가 연결 리스트에 노드를 삽입하고 검색을 하는 상황일 때 (삽입 연산은 리스트를 변경하고, 검색은 단순히 읽기만 할 때) 삽입 연산이 없다는 보장만 된다면 다수의 검색 작업을 동시에 수행할 수 있다 

이와 같은 경우를 위해 만들어진 락이 reader-writer 락이다 

 

자료 구조를 "갱신"하려면 배타적 접근 권한을 갖는 락을 사용하여 하나의 쓰기 쓰레드만이 락을 획득할 수 있도록 한다 

읽기 락 Reader Lock 은 동시에 여러 쓰레드가 락을 보유할 수 있고, 읽기 락을 획득 시 읽기 중인 쓰레드의 수를 표현하는 readers 변수를 증가시킨다 

이 방식의 단점은 쓰기 쓰레드에게 기아 현상 Starvation 이 발생하기 쉽다는 점과

기법이 정교할수록 오버헤드가 크다는 사실이다 

31.6 식사하는 철학자 

다섯 명의 철학자가 원형 식탁에 둘러 앉고 다섯 개의 포크가 철학자들 사이에 하나씩 놓여 있다

자신의 왼쪽과 오른쪽에 있는 포크를 들어야 식사를 할 수 있다, 이 포크를 잡기 위한 경쟁과 그에 다른 동기화 문제를 다룬다 

31.7 쓰레드 제어 

"과도하게 많은" 쓰레드가 동시에 수행되면 시스템의 효율이 매우 나빠진다 

이 문제를 방지하기 위해서는 "과도하게 많은"에 대한 임계값을 정하고, 세마포어를 사용하여 문제가 되는 코드를 동시에 실행하는 쓰레드 개수를 제한한다, 이 접근법을 제어 Throttling 라고 부르며 수락 제어의 한 형태로 간주한다 

세마포어의 값을 메모리-집약 영역에 동시에 들어갈 수 있는 최대 쓰레드 수로 초기화하고, 코드 앞뒤에 sem_wait() 와 sem_post() 를 각각 추가하면 이 세마포어가 위험한 영역에서 병행하게 실행할 수 있는 쓰레드의 개수를 통제한다 

31.8 세마포어 구현

저수준 동기화 기법인 락과 컨디션 변수를 사용하여 우리만의 세마포어, 제마포어 Zemaphore 를 만들어 보자 

세마포어와의 차이 중 하나는 세마포어의 음수 값이 대기 중인 쓰레드의 수를 나타낸다는 부분인데, 제마포어는 0보다 작을 수 없기 때문이다, 이 방식은 현재 Linux 에 구현된 방식이기도 하다 

31.9 요약

세마포어는 병행 프로그램 작성을 위한 강력하고 유연한 기법이고,

진정한 병행성 전문가가 되는 것은 수년간의 노력이 필요한 일이다 

🐣 세마포어와 뮤텍스는 공유 자원에 대한 접근 방식을 제어하는 매커니즘으로, 아래와 같은 차이점을 가지고 있다

	뮤텍스 Mutex	세마포어 Semaphore
매커니즘	잠금 Locking 매커니즘	신호 Signaling 매커니즘
소유권	잠금을 획득한 스레드만이 잠금 해제 가능	다른 스레드도 신호를 보내 잠금 해제 가능
카운트	이진값 0 or 1 만 가짐	0 이상의 정수값을 가질 수 있음
용도	주로 상호 배제를 위해 사용	상호 배제 및 조건 동기화에 사용 가능
연산	Lock/ Unlock 연산 사용	wait(P), signal(V) 연산 사용
초기화	항상 1로 초기화	임의의 음이 아닌 정수로 초기화 가능

 

CH32 병행성 관련 버그 

핵심 질문 - 일반적인 병행성 관련 오류들은 어떻게 처리하는가? 
병행성 버그는 몇 개의 전형적인 패턴을 가지고 있다, 튼튼하고 올바른 병행 코드를 작성하기 위한 가장 첫 단계는 어떤 경우들을 피해야 할지 파악하는 것이다 

32.1 오류의 종류

Lu와 그의 동료들이 복잡한 병행 프로그램에서 발생한 오류에 대한 통계를 정리했다

총 105개 중 74개는 교착 상태와 무관했고, 31개의 오류들이 교착 상태 관련 오류였다 

32.2 비 교착 상태 오류

비 교착 상태 오류 중 대표적인 오류는 원자성 위반 Atomicity Violation 과 순서 위반 Order Viloation 이 있다 

원자성 위반 오류

Lu가 기술한 원자성 위반은, "다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성 Serializability 이 보장되지 않았다" 로 정의된다  

즉, 코드의 일부에 원자성이 요구되었으나, 실행 시에 그 원자성이 위반하였다 

🐣 코드 블록은 중단 없이 연속적으로 실행되어야 하지만, 중간에 다른 쓰레드가 개입하여 비결정적 결과가 출력되는 상황으로 이해했다 

이런 문제의 해결은, 공유 변수 참조 앞뒤에 락을 추가하여, 해당 자료 구조를 사용하는 다른 모든 코드들이 락을 먼저 획득하도록 한다

순서 위반 오류

순서 위반의 공식 정의는 "두 개의 (그룹의) 메모리 참조 간의 순서가 바뀌었다 (즉,  A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다" 이다 

해결 방법은, 컨디션 변수 또는 세마포어로 순서를 강제하여 해결할 수 있다 

32.3 교착 상태 오류

복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서는 교착 상태 Deadlock 이라는 고전적인 문제가 발생한다 

🐣 두 개 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리며 무한 대기 상태에 빠지는 현상 

핵심 질문 - 교착 상태를 어떻게 다룰 것인가
시스템을 어떻게 개발해야 교착 상태를 예방하여 회피하거나 최소한 감지하고 회복할 수 있을까?
현대의 시스템에도 있는 실제의 문제인가?

 

교착 상태가 발생하는 이유는 아래와 같다 

1) 코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생한다 

대형 시스템의 락 사용 전략의 설계는 매우 신중해야 한다 

2) 캡슐화 Encapsulation 의 성질 때문이다 

모듈화와 락은 잘 조화되지 않아서, 전혀 문제 없어 보이는 인터페이스도 교착 상태를 발생시킨다 

교착 상태 발생 조건

교착 상태가 발생하기 위해서는 네 가지 조건이 충족되어야 한다 

1) 상호 배제 Mutual Exclustion - 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다 

2) 점유 및 대기 Hold-and-wait - 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기한다 

3) 비선점 No Preemption - 자원(락)을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없다 

4) 환형 대기 Circular Wait - 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원(락)을 갖고 있는 쓰레드들의 순환 고리가 있다 

교착 상태의 예방

순환 대기 Circular Wait 

가장 실용적인 교착 상태 예방 기법은 락 획득을 하는 전체 순서 Total Ordering 을 정하는 것이다 

두 개 이상의 락이 존재하는 상황에서는 부분 순서 Partial Ordering 만을 정의할 수도 있다 

순서를 이용하여 락을 제어할 때 섬세한 주의가 필요하며, 다양한 루틴 간의 상호 호출 관계를 이해하여 순서를 결정해야 한다 

점유 및 대기 Hold-and-Wait

원자적으로 모든 락을 단번에 획득하도록 하면 점유 및 대기를 예방할 수 있다 

prevention 락을 먼저 획득하면, 락을 획득하는 과정 중에 쓰레드의 문맥 교환이 발생하는 것을 방지할 수 있다 

이 방식에서는 각 쓰레드가 필요한 락들을 요청하기 전에 prevention 락을 먼저 획득해야 하므로, 다른 쓰레드가 L1과 L2 같은 락들을 다른 순서로 요청하더라도 해당 쓰레드가 prevention 락을 이미 획득한 후이므로 안전하다 

하지만 1) 필요한 락들을 정확히 파악해야 하고 (캡슐화) 2) 그 락들을 미리 획득해야 하기 때문에 병행성이 저하되는 문제가 있다 

🐣 캡슐화 - 필요한 자원의 명확한 식별과 관리 강조, 병행성 저하 - 락 획득 방식에서 발생하는 성능 저하 문제 

비선점 No Preemption 

락을 한번 획득하게 되면 이를 명시적으로 반납하기 전까지는 락을 보유하고 있는 것이 되기 때문에

여러 개의 락을 보유한 상태에서 추가로 락을 요청할 경우 문제 발생의 소지가 있다 

pthread_mutex_trylock() 루틴은 락이 획득 가능하면 락을 획득하고 성공을 나타내는 코드를 반환하거나, 락이 점유되었다는 것을 나타내는 에러 코드를 반환한다, 이러한 인터페이스를 이용하여 교착 상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있다 

이 방식에서는 무한반복 Livelock 이라는 문제가 발생할 수 있지만, 락 획득을 위한 코드를 반복하기 전에 임의의 시간 동안 지연하는 방법으로 경쟁하는 쓰레드 간의 반복 간섭 확률을 줄일 수 있다, 그리고 trylock 방식의 어려운 부분은 캡슐화하여 관리하는 것이다 

상호 배제 Mutual Exclustion  

강력한 하드웨어 명령어를 사용하면, 상호 배제 자체를 없애고 락이 없는 Lock-free (or 대기 없는 Wait-free) 자료 구조를 만들 수 있다 

락을 획득하여 값을 갱신한 후에 락을 해제하는 대신, Compare-And-Swap 명령어로 값에 새로운 값을 갱신하는 방식을 사용하면

락을 획득할 필요가 없으며 교착 상태가 발생할 가능성도 없다 (다만, 무한 반복은 발생 가능성이 있다) 

스케줄링으로 교착 상태 회피하기 

어떤 시나리오에서는 교착 상태를 예방하는 대신 회피하는 것이 더 유용할 때가 있다, 회피를 위해서는 실행 중인 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적인 파악이 필요하며, 이를 기반으로 쓰레드들을 스케줄링하여 교착 상태가 발생하지 않도록 해야 한다 

다만, 병행성에 제약을 가져올 수도 있기 때문에, 스케줄링으로 교착 상태를 회피하는 것은 보편적인 방법은 아니다 

발견과 복구 

교착 상태 발생을 허용하고, 교착 상태를 발견하면 복구하는 방법 또한 많은 데이터베이스 시스템들이 사용한다 

🐣 이러한 접근은 시스템의 자원 효율성을 높이고, 교착 상태 방지를 위한 과도한 자원 낭비를 피할 수 있다 

32.4 요약

교착 상태를 다루는 가장 좋은 해법은 조심하는 것과 락 획득 순서를 정해서 애초에 교착 상태가 발생하지 않도록 예방하는 것이다 

최선의 해법은 아마도 새로운 병행 프로그래밍 방법론을 만드는 것이라고 보인다 

락은 원천적으로 문제점을 수반하기 때문에 반드시 필요한 경우가 아니면 사용을 피하도록 노력해야 한다