• 협력적 프로세스에서 Shared Memmory로의 동시 접근은 데이터의 비일관성을 낳을 수 있다. 그래서 다양한 기법을 이용하여 데이터의 일관성을 유지해야 한다.

1. 배경

• 협력적 프로세스 혹은 스레드로 구성된 시스템에서 이들은 서로 비동기적으로 실행될 가능성이 있다.
• 만약 두 개의 프로세스가 동시에 특정 데이터를 변경 할 경우, 그 실행 결과가 접근 순서에 따라 달라지는 상황이 발생할 수 있다. 그리고 이 경우를 Race Condition이라고 한다.
• Race condition으로부터 보호하기 위해, 우리는 프로세스들이 동기화 되도록 할 필요가 있다.

A. Critical Section

• Critical Section이란, 한 프로세스가 자신의 Critical Section에서 수행하는 동안에 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다. 이 구역에서는 비동기적으로 실행이 불가능하다.

• 임계 구역은 진입 요청을 하는 entry section과 나가면서 다른 프로세스들이 임계구역에 들어올 수 있게 하면서 나가는 reminder section이 있다.
• Critical Section은 다음 세가지 조건을 충족해야한다.
  • 상호 배제: 프로세스 a의 임계 구역에서 실행중이라면, 프로세스 b는 자신의 임계 구역을 실행 하지 못한다.
  • 진행: 프로세스들이 자신의 Critical Section에 진입 요청을 한 후부터 그 요청이 허용될 때까지 무기한 대기하지 않도록 한다.
  • Bound waiting: 프로세스가 자신의 Critical Section에 진입 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
• 운영체제 내에서도 임계구역을 다루기 위해 Preemitive Kernel과 non-Preemitive Kernel의 두가지 일반적인 접근법이 사용된다.
• Non-preemitive한 경우 Race Condition은 일어나지 않는다.
• preemitive한 경우 Race Condition이 일어날 수도 있다.

2. Peterson’s Solution

• 상호배제, 진행, 한정된 대기의 요구 조건을 중점으로 다루는 소프트웨어를 설계하는데 필요한 복잡성을 잘 표현하는 알고리즘이다.
• 두 프로세스는 두 개의 데이터 항목을 공유한다.

  bool flag[]; // 임계영역 진입 상태를 저장한다.
  int turn; // 임계 영역을 실행할 프로세스의 순서를 저장한다.
  					//process 1, process 2 모두 자신의 순서를 원하더라도 오직 한 배정만 가능하다. 

• while(true){
  	flag[i] = true; // 해당 번호의 프로세스가 임계구역에서 실행 준비 완료를 나타낸다.
  	turn = j; // 임계 구역에 진입할 차례의 프로세스 번호
    
  	while(flag[j] && turn == j){}; // 이 조건을 만족한다면 다른 프로세스가 임계구역에서 나오기 전까지  spinlock상태로 busywaiting한다.
      
  	/* critical section */
      
  	flag[i] = false; // 임계영역에서 요청을 수행하고 나왔으니 다음 프로세스가 임계구역에 들어갈 수 있게  자신의 상태를 false로 바꾸어준다.
      
  	/* remainder section */   
  }
  

  • flag[0],flag[1]이 모두 true 이어도 turn 에 따라 한 프로세스는 실행되고 다른 프로세스는 while문에서 spinlock 상태이므로 상호 배제적으로 실행된다.
  • 또한 임계 구역 실행 후 flag[i] = false; 를 통해 자신의 상태를 바꾸어주면서 다른 프로세스가 임계구역에 들어 갈 수 있도록 하여 Progress와 BoundWaiting을 지킨다.
  • 하지만 Peterson’s의 방법은 프로세스가 두 개인 경우에만 가능하다.

3 . Synchronize Hardware

• sw 기반 해결책은 현대의 컴퓨터에서 제대로 동작하지 않을 수 있으므로 프로그래머는 하드웨어에서 소프트웨어를 모두 망라한 임계구역 해결책을 사용한다.
• 이 모든 해결책은 Locking에 대한 가정, 즉 임계구역 문제에 대해 락을 사용하는 것에 기반을 한다.
• 단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않으면 되지만, 다중 처리기 환경에서는 인터럽트의 사용 불가능화가 상당한 성능 저하를 일으킨다.
• 그러므로 많은 현대 기계들은 atomically(인터럽트 되지 않는 하나의 단위)하게 실행된다.

A. test_and_set()

boolean test_and_set(boolean *target){
	boolean rv = *target;
    *target = true;
    
    return rv;
}

• 반환값은 입력값을 그대로 반환한다.
• 그리고 target값은 입력값이 어떤 값으로 들어오던간에 true로 set된다.
• test_and_set를 이용한 상호배제 구현

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

  • lock값이 false 일 때만 Critical Section에 접근이 가능하다. lock은 전역변수로 어떤 프로세스가 임계구역에서 요청 수행후 다시 전역 변수 lock값을 false로 바꿔주어(lock = false;) 다음 프로세스가 임계구역에 접근이 가능하다.
• test_and_set방식은 Mutual Exclusive는 만족시키지만, FCFG의 처리방식을 가지므로 Progress와 Bounded Waiting을 만족시키지 못한다.

B. compare_and_swap()

int compare_and_swap(int *value, int expected, int newvalue){
		int temp = *value;
	
		if(expected==*value)
			*value = newvalue;

		return temp
	}

• 반환값은 *value 이다.
• expected 와 *value 가 같다면 *value 값은 newvalue 로 바뀐다.
• compare_and_swap을 이용한 상호배제 구현

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

  • 전역변수인 lock 가 0인 경우 아래의 임계 영역이 실행된다. 실행 중일 때는 lock==expected(두 번째 매개변수) 이므로 lock은 1(newvalue)로 바뀌어 다른 프로세스는 임계구역에 들어오지 못한다.
  • 임계구역에 있던 프로세스는 요청한 작업을 마치고 나오면서 lock값을 다시 1로 바꾸면서 나오고 이제 다른 프로세스가 임계구역에 접근할 수 있다.
• compare_and_swap 방식은 Mutual Exclusive는 만족시키지만, FCFG의 처리방식을 가지므로 Progress와 Bounded Waiting을 만족시키지 못한다.

4. Mutex Locks

• Critical Section에 대한 하드웨어적 접근은 복잡하여 응용프로그래머가 사용하기 힘들다.

• Mutual exclusion의 축약 형태인 Mutex는 OS설계자들이 임계구역 문제를 해결하고자 만든 소프트웨어 툴이다.

• Mutex Locks

  // acquire 함수의 정의
  acquire(){
  	while(!available); // busywaitng(aka.spinlock)
  	available = false;
  }
  
  //release 함수의 정의
  release(){
  	available = true;
  }

  • mutex는 available 변수를 가지는데, 이 변수는 락이 가용가능한지에 대한 변수이다. available 이 true인 경우 busywaiting하고 false인 경우 acquire lock 함수는 락을 획득한다. 그리고 Critical section을 진입하여 요청사항을 수행한다.
  • release lock 에서 락을 반환 해야한다.

5. Semaphore