경쟁상황 (Race Condition), 뮤텍스, 세마포어

경쟁 상황(Race Condition)이란?

동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 합니다.

경쟁 상황 예시

여러개의 프로세스가 어떤 자원을 공유하게 된다면 데이터의 무결성에 문제가 생길 수 있습니다.

static int count;

func thread_1() {
	for (int i = 0; i < 10000000; i++) {
		count++;
	}
}

func thread_2() {
	for (int i = 0; i < 10000000; i++) {
		count--;
	}
}

위의 코드처럼 서로 다른 쓰레드가 count라는 하나의 변수에 접근한다고 가정해봅시다.

위의 코드의 값은 같은 횟수만큼 더하고 같은 횟수만큼 빼서 count의 값이 0이 될 것이라고 예상됩니다.

하지만 실제로 실행시켜보면 알 수 없는 값이 나오는 것을 볼 수 있습니다.

이런 결과가 나오는 이유는 다음과 같습니다.

프로세스 A와 B가 준비큐에 존재한다고 가정해봅시다.

먼저 기계어에서 count가 연산되는 과정은 다음과 같이 구현됩니다.

1. 레지스터에 count 변수 값 할당
2. 레지스터가 값을 연산
3. 레지스터가 카운터에 값을 반환

만약 2번 과정중에 컨텍스트 스위칭이 발생하여 프로세스 B가 실행된다고 가정해봅시다.

count의 값이 변하지 않은 상태에서 레지스터에 count가 할당되고 해당 레지스터가 값을 연산한 후 count의 값이 반환될 것입니다.

이때 프로세스 A가 다시 실행이 된다면 연산했던 값이 count에 반환되게 됩니다.

즉, 프로세스 B에서 연산했던 값이 사라지는 증상을 볼 수 있습니다.

이런 상황을 경쟁 상황이라하며, 이를 막기 위해서는 한번에 하나의 프로세스만 리소스에 접근할 수 있도록 보장해야 합니다.

이러한 보장을 위해 어떤 형태로든 프로세스들이 동기화될 수 있도록 만들어 주어야합니다.

임계구역(critical section)

임계 구역이란 파일, 입출력, 공유 데이터 등 원자적으로 실행할 필요가 있는 명령문 또는 코드의 일부 영역을 의미합니다.

static int count;

func thread_1() {
	
	for (int i = 0; i < 10000000; i++) {
		count++; // 임계구역
	}
}

func thread_2() {
	for (int i = 0; i < 10000000; i++) {
		count--; // 임계구역
	}
}

프로세스의 동기화문제는 임계구역 문제로부터 시작하게 됩니다.

각 프로세스가 임계 구역이 존재하는 상태일때 동기화문제(race condition)가 발생하는 것을 방지하기 위해 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 임계구역에 접근할 수 없어야 합니다.

한 프로세스가 임계구역에서 명령을 수행하는 동안 임계구역에 들어오지 않도록 하기 위해 임계구역에 접근해야 하는 프로세스는 자신의 임계구역으로 진입해야 할 때 진입 허가를 요청하게 됩니다.

이러한 요청을 구현하는 부분을 진입 구역(entry section)이라고 부릅니다.

그리고 임계구역 이후에 퇴출 구역(exit section)이 따라올 수 있습니다.

임계구역, 진입구역, 퇴출구역을 제외한 나머지 부분을 나머지 구역(remainder section)이라고 할 수 있습니다.

func thread1() {
	// remainder section
	// entry section
		// critical section
	// exit section
	// remainder section
}

임계 구역 문제를 해결하기 위한 조건

1. 상호 배제(mutral exclusion) : 프로세스 A가 자기의 임계구역에서 실행된다면 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없습니다.
2. 진행(progress) : 자기의 임계구역에서 실행되는 프로세스가 없고 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지 결정하는데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없습니다.
3. 한정된 대기(bounded waiting) : 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용하는 횟수에 한계가 있어야 합니다.

임계구역문제 해결 방법(sigle core)

• 공유된 자원을 사용할 때 인터럽트가 발생하지 않도록 합니다.
• 단, 멀티코어 환경일 경우 다른 코어도 전부 인터럽트를 발생시키지 않게 되어 효율성이 매우 떨어집니다.

비선점형 커널과 선점형 커널

• 비선점형 커널
  • 한 프로세스가 종료될 때까지 점유하기 때문에 경쟁 상황이 발생하지 않습니다. 즉, 임계영역을 만들 필요가 없습니다.
• 선점형 커널
  • 계속해서 컨텍스트 스위칭이 일어나기 때문에 경쟁 상황이 발생할 수 있습니다. 경쟁상황을 피하기 위해 임계영역을 만들어 문제가 생기지 않도록 막아야 합니다.

 

하지만 비선점형 커널과 선점형 커널 중 선점형 커널이 선호되는데 하나의 프로세스가 긴 시간동안 실행되 다른 프로세스가 실행되지 않는 상황을 피할 수 있기 때문에 선점형 커널이 선호됩니다.

 

임계영역의 소프트웨어적 해결방안

• Dekker's 알고리즘
  • flag를 이용해서 임계영역에 들어갈 프로세스를 결정하는 방식의 알고리즘입니다.
• Eisenberg and McGuire's 알고리즘
  • 여러개의 프로세스가 최대 n - 1번 시도 이내에 임계 구역에 들어갈 수 있게 보장하는 알고리즘입니다.
• Bakery Algorithm
  • 여러개의 프로세스가 동작할 때 프로세스마다 번호를 부여해 가장 낮은 번호를 받은 프로세스가 가장 먼저 임계영역에 들어갈 수 있습니다.
• Peterson's Algorithm
  • flag를 이용해서 임계영역에 들어갈 프로세스를 결정하는 방식의 알고리즘입니다.

Peterson’s Algorithm

flag와 turn이라는 변수로 임계영역에 들어갈 프로세스(혹은 스레드)를 결정하는 방식입니다.

Dekker's 알고리즘과 상당히 유사하지만 상대방에게 진입기회를 양보한다는 차이가 있습니다.

flag 값은 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수이고, turn 변수는 누가 임계영역에 들어갈 차례인지 나타내는 변수입니다.

• 문제점

피터슨 알고리즘은 현대 컴퓨터에서 정상 작동하지 않는 문제점이 있습니다.

현대 컴퓨터의 구조가 load와 store 같은 기본적인 기계어를 수행하는 방식 때문에 Peterson의 해결안이 이러한 구조에서 올바르게 실행된다고 보장할 수 없습니다.

하지만 임계영역을 문제를 해결하는 방법인 상호배제, 진행, 한정 대기를 하는 방법을 쉽게 이해할 수 있도록 해줍니다.

 

임계영역의 하드웨어 기반의 해결방법

• 메모리 장벽 (memory barriers)
• 하드웨어 명령어 (hardware instructions)
• 원자적 변수 (atomic variables)

메모리 장벽

컴퓨터가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 합니다.

메모리 모델은 일반적으로 두 가지 범주 중에 하나에 속합니다.

• 강한 순서 : 한 프로세스의 메모리 변경 결과가 다른 모든 프로세스에 즉시 보입니다.
• 약한 순서 : 한 프로세스의 메모리 변경 결과가 다른 프로세스에 즉시 보이지 않습니다.

메모리 모델은 프로세서 유형에 따라 다르므로 커널 개발자는 공유 메모리에서 메모리의 변경 사항을 알 수 없습니다.

이 문제를 해결하기 위해 컴퓨터는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세스에서 실행중인 쓰레드에 메모리 변경 사항이 보이는 것을 보장합니다.

이러한 명령어를 메모리 장벽(memory barriers) 또는 메모리 펜스(memory fences)라고 합니다.

 

하드웨어 명령어

하나의 값을 검사하고 변경하거나, 두 값을 원자적으로 교환할 수 있는, 즉 인터럽트되지 않는 하나의 단위로서 특별한 하드웨어 명령어들을 제공합니다.

 

원자적 변수

원자적(더이상 인터럽트 할 수 없는 최소의 단위)인 연산을 제공하는 변수를 의미합니다.

 

뮤텍스 (Mutex)

동기화를 위한 가장 간단한 도구로 임계영역을 보호해주고 경쟁상황이 발생하는 것을 막아줍니다.

프로세스는 임계영역에 들어가기전에 lock을 걸고(acquire lock) 임계영역에 벗어나면 lock을 해제합니다.(release lock)

acquire()로 lock을 걸고 releases()로 lock을 해제합니다.

avaliable : 잠금 상태를 확인하는 boolean 변수를 사용합니다.

while (true) {
	acquire lock
		critical section
	releases lock
		remainder section
}

• acquire() 구현

acquire() {
	while (!available)
		; /* busy wait */
	available = false;
}

• releases() 구현

 releases() {
	 available = true;
 }

acquire() 와 releases()는 원자적으로 구현되어야 합니다. (원자적이지 않으면 context switch가 일어나면서 값이 이상하게 나올 수 있음)

compare_and_swap 방식으로 구현할 수 있습니다.

 

busy waiting

• 어떤 프로세스가 임계영역에 진입하기 위해 계속해서 acquire()를 호출합니다.
• busy wating 방식은 계속해서 루프를 돌며 기다리기 때문에 멀티프로그래밍 환경에서 CPU 처리시간을 낭비하게 됩니다.

Spinlock

• busy waiting을 사용하는 mutex lock을 Spinlock이라고 합니다.
• 사용가능한 상태가 될때까지 계속해서 프로세스를 회전합니다.
• busy wating 상태로 대기하다가 권한을 얻는 순간 바로 작업이 수행할 수 있기 때문에 context switch를 하면서 소모되는 시간이 줄어들지만 CPU를 선점하는 동안 사실상 아무 동작을 하고 있지 않는 것이기 때문에 시간을 낭비하게 됩니다.

세마포어 (Semaphore)

• 공유된 자원의 데이터 혹은 임계영역 등에 프로세스나 스레드를 나타내는 값을 두어서 상호배제를 구현할 수 있습니다.

세마포어는 두 가지 원자연산을 통해서만 접근할 수 있는 정수 변수입니다.

wait(), signal() or P() V()로 표현합니다.

wait(s) {
	while (s <= 0);
}
s--;

signal(s) {
	s++;
}

세마포어의 종류

• Binary Semaphore(이진 세마포어)
  • 세마포어의 값으로 0또는 1을 가집니다. 뮤텍스와 비슷한 방식입니다.
• counting semaphore
  • 초기값은 할당가능한 자원의 수로 정해지며, 세마포어의 값의 범위는 정해져 있지 않습니다.

카운팅 세마포어

• 할당가능한 자원수로 세마포어 변수를 초기화합니다.
• 프로세스가 자원을 사용하려고 하면 wait()을 호출하여 값을 1 감소시킵니다.
• 프로세스가 자원을 다 사용하면 signal()을 호출하여 값을 다시 증가시킵니다.

typedef struct {
	int value;
	struct process *list;
} semaphore;

wait(semaphore *s) {
	s->value--;
	if (s->value < 0) {
		add this process to s->list
		sleep();
	}
}

signal(semaphore *s) {
	s->value++;
	if (s->value <= 0) {
		remove a process P from S->list;
		wakeup(P);
	}
}

세마포어 사용의 어려움

세마포어는 동기화에 편리하고 효과적인 방법이지만 특정 시퀀스가 발생하는 경우 타이밍 오류가 발생할 수 있습니다.

특정 시퀀스는 항상 일어나지도 않고 잡기도 어렵습니다.

예를 들어 이진 세마포어에서 wait()후 signal()을 지키지 않으면 임계영역에 두개의 프로세스가 들어가서 문제가 생길 수 있습니다.

signal(mutex);
	critical section
wait(mutex);

wait(mutex);
	critical section
wait(mutex);

세마포어와 뮤텍스 같은 경우 실수가 발생할 위험이 커서 이 실수를 줄이고자 monitor 라는 방법을 사용하게 됩니다.

모니터 (monitor)

모니터 타입은 상호 배제를 하기 위한 하나의 타입입니다. 자바의 경우 클래스라고 생각하면 됩니다.

monitor monitor name

function P1(...) {
	// code
}

function P2(...) {
	// code
}

function Pn(...) {
	// code
}

init_code(...) {
	// code
}

모니터는 다음과 같은 흐름을 가집니다.

condition value

모니터 자체로는 프로세스 동기화를 모델링하기에 충분하지 않기 때문에 condition value 를 선언하여 추가해줍니다.

컨디션 변수는 어떤 실행을 상태가 원하는 것과 다를 때 조건이 참이 되기를 기다립니다.

condition x, y;
x.wait();
x.signal();
y.wait();
y.signal()

java monitor

java는 스레드 동기화를 위해 모니터와 같은 것을 제공합니다.

모니터 락이라고 불립니다.

자바에서 동기화 하기 위해서는 synchronized 키워드와 wait() notify 메서드를 알고 있으면 됩니다.

syncronized keyword

임계영역에 해당하는 코드 블록을 선언할 때 사용하는 자바 키워드입니다.

해당 코드 블록(임계영역)에는 모니터락을 획득해야 진입 가능합니다.

모니터락을 가진 객체 인스턴스를 지정할 수 있습니다.

메서드에 선언하면 메서드 코드 블록 전체가 임계영역으로 지정됨

이 때, 모니터락을 가진 객체 인스턴스는 this 객체 인스턴스입니다.

synchronized (object) {
	// critical section
}

public syncronized void add() {
	// critical section
}

wait() and notify() 메서드

java.lang.Object 클래스에 선언된 모든 자바 객체가 가지고 있는 메서드입니다.

쓰레드가 어떤 객체의 wait() 메서드를 호출하면 해당 객체의 모니터락을 획득하기 위해 대기 상태로 진입합니다.

쓰레드가 어떤 객체의 notify() 메서드를 호출하면 해당 객체 모니터에 대기 중인 쓰레드 하나를 깨웁니다.

notify() 대신에 notifyAll() 메서드를 호출하면 해당 객체 모니터에 대기중인 쓰레드 전부를 깨웁니다.

라이브니스 (liveness)

임계영역에 대한 해결방안으로 알아본 뮤텍스, 세마포어, 모니터는 상호배제만 해결이 가능합니다.

Liveness(라이브니스)는 진행(Progress), 한정대기(bounded-waiting)문제를 해결할 수 있습니다.

교착상태(deadlock)

두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 무한 대기에 빠지는 상황을 말합니다.

우선순위 역전 (Priority Inversion)

높은 우선순위를 가지는 프로세스가 낮은 우선순위를 가진 프로세스보다 늦게 실행되는 현상입니다.

예를들어, 프로세스 3개가 존재하고 P1 > P2 > P3와 같은 우선순위를 가지고 있다고 할때, P1과 P3는 실행시 공유자원에 접근을 해야되고 P2는 공유자원에 접근하지 않는다고 합시다.

가장 먼저 P3가 실행된다고 하면 공유자원 접근을 위해 lock을 획득하고 다른 프로세스 이 자원에 접근할 수 없게됩니다.

이 때 P1이 공유자원의 접근이 필요해지면 lock을 획득해야 하는데 이미 P3가 점유하고 있으므로 대기 하게 됩니다.

이 때 공유자원이 필요없는 P2가 실행하려고 했을 때 P3보다 우선순위가 높기 때문에 P3를 대기시키고 P2가 실행됩니다.

P2의 작업이 완료되면 P3는 다시 작업을 시작하고 P3가 종료되면 P1이 실행됩니다.

이런식으로 우선순위가 역전되는 상황을 Priority Inversion(우선 순위 역전)이라고 합니다.

정리

• 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 합니다.
• 경쟁 상황은 여러개의 프로세스가 하나의 공유 자원에 접근하는 상황에서 컨텍스트 스위칭이 일어났을 때 발생합니다.
• 임계구역이란 파일, 입출력, 공유 데이터 등 원자적으로 실행할 필요가 있는 명령문 또는 코드의 일부 영역을 의미합니다.
• 임계 구역 문제를 해결하기 위해서는 상호배제, 진행, 한정된 대기를 만족시켜야 합니다.
• 커널은 비선점형과 선점형 커널로 나뉩니다.
• 임계 영역을 해결하기 위한 소프트웨어 적인 방안으로 Dekker’s 알고리즘, Eisenberg and McGuire’s 알고리즘, Bakery Algorithm, Peterson’s Algorithm이 존재합니다.
• Peterson’s Algorithm은 flag와 turn이라는 변수로 임계영역에 들어갈 프로세스(혹은 스레드)를 결정하는 방식입니다. 단, 현대 컴퓨터에서는 정상적으로 작동하지 않습니다.
• 임계영역을 해결하기 위한 하드웨어 적인 방법으로는 메모리 장벽, 하드웨어 명령어, 원자적 변수가 존재합니다.
• 뮤텍스는 동기화를 위한 가장 간단한 도구로 임계영역 보호해주고 경쟁상황이 발생하는 것을 막아줍니다.
• 어떤 프로세스가 임계영역에 진입하기 위해서 계속해서 대기하고 있는 상태를 busy waiting이라고 합니다.
• busy waiting을 사용하는 mutex를 Spinlock이라고 합니다.
• 세마포어는 공유된 자원의 데이터 혹은 임계영역에 프로세스나 스레드를 나타내는 값을 두어 구현하는 방식으로, 이진 세마포어와 카운팅 세마포어가 있습니다.
• 모니터는 상호 배제를 하기 위한 하나의 타입으로, 자바의 경우 클래스라고 생각하면 됩니다.
• 라이브니스는 상호 배제를 위한 방법으로 진행, 한정대기 문제를 해결할 수 있습니다.
• **교착상태(deadlock)**는 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태로, 무한대기에 빠지게 됩니다.
• 우선 순위 역전은 높은 우선순위를 가지는 프로세스가 낮은 우선순위를 가진 프로세스보다 늦게 실행되는 상태입니다.