스레드 동기화

<병행 프로세스(Concurrent Process)>
- 프로세스 여러 개가 동시에 실행되는 것
  - 독립적인 프로세스(Independent process)
    - 다른 프로세스 실행에 영향을 주거나 받지 않는 프로세스

  - 협력적인 프로세스(Cooperating process)
    - 다른 프로세스 실행에 영향을 주거나 받는 프로세스
      - 정보 공유
      - 계산 속도 향상
      - 모듈식 시스템 구성
      - 사용자 편의
 
    - 제한된 자원을 공유하기 위해 자주 상호작용 한다
      - 상호작용하는 프로세스는 순서에 맞게 실행되도록 동기화 시켜야한다




<동기화의 필요성>
- 협력적인 스레드들간에
  - 공유 데이터를 동시에(concurrently) 조작하면 데이터 불일치(data inconsistency)가 생길 수 있다
    - 데이터 훼손 발생

- 데이터 일치(data consistency)를 위해서는
  - 협력적인 스레드들이 공유 데이터를 순서적으로 접근하는 방법이 필요
    - 공유 데이터는 한 스레드씩 배타적/독점적 접근 필요

- 공유 집계판의 동시 접근 문제





<공유 집계판 사례의 코드 모델>
- 두 학생 : 스레드 T1, T2
- 공유 집계판 : 공유 변수 sum
- 처리할 계산 : sum = sum + 10;
- ex)
mov ax, [sum] //sum 변수 값을 읽어 ax 레지스터에 저장
add ax, 10; //ax 레지스터 값 10 증가
mov[sum], ax; //ax 레지스터 값을 sum 변수에 저장
==(동일)
sum = sum+10;






<경쟁 상태(race condition)>
- 여러 스레드가 공유 변수에 동시에(concurrently)접근하는 상황
  - 공유 데이터의 결과를 보장할 수 없는 상황 
    - 공유 데이터가 훼손 될 수도 있다

   - 멀티 스레딩, 커널 코드, 다중 코에에서

- '협력적인' 스레드들을 동기화(synchronized)
  - 한 스레드가 접근 마칠 때까지
  - 다른 스레드의 접근을 막도록 제어




<임계 영역 문제(Critical-Section Problem)>
- 공유 데이터를 사용하기 위해 경쟁하는 n개의 스레드들 가정
  - 임계 영역(Critical Section)
    - 공유 데이터를 조작하는 명령을 포함하는 코드 영역
      - 공유 데이터는 둘 이상의 스레드가 동시에 접근하면 안된다

- 한 스레드가 임계 영역을 수행 중이면
  - 다른 스레드는 자신의 임계 영역의 코드를 수행할 수 없어야한다
    - 한 번에 하나의 스레드만 공유 데이터에 접근 위해





<상호 배제(mutual exclusion)>
- 임계영역을 한 스레드만 배타적, 독점적으로 사용하도록 하는 기법
  - 임계영역에 먼저 진입한 스레드가 임계영역의 실행을 끝마칠 때까지 다른 스레드가 '진입하지' 못하도록 보장





<멀티 스레드 프로그램의 일반적인 구성>
일반 코드(non-critical code)
entry 코드(임계구역 진입코드) //임계구역의 상호배제를 위한 코드
--------------------------------------------------------------------
임계구역(critical code)
--------------------------------------------------------------------
exit 코드(임계구역 진출코드) //임계구역의 상호배제를 위한 코드
일반코드(non-critical code)





<상호 배제를 포함하는 프로그램의 구성>
- 일반 코드(non-critical code)
  - 공유 데이터에 접근하지 않는 코드

- 임계영역 진입 코드(entry code)
  - 상호 배제를 위한 처리 수행
    - 현재 스레드만이 임계 영역의 수행 할 수 있도록 처리

- 임계영역 코드(critical code)
  - 공유 데이터를 접근하는 코드

- 임계영역 진출 코드(exit code)
  - 상호 배제를 위한 처리 수행
    - 다른 스레드가 임계 영역에 진입할 수 있도록 처리




<상호 배제 구현>
- 목표 : 오직 하나의 스레드만 진입을 허용
  - 'entry/exit' 코드를 어떻게 구현하나

- 구현 방법
  - 소프트웨어적 방법

  - 하드웨어적 방법
    - 방법1 : 인터럽트 서비스 금지
      - 인터럽트가 발생해도 CPU가 인터럽트를 무시하도록 하는 CPU 명령 이용

    - 방법2 : 원자 기계 명령(atomic instruction)사용
      - 오늘날 상호 배제 구현에 가장 많이 사용하는 방법
      - 임계영역 진입 시, 임계영역을 잠그고 들어가는 원자 명령 사용




<상호배제 구현1 : 인터럽트 서비스 금지>
- 임계구역에 대한 상호배제를 만드는 간단한 방법
  cli ; entry 코드. 인터럽트 서비스 금지 명령 cli(clear interrupt flag)
  ...
  임계구역 코드
  ...
  sti ; exit 코드. 인터럽트 서비스 허용 명령 sti(set interrupt flag)

  - 인터럽트가 발생해도 CPU는 무시하고 ISR 실행 안한다
    - 임계 영역을 실행하던 스레드는 중단되지 않는다





<인터럽트 서비스 금지 방법의 문제점>
- 모든 인터럽트가 무시되는 문제 발생
  - 중요 ISR의 실행이 지연될 수 있다

- 멀티 코어 CPU나 다중 CPU를 가진 시스템에서는 활용 불가
  - 한 CPU의 인터럽트 금지가 다른 코어/CPU의 인터럽트 서비스까지 금지할 수는 없다
    - 다른 코어/CPU에서 실행되는 스레드가 임계 영역에 진입 가능





<상호배제 구현2 : 락을 이용한 상호배제 시도>
- locking/unlocking 방식으로 임계구역의 entry/exit 코드 작성하면 상호배제가 가능할까?
  - lock 변수 : 1이면 잠금 상태
  - lock 변수 : 0이면 열린 상태

- ex)
entry 코드 //locking, lock 변수의 초기 값은 0
I1:
mov ax, [lock] //lock 변수 읽기
mov [lock], 1 //lock 변수에 1 저장
cmp, ax, 0 //이전 lock 변수가 0인지 비교
jne I1 //같지 않으면 I1으로 점프, 같으면 임계구역 진입
----------------------------------
  임계구역
----------------------------------
exit 코드 //unlocking
  mov [lock], 0 //lock 변수에 0 저장





<lock 변수 이용한 상호배제의 실패 원인>
- entry 코드의 한계
  - lock 변수의 값을 읽는 명령과 저장하는 명령 사이에 '컨텍스트 스위칭'이 될 때에만 문제가 발생
  - 그 외의 경우에는 문제 없음
  
- ex)
  I1:
mov ax, [lock] //lock값을 읽고
---------------------- 컨텍스트 스위칭
mov[lock], 1 //lock에 1기록
cmp ax, 0
jne I1






<lock 변수 이용한 상호배제의 해결책>
- 원자 명령(atomic instruction) 도입
  - lock 변수를 읽어 들이는 명령과 값을 저장하는 명령을 '하나의 CPU 명령'으로 처리
    - atomic operation

  - 원자 명령 : TLS(Test and Set Lock) 
    - 오늘날 대부분의 CPU에서 제공

- ex)
  mov ax, [lock]
  mov [lock], 1        --->     TSL ax, [lock] //원자 명령






<lock 변수와 TSL을 이용한 상호배제>
(a) 상호배제 실패
entry 코드 
I1:
mov ax, [lock]
mov [lock], 1
cmp ax, 0
jne I1
--------------------------임계구역
exit 코드
mov[lock], 0


(b) 원자명령 TSL를 사용하여 상호배제 성공
entry 코드
I1:
TSL ax, [lock]
cmp ax, 0
jne I1
--------------------------임계구역
exit 코드
mov[lock]. 0






<멀티스레드 동기화 기법>
- 상호 배제 기반 위에서 여러 스레드들이 자원을 원활히 공유할 수 있도록 하는 기법
  - 동기화 프리미티브(synchronization primitives)로 부름
  - '임계 영역' 진입 시 상호배제를 위해 원자 명령 사용






<대표적인 멀티 스레드 동기화 기법>
- locks 방식 : 뮤텍스(mutex), 스핀락(spinlock)
  - 상호 배제가 되도록 만들어진 'lock 변수' 활용
    - lock을 소유한 스레드만이 임계 영역 진입
    - lock을 소유하지 않은 스레드는 대기

- wait-signal 방식 : 세마포어(semaphore)
  - 'n개의 자원'을 사용하려는 m개의 스레드의 원활한 관리 제공
    - 자원을 소유하지 못한 스레드는 대기(wait)
    - 자원의 사용을 마친 스레드는 알림(signal)





<뮤텍스>
- 잠김/열림 중 한 상태를 갖는 lock 변수 이용
  - 한 스레드만 임계 영역에 진입시키고
  - 나머지 스레드는 '큐에 대기'
    - sleep-waiting lock, blocking lock 기법이라고도 한단





<뮤텍스의 구성 요소>
- lock 변수
  - true : lock을 잠근다. lock을 소유한다
  - false : lock을 연다. lock을 해제한다

- 대기 큐
  - lock이 열리기를 기다리는 스레드 큐

- 연산
  - lock 연산(임계 영역의 entry 코드)
  - unlock 연산(임계 영역의 exit 코드)






<뮤텍스의 연산>
- lock 연산(임계 영역의 entry 코드)
  - 잠김 상태(lock = true)이면, 현재 스레드를 블록 상태로 만들고 '대기 큐'에 진입
  - lock이 열린 상태이면, lock을 잠그고 임계 영역 진입

- unlock 연산(임계 영역의 exit 코드)
  - lock을 열린 상태(lock = false)로 변경
  - 대기 큐에서 기다리는 스레드 하나 깨움






<뮤텍스를 이용한 동기화의 특징>
- 임계 영역에서의 실행 시간이 짧은 경우 비효율적
  - 특정 스레드가 임계 영역 접근시 lock이 잠겨있으면 대기 큐에서 대기시키고 컨텍스트 스위칭
  - lock이 풀리면 깨어난 후 컨텍스트 스위칭하여 CPU를 할당 받아 실행 재개

  - 두 번의 컨텍스트 스위칭 시간 발생
    - lock이 잠겨 있는 시간보다
    - 스레드를 잠자게/깨어나게 하는데 걸리는 시간이 더 작아야





<POSIX 라이브러리에서 제공하는 뮤텍스>
- 뮤텍스 락 변수 : pthread_mutex_t lock;

- 뮤텍스 조작 함수
  - pthread_mutex_init() : 뮤텍스락 변수 초기화
  - pthread_mutex_lock() : 뮤텍스락 잠그기
  - pthread_mutex_unlock() : 뮤텍스락 풀기
  - pthread_mutex_destory() : 뮤텍스락 변수 사용
 





<스핀락(spinlock)>
- 기본적으로 뮤텍스와 같으나 대기하는 스레드가 블록되는 대신 'busy-waiting'한다는 점만 다르다
  - 대기 큐를 갖지 않는다
   - 스레드가 큐에서 블록되지 않고 lock이 열릴 때까지 계속 lock 변수값 '검사'
    - CPU를 계속 소모하므로 CPU는 다른 스레드 실행 불가

  - lock을 소유한 스레드만이 자원 배타적 사용
    - 공유 자원 하나마다 하나의 스핀락 사용

  - 공격적은 뮤텍스(aggressive mutex),
    busy-waiting lock 기법





<스핀락의 구성 요소>
- lock 변수
  - true : lock을 잠근다. lock을 소유한다
  - false : lock을 연다. lock을 해제한다

- 연산
  - lock 연산
    - 임계 영역에 들어갈 때 실행되는 entry 코드
    - lock이 잠김 상태면, lock이 풀릴 때까지 무한 루프 돌면서 lock 연산 시도
    - lock이 열린 상태면, lock을 잠그고 바꾸고 임계 영역 실행

  - unlock 연산
    - 임계 영역을 나올 때 실행하는 exit 코드
    - lock을 열린 상태로 변경





<스핀락을 이용한 동기화의 특징>
- 뮤텍스의 non-blocking 모델
- 단일 CPU/코어를 가진 OS에서 비효율적
  - 다소 의미 없는 CPU 시간 낭비
    - 스핀락을 검사하는 스레드는 타임 슬라이스 소비
    - 락을 소유한 스레드가 실행되어야 락이 풀릴 수 있다

  - 임계 영역의 실행 시간이 짧은 경우 효과적






<POSIX 라이브러리에서 제공하는 스핀락>
- 스핀락 변수 : pthread_spinlock_t lock;

- 스핀락 조작 함수
  - pthread_spinlock_init() : 스핀락 변수 초기화
  - pthread_spinlock_lock() : 스핀락 잠그기
  - pthread_spinlock_unlock() : 스핀락 풀기
  - pthread_spinlock_destory() : 스핀락 변수 사용






<하이브리드 뮤텍스(hybrid mutex)>
- 뮤텍스와 스핀락을 혼합한 동기화 방식
  - 오늘날 커널에서 많이 사용됨
  - 처음에는 스핀락처럼 동작하다 일정 시간이 지날 때까지 락을 획득하지 못하면 뮤텍스처럼 블럭된다
  - 적응형 뮤텍스(adaptive mutex), 적응형 스핀락(adaptive spinlock)






<뮤텍스 vs. 스핀락>
- 뮤텍스
  - 락이 잠기는 시간이 긴 경우
  - 단일 CPU를 가진 시스템
  - 사용자 모드, 사용자 응용 프로그램에서 주로 사용

- 스핀락
  - 락이 잠기는 시간이 짧은 경우
  - 멀티 코어/CPU 시스템
  - 커널 모드, 커널 코드나 ISR(Interrupt Service Routine)에서 주로 사용






<세마포어(semaphore)>
- 멀티 스레드 간의 자원 관리 기법
  - 'n'개의 공유 자원을 다수의 스레드가 공유해 사용하도록 돕는 자원 관리 기법






<세마포어의 구성 요소>
- 자원 : n개

- 대기 큐 
  - 자원을 할당받지 못한 스레드들을 위한 대기 큐

- counter 변수
  - 사용 가능한 자원의 개수를 나타냄
  - 정수형 전역 변수 : 자원의 개수(n)로 초기화

- P/V 연산 : atomic operation
  - P(wait) 연산 : 자원의 사용 허가를 받기 위해 자원 요청 시 실행
  - V(signal) 연산 : 자원 사용이 끝났음을 알리기 위해 자원 발환 시 실행





<세마포어의 종류>
- 자원을 할당 받지 못한 경우의 처리에 따라 구분
  - sleep-wait 세마포어
    - P 연산 : 대기 큐에서 잠자기
    - ex) P 연산
{ //wait
counter--; //자원 요청
...현재 스레드를 대기 큐에 삽입...//sleep-wait
}
...자원 획득...
}

    - V 연산 : 사용 가능한 자원이 있으면 잠자는 스레드 깨우기
    - ex) V 연산
{ //signal
counter++; //자원 반환
if counter <=0 { //기다리는 스레드 있는 경우
  ...대기 큐에서 한 스레드 깨움...
}
}

  - busy-wait 세마포어 //blocking 하지 않는다
    - P 연산 : 사용 가능한 자원이 생길 때까지 무한 반복 검사
    - ex) P 연산
{ //wait
while counter <= 0; //busy-wait
counter--;
}

    - V 연산 : counter++; 
    - ex) V 연산
{ //signal
counter++;
}






<POSIX 라이브러리에서 제공하는 세마포어>
- 세마포어 구조체 : sem_t s

- 세마포어 조작 함수
  - sem_init() : 세마포어 변수 초기화
  - sem_destory : 세마포어 초기화
  - sem_wait() : P 연산을 수행하는 함수(blocking)
  - sem_trywait() : P연산을 수행하는 함수(non-blocking)
  - sem_post() : V 연산을 수행하는 함수
  - sem_getvalue() : 세마포어의 현재 counter 값을 반환






<카운팅 세마포어와 이진 세마포어>
- 카운팅 세마포어(counting semaphore)
  - 자원의 인스턴스가 여러 개인 경우

- 이진 세마포어(binary semaphore)
  - 자원이 1개 있는 경우의 멀티 스레드 간의 자원 관리
  - 1개 자원에 대해 배타적 접근 위해
    - 뮤텍스와 유사





<이진 세마포어의 구성 요소>
- 세마포어 변수 S
  - 0과 1중 하나를 가지는 전역 변수
    - S는 1로 초기화

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

- 연산
  - wait 연산 : 자원의 사용 허가를 얻는 과정 처리
  - signal 연산 : 자원 사용이 끝났음을 알리는 과정 처리






<뮤텍스 vs. 세마포어>
- 뮤텍스
  - 하나의 자원에 대한 상호 배제
    - 자원 : 공유 변수
    - 하나의 자원에 대한 이진 세마포어
    - 예 : 한 칸짜리 화장실에 하나의 키가 있는 경우

- 세마포어
  - 각 자원에 대한 여러 인스턴스 관리
    - 자원 : 버퍼, 로그인 개수
    - 자원 제어와 시그널링에 사용
    - 예 : 독립된 키를 갖는 4칸짜리 화장실의 경우






<동기화 이슈 : 우선순위 역전(priority inversion)>
- 높은 우선순위의 스레드가 낮은 우선순위의 스레드보다 늦게 스케줄링 되는 현상
  - 실시간 시스템이나 우선순위를 기반으로 하는 시스템에서 스레드의 동기화로 인해 발생
  - 실시간 시스템의 근본이 붕괴될 수 있음
  - 중요한 일을 할 가능성이 있는 스레드의 처리가 지연





<우선 순위 역전의 해결책>
- 구현이 쉽지 않고 오버헤드 존재
  - 우선순위 올림(priority ceiling)
    - 스레드가 공유 자원을 소유하게 될 때, 스레드의 우선순위를 미리 정해진 높은 우선순위로 일시적으로 올림
      - 공유 자원을 접근할 어떤 스레드보다도 높게 설정
    - 선점되지 않고 빨리 실행되도록 유도
    - 공유 자원에 대한 사용이 끝나면 우선순위 복원

  - 우선순위 상속(priority inheritance)
    - 낮은 우선순위의 스레드가 공유 자원을 갖고 있는 동안
    - 높은 순위의 스레드가 공유 자원을 요청하면,
    - 공유 자원을 가진 스레드의 우선순위를 요청한 스레드보다 높게 설정하여 계속 실행시킴
    - 공유 자원에 대한 사용이 끝나면 우선순위 복원






<생산자-소비자 문제>
- 정보 생상자 스레드와 정보 소비자 스레드가 공유한 공유 버퍼를 통해 정보를 원활히 주고 받을 수 있도록 동기화
  - 많은 멀티 스레딩 app에서 발생하는 전형적인 동기화 문제
  - 생산자 스레드(producer) -> 공유 버퍼 -> 소비자 스레드(consumer)

- ex) (a) 미디어 플레이어의 구조(1:1 생산자 소비자 관계)
네트워크, 비디오 파일 -> 입력스레드(생산자) -> 비디오 버퍼 -> 재생스레드(소비자) -> 디스플레이

- ex) (b) 스트리밍 서버의 구조(1:N 생산자 소비자 관계)
비디오 파일 -> 입력스레드(생산자) -> 비디오 버퍼 -> 송신스레드1, 송신스레드2, 송신드레드3(소비자) -> 인터넷 -> 미디어 플레이어1, 미디어 플레이어2, 미디어 플레이어3 








<생산자-소비자 문제의 주된 관심사>
- 생상사-소비자들의 공유 버퍼에 대한 상호 배제
  - 뮤텍스나 세마포어를 이용해 해결
- 비어있는 경우 공유 버퍼를 소비자가 읽으려 할 때
- 꽉 찬 공유 버퍼에 생산자가 추가하려 할 때






<꽉 찬 공유 버퍼 문제의 해결 방안>
- 세마포 W(쓰기 가능한 버퍼 개수) 활용 : 버퍼가 꽉 차 있을 때 처리하는 P/V 연산으로 해결
  (1) 공유 버퍼가 찬 상태에서, 생산자가 쓰려고 할 때
    생산자 : 버퍼에 쓰기 전 P 연산 실행
    P 연산 : 버퍼가 꽉 찬 상태(W=0)이면, 생산자가 잠을 자면서 대기하도록 작성

  (2) 버퍼에 데이터가 있는 경우, 소비자가 읽을 때
    소비자 : 버퍼에서 데이터를 읽은 후 V 연산 실행
    V 연산 : 세마포 변수 W를 1증가시키고(W=1), 대기 중인 생산자를 깨우도록 작성
    생산자 : 깨어나면 P연산을 마치고 공유 버퍼에 쓴다. P연산에서 세마포 W를 1감소(W=0)







<생산자-소비자 알고리즘>
- 카운팅 세마포어
  - W : 버퍼에 쓰기 가능한 저장 공간의 수
    - 0이면 꽉 찬 상태

   - R : 버퍼에서 읽기 가능한 저장 공간의 수
    - 0이면 비어있는 상태
  
- 뮤텍스
  - M : 공유 버퍼의 배타적 접근을 위해 모든 생산자-소비자 스레드에 의해 사용







<생산자-소비자 알고리즘>
Consumer{ //소비자 스레드
while(true){
P(R); //세마포R에 P/wait 연산을 수행하여
//버퍼가 비어있으면(읽기 가능한 버퍼 수=0) 대기한다.

배타적 사용을 위해,
뮤텍스(M)을 잠근다. 
공유버퍼에서 데이터를 읽는다. //임계구역 코드
뮤텍스(M)을 연다.

V(W); //세마포 W에 대해 V/signal 연산을 수행하여
//버퍼가 비기를 기다리는 Producer를 깨운다
}
}

Producer{ //생산자 스레드
while(true){
P(W); //세마포 W에 P/wait 연산을 수행하여
//버퍼가 꽉 차 있으면(쓰기 가능한 버퍼 수=0) 대기

배타적 사용을 위해, 
뮤텍스(M)를 잠근다.
공유버퍼에 데이터를 저장한다. //임계구역 코드
뮤텍스(M)을 연다.

V(R); //세마포 R에 대해 V/signal 연산을 수행하여
//버퍼에 데이터가 저장되기를 기다리는 Consumer를 깨운다
}
}






<생산자-소비자 app의 구성(1)>
- 1개의 생산자, 1개의 소비자 스레드로 구성
  - 생산자 스레드 
    - 0~9까지의 정수를 임의 시간 간격으로 공유 버퍼에 씀
 
  - 소비자 스레드
    - 공유버퍼로부터 임의 시간 간격으로 정수를 읽어 출력
  
  - 공유 버퍼
    - 4개의 정수를 저장하는 원형 큐
    - 배열로 작성






<생산자-소비자 app의 구성(2)>
- 2개의 세마포어
  - semWrite
    - 공유 버퍼에 쓰기 가능한 공간의 개수를 나타냄
    - 초기값이 4인 conuter를 가짐

  - semRead
    - 공유 버퍼에 읽기 가능한 공간의 개수를 나타냄
    - 초기값이 0인 counter를 가짐

- 1개의 뮤텍스
  - 공유 버퍼 접근 코드를 임계 영역으로 설정