운영체제(Operating System) - 스레드 동기화

스레드 동기화의 필요성

다수의 스레드가 공유 데이터를 동시에 접근하는 충돌 상황에서 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 기법
-> 한 스레드가 공유 데이터에 대해 배타적이고 독점적으로 접근, 임계구역에 대한 상호배제 구현

예시
두 학생 : 스레드 T1, T2
공유 집계판 : 공유 변수 sum
계산 식 : sum = sum + 10;

스레드 동기화가 안된 사례

#include <stdio.h> 
#include <pthread.h>
int sum = 0; // 두 스레드가 공유하는 변수
void* worker(void* arg) { // 스레드 코드 
  for(int i=0; i<1000000; i++) {
    sum = sum + 10;
    } 
}


int main() {
  char *name[] = {"철수", "영희"};
  pthread_t tid[2]; // 2개의 스레드 ID를 담을 배열 
  pthread_attr_t attr[2]; // 2개의 스레드 정보를 담을 배열
  pthread_attr_init(&attr[0]); // 디폴트 속성으로 초기화 
  pthread_attr_init(&attr[1]); // 디폴트 속성으로 초기화
  pthread_create(&tid[0], &attr[0], worker, name[0]); // 스레드 생성 
  pthread_create(&tid[1], &attr[1], worker, name[1]); // 스레드 생성
  pthread_join(tid[0], NULL); pthread_join(tid[1], NULL);
  printf("sum = %d\n", sum); // 두 스레드 종료 후 sum 출력 
  return 0;
}

$ gcc –o sum sum.c -lpthread $ ./sum
sum = 13814970
$ ./sum
sum = 10352010 $ ./sum
sum = 11502410 $

공유 변수 sum에 대한 두 스레드의 충돌로 인해, 20000000에 미치지 못하는 결과가 발생했다.
sum은 공유변수, sum = sum + 10이 임계구역인데
임계구역을 한 스레드가 배타적으로 사용할 수 있도록해주는 동기화(상호배제)기능이 마련되지 않았기 때문.

임계구역과 상호배제

임계구역(critical section)
공유 데이터에 접근하는 프로그램 코드들

상호배제(mutual exclusion)
임계구역을 오직 한 스레드만 배타적 독점적으로 사용하도록 하는 기술
임계구역에 먼저 진입한 스레드가 임계구역의 실행을 끝낼 때까지 다른 스레드가 진입하지 못하도록 보장

상호 배제(mutual exclusion)

일반 코드(non-critical code)

• 공유 데이터를 액세스하지 않는 코드

임계구역 진입 코드(entry code)

• 상호배제를 위해 필요한 코드
• 임계구역에 진입하기 전 필요한 코드 블록
• 현재 임계구역을 실행 중인 스레드가 있는지 검사
  - 없다면, 다른 스레드가 들어오지 못하도록 조치하고 진입
  • 있다면, 진입이 가능해질 때까지 대기

임계구역 코드(critical code)

• 최소한의 코드

임계구역 진출 코드(exit code)

• 상호배제를 위해 필요한 코드
  - 임계구역의 실행을 마칠 때 실행되어야 하는 코드 블록
• 진입 코드에서 대기중인 스레드가 임계구역에 진입할 수 있도록, 진입 코드에서 취한 조치를 해제하는 코드
• 임계구역의 상호배제를 위한 코드
  

상호 배제 구현

임계구역에 오직 1개의 스레드만 진입하도록

방법 1 – 인터럽트 서비스 금지

임계구역 entry 코드에서 인터럽트 서비스를 금지하고 exit 코드에서 인터럽트 서비스를 허용하는 명령 실행

cli ; entry 코드. 인터럽트 서비스 금지 명령 cli(clear interrupt flag) .....
임계구역 코드
...
sti ; exit 코드. 인터럽트 서비스 허용 명령 sti(set interrupt flag)

cli명령은 CPU내부의 인터럽트 플래그(IF)를 0으로 리셋시켜, 인터럽트가 발생해도 CPU가 인터럽트를 무시하고 현재 작업을 계속 수행하게 함.
sti명령은 인터럽트 플래그를 1로 설정하여 인터럽트가 발생하면 CPU가 하던 일을 멈추고 인터럽트 서비스 루틴을 실행하게 함

문제점
1. 모든 인터럽트가 무시되는 문제 발생(임계구역의 실행시간이 길어지면)
2. 멀티 코어 CPU나 다중 CPU를 가진 시스템에서 활용 불가(한 CPU의 인터럽트 금지로 다른 CPU에게 인터럽트를 금지시킬 수 없음)

방법 2 - 원자 명령(atomic instruction) 사용

원자명령: 상호배제를 위해 만들어진 CPU명령

Q. locking/unlocking 방식으로 임계구역의 entry/exit 코드 작성하면 상호배제가 가능할까?
lock 변수가 1이면 잠금 상태. 0이면 열린 상태

상호 배제가 잘 이루어진 것 처럼 보이지만..

lock 변수 값을 읽는 명령과 lock 변수에 1을 저장하는 2개의 명령 사이에 컨텍스트 스위칭이 될 때 문제가 발생한다.

원자 명령(또는 TLS)을 이용한 상호배제

lock 변수를 읽어 들이는 명령과 lock 변수에 1을 저장하는 2개의 명령을 하나의 명령으로 처리한다.(기계어명령어 종료 후 인터럽트 체크함. page fault의 경우는 예외)

멀티스레드 동기화 기법

• 상호배제 기반위에 자원을 사용하려는 여러 스레드들이 자원을 원활히 공유하도록 하는 기법
• 동기화 프리미티브(synchronization primitives)

대표적인 기법
locks 방식 : 뮤텍스(mutex), 스핀락(spinlock)

• 상호배제가 되도록 만들어진 락(lock) 활용
• 락을 소유한 스레드만이 임계구역 진입
• 락을 소유하지 않은 스레드는 락이 풀릴 때까지 대기
  wait-signal 방식 : 세마포(semaphore)
• n개 자원을 사용하려는 m개 멀티스레드의 원활한 관리
• 자원을 소유하지 못한 스레드는 대기(wait)
• 자원을 다 사용한 스레드는 알림(signal)

뮤텍스

• 잠김/열림중한상태를가지는lock변수이용
• 한 스레드만 임계구역에 진입시킴
• 다른 스레드는 큐에 대기

구성요소

락 변수

• true 혹은 false
• true : 락을 잠근다. 락을 소유한다.
• false : 락을 연다. 락을 해제한다.
  대기 큐
• 락이 열리기를 기다리는 스레드 큐
  연산
• lock 연산(임계구역의 entry 코드)
• 락이 열린 상태이면, 락을 잠그고 임계구역 진입
• 락이 잠김 상태(lock = true)이면, 현재 스레드를 블록 상태 로 만들고 대기 큐에 삽입
  unlock 연산(임계구역의 exit 코드)
• lock = false, 락을 열린 상태로 변경
• 대기 큐에서 기다리는 스레드 하나 깨움
  

뮤텍스를 활용한 스레드 동기화 과정

뮤텍스의 특징

• 임계구역의 실행 시간이 짧은 경우 비율적
• 락이 잠겨 있으면 (컨텍스트 스위칭되어) 대기 큐에서 대기, 락이 풀리면 다시 (컨텍스트 스위칭되어) 실행
• 락이 잠겨있는 시간보다 스레드가 잠자고 깨는 데 걸리는 시간이 상대적으로 크다

뮤텍스 동기화를 위한 POSIX 표준 라이브러리

• 뮤텍스락 변수 생성: pthread_mutex_t lock;
• 뮤텍스 조작 함수들
  pthread_mutex_init() – 뮤텍스락 변수 초기화
  pthread_mutex_lock() - 뮤텍스락 잠그기
  pthread_mutex_unlock() - 뮤텍스락 풀기
  pthread_mutex_destroy() - 뮤텍스락 변수 사용 종료

스핀락

busy-waiting lock 기법

• 스레드가 큐에서 대기하지 않고 락이 열릴 때까지 계속 락 변수 검사
• 대기 큐 없음
• busy-waiting으로 인해 CPU를 계속 소모, CPU가 다른 스레드를 실행할 수 없음
• 락을 소유한 스레드만 자원 배타적 사용, 동기화 기법
• 공유 자원 하나 당 하나의 스핀락 사용

구성요소

락 변수

• true 혹은 false
• true : 락을 잠근다. 락을 소유한다.
• false : 락을 연다. 락을 해제한다.
  연산
• lock 연산
• 임계구역에 들어갈 때 실행되는 entry 코드
• 락이잠김상태면,락이풀릴때까지무한루프돌면서lock연산시도
• 락이열린상태면,락을잠김상태로바꾸고임계구역실행
• unlock 연산
• 임계구역을 나올 때 실행하는 exit 코드
• 락을 열림 상태로 변경
  

스핀락을 활용한 스레드 동기화 사례

스핀락 특징
뮤텍스의 non-blocking 모델, busy-waiting

• 단일 CPU(단일 코어)를 가진 운영체제에서 비효율적, 멀티 코어에 적합
• 단일코어CPU에서T2의경우의미없는CPU시간낭비
• Multi core의 경우 lock을 경쟁하는 스레드를 각기 다른 core에서 실행시키면 효과적
• 임계구역의 실행 시간이 짧은 경우 효과적
• 기아가발생할수있음

스핀락 동기화를 위한 POSIX 표준 라이브러리
스핀락 변수 생성

• pthread_spinlock_t lock;
  스핀락 조작 함수들
  pthread_spin_init() - 스핀락 변수 초기화
  pthread_spin_lock() - 스핀락 잠그기
  pthread_spin_unlock() - 스핀락 풀기
  pthread_spin_destroy() - 스핀락 변수 사용 종료

뮤텍스와 스핀락은 어떤 경우에 적합한가?

락이 잠기는 시간이 긴 응용 : 뮤텍스

• 락을 얻지 못했을 때, CPU를 다른 스레드에게 양보하는 것이 효율적
• 락이 잠기는 시간이 짧은 경우 : 스핀락이 효율적

단일 CPU를 가진 시스템 : 뮤텍스

• 단일 CPU에서 스핀락은 크게 의미 없음

멀티 코어(멀티 CPU)를 가진 시스템 : 스핀락

• 잠자고 깨는 컨텍스트 스위칭 없이 바로 자원 사용
• 임계구역을 가능한 짧게 작성하므로

사용자 응용프로그램 : 뮤텍스, 커널 코드 : 스핀락

• 커널 코드나 인터럽트 서비스 루틴은 빨리 실행되어야 하고
• 인터럽트 서비스 루틴 내에서 잠잘 수 없기 때문

스핀락을 사용하면 기아 발생 가능

• 스핀락은 무한 경쟁 방식이어서 기아 발생 가능
• 락을 소유한 스레드가 락을 풀지 않고 계속 실행하거나 종료해버린 경우
• 코딩이 잘못된 경우

세마포(semaphore)

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

구성 요소

자원 : n 개
대기 큐 : 자원을 할당받지 못한 스레드들이 대기하는 큐
counter 변수

• 사용 가능한 자원의 개수를 나타내는 정수형 전역 변수(n으로 초기화)
• 음수이면 자원을 기다리는 스레드의 개수
  P/V 연산
  P연산(wait 연산) – 자원 요청 시 실행하는 연산
• 자원사용허가를얻는과정
  V 연산(signal 연산) – 자원 반환 시 실행하는 연산
• 자원 사용이 끝났음을 알리는 과정
  

P 연산과 V 연산

P 연산 : 자원 사용을 허가하는 과정, 사용가능 자원 수 1 감소(counter--)
V 연산 : 자원 사용을 마치는 과정, 사용가능 자원 수 1 증가(counter++)

세마포 종류 2가지
자원을 할당받지 못한 경우의 행동에 따라 구분
sleep-wait 세마포

• P연산 : 대기 큐에서 잠자기
• V연산: 사용가능 자원이 있으면 잠자는 스레드 깨우기
  busy-wait 세마포
• P연산 : 사용 가능 자원이 생길 때까지 무한 루프, V연산: counter--;
  

세마포 구조체
sem_t s; // counter 변수 등을 가진 세마포 구조체

세마포 조작 함수들
sem_init() - 세마포 초기화
sem_destroy() - 세마포 기능 소멸
sem_wait()

• P 연산을 수행하는 함수(blocking call)
• sleep-wait 방식으로, 가용 자원이 없으면 대기 큐에서 잠을 잠
  sem_trywait()
• P 연산을 수행하는 함수(non-blocking call)
• 가용 자원이 있으면, counter 값을 감소시키고 0리턴 - 없으면, counter 값을 감소시키지 않고 -1 리턴
  sem_post()
• V 연산을 수행하는 함수
• sem_getvalue()
• 세마포의 현재 counter 값을 리턴하는 함수

카운터 세마포와 이진 세마포

카운터 세마포(counter semaphore)

• 자원의 인스턴스가 n개(n>1)인 경우
  이진 세마포(binary semaphore)
• 자원이 1개 있는 경우 멀티스레드 사이의 자원 관리
• 1개의 자원에 대해 1개의 스레드만 액세스할 수 있도록 보호(뮤텍스와 매우 유사)

이진 세마포 구성요소
1. 세마포 변수 S

• 0 과 1 중 하나를 가지는 전역 변수, S는 1로 초기화

2. 대기 큐

• 사용 가능한 자원이 생길 때까지 스레드들이 대기하는 큐 - 스레드 스케줄링 알고리즘 필요

3. 2개의 원자 연산

• wait 연산(P 연산) – 자원 사용 허가를 얻는 과정
• S를 1 감소시키고, 0보다 작으면 대기큐에서 잠듦.
  0보다크거나 같으면,자원 사용하는코드 실행
• signal 연산(V 연산) – 자원 사용이 끝났음을 알리는 과정
• S를1증가시키고,0보다크면그냥리턴.0보다 작거나 같으면대기큐에 있는 스레드 중 하나를 깨움

동기화 이슈 : 우선순위 역전

우선순위 역전(priority inversion)

• 스레드의 동기화로 인해 높은 순위의 스레드가 낮은 스레드보다 늦게 스케줄링되는 현상
• 우선순위를 기반으로 스케줄링하는 실시간 시스템에서 스레드 동기화로 인해 발생

우선 순위 역전의 문제점

• 실시간 시스템의 근본 붕괴
• 우선순위가 높다는 것은 중요한 일을 할 가능성이 높은데, 높은 순위의 스레드(T3)가 늦게 실행되면 심각한 문제 발생 가능
• 낮은 순위의 스레드(T2)가 길어지면 더욱 심각한 문제 발생
  

우선순위 역전 해결책

우선순위 올림(priority ceiling)

• 스레드가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 미리 정해진 높 은 우선순위로 일시적으로 올림
• 선점되지 않고 빨리 실행되도록 유도

우선순위 상속(priority inheritance)

• 낮은 순위의 스레드가 공유 자원을 가지고 있는 동안,
• 높은 순위의 스레드가 공유 자원을 요청하면,
• 공유 자원을 가진 스레드의 우선순위를 요청한 스레드보다 높게 설정하여 빨리 실행시킴

생산자 소비자 문제

• 공유버퍼를 사이에 두고, 공유버퍼에 데이터를 공급하는 생산자들
• 공유버퍼에서 데이터 읽고 소비하는 소비자들
• 공유버퍼를 문제 없이 사용하도록 생산자와 소비자를 동기화시키는 문제
• 멀티스레딩 응용프로그램 작성 시 자주 발생

해결책
문제 1

• 상호 배제 해결: 뮤텍스나 세마포 사용
• 생산자들과 소비자들의 공유 버퍼에 대한 상호배제
  문제 2
• 비어있는공유버퍼문제(비어있는공유버퍼를소비자가읽을때)
  문제 3
• 꽉찬 공유버퍼 문제(꽉찬공유버퍼에생산자가쓸때

문제2: 비어 있는 버퍼 문제 해결

세마포 R활용(읽기 가능한 버퍼 개수):버퍼가 비어있는지 살피는 P/V연산으로 해결

문제3: 꽉 찬 공유 버퍼 문제 해결

세마포 W(쓰기가능한버퍼개수) 활용: 버퍼가 꽉 차있을때 처리하는 P/V연산으로 해결