[OS] 5. 비동기 병행 실행(Asynchronous Concurrent Execution)

4/6

 

Part 1.

병행 실행(concurrent execution)

• 동시에 존재하는 쓰레드 실행
• 비동기적(asynchronous) 실행
  • 독립적으로 실행되거나 협력하여 실행
  • 때때로 통신이나 동기화(synchronization) 필요
• 경쟁조건(race condition)
  • 복수 개의 프로세스나 쓰레드가 동일한 데이터를 동시에 접근하는 경우 순서에 따라 결과가 달라질 수 있다.

상호 배제(mutual exclusion, mutex)

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

 

생산자-소비자 관계(producer-consumer relationship) 멀티쓰레딩

• 동기화(synchronization)가 필요한 사례
• 생산자(producer): 공유객체(shared object)에 데이터를 생성하여 저장
• 소비자(consumer) 쓰레드: 공유 객체에서 데이터를 읽어감. 동기화가 안되면 데이터 corruption 우려.
• 공유하는 단일 정수(single integer) 관리 클래스
• 동기화를하지 않고 공유 객체를 변경하는 쓰레드를 시작하는 클래스
• 생산자와 소비자 모두 Thread에서 extend하여 사용

임계구역(critical section)

• 공유 데이터가 변경되는 프로그램 부분
• 한번에 하나의 쓰레드만 머물 수 있음
• 무한 반복이나 블록킹을 하지 않게 신중해야함.
• 상호 배제가 필요한 상황에서 하나만 넣어서 실행.(마치 왕복 1차선)
• 요구조건 4가지
  • 상호 배제(mutex): 두개 이상의 쓰레드가 동시에 있어서는 안됨.
  • 진행(progress): 임계 구역 밖의 쓰레드가 다른 쓰레드의 진입을 막으면 안됨.
  • 한정된 대기(bounded waiting): 어떤 쓰레드도 진입이 무한정 연기되면 안됨.
  • 실행속도 무관: 상대적인 속도에 대한 가정은 하면 안됨.

 

Part 2.

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

• enterMutualExclusion(진입)
• exitMutualExclusion(탈출)

2개 쓰레드 상호 배제 구현

• Dekker 알고리즘
  • 누가 우선인지 확인하여, 상대가 우선이면, 나올때 까지 대기하였다가 실행.
• Peterson 알고리즘
  • 우선권을 넘기고 일단 진입시킴.

다수 쓰레드 상호 배제 구현

• Lamport 제과점 알고리즘
  • 다수 쓰레드에 대한 임계구역.
  • 번호 ticket을 활용하여 대기 쓰레드의 큐 생성
  • 가장 번호가 낮은 것부터 실행.
  • 중복된 번호에서는 쓰레드 ID 비교

 

하드웨어적 상호배제 구현

-소프트웨어적 방법보다 성능 개선

• 인터럽트 거부(disable)
  • 임계구역에 들어가면서 인터럽트를 받지 않게하여 실행중인 쓰레드가 선점당하지 않게 하고, 임계구역을 벗어나면서 인터럽트를 받을 수 있게 함
  • 단일 프로세서의 경우 적용 가능
  • 교착상태(deadlock) 발생 가능
  • 거의 사용되지 않는 기술.(시스템 죽어버리면 끝나기 때문에)
• 원자적명령어(atomic instruction) 사용 상호배제 프리미티브 구현
  • 상호배제 프리미티브가 단번에 실행되도록 특수한 명령어 사용
  • 상호배제를 명령어만으로 보장하진 않고, 소프트웨어적으로 적절히 사용해야함.(구현 단순화)
• Test-and-Set 명령어
  • testAndSet(a, b); a<-b; b<-true;
  • read-modify-write를 원자적으로 수행하는 명령어
• Swap 명령
  • 두 변수값을 동시에 교환
  • 많은 컴퓨터 구조에서 구현
• Compare-and-Exchange 명령어(CAS, Compare and Swap)
  • 특정 주소의 값이 주어진 값과 같으면 새로운 값으로 변경
  • lock cmpxchg 명령어 지원
    • 이 명령어 실행 시점에는 해당 쓰레드만 메모리 접근 가능.(경쟁조건 X)

 

Part 3.

세마포어(semaphore)

• 상호배제를 지원하기 위한 두 개의 원자적 함수로 조작되는 정수 변수
• Edsger W. Dijkstra가 제안[1]
• 원자성을 만족하는 2가지 연산만 가능.
  • P연산((네)proberen; try) //wait
  • V연산((네)verhogen; increase) //signal

세마포어를 이용한 생산자/소비자 관계 구현

 

계수 세마포어(counting semaphore)

• 1보다 큰 값으로 초기화 되는 세마포어
• 동일한 여러 개의 자원에 대한 접근 제어에 유용
  • 자원 사용시 값 1 감소
  • 자원 반환시 값 1 증가
  • 자원이 없으면 가용할 때까지 쓰레드 중지(block)

Reader-Writer문제

• 복수의 reader와 writer의 저장공간을 공유하면서 데이터를 읽거나 기록
• 여러 reader가 동시에 저장공간 접근 가능
• 한 writer가 저장공간을 접근하면 다른 reader나 writer는 저장공간 접근 불가

 

모니터(monitor)

• 순차적으로 사용할 수 있는 공유 자원을 할당하는데에 사용되는, 데이터와 프로시저, 초기화코드를 포함하는 객체 또는 프로그램 구조
• 데이터(객체)에 모니터를 결합하면 동시에 두개 이상의 쓰레드에 접근할 수 없게 lock 기능을 제공
• 하나의 쓰레드만 모니터 내에 존재 가능(상호배제 보장)

조건변수(condition variable)

• 모니터 내부에 들어온 쓰레드들이 다른 쓰레드가 작업을 수행할 때까지 대기하는 경우
• 쓰레드를 대기시키는 상황 별로 조건변수 생성
• 각 조건변수는 별도 대기열(queue) 보유
• 조건 변수에 적용가능한 연산
  • wait(현재 쓰레드를 중단하고 해당 조건변수 대기열로 들어감)
  • signal(해당 조건변수의 대기열에 있는 쓰레드 선택 실행 재개, 호출한 쓰레드는 대기열에 진입)

JAVA 모니터(사실 이름은 모니터가 아님)

• 상호배제와 동기화 제공
• 키워드 synchronized 사용(해당 객체에 대한 상호 배제 강제)
• Java 객체는 lock 보유
• 메소드를 호출하면 lock 확보
• 메소드가 끝나면서 lock 반환
• lock을 얻기 위해 대기하느 쓰레드는 해당 lock 의 진입 집합에 포함
• 메소드 3개(Object에 기록되어있음, 동기화블록 내에서만 사용 가능)
  • wait(): 호출 쓰레드는 모니터에 대한 lock 반환, 대기 집합에 자신 추가, 쓰레드 상태는 blocked로 변경.(조건변수 명시적 지정X)
  • notify(): 대기 집합에서 하나의 쓰레드를 진입 집합으로.(쓰레드는 준비상태로 변경)[2]
  • notifyAll(): 대기집합의 모든 쓰레드를 진입 집합으로

 

---

 

[1] 그 다이크스트라 알고리즘의 개발자이시다.

[2] 사실 하나씩 해도 큰 의미가 없어서(하나씩만 객체를 사용할 수 있으므로+ 어떤 쓰레드가 갈지 모름) notifyAll()을 이용하여 다 깨우고, JVM의 스케줄러에게 처리시키는게 안전하다.