[Operating System Concepts] Chapter6 Synchronization Tools (Part.1)

nc

1. Concurrent Process
2. Race Condition
3. The Critical Section Problem
   • Requirements for the solution
   • single core environment solution
4. Peterson's Algorithm (bakery algorithm)
5. Hardware-based Solutions

---

Concurrent Process

프로세스가 동시에 작동할 때 순서대로 실행이 되는것을 사용자가 보장해주어야 한다. (data consistency)

 

•  데이터를 공유하게 된다면 integrity of data 가 저해된다. (병렬처리의 경우에도)
  → 소프트웨어 보안의 3요소 (C.I.A) 를 고려해야 한다.
  Confidentiality: 데이터 자체의 보안, 암호화된 데이터
  Integrity : 위변조가 생겨나는 상황
  Availability: 디도스 공격등 프로그램 가용성을 저해시킬때

Producer-Consumer Problem에서 producer은 버퍼에 item을 생산하고 consumer은 버퍼의 item을 소모하는 방식으로 구현된다.

#producer

while (true) {
    /* produce an item in next produced */
    while (counter == BUFFER_SIZE)
    ; /* do nothing */
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

#consumer

while (true) {
    while (counter == 0)
    ; /* do nothing */
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
    /* consume the item in next consumed */
}

위의 코드는 잘 동작할 것 같지만 제대로 동작하지 않는다.

 

count ++ 과 count -- 는 인스트럭션이 구분되어 있지 않다. (중간에 컨텍스트 스위칭이 생길 수 있다.)
→ 컨텍스트 스위칭은 페이지 단위로 달라지게된다(2페이지 이상일때와 ~ 여러가지)

 

같은 physical register이지만 save과정과 restore되는 핸들링 과정에서 문제가 생긴다. (임의의 실행 사이에 들어갈 수 있다.)

S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 – 1 {register2 = 4}
S4: producer execute counter = register1 {counter = 6 }
S5: consumer execute counter = register2 {counter = 4}

이러한 과정을 경쟁 상황(Race Condition) 이라고 한다.

 

Race Condition

2개 이상의 데이터가 동시에 처리되고 있을 때 race condition이라고 한다. Synchronization을 통해 경쟁상황을 막을 수 있도록 한다.

• Race Condition을 방지하기 위해 한프로세스가 한 타임에 공유 데이터에 접근할 수 있도록 해야한다.
• 이러한 상황을 보장하기 위해 프로세스가 동기화되도록 해주어야 한다. (Process / thread synchronization)
• Race Condition은 계좌이체, Stack의 pop, push 과정에서 일어날 수 있다.

 

#JAVA 에서 Race Condition이 다른경우

public class RaceCondition1{
	public static void main(String[] args) throws Exception {
    	RunnableOne run1 = new RunnableOne();
        RunnableOne run2 = new RunnableOne();
        Thread t1 = new Thread(run1);
        Thread t2 = new Thread(run2);
        t1.start(); t2.start();
        t1.join(); t2.join();
        System.out.println("Result: " + run1.count + ", " + run2.count);
    }
}

 

 

#JAVA 에서 Static Variable 의 경우

public class RaceCondition2{
	public static void main(String[] args) throws Exception {
    	RunnableTwo run1 = new RunnableOne();
        RunnableTwo run2 = new RunnableOne();
        Thread t1 = new Thread(run1);
        Thread t2 = new Thread(run2);
        t1.start(); t2.start();
        t1.join(); t2.join();
        System.out.println("Result: " + RunnableTwo.count);
    }
}

 

 

The Critical Section Problem

공유 데이터를 처리하게 되는 영역, 허가를 통해 임계영역 내부에 들어가고 반납을 통해 임계영역을 빠져나온다.

• 4가지 영역으로 나눌 수 있음
  • entry-section (permission 을 통해 critical section 들어간다 - 나중에 반납)
  • critical -section
  • exit-section (임계영역 탈출한다)
  • remainder-section

#Three requirements for the solution : 동시성 문제를 해결하기 위해 해야 할 숙제들

• Mutual Exclusion : 상호 배제
• Deadlock(Progressive) : 아무도 진입못하는 경우를 케어해주기, CS안에 프로세스가 없다면 CS에 진입할 수 있어야 한다.
• Starvation(Bounded Waiting) : 임계영역에 들어갈 때 평생 진입 못하는 경우, 프로세스의 CS 진입은 유한 시간 내에 허용되어야 한다. 계속 기다리는 상황을 만들지 말고 언젠간 들어갈 수 있게 하여 기아상태(starvation)를 방지해야 한다.

→ 모두 해결하는 방법은 어렵고 비싸다. 따라서, Deadlock, Starvation은 상황이 발생할 때마다 그때 그때 처리한다.

 

상호배제를 하지 않는다면 pid가 중복되는 자식프로세스가 생겨버릴 수 있다...

#single core 환경에서의 솔루션

• prevent interrupts from occuring → 단순한 순서 진행에 따라 막기 가능
• 단순 무식하지만, 임계영역이 긴 경우에 대해서 멀티프로세싱의 장점을 막는다는게 결점이다.
• non-preemptive kernel 보다 preemptive kernel 사용함 (동시성의 이점을 포기할 수 없다.)

 

Peterson's Algorithm (bakery algorithm, spinlock)

임계영역과 나머지 영역의 구분으로, 'flag'를 사용해서 두개의 프로세스의 실행을 제한한다. ('classic' but 'no guarantee')

 

#Peterson algorithm

shared boolean flag[2]={false, false};
shared int turn = 0 ;
--------------------------------
(P0 code)

do
{ 
  flag[0] = true ; // 0번 프로세스가 지금 사용하고 싶다는 걸 전달하기 위해 flag를 true로 변경한다.
  turn = 1 ;
  /*
  들어가고 싶다고 선언해주고 1차례로 돌려줌으로써, 혹시 쓰고 싶은 다른 프로세스가 있는지 확인한다.
  이 프로세스가 쓰기 전에 먼저 쓰고 싶어했던 애가 있는지 확인하고 수행시켜주는 코드이다.
  */
  
  while (flag[1] && turn == 1) // busy waiting하는 과정
  /*
  임계영역에 들어가기 위해서는 0번 차례여야 한다. turn == 1인 경우, 0번 차례가 아닌데 1이 자원까지 쓰고싶다면
  0번 프로세스는 spinlock에서 머물러야 한다.
  반면에, 0번 차례거나 1이 자원을 쓰고 싶지 않은 경우 (flag[1] == false)
  spinlock을 빠져나와 진입할 수 있다.
  */ 
  critical section of P0 ; 
  flag[0]=false ;  // 다 쓰고 나면 flag를 다시 false로 바꿔준다.
  remainder section of P0
} while (true) ;

--------------------------------
(P1 code)

do
{
  flag[1] = true ;
  turn = 0  
  while (flag[0] && turn == 0) 
    /* do nothing */ ; 
  critical section of P1 ; 
  flag[1]=false ; 
  remainder section of P1 ;
} while (true) ;

→ 돌려보면 원하는대로 작동하지 않는다. 컴퓨터 안에서 flag가 작동하지 않을 가능성을 배제하지 못하기 때문이다.

Peterson algorithm은 N개의 프로세스에 대해서도 충분히 적용시킬 수 있다. 그러나 속도가 느리며 Busy Waiting(Spinlock)을 하기 때문에 자원을 많이 소모한다는 단점이 있다.

Hardware-based Solutions

눈부신 기술발전으로 하드웨어 내부에다가 동시성을 제어하는 instruction/variable 이 존재한다.

 

하드웨어에서 동시성 제어를 위한 세가지 종류의 기본 연산들이 있다

• memory barriers of fences - instruction(명령어)
• hardware instruction - instruction(명령어)
• atomic variables - variable(변수)

• Atomicity : 새로운 하드웨어 명령어가 많이 생겨나고있는 추세 (상용적인 인스트럭션이 많이 생김)

 

LLVM 으로 해당 instruction 들을 에뮬레이팅할 수 있다. 아래는 소프트웨어적(코드)로 구현한 것이다.

#test_and_set() : Mutex(상호배제)를 만족하지만 Bounded waiting(기아상태)를 방지하지 못한다.

boolean TestAndSet(boolean *lock) {
    boolean initial = *lock
    *lock = true
    return initial
}

do {
 while(TestandSet(&lock); // 진입구역
 CRITICAL SECTION
 lock = FALSE; // 퇴출구역
 REMAINDER SECTION
} while(TRUE)

• 전역 bool 변수는 lock (False가 기본설정으로 설정됨)
• Bounded waiting 을 만족하지 못함, 해결하기 위해서는 여전히 어렵고 복잡하다.
• 여전히 Spinlock으로 구현되어 있어 락킹을 기다리는동안 자원을 소모한다

#compare_and_swap()

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

• 전역 bool 변수는 lock (0이 기본설정으로 설정됨)
• CAS에는 세개의 인자를 통해 락킹과 기대하는 값(0이 기본) 그리고 CS에 들어갈 때 변경되는 락킹값을 인자로 지정한다.
  value : 현재 락킹 상태(0이면 CS에 없음, 1이면 CS에 있으므로 사용불가)
  expected : 기대하는 값(0이 기본)
  new_value : CS에 들어가고 나올 때 변경되는 값

#Atomic Variable

• 원자성을 보장하는 변수이기 때문에 당연하게도 mutual exclusion 이 가능해짐
• 내부적으로 compare_and_swap() 알고리즘을 사용한다.

각 CPU는 메인 메모리에서 변수값을 참조하는 것이 아니라, 각 CPU의 캐시 영역에서 메모리를 참조하게 된다.

compare and swap / Atomic variable comparison

• 현재 스레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체되고, 일치하지 않는다면 실패하고 재시도를 한다.
• 자바에서의 synchronized 의 경우 synchronized 진입 전 메인 메모리와 CPU 캐시 메모리 값을 동기화하여 문제가 없도록 처리한다. (synchronized는 임계영역 블록을 모두 락킹시키기 때문에 CAS보다 효율이 좋지못함) 
  출처:https://beomseok95.tistory.com/225

피터슨 알고리즘은 동시성의 세가지 문제를 해결할 수 있다. 하지만 하드웨어 명령어들은 대부분 Bounded Waiting을 만족하지 못하는 이슈가 있다. 이러한 이슈를 해결하기 위해 mutex, semaphore 을 다음에 소개하겠다.