1 스레드 동기화의 필요성
공유 데이터에 대한 다수 스레드의 동시 접근을 해결하는 방법이 스레드 동기화(thread synchronization)
1.1 공유 집계판 문제
공유 데이터에 대한 멀티스레드의 접근 문제 스레드 동기화(thread synchronization): 다수의 스레드가 공유 데이터를 동시에 접근하는 충돌 상황에서 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 기법이다.
1.2 공유 데이터 액세스 문제와 해결방법
공유 데이터에 대한 멀티스레드의 동시 접근 문제의 원인 분석
sum = sum + 10의 C 코드는 다음 3개의 기계 명령들로 번역된다.
mov ax, sum
add as, 10
mov sum, ax
이때 T1과 T2 스레드에 의해 동시에 실행되는 문제가 발생 할 수 있다.
- T1이 sum 변수 값을 읽은 후 중단
- T2가 실행되어 sum 변수에 60 기록
- T1이 다시 실행되어 sum 변수에 60 기록 - 잘못된 결과 발생! 이 문제의 원인은 C 언어의 한 줄짜리 코드가 하나의 CPU 명령이 아니라는 점과, 그래서 한 스레드가 실행을 완전히 마칠 때까지 다른 스레드가 이 코드를 실행하는 것을 막지 못했다는 것
공유 데이터에 대한 동시 접근 문제의 해결책
문제점: 여러 스레드가 공유 데이터에 동시 접근할 때 공유 데이터가 훼손될 수 있다.
해결책: 스레드 동기화, 한 스레드가 공유 데이터에 대한 접근을 마칠 때까지 다른 스레드가 접근하지 못하도록 제어한다.
1.3 임계구역과 상호배제
임계구역(critical section): 사용자가 작성한 프로그램 중 공유 데이터에 접근하는 코드 블록 상호배제(mutual exclusion): 다수의 스레드로부터 공유 데이터의 훼손을 막기 위해, 임계구역은 반드시 한 스레드만 배타적 독점적으로 실행하도록 관리하는 기법?
2 상호배제
2.1 상호배제 위치
- 일반 코드(non-critical code) 공유 데이터를 액세스하지 않는 코드 부분
- 임계구역 진입코드(entry code) 임계구역에 진입하기 전 필요한 코드 블록, 현재 임계구역을 이미 실행 중인 스레드가 있는지 검사하고, 없는 경우 다른 스레드가 들어오지 못하도록 조치를 취한다. 이미 진입한 스레드가 있다면 진입한 스레드가 exit 코드를 실행할 때까지 현재 스레드를 대기시킨다.
- 임계구역 진출코드(exit code) 스레드가 임계구역 실행을 마칠 때 실행되어야 하는 코드 블록, entry 코드에서 대기 중인 스레드가 임계구역에 진입할 수 있도록 entry 코드에서 취한 조치를 해제한다.
- 임계구역 코드(critical code) 공유 데이터에 접근하는 코드 블록, 한 번에 한 스레드만 실행하도록 보장되어야 하는 부분, 짧을수록 좋기 때문에, 공유 데이터를 액세스하는 최소한의 코드를 입계구역으로 만드는 것이 바람집하다.
2.2 상호배제 구현
상호배제 방법은 크게 소프트웨어적 방법과 하드웨어적 방법으로 나눈다. 소프트웨어적 방법은 실제 구현에 있어 여러 문제를 노출하기 때분에, 오늘날에는 원자명령(하드웨어적 방법)을 활용하는 방법 사용. 임계구역의 상호배제는 임계구역의 entry 코드와 exit 코드를 어떻게 구현하느냐가 관건
다른 방법들?
2.3 방법 1 - 인터럽트 서비스 금지
임계구역으로 진입할 때 entry 코드에서 인터럽트 서비스를 금지하고 exit 코드에서 인터럽트 서비스를 허용하는 CPU 명령들을 실행하는 방법
인터럽트 서비스 금지
2가지 문제점
- 임계구역을 실행하는 동안 모든 인터럽트가 무시됨, 임계구역의 실행 시간이 길어지게 되면 중요한 ISR이 제때 실행되지 못할 수 있다.
- 단일 CPU 시스템에서는 활용 가능하지만, 멀티코어를 비록한 다중 CPU를 가진 시스템에서는 활용 불가, 다른 코어의 ISR까지 금지시키지는 못하기 때문
왜 다른 코어의 ISR을 금지시키지 못하는가?
2.4 방법 2 - 원자명령(atomic instruction) 사용
원자명령(atomic instruction): 상호배제를 위해 만들어진 CPU 명령이며, CPU마다 명령이 서로 다르지만 통일하여 원자명령이라고 부른다.
원자명령 없이 lock 변수를 이용한 상호배제 시도
lock 변수를 이용한 상호배제의 근본적인 문제
2.5 원자명령을 이용한 상호배제
lock 변수를 사용한 경우 상호배제가 실패한 원인
lock 변수 값을 읽어 들이는 명령과 lock 변수를 1로 바꾸는 명령 사이에 컨텍스트 스위칭이 발생할 때 문제가 발생
해결 방법 - 원자명령 도입
lock 값을 읽어 들이는 명령과 lock 변수에 1을 저장하는 명령 사이에 컨텍스트 스위칭이 일어나지 않도록 이 두 명령을 하나의 명령으로 만드는 것. 이 멸령을 원자명령(atomic instruction) 혹은 TSL(Test and Set Lock) 명령이라고 부른다.
t1 이 tsl을 실행해서 lock 변수가 1일때 인터럽트가 계속 들어오면 어떻게 되는가? 발생할 수 있는 문제점은?
- Busy Waiting
- Priority Inversion
- Deadlock https://www.slideshare.net/slideshow/ndc12-2/12746882
3 멀티스레드 동기화 기법
- 락(lock) 방식 - 하나의 락 변수를 두고, 락을 잠근 스레드만이 입계구역에 진입하도록 하는 기법
- ex) 뮤텍스(mutex), 스핀락(spinlock)
- wait-signal 방식 - 여러 개의 공유 자원을 여러 스레드가 사용할 수 있도록 관리하는 기법
- ex) 세마포(semaphore)
3.1 뮤텍스
- 변수 - 락 변수(locked/unlocked)
- 연산 - lock/unlock 연산
- 큐 - 대기 큐(wait queue)
뮤텍스의 특징
임계구역의 실행 시간이 짧은 경우 뮤텍스는 비효율적이다. 락이 잠겨 있는 시간보다 컨텍스트 스위칭 시간이 더 크기 때문
pthread 라이브러리의 뮤텍스
- 뮤텍스락 변수 - pthread_mutex_t lock;
- 뮤텍스 조작 함수들
- pthread_mutex_init() - 뮤텍스락 변수 초기화
- pthread_mutex_lock() - 뮤텍스락 잠그기
- pthread_mutex_unlock() - 뮤텍스락 풀기
- pthread_mutex_destroy() - 뮤텍스락 변수 사용 종료
pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL)
pthread_mutex_lock(&lock)
... 임계구역코드 ...
pthread_mutex_unlock(&lock)
3.2 스핀락(spinlock)
대기 큐가 없음
- 변수 - 락 변수
- 연산 - lock/unlock 연산
스핀락의 특징
- 뮤텍스 기법의 바쁜 대기(busy-waiting) 모형이다. lock 연산에서 락이 잠겨 있을 때 블록되지 않고 락이 열릴 때까지 락을 검사하는 코드를 실행하기 때문
- 단일 CPU 운영체제에서 매우 비효율적이다. 다른 스레드에 의해 잠겨있는 경우 lock을 검사하는 코드를 실행하기 때문에 타임 슬라이스 내내 의미 없는 검사에 CPU를 사용하는 것, 이와 대조적으로, 멀티 코어 CPU 의 경우, 락을 경쟁하는 스레드들을 서로 다른 코어에서 실행시키면 상당히 효과적이다.
- 임계구역 코드가 짧아서 락이 빨리 열리는 응용에 매우 효과적이다. 컨텍스트 스위칭과 스케줄링이 필요 없기때문
- 기아가 발생할 수 있다. 또한 락을 잠근 스레드가 unlock 하기 전 종료하거나 무한 루프를 도는 경우, 락이 열리기를 기다리는 다른 스레드들은 무한정 CPU를 사용하면서 영원히 기다릴 수도 있다.
linux 커널은 스핀락을 사용한다. https://docs.kernel.org/locking/spinlocks.html
pthread 라이브러리의 스핀락
- 스핀락 변수 - pthread_spinlock_t lock;
- 스핀락 조작 함수들
- pthread_spinlock_init() - 스핀락 변수 초기화
- pthread_spinlock_lock() - 스핀락 잠그기
- pthread_spinlock_unlock() - 스핀락 풀기
- pthread_spinlock_destroy() - 스핀락 변수 사용 종료
pthread_spinlock_t lock;
pthread_spinlock_init(&lock, NULL)
pthread_spinlock_lock(&lock)
... 임계구역코드 ...
pthread_spinlock_unlock(&lock)
하이브리드 뮤텍스(hybrid mutex)란?
스핀락과 뮤텍스를 혼합한 동기화 방식으로 오늘날 커널에서 많이 사용
처음에는 스핀락처럼 동작하다가 일정 시간이 지날 때까지 락을 획득하지 못하면 뮤텍스처럼 작동하여 스레드를 블록 상태로 만들어 대기 큐에 넣고 락이 풀릴 때까지 대기시킨다.
The glibc already provides this. Just use the PTHREAD_MUTEX_ADAPTIVE_NP type or use PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP as the mutex initializer.
| 뮤텍스 | 스핀락 | |
|---|---|---|
| 대기 큐 | 있음 | 없음 |
| 블록 가능 여부 | blocking | non-blocking |
| lock/unlock 연산 비용 | 저비용 | 고비용 |
| 하드웨어 관련 | 단일 CPU | 멀티코어 CPU |
| 주 사용처 | 사용자 응용 프로그램 | 커널 코드, ISR |
3.3 세마포(Semaphore)
세마포 개념
세마포는 n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원 관리 기법이다.
- 자원 - n개
- 대기 큐 - 자원을 할당받지 못한 스레드가 잠자는 곳
- counter 변수 - 사용가능한 자원의 개수를 나타내는 정수형 변수로 자원의 개수 n으로 초기화된다. 음수이면 자원을 기다리는 스레드의 개수를 나타낸다.
- P/V 연산 - P 연산은 자원 요청시, V 연산은 자원 반환 시 실행되는 연산
P 연산과 V 연산
P/V 연산은 wait/signal 연산으로도 불린다. P 연산은 스레드에게 자원 사용을 허가하는 과정, counter 1 감소 V 연산은 스레드가 자원 사용이 끝났음을 세마포에게 알리는 과정, counter 1 증가 세마포는 자원을 할당받지 못하는 스레드를 다루는 방법에 따라 다음 2가지 종류로 나뉘며 P/V 연산이 다르게 작동한다.
- 수면 대기(sleep-wait) 세마포
- 대기 큐 이용
- 바쁜 대기(busy-wating) 세마포
- 무한 루프
P/V 연산과 원자명령 counter 변수는 P, V 연산에 의해 공유되는 변수이므로 counter에 대한 접근은 원자적으로 처리되도록 구현, P, V 연산은 원자적으로 수행
pthread 라이브러리의 세마포
- 세마포 구조체 - sem_t s; // counter 변수 등을 가진 구조체
- 세마포 조작 함수들
- sem_init() - 세마포 구조체 초기화. counter 변수를 자원의 개수로 초기화
- sem_destroy() - 세마포 기능 소멸
- sem_wait() - P 연산 수행. 대기 큐 사용
- sem_trywait() - P 연산 수행. 무한 루프로 사용
- sem_post() - V 연산 수행
- sem_getvalue() - 세마포의 현재 counter 값 리턴
sem_t sem;
sem_wait(&esm); or while(sem_trywait(&sem));
... 할당받은 자원 활용 ...
sem_post(&sem);
3.4 이진 세마포
- 카운터 세마포(counter semaphore) - 자원이 여러 개인 경우
- 이진 세마포(binary semaphore) - 자원이 1개인 경우
- 세바포 변수 S - 0과 1 중 하나를 가지는 변수. 1로 초기화됨
- 대기 큐 - 자원이 사용가능하게 될 때까지 스레드들이 대기하는 큐
- P 연산 - 자원 사용의 허가를 얻는 과정으로 S를 1감소시키고 0보가 작으면 스레드를 대기 큐에서 잠들게 한다. 만일 S가 0보다 크거나 같으면 스레드는 자원을 사용하는 코드를 실행한다.
- V 연산 - 자원 사용이 끝났음을 알리는 과정으로, S를 1 증가시키고 0보다 크면 그냥 리턴하고, 0보다 작거나 같으면 대기 큐에 있는 스레드 중 하나를 깨운다. 이진 세마포는 하나의 자원에 대해 여러 스레드가 사용하고자 할 때 관리하는 기법, 뮤텍스와 매우 유사
3.5 동기화 이슈: 우선순위 역전
우선순위 역전
스레드 동기화로 인해 우선순위 역전(priority inversion)이 발샐할 수 있다.
- T1과 T3은 자원을 공유
우선순위 역전의 해결책
- 우선순위 올림(priority ceiling) 공유자원을 소유하게 될 때 우선순위를 일시적으로 미리 정해진 우선순위로 높이는 방법. 이 우선순위는 공유 자원을 액세스할 어떤 스레드 보다 더 높게 책정된다. → 공유 자원을 소유한 스레드는 다른 스레드에 의해 선점되지 않고 빨리 실행된다. 공유 자원에 대한 액세스가 끝나면 원래 우선순위로 되돌린다.
- 우선순위 상속(priority inheritance) 스레드가 공유 자원을 획득하고 실행하는 동안 높은 순위의 스레드가 공유 자원을 요청하면, 낮은 순위의 스레드 우선순위를 요청한 스레드보다 높게 변경하여 계속 실행시키고 공유 자원에 대한 사용이 끝날 때 원래 순위로 되돌린다.
linux: 우선순위 상속 windows: random?
4 생산자 소비자 문제
4.1 응용프로그램에 존재하는 생산자 소비자 문제 사례
- 입력스레드와 재생스레드가 비디오 버퍼를 동시에 접근하는 경우의 상호배제
- 재생스레드가 읽으려고 했을 때 비디오 버퍼가 비어있는 문제 - 네트워크의 지연 등으로 입력스레드에 의한 프레임 공급이 늦어지고 있는 상황
- 입력스레드가 쓰려고 했을 때 비디오 버퍼가 꽉 찬 문제 - 재생스레드가 비디오 버퍼를 비워내는 속도보다 더 빠르게 입력스레드에 의해 프레임이 채워지는 경우
4.2 생산자 소비자 문제의 정의
생산자 소비자 문제는, 공유버퍼에 데이터를 공급하는 생산자들과 공유버퍼에서 데이터 읽고 소비하는 소비자들이 공유버퍼를 문제없이 사용하도록 생산자와 소비자를 동기화시키는(실행 순서를 제어하는) 문제이다.
다음 3가지 문제
- 상호배제(생산자들과 소비자들의 공유버퍼 사용에 대한 상호배제)
- 비어 있는 공유버퍼 문제(비어 있는 공유버퍼를 소비자가 읽을 때)
- 꽉 찬 공유버퍼 문제(꽉 찬 공유버퍼에 생산자가 쓸 때)
4.3 생산자 소비자 문제의 해결책
상호배제 해결
임계구역에 대한 상호배제는 뮤텍스나 세마포를 이용하여 작성
비어있는 공유버퍼 문제 해결
소비자 스레드는 대기, 생산자 스레드는 대기상태에서 깨어나도록 알리는 방식, 스레드 동기화를 위해 세마포가 적당. 세마포 R을 만들고 세바포 R에 대한 P 연산은 소비자 스레드가, V 연산은 생산자 스레드가 실행하도록 설계
꽉 찬 공유버퍼 문제 해결
세마포 W를 만든다. 세마포 W의 counter 값은 쓰기 가능한 버퍼의 개수를 나타내며 버퍼가 꽉차있는 경우 counter 값은 0이다.
생산자와 소비자 알고리즘
위 두 그림에서 본 바와 같이 생산자와 소비자를 구현하기 위해서는 2개의 카운팅 세마포가 필요하며 counter의 최댓값은 공유버퍼의 개수이다.
- 세마포 R: 읽기 가능한 버퍼의 개수를 나타내며 0이면(비어있는 경우) 대기
- 세마포 W: 쓰기 가능하느버퍼의 개수를 나타내며 0이면(꽉 차있는 경우) 대기
- 뮤텍스 M: 생산자 소비자 두 스레드에 의해 사용
Consumer {
while(true) {
P(R);
M lock
공유버퍼에서 데이터 읽기
M open
V(W);
}
}
Producer {
while(true) {
P(W);
M lock
공유버퍼에 데이터 저장
M open
V(R);
}
}
질문
- 뮤텍스 vs 이진 세마포 뭐가 더 좋고 많이 쓸까?
- 그래서 위 4가지 동기화 기법중 가장 많이 쓰는 것은 무엇이고 이유가 뭐냐?
- 리눅스에서 스핀락을 사용한다고 했는데 기아는 어떻게 해결하나?
Ref.
황기태, “명품 운영체제”, (주)생튼출판사(2021)