[OS][운영체제] 6. Process Synchronization / 프로세스 동기화(순서화)

1. Background
2. The Critical-Section Problem
3. Peterson’s Solution + 동기화 하드웨어 기법
4. Semaphores
5. Classic Problems of Synchronization
6. Synchronization Examples

---

1. Background

공유 데이터에 대한 동시 접근은 데이터 불일치가 일어나게 된다.

이를 막기 위해 Cooperating 프로세스들을 순서를 정해 실행해야 한다.

예를 들어, Consumer, Producer의 경우(Cooperating Processes)에 ‘buffer’ 데이터 인덱스에 접근하는 ‘count’ 전역 변수를 공유한다.

 

[사진 1] 공유 데이터 불일치 예시

위와 같이, counter++(파란색)과 counter--(빨간색) 명령이 Interleaving하여 데이터 불일치가 일어난다.

---

2. The Critical-Section Problem

[그림 2] 프로세스와 entry-critical-exit section

프로세스의 일반적인 구조는 위와 같다.

Entry-Section을 통해 Critical-Section에서 공유 변수의 값을 바꾸게 된다.

후에 Exit-Section으로 나오고 다른 프로세스가 Critical-Section에 들어갈 수 있도록 조건을 초기화해준다.

 

Critical-Section 문제 해결에 다음과 같은 3가지 조건이 있다.

• 상호 배제(Mutual Exclusion)
  • : 한 프로세스가 들어갔다면 다른 프로세스 들어갈 수 없음
• Progress
  • : critical section이 비어 들어가려 할 때, 프로세스를 선정하는 작업이 뒤로 밀려서는 안 됨
• Bounded Waiting
  • : 한정된 만큼만 기다리면 critical section에 들어갈 수 있도록 보장해줌

---

3. Peterson’s Solution

Peterson's Solution

프로세스 Pi

do { 
  flag[ i ] = TRUE;
  turn = j;
  while ( flag[ j ] && turn == j); //do nothing
  
    //CRITICAL SECTION
  
  flag[ i ] = FALSE;
  
    //REMAINDER SECTION

} while (TRUE);

 

프로세스 Pj

do {
  flag[ j ] = TRUE;
  turn = i; 
  while ( flag[ i ] && turn == i); //do nothing
  
    //CRITICAL SECTION 
    
  flag[ j ] = FALSE; 
    
    //REMAINDER SECTION
    
  } while (TRUE);

 

Peterson 해결은 두 프로세스일 때의 해결법이다.

• int turn;        // Pi와 Pj 누가 Critical-Section에 들어갈 차례인지
• Boolean flag[2];        // Critical-Section에 들어갈 준비가 되었는지

• turn 변수로 상호 배제 조건 O
• Exit Section 나오면서 flag 바꿔 progress 조건 O
• flag로 인해 Pi, Pj 차례로 들어갈 수 있게 하여 bounded waiting 조건 O

Bakery 알고리즘

이는 빵집에서 번호표를 나누어 주듯이, 프로세스에 numbering하는 알고리즘이다

 

do {
  choosing[ i ] = true; 
  number[ i ] = max(number[0], number[1], …, number [n – 1])+1; 
  choosing [ i ] = false; 
  for ( j = 0; j < n; j++) { 
    while (choosing[ j ]) ; //do nothing
    while ((number[ j ] != 0) && (number[ j ], j) < (number[ i ], i)) ; //do nothing
  } 
  
    //critical section 
  
  number[ i ] = 0; 
  
    //remainder section

} while (1);

number[i] 는 여태 받는 number보다 1 큰 값이고,

j 경우가 번호표 받는 과정일 경우 + number나 ID가 작을 경우 while에 걸린다

 

이는 n개 프로세스 사이에서의 해결법이다.

번호가 같다면, 프로세스 ID 값을 비교해 작은 프로세스가 first로 실행된다

• Boolean choosing[n];      // 번호표를 받는 과정인지
• int number[n];      // 번호표 숫자

---

3-1. 동기화 하드웨어 기법

Pi가 인터럽트 될 때 Pj가 들어오는 경우를 방지하기 위해, Uniprocessor로 disable interrupts(인터럽트 시스템을 끔)한다.

이는 여러 CPU에서 동작하기에 너무 비효율적이다.

이에 따라 시스템 확장성에 문제가 생긴다.

 

현대 machines는 atomic한 (non-interruptable) 하드웨어 명령을 제공한다.

 

TestAndSet 명령

boolean TestAndSet (boolean *target) { 
  boolean rv = *target; 
  *target = TRUE; 
  return rv: 
}

do { 
  while ( TestAndSet (&lock) ) ; // do nothing 
  
    // critical section 
    
  lock = FALSE; 
  
    // remainder section 
    
} while (TRUE);

lock은 false로 초기화한다

 

lock이 true로 바뀌어 두번째로 들어오는 프로세스는 while에 걸려 loop를 돈다.

-> busy waiting (조건을 계속 체크), spinlock (자물쇠를 열기위해 계속 헛도는 현상)

 

• lock 변수로 상호 배제 조건 O
• lock을 false로 바꾸며 Exit하여 progress 조건 O
• 넘버링이 되어있지 않아 bounded waiting은 만족 X (둘일 때만 가능)

Swap 명령

void Swap (boolean *a, boolean *b) { 
  boolean temp = *a; 
  *a = *b; 
  *b = temp: 
}

do { 
  key = TRUE; 
  while (key == TRUE) Swap (&lock, &key ) .. ;
    
    // critical section 
    
  lock = FALSE;
    
    // remainder section
    
} while ( TRUE);

전역 변수 lock은 false로 초기화하고, 지역 변수 key를 이용한다

 

• lock과 key 변수로 상호 배제 조건 O
• lock을 false로 바꾸며 Exit하여 progress 조건 O
• 넘버링이 되어있지 않아 bounded waiting은 만족 X (둘일 때만 가능)
  • 이를 만족시키기 위해서 waiting[i] 변수를 추가한다

---

4. Semaphores

Semaphore(세마포어)는 CS(Critical Section)에 들어가기 위해 busy waiting을 요구하지 않는 (-> block, wake up) 동기화 도구이다.

 

이는 두 독립적인(atomic) 명령이 있다.

 

wait (S) { 
  while (S <= 0) ; // no-op 
  S--; 
}

signal (S) { 
  S++; 
}

 

세마포어는 정수값으로 이루어지며(Counting Semaphore),

 

0과 1로만 이루어진 Binary Semaphore는 Mutex(mutual exclusion) Locks라고 부른다.

Mutex Locks는 다음과 같이 이루어진다.

 

Semaphore S; // initialized to 1

wait (S);

  //Critical Section

signal (S);

 

P2보다 P1를 먼저 실행시키고 싶을 때,

[사진 3]과 같이 P2 실행 전에 Wait(S)을, P1 실행 후에 Signal(S)를 넣는다.

 

[사진 3] 세마포어 예시

두 프로세스는 동시에 같은 세마포어에서 wait(), signal()을 실행하면 안 된다.

이를 위해 Spinlock(busy waiting이 짧을 때), Context Switching(busy waiting이 길 때) 방법을 쓰지만,

이는 CS에서 긴 시간을 보내게 되어 좋은 해결책이 아니다.

 

따라서 busy waiting이 없는 세마포어에서는

waiting queue를 각 세마포어에 두어 (value, pointer) 다음 명령이 가능하다.

• block: 프로세스를 중지시켜 waiting queue에 넣는다
• wakeup: waiting queue에서 깨워 ready queue에 넣는다

이는 다음과 같이 이루어진다

 

wait (S){ 
  value--; 
  if (value < 0) { 
    //add this process to waiting queue 
    block();
  } 
  
    // waiting state 
  
}

// Critical Section

Signal (S){ 
  value++; 
  if (value <= 0) { 
    //remove a process P from the waiting queue
    wakeup(P); 
  } 
  
    // ready state 

}

[사진 4] 세마포어 waiting Q

다른 프로세스 못들어오게 value<0이면 waiting Q에 넣고,

하나씩 CS 실행하면서 value 높이고,

하나씩 ready Q로 들여보내게 된다.

Deadlock & Starvation 문제

Deadlock: 프로세스들 간에 풀어줘야 하는 조건을 풀어주지 못해 무한정 Waiting

 

[사진 5] Deadlock 예시

-> Starvation 상태(프로세스는 세마포어 큐에서 무한정 Blocking)

---

5. Classic Problems of Synchronization

Bounded-Buffer Problem

(이 외에 Readers and Writers Problem, Dining-Philosophers Problem 등이 있다)

Bounded-Buffer의 경우에는 다음 공유 변수를 이용한다.

• 세마포어 mutex: 1로 초기화
• 세마포어 full: 0으로 초기화
• 세마포어 empty: N으로 초기화

 

Producer의 process 구조는 다음과 같다

 

do { 

    // produce an item 
  
  wait (empty); 
  wait (mutex); 
  
    // add the item to the buffer 
    
  signal (mutex);   
  signal (full); 
  
} while (true);

wait(mutex): CS로 들어가 buffer에 접근

signal(mutex): 다른 프로세스 들어올 수 있도록

-> wait(empty)와 signal(full)로 인해 empty와 full이 각각 1씩 감소하고 증가한다.

 

Consumer의 process 구조는 다음과 같다

 

do { 

  wait (full); 
  wait (mutex); 
  
    // remove an item from buffer 
    
  signal (mutex); 
  signal (empty); 
  
    // consume the removed item 

} while (true);

wait(mutex): CS로 들어가 buffer에 접근

signal(mutex): 다른 프로세스 들어올 수 있도록

-> wait(full)과 signal(empty)로 인해 full과 empty가 각각 1씩 감소하고 증가한다.

 

Producer와 Consumer의 N=3이라고 하고, p-p-p-p-c-c-c-c 순서라고 가정해보자

 

[사진 6] Bounded-Buffer 일 때의 예시

---

6. Synchronization Examples

Solaris Synchronization

multitasking, multithreading, multiprocessing을 위한 다양한 lock을 사용한다.

• Adaptive Mutexes(run 상태면 spin, 아니면 block / spin, busy waiting보다는 sleep, block)
• Condition Variables(Wait, Sleep), Readers-Writers locks
• Turnstiles(mutex를 획득하기 위해 기다리는 스레드를 순서화)

Windows XP Synchronization

CPU가 하나일 때(Uniprocessor systems)는 Interrupt masking(인터럽트를 끔)

• Spinlocks
• Dispatcher Object
• Condition Variable

Linux Synchronization

Disables Interrupts

• Semaphores
• Spin Locks
• Kernel preemption, non preemption

Pthreads Synchronization

OS와 독립적인 API

• mutex locks
• condition variables(wait & sleep)

Non-portable에는 다음을 포함한다

• read-write locks
• spin locks