스레드 동기화 (명품_운영체제 Ch 06)

스레드 동기화

공유 데이터에 대한 다수 스레드의 동시 접근을 해결하는 방법 다수의 스레드들이 공유 데이터에 동시에 접근하면 공유 데이터가 훼손, 변형될 수 있다

문제 예시

공유 집계판 문제

• 공유 데이터에 대한 변경을 하는 작업에서 앞선 스레드가 중간에 중단되어 뒤의 두 번째 스레드가 실행되고 완료됨. 이후 다시 실행되는 첫 번째 스레드는 두 번째 스레드가 만든 값이 아닌 중단될 때 저장한 값을 사용함

• sum = sum + 10; 코드를 기계 명령으로 번역하면
  -> mov ax, sum
  add ax, 10
  mov sum, ax

• T1은 sum 변수의 값을 ax 레지스터에 저장하고 인터럽트로 인해 작동이 중단됨
  ->T2 가 실행되어 모든 작업을 완료하고 sum 변수의 값이 10 증가되어 60이 됨
  ->T1이 다시 실행되었고, 기존에 저장된 시점부터 시작되기 때문에 sum 값이 50인 상태에서 10을 더하여 sum 값이 여전히 60이 됨
  ->두 스레드가 10씩 더했으나 70이 아닌 60으로 최종 값이 결정됨(10이 사라짐)

해결 방법

• 스레드 동기화를 통해 공유 데이터를 한 개의 스레드 씩 사용하도록 제어
• 즉, 해당 코드의 실행의 완전히 종료되기 전까지 다른 스레드의 접근을 막는 것

임계구역과 상호배제

스레드 동기화는, 먼저 접근한 스레드가 공유 데이터를 배타적으로 사용하도록 다른 스레드의 접근을 상호 협력하여 막는 것 이와 관련하여 알아야할 2개의 용어이다

임계구역(critical section)

• 사용자가 작성한 프로그램 중 공유 데이터에 접근하는 코드 블록
• 훼손을 막기 위해, 반드시 한 스레드만 배타적 독점적으로 실행하도록 관리되어야 함
  • 이를 상호배제(mutual exclusion)라고 한다
  • 상호배제 장치가 없는 임계구역은 있을 수 없다
• 임계구역 설정은 전부 개발자에 의해 이루어진다(멀티스레드 라이브러리, 시스템 호출 등을 통해)
  • 공유 데이터를 엑세스하는 부분만 최소화하여 임계구역을 설정하는 것이 좋다

상호배제(mutual exclusion)

• 임계구역에 먼저 진입한 스레드가 실행을 끝낼 때까지 다른 스레드가 진입하지 못하도록 보장하는 것

상호배제 구현 위치

• 임계구역 전후에 상해보제 코드가 작성된다
• 각각 임계구역 진입코드(entry 코드), 임계구역 진출코드(exit 코드)

• 임계구역 진입 코드(entry 코드)
  • 임계구역 진입 전 필요한 코드 블록
  • 현재 임계구역을 이미 실행중인 스레드가 있는지 검사
  • 없는 경우 현재 스레드를 진입시키고 다른 스레드가 들어오지 못하도록 조치
  • 있는 경우 해당 스레드가 임계구역 실행을 끝내고 exit 코드를 실행할 때까지 현재 스레드를 대기시킴
• 임계구역 진출코드(exit 코드)
  • 임계구역 실행을 마칠 때 실행되어야 하는 코드 블록
  • entry 코드에서 대기 중인 스레드가 임계구역에 진입할 수 있도록 entry 코드에서 취한 조치 해제

상호배제 구현

소프트웨어적, 하드웨어적 방법이 있으며 현대에는 하드웨어적 방법 중 원자명령을 활용하는 방법을 사용한다

1. 인터럽트 서비스 금지
   • 임계구역으로 진입할 때 entry 코드를 통해 인터럽트 서비스를 금지하고 exit 코드에서 다시 허용하도록 한다
   • 임계구역 실행 중 인터럽트가 발생하지 않아 해당 스레드는 선점(preemption)되지 않는다

*그러나 인터럽트가 발생하지 않게 하려면 모든 입출력 장치와 타이머가 인터럽트를 걸지 못하도록 해야하기에 현실적으로 불가능하다

• 다른 방법
  • 인터럽트 자체는 허용하되, 임계구역 실행 동안만 CPU가 인터럽트를 서비스하지 않도록 한다
  • entry 코드에서 서비스를 못하도록 하는 기계 명령 실행, exit 코드에서 다시 허용하는 기계 명령 실행
  • 대표적인 x86 명령으로 cli와 sti가 있다
• cli 명령
  • CPU 내부의 인터럽트 플래그(IF)를 0으로 설정하여, CPU가 인터럽트를 무시하고 현재 작업을 계속 수행하게 한다
• sti 명령
  • CPU 내부의 인터럽트 플래그(IF)를 1로 설정하여, 인터럽트 발생 시 CPU가 인터럽트 서비스 루틴을 실행하게 한다 인터럽트 플래그 : 외부 인터럽트에 대해서 응답 여부를 결정하는 CPU FLAGS 레지스터 내부의 플래그 비트 내부 인터럽트 : 인터럽트 플래그를 통한 제어가 불가능한 중요한 인터럽트 (ex 하드웨어 고장, 실행 불가 명령어, 명령어 실행 오류, 사용 권한 위배) 외부 인터럽트 : 주로 입출력 장치에 의해 발생하며, 인터럽트 플래그를 통해 제어 가능(ex 타이머 인터럽트, 입출력 인터럽트)

그러나.. 이 방법도 임계구역 실행 시간이 길어지는 동안 계속 인터럽트가 무시되는 점, cli가 다른 코어나 다른 CPU의 인터럽트는 막지 못하는 2가지 문제가 있다

1. 원자명령(atomic instruction) 사용
   • 상호배제를 위해 만들어진 CPU 명령
   • CPU마다 이름은 다르지만 대부분의 CPU가 제공
   • 현대에서 사용하는 상호배제 방법이며, 원자명령 없이는 상호배제가 불가능하다

• 원자명령 없이 lock 변수를 이용한 상호배제 시도
  • 0과 1을 가지는 lock 변수를 통해 임계구역에 들어갈 때 entry 코드를 통해 1을 쓰고 나올 때 exit 코드를 통해 0으로 변경하여 0인 경우에만 임계구역에 들어갈 수 있도록 하는 방법(locking/unlocking 방식)
• 실패 예시 진행 순서
  1. T1이 entry 코드를 실행하여 lock 변수 값 0을 ax로 읽어 들인 후, T2로 컨텍스트 스위칭 됨, lock에 1을 쓰지 못하고 종료
  2. T2가 실행되어 lock 변수에 1을 쓰고(잠그고) 임계구역 실행, 실행하다가 중간에 중단
  3. T1이 다시 스케줄링되어 TCB1 값들과 함께 복귀 후 mov lock, 1 명령부터 실행
  4. 중단 이전에 읽어놓은 lock값 0이 ax에 저장되어 있어서 임계구역으로 진입하게 되고 T1, T2가 모두 임계구역에 있어 상호배제에 실패하게 된 상황

실패 원인

• lock을 읽는 명령과 lock을 1로 바꾸는 명령 사이에 컨텍스트 스위칭이 발생함
• 읽는 명령과 바꾸는 명령을 한 단위로 실행하도록 해야함

해결 방법

• 원자명령(aomic instruction, TSL(Test and Set)이라고도 한다) 도입하여 두 명령을 하나의 명령으로 만드는 것

개발자가 직접 원자명령을 이용한 entry/exit 코드를 작성할 수는 없기에 여러 동기화 라이브러리를 이용한다

멀티스레드 동기화 기법

임계구역을 지키는 상호배제를 위해 스레드를 동기화하며, 일반적인 동기화 기법들은 스레드 라이브러리나 시스템 호출에 의해 제공된다

이들은 동기화 프리미티브(synchronization primitive)로 불리며, 상호배제를 위해 원자명령을 사용한다

• 락(lock) 방식
  • 하나의 락 변수를 두고, 락을 잠근 스레드만이 임계구역에 진입하도록 하는 기법
  • 뮤텍스(mutex), 스핀락(spinlock)
• wait-signal 방식
  • 여러 개의 공유 자원을 여러 스레드가 사용할 수 있도록 관리하는 기법
  • 이진 세마포(binary semaphore)
    • 카운터 세마포(counter semaphore)는 항상 상호배제를 만족하지는 않는다

뮤텍스

락 변수를 이용하여, 한 스레드만 임계구역에 진입시키고 다른 스레드들은 큐에 대기시키는 기법

구성요소

• 변수
  • 락 변수
    • locked/unlocked 중 하나의 상태를 가진다
• 연산
  • lock/unlock 연산
    • lock 연산 = entry 코드, unlock 연산 = exit 코드
    • 연산 구현에 원자명령이 사용된다
• 큐
  • 대기 큐(wait queue)

동기화 과정 예시

1. T1 스레드가 lock 연산으르 실행하여 락을 잠그고 임계구역 실행
2. 그동안 T2가 실행되어 lock 연산을 실행하였으나 락이 잠겨져있어 T2를 중단시키고 대기 큐에 삽입
3. T1이 임계구역 실행을 마치고 unlock 연산 실행 락을 열림 상태로 바꾸고 대기 큐에 잠든 스레드 하나를 꺠워 준비 리스트에 넣음 unlock 연산을 마친 후 다른 작업을 계속 진행
4. 깨어난 스레드 T2는 준비 리스트에 있다가 스케줄링되면 중단된 lock 연산에서 재실행하여 임계구역으로 진입

특징

• 임계구역의 실행 시간이 짧은 경우 비효율적이다
  • 락이 잠겨있는 시간보다 스레드가 잠자고 깨는 시간 낭비가 더 크기 때문이다

스핀락

뮤텍스와 다르게 대기 큐가 없는 락 기반 동기화 기법 락이 열린 상태이면 잠김 상태로 만들고 임계구역에 진입하며, 잠긴 상태이면 열릴 때까지 락 검사를 무한 반복하여 열리면 락을 잠그고 임계구역에 진입한다

구성요소

• 변수
  • 락 변수
    • 스핀락이라고 부르면 스핀락을 소유한 한 개의 스레드만 임계구역에 진입할 수 있음
• 연산
  • lock/unlock 연산
    • lock 연산 = entry 코드, unlock 연산 = exit 코드
    • 잠긴 락에 대해 무한 루프를 통해 풀릴 때까지 검사하며, 중간에 타이머 인터럽트로 컨텍스트 스위칭되고, 다시 스케줄링되면 다시 무한 반복한다

스핀락을 공격적인 뮤텍스(aggressive mutex) 혹은 바쁜 대기 락(busy-waiting lock) 이라고도 한다

동기화 과정 예시

1. T1 스레드가 lock 연산을 수행하여 락을 잠구고 임계구역을 실행한다
2. 실행 중에 T2가 스케줄되어 lock연산을 실행하는데 잠겨있기 때문에 열림 상태가 될 때까지 반복하여 락을 검사하는 CPU 명령들을 실행한다
3. T1이 임계구역 실행을 마치고 unlock 연산을 실행한다
4. 락이 열림 상태가 되며, T1은 임계구역을 벗어나 다른 작업을 지속하낟
5. T2는 반복된 락 검사를 하는 중에 락이 열림 상태가 된 것을 확인하고 락을 잠근 뒤 임계구역으로 들어간다

특징

• 뮤텍스 기법의 바쁜 대기(busy-waiting) 모형으로, 락이 잠겨있을 떄 열릴 때 까지 검사를 반복한다
• 단일 CPU 운영체제에서 매우 비효율적이다
  • 스레드가 락 검사를 반복할 때, 임계구역에서 실행중인 스레드가 unlock 연산을 수행해줘야 락이 풀리는데 그렇게 할 수 없기 떄문에 의미없는 CPU 사용이 발생한다
• 임계구역 코드가 짧을수록 성능이 좋다
  • 임계구역 코드가 짧을수록 락이 빠르게 열리기 때문
• 락을 얻기 위한 무한 경쟁 시스템으로 인해 기아가 발생할 수 있다
  • 또한 락을 잠근 스레드가 락을 열지 않고 종료되거나 코딩이 잘못되어 무한 루프를 도는 경우, 다른 스레드들은 무한정 락 검사에 CPU를 사용하며 영원히 기다리게 될 수도 있다

리눅스 커널은 스레드 동기화의 기본 기법으로 스핀락을 사용한다

하이브리드 뮤텍스란? 뮤텍스와 스핀락을 혼합한 동기화 방식으로 오늘날 커널에서 많이 사용된다 처음에는 스핀락처럼 동작하다가 일정 시간 내에 락을 획득하지 못하면 뮤텍스처럼 스레드를 블록상태로 만들어 대기 큐에 넣어 대기시킨다

뮤텍스 VS 스핀락

	뮤텍스	스핀락
대기 큐	있음	없음
블록 가능 여부	락이 점겨 있으면 블록됨(blocking)	락이 잠겨 있어도 블록되지 않고 계속 락 검사(non-blocking)
lock/unlock 연산 비용	저비용	CPU를 계속 사용하므로 고비용
하드웨어 관련	단일 CPU에서 적합	멀티코어 CPU에서 적합
주 사용처	사용자 응용 프로그램	커널 코드, 인터럽트 서비스 루틴

세마포

n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원 관리 기법

자원이 부족하면 스레드를 대기큐에서 대기시키고 자원 사용을 끝낸 스레드가 세마포에게 알려주면 대기큐에서 스레드를 깨워 자원을 사용하게 한다

세마포 종류

• 카운터 세마포(counter semaphore)
  • 관리하는 자원이 여러 개인 경우
• 이진 세마포(binary semaphoer)
  • 관리하는 자원이 1개인 경우

카운터 세마포

하나의 자원에 한 번에 최대 n개의 스레드가 접근 가능하다 접근한 스레드의 갯수를 카운팅하여 자원을 관리하는 기법

구성요소

• 자원
  • n개
• 대기 큐
  • 자원을 할당받지 못한 스레드가 대기하는 곳
• counter 변수
  • 사용가능한 자원의 개수를 나타내는 정수형 변수(자원의 개수 n으로 초기화됨)
  • 음수이면 자원을 기다리는 스레드의 개수를 나타냄
• P/V 연산
  • 자원 요청 시 P 연산, 자원 반환 시 V 연산이 실행됨 counter 변수 또한 P, V 연산에서 사용하는 공유 데이터이므로 접근을 원자적으로 처리되도록 구현되며 여러 스레드가 동시에 P, V 연산을 수행할 수 없다

P 연산과 V 연산

• wait/signal 연산으로도 불린다
• P 연산
  • 스레드에게 자원 사용을 허가하는 과정
  • counter 변수를 1 감소시킨다
• V 연산
  • 스레드가 자원 사용이 끝났음을 세마포에게 알리는 과정
  • counter 변수를 1 증가시킨다

수면 대기(sleep-wait) 세마포와 바쁜 대기(busy-waiting) 세마포

• 수면 대기 세마포
  • P 연산 중 자원 사용을 허가받지 못한 스레드를 대기 큐에서 잠을 재우고(sleep-wait), V 연산에서 사용가능한 자원이 생기면 스레드를 깨워 사용하도록 하는 형태
• 바쁜 대기 세마포
  • P 연산에서 사용 가능한 자원이 생길 때까지 무한 루프를 돌며 검사하는 방식
  • 대기 큐가 없다

동기화 과정 예시

1. 자원에 4개의 인스턴스가 있을 때 counter 변수는 4로 초기화된다
2. T1, T2, T3, T4 스레드가 순서대로 P 연산을 실행하여 자원을 할당받고 counter 변수는 0이 된다
3. T5, T6은 P 연산을 실행했으나 counter 변수가 0 이하이기 떄문에 대기 큐에 들어가며 counter 변수는 -2가 된다
4. 이후 자원을 사용중이던 스레드 중 특정 스레드가 V 연산을 통해 자원 사용을 중단할 때, 대기 큐에 있던 스레드가 차레대로 자원을 할당받게 됨

이진 세마포

구성요소

• 세마포 변수 S
  • 0과 1 중 하나를 가지는 변수, 1로 초기화 됨
• 대기 큐
  • 자원이 사용가능하게 될 때까지 스레드들이 대기하는 큐
• P 연산
  • 자원 사용 허가를 얻는 과정으로 S를 1 감소시킨 뒤 S가 0보다 작으면 스레드를 대기 큐에서 잠들게 한다
  • 만일 S가 감소한 뒤 0보다 크거나 같으면 스레드는 자원을 사용하는 코드를 실행한다
• V 연산
  • 자원 사용이 끝났음을 알리는 과정으로 S를 1 증가시킨 뒤 S가 0보다 크면 리턴한다
  • 만약 S가 증가한 뒤 0보다 작거나 같으면 대기 큐에 있는 스레드 중 하나를 깨운다

세마포 VS 뮤텍스, 스핀락

이렇게 보면 세마포는 대기 스레드를 처리하는 방식에 따라 뮤텍스나 스핀락과 차이가 없이 똑같아 보인다(P/V 연산 = lock/unlock ,,?)

결국 자원 하나 당 하나의 스레드가 들어갈 때 락을 잠그고 나올 때 열어서 다음 스레드를 들어가게 하는 방식이다

하지만 자원의 소유권의 관점에서 차이가 있다

뮤텍스

• 목적이 무엇인가?
  • 공통적인 상호배제를 포함하여 특정 코드 영역 보호를 위해 락을 거는 것
• 자원을 소유하는가?
  • 소유한다고 볼 수 있다
  • 자원 사용이 완료된 뒤에 실행하는 unlock 연산은 반드시 lock 연산을 실행한 스레드 본인이 실행해야한다

세마포

• 목적이 무엇인가?
  • 자원에 접근하는 스레드의 개수를 제한하는 것
• 자원을 소유하는가?
  • 소유권 개념이 없다
  • 자원 사용이 완료된 뒤에 실행하는 V 연산은 원칙적으론 P 연산을 실행한 스레드가 실행해야 하지만 특정 상황에 있어 다른 스레드가 실행할 수 있다

핵심은 세마포는 특정 상황에 한하여 P(lock) 연산을 실행한 스레드가 아닌 다른 스레드가 V(unlock) 연산을 실행하여 락을 열림 상태로 만들 수 있다는 것

우선순위 역전

스레드 동기화로 인해 우선순위가 높은 스레드가 순위가 낮은 스레드보다 늦게 실행되는 상황

과정 예시

• 조건
  • 우선순위 : T3 > T2 > T1
  • T1, T3는 자원을 공유하며 뮤텍스나 이진 세마포로 동기화된다
  • T2는 다른 스레드와 자원을 공유하지 않는다
    1. T1이 먼저 스레드 큐에 도착하여 스케줄링 되어 실행되고 세마포 P 연산을 통해 자원을 할당받음
    2. T1 실행 중 우선순위가 더 높은 T3가 도착하여 컨텍스트 스위칭 됨
    3. T3가 P 연산을 실행하지만 이미 T1에게 할당된 자원이기에 P 연산에서 잠든다
    4. 다시 T1이 스케줄링 되어 실행
    5. T1보다 높은 순위의 T2가 도착하여 컨텍스트 스위칭 됨(이때, T2가 T3보다 순위가 낮음에도 먼저 실행되는 우선순위 역전이 발생)
    6. T2가 끝난 후 T1이 다시 실행
    7. T1이 자원을 다 사용한 후 V 연산을 실행하면 T3이 깨어나며, 운영체제는 우선순위가 더 높은 T3로 컨텍스트 스위칭

T2처럼 T1보다 높은 스레드가 계속 들어오면 T3의 실행도 계속 늦어져서 우선순위가 높은 중요한 작업을 처리할 수 없는 심각한 문제가 발생

해결책

• 우선순위 올림(priority ceiling)
  • 스레드가 공유 자원을 소유하게 될 때 일시적으로 미리 정해진 우선순위를 가지게 하는 기법
  • 해당 우선순위는 공유 자원을 액세스하는 어떤 스레드 보다 높게 책정되어 다른 스레드에 의해 선점되지 않고 빠르게 자원의 사용을 마침
  • 이후 공유 자원에 대한 액세스가 끝나면 원래대로 돌아감
• 우선순위 상속(priority inheritance)
  • 스레드가 공유 자원을 소유하여 실행하는 동안 높은 순위의 스레드가 공유 자원을 요청하면 해당 스레드보다 우선순위를 높게 설정하여 실행을 지속함
  • 자원 사용이 끝나면 원래대로 돌아감
• 두 기법 모두 공유 자원을 소유한 스레드의 우선순위를 높여 최대한 빨리 공유 자원을 해제하도록 하기 위함

생산자 소비자 문제

전형적인 동기화 문제를 알아보자

정의

• 공유 버퍼에 데이터를 공급하는 생산자들과 공유 버퍼에서 데이터를 읽고 사용하는 소비자들이 공유 버퍼를 문제없이 사용하도록 동기화 시키는 것 (ex 웹 서버와 클라이언트)

발생 가능한 문제

• 생산자와 소비자가 동시에 공유 버퍼에 접근하는 문제(상호배제)
• 생산 속도가 소비 속도보다 느려서 소비자가 데이터를 읽으려 할 때 공유 버퍼가 비어있는 문제(비어있는 공유 버퍼 문제)
• 생산 속도가 소비 속도보다 빨라서 생산자가 데이터를 생성하려 할 때 공유 버퍼가 가득 차있는 문제(꽉 찬 공유 버퍼 문제)

ex) 비디오 플레이어, 스트리밍 서버

문제 상황에 따른 해결책

• 상호배제 문제
  • 뮤텍스, 세마포와 같은 동기화 기법 사용
• 비어있는 공유 버퍼 문제
  • 비어있는 버퍼를 본 소비자 스레드는생산 스레드가 버퍼에 데이터를 쓸 때까지 기다려야 하기 때문에 소비자 스레드는 대기(wait), 생산자 스레드는 대기상태에서 깨어나도록 알리는(signal) 세마포 R(read)를 사용한다
    • R은 그냥 이름일 뿐 특별한 기능이 있는 것은 아니며, counter 값은 읽기 가능한 버퍼의 개수를 나타낸다
  • P 연산은 소비자 스레드가, V 연산은 생산자 스레드가 실행하도록 설계
• 꽉 찬 공유 버퍼 문제
  • 꽉 차있는 버퍼를 본 생산자 스레드는 소비자 스레드가 하나라도 비울 때까지 기다려야 하기 때문에 wait-signal 방식으로 세마포 W를 사용한다
    • W는 그냥 이름일 뿐 특별한 기능이 있는 것은 아니며, counter 값은 쓰기 가능한 버퍼의 개수를 나타낸다
  • P 연산은 생성자 스레드가, V 연산은 소비자 스레드가 실행하도록 설계

생산자, 소비자 문제를 해결하기 위해선 2개의 카운팅 세마포(R, W)가 필요하며 버퍼를 읽고 쓰는 임계구역의 상호배제를 위해 1개의 뮤텍스가 필요하다