1. 스레드 동기화의 필요성
공유 데이터에 대한 다수 스레드의 동시 접근을 해결하는 방법 → 스레드 동기화
1.1 공유 집계판 문제
스레드 동기화(thread synchronization)
다수의 스레드가 공유 데이터를 동시에 접근하는 충돌 상황에서 공유 데이터가 훼손되지 않도록 스레드의 실행을 제어하는 기법
1.2 공유 데이터 액세스 문제와 해결방법
공유 데이터에 대한 멀티스레드의 동시 접근 문제의 원인 분석
- 스레드 T1, T2
- 공유변수 sum
- sum = sum + 10
mov ax, sum - sum 변수 값을 읽어 ax 레지스터에 저장
add ax, 10 - ax 레지스터의 값을 10 증가
mov sum, ax - ax 레지스터 값을 sum 변수에 저장
문제 원인
- sum = sum + 10 이 하나의 cpu 명령이 아님 → 한 스레드가 실행을 완전히 마칠 때까지 다른 스레드가 이 코드를 실행하는것을 막지 못함
공유 데이터에 대한 동시 접근 문제의 해결책
문제점 : 여러 스레드가 공유 데이터에 동시 접근할 때 공유 데이터가 훼손될 수 있다 해결책 : 스레드 동기화(한 스레드가 공유 데이터에 접근을 마칠때까지 다른 스레드 접근 제어)
1.3 임계구역과 상호배체
임계구역 : 사용자가 작성한 프로그램 중 공유데이터에 접근하는 코드블록 상호배제 : 공유 데이터 훼손 방지를 위해 한 스레드만 배타적, 독점적으로 실행하도록 관리하는 것
2. 상호배제
2.1 상호배제 위치
- 일반코드(non-critical 코드) : 멀티스레드 응용프로그램에서 공유 데이터를 액세스하지 않는 코드 부분
- 임계구역 진입코드(entry 코드) : 임계구역 진입 전 필요한 코드블록, 현재 임계구역을 이미 실행중인 스레드가 있는지 검사하고 없는 경우 다른 스레드가 들어오지 못하도록 조치를 취함. 이미 진입한 스레드가 있다면 진입한 스레드가 임계구역 실행을 끝내고 exit 코드를 실행할 때까지 현재 스레드 대기시킴
- 임계구역 진출코드(exit 코드) : 스레드가 임계구역 실행을 마칠 때 실행되어어야 하는 코드 블록, entry 코드에서 대기 중인 스레드가 임계구역에 진입할 수 있도록 entry 코드에서 취한 조치 해제
- 임계구역 코드(critical 코드) : 공유 데이터에 접근하는 코드 블록, 한 번에 한 스레드만 실행하도록 보장되어야 하는 프로그램 부분
2.2 상호배제 구현
- 소프트웨어적 방법 - Peterson’s 알고리즘
- 하드웨어적 방법 - 인터럽트 서비스 금지, 원자명령 활용
2.3 방법 1 - 인터럽트 서비스 금지
임계구역으로 진입할 때 entry 코드에서 인터럽트 서비스를 금지하고 exit코드에서 인터럽트 서비스를 허용하는 CPU 명령들을 실행하는 방법
cli - entry 코드, 인터럽트 서비스 금지 명령
.....
임계구역 코드
...
sti - exit 코드, 인터럽트 서비스 허용 명령
cli 명령 : cpu 내부 인터럽트 플래그를 0으로 리셋시켜 인터럽트가 발생해도 무시하고 현재 작업 계속 수행 sti 명령 : cpu 인터럽트 플래그를 1로 설정하여 인터럽트가 발생하면 cpu가 하던 일을 멈추고 인터럽트 서비스 루틴 실행
문제점
- 임계구역 실행 중 모든 인터럽트가 무시됨 : 중요한 인터럽트 서비스 루틴이 제때 실행되지 못할 수 있음
- 인터럽트 서비스를 금지하는 방법은 단일 cpu 시스템에서는 활용 가능하지만, 멀티코어를 비롯한 다중 cpu를 가진 시스템에서는 활용 불가능 : 다른 코어 인터럽트 서비스까지 금지시키지는 못함(다른 코어의 스레드가 임계구역에 들어오는것을 막지 못함)
2.4 방법 2 - 원자명령(atomic instruction) 사용
상호배제를 위해 만들어진 cpu 명령
원자명령 없이 lock 변수를 이용한 상호배제 시도
0이나 1의 값을 가지는 lock 변수를 두고 임계구역에 들어갈 때 lock에 1을 쓰고 나올 때 0으로 변경하여 lock이 0인 경우에만 임계구역에 들어갈 수 있도록 하는 방법
lock 변수를 이용한 상호배제의 근본적인 문제
2.5 원자명령을 이용한 상호배제
lock 변수를 사용한 경우 상호배제가 실패한 원인
lock 변수 값을 읽어 들이는 명령과 lock 변수를 1로 바꾸는 명령 사이에 컨텍스트 스위칭이 발생할 때 문제 발생 lock변수값을 cpu 레지스터에 읽어놓는 명령과 lock 변수를 1로 바꾸는 명령이 하나의 단위로 실행되지 않는 것
해결방법 - 원자명령 도입
원자명령(atomic instruction) / TLS
- lock 값을 읽어 들이는 명령과 lock 변수에 1을 저장하는 명령 사이에 컨텍스트 스위칭이 일어나지 않도록 두 명령을 하나의 명령으로 만드는 것
3. 멀티스레드 동기화 기법
멀티스레드 동기화 - 여러 스레드들이 문제없이 공유 자원을 활용하도록 돕는 방법
- 락 방식 - 뮤텍스(mutex), 스핀락(spinlock)
- 락 변수를 두고 락을 잠근 스레드만이 임계구역에 진입하도록 하는 기법
- wait-single 방식 - 세마포(semaphore)
- 여러개의 공유 자원을 여러 스레드가 사용할 수 있도록 관리하는 기법
3.1 뮤텍스
락 변수(잠김/열림)를 이용하여 한 스레드만 임계구역에 진입시키고 다른 스레드들을 큐에 대기시키는 기법
- 변수 - 락 변수
- 연산 - lock/unlock 연산
- 큐 - 대기 큐(wait queue)
락 변수
락 변수를 잠김으로 만든 스레드만이 임계구역 실행 가능
lock / unlock 연산
lock 연산
- 스레드가 임계구역에 들어가기 전 실행하는 entry 코드
- 락이 잠겨있으면 현재 스레드를 블록 상태로 만들어 대기 큐에 삽입
- 열린 상태면 락을 잠구고 임계구역으로 진입
unlock 연산
- 임계구역을 나올 때 실행하는 exit 코드
- 락을 열림 상태로 바꾸고 대기 큐에 있는 스레드 하나를 깨워 준비상태로 만듬
뮤텍스 : 락이 잠겨있는 경우 락이 풀릴 때까지 스레드가 블록 상태로 대기큐에서 잠을 자기때문에 블록킹 락(blocking lock)이나 수면 대기 락(sleep-waiting lock) 이라고 함
뮤텍스를 활용한 스레드 동기화 과정
- T1 스레드가 lock연산을 실행하여 락을 잠구고 임계구역 실행
- T1이 임계구역을 실행하는 도중 T2가 실행되어 lock 연산 실행, 락이 잠겨있어 T2를 중단시키고 대기큐에 삽입
- T1이 실행을 마치고 Unlock 연산 실행, 락을 열림상태로 바꾸고 대기큐에서 잠든 스레드를 하나 깨워 준비리스트에 넣음
- T2는 준비 리스트에 있다가 스케줄되면 중단된 lock 연산에서 실행을 계속 하여 락이 잠겨있는지 검사하고 락을 잠근 후 임계구역으로 진입
뮤텍스의 특징
- 임계구역의 실행 시간이 짧은경우에는 비효율적
- 락이 잠겨있는 실행보다 스레드가 잠자고 깨는데 걸리는 시간낭비가 더 크기때문에 비효율적
pthread 라이브러리의 뮤텍스
- 뮤텍스 락 변수 - pthread_mutex_t lock;
- 뮤텍스 조작 함수
- pthread_mutex_init() - 뮤텍스락 변수 초기화
- phtread_mutex_lock() - 뮤텍스락 잠그기
- phtread_mutex_unlock() - 뮤텍스락 풀기
- phtread_mutex_destroy() - 뮤텍스락 변수 사용 종료
phtread_mutex_t lock; // 뮤텍스락 변수 생성
phtread_mutex_init(&lock, NULL); // 뮤텍스락 변수 초기화
phtread_mutex_lock(&lock); // 임계구역 entry 코드, 뮤텍스락 잠그기
--- 임계구역 코드 ---
phtread_mutex_unlock(&lock); // 임계구역 exit 코드, 뮤텍스락 열기
3.2 스핀락(spinlock)
- 변수 - 락 변수
- 연산 - lock/unlock 연산
락을 기반으로 하지만 대기큐가 없음
락 변수
스핀락을 소유한 한 개의 스레드만 임계구역에 진입 가능
lock/unlock 연산
lock 연산
- 스레드가 임계구역에 들어가기 전 실행하는 entry코드
- 락 변수가 열림 상태이면 잠김 상태로 만들고 스레드가 임계구역에 들어가게 함
- 잠겨있다면 열릴때가지 락 검사를 무한 반복하고 열리면 즉각 락을 잠그고 스레드가 임계구역에 들어가게 함
unlock 연산
- 락을 열림으로 변경
- 락이 잠겨있으면 무한 루프를 돌면서 락이 풀릴 때까지 검사
- 타임 슬라이스가 소진될 때 스레드는 컨텍스트 스위칭되고 다시 스케줄되면 다시 검사 반복
- 공격적인 뮤텍스(aggressive mutex), 바쁜 대기 락(busy-waiting lock)
스핀락을 활용한 스레드 동기화 사례
- T1 스레드가 lock 연산을 수행하여 락을 잠그고 임계구역 실행
- T1이 임계구역을 실행하는 중 T2가 스케줄되어 lock 연산 실행, lock 연산은 열림 상태가 될 때까지 반복하여 락을 검사하는 CPU 명령 실행
- T1이 임계구역의 실행을 마치고 unlock 연산 실행, unlock 연산으로 락을 열림 상태로 만듬
- T2는 반복된 락 검사중 열림 상태를 확인하고 락을 잠그고 임계구역으로 진입
스핀락의 특징
- 스핀락 기법은 뮤텍스 기법의 바쁜 대기 모형
- 단일 cpu를 가진 운영체제에서 스핀락은 매우 비효율적, 멀티코어 cpu의 경우 락을 경쟁하는 스레드들을 서로 다른 코어에서 실행시키면 효과적
- 임계구역 코드가 짧아 락이 빨리 열리는 응용에 효과적
- 스레드들이 락을 얻기 위해 무한경쟁하기 때문에 어떤 스레드는 기아가 발생할 수 있음, 락을 열어놓지 않고 종료하거나 무한루프를 도는 경우 다른 스레드들은 무한정으로 cpu를 사용하고 영원히 기다릴 수 있음
pthread 라이브러리 스핀락
- 스핀락 변수 - pthread_spinlock_t lock;
- 스핀락 조작 함수들
- pthread_spin_init() - 스핀락 변수 초기화
- pthread_spin_lock() - 스핀락 잠그기
- pthread_spin_unlock() - 스핀락 풀기
- pthread_spin_destroy() - 스핀락 변수 사용 종료
pthread_spinlock_t lock; // 스핀락 변수 lock 생성
pthread_spin_init(&lock, NULL) // 스핀락 변수 초기화
pthread_spinlock_lock(&lock); // 임계구역 entry 코드, 스핀락 잠그기
--- 임계구역 코드 ---
pthread_spinlock_unlock(&lock); // 임계구역 exit 코드, 스핀락 열기
뮤텍스와 스핀락은 어떤 상황에 적합할까?
- 락이 잠기는 시간이 긴 경우 - 뮤텍스
- 단일 cpu를 가진 시스템 - 뮤텍스
- 멀티코어를 가진 시스템 - 스핀락
- 뮤텍스는 사용자 응용 프로그램에서, 스핀락은 커널코드나 인터럽트 서비스루틴에서 주로 사용
/ 뮤텍스 스핀락 대기 큐 있음 없음 블록 가능 여부 락이 잠겨있으면 블록 락이 잠겨있어도 계속 락 검사 lock/unlock 연산 비용 저비용 cpu를 계속 사용하므로 고비용 하드웨어 관련 단일 cpu 멀티코어 cpu 주 사용처 사용자 응용 프로그램 커널 코드, 인터럽트 서비스 루틴
3.3 세마포(semaphore)
세마포는 n개의 자원을 다수의 스레드가 공유하여 사용하도록 돕는 자원관리 기법
세마포가 필요한 상황
- n개의 자원이 있는 상황에서 멀티스레드가 자원을 사용하려고 하는데 자원이 모두 동날때 자원을 사용하려는 스레드는 기다려야하고 자원을 다 사용한 스레든느 이를 알려 대기중인 스레드가 자원을 사용할 수 있도록 관리하는 주체가 필요함 ⇒ 세마포
자원의 개수를 알고, 스레드의 요청을 받아 사용을 허락하고, 자원이 모자랄 때 요청한 스레드는 대기큐에서 잠을 재우며, 자원 사용을 끝낸 스레드가 세마포에게 알리면 세마포가 대기큐에서 잠을 자는 스레드를 깨워 자원을 사용하도록 허락하는 방식
- 자원
- 대기 큐 - 자원을 할당받지 못한 스레드가 잠자는 곳
- counter 변수 - 사용가능한 자원의 개수를 나타내는 정수형 변수로 자원의 개수 n으로 초기화
- P/V 연산 - P 연산 : 자원 요청 시, V 연산 : 자원 반환 시
T1~T4 스레드는 하나씩 자원을 할당받아 사용
T5와 T6은 사용가능한 자원이 생기기를 기다리고 있는 상태
n개의 자원이 있고 여러 스레드들이 자원을 사용하고자 할 때 원활하게 관리하는것이 목적
P연산과 V연산
P연산(wait 연산)
- 스레드에게 자원 사용을 허가하는 과정
- counter 변수 1 감소
- 자원을 얻을 때까지 대기(wait)
V연산(single 연산)
- 스레드가 자원 사용이 끝났음을 세마포에게 알리는 과정
- counter 변수 1 증가
- 자원 사용을 끝낸 스레드는 대기하는 스레드에게 알림(single)
수면 대기(sleep-wait) 세마포
- P 연산중 자원 사용을 허가받지 못한 스레드를 대기 큐에서 잠을 깨움
- V 연산에서 사용 가능한 자원이 생기면 스레드를 깨워 자원 사용을 허락 바쁜 대기(busy-waiting) 세마포
- P 연산에서 가용 자원이 생길 때까지 무한 루프를 돌면서 검사
- V 연산에 의해 가용 자원이 생기면 P연산에서 자원 획득
- 대기큐가 없음
pthread 라이브러리 세마포
sem_t sem; 세마포 구조체 생성
sem_wait(&sem); // P연산, 자원사용 요청
--- 할당받은 자원 활용 ---
sem_post(&sem); V 연산, 자원사용 끝
3.4 이진 세마포
- 카운터 세마포(counter semaphore) - 자원이 여러개인 경우
- 이진 세마포(binary semaphore) - 자원이 1개인 경우
이진 세마포 구성 요소
- 세마포 변수 S - 0과 1 중 하나를 가지는 변수, 1로 초기화
- 대기 큐 - 자원이 사용 가능하게 될 때까지 스레드들이 대기하는 큐
- P 연산 - 자원 사용의 허가를 얻는 과정
- V 연산 - 자원 사용이 끝났음을 알리는 과정
하나의 자원에 대해 여러 스레드가 사용하고자 할 때 관리하는 기법 (뮤텍스와 유사)
3.5 동기화 이슈 : 우선순위 역전
우선순위 역전(priority inversion)
스레드 동기화로 인해 우선순위 높은 스레드가 낮은 스레드보다 늦게 실행되는 경우
- T1과 T3는 자원 공유, T2는 공유하지 않음
해결책
우선순위 올림(priority ceiling)
- 스레드(T1)가 공유 자원을 소유하게 될 때 우선순위를 일시적으로 높이는 방법
- 공유 자원을 소유한 스레드는 다른 스레드(T2)에 의해 선점되지 않고 빨리 실행됨
우선순위 상속(priority inheritance)
- 높은 순위의 스레드(T3)가 공유 자원을 요쳥하면 낮은 순위의 스레드(T1) 우선순위를 요청 스레드보다 높게 변경하여 계속 실행시키고 사용이 끝나면 원래 순위로 되돌림
구현이 쉽지 않고 오버헤드가 존재함
4. 생산자 소비자 문제
4.1 응용프로그램에 존재하는 생산자 소비자 문제 사례
4.1 생상자 소비자 문제의 정의
공유버퍼에 데이터를 공급하는 생산자들과 공유버퍼에서 데이터를 읽고 소비하는 소비자들이 공유 버퍼를 문제없이 사용하도록 생산자와 소비자를 동기화시키는(실행순서를 제어하는)문제
- 문제 1 - 상호 배제(생산자들과 소비자들의 공유버퍼 사용에 대한 상호배제)
- 문제 2 - 비어있는 공유버퍼 문제(비어있는 공유버퍼를 소비자가 읽을 때)
- 문제 3 - 꽉 찬 공유버퍼 문제(꽉 찬 공유버퍼에 생산자가 쓸 때)
4.3 생산자 소비자 문제의 해결책
상호배재 해결
생산자와 소비자가 1개씩 있는 경우 : 생산자와 소비자 사이에만 발생 생산자나 소비자가 여러개 있는 경우 : 생산자들 사이 or 소비자들 사이에서도 발생 가능
뮤텍스나 세마포를 이용하여 작성
비어있는 공유버퍼 문제 해결
소비자 스레드가 공유 버퍼에서 읽을 때 공유 버퍼가 완전히 비어있는 경우, 버퍼 내 저장 공간 중 하나라도 데이터가 기록될 때 까지 기다리도록 설계 생산자 스레드는 공유버퍼에 데이터를 기록하고 기다리고 있을 소비자 스레드를 깨운다 소비자 스레드는 깨어나서 공유버퍼로부터 데이터를 읽는다
소비자스레드는 대기하고 생산자 스레드는 대기상태에서 깨어나도록 알리는 방식 → 세마포
세마포 R에 대한 P 연산 - 소비자 스레드, V 연산 - 생산자 스레드
- 소비자 스레드가 공유버퍼에서 읽고자 P 연산 실행 → 세마포 R의 counter가 0이므로 P연산에서 잠
- 생산자 스레드가 공유버퍼내에 데이털르 쓰고 V 연산을 실행하면 V연산은 세마포 R의 counter값을 1로 만들고 소비자 스레드를 깨움
- 생산자 스레드는 일 수행, 소비자 스레드는 P연산의 남은 부분을 실행한 후 버퍼를 읽음
- P연산 실행이 마치면 세마포 R은 다시 0
꽉 찬 공유버퍼 문제 해결
생산자 스레드가 공유 버퍼에 기록 전 버퍼가 꽉 차있는지 확인 버퍼가 꽉 참 - 생산자 스레드는 소비자 스레드가 하나의 버퍼라도 비울 때까지 대기, 소비자 스레드는 버퍼에서 데이터를 읽은 후 기다리고 있을 생산자 스레드를 깨움, 비어있는 버퍼에 데이터를 씀
- 생산자스레드는 버퍼에 쓰기 위해 세마포 W에 대해 P 연산 수행, 버퍼가 꽉 차있기 때문에 P연산은 생산자 스레드를 중단시키고 잠을 재움
- 소비자 스레드는 버퍼에서 데이터를 읽고 세마포 W에 대해 V연산을 수행하면 V연산은 세마포 W의 값을 1 증가시켜 1로 만들고 대기중인 생산자 스레드를 깨우고 자신의 일을 함
- 깨어난 생산자 스레드는 P연산의 남은 코드 실행, 버퍼에 기록
- 세마포 W는 다시 0
생산자와 소비자 알고리즘
- 세마포 R : 읽기 가능한 버퍼의 개수, 0이면 대기
- 세마포 W : 쓰기 가능한 버퍼의 개수, 0이면 대기
- 뮤텍스 M : 생산자 소비자 두 스레드에 의해 사용(임계구역 코드의 상호 배제를 위해 필요)
