비동기 병행 실행

상호 배제

병행 실행

• 동시에 존재하는 쓰레드의 실행
• 비동기적 실행
  • 독립적으로 실행되거나 협력하여 실행
  • 때때로 서로 통신을 하거나 동기화가 필요
    - 이러한 상호작용은 복잡

경쟁 조건

• 복수 개의 프로세스나 쓰레드가 동일한 데이터를 동시에 접근하는 경우, 접근 순서에 따라 실행결과가 달라질 수 있는 상황

상호 배제

• 두 개이상의 쓰레드가 같은 데이터를 동시에 접근할 때 문제점
  • 쓰레드가 데이터의 값을 수정하는 것을 마치기 전에, 문맥교환 발생 가능
  • 데이터가 모순된 상태에 빠질 가능성
• 동시 접근 가능 데이터에 대한 상호배제적 접근 제어
  • 한번에 하나의 쓰레드만 접근 가능
  • 다른 쓰레드는 해당 자원이 언락(unlock)될 때까지 대기
  • 순차적 접근 강제
  • 대기 시간이 지나치게 길지 않게 관리

생산자-소비자 관계 멀티쓰레딩

생산자-소비자 관계

• 동기화가 필요한 사례
• 생산자 쓰레드
  • 공유 객체에 데이터를 생성하여 저장
• 소비자 쓰레드
  • 공유 객체로 부터 데이터를 읽어가는 역할
  • 동기화가 되지 않으면 데이터 손상 우려

임계 구역

• 공유 데이터가 변경되는 프로그램 부분
• 한번에 하나의 쓰레드만 임계 구역에 머물 수 있음
• 임계 구역에서는 무한 반복이나 블록킹을 하지 않도록 신중

임계 구역 문제 해결방법에 대한 요구조건

• 상호 배제
  - 두 개 이상의 쓰레드(또는 프로세스)가 동시에 임계 구역에 있어서는 안됨
• 진행
  - 임계 구역 밖의 쓰레드가 다른 쓰레드의 임계 구역 진입을 막으면 안됨
• 한정된 대기
  - 어떤 쓰레드도 임계 구역으로 들어가는 것이 무한정 연기되면 안됨
  
• 실행속도 무관
  - 쓰레드의 상대적인 속도에 대한 가정을 하면 안됨
  

소프트웨어적 상호배제 구현

소프트웨어적인 상호배제 프리미티브 구현 방법

• enterMutualExclusion
• exitMutualExclusion

2개 쓰레드 상호배제 구현

• Dekker 알고리즘
• Peterson 알고리즘

다수 쓰레드 상호배제 구현

• Lamport 제과점 알고리즘

Dekker 알고리즘

• 2개의 플래그를 사용하여 구현
• 각각 임계영역에 들어갈 의향, 두 프로세스 사이의 우선권

f0 ← false
f1 ← false
turn ← 0   // or 1

 p0:                                 p1:
     f0 ← true                         f1 ← true
     while f1 {                          while f0 {
         if turn ≠ 0 {                      if turn ≠ 1 {
             f0 ← false                         f1 ← false
             while turn ≠ 0 {                  while turn ≠ 1 {
             }                                   }
             f0 ← true                          f1 ← true
         }                                   }
     }                                    }

    // 임계 구역                          // 임계 구역 
    ...                                   ...
    // 나머지 구역                        // 나머지 구역
   turn ← 1                             turn ← 0
   f0 ← false                           f1 ← false

Peterson 알고리즘

• Dekker 알고리즘보다 단순
• 2개의 플래그에 turn 변수 사용하여 구현

P0: flag[0] = true // 임계 구역 사용을 원함
     turn = 1 // 1번 프로세스에게 차례가 감
     while( flag[1] && turn == 1 )
     {
          // flag[1] 이 turn[1] 을 가지고 있으므로
          //현재 사용중임
          // 임계 구역이 사용 가능한지 계속 확인
     }// 임계 구역
     ...
    // 임계 구역의 끝
   flag[0] = false
   
P1: flag[1] = true
    turn = 0
    while( flag[0] && turn == 0 )
    {
         // 임계 구역이 사용 가능한지 계속 확인
    }// 임계 구역
    ...
    // 임계 구역의 끝
    flag[1] = false

Lamport 제과점 알고리즘

• 다수 쓰레드에 대한 임계 구역 지원
• 번호 ticket을 나누어줘서 대기 쓰레드의 큐 생성
• 가장 번호가 낮은 ticket을 가진 쓰레드 실행
• 중복된 번호가 있으면 쓰레드 ID를 비교 우선순위 결정

하드웨어적 상호배제 구현

하드웨어적인 상호배제 프리미티브 구현 방법

• 소프트웨어적 방법보다 성능 개선
• 방법
  • 인터럽트 거부
  • Test-and-Set 명령어
  • Swap 명령어
  • Compare-and-Exchange 명령어

인터럽트 거부 방법

• 임계구역에 들어가면서 인터럽트를 받지 않도록 하여 실행중인 쓰레드가 선점당하지 않도록 하고 임계구역을 벗어나면서 인터럽트를 받을 수 있도록 하는 것
• 단일 프로세서를 갖는 경우에는 적용 가능
• 교착상태 발생 가능
  - 임계구역에서 I/O 이벤트를 쓰레드가 대기하는 경우
• 거의 사용되지 않는 기술

원자적 명령어 사용 상호배제 프리미티브 구현

• 상호배제 프리미티브가 단번에(중간에 인터럽트 당하지 않고) 실행되도록 특수한 명령어를 사용하는 방법
• 이러한 명령어 자체만으로 상호배제를 보장하는 것은 아니고, 소프트웨어적으로 적절히 사용해야 함
  - 소프트웨어적인 방법에 비해 상호배제 구현을 단순화
  

Test-and-Set 명령어

testAndSet(a,b)

• a <- b
• b <- true
• read-modify-write를 원자적으로 수행하는 명령어

Swap 명령어

swap(a,b)

• a <-> b 두 변수의 값을 동시에 교환
• 많은 컴퓨터 구조에서 구현

CAS(Compare and Exchange / Compare and Swap) 명령어

• 특정 주소의 값이 주어진 값과 같으면 새로운 값으로 변경하는 원자적 명령어
• x86 (80486 이후)와 Itanium 구조에서 lock cmpxchg 명령어 지원
  • 원자적 명령어 형태로 CAS 실행
  • lock을 cmpxchg붙이면 이 명령어가 실행되는 시점에는 해당 쓰레드만 메모리 접근 가능, 타 쓰레드의 메모리 접근 불가

세마포어

• 상호배제를 지원하기 위한 두개의 원자적 함수로 조작되는 정수 변수

• Edsger W. Dijkstra가 제안

• 원자성을 만족하는 2가지 연산만 접근 가능

  • P 연산 / wait 연산, 임계구역 진입 전에 수행

    procedure P(S)
    	while S=0 do wait
    	S := S-1
    end
    

  • V 연산 / signal 연산, 임계 구역을 나올 때 수행

    procedure V(S)
    	S := S+1
    end 

Semaphore valueProduced = new Sempahore(0);
Semaphore valueConsumed = new Sempahore(1);
int sharedValue; // 생산자와 소비자가 공유하는 변수

// 생산자 쓰레드
void Producer( )
{
	int nextValueProduced;
	while (!done) {
		nextValueProduced = generateTheValue( );
		P(valueConsumed);
		sharedValue = nextValueProduced; // 임계 구역
		V(valueProduced);
	}
}

// 소비자 쓰레드
void Consumer( )
{
	int nextValueProduced;
	while (!done) {
		P(valueProduced);
		nextValueConsumed = sharedValue; // 임계 구역
		V(valueConsumed);
		processReceivedValue(nextValueConsumed);
	}
}