[23-01/운영체제] 스레드 동기화
1. 스레드 동기화의 필요성
■ 다수의 스레드가 동시에 공유 데이터에 쓰기를 접근하면
- 공유 데이터가 훼손되는 문제 발생 가능
- 두 스레드가 동시에 공유 데이터 읽는 경우 -> 문제 없음
- 한 스레드는 쓰고 한 스레드는 읽을 경우 -> 읽고 쓰는 순서에 따라 읽는 값이 달라질 수 있지만 공유데이터의 훼손은 없음
- 두 스레드가 동시에 공유 데이터에 쓰는 경우 -> 공유 데이터 훼손 가능성
■ 스레드 동기화 (Thread Synchronization)
- 공유데이터에 대한 다수의 스레드가 동시에 접근할 때 공유데이터가 훼손되지 않게 하는 기법
- 한 스레드가 공유데이터를 배타적 독점적으로 접근하도록 순서화
공유 집계판에 동시 접근하는 사례
공유 집계판 문제를 프로그램으로 작성
■ 공유 집계판 사례의 코드 모델
- 두 학생 : 스레드 T1, T2
- 공유 집계판 : 공유 변수 sum
- 계산 식 : sum = sum + 10;
memo : sum 변수가 같이 사용됨
동기화 처리가 제대로 되지 않음
공유 데이터 접근 문제의 해결책
■ 문제점
- 여러 스레드가 공유 변수에 접근할 때, 공유 데이터 훼손
■ 해결책 - 스레드 동기화
- 한 스레드가 공유 데이터 사용을 마칠 때까지 다른 스레드가 공유 데이터에 접근하지 못하도록 제어
■ 멀티스레드의 경쟁 상황이 자주 발생하는가?
- 매우 자주 발생
- 사용자의 멀티스레드 프로그램에서 자주 발생
- 커널 코드에서 매우 자주 발생 (커널에 공유 데이터가 많기 때문)
- 다중 코어에서 더욱 조심
임계구역과 상호배제
- 스레드 동기화와 관련된 2가지 중요 개념 : 임계구역과 상호배제
■ 임계구역 (Critical Section) ★
- 공유 데이터에 접근하는 프로그램 코드들
■ 상호배제 (Mutual Exclusion) ★
- 임계구역을 오직 한 스레드만 배타적 독점적으로 사용하도록 하는 기술
- 임계구역에 먼저 진입한 스레드가 임계구역의 실행을 끝낼 때까지 다른 스레드가 진입하지 못하도록 보장
2. 상호배제 (Mutual Exclusion)
상호 배제를 포함하는 전형적인 프로그램 모습
1. 일반 코드 (non-critical code)
- 공유 데이터를 액세스하지 않는 코드
memo : 지역 변수
2. 임계구역 진입 코드 (entry code)
- 임계구역에 진입하기 전 필요한 코드 블록
- 현재 임계구역을 실행 중인 스레드가 있는지 검사
- 없다면, 다른 스레드가 들어오지 못하도록 조치 / 있다면, 진입이 가능해질 때까지 대기
3. 임계구역 코드 (critical code)
4. 임계구역 진출 코드 (exit code)
- 임계구역을 마칠 때 필요한 코드 블록
- 대기중인 스레드가 임계구역에 진입할 수 있도록 진입 코드에서 취한 조치 해제
상호배제 구현
■ 상호배제 구현 목표
- 임계구역에 오직 1개의 스레드만 진입
■ 상호배제 구현 방법
- 소프트웨어적 방법 - Peterson's 알고리즘 등
- 알고리즘 수준에서 제시된 것들로 구현 시 여러 문제 노출
- 하드웨어적 방법 - 하드웨어의 도움을 받는 방법
- 인터럽트 서비스 금지, 원자 명령 활용 등
- 오늘날 대부분 하드웨어적 방법 사용
■ 하드웨어적 방법
방법 1 - 인터럽트 서비스 금지
- 인터럽트 서비스를 금지하거나 허용하는 CPU 명령 사용
방법 2 - 원자 명령(atomic instruction) 사용 <- 보통 사용함
- 원자 명령은 CPU 명령임
- 오늘날 상호배제 구현에 사용하는 방법
상호배제구현 방법 1 - 인터럽트 서비스 금지
■ 인터럽트 서비스 금지 방법
- entry 코드에서 인터럽트 서비스를 금지하는 명령 실행
- 장치로부터 인터럽트가 발생해도, CPU가 인터럽트 발생을 무시
- 인터럽트가 발생해도 CPU는 인터럽트 서비스 루틴을 실행하지 않음
- 인터럽트를 무시하면 임계구역을 실행하는 스레드가 중단되지 않음
■ 문제점
- 모든 인터럽트가 무시되는 문제 발생
- 멀티 코어 CPU나 다중 CPU를 가진 시스템에서 활용 불가
- 한 CPU의 인터럽트 금지로 다른 CPU에게 인터럽트를 금지시킬 수 없음
- 다른 CPU가 타이머 인터럽트 서비스 루틴을 실행하여, 임계구역을 실행중인 스레드를 컨텍스트 스위칭시키고 다른 스레드를 스케줄할 수 있음
■ 동작 과정
■ 단순 lock 변수로 상호배제 시도
- locking / unlocking 방식으로 임계구역의 entry / exit 코드 작성하면 상호배제가 가능할까?
- lock 변수 : 1이면 잠금 상태
- lock 변수 : 0이면 열린 상태
● lock 변수를 사용한 상호배제가 성공하는 경우
● lock 변수를 사용한 상호배제의 근본 문제 보기 - 실패 사례
상호배제구현 방법 2 - 원자명령 (atomic instruction) 사용
■ lock 변수를 이용한 상호배제의 실패 원인?
- 실패 원인은 entry 코드에 있음
- lock 변수 값을 읽는 명령과 lock 변수에 1을 저장하는 2개의 명령 사이에 컨텍스트 스위칭이 될 때 문제 발생
■ 해결책 - 원자명령(atomic instruction) 도입 ★
- lock 변수를 읽어 들이는 명령과 lock변수에 1을 저장하는 2개의 명령을 한 번에 처리하는 원자명령 필요
- 원자명령 : TSL (Test Set Lock)
- Intel Pentium에서 시작, 현재 대부분의 CPU에 원자 명령 있음
■ 임계구역의 entry/exit 코드를 원자명령으로 재 작성
3. 멀티스레드 동기화 기법
멀티스레드 동기화
■ 멀티스레드 동기화란?
- 상호배제 기반 위에 자원을 사용하려는 여러 스레드들이 자원을 원활히 공유하도록 하는 기법
- 동기화 프리미티브(Synchronization Primitives)로 부름
■ 대표적인 기법
● locks 방식 : 뮤텍스 (Mutex), 스핀락 (Spinlock)
- 상호배제가 되도록 만들어진 락(lock) 활용
- 락을 소유한 스레드만이 임계구역 진입
- 락을 소유하지 않은 스레드는 락이 풀릴 때까지 대기
● wait-signal 방식 : 세마포어 (Semaphore)
- n개 자원을 사용하려는 m개 멀티스레드의 원활한 관리
- 자원을 소유하지 못한 스레드는 대기 (wait)
- 자원을 다 사용한 스레드는 알림(signal)
뮤텍스 (뮤텍스 기법)
■ 뮤텍스 (Mutex) 기법
- 잠김/열림 중 한 상태를 가지는 락 변수 이용
- 한 스레드만 임계구역에 진입시킴
- 다른 스레드는 큐에 대기 ★
- sleep-waiting lock 기법
■ 뮤텍스 기법의 구성 요소
1. 락 변수
- true/false 중 한 값
- true : 락을 잠금. 락을 소유함.
- false : 락을 엶. 락을 해제함
2. 대기 큐
- 락이 열리기를 기다리는 스레드 큐
3. 연산
- lock 연산 (임계구역의 entry 코드)
- 락이 열린 상태이면, 락을 잠그고 임계구역 진입
- 락이 잠김 상태(lock = true)이면, 현재 스레드를 블록 상태로 만들고 대기 큐에 삽입
- unlock 연산 (임계구역의 exit 코드)
- lock = false, 락을 열린 상태로 변경
- 대기 큐에서 기다리는 스레드 하나 깨움
■ 뮤텍스를 활용한 스레드 동기화 과정
■ 뮤텍스의 특징
● 뮤텍스를 이용한 동기화 특징 ★
- 임계구역의 실행 시간이 짧은 경우, 비효율적
- 락이 잠겨 있으면 (컨텍스트 스위칭되어) 대기 큐에서 대기, 락이 풀리면 다시 (★컨텍스트 스위칭되어) 실행
- 락이 잠겨있는 시간보다 스레드가 잠자고 깨는 데 걸리는 시간이 상대적으로 크면 비효율적
● 뮤텍스 동기화를 위한 POSIX 표준 라이브러리
- 뮤텍스락 변수 : pthread_mutex_t lock;
- 대기큐는 pthread 라이브러리 내부에 구현되어 있기 때문에 사용자에게 보이지 않음
- 뮤텍스 조작 함수들
- pthread_mutex_init() - 뮤텍스락 변수 초기화
- pthread_mutex_lock() - 뮤텍스락 잠그기
- pthread_mutex_unlock() - 뮤텍스락 풀기
- pthread_mutex_destroy() - 뮤텍스락 변수 사용 종료
● pthread를 이용한 뮤텍스 동기화 코딩 사례
스핀락 (스핀락 기법)
■ 스핀락(Spinlock) 기법
- busy-waiting lock 기법
- 스레드가 큐에서 대기하지 않고 락이 열릴 때까지 계속 락 변수 검사
- 뮤텍스와 거의 같고 busy-waiting이라는 점에서만 다름 ★ 대기큐 X
- 대기 큐 없음
- busy-waiting으로 인해 CPU를 계속 소모, CPU가 다른 스레드를 실행할 수 없음
- 락을 소유한 스레드만 자원 배타적 사용, 동기화 기법 컨텍스트 스위칭 X
- 공유 자원 하나 당 하나의 스핀락 사용
■ 스핀락 기법의 구성 요소
1. 락 변수
- true/false 중 한 값
- true : 락을 잠금. 락을 소유함
- false : 락을 엶. 락을 해제함.
2. 연산
- lock 연산
- 임계구역에 들어갈 때 실행되는 entry 코드
- 락이 잠김 상태면, 락이 풀릴 때까지 무한 루프 돌면서 lock 연산 시도
- 락이 열린 상태면, 락을 잠김 상태로 바꾸고 임계구역 실행
- unlock 연산
- 임계구역을 나올 때 실행하는 exit 코드
- 락을 열림 상태로 변경
■ 스핀락을 활용한 스레드 동기화 사례
memo : 락이 풀릴 때까지 락을 검사할 필요없이 큐에 넣으면 됮 않나? 싶음
하지만 이것 또한 장단점이 있음
■ 스핀락 특징
● 스핀락을 이용한 동기화 특징
- 뮤텍스의 non-blocking 모델 - 락이 잠겨 있을 때 블록되지 않고 락이 풀릴 때까지 검사하는 코드실행
- 단일 CPU(단일 코어)를 가진 운영체제에서 비효율적 ★
- 단일 코어 CPU에서 의미 없는 CPU 시간 낭비
- 멀티 코어에 적합
- 임계구역의 실행 시간이 짧은 경우 효과적
● 스핀락 동기화를 위한 POSIX 표준 라이브러리
- 스핀락 변수 : pthread_spinlock_t lock;
- 대기큐는 pthread 라이브러리 내부에 구현되어 있기 때문에 사용자에게 보이지 않음
- 스핀락 조작 함수들
- pthread_spin_init() - 스핀락 변수 초기화
- pthread_spin_lock() - 스핀락 잠그기
- pthread_spin_unlock() - 스핀락 풀기
- pthread_spin_destroy() - 스핀락 변수 사용 종료
● pthread를 이용한 스핀락 동기화 코딩 사례
뮤텍스와 스핀락은 어떤 경우에 적합한가?
- 락이 잠기는 시간이 긴(임계구역이 긴) 응용 : 뮤텍스
- 락을 얻지 못했을 때, CPU를 다른 스레드에게 양보하는 것이 효율적
- 락이 잠기는 시간이 짧은 경우 : 스핀락이 효율적
- 단일 CPU를 가진 시스템 : 뮤텍스
- 단일 CPU에서 스핀락은 크게 의미 없음
- 멀티 코어(멀티 CPU)를 가진 시스템 : 스핀락
- 임계구역은 보통 짧게 작성됨
- 잠자고 깨는 컨텍스트 스위칭 없이 바로 자원 사용
- 사용자 응용프로그램 : 뮤텍스 / 커널 코드 : 스핀락
- 커널 코드나 인터럽트 서비스 루틴은 빨리 실행되어야 함
- 인터럽트 서비스 루틴 내에서 잠잘 수 없기 때문
- 스핀락을 사용하면 기아 발생 가능
- 스핀락은 무한 경쟁 방식이어서 기아 발생 가능성
- 락을 소유한 스레드가 락을 풀지 않고 종료한 경우나 코딩이 잘못된 경우에도 기아 발생 가능
뮤텍스와 스핀락 비교 ★
| 뮤텍스 | 스핀락 | |
| 대기 큐 | 있음 | 없음 |
| 블록 가능 여부 | 락이 잠겨있으면 블록됨 (blocking) |
락이 잠겨있어도 블록되지 않고 계속 락 검사 (non-blocking) |
| lock / unlock 연산 비용 | 저비용 | CPU를 계속 사용하므로 고비용 |
| 하드웨어 관련 | 단일 CPU에서 적합 | 멀티코어 CPU에서 적합 |
| 주 사용처 | 사용자 응용 프로그램 | 커널 코드, 인터럽트 서비스 루틴 |
세마포어가 필요한 상황
세마포어
■ 세마포어(Semaphore) 정의
● 멀티스레드 사이의 자원 관리 기법
- n개의 공유 자원을 다수 스레드가 공유하여 사용하도록 돕는 자원 관리 기법 ★
- n개의 프린터가 있는 경우, 프린터를 사용하고자 하는 다수 스레드의 프린터 사용 관리
■ 구성 요소
1. 자원 : n개
2. 대기 큐 : 자원을 할당받지 못한 스레드들이 대기하는 큐
3. counter 변수
- 사용 가능한 자원의 개수를 나타내는 정수형 전역 변수
- n으로 초기화 (counter=n)
4. P/V 연산
- P연산(wait 연산) - 자원 요청 시 실행하는 연산
- 자원 사용 허가를 얻는 과정
- V 연산(signal 연산) - 자원 반환 시 실행하는 연산
- 자원 사용이 끝났음을 알리는 과정
세마포어를 이용한 멀티스레드 자원 관리의 구조
- 4개의 인스턴스를 가진 자원에 대해, 4개의 스레드(T1 ~ T4)가 할당 받아 사용
- 2개의 스레드 T5와 T6은 자원을 기다리고 있는 상태
- Counter 변수는 사용 가능한 자원의 개수를 나타내지만 음수이면 대기 중인 스레드의 수를 나타냄
P 연산과 V 연산
- 세마포어 종류 2가지 - sleep-wait 세마포어와 busy-wait 세마포어
- 자원을 할당받지 못한 경우의 행동에 따라 구분
■ sleep-wait 세마포어 ★
- P 연산 : counter--, 대기 큐에서 잠자기
- V 연산 : counter++, 사용가능 자원이 있으면 잠자는 스레드 깨우기
■ busy-wait 세마포어 ★
- P 연산 : 사용 가능 자원이 생길 때 까지 무한 루프 후 자원이 생기면 counter--
- V 연산 : counter++
세마포어 활용을 위한 POSIX 표준 라이브러리
■ 세마포 구조체
- 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)
- 여러 개의 자원을 관리하는 세마포어
■ 이진 세마포어 (Binary Semaphore)
- 한 개의 자원을 관리하는 세마포어
- 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)
- 스레드의 동기화로 인해 높은 순위의 스레드가 낮은 스레드보다 늦게 스케줄링되는 현상
- 우선순위를 기반으로 스케줄링하는 실시간 시스템에서 스레드 동기화로 인해 발생
■ 우선 순위 역전의 문제점
- 실시간 시스템의 근본 붕괴
- 우선순위가 높다는 것은 중요한 일을 할 가능성이 높음 -> 늦게 실행되면 심각한 문제 발생 가능
- 낮은 순위의 스레드가 길어지면 더욱 심각한 문제 발생
■ 우선순위 역전 해결책
● 우선순위 올림 (Priority Ceiling)
- 스레드가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 미리 정해진 높은 우선순위로 일시적으로 올림
- 선점되지 않고 빨리 실행되도록 유도 -> 예측
● 우선순위 상속 (Priority Inheritance)
- 낮은 순위의 스레드가 공유 자원을 가지고 있는 동안,
- 높은 순위의 스레드가 공유 자원을 요청하면,
- 공유 자원을 가진 스레드의 우선순위를 요청한 스레드보다 높게 설정하여 빨리 실행시킴
4. 생산자 소비자 문제
생산자 소비자 문제의 정의
■ 생산자 소비자 문제란?
- 공유버퍼를 문제 없이 사용하도록 생산자와 소비자를 동기화시키는 문제
( 생산자 : 공유버퍼에 데이터를 공급 / 소비자 : 공유버퍼의 데이터를 읽고 소비함)
■ 생산자 소비자 문제의 구체적인 3가지 문제
- 상호 배제 해결 (생산자와 소비자들의 공유 버퍼에 대한 상호배제)
- 비어있는 공유 버퍼 문제 (비어 있는 공유버퍼를 소비자가 읽을 때)
- 꽉 찬 공유버퍼 문제 (꽉 찬 공유버퍼에 생산자가 쓸 때)
2. 비어있는 공유 버퍼 문제 해결
- 세마포어 R 활용(읽기 가능한 버퍼 개수) : 버퍼가 비어있는지 살피는 P/V 연산으로 해결
3. 꽉 찬 공유 버퍼 문제 해결
- 세마포어 W(쓰기 가능한 버퍼 개수) 활용 : 버퍼가 꽉 차 있을 때 처리하는 P/V 연산으로 해결
