동기화

경쟁 상태

공유 메모리와 메시지 전달을 통해 프로세스 간 데이터 통신을 할 수 있다. 이 과정에서 동일한 메모리 영역에 서로 다른 두 프로세스가 접근하여 데이터를 읽고 쓰게 된다면, 데이터의 일관성이 깨지는 현상이 발생한다. 아래의 예시를 통해 이를 이해할 수 있다.

// 생산자
while (true) {
	/* produce an item in next_produced */
	
	while (count == BUFFER_SIZE)
		; /* do noting */
		
	buffer[in] = next_produced;
	in = (in + 1) % BUFFER_SIZE;
	count++;
}

// 소비자
while (true) {
	while (count == 0)
		; /* do nothing */
		
	next_consumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	count--;
	
	/* consume the item in next_consumed */
}

count 값을 증가시키고 감소시키는 생산자/소비자 코드이다. 생산자는 count가 버퍼 사이즈보다 작아지기 전까지 아무런 행동을 하지 않고, 소비자는 count가 0이 아닐때 까지 아무런 행동을 하지 않는다. 여기서 count는 전역 변수라고 가정을 하자.

현재 count의 값이 10일 때, 생산자와 소비자 코드를 병렬로 실행을 한다면 어떤 결과가 나올까? 10이 그대로 유지될 것으로 생각하지만, 실제로는 10이 나올 수도 있고 아닐 수도 있다. 이유는 증감 연산자에 있다.

증감 연산자(++, —)가 기계어로 컴파일됐을 때, 다음과 같은 내부 동작을 가지게 된다.

register_1 = count
register_1 = register_1 + 1
count = register_1

증감 연산자가 3개의 명령어로 나눠서 실행되고 있다. 이때, 각 명령어를 수행하는 중간중간 인터럽트가 발생하여 컨텍스트 스위칭이 발생하게 된다면 문제가 발생한다. register_1에서는 10의 값을 읽고 1을 증가시켰는데 인터럽트가 발생하여 소비자 코드가 실행이 됐다고 하자. 그럼 소비자 코드로 인해 count에는 9라는 값이 저장되고, 인터럽트가 발생하여 컨텍스트 스위칭이 발생하면 생산자 코드에서는 여전히 11이라는 값을 가지고 있기 때문에 count의 값이 11이 되버리는 문제가 발생한다.

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

임계 영역 문제

각 프로세스는 임계 영역이라는 코드 영역을 포함하고 있다. 이 영역은 다른 프로세스들이 접근하여 데이터를 업데이트 할 수 있다. 임계 영역의 중요한 특징은 임계 영역 내부에서 하나의 프로세스가 실행되고 있다면, 다른 프로세스들은 임계 영역에 접근할 수 없다.

그렇기 때문에, 임계 영역 문제는 서로 다른 프로세스들이 동시에 임계 영역에 접근하는 것을 막는 것이다. 임계 영역에 접근하기 위해서는 접근 권한을 받아야하는데, 이때 접근 권한을 요청하는 코드 부분을 진입 구역이라고 한다. 임계 영역에서 작업이 끝나고 나오는 부분을 퇴출 구역, 그 이외의 나머지 코드를 나무지 구역이라고 부른다.

임계 영역 문제에 대한 해결책은 아래 세 가지 요구 조건을 만족해야 한다.

• 상호 배제 : 프로세스가 자기의 임계 구역에서 실행된다면, 다른 프로세스는 그들 자신의 임계구역에서 실행될 수 없다.
• 진행 : 임계 영역에 접근하고자 하는 프로세스가 없거나, 임계 영역에서 실행을 마친 프로세스가 다른 프로세스의 진입을 무한히 지연시키지 않아야 한다.
• 한정된 대기 : 어떤 프로세스도 다른 스레드에 의해 무한히 대기 상태로 남겨져서는 안된다.

경쟁 상태 섹션에서 발생한 문제를 해결하기 위해서, 하나의 명령어가 실행될 동안 인터럽트를 막는 방법이 존재한다. 하지만, 이 경우는 단일 코어에서는 구현이 가능할지라도 멀티 코어 환경에서는 성능이 저하되는 등 추가적인 문제를 발생시킨다.

동기화

하드웨어 해결 방법

메모리 장벽

컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 한다. 일반적으로 두 가지 범주 중 하나에 속한다.

• 강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임
• 약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에게 즉시 보이지 않음

메모리 모델은 프로세서 유형에 따라 다르기 때문에 커널 개발자가 메모리 변경의 가시성에 대한 가정이 불가능하다. 이런 문제를 해결하기 위해 메모리 장벽을 사용한다. 메모리 장벽은 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장하는 명령어이다.

메모리 장벽은 매우 낮은 수준의 연산으로 간주하며 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다.

하드웨어 명령어

경쟁 상태 섹션에서 다룬 증감 연산자 내부 동작으로 인해 발생하는 데이터의 일관성을 해결할 수 있는 방법이다. 하나의 명령어가 원자적으로 실행되고 인터럽트가 발생하지 않아, 데이터의 일관성을 보장할 수 있다. test_and_set()과 compare_and_swap() 명령어를 통해 이를 보장한다.

boolean test_and_set(boolean *target) {
	boolean rv = *target;
	*target = true;
	
	return rv;
}

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	
	if (*value == expected)
		*value = new_value;
		
	return temp;
}

원자적 변수

위에서 다룬 compare_and_swap() 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않고, 임계 구역 문제 해결하는 다른 도구 구축을 위한 기본 구성요소로 사용된다. 그러한 도구 중 하나가 원자적 변수이다. 정수 및 boolean과 같은 기본 데이터 유형에 대한 원자적 연산을 제공하며, 단일 변수에 대한 데이터 경쟁에 대해 상호 배제를 보장하는 데 사용될 수 있다.

소프트웨어 해결 방법

뮤텍스 락

뮤텍스 락은 임계구역에 들어가기 전 획득해야하는 락이다. 임계구역에 들어가기 전, acquire() 호출을 통해 뮤텍스 락을 획득하고 나올 때 release() 호출을 통해 락을 반환한다. acquire()를 호출하는 부분을 acquire lock 영역, 임계 구역을 나오면서 release()를 호출하는 부분을 release lock 영역 그리고 나머지 영역을 remainder section이라고 한다.

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

release() {
	available = true;
}

위 두 함수는 원자적으로 수행되어야 하고 compare_and_swap()를 사용하여 구현될 수 있다. acquire() 함수를 통해 락을 획득하고자 바쁜 대기를 한다. 반복문을 통해 지속적으로 대기를 하며, 다른 프로세스들의 CPU 점유를 방해하고 CPU 사용률 저하로 이어지기 때문에 단점으로 작용한다.

바쁜 대기가 꼭 단점으로 작용하지는 않는다. 만약, 바쁜 대기를 하는 과정에서 락을 획득한다면 별도의 컨텍스트 스위칭 없이 CPU를 바로 점유할 수 있다. 바쁜 대기를 하지 않는다면 대기 큐로 옮기는 과정에 컨텍스트 스위칭, 대기 큐에서 레디 큐로 옮기는 과정에서 컨텍스 스위칭 총 2번의 컨텍스트 스위칭이 발생하기 때문에 오버헤드가 발생한다.

세마포

세마포는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산으로 접근할 수 있다.

wait(S) {
	while (S <= 0)
		; // busy wait
		
	S--;
}

signal(S) {
	S++;
}

wait() 함수는 세마포가 0 이상인지를 검사하고, 참일 경우 세마포를 1 감소시킨 후 락을 획득한다. signal() 함수는 락을 반환하는 과정에서 세마포를 1 증가시킨다. 두 함수는 모두 원자적으로 실행되어어야 하며, 동시에 동일한 세마포 값을 변경할 수 없다.

세마포는 크게 두 가지로 구분한다.

• 카운팅 세마포
  • 세마포의 값의 제한이 없다.
  • 세마포의 초기 값은 자원의 개수로 초기화된다.
• 이진 세마포
  • 세마포의 값이 0과 1사이의 값만 가진다.
  • 뮤텍스 랑과 유사하게 동작한다.

세마포도 뮤텍스와 동일하게 세마포의 값이 양수가 될 때까지 대기해야하는 문제가 있다. 뮤텍스의 바쁜 대기를 했지만, 세마포의 경우 위의 두 연산을 변경하여 바쁜 대기를 진행하지 않아도 된다.

• wait()
  • 세마포 값이 양수가 아닌 것이 발견되면, 프로세스는 자신을 일시 중지 시킨다.
  • 일시 중지 연산은 프로세스를 세마포에 연관된 대기 큐에 넣는다.
  • 프로세스의 상태를 대기 상태로 전환한다.
  • 이후 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행하기 위해 선택한다.
• signal()
  • 세마포를 반납하는 프로세스가 wakeup() 연산을 내부적으로 호출하여 대기중인 프로세스를 재시작한다.
  • 해당 연산은 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경한다.
  • 이후, 프로세스는 레디 큐에 넣어진다.

세마포는 한 개의 정수와 프로세스 리스트 list를 가진다. 프로세스가 세마포를 기다려야 한다면, 세마포의 프로세스 리스트에 추가된다.

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)
	}
}