Process Synchronization(1)

Background.

공유하는 변수(ex.전역변수)에 동시에 접근할 때, 데이터 일관성(Data Inconsistency)의 문제가 발생할 수 있다!

따라서 공유하는 변수에 접근하는 작업을 순서화,동기화 시켜야 한다. → Process Synchronization

Producer(Data를 제공하는 Process)와 Consumer(Data를 받는 Process) 관계에서 Counter라는 전역변수를 사용함으로써 둘 사이 버퍼공간을 모두 사용할 수 있다.

Producer는 Counter++;

Consumer는 Counter--;

Producer와 Consumer는 Counter를 공유하므로 Counter라는 전역변수에 대한 데이터 접근에 순서화, 동기화를 해주어야 한다.

→ Race Condition이 발생하면 안된다!

🛑 Race Condition : Instruction이 실행되는 순서에 따라 변수의 값이 달라지는 것.

Race Condition Example

// Assembler Language

// counter를 증가시키는 표현. 
register1 = count
register1 = register1 + 1
count = register1

// counter를 감소시키는 표현.
register2 = count
register2 = register2 - 1
count = register2

// Race Condition이 발생하는 경우 -> Interleaving하는 경우.
// counter++;과 counter--;가 맞물려서 돌아간다.
register1 = count
register1 = register1 + 1 // register1 = 6
register2 = count
register2 = register2 + 1 // register2 = 4
count = register1 // count = 6
count = register2 // count = 4

위의 코드에서 마지막으로 어떤 Instruction이 실행되는지에 따라 count의 값이 달라지는 것을 알 수 있다.

용어설명

Critical Section : 매우 중요한 부분. 공유하는 변수의 값을 변경하는 부분.

Entry Section : Critical Section에 진입하기 위한 부분.

Exit Section : Critical Section에서 나오는 부분.

🛑 Process들은 actions을 동기화, 순서화 하기위해 몇몇 변수를 공유하기도 한다.

Process Synchronization Solution

Solution이 만족해야하는 세가지 조건

1. Mutual Exclusion : 한번에 하나의 Process만 Critical Section에 접근이 가능해야한다.
2. Progress : Critical Section에 들어가고 싶은 Process들 중 Process를 선택하는 작업이 무한히 연기되어서는 안된다. -> Critical Section이 비어있으면 들어갈 수 있어야 한다.
3. Bounded Waiting : Critical Section에 들어가고 싶은 Process가 언젠가는 Critical Section에 들어갈 수 있어야 한다.

🛑 Process들은 일을 처리하는데 시간이 걸리고 그 시간은 프로세스간에 동일하다고 가정한다.

여러가지 솔루션

Software Solution

1. Peterson's Solution

두개의 Process 사이에만 적용이 가능하다.

Process의 LOAD와 STORE 명령은 atomic하다고 가정한다.

⭐ Atomic : Instruction이 Interrupt에 의해 방해받지 않고 종료될 때 까지 실행된다.

int형 turn : Critical Section에 들어갈 차례(순서)를 알려주는 변수

Boolean 형 flag[2] : 들어가길 원하는지 알려주는 변수. flag[i] = True이면 Process[i]는 Ready상태이다.

• 방식.

do{
	//Entry Section
	flag[i] = TRUE; // Process[i]는 Ready되었다.
	turn = j;
	while(flag[j] && turn ==j); // wait until Critical Section Empty

	//-----
	//Critical Section
	//do Something
	//-----

	//Exit Section
	flag[i] = FALSE; // Exit

}while(TRUE);

Peterson’s Solution은

turn이 하나의 값( i or j)만 가질 수 있어 Mutual Exclusion을 만족한다.

While(flag[j] && turn==j); 를 통해 기다리고, Exit할 때 Flag[i] = FALSE;를 하며 Progress와 Bounded Waiting을 만족한다.

2. Bakery Algorithm

N개의 Process를 다루는 알고리즘. 번호표를 뽑는 것 과 비슷하다.

Process마다 번호표가 발급되고, 번호표가 작은 순서대로 Critical Section에 들어간다.

같은 숫자의 번호표도 발급이 가능하고 번호표가 같은 경우에는 ProcessID를 비교한다.

Boolean형 choosing[N] : 번호표를 할당받는 상태. → True = 번호표 발급 과정 진행중 / False = 번호표 발급 과정 X. 초기값 : FALSE

int형 number[i] : 번호표. 초기값 0

• 방식

do{
	//Entry Section
	choosing[i] = TRUE; //want to enter Critical Section
	number[i] = max(number[0],number[1],.....number[n-1]) + 1; //번호표 발급.
	choosing[i] = FALSE;
	for(j=0;j<n;j++){
		while(choosing[j]); // 다른 프로세스가 번호표를 뽑는 상태에 있다면 번호표 뽑는 것을 기다린다.
		while((number[j]!=0) && (number[j],j) < (number[i],i)); // 순서가 minimum일때까지 기다린다.
	}

	//-----
	//Critical Section
	//do Something
	//-----

	//Exit Section
	number[i] = 0;

}while(1);

번호표 순서가 올 때 까지 기다린 뒤, 순서가 되면 Critical Section으로 들어간다.

Critical Section에서 나올 때 번호표를 버린다. number[i] = 0;

Hardware Solution

많은 시스템이 hardware 방식을 지원한다.

Uniprocessors에서는 한 Process가 Critical Section에 들어가면 Interrupt를 꺼버린다.

이 방식은 Multiprocessor에서는 비효율적이다. -> atomic한 Instruction을 구현하여 해결한다.

1. TestAndSet Instruction

boolean TestAndSet(boolean *target)함수를 통해 구현된다.

boolean lock : local변수, 초깃값 FALSE

boolean TestAndSet(boolean *target){
	boolean rv = *target; //target값 저장.
	*target = TRUE;//target값 변경.
	return rv; 
}

• 방식

do{
	//Entry Section
	while( TestAndSet(&lock)); //while문을 Waiting -> Busy Waiting or spinlock이라고 한다.
	
	//-----
	//Critical Section
	//do Something
	//-----

	//Exit Section
	lock = FALSE;
}while(TRUE);

TestAndSet은

Mutual Exclusion, Progress는 만족

Bounded Waiting은 Process가 2개일때는 만족, Process가 2개 이상일 때는 불만족.

→ 여러 Process가 돌아가는 환경에서 사용하면 무한히 기다리는 Process가 생길 수 있다.

2. Swap Instruction

void Swap(Boolean *a, Boolean *b)를 정의.

boolean lock : 전역 변수. 초기값 FALSE. Critical Section의 잠김유무를 나타낸다.

boolean key : 지역 변수. 초기값 FALSE

void Swap(boolean *a, boolean *b){
	boolean temp = *a;
	*a = *b;
	*b = temp;
}

• 방식

do{
	//Entry Section
	key = TRUE;
	while(key == TRUE){ //Swap을 통해서 key = FALSE가 되면 while을 탈출.
		Swap(&lock,&key); 
	}

	//-----
	//Critical Section
	//do Something
	//-----

	//Exit Section
	lock = FALSE;
}while(TRUE);

Swap Instruction은

Mutual Exclusion, Progress는 만족

Bounded Waiting은 Process는 2개일때는 만족, Process가 2개 이상일 때는 불만족.

→ 여러 Process가 돌아가는 환경에서 사용하면 무한히 기다리는 Process가 생길 수 있다.