[OS] Synchronization

[ Background ]

프로세스는 다른 프로세스와 상호작용할 수 있으며, 이 과정에서 logical address space를 공유하거나 shared data가 생길 수 있다.(address space를 공유하는 경우는 멀티 스레딩에서, shared data가 생기는 경우는 프로세스끼리 통신할 때 발생한다) 공유 데이터에 여러 프로세스/스레드가 동시에 접근하여 값을 변경하게 되면 의도한 바와 다른 결과가 나타날 수 있다. 이를 data intetegrity(데이터 무결성)이 깨졌다, data inconsistency(데이터 불일치)가 발생했다고 표현한다. 데이터 무결성이란 데이터가 처리되는 모든 과정동안 데이터의 완전성, 정확성, 일치성이 보장됨을 의미한다. 데이터 무결성을 유지하기 위해서는 공유 데이터에 프로세스/스레드가 동시에 접근해 데이터를 조작하면 안되며 알맞은 순서대로 접근해야 한다. 이와 같이 프로세스/스레드가 어떤 순서로 공유 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 Race condition(경쟁 상태)라고 한다. race condition을 방지하기 위해 공유 데이터에 접근하는 부분을 프로세스/스레드들이 순차적으로 실행할 수 있도록 해야 하는데, 이를 process(or thread) synchronization(프로세스 동기화)라고 한다.

 

race condition이 발생할 수 있는 경우를 2가지로 나눌 수 있는데, concurrent execution과 parallel execution이다. 멀티프로그래밍으로 여러 프로세스가 동시에 실행되고 있으며, 이 프로세스들이 공유 데이터를 기반으로 상호작용하고 있다고 할 때, 만약 어떤 프로세스가 공유 데이터를 조작하고 있는 도중에 context switching이 일어나면 문제가 발생할 수 있다. 또한 멀티 코어 시스템에서 여러 프로세스가 각 코어에서 병렬적으로 실행되고 있는 상황에서 동시에 같은 데이터에 접근할 경우 역시 문제가 발생할 수 있다.

 

ex) producer-consumer problem

두 개의 프로세스가 현재 남아있는 아이템의 개수 'count' 데이터를 공유하고 있으며, 비동기적으로 실행하고 있다. 

생산자는 최대 BUFFER_SIZE만큼의 아이템을 생산하며, 소비자는 생산되어 있는 아이템을 소비한다.

#include <stdio.h>
#include <pthread.h>
#define BUFFER_SIZE 10000

/* shared data */
int count = 0;

/* producer - produce a new item, so 'count' increases */
void *producer(void *param) {
	for(int i=0; i<BUFFER_SIZE; i++)
		count++;
	pthread_exit(0);
}

/* consumer - consume the item, so 'count' decreases */
void *consumer(void *param) {
	for(int i=0; i<BUFFER_SIZE; i++)
		count--;
	pthread_exit(0);
}

int main() {
	pthread_t tid1, tid2;
	pthread_create(&tid1, NULL, producer, NULL);
	pthread_create(&tid2, NULL, consumer, NULL);
	pthread_join(tid1, NULL);
	pthread_join(tid2, NULL);
	printf("%d\n", count);
}

위 코드를 보면 두 개의 스레드가 생성되고 각각 producer와 consumer를 수행하며 count를 조작한다. 코드 상으로 보기에는 정상 작동할 것처럼 보이지만, 실제로 돌려보면 항상 0이 나오지 않는다.

 

왜 그럴까?

바로 count++; count--; 에서 문제가 발생한다. count++이 기계어로 변환되면 다음과 같아진다.

register1 = count
register1 = register1 + 1
count = register1

만약 두 번째 라인까지 실행하고 context switching이 발생하였다면, register1은 +1이 되었지만 이 변한 값이 count에 반영되지 않은 것이다. 물론 해당 스레드가 다시 CPU에 할당되면 그 다음 라인부터 실행하기 때문에 그때는 count가 바뀌게 된다. 하지만 만약 해당 프로세스와 context switching 된 다른 스레드에서 count값을 조작하였다면 어떻게 될까?

예를 들어 count가 5인 상황에서 스레드1이 count++을 실행하고, 기계어 기준 두 번째 라인에서 context switching이 발생하였다. 그렇다면 현재까지의 상태는 register1=6, count=5이다. CPU를 점유하게 된 새로운 스레드2에서 count--이 실행되었다. 현재 count=5이므로 count--에 의해 count=4가 될 것이다. 그 상태에서 다시 스레드1이 CPU를 점유하게 되고 다음 라인인 count=register1 부터 실행을 이어나간다. register1=6이었기 때문에 결국 count=6이 된다.

 

count++; count--; 가 순차적으로 진행이 되었다면 최종 count 값은 5가 되어야 하지만 다른 값이 나오게 되었다. 이와 같이 low level statement에서 의도하지 않은 순서대로 실행이 되어 공유 데이터의 무결성/일치성이 깨지는 경우를 race condition(경쟁 상태)라고 한다.

 

---

[ The Critical-Section Problem ]

다른 프로세스와 공유하는 데이터에 접근하고 조작하는 코드 부분을 critical section(임계 영역)이라고 한다. (위 접은 글 예시에서는 count++; count--;이 critical section에 해당한다) 추가적으로 critical section에 들어가기 위해 허가를 요청하는 부분을 entry section, critical section에서 나와 허가를 반납하는 부분을 exit section, 그 외의 나머지를 remainder section이라고 한다.

critical section problem을 해결하기 위해서는 두 개 이상의 프로세스가 critical section을 동시에 실행하지 못하도록 해야 한다. 이를 위해서는 다음 3가지 조건을 충족해야 한다.

• Mutual Exclusion(상호배제)
  : 어떤 프로세스가 critical section을 실행하고 있다면 다른 프로세스는 그 영역에 진입하지 못하도록 상호배제해야 한다.
• Progress(진행), avoid deadlock
  : critical section을 실행 중인 프로세스가 없다면 다른 프로세스가 그 영역에 진입할 수 있어야 한다. 하지만 여러 프로세스가 동시에 entry 허가를 요청하여 어떤 프로세스도 critical section으로 진입하지 못하고 무한 대기를 하게 되는 데드락이 발생할 수 있다. 이를 방지해야 한다.
• Bounded Waiting(한정 대기), avoid starvation
  : critical section에 들어가기 위해 entry를 요청하고 대기하게 되는데(이미 다른 프로세스가 진입한 상태라면) 이때 이 대기시간으 무한해서는 안된다. 대기 시간에 제한을 두어야 한다.

non-preemptive(비선점형) 커널에서는 critical section 문제가 발생하지 않는다. 프로세스가 스스로 다음 프로세스에게 CPU 점유를 넘기기 때문이다. 하지만 비선점형 스케줄링은 선점형에 비해 성능이 안좋기 때문에 잘 사용되지 않는다. 반면에 preemptive(선점형) 커널의 경우 OS가 강제로 실행 중이던 프로세스를 interrupt시키고 context switching을 할 수 있기 때문에 critical section 문제가 발생할 수 있다.

 

---

[ Peterson's Solution ]

• a classic software solution to the critical-section problem.
• 프로세스가 작업중인지를 저장하는 변수 flag와 critical section에 진입하고자 하는 프로세스를 가리키는 변수 turn을 만들어, 프로세스가 critical section에 진입하면 flag를 lock하고, 나오면 unlock한다.

ex) producer-consumer problem

위에서 발생했던 race condition을 Peterson's solution으로 해결해보자

#include <stdio.h>
#include <pthread.h>

#define BUFFER_SIZE 10000
#define true 1
#define false 0
#define prod 0
#define cons 1

/* shared data */
int count = 0;

/* variables to lock critical section in Peterson's solution */
int turn;
int flag[2]; 

/* producer - produce a new item, so 'count' increases */
void *producer(void *param) {
	for (int i=0; i<BUFFER_SIZE; i++) {
		/* entry */
    	flag[prod] = true;
    	turn = cons;
    	while (flag[cons] && turn==cons); // consumer in critical section, waiting
        
    	/* critical */
		count++;
        
    	/* exit */
    	flag[prod] = false;
	}
	pthread_exit(0);
}

/* consumer - consume the item, so 'count' decreases */
void *consumer(void *param) {
	for(int i=0; i<BUFFER_SIZE; i++) {
    	/* entry */
    	flag[cons] = true;
    	turn = prod;
    	while (flag[prod] && turn==prod); // producer in critical section, waiting
        
    	/* critical */
		count--;
        
    	/* exit */
    	flag[cons] = false;
	}
	pthread_exit(0);
}

int main() {
	pthread_t tid1, tid2;
	pthread_create(&tid1, NULL, producer, NULL);
	pthread_create(&tid2, NULL, consumer, NULL);
	pthread_join(tid1, NULL);
	pthread_join(tid2, NULL);
	printf("%d\n", count);
}

상호배제를 통해 이전과 달리 정상작동하게 된다. 하지만 이 코드 역시 여러 번 실행해보면 분명 이전보다는 적은 비율이고 차이도 적지만 오류가 발생한다. 이는 Peterson's solution이 완전히 정상적으로 작동할 것이라는 보장이 없기 때문이다. (단점 참고)

• 단점
  : no guarantees that Peterson's solution will work correctly since modern computers perform basic machine-language instructions such as load and store
  접은 글 예시에서 언급한 바와 같이 Peterson's solution은 정상작동을 보장하지 않는다. (물론 Peterson's solution을 사용할 경우 하지 않는 경우보다 확실하게 정상적으로 작동하는 비율이 늘고 이상한 값이 나오더라도 그 차이가 현저히 줄어든다) 이는 기계어 단계에서 entry section에 count++과 같이 context switching이 발생할 수 있는 부분이 있기 때문이다. (load, store 등..) 이를 해결하기 위해서는 결국 하드웨어적 접근이 필요하다.
• 장점
  : CSP을 해결하는 데에 있어 좋은 알고리즘적 방법이다.
  : mutual exclusion, progress, bounded waiting 3가지가 만족함을 증명할 수 있다. (증명 생략)

(+) Peterson's Algorithm 외에도 Dekker's Algorithm, Eisenberg and McGuire's Algorithm이 있다. 

 

---

[ Hardware Support ]

소프트웨어 레벨만으로는 race condition을 해결하는 데에 한계가 있었다. 기계어 단계에서 문제가 발생했기 때문이다. 따라서 하드웨어적 지원이 필요한데 3가지의 방법이 있다.

• memory barriers or fences
• hardware instructions
• atomic variables

Atomicity

Atomicity(원자성)이란 더 이상 쪼갤 수 없는 즉 interrupt할 수 없음을 의미한다.

 

atomic operation이란 더이상 나눌 수 없는 단위, interrupt할 수 없는 operation 단위이다. count++의 경우 3개의 기계어 instruction으로 분리되었으므로 atomic하지 않다. 그렇게 분리된 3개의 instruction을 atomic operation이라고 할 수 있다. 최근 컴퓨터 시스템은 이러한 atomic operation을 이용한 하드웨어 instruction을 제공하는데, test_and_set(), compare_and_swap() 이 그 예이다. 

 

atomic variable이란 atomic operation을 이용해 만들어진 기본 데이터 타입의 변수(integers, booleans, ...)이며, 어떤 한 변수에 대해 race condition이 발생했을 때 이를 상호배제하기 위해 사용된다.