Operating Systems 6. Synchronization Tools

Background

- 공유 데이터에 대한 병행/병렬 접근은 데이터 일관성을 보장하지 못할 수 있다. -> data inconsistency

- 이를 막기 위해 병행 프로세스가 공유 데이터에 접근할 때에는 프로세스 동기화가 필요하다.

 

 

Producer-Consumer

생산자와 소비자는 counter 라는 공유변수에 접근한다. 

 

 

 

경쟁조건(Race Condition)

- 병행 프로세스가 공유 데이터를 접근하였을 때 공유 데이터의 일관성이 깨지는 상황을 의미한다.

- 즉, 실행 결과가 자료의 접근 순서에 영향을 받는 상황이다.

-> 불확실한 상태에 도달할 수 있다.

-> 경쟁 조건의 예방을 위하여 한번에 오직 하나의 프로세스만이 특정 변수를 조작하는 것을 보장하기 위해 동기화가 필요하다.

 

 

 

Critical Section Problem

- 각 프로세스의 code 에는 공유 데이터를 접근하는 부분인 임계구역이 존재한다.

• 임계 구역를 실행하는 동안 공유변수를 바꾸거나, 테이블을 갱신하거나, 파일을 쓰는 등의 동작을 할 수 있다.
• 하나의 프로세스가 임계구역에 있는 동안, 다른 어떠한 프로세스도 임계구역에 있어선 안된다.

- 임계 구역 문제

• 프로세스들이 임계 구역에서 경쟁 조건이 발생하지 않도록, 서로 협력하기 위해 사용할 수 있는 protocol 을 설계하는 것이다

- 프로세스의 일반 구조

-> 각 프로세스는 critical section 에 들어가기 전 entry section 에서 허락을 요청해야 하고, critical section 을 수행한 후 exit section 을 실행하여야 한다.

 

- 3가지 필요조건

• Mutual Exclusion  : 프로세스가 자신의 임계구역 내에서 실행 중이라면, 다른 프로세스들은 자신의 임계구역에서 실행될 수 없다. -> 동시에 두 개 이상의 프로세스가 임계 구역에서 실행될 수 없다.

• Progress : 임계구역에서 실행 중인 프로세스가 없고, 임계구역에 진입하려는 프로세스가 존재한다면, 임계구역에 들어갈 프로세스를 선택하는 것이 무한히 지연되어서는 안된다. -> 임계구역 밖에서 수행중인 프로세스는 다른 프로세스를 block 할 수 없다.
• Bounded Waiting : 프로세스가 임계구역 진입을 요청한 후에 요청이 허용될 때까지 다른 프로세스가 임계 구역 진입이 허용되는 횟수에 제한이 있어야 한다. -> 어떤 프로세스도 임계구역 진입을 영원히 기다려선 안된다.

 

커널에서의 경쟁조건

- 커널에서 여러 개의 커널 모드 프로세스가 활성화될 수 있으며 커널 자료구조를 공유할 수 있다. -> 경쟁조건 발생 가능

- 커널은 경쟁조건이 발생하지 않도록 개발자가 설계해야 한다.

- 단일 코어 환경에서는 인터럽트 불능(비선점형) 으로 임계구역 문제를 해결할 수 있다.

 

• 선점형 커널 : 커널모드에서 프로세스가 선점되는 것을 허용한다. 
• 비선점형 커널 : 커널모드에서 프로세스가 선점되는 것을 허용하지 않는다. 따라서 커널모드가 종료되거나, 봉쇄(block) 되거나, 자발적인 양보를 하기 전까지 프로세스를 계속 실행한다.

 

 

Peterson's Solution

- 피터슨의 solution 은 임계구역 문제에 대한 고전적인 소프트웨어 기반 해결방안으로, 두 프로세스에 대해서만 적용가능하다. 

- load 와 store 명령어가 atomic 하다는 것을 가정한다. -> 두 프로세스가 각각 다른 코어에서 실행한다고 가정하고 동시에 어떤 메모리 상의 변수에 접근할 때 한번에 하나씩 순차적으로 접근이 이루어지도록 하드웨어가 보장을 한다.

 

- 정수형 변수 2개 사용 : int turn, Boolean flag[2]

- turn : 이번에 어느 프로세스가 임계 구역에 진입할 차례인지를 나타내는 변수이다.

- flag : 프로세스가 임계구역에 진입할 준비가 되었는지를 나타내는 배열이다. (flag[i] = true 는 프로세스i가 진입할 준비가 되었음을 의미한다.) -> 만약 flag[0], flag[1] 이 모두 true 라면, 둘다 임계구역 진입을 요청한 상태이다.

-> 프로세스 i는 자신이 임계구역에 진입하고자 한다. 그리고 turn 을 j에게 줌으로써, 프로세스 j가 임계구역에 진입하고 자 한다면 먼저 진입할 수 있도록 한다. 따라서 j의 차례이고, j가 임계구역에 들어가고자 한다면 계속해서 while 문을 돌면서 i는 임계구역에 들어가지 못한다. i가 임계구역에 들어가서 모두 실행한후, 자신의 flag 를 false 로 변경한다.

 

 

피터슨의 해결책 증명

- 상호 배제 : Pi 는 flag[j] == false 이거나 turn == i인 두 조건 중 하나가 만족되어야지만 임계 구역에 들어갈 수 있다. 이는 즉, p0 과 p1 이 절대로 동시에 임계구역에 머무르지 않음을 뜻한다.

- 진행 : 상대방의 flag 가 false 이면 바로 임계구역에 진입할 수 있고, 두 flag 가 모두 true 라면 turn 이 1인 프로세스는 바로 임계구역에 진입할 수 있다. 

- 한정대기 : 상대방이 임계구역을 모두 실행한 후, flag 는 false 가 되므로 자신이 임계구역에 들어갈 수 있다. 또한, 상대방의 flag 가 true 가 되더라도, turn 을 넘겨주므로 임계구역에 들어갈 수 있다.  

 

-> 그러나, 현대 컴퓨터 구조에서는 보장된 작동을 하지 않을 수 있다. 성능 향상을 위해 종속성이 없는 읽기 및 쓰기 작업들의 순서를 변경할 수 있는데, 이때 예기치 않은 결과가 발생할 수 있다.

 

 

 

Synchronization Hardware

- lock 을 사용하는 임계구역 문제 해결책

lock 은 hardware 에게 요청한다

- 임계구역을 lock 으로 보호하여, 경쟁조건을 방지한다.

- 현대의 시스템들은 atomic hardware 명령어를 지원한다. 

- Atomic = non-interruptible (인터럽트 금지)

 

 

 

test_and_set Instruction

공유변수는 lock 이며 초기값은 false(==0) 이다.

test_and_set 에 lock 을 파라미터로 전달하면 0을 리턴받는다.

따라서 while문의 조건이 fail 되므로, critical section 에 들어갈 수 있게 된다. 

이때 test_and_set 의 정의에 의해 lock 변수는 true 값을 갖게 된다. (리턴값은 0, lock변수는 1)

 

따라서 만약 임계구역을 실행 중에 다른 두번째 프로세스가 들어온다면, lock 이 true 이기 때문에 while 문 조건에 걸려 기다리게 된다. 그리고 첫번째 프로세스가 임계구역을 모두 실행하고 lock = false; 를 실행한다면 while 문에서 두번째 프로세스의 return value 가 false 가 되어 두번째 프로세스가 임계구역에 진입할 수 있게 된다. 

 

 

 

compare_and_swap Instruction

val 과 expected 의 값이 같을 경우, new_val 의 값을 val 에 넣고 val 의 초기값을 리턴한다.

공유변수 lock 은 false 로 초기화 되어있다. compare_and_swap 의 정의에 따라 리턴값은 lock 에 있는 초기값인 false 이므로 while 의 조건이 fail 이 되어, 임계구역에 진입하게 된다. 그 순간 lock 변수는 new_value 의 1의 값을 가지게 된다. 

이때 두 번째 프로세스가 entry section 에 들어온다면, lock 변수가 1의 값을 가지고 있기 때문에 1을 리턴받아 while 문에서 기다리게 된다. 첫 번째 프로세스가 임계영역을 모두 실행한 후 lock = 0으로 바꿔준다면, 두번째 프로세스가 0을 리턴받아 임계구역에 들어올 수 있게 된다. 

 

 

 

Bounded-waiting Mutual Exclusion with test_and_set

do {
	/* entry section */
    // 임계구역에 들어가고 싶음
	waiting[i] = true;
    
    // lock 값을 다루기 위한 변수
	key = true;
    
    // 임계구역에 들어가기 위한 조건 체크
	while (waiting[i] && key)
		key = test_and_set(&lock);
        // test_and_set 이 0을 리턴한다면 반복문을 탈출
		/* key = compare_and_swap(&lock,0,1);
        
    // 이제 임계구역에 진입하는 상황이므로 waiting을 false 로 바꿔준다.    
    waiting[i] = false;
    
    /* critical section */

    j = (i + 1) % n;
    // j를 1씩 증가시킨다.    
    // j==i 이거나, 기다리고 있는 j가 있다면 j를 그만 증가시킨다.
    while ((j != i) && !waiting[j])
    	j = (j + 1) % n;
        
    // 기다리는 다른 프로세스 j가 없다는 뜻이다.    
    if (j == i)
   	 lock = false;
    else
    // 다음에 들어가고자 하는 프로세스 j의 waiting 을 false 로 바꿔 진입할 수 있게 해준다.
    	waiting[j] = false;
   
   /* remainder section */
} while (true);

 

-> 이 경우는 최악의 경우에도 n-1 개의 다른 프로세스를 기다리면 나는 임계구역에 들어가는 것이 보장이 된다. 즉 계속 1이 리턴되어 무한대기를 하는 경우를 방지하는 방법이다.