[OSTEP] II. 병행성

[26장. 병행성: 개요]

 

쓰레드들은 주소 공간을 공유하기 때문에 동일한 값에 접근할 수 있다.

두 개의 쓰레드가 하나의 프로세서에서 실행 중이라면 실행하고자 하는 쓰레드는 반드시 문맥 교환을 통해 실행중이 쓰레드와 교체되어야 한다.

프로세스가 교환될 때 사용된 PCB처럼 쓰레드도 TCB를 사용한다.

 

[28장. 락]

 

락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다.

쓰레드는 프로그래머가 생성하고 OS가 제어한다. 락은 쓰레드에 대한 제어권을 일부 이양 받을 수 있도록 해준다.

 

락 설계시 평가기준

• 상호 배제를 제대로 지원하는가? (임계영역 진입 여부)
• 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가? (기아현상 발생 여부)
• 하나의 쓰레드가 실행 중에 락을 획득하고 해제하는 과정에서 발생하는 부하는 얼마나 되는가? (성능)

 

하드웨어 기법

• Test and Set: 락의 값을 검사하고 새로운 값으로 설정하는 것을 나누어서 실행하면 상호 배제가 지켜지지 않을 수 있다. 원자적(동시) 연산으로 만든것을 스핀 락이라고 한다. 선점형 스케줄러에서만 사용할 수 있다.
• Compare and Swap: 위와 비슷한 방식이지만 더 강력하다.
• Load Linked & Store Conditional
• 그 외.. 일단 패스함

 

락에서 가장 중요한 측면

• 상호 배제의 정확성
• 공정성: 단순한 스핀 락은 공정하지 않다.
• 성능

 

락을 기다리며 스핀만 무한히 하는경우 할당된 CPU 시간을 다른 쓰레드에게 넘겨주어서 시간 낭비를 하지 않을 수 있지만 문맥 교환에 소모되는 비용과 해결하지 못한 기아 현상이 남게된다.

 

그 외 내용이 많은데 정리하기가 애매해서 일단 넘어감

 

[29장. 락 기반의 병행 자료 구조]

 

자료 구조에 락을 추가하면 경쟁 조건에서 안전한 자료 구조로 만들 수 있다.

 

병행 카운터

확장성 없는 카운팅: 간단하고 정확하게 동작하지만 확장성이 전혀 없다.

확장성 있는 카운팅: 근사 카운터를 이용한다.

 

이번장도 넘어감

 

[30장. 컨디션 변수]

 

쓰레드 실행 시, 특정 조건이 만족될 때 까지의 대기를 위한 컨디션 변수라는 개념을 사용할 수 있다. 일종의 큐 자료구조이다. 조건이 만족되기를 대기하는 큐이다. 조건이 만족되었을 때 대기중인 쓰레드를 깨워 실행을 계속 하도록 한다.

 

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

시그널을 보낼 때, 대기할 때는 항상 락을 획득하는 것이 좋다.

 

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

공유 변수에서 경쟁 조건(race condition)이 발생한다. 시그널을 받아서 깨어난 스레드가 실제 실행되는 시점에는 시그널을 받은 시점의 상태가 그대로 유지되어있는지를 다시 체크해야 한다.(Mesa semantic)

단일 버퍼 생산자-소비자의 경우에는 컨디션 변수를 2개 사용하면 된다.

 

포함 조건

다수의 쓰레드가 메모리 할당을 요청하고 대기중인 경우 컨디션 변수에서 대기중인 모든 쓰레드에게 시그널을 전송한다. 다수의 쓰레드를 불필요하게 깨워서 문맥 교환이 많이 발생하는 단점이 있다.

 

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

 

[31장. 세마포어]

 

세마포어는 초기값에 의해 동작하기 때문에 반드시 제일 먼저 값을 초기화해야 한다.

 

이진 세마포어: 락의 상태가 두가지만 존재한다.

 

세마포어는 병행 프로그램에서 일어나는 사건의 순서를 정하는 데에도 유용하다.

 

생산자-소비자 문제

다수의 쓰레드가 존재하는 경우에 상호 배제가 지켜지지 않아 경쟁 조건이 발생한다.

 

교착 상태의 방지

락의 범위를 줄여야 한다.

 

식사하는 철학자

모든 포크는 누군가 다 잡고있고 서로 대기중이기 때문에 교착 상태가 발생한다.

단순한 해결방법으로는 최소 한명의 철학자가 다른 순서로 포크를 집도록 하면 된다.

 

쓰레드 제어: 과도하게 많은 쓰레드가 동시에 실행되면 성능이 나빠지므로 쓰레드 개수의 임계값을 정하고 동시에 실행하는 쓰레드 개수를 제한한다.

 

 

내용이 많아서 어느정도 쳐냈음. 다른 정보들도 더 찾아봐야 할 것 같음

 

[32장. 병행성 관련 버그]

 

비 교착 상태 오류

• 원자성 위반 오류: 다수의 메모리 참조 연산들에 대해 예상했던 직렬성이 보장되지 않음. 락을 추가해서 해결할 수 있다.
• 순서 위반 오류: 메모리 참조 간의 순서가 지켜지지 않음. 컨디션 변수를 추가해 동기화하여 해결할 수 있다.

 

교착 상태 오류

교착 상태 발생 조건

• 상호 배제
• 점유 및 대기
• 비선점
• 환형 대기

네 가지 조건중 하나라도 만족하지 않는다면 교착 상태는 발생하지 않는다.

 

교착 상태의 예방

• 순환 대기: 락 획득을 하는 전체 순서를 정한다. 부분 순서만을 정의할 수도 있다.
• 점유 및 대기: 원자적으로 모든 락을 한번에 획득하도록 한다. 실제 필요할 때 요청하는것이 아니라서 병행성이 저하되는 문제가 있다.
• 비선점
• 상호 배제

 

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

병행성에 제약을 가져 올 수도 있는 문제가 있기때문에 보편적으로 사용되는 방법은 아니다.

 

발견 및 복구

교착 상태 발생을 허용하고 발견 시 복구하도록 하는 방법.

 

[33장. 이벤트 기반의 병행성(고급)]