상호 배제
병행 실행
- 동시에 존재하는 쓰레드의 실행
- 비동기적 실행
- 독립적으로 실행되거나 협력하여 실행
- 때때로 서로 통신을 하거나 동기화가 필요
- 이러한 상호작용은 복잡
경쟁 조건
- 복수 개의 프로세스나 쓰레드가 동일한 데이터를 동시에 접근하는 경우, 접근 순서에 따라 실행결과가 달라질 수 있는 상황
상호 배제
- 두 개이상의 쓰레드가 같은 데이터를 동시에 접근할 때 문제점
- 쓰레드가 데이터의 값을 수정하는 것을 마치기 전에, 문맥교환 발생 가능
- 데이터가 모순된 상태에 빠질 가능성
- 동시 접근 가능 데이터에 대한 상호배제적 접근 제어
- 한번에 하나의 쓰레드만 접근 가능
- 다른 쓰레드는 해당 자원이 언락(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 ← falsePeterson 알고리즘
- 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] = falseLamport 제과점 알고리즘
- 다수 쓰레드에 대한 임계 구역 지원
- 번호 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);
}
}
계수 세마포어
-
1보다 큰 값으로 초기화 되는 세마포어
-
동일한 여러 개의 자원에 대한 접근 제어에 유용
- 자원을 사용할 때 값을 1 감소
- 자원을 반환할 때 값을 1 증가
- 자원이 없으면, 자원이 가용해질 때까지 쓰레드 중지(block)
P(S) { S--; if S < 0 // 이 프로세스를 재움 큐에 추가 (잠 듦) } V(S) { S++; if S <= 0 // 재움 큐로부터 프로세스를 제거 (깨어남) }
Reader-Writer 문제
- 복수의 reader와 writer의 저장공간을 공유하면서 데이터를 읽거나 기록
- 여러 reader가 동시에 저장공간 접근 가능
- 한 writer가 저장공간을 접근하고 있으면 다른 reader나 writer는 해당 저장공간에 접근 불가
모니터
- 순차적으로만 사용할 수 있는 공유 자원을 할당하는데 사용되는, 데이터와 프로시저, 초기화 코드를 포함하는 객체 또는 프로그램 구조(construct)
- 공유자원은 모니터 내에서만 접근 가능
- 데이터(객체)에 모니터를 결합하면, 동시에 두 개 이상의 쓰레드에 접근 할 수 없도록 잠금(lock) 기능을 제공
- 하나의 쓰레드만 모니터 내에 존재 가능
-상호배제 보장
조건변수
- 모니터 내부에 들어온 쓰레드들이, 다른 쓰레드가 모니터에 들어와 어떤 작업을 수행할 때 까지 대기해야하는 경우
- 쓰레드를 대기시키는 상황별로 조건변수 생성
- 각 조건변수는 별도 대기열 보유
- 조건 변수에 적용가능한 연산
- wait
- 현재 쓰레드를 중단하고 해당 조건변수 대기열에 들어감
- signal
- 해당 조건변수의 대기열에 있는 쓰레드 선택 실행 재개
- signal을 호출한 쓰레드는 대기열에 진입
- wait
Java 모니터
- 상호 배제와 동기화 제공
- 키워드 synchronized 사용
- 해당 객체에 대한 상호 배제 강제 - Java 객체는 잠금(lock) 보유
- synchronized 메소드를 호출하면, 잠금(lock) 확보
- synchronized 메소드가 끝나면서, 잠금(lock) 반환
- 잠금(lock)을 얻기 위해 대기하는 쓰레드는 해당 잠금(lock)의 진입 집합(entry set)에 추가
- 메소드 wait()
- 호출 쓰레드는 모니터에 대한 잠금(lock)을 반환하고, 대기 집합에 자신 추가, 쓰레드 상태는 대기(blocked)로 변경
- 조건변수를 명시적으로 지정하지 않음
- 호출 쓰레드는 모니터에 대한 잠금(lock)을 반환하고, 대기 집합에 자신 추가, 쓰레드 상태는 대기(blocked)로 변경
- 메소드 notify()
- 대기 집합에서 하나의 쓰레드를 진입 집합으로 이동시킴
- 해당 쓰레드의 상태는 준비(ready)로 변경
- 메소드 notifyAll()
- 대기 집합의 모든 쓰레드를 진입 집합으로 이동
wait(), notify(), nonifyAll()
- Object에 정의되어 있음
- 동기화 블록(synchronized 블록) 내에서만 사용 가능
- 보다 효율적인 동기화 지원
- 한 쓰레드가 객체에 잠금(lock)을 보유하고 오래 기다리는 대신
wait()를 호출해서 다른 쓰레드에게 제어권을 넘겨주고 대기상태로 기다리다가 다른 쓰레드에 의해서 notify()가 호출되면 다시 실행상태가 되도록 하는 것
- notifyAll()
- 모든 쓰레드를 깨우나 어차피 한번에 하나의 쓰레드만 객체를 사용할 수 있기 때문에 별 차이는 없음
- notify()에 의해 어떤 쓰레드가 깨워지게 될지는 알 수 없어서 우선순위가 높은 특정 쓰레드가 오랫동안 객체의 대기 풀에 머물 수 있음
- notifyAll()을 이용해서 모든 쓰레드를 깨워놓고 JVM의 쓰레드 스케줄러가 처리되도록 하는 것이 안전
으악