[운영체제/OS] Synchronization_동기화, 임계 구역 문제

동기화(Synchronization)

 

Producer (=master): 데이터 생성

while(TRUE)
{
  //produce an item and put into the buffer
  while(counter==BUFFER_SIZE) 	//is buffer full?
  	; //do nothing 				//busy waiting. spin lock
  buffer[in] = nextProduced;	//write연산 (차있지 x경우)
  in = (in+1) % BUFFER_SIZE;
  
  counter++;
}

 

Consumer 

while(TRUE)
{
	while(counter == 0) 	//is buffer empty?
    	; //do nothing
    nextConsumed = buffer[out];
    out = (out+1) % BUFFER_SIZE;
    
    counter--;
    // consume the item
}

 

Race Condition(경쟁 조건)

생산자와 소비자의 작업이 동시에 수행되면 바르게 동작하지 않을 수 있다.

즉, counter 변수 값이 consistent하지 않게 될 수 있다.

 

race condition에 의해 불확실한 상태에 도달하는 경우, 그 이유는 두 개 이상의 프로세스가 동시에 하나의 변수 조작을 허용했기 때문이다. 

 

예방법: 한번에 오직 하나의 프로세스만이 특정 변수를 조작하는 것을 보장할 필요가 있다.

프로세스들이 동기화(synchronization)이 필요하다.

 

 

 

Critical Section Problem(임계 구역 문제)

do{
	entry section
    	critical section
    exit section
    	remainder section
} while(true);

 

OS의 제공 역할은 3가지를 반드시 만족해야 합니다.

1. Mutual Exclusion(상호배제) - 프로세스 Pi가 임계구역에서 수행중이라면, 동일 데이터에 대해 스레드 하나만이 수행해야 한다.

2. Progress - 임계구역 수행 중인 프로세스가 없고, wait상태인 프로세스들이 있다면, 임계구역에 들어갈 다음 프로세스 선택하는 과정을 연기해서는 안된다.

3. Bounded Waiting(한정 대기시간) - 대기 시간이 지나치게 길어지는 걸 방지해야 한다. Starvation-free 

 

 

임계 구역 문제의 해결

선점형 커널, 비선점형 커널

 

 

Peterson's Solution

임계구역문제를 해결하는 좋은 알고리즘

두 프로세스는 두 공유 변수를 가진다: int turn, Boolean flag[2];

 

do{
	flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);	//busy waiting
    	critical section
    flag[i] = false;			//수행완료후 flag변경(상대방에게 양보)
    	remainder section
} while(true);

 

-Mutual Exclusion: 

Pi는 flag[j]==false 거나 turn==i 인 두 조건 중 하나가 만족되어야만 임계 구역에 들어감

Pi는 flag[i]==true인 상태에서만 임계구역에 들어감

Pi와 Pj는 동시에 임계구역에 들어갈 수 없다.

 

-Progress:

Pi는 flag[j]==true이고 turn==j인 경우에만 멈춘다.

 

-Bounded waiting:

Pi는 기껏해야 Pj의 한 번의 출입 후에 임계 구역에 들어가게 된다.

 

 

하지만 peterson's 해결책은 최신 컴퓨터 구조에선 보장되기 어렵다. 

 

thread 1:

while(!flag)

   ;

print x;

 

thread2:

x=100;

flag=true;

 

에서 x=100과 flag=true의 순서가 바뀐다면, x=100이 출력되지 않을 수 있다. 이 경우 상호배제가 보장되지 않았다.

 

Synchronization Hardware

Atomic(=non-interruptible) 한 hardware 명령어로 임계구역문제를 해결한다.

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

 

test_and_set Instruction

 

boolean test_and_set (boolean *target)
{
	boolean rv = *target;	//1이면 그대로, 0이면 바꿈.
    *target = TRUE;	//1
    return rv:
}

1은 다른 누군가 가지고 있다는 뜻(냅둠)

0이면 내가 가져가므로 1로 바꿔줌

그래서 target값과는 상관없이 1로 설정한다.

 

Solution: atomic 명령어를 사용하는 경우

do{
	while(test_and_set(&lock))
    	;/*do nothing*/
        	/*critical section*/
        lock = false;
        	/*remainder section*/
} while(true);

compare_and_swap Instruction

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

Solution with compare_and_swap

do{
	while(compare_and_swap(&lock,0,1) != 0)
    ; /*do nothing*/
    /*critical section*/
 lock=0;
 	/*remainder section*/
 } while(true);

하지만 이는 무한루프 가능성이 있다.

 

그러므로 Bounded-waiting Mutual Exclusion with test_and_set으로 

do{
	waiting[i]=true;
    key=true;
    while(waiting[i] && key)
    	key = test_and_set(&lock);
    /*key=compare_and_swap(&lock,0,1);
    waiting[i]=false;
    /*critical section*/ 
    j = (i+1) % n;
    while((j!=i) && !waiting[j])
    	j = (j+1) % n;
    if(j == i)
    	lock = false;
    else
    	waiting[j] = false;
    /* remainder section */
} while(true);