여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황
여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것
공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행 가능한 영역
여러 프로세스/스레드 사이에서 공유 불가능한 자원의 동시 사용을 피하는 알고리즘으로 임계 영역에 구현된다.
상호 배제를 구현하기 위해 락을 사용하게 된다.
volatile int lock = 0; //global
void critical() {
while (test_and_set(&lock) == 1); // lock을 획득할 때까지 기다
// critical section
lock = 0;
}
int test_and_set(int* lockPtr) {
int oldLock = *lockPtr;
*lockPtr = 1;
return oldLock;
}
TestAndSet은 CPU atomic 명령어
실행 중간에 간섭 받거나 중단되지 않고 같은 메모리 영역에 대해 동시에 실행되지 않는다.
class Mutex {
int value = 1; // 임계 영역에 진입하기 위해 얻어야 하는 값
int guard = 0;
void lock() {
while(test_and_set(&guard));
if (value == 0) { // 다른 스레드가 락을 먼저 얻은 경우
// 현재 스레드를 큐에 넣음;
guard = 0;
// 그리고 스레드를 sleep
} else {
value = 0; // 락 취득
guard = 0;
}
}
void unlock() {
while (test_and_set(&guard));
if (큐에 하나라도 대기 중이라면) {
// 그 중 하나를 깨운다;
} else {
value = 1; // 락 반환
}
guard = 0;
}
}
value
라는 값을 얻어 임계 영역에 진입하게 된다.value
도 여러 스레드에서 동시에 값을 바꾸려는 또 하나의 임계 영역이기 때문에 while(test_and_set(&guard))
를 통해 한 스레드만 value
를 얻도록 해두었다.value
를 얻기 위해 기다리는 스레드는 while
를 돌면서 계속 CPU를 쓰면서 기다리는 것이 아닌 sleep을 하다가 깨어나야 할 때 깨어나게 된다.class Semaphore {
int value = 1; // 임계 영역에 진입하기 위해 얻어야 하는 값
int guard = 0;
void wait() {
while(test_and_set(&guard));
if (value == 0) { // 다른 스레드가 락을 먼저 얻은 경우
// 현재 스레드를 큐에 넣음;
guard = 0;
// 그리고 스레드를 sleep
} else {
value -= 1;
guard = 0;
}
}
void signal() {
while (test_and_set(&guard));
if (큐에 하나라도 대기 중이라면) {
// 그 중 하나를 깨워서 준비 시킨다;
} else {
value += 1;
}
guard = 0;
}
}
value
를 증가, 감소 시키는 형태이다. 초기 value
값에 따라 임계 영역에 들어오는 프로세스/스레드 수를 조정할 수 있다.
value=1
인 세마포를 바이너리 세마포라고 부르고 그 이상이면 카운팅 세마포라고 한다.wait()
를 하는 스레드와 siginal()
을 날리는 스레드는 다를 수 있다.unlock()
)할 지 알 수 있지만 세마포는 누가 signal()
을 호출할 지 알 수 없다.