[운영체제] 프로세스 동기화

1. Race Condition

Race Condition(경쟁 상태)

여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황

 

공유 데이터에 동시에 접근하는 행위는 데이터의 불일치 문제를 발생시킬 수 있음

Race condition을 막고 일관성을 유지하는 것이 필요

-> 협력 프로세스 간의 실행 순서를 정해주는 동기화(Synchronization)가 필요

 

대표적으로 다음 세 경우에서 Race Condition이 발생 가능

 

1. kernal 수행 중 인터럽스 발생 시

count++과 count--가 모두 반영되어 count가 초기값을 유지하는 것이 의도이다.

하지만 Load를 한 후에 Interrupt가 발생하면 Interrupt의 결과는 반영되지 않고 count++만 반영된다.

-> kernal mode의  수행이 끝나기 전에는 Interrupt를 받지 않도록 함으로써 해결 가능

 

2. Process가 system call을 하여 kernal mode로 실행 중에 context switch 발생 시

두 프로세스의 주소 공간에서 데이터를 공유하는 것은 아님.

다만, system call을 수행하는 동안 둘 다 kernal 주소 공간의 데이터에 접근.

따라서 kernal 주소 공간에서 작업을 수행하는 동안에 CPU를 빼앗을 시 Race Condition 발생

-> kernal mode 수행 중일 때 CPU가 선점되지 않게 하고, kernal mode에서 user mode로 돌아갈 때 선점되도록 함으로써 해결 가능

 

3. Multiprocesser에서 공유 메모리 내의 kernal data에 접근 시

어떤 CPU가 마지막으로 count를 저장했는지에 따라 결과값이 달라지는 상황.

Multiprocesser이기 때문에 Interrupt 제어로는 해결 불가능.

-> kernal 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해서만 lock/unlock을 하는 방식으로 해결 가능.

 

 

 

 

2. Critical Section

Critical Section(임계 구역)

코드 상에서 Race condition이 발생할 수 있는 특정 부분

(= 공유 데이터에 접근하는 코드 부분)

 

Critical Section으로 인해 발생하는 문제들을 해결하기 위해 다음 조건을 만족해야 함

 

1. Mutual Exclusion (상호 배제)

이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical Section에 진입 불가

 

2. Progress (진행)

Critical Section에서 작업 중인 프로세스가 없다면 Critical Section에 진입하고자 하는 프로세스가 존재하는 경우 진입 가능해야함

 

3. Bounded Waiting (한정 대기)

프로세스가 Critical Section에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 함. (무한정 기다리기 x)

 

 

 

 

3. Synchronization Algorithms

Critical Section 문제를 해결하기 위한 알고리즘

 

1. Algorithm 1

int turn을 사용하여 Pi가 turn == i일 때 Critical Section에 접근할 수 있는 코드

do {
	while(turn != i);
	critical section
	turn = j;
	remainder section
}while(1);

이 방식은 Mutual Exclusion은 만족하지만 Progress를 만족하지 못함.

만약 remainder section이 너무 길어서 수행중일 때 Pj가 수행을 한번 마치고 다시 Critical Section으로 진입하려고 한다면 turn == i 이기 때문에 진입할 수 없다.

-> Critical Section에 아무런 프로세스가 존재하지 않게 된다.

 

2. Algorithm 2

boolean flag[2]를 사용하여 Pi가 flag[i] == true일 때 Critical Section에 접근할 수 있는 코드

do {
	flag[i] = true;
	while(flag[j]);
	critical section
	flag[i] = false;
	remainder section
}while(1);

이 방식 또한 Mutual Exclusion은 만족하지만 Progress를 만족하지 못함.

두 프로세스가 flag = true를 수행하고 나면 두 프로세스 모두 무한히 Critical Section에 진입하지 못하고 기다리는 상황 발생

 

3. Algorithm 3

알고리즘 1과 2를 합쳐놓은 개념. turn 변수와 flag 변수를 동시에 사용함.

do {
	flag[i] = true;
	turn = j;
	while(flag[j] && turn == j);
	critical section
	flag[i] = false;
	remainder section
}while(1);

Pi 프로세스는 flag[i] = true로 바꾸면서 Critical Section 에 진입하려고 한다.

그리고 turn = j 로 바꿔주면서 상대방이 들어가게 한다.

만약 상대방이 들어가려는 상태(flag[j] == true) 상대방이 Critical Section에 들어가있으면(turn == j) 기다린다.

그렇지 않으면 Pi가 들어간다.

Critical Section을 빠져나오면 이제 들어가고 싶지 않다는 뜻으로 flag[i] = false로 바꾼다.

 

이 방식은 Mutual Exclusion, Progress, Bounded waiting 모두 만족한다.

하지만 Critical Section의 진입을 기다리면서 확인하는 데 CPU와 메모리를 계속 사용하는 Busy Waiting 문제가 발생한다.

 

 

 

 

4. Synchronization Hardware

하드웨어적 지원을 통해, 현재 상태를 확인하고 변경하는 Test & Modify를 atomic하게 수행할 수 있다면 Critical Section 문제를 간단히 해결 가능

 

boolean Test_and_Set(boolean *target){
	Boolean rv = *target;
	*target = TRUE;
	return rv;
}

do {
	while(Test_and_Set(&lock));
	critical section
	lock = false;
	remainder section
}while(1);

하지만 이런 하드웨어적 명령어는 Bounded wating 조건을 만족하지 못하는 단점이 존재.

 

 

 

5. Mutex Locks

Critical Section 문제를 해결하기 위한 소프트웨어 도구 중 가장 단순한 방법

Mutex Locks는 lock이 하나만 존재할 수 있는 locking 매커니즘

-> 이미 하나의 프로세스가 Critical Section에서 작업 중이면 다른 프로세스들은 Critical Section에 접근 불가

 

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

do {
	acquire lock
	critical section
	release lock
}while(1);

Lock을 걸고 푸는 동작은 하드웨어 방식처럼 atomic하게 수행되지만, Busy Waiting의 단점이 있음

(Critical Section에 프로세스가 존재할 때, 다른 프로세스들은 Critical Section에 계속해서 진입하려고 시도하기 때문에 CPU 낭비 발생)

 

다른 말로 Spin Lock이라고도 하는데, Critical Section 진입을 위한 대기 시간이 짧을 때, 즉 context switching 하는 비용보다 기다리는 게 더 효율적인 상황을 위해 고안된 방법이다.

단일 CPU 시스템에서는 어차피 lock을 갖고 있는 스레드를 풀어주기 위해 context switching이 일어나기 때문에 유용하지 않지만, 멀티프로세서 시스템에서는 종종 사용된다.

 

 

 

 

6. Semaphores

Semaphore는 Busy Waiting이 필요 없는 동기화 도구

여러 프로세스나 스레드가 Critical Section에 진입할 수 있는 Signaling 매커니즘

 

Semaphore는 카운터를 이용하여 동시에 자원에 접근할 수 있는 프로세스를 제한

주로 S라는 정수형 변수로 나타냄 (= 사용 가능한 자원의 개수)

 

Semaphore 변수는 오직 두 개의 atomic한 연산을 통해 접근 가능.

(한 프로세스가 Semaphore 변수를 수정할 때 다른 프로세스가 동시에 수정할 수 없음)

 

wait(S) { // originally called P(S)
	while(S<=0) do no-op;
	S--;
}

signal(S) { // originally called V(S)
	S++;
}

P(S)는 공유 데이터를 획득하는 연산, V(S)는 반납하는 연산.

 

 

Semaphore에는 두 종류가 있다.

1. Counting Semaphore: 정수 값의 범위가 0 이상으로 제한이 없다. 주로 자원의 개수를 세는 데 사용.

2. Binary Semaphore: 정수 값이 오직 0 또는 1이다. Mutex lock과 동일한 역할.

 

Semaphore는 다음과 같이 사용된다.

(int mutex는 초기 값 1로 지정)

do {
	P(mutex);
	critical section
	V(mutex);
	remainder section
}while(1);

하지만 이 방식은 Busy Waiting이 발생하므로 비효율적이다. 따라서 Block & Wakeup 방식을 사용한다.

이 방식은 Critical Section으로 진입이 실패한 프로세스를 기다리게 하지 않고 Block 시킨 뒤, Critical Section에 자리가 나면 다시 깨워줌으로써 Busy Waiting에서의 CPU 낭비 문제를 해결한다.

하지만 Critical Section이 매우 짧은 경우 Block & Wakeup의 오버헤드가 더 커질 수도 있다.

 

Block & Wakeup 구현일 위해 Semaphore를 다음과 같이 정의한다.

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

value는 Semaphore 변수를, L은 block 된 프로세스들이 기다리는 Queue다.

 

void wait(semaphore S) {
	S.value--;
	if(S.value < 0) {
		add this process to S.L;
		block();
	}
}

Block을 수행하면, 커널은 block을 호출한 프로세스를 suspend 시키고 해당 프로세스의 PCB를 wait queue에 넣는다.

 

void signal(semaphore S) {
	S.value++;
	if(S.value <= 0) {
		remove a process from S.L;
		wakeup(P);
	}
}

Wakeup을 수행하면 block 된 프로세스 P를 깨운 다음, 이 프로세스의 PCB를 Ready Queue로 이동시킨다.

signal 함수에서 S.value가 0 이하인 이유는 이전에 S.value++를 통해 자원을 내놓았는데 아직 0 이하라는 것은, 기다리고 있는 프로세스가 존재한다는 의미이기 때문이다.

 

wait나 signal 함수는 같은 Semaphore에 대해 두 프로세스가 동시에 실행할 수 없다.

만약 둘 중 하나를 수행하는 도중에 CPU가 선점(preempt)된다면 Critical Section 문제가 발생한다.