[운영체제] CH05. 프로세스 동기화 - Critical Section, Peterson's Solution, Mutex Lock

Background

• 프로세스들은 병행 수행을 함
• 멀티프로그래밍은 CPU의 활용도를 높이기 위해 한 프로세스가 입출력을 하는 동안 다른 프로세스들이 병행 수행을 하도록 하는 기법
• 개별 프로세스 입장에서 자신의 코드를 실행하는 도중 언제든 임의의 지점에서 수행이 중단되고 다른 프로세스로 실행이 전환될 수 있음
• 만일 다수의 프로세스 간의 데이터를 공유하고 있는 상황일 때 이중에서 한 프로세스가 공유 데이터를 접근하는 도중 실행이 중단되면 데이터의 consistency가 깨질 수 있음
  → 이를 방지하기 위해 실행을 강제하는 것이 프로세스 동기화

Producer-consumer problem

• 현재 buffer에 들어있는 데이터의 개수를 표시하기 위해 counter라는 이름의 공유 변수를 사용
• Producer 프로세스

  while (true) {
  	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--;
  }

  
  

Race Condition

• 병행 프로세스가 공유 데이터를 접근한 결과 공유 데이터의 consistency가 깨지는 상황
• 앞선 코드에서 Producer와 Consumer는 공유 변수에 접근
  • counter를 증가시키는 동작은 C 코드에서는 1줄이지만 이를 실행시키기 위해 컴파일 후 기계어 코드로 만드는 경우 아래와 같은 3단계의 CPU 명령으로 만들어짐

    register1 = counter
     register1 = register1 + 1
     counter = register1

  • counter를 감소시키는 동작도 마찬가지

    register2 = counter
     register2 = register2 - 1
     counter = register2

  • 데이터에 대해 CPU가 연산을 하기 위해서는 데이터를 먼저 레지스터로 가져와야 함
• 올바른 실행 순서

  register1 = counter
   register1 = register1 + 1
   counter = register1
   register2 = counter
   register2 = register2 - 1
   counter = register2
   
   OR
   
   register2 = counter
   register2 = register2 - 1
   counter = register2
   register1 = counter
   register1 = register1 + 1
   counter = register1

• 잘못된 실행 순서
  • counter 초기값은 5
  • S0 : register1 = counter (register1 = 5)
  • S1 : register1 = register1 + 1 (register1 = 6)
  • S2 : register2 = counter (register2 = 5)
  • S3 : register2 = register2 - 1 (register2 = 4)
  • S4 : counter = register1 (counter = 6)
  • S5 : counter = register2 (counter = 4)

---

Critical Section Problem

• critical section (임계 구역) : 프로세스의 코드 중에서 공유 데이터를 접근하는 부분
• remainder section : 공유 데이터 변수 접근과 관련 없는 부분
• entry section / exit section : 임계 구역에 진입하기 전, 후에 수행해야 되는 부분
• 한 프로세스가 임계 구역에 있는 동안 다른 프로세스들은 그들의 임계 구역을 수행하면 안됨

Solution of Critical Section Problem

• 예시

  do {
  	while (turn == j);	/* entry section */
    
    		/* critical section */
            
    	turn = j; 		/* exit section */
        
        	/* remainder section */
            
   } while (true);

  • entry section은 critical section에 진입하기 위해 해야 하는 일을 수행하며, 반복문이 사용되는 경우가 많음
• 아래 3가지를 만족해야 solution으로 인정됨
  1. Mutual Exclusion
     • 프로세스 Pi가 자신의 임계 구역을 실행하는 동안 다른 프로세스는 그들의 임계 구역을 실행훌 수 없음
  2. Progress
     • 임계 구역을 실행하는 프로세스가 하나도 없고 그 중에 일부 프로세스가 임계 구역에 진입하려고 한다면 이들만이 다음번 임계 구역에 진입할 프로세스를 결정하는데 참여할 수 있음
     • remainder section을 실행 중인 프로세스는 다른 프로세스가 임계 구역에 진입하는 것에 영향을 미치면 안됨
     • 임계 구역 진입 결정은 entry section을 실행하면서 임계 구역 진입을 시도하는 프로세스들 간에만 이뤄져야 함
  3. Bounded Waiting
     • 프로세스가 자신의 임계 구역에 진입하려고 요청한 이후로부터 그 요청이 허용될 때까지는 그 시도 횟수에 한계가 있어야 함
     • 프로세스는 유한번 진입 시도 후에 임계 구역에 진입 가능

---

Peterson's Solution

• critical section에 대한 순수한 소프트웨어적 해결책
• CPU 명령 중 load와 store 명령이 atomic 하다는 것을 가정
  • atomic : 두 프로세스가 각각 다른 코어에서 실행되며 동시에 어떤 메모리 상의 변수 x에 접근할 때 한 번에 하나씩 순차적으로 접근이 이뤄지도록 하드웨어가 보장함
• 프로세스는 두 가지 변수를 공유
  • int turn : 이번에 어느 프로세스가 임계 구역에 진입할 차례인지 나타내는 변수
  • Boolean flag[2] : 프로세스가 임계 구역에 진입할 준비가 되었는지를 나타내는 변수

Algorithm for Process P0 and P1

• P0

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

  • entry section
    • flag[0]을 true로 만들어서 자신이 임계 구역에 진입하고자 하는 의사를 표시
    • turn을 1로 지정하여 자신보다 P1이 임계 구역에 진입하기를 원한다면 진입할 수 있도록 보장
  • exit section
    • P0 입장에서 자신은 더 이상 critical section에 있지 않음을 표시
  • P0의 critical section 진입 조건
    • flag[1] == 0 : P1은 자신의 임계 구역을 빠져나가면서 flag[1]을 0으로 만듦
      → P1이 remainder section을 수행 중
    • turn == 0 : P1의 entry section에서 turn을 0으로 설정
      → P1 관점에서 P0에게 먼저 critical section에 진입하도록 허락
• P1

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

Peterson's Solution은 올바른 해결책인가

• Mutual Exclusion
  • P0과 P1은 절대로 동시에 critical section에 머물지 않음
• Progress and Bounded-Waiting
  • P0는 while문을 수행하는 동안 turn의 값을 바꾸지 않기 때문에 P0는 P1이 지난번에 진입을 했다면 이번에는 자신도 한 번은 들어갈 수 있게 되어 progress 조건이 만족하고, 또한 이 상황에서 대기 시간도 한없이 길어지지 않음을 알 수 있음

---

Synchronization Hardware

• 대부분 시스템에서 임계 구역 문제를 해결하기 위한 하드웨어적 지원을 제공
• 단일 CPU 시스템에서는 interrupt를 끔으로써 간단하게 해결
  • 임계 구역 진입시 interrupt를 끄고 빠져나올 때 다시 켬으로써 상호 배제를 보장
  • 멀티 프로세서 상에서는 비효율적이므로 적용 불가능
    → interrupt를 disable 시키는 것이 모든 프로세스에게 전달되므로 상당한 시간 소요
• 현대 CPU에서는 특정 메모리의 한 word 내용을 검사하고 값을 변경하거나, 두 개의 메모리 word의 값을 atomic하게 교환할 수 있는 특별한 CPU 명령을 제공

test_and_set

boolean test_and_set (boolean *target)
{
	boolean rv = *target;
    *target = TRUE;
    return rv;		/* target의 오리지널 값을 리턴 */
}

• 편의를 위해 함수 형태로 작성했지만 이는 메모리의 특정 위치에서 동작하는 CPU 명령임에 유의
• 메모리의 특정 위치의 값을 읽어냄과 동시에 이 위치의 값을 1로 만드는 명령

Solution using test_and_set

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

• 공유 변수 lock을 사용하며 초기값은 false
• test_and_set을 하면 false가 읽혀지고 lock의 값은 true가 됨
• 하나의 프로세스가 critical section에 있는 동안 lock의 값은 항상 true가 되므로, 다른 프로세스가 진입을 시도하면 while문에서 벗어날 수 없음

compare_and_swap

int compare_and_swap (int *value, int expected, int new_value)
{
	int temp = *value;
    
    if (*value == expected)
    	*value = new_value;
    
    return temp;	/* value의 오리지널 값을 리턴 */
}

• value : compare_and_swap이 읽어내는 대상이 되는 메모리값
• value의 값이 expected와 같다면 value의 값을 new_value로 변경

Solution using compare_and_swap

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

• lock의 초기값은 0
• lock의 값이 0인 경우 compare_and_swap을 통해 값 0을 읽고 lock의 값을 1로 변경
• 한 프로세스가 critical section 안에 있는 동안 lock의 값은 항상 1임

Bounded-Waiting Mutual Exclusion with test_and_set

do {
	waiting[i] = true;
    key = true;
    while (waiting[i] && key)
    	key = test_and_set(&lock);
    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);

• lock : test_and_set의 대상이 되는 공유 변수
• waiting[n] : 프로세스 n개가 있고 waiting[i] == true일 때 프로세스 Pi가 자신의 임계 구역에 진입하기를 원한다는 의미
• entry section
  • test_and_set으로 lock의 값을 읽어서 true이면 반복하게 되어 임계 구역에 진입하지 못함
  • 다른 프로세스의 exit section에서 waiting[i]가 false로 바뀌면 임계 구역에 진입
• exit section
  • 프로세스 Pi 입장에서 n개의 프로세스 중 자기 다음번 프로세스 중 waiting[j]가 true인 첫 번째 프로세스를 찾음
  • waiting[j]가 true인 프로세스를 찾지 못한 경우 임계 구역에 있는 프로세스가 없다는 의미이므로 lock을 false로 변경
  • waiting[j]가 true인 프로세스가 있는 경우 이를 임계 구역에 진입시키기 위해 waiting[j]를 false로 변경
• 한 프로세스가 빠져나오면서 다른 프로세스를 임계 구역에 진입시켜주기 때문에 어느 프로세스라도 일정한 시간이 흐른 뒤 임계 구역에 진입할 수 있게 됨

---

Mutex Lock

• OS를 설계하는 사람들이 임계 구역 문제를 쉽게 해결하기 위해 개발한 소프트웨어적 도구
• 임계 구역 진입 가능 여부를 나타내는 boolean 타입 변수
• acquire()를 통해 lock을 얻어서 임계 구역에 진입하고, release()를 통해 lock을 해제하여 임계 구역에서 빠져나갈 수 있음
  • acquire()과 release()는 atomic하게 동작하며, 이를 구현하기 위해 내부에서 test_and_set 등이 사용됨
• mutex lock은 lock을 얻기 위해 반복문을 수행하는 형태로 구현
  → busy waiting
• spinlock이라고 부르기도 함

acquire() and release()

acquire() {
	while (!available)
    	;	/* busy wait */
    available = false;
}

release() {
	available = true;
}

• available 값이 true인 동안 임계 구역 진입을 막음
• busy wait : while문의 코드를 반복하면서 (CPU 사이클을 소모하면서) available의 값이 0이 되기를 기다림

---

참고 자료 : Operating System Concepts Essentials
*이미지 자료는 교재 자료를 직접 다시 만든 것으로 무단 불펌 금지입니다

---

나머지는 다음편에 이어서!

끄읏!