CSAPP 12.4 - 12.5

CSAPP

12.4 쓰레드 프로그램에서 공유변수

• 변수는 다수의 쓰레드가 이 변수의 일부 인스턴스를 참조할 때만 공유된다.

12.4.1 쓰레드 메모리 모델

• 동시성 쓰레드의 풀은 한 개 프로세스의 컨텍스트에서 돌아간다. 각각의 쓰레드는 자신만의 별도의 쓰레드 컨텍스트를 가진다. 각 쓰레드는 나머지 프로세스 컨텍스트를 다른 쓰레드와 공유한다. 여기에는 전체 사용자 가상 주소공간이 포함된다. 또한 동일한 오픈된 파일들을 공유한다.
• 동작적인 측면에서, 하나의 쓰레드가 다른 쓰레드의 레지스터를 읽거나 쓰는것은 불가능한 반면, 모든 쓰레드는 공유 가상메모리 내의 모든 위치에 접근할 수 있다. 만일 어떤 쓰레드가 한 메모리 위치를 수정하면, 그 위치를 읽는 다른 모든 쓰레드는 결국 이 변경사항을 알 수 있게된다. 그래서 레지스터들은 절대 공유되지 않지만, 가상메모리는 항상 공유된다.
• 별도의 쓰레드 스택을 위한 메모리 모델은 깔끔하지 않다. 이 스택들을 가상 주소공간의 스택 영역에 포함되어 있고, 대개 이들 각각의 쓰레드에 의해 독립적으로 접근된다. 항상이 아닌 대개라고 하는 이유는 서로 다른 쓰레드 스택이 다른 쓰레드로부터 보호되지않기 때문이다. 그래서 만일 어떤 쓰레드가 다른 쓰레드의 스택을 가리키는 포인터를 획득하게 된다면, 이 스택의 모든 부분을 읽고 쓸 수 있다.

12.4.2 변수들을 메모리로 매핑하기

• 쓰레드를 사용하는 C프로그램의 변수들은 이들의 저장클래스에 따라 가상메모리에 매핑된다.
• 전역변수
  • 전역변수는 함수 밖에서 선언된 모든 변수를 말한다. 런타임에 가상메모리의 읽기/쓰기 영역은 쓰레드에 의해 참조될 수 있는 각각의 전역변수의 정확히 한 개의 인스턴스를 포함한다.
• 지역 자동 변수
  • 지역 자동 변수는 함수 내에서 static특성 없이 선언된다. 런타임에 각 쓰레드의 스택은 자신만의 지역 자동 변수의 인스턴스를 가진다. 이것은 심지어 다수의 쓰레드가 동일한 쓰레드 루틴을 사용하는 경우에도 그렇다.
• 지역 정적 변수
  • 지역 정적 변수는 함수 안에서 static 특성으로 선언된 변수다. 전역변수 처럼 가상메모리의 읽기/쓰기 영역은 프로그램에서 선언된 각 지역 정적 변수의 정확히 한 개의 인스턴스를 포함한다.

12.4.3 공유변수

• 어떤 변수 v는 자신의 인스턴스중의 한 개가 하나 이상의 쓰레드에 의해 참조되는 경우에만 공유되어 있다고 말한다.

12.5 세마포어로 쓰레드 동기화하기

• 공유변수들은 편리하지만 심각한 동기화 오류를 가져올 수 있다.
• 일반적으로, 운영체제가 여러분의 쓰레드를 위해서 정확한 순서를 선택하게 될지 여부를 예측할 수 있는 방법은 없다. 이러한 부정확성을 갖는 인스트럭션 순서를 진행그래프라고 하는 도구를 이용해서 명확히 할 수 있다.

12.5.1 진행그래프(Progress Graph)

• 진행그래프는 n개의 동시성 쓰레드를 n차원 직교 좌표공강을 지나는 궤적으로 모델링한다. 각각의 축 k는 쓰레드 k의 진행에 대응된다. 각각의 점은 쓰레드 k가 인스트럭션 Ik를 완료한 상태를 나타낸다. 그래프의 원점은 초기 상태를 나타내며, 쓰레드 모두가 아직 한 개의 인스트럭션도 완료하지 못한 상태이다.
• 진행그래프는 인스트럭션의 실행을 하나의 상태에서 다른 상태로의 전환으로 모델링한다. 전환은 한 점에서 인접하는 한 점으로의 화살표로 표시한다. 합법적인 전환은 오른쪽으로 이동하거나 위로 이동하는 경우다. 두 인스트럭션은 동시에 완료할 수 없다. 프로그램이 뒤로 실행되는 경우는 없으며, 따라서 아래로 또는 왼쪽으로 이동하는 것은 규칙에 위배된다.
• 쓰레드 i에 대해서 공유변수의 내용을 조작하는 인스트럭션(Li, Ui, Si)는 크리티컬 섹션을 형성하며 다른 크리티컬 섹션과 중첩되면 안된다. 각각의 쓰레드가 자신의 크리티컬 섹션 내의 인스트럭션들을 실행하는 동안에는 상호 배타적으로 공유변수를 접근하도록 보장하기를 원한다. 이 현상을 상호배제(mutual exclusion)라고 한다.
• 진행그래프에서, 두 개의 크리티컬 섹션의 교차점은 위험영역이라는 상태공간의 구역을 정의한다. 위험영역은 둘레에 있는 상태들과 접해있지만 포함하지는 않는다는 점에 유의해라. 위험영역을 둘러싼 궤적은 안전궤적이라고 한다. 역으로, 위험영역의 어떤 부분이라도 닿은 궤적은 위험궤적이다.
• 모든 안전궤적은 공유 카운터를 정확히 갱신하게 된다. 쓰레드 프로그램을 정확히 실행하도록 보장하려면 쓰레드들을 어떤 방식으로든 동기화해서 이들이 항상 안전궤적을 가지도록 해야한다. 고전적인 방법은 세마포어 개념에 기초한다.

12.5.2 세마포어

• 세마포어 s는 비음수 정수값을 갖는 전역변수로 두 개의 특별한 연산인 P,V를 통해서만 조작할 수 있다.
• P(s) : s가 0이 아니면 P는 s를 감소시키고 즉시 리턴한다. 만일 s가 0이면 이 쓰레드는 s가 0이 아닌 값을 가지고, 쓰레드가 V연산에 의해 재시작될 때까지 정지된다. 재시작후에 P연산은 s를 감소시키고 제어를 호출자에게 돌려준다.
• V(s) : V연산은 s를 1증가 시킨다. 만일 s가 0이 아닌 값이 되는것을 기다리면서 P연산에서 멈춰있는 쓰레드가 있다면, V연산은 이중에서 정확히 한 개의 쓰레드를 시작하고, 그 후에 s를 감소시켜서 자신의 P연산을 완료한다.
• P에서 테스트와 감소연산은 일단 세마포어 s가 0이 아니면 s의 감소가 중단없이 일어난다는 의미에서 개별적으로 일어난다. V에서 증가연산 또한 개별적으로 일어나는데, 그것은 이 연산이 세마포어를 중단없이 로드하고, 증가하고, 저장하기 때문이다. V의 정의가 기다리고 있는 쓰레드들이 재시작되는 순서를 정의하지 않는다는 것에 주목하라. 유일한 요구사항은 V가 정확히 한 개의 대기하는 쓰레드를 재시작해야 한다는 것이다. 그래서 여러개의 쓰레드가 하나의 세마포어를 기다리고 있을 때, 어떤것이 V의 결과로 재시작되는지는 예측 할 수 없다.
• P와 V의 정의는 돌고 있는 프로그램이 적절히 초기화된 세마포어가 음수 값을 가지는 상태로 절대 들어갈 수 없도록 보장해준다. 이 특성을 세마포어 불변성이라고 하며, 동시성 프로그램의 궤적을 제어하기 위한 강력한 도구를 제공한다.

12.5.3 상호배제를 위한 세마포어 이용하기

• 공유변수들을 상호배타적으로 접근하기 위한 방법. 하나의 세마포어 s를 초기값 1로 시작해서 각각의 공유변수에 연계하고 그 후에 대응하는 크리티컬 섹션을 P(s)와 V(s) 연산으로 둘러싸는 것.
• 이런 방법으로 공유변수들을 보호하기 위해 이용된세마포어는 바이너리 세마포어라고 부르며, 그 이유는 이들의 값이 항상 0 또는 1이기 때문이다. 상호 배타성을 제공하는 목적의 바이너리 세마포어는 뮤텍스(mutex)라고도 한다. 뮤텍스는 P연산을 수행하는것을 뮤텍스를 잠근다(locking)라고 한다. 비슷하게 V연산을 수행가는 것을 뮤텍스를 연다(unlocking)라고 한다. 뮤텍스를 잠갔으나 아직 열지 못한 쓰레드는 뮤텍스를 소유하고 있다고 말한다.
• 가능한 자원들의 집합에 대한 카운터로 이용된 세마포어는 카운팅 세마포어라고 부른다.

12.5.4 세마포어를 이용한 공유 자원 스케줄링하기

• 세마포어의 또 다른 중요한 용도는 상호배제를 제공할 뿐만 아니라, 공유자원으로의 접근을 스케줄링하는 것이다. 이 시나리오에서, 쓰레드는 세마포어 연산을 이용해서 프로그램 상태의 어떤 조건이 참이 되었다는 것을 다른 쓰레드에 알려준다. 두 개의 고전적이고 유용한 사례는 생산자 - 소비자와 reader - writer 문제다.

생산자 - 소비자 문제

• 생산자와 소비자 쓰레드는 n개의 슬롯을 갖는 제한된 버퍼를 공유한다. 생산자 쓰레드는 반복적으로 새 아이템을 만들고 이들을 버퍼에 삽입한다. 소비자 쓰레드는 반복적으로 아이템을 버퍼에서 제거하고 그 후에 이들을 소모한다(이용한다).
• 아이템들을 추가하고 제거하는 것이 공유변수들의 갱신과 관련되어 있으므로 버퍼에 접근할 때 상호배타성을 보장해야 한다. 그러나 상호배타성을 보장하는 것으로는 충분하지 않다. 버퍼로의 접근을 스케줄링 할 필요도 있다. 만일 버퍼가 차 있으면(빈 슬롯이 없으면), 생산자는 슬롯이 가능해질 때 까지 기다려야 한다. 비슷하게 버퍼가 비어있으면(가용한 아이템이 없다면) 소비자는 아이템이 가용할 때까지 기다려야 한다.

읽기 - 쓰기 문제

• 읽기 - 쓰기 문제는 상호 배제 문제의 일반화된 형태다. 동시성 스레드들의 집합은 메인메모리의 자료구조나 디스크 상의 데이터베이스 같은 공유객체에 접근하고 있다. 일부 쓰레드들은 객체를 읽기만 하고, 다른 쓰레드들은 이것을 수정만 한다. 객체를 읽기만 하는 쓰레드를 reader, 수정만 하는 쓰레드를 writer라고 한다. writer는 객체로 배타적인 접근을 해야 하지만, reader는 이 객체를 무수히 많은 다른 reader들과 공유할 수도 있다.
• reader - writer 문제는 몇 가지 변화가 있을 수 있는데, 이들 각각은 reader와 writer의 우선순위에 근거를 두고 있다. reader를 선호하는 reader - writer 문제는 어떠한 reader도 writer가 이미 이 객체를 이용하도록 허가하지 않았으면 계속 기다려서는 안된다. 두 번째는 writer를 선호하는, writer가 쓸 준비가 되었다면 가능한 한 빨리 자신의 쓰기 작업을 수행하는 것을 요구한다.
• 두 개의 reader - writer 문제에 대한 정확한 해결책은 기아문제로 이어질 수 있으며, 이 경우 쓰레드는 영원히 정지하고 진행하지 못한다.