스레드 동기화

스레드 동기화의 필요성

스레드 동기화(Thread synchronization) : 공유 데이터에 대한 다수 스레드가 동시에 접근할 때 해당 데이터가 훼손되지 않게 하는 기법으로 한 스레드가 공유데이터에 배타적 독점권을 가지도록 순서화

• 공유 데이터(Resource)에 동시에 쓰기를 접근한다면
  - 공유 데이터가 훼손되는 문제가 발생할 수 있음
  - 예) 공동계좌에 2명이 완전히 동일한 시각에 10만원을 입금한다면 동시 쓰기가 발생하여 결과가 20만원이아닌 10만원이 될 수 있음

 

 

공유 데이터 접근 문제의 해결책

• 스레드 동기화 : 한 스레드가 공유 데이터 사용을 마칠 때 까지 다른 스레드가 해당 데이터에 접근하지 못하도록 제어

-> 멀티 스레드의 경쟁 상황은 매우 자주 발생하며, 주로 사용자가 작성한 멀티스레드 프로그램이나 커널 코드에서 빈번하게 발생하고 다중 코어 CPU일 경우 더더욱 조심해야 함

 

 

 

 

임계구역과 상호배제

• 임계 구역(Critical Section) : 공유 데이터에 접근하는 프로그램 코드영역을 의미
• 상호 배제(Mutual Exclusion) : 임계 구역을 오직 한 스레드에만 배타적 독점권을 부여하는 기술
  - 임계 구역에 먼저 진입한 스레드가 임계구역의 작업을 끝낼 때 까지 다른 스레드가 진입하지 못하도록 보장

 

 

 

상호 배제를 포함하는 프로그램의 형태

• 일반 코드(non - critical code) : 공유 데이터에 액세스하지 않는 코드
• 임계구역 진입 코드(Entry code)
  - 임계 구역에 진입하기 전 필요한 코드 블럭(공유 자원에 접근하는)
  - 현재 임계구역을 실행 중인 스레드가 있는지를 검사한 뒤
  - 있다면 진입이 가능할 때 까지 대기
  - 없다면 다른 스레드가 들어오지 못하도록(Lock) 조치하고 실행
• 임계구역 코드 (Critical code)
  - 임계 구역에 존재하여 하나의 스레드가 배타적 독점권을 얻어 실행하는 코드(공유 자원을 사용하는)
• 임계구역 진출 코드(Exit code)
  - 임계구역을 마칠 때 필요한 코드 블럭
  - 대기중인 스레드가 임계구역에 진입할 수 있도록 진입 코드에서 시행한 조치를 해제

 

 

 

상호 배제 구현

• 소프트웨어적 방법
  - 알고리즘 수준에서 상호 배제를 구현하기에는 여러 문제가 발생
  - Peterson's 알고리즘 등
• 하드웨어적 방법
  - 하드웨어의 도움을 받아 상호배제를 구현하는방법
  - 인터럽트 서비스 금지(인터럽트 플래그), 원자 명령(CPU 명령) 사용 등
  - 오늘날 OS는 대부분 하드웨어적 방법을 사용

 

 

 

인터럽트 서비스 금지

• Entry code에서 인터럽트 서비스를 금지하는 명령을 실행함(cli : 0으로 set하여 인터럽트 금지, sti : 1로 set하여 인터럽트 허용)
  - 임계구역 코드 실행 중 인터럽트가 발생해도 CPU가 인터럽트 발생을 무시
  - 즉 인터럽트가 발생해도 CPU는 인터럽트 서비스 루틴을 실행하지 않음
  - 이로써 임계구역을 실행하는 스레드가 중단되지않음
• 문제점
  - 모든 인터럽트가 무시되어 문제들이 발생
  - 인터럽트 금지는 코어별로 설정되기 때문에, 하나의 코어에서 인터럽트를 금지해도 다른 코어에서 임계구역에 접근할 수 있으므로 멀티 코어CPU에서는 활용할 수 없음

 

 

 

lock 변수로 상호 배제를 시도

• locking / unlocking 방식으로 임계구역의 Entry code와 Exit code를 작성하면 상호 배제가 가능한지에 대한 시도
  - 1이면 잠금
  - 0이면 풀림
  -> cli, sti와는 비트가 반대임
• Entry code 예시
  l1:
      mov ax, lock ;lock 변수를 읽어 ax레지스터에 저장
      mov lock, 1 ;1을 lock 변수에 저장
      cmp ax, 0 ;lock변수를 읽어온 ax레지스터와 0을 비교
      jne l1 ;0이 아니면 l1으로 다시 점프
• Exit code 예시
  move lock, 0 ;lock 변수에 0을 저장
• 문제점
  - ax레지스터에 lock변수의 값을 입력하고 lock을 1로 되돌릴 때 이 사이에서 스레드가 중단되면 임계구역 충돌이 발생
  - 이를 해결하기 위해서는  l1의 mov ax, lock과 mov lock, 1의 코드를 한 블럭으로 실행해야함

 

 

 

원자 명령 사용

lock 변수를 이용한 상호 배제시행의 실패 원인
- 실패 원인은 Entry code의 mov ax, lock과 mov lock, 1의 코드 사이에 컨텍스트 스위칭이 발생할 때 발생하는 문제

• 해결책 : 원자 명령(Atomic instruction) 도입
  - lock 변수를 읽는 명령과 lock 변수에 1을 저장하는, 즉 원인이 되는 2개의 명령을 한 번에 처리하는 원자 명령 필요
  - 해당 원자 명령은 TSL(Test and Set Lock) 으로 1970년 인텔 펜티엄에서 시작되어 현재 대부분의 CPU에 존재함
  - mov ax, lock과 mov lock, 1을 합침 -> TSL ax, lock

 

 

 

 

멀티스레드 동기화 기법

멀티스레드 동기화 : 상호배제 기반위에서 공유 자원을 이용하려는 여러 스레드들이 자원을 원활히 공유하도록 하는 기법

- Synchronization primitives로 부르는 저수준의 메커니즘

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

 

 

 

뮤텍스(Mutex)

- 잠김 / 열림 중 한 상태를 나타내는 lock 변수 사용

- 한 스레드만 임계구역에 진입시킴

- 다른 스레드는 대기 큐에서 대기

- 락 변수가 잠겨 다른 스레드가 임계구역을 실행중일 경우 대기할 스레드를 대기 큐에 삽입하고 락 변수가 열릴 때 깨우는sleep-waiting lock 기법

- 자원의 배타적 사용을 위한 동기화 기법이며 공유자원 하나 당 하나의 뮤텍스 사용

 

뮤텍스 기법의 구성 요소

• lock 변수
  - true / false의 값을 가지며 true는 잠금, false는 열림
• 대기 큐(Wait Queue)
  - lock이 열리기를 기다리는 스레드를 가지는 큐
• lock 연산 (임계구역의 Entry code)
  - lock이 열린 상태면(false, 0), lock을 잠그고(true, 1) 임계구역에 진입
  - lock이 잠긴 상태이면(false, 0) 현재 스레드를 블록 상태로 만들고 대기 큐에 삽입
• unlock 연산 (임계구역의 Exit code)
  - lock을 열림 상태로(false, 0)으로 변경 후 대기 큐에서 대기중인 스레드 하나를 깨움

 

뮤텍스 특징 : 임계구역의 실행 시간이 짧을 경우, 비효율적임
- 잠겨있으면 컨텍스트 스위칭이 시행되고 대기 큐에서 대기하고 락이 풀리면 다시 컨텍스트 스위칭을 시행하고 실행하게 되는데 여기서 큰 오버헤드가 발생, 락이 잠긴 시간보다 스레드가 잠자고 깨는 시간이 더 길면 비효율적임

 

 

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

- UNIX계열의 표준 OS Interface 라이브러리

• 뮤텍스 락 변수
  - pthread_mutex_t lock;
• 대기 큐는 pthread 라이브러리 내부에 구현되어 있음
• 조작 함수
  - pthread_mutex_init() : 뮤텍스 락 변수 초기화
  - pthread_mutex_lock() : 뮤텍스 락 연산
  - pthread_mutex_unlock() : 며텍스 언락 연산
  - pthread_mutex_destroy() : 뮤텍스 락 변수 사용 종료후 해제

#include<stdio.h>
#include<pthread.h>

pthread_mutex_t lock; // 뮤텍스 락 변수 생성

pthread_mutex_init(&lock, NULL); // 뮤텍스 락 변수 초기화

pthread_mutex_lock(&lock); // 임계구역 Entry code, lock 변수에 lock 연산 시행
// 임계구역
pthread_mutex_unlock(&lock); // 임계구역 Exit code, lock 변수에 unlock 연산 시행

 

 

 

 

 

스핀락(Spinlock)

- 기본 로직은 뮤텍스와 같음

- 차이점은 대기 큐가 없으며 스레드가 락이 열릴 때 까지 계속 락 변수를 검사하는 busy-waiting 기법

- busy-waiting으로 인해 CPU를 계속 소모하며 락 변수를 검사중인 CPU는 다른 스레드를 실행할 수 없음

- 자원의 배타적 사용을 위한 동기화 기법이며 공유자원 하나 당 하나의 스핀락 사용

 

스핀락의 구성요소

• lock 변수
  - true / false의 값을 가지며 true는 잠금, false는 열림
• lock 연산(임계구역의 Entry code)
  - lock이 잠긴상태(true, 1)일 경우 lock이 풀릴 때 까지 무한정 루프를 돌면서 lock 연산을 재시도
  - lock이 열린상태(false, 0)일 경우 lock을을 잠금상태(true, 1)로 바꾸고 임계구역을 실행
• unlock 연산(임계구역의 Exit code)
  - lock을 열림상태(false, 0)으로 변경

 

스핀락의 특징 : 싱글코어 시스템일 경우 비효율적임

- 스핀락은 대기큐가 없는 non-blocking 모델이므로 싱글코어 시스템에서는 스핀락 검사 스레드의 타임슬라이스가 소진될 때 까지 다른 스레드를 실행시킬 수 없으므로 비효율적임

- 반대로 컨텍스트 스위칭이 일어나지않아, 멀티코어 시스템이라면 오버헤드도 적으면서 상기 단점도 상쇄하므로 멀티코어 시스템에 적합함

- 스핀락은 무한 경쟁 방식이므로 기아 스레드가 발생할 수 있으며, lock을 풀지않고 종료하는 경우와 같이 코딩에 실수가 발생해도 기아가 발생할 수 있음

 

 

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

- UNIX계열의 표준 OS Interface 라이브러리

• 스핀락 락 변수
  - pthread_spinlock_t lock;
• 스핀락 조작 함수
  - pthread_spin_init() : 스핀락 락 변수 초기화
  - pthread_spin_lock() : 스핀락 lock 연산
  - pthread_spin_unlock() : 스핀락 unlock 연산
  - pthread_spin_destory() : 스핀락 락 변수 사용 후 해제

#include<stdio.h>
#include<pthread.h>

pthread_spinlock_t lock; // 스핀락 락 변수 생성

pthread_spin_init(&lock, NULL); // 스핀락 락 변수 초기화

pthread_spin_lock(&lock); // 임계구역 Entry code, lock 변수에 lock 연산 시행
// 임계구역
pthread_spin_unlock(&lock); // 임계구역 Exit code, lock 변수에 unlock 연산 시행

 

 

 

 

 

뮤텍스와 스핀락의 사용처

락의 잠금 시간(임계구역의 길이)에 따른 구분

• 임계구역이 길 경우(락의 잠금시간이 길 경우) : 뮤텍스 사용
  - 임계구역이 길 경우 접근 권한을 얻기까지 오래 걸리기에 CPU를 다른 스레드에게 양보하는 것이 효율적임
• 임계구역이 짧은 경우(락의 잠금시간이 짧은 경우) : 스핀락 사용
  - 임계구역이 짧을 경우 접근 권한을 금방 얻을 수 있으므로, 대기 큐 사용으로 오버헤드를 증가시키지 않는 스핀락이 효율적임

 

CPU 구조에 따른 구분

• 싱글코어 시스템 : 뮤텍스 사용
  - 싱글 코어 시스템에서 스핀락은 타임슬라이스만 낭비하며 사용하는 의미가 없음
• 멀티코어 시스템 : 스핀락 사용
  - 멀티코어 시스템에서는 대기 큐를 사용하는 장점이 희석되고 임계구역은 보통 짧으므로 컨텍스트 스위칭 오버헤드가 없는 스핀락이 효율적임

 

최적화 필요성에 따른 구분

• 사용자 응용프로그램 : 뮤텍스 사용
  - 사용자 응용프로그램은 커널코드에 비해 상대적으로 최적화의 중요성이 덜하고 임계구역이 기므로 뮤텍스가 적합
• 커널 코드 : 스핀락 사용
  - 커널 코드, 인터럽트 서비스 루틴은 빠른 실행을 위한 최적화가 필수적이며 이로써 임계구역이 짧으므로 스핀락이 적합
  - 인터럽트 서비스 루틴 도중에는 블록상태가 될 수 없으므로 스핀락이 적합

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

 

 

 

 

세마포어

n개의 자원 풀이 존재할 때 이보다 많은 스레드가 자원을 활용하려 할 때 자원들을 원활히 사용할 수 있도록 관리해야하는데 이 때 세마포어가 필요

 

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

 

세마포어의 구성요소

• 자원 : 공유자원, n개가 존재
• 대기 큐(Wait Queue) : 자원을 할당받지 못한 스레드들이 대기하는 큐
• counter 변수 : 사용가능한 자원의 개수를 나타내는 정수형 전역변수로 총 자원의 개수인 n으로 초기화(counter = n)
• P / V 연산
  - P 연산(wait 연산) : 자원 요청 시 실행하는 연산, 자원 사용 허가를 얻는 과정 -> counter 변수 감소
  - V 연산(signal 연산) : 자원 반환 시 실행하는 연산, 자원 사용이 끝났음을 알리는 과정 -> counter 변수 증가

 

세마포어의 종류

• sleep-wait 세마포어
  - P연산 : counter--, 대기 큐에서 블록됨
  - V연산 : counter++, 사용 가능한 자원이 있으면 잠자는 스레드를 깨움
• busy-wait 세마포어
  - P연산 : 사용 가능한 자원이 생길때까지 무한 루프를돌며 대기하다가 자원이 생기면 counter--
  - V연산 : counter++

 

세마포어 활용을 위한 POSIX 표준 라이브러리
- UNIX계열의 표준 OS Interface 라이브러리

• 세마포어 구조체
  - sem_t s;
• 세마포어 조작 함수
  - sem_init() : 세마포어 초기화
  - sem_destory() : 세마포어 소멸
  - sem_wait() : P연산 수행, sleep-wait 방식으로 가용할 자원이 없으면 대기 큐에서 블록되는 Blocking Call
  - sem_trywait() : P연산 수행, 가용자원이 있으면 counter 감소 후 0리턴, 없으면 counter 증감 없이 -1만 리턴하고 블록되지 않는 Non - Blocking Call
  - sem_post() : V연산 수행
  - sem_getvalue() : 세마포어의 현재 counter 값을 리턴

 

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

• 카운터 세마포어 : 앞선 여러개의 자원을 관리하는 세마포어
• 이진 세마포어 : 한 개의 자원을 관리하는 세마포어로 뮤텍스와 매우 유사
  - 세마포어 변수 S : 전역 변수이며 1로 초기화 함(0과 1중 하나를 가짐)
  - 대기 큐 : 사용가능한 자원이 생길때까지 스레드들이 대기하는 큐
  - P연산(wait) : 자원 사용 허가를 얻는 과정 -> S를 1감소시키며 S가 0이되므로 이후의 스레드들은 대기 큐에서 잠듦
  - V연산(signal) : 자원 사용 후 반환하는 과정 -> S를 1증가시키며 S가 1이되고 대기큐의 스레드 1개를 깨움

 

 

 

 

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

우선순위 역전(Priority Inversion) : 스레드의 동기화로 인해 높은 우선순위의 스레드가 낮은 스레드보다 늦게 스케줄링 되는 현상
- 우선순위 기반 스케줄링 시스템에서의 스레드 동기화로 인해 발생

 

우선순위 역전의 문제점
- 우선순위 기반 스케줄링 시스템의 목적성이 희석되고 이는 실시간 시스템의 근본을 붕괴함
- 우선순위가 높다는 것은 중욯나 일을 할 가능성이 높다는 것인데, 이가 늦게 실행되면 심각한 문제 야기 가능

 

우선순위 역전 해결책

• 우선순위 올림(Priority Ceiling)
  - 낮은 순위의 스레드가 공유자원을 소유하게 될 때 스레드의 우선순위를 미리 정진 높은 우선순위로 일시적으로 올리는 방법
  - 선점되지 않고 빨리 실행되도록 유도
• 우선순위 상속(Priority Inheritance)
  - 낮은 순위의 스레드가 공유자원을 가지고 있는 동안 높은 순위의 스레드가 공유 자원을 요청하면 낮은 순위의 스레드를 일시적으로 요청한 높은 순위의 스레드보다 더 높게 설정해서 빨리 실행시키도록 함

 

 

 

 

생산자 소비자 문제

공유 버퍼를 두고, 공유 버퍼에 데이터를 공급하는 생산자와 데이터를 읽는 소비자들이 공유 버퍼를 문제없이 사용하도록 생산자 소비자를 동기화시키는 문제

• 문제1 : 상호배제문제
  - 생산자들과 소비자들이 공유버퍼에 동시접근할 수 없도록 상호배제
• 문제2 : 비어있는 공유 버퍼 문제(Buffer Underrun)
  - 비어있는 공유버퍼를 소비자가 읽을 때
• 문제3 : 꽉 찬 공유 버퍼 문제(Buffer Overflow)
  - 꽉 찬 공유버퍼에 생산자가 쓸 때

 

비어있는 공유 버퍼 문제 해결
- 세마포어 R 활용 : 세마포어의 R은 읽기가 가능한 버퍼의 개수를 나타내는 세마포어
- 공유버퍼가 빈 상태에서 소비자가 읽으려 할 때, 즉 소비자가 P연산을 수행할 때 R=0일 경우 소비자가 잠을자면서 대기하도록 함
- 공유버퍼가 빈 상태에서 생산자가 쓰려 할 때 생산자는 버퍼에 데이터를 기록하고 V연산을 수행한 뒤 R을 1증가시키고 대기중인 소비자를 깨운다
- 깨어난 소비자는 P연산을 마치고(R이 1이므로 통과 가능) 공유 버퍼에서 읽는다. P연산에서 R은 1감소한다(다시 0)

 

 

 

꽉 찬 공유 버퍼 문제 해결

- 세마포어 W 활용 : 세마포어 W는 쓰기가 가능한 버퍼의 개수를 나타내는 세마포어
- 공유 버퍼가 꽉 찬 상태에서 생산자가 쓰려 할 때, 즉 생산자가 P연산을 수행할 때 W=0일 경우 생산자가 잠을 자면서 대기하도록 함
- 공유 버퍼가 꽉 찬 상태에서 소비자가 읽으려 할 때 소비자는 버퍼에서 데이터 1개를 읽고 지운 뒤 W를 1증가시키고 대기중인 생산자를 깨운다

- 깨어난 생산자는 W연산을 마치고(W가 1이므로 통과가능) 공유 버퍼에 데이터를 쓴다. P연산에서 W는 1감소한다(다시0)