[OSTEP] 병행성 CH29 - CH30

CH29 락 기반의 병행 자료 구조 

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

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

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

 

+ 병행성 - 뮤텍스 락, 세마포어, 컨디션 변수 

락 - 공유하는 자원에 락을 걸어서 하나만 접근 

세마포어 - 자원에 접근하는 쓰레드 개수를 제한을 둔다, 1개 이상 접근 가능

컨디션 변수 - 재운다, 깨운다 

+ 교착 상태 - 서로가 서로의 자원을 기다리며 대기하는 상태 

29.1 병행 카운터 

카운터는 가장 간단한 자료 구조 중 하나이다, 보편적으로 사용되는 구조이면서 인터페이스가 간단하다

병행이 가능한 카운터는, 모니터 minotor 를 사용하여 만든 자료 구조와 유사하다

모니터 기법은 객체에 대한 메소드를 호출하고 리턴할 때 자동적으로 락을 획득하고 해제한다 

이 간단한 방법은 쓰레드 개수가 늘어날수록 성능이 나빠진다 🐣 1) 쓰레드가 많아질수록 여러 쓰레드가 동시에 value 에 접근하려고 하고, 하나의 쓰레드만 lock 을 획득할 수 있기 때문에 대기 시간이 증가한다 2) 잠금 대기 중인 쓰레드가 많아질수록 여러 쓰레드를 계속해서 전환해야 하기 때문에 이 과정에서 문맥 교환이 자주 발생한다 3) 쓰레드가 많을수록 각 쓰레드가 lock 을 획득하고 사용하는 시간이 늘어나므로 락 홀딩 타임이 증가하고 오버헤드가 커진다 4) 뮤텍스 잠금으로 인해 value 에 접근하는 코드가 직렬화되므로 병렬성의 효과를 극대화하기 어렵다 + value 는 여러 쓰레드가 동시에 접근할 수 있는 공유 자원

완벽한 확장성 Perfect Scaling 이 담보되는 환경에서는 작업양이 CPU 의 개수에 비례하여 증가하더라도, 각 작업이 병렬적으로 처리되어 전체 완료 시간이 늘어나지 않는다 🐣 한계치 S 부분 다시 읽어보기 

 

근사 카운터 Approximate Counter 는 하나의 논리적 카운터로 표현되고, CPU 코어마다 존재하는 하나의 물리적인 지역 카운터와 하나의 전역 카운터로 구성되어 있다, 이 카운터들 외에도 지역 카운터들을 위한 락들과 전역 카운터를 위한 락이 존재한다 (설명 중략)

근사 카운터는 확장성이 있고, 정확도와 성능의 개선을 조절할 수 있다 

29.2 병행 연결 리스트

연결 리스트에서 병행 삽입 연산을 살펴보면, 삽입 연산을 시작하기 전에 락을 획득하고 리턴 직전에 해제한다 

malloc() 이 실패할 경우 미묘한 문제가 생길 경우가 발생할 수 있는데, 실패를 처리하기 전에 락을 해제하면 된다 

하지만 약 40%에 달하는 버그가 이런 자주 사용되지 않는 코드에서 발생한다는 결과에서 영감을 얻어 

삽입 연산이 병행하여 진행되는 상황에서 실패를 하더라도 락 해제를 호출하지 않으면서 삽입과 검색을 동작하게 하려면,

1) 삽입 코드에서 임계 영역을 처리하는 부분만 락으로 감싸도록 코드 순서를 변경한다

2) 검색 코드의 종료는 검색과 삽입 모두 동일한 코드 패스를 사용한다 << 삽입이 아니라 실패 오타 같은데 

 

병행성을 개선하기 위한 방법 중 하나인 Hand-over-hand locking (or Lock coupling) 기법은

전체 리스트에 하나의 락이 있는 것이 아니라 개별 노드마다 락을 추가하는 것이다 

리스트를 순회할 때 다음 노드의 락을 먼저 획득하고, 지금 노드의 락을 해제한다 

개념적으로는 괜찮아보이지만 간단한 락 방법 (락을 하나 두는) 에 비해 속도 개선이 좋지 않다/ 오버헤드가 크다 

-> 락을 노드마다 주는 것이 아니라, 일정 개수의 노드들마다 하나의 락을 주는 하이브리드 방식이 더 낫다

29.3 병행 큐

Michael 과 Scott 이 만든 조금 더 병행성이 좋은 큐는, 락을 큐의 헤드와 테일에서 하나씩 사용한다

이 두 개 락의 목적은 큐의 삽입과 추출 연산에 병행성을 부여하는 것이다 

그리고 큐 초기화 코드에 더미 dummy 노드를 추가하여 헤드와 테일 연산을 구분하는 데 사용한다 

하지만 이 큐는 큐가 비었거나 가득찬 경우, 쓰레드가 대기하도록 하는 기능이 필요하다

29.4 병행 해시 테이블

병행 해시 테이블은 리스트로 구현된 해시 버켓 Hash Bucket 마다 락을 사용하여 병행성이 좋다 

병행 해시 테이블은 병행성이 매우 좋지만, 연결 리스트는 확장성이 매우 떨어진다 

29.5 요약

락 획득과 해제 시 코드의 흐름에 매우 주의를 기울여야 한다

병행성 개선이 반드시 성능 개선은 아니다 

성능 개선은 성능에 문제가 생길 경우에만 해결책을 간구해야 한다 

미숙한 최적화 Premature Optimization 을 피해야 한다 - 부분적인 성능 개선 시도가 응용 프로그램의 전체 성능을 개선하지 못하면 아무 의미 없다 

 

CH30 컨디션 변수

쓰레드가 실행을 계속하기 전에, 특정 조건의 만족 여부를 검사해야 하는 경우가 많이 있다 ex. join() 

🐣 병행성 프로그램을 구현하는 방법 1) 폴링 Polling 방식 2) 이벤트 기반 Event-driven 

동기화 Synchronization - 동기화란 여러 작업들이 공유 자원에 접근할 때, 그 순서나 접근 방식을 조정해서 데이터 충돌없이 모든 작업들이 안전하게 완료되도록 조율하는 것을 뜻한다

핵심 질문 - 조건의 대기
멀티 쓰레드 프로그램에서는 쓰레드가 계속 진행하기에 앞서 특정 조건이 참이 되기를 기다리는 것이 유용할 때가 많이 있다
조건이 참이 될 때까지 회전을 하며 기다리는 것이 간단하기는 하겠지만 지독하게 비효율적이고 CPU 사이클을 낭비하며
어떤 경우에는 부정확할 수도 있다, 그렇다면 쓰레드는 어떻게 조건을 기다려야 할까?

30.1 컨디션 변수의 개념과 관련 루틴

쓰레드 실행 시, 특정 조건이 만족될 때까지의 대기를 위해 컨디션 변수 Conditional Variable 를 사용할 수 있다 

컨디션 변수는 일종의 큐 자료 구조이며, 쓰레드 실행에서 어떤 상태 (or 어떤 조건) 가 원하는 것과 다를 때 조건이 만족되기를 대기하는 큐이다, 다른 쓰레드가 실행되어 시스템의 상태를 변경시키고, 해당 조건이 만족되었을 때, 대기 중인 쓰레드를 깨워 실행을 계속하도록 한다 

 

pthread_cond_wait() 와 pthread_cond_signal() 이 있을 때, wait() 는 쓰레드가 스스로를 잠재우기 위해 호출하고, signal() 은 조건이 만족되기를 대기하며 잠자고 있던 쓰레드를 깨울 때 호출한다 

대기 중인 쓰레드가 슬립 sleep 상태에서 깨어나면 wait() 에서 리턴하기 전에 반드시 락을 재획득해야 한다, 락 획득에 실패하면 다시 sleep 모드로 들어간다 

 

"슬립에서 깨어난 프로세스는 리턴하기 전에 락을 재획득해야 한다"

모든 경우에 락을 획득할 필요는 없지만, 컨디션 변수를 사용할 때는 락을 획득한 후에 시그널을 보내는 것이 가장 간단하고 최선의 방법이다, 시그널을 보낼 때는 락을 무조건 획득하자 

wait()는 항상 a) wait() 를 호출했을 때 락을 갖고 있다고 가정하며, b)호출자를 잠들게 할 때 락을 해제하고 c) 리턴하기 직전에 락을 다시 획득한다, 시그널을 보낼 때, 대기할 때 항상 락을 걸자 

🐣 왜 락을 걸어야할까? -> 동기화 문제 때문! wait() 와 signal() 은 주로 공유 자원이나 공통 조건을 기반으로 동작하기 때문에, 여러 쓰레드가 동시에 접근할 경우, 데이터의 일관성이 깨질 수 있다 (경쟁 조건 Race Condition 이 발생할 수 있다) 락을 이용해 signal() 과 wait() 를 보호하면 각 쓰레드가 필요한 순서대로 안전하게 접근할 수 있고, 락을 걸면 자원이 보호된 상태에서 진행하게 되어 유지보수에도 유리하다 

+ done 상태 변수가 없다면? - 자식 쓰레드가 먼저 실행될 경우에, 후에 대기 상태로 들어가는 부모 쓰레드를 깨워줄 쓰레드가 없다.

lock이 없다면? - 경쟁 조건이 발생하여, 부모 쓰레드가 또 무기한 수면에 들어갈 수 있다 

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

생산자/ 소비자 (Producer/ Consumer), 유한 버퍼 (Bounded Buffer) 문제는 다수의 생산자 쓰레드와 소비자 쓰레드 사이에서 동시에 생산과 소비가 이루어질 때 발생할 수 있는 문제를 다룬다 

초기 방식 

put() 함수로 생산자가 버퍼에 내용을 기록하고 get() 함수로 소비자가 버퍼에 있는 내용을 읽는다

임계 영역을 락으로 보호하는 것만으로는 제대로 동작하지 않고 (mutex 락) 추가적으로 컨디션 변수가 필요하다 

시그널을 받는 시점과 쓰레드가 실제로 실행되는 시점 사이에 시차가 존재하는데, 이 기간 동안 버퍼 상태가 변경되면 문제가 발생할 수 있다 

 

"깨운다" 라는 행위의 본질은 쓰레드의 상태를 대기 상태 Blocked 에서 준비 상태 Ready 로 변경하는 것이다

Mesa Sematic 방식은 깨어난 쓰레드가 실행되는 Running 시점에서는 버퍼의 상태가 다시 변경될 수도 있기 때문에, 깨어난 쓰레드가 실제 실행되는 시점에서는 시그널을 받았던 시점의 상태가 그대로 유지되어있는지를 다시 한 번 확인하는 방식이다 

Hoare Semantic 의 시그널에서는 시그널을 받아서 깨어난 쓰레드가 실행될 때, 시그널 발생 시점의 조건이 유지된다는 것을 보장한다

Hoard Semantic 은 구현이 어렵기 때문에, 대부분의 시스템이 Mesa Semantic 을 채용하고 있다 

개선 방식 

1) Mesa Semantic 의 컨디션 변수에서 가장 기본적인 법칙은 언제나 while 문을 사용하라는 것이다 

2) 두 개의 컨디션 변수를 사용하면 문제를 해결할 수 있다, 시스템의 상태가 변경되었을 때 깨워야 하는 쓰레드에게만 시그널을 제대로 전달한다 

생산자 쓰레드가 empty 조건 변수에서 대기하고 fill 에 대해서 시그널을 발생하고, 소비자 쓰레드는 fill 에 대해서 대기하고 empty 에 대해서 시그널을 발생시켜, 소비자는 다른 소비자를 깨울 수 없고, 생산자도 다른 생산자를 깨우지 않도록 만들 수 있다

3) 버퍼를 확장하여 병행성을 증가시킨다, 대기 상태에 들어가기 전에 여러 값들이 생산될 수 있도록 (그리고 마찬가지로 여러 개의 값이 대기 상태 전에 소비될 수 있도록) 한다, 버퍼 크기가 증가하면 쓰레드 간의 문맥 교환이 줄어들고 (성능이 좋아진다), 멀티 생산자 or 멀티 소비자의 경우 생산과 소비가 병행이 될 수 있기 때문에 병행성이 좋아진다 

30.3 포함 조건 Covering Condition 

메모리 공간이 생길 때까지 대기하는 메모리 할당을 요청한 쓰레드가 있을 때, 응용 프로그램이 메모리를 해제하고 반납하면, 가용 메모리 공간의 발생을 알리는 시그널을 생성한다, 다수의 쓰레드가 메모리 공간의 발생을 대기하고 있을 때, 어떤 쓰레드를 깨워야 할까?

시그널을 생성하는 쓰레드는 시그널 수신 대상자를 명시할 수 없기 때문에, 어떤 쓰레드를 깨울지, 해당 시그널을 어떤 쓰레드에게 전달할지는 전적으로 운영체제의 몫이다 

컨디션 변수에서의 시그널 함수는 시그널 수신자를 명시하지 않기 때문에, Lampson과 Redell은 컨디션 변수에서 대기 중인 모든 쓰레드에게 시그널을 다 전송하는 방법을 제안했다, 이 방식은 다수의 쓰레드를 불필요하게 깨울 수 있다/ 불필요한 문맥전환이 많이 발생할 수 있다는 단점이 있다, 이런 경우를, 쓰레드가 깨어나야 하는 모든 경우를 다 포함하기 때문에 포함 조건 Covering Condition 이라고 한다

일반적으로 시그널을 브로드캐스트 Broadcast 로 바꿨을 때만 동작하는 프로그램은 버그가 존재하는 것일테지만, 메모리 할당 문제에서는 가장 자명한 해법이다 

30.4 요약

컨디션 변수는 프로그램 상태를 특정 조건이 만족될 때까지 대기하도록 하여 동기화를 매우 쉽게 해결한다