(31) Hardware Support Synchronization

### Hardware Supprot Synchronization ###

1. < Test-and-Set instruction >

: 하나의 word가 주어질때 word 확인 후 값 바꾸는 일한다

: test-and-set instruction동안에는 system call/interrupt가 발생하지 않는다.

=> instruction 자체가 이러한 특성을 가진다(cpu가 고정된 형태로 지원해 준다) => overhead가 없다.

​

<구현>

: 자동적으로 실행

: 전달된 parameter의 원래 value를 return한다.

: 전달된 parameter의 새 값을 true로 설정한다.

boolean test_and_set(boolean *target){
	boolean return_value = *target;
	*target = true;
	
    return return_value;
	}
    
    
    
 do{
 	while (test_and_set(&lock)); //아무것도 안함 
    
   	//criticl section 
    
    lock = false;
    
    //remainder section 
 	}while true;

(lock: 각 process들이 정보를 공유하는 변수(process에서 진입할 수 있는지 없는지 알려주는 것))

=> critical section에 들어가기 위해 대기중인 process에 starvation(굶주림)이 발생한다 .

(Bounded waiting 조건 만족 못한다)

 

 

​

​

 

2. < Compare-and-Swap instruction >

: 두개의 word를 받아 서로 exchange하는 것

: compare-and-swap instruction동안에는 system call/interrupt가 발생하지 않는다.

=> instruction 자체가 이러한 특성을 가진다(cpu가 고정된 형태로 지원해 준다) => overhead가 없다.

​

<구현>

: 자동으로 실행된다.

: 전달 된 parameter value의 원래 value를 반환한다.

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



while true{
	while (compare_and_swap(&lock, 0, 1) != 0); //아무것도 안함
    
    // critical section 
    
    lock = 0; // 각 process들이 정보를 공유하는 변수
    
    //remainder section

}

(lock: 각 process들이 정보를 공유하는 변수(process에서 진입할 수 있는지 없는지 알려주는 것))

=> critical section에 들어가기 위해 대기중인 process에 starvation(굶주림)이 발생한다.

(Bounded waiting 조건 만족 못한다)

 

 

 

< Bounded waiting 해결 방법 >

: lock + waiting array사용

=> Bounded waiting 문제 해결

 

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