[CS] OS - 프로세스 동기화

프로세스 동기화

프로세스가 서로 메시지를 보내고 내부에서 스레드끼리 자원을 공유하는 과정에서 공유된 자원에 여러 프로세스, 여러 스레드가 동시에 접근하면서 문제가 발생했을 때 경쟁 상태를 막기 위한 방법이다.
여러 스레드에게 하나의 자원에 대한 처리 권한을 주거나 순서를 조정한다.

 
-> 공유 데이터의 동시 접근은 데이터의 불일치(Rare Condition)를 발생시킬 수 있기 때문에 일관성 유지를 위해 협업 프로세스 간 순서 매커니즘이 필요하다.

 
 

경쟁 상태 Rare Condition

여러 개의 프로세스가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과값이 달라질 수 있는 현상.
컴퓨터의 입장에서 아주 큰 문제이다 -> 같은 코드를 돌리면 항상 결과가 같아야 하는데 경쟁 상태 발생 시 결과가 달라질 수 있기 때문.
이런 문제를 방지하기 위해 공유 메모리를 사용하는 프로세스끼리 동기화를 해주는 것 즉, 경쟁 상태에 대한 해결 방법이 동기화이다.
 
경쟁 상태 예시

• 커널 모드 수행 중 interrupt 발생
  커널모드 실행 중 인터럽트가 발생해 인터럽트 처리 루틴이 실행된다. 양쪽 모두 커널 모드의 코드이기 때문에 kernel address space가 공유된다.
• 프로세스가 system call을 통해 커널 모드 수행중일때 context switch 발생

 

---

임계 구역(영역) Critical Section

n개의 프로세스가 공유데이터를 동시에 사용하기 원하는 경우 각 프로세스의 code segement에는 공유 데이터에 접근하는 임계 구역이 존재한다. 즉, 경쟁 상태가 발생할 수 있는 코드의 조각들이다. (동시에 접근해서는 안되는 공유 자원에 접근하는 코드의 일부)
 
임계구역 문제
임계구역에서 경쟁 상태가 발생한 것을 말한다. (임계구역 문제를 해결한다 = 경쟁 상태 해결한다)
 
임계 구역 필수 충족 조건

1. 상호 배제 Mutual Exclusion
   하나의 자원에는 하나의 프로세스만 접근할 수 있어야 한다.
   프로세스가 임계 구역 부분을 수행중이면 다른 모든 프로그램들은 그 임계 구역에 들어가서는 안된다.
2. 진행 Progress
   임계 구역이 비어있으면 자원을 사용할 수 있어야(들어가고자 하는 프로세스는 들어갈 수 있어야) 한다 -> deadlock free
3. 유한(한정된, 한계) 대기 Bounded Waiting
   기다리다보면 언제가는 임계 구역에 진입할 수 있어야 한다 -> starvation free
   프로세스가 임계 구역에 들어가려고 요청한 후부터 요청 허용시까지 다른 프로세스들이 임계 구역에 들어가는 횟수는 유한하다.

 

---

 
임계 구역 문제 (경쟁 상태) 발생 예시

// process 1
do{
    wants[1] = true;
    while (wants[2]) {
    	wait();
    }
    CRITICAL SECTION
    wants[1] = false;
    REMAINKER SECTION
} while (TRUE);


// process 2
do {
    wants[2] = true;
    while (wants[1]) {
    	wait();
    }
    CRITICAl SECtiON
    wants[2] = false;
    REMAINDER SECTION
} while (TRUE);

 
위의 코드에서 코드의 흐름 순서에 따라 문제가 없을 수도 문제가 발생할 수도 있다. (상호배제는 기본 전제)

• 문제 X 정상적
  p2가 임계 구역 진입을 원한다. 이때 p1이 임계 구역 안에 있는지를 확인한다. 아직 없기에 p2가 임계 구역 안으로 진입한다.
  p1이 임계 구역 진입을 원한다. 이때 p2가 임계 구역 안에 있는지를 확인한다. 앞서 p2가 진입했기 때문에 p1은 대기한다.
  p2가 임계 구역에서 벗어난다. 대기 상태이던 p1이 임계 구역으로 진입한다. 수행 후 p1이 임계 구역을 벗어난다.
• 문제 O 비정상적 
  p2가 임계 구역 진입을 원한다. 이때 p1도 임계 구역 진입을 원한다.
  p2와 p1 모두 want[ ]=true 상태이기 때문에 두 프로세스가 모두 대기 상태가 된다. 즉, 무한 대기에 돌입한다.

 
즉, 위의 코드에서는 무한 대기에 빠지는 데드락이 발생할 수 있다. 임계 구역이 비어 있는데도 사용 못하고 있으므로 진행 조건 위반이며, 무한 대기에 빠져있기에 유한 대기 위반이다.
 
 
> 해결 (Peterson's Solution)
아직 내 차례가 아님을 나타내는 not_turn 변수 추가하는 방식으로 해결 가능하다.
not_turn 전역변수이기 때문에 무조건 하나의 프로세스만 lock 되어 상호 배재 해결된다. 진입 구역 직전에 not_turn 변수를 갱신하기 때문에 임계구역에 진입하지 못하는 상황은 발생하지 않게되어 진행과 유한대기가 해결된다.

for () {
    wants[i] = true;
    not_turn = i;
    
    while (wants[j] && not_turn == i) {
        wait();
    }
    
    CRITICAL SECTION
    
    wants[i] = false;
    
    REMAINDER SECTION

 
위의 코드와 같은 피터슨의 방식은 상호배제, 진행, 유한대기의 조건을 모두 만족하지만 프로세스가 2개인 경우에만 적용 가능하기 때문에 실용성은 거의 없다고 볼 수 있다. 또한 피터슨 방법은 소프트웨어적 방식으로 현대 컴퓨터에서는 정상 작동하지 않으며 2개 중 하나가 임계 구역에 진입하여 다른 하나가 기다리는 동안 CPU를 계속해서 사용하기 때문에 자원 사용이 크다(Busy Waiting).
 

* 소프트웨어적 방식 : 짜여진 code에 의해 수행되기 때문에 도중에 context switch가 발생할 수 있다.
* 하드웨어적 방식 : 전기적 회로에 의해 수행되어 작업 자체가 실행 단위가 되어 context switch가 발생할 수 없으며 속도가 빠르다.

 
 
> 2차 해결 (하드웨어적 방식)
하드웨어적 방식은 원자적 실행 단위를 보장하기 때문에 코드 순서가 바뀌는 일(소프트웨어적 방식의 문제점)이 없다.
 
Mutex(Mutual Exclusion) Locks
공유된 자원의 데이터에 여러 프로세스, 스레드가 접근하는 것을 막는 것으로, 임계 구역을 가진 스레드들의 Running time이 서로 겹치지 않도록 각각 단독으로 실행되게 한다. 무조건 1개만 가질 수 있어 다른 프로세스(스레드)가 key를 반납한 경우에만 사용 가능하다.
acquire(), release() 함수를 사용해 available이라는 boolean 변수로 locking/unlocking 잠금 여부를 확인해 공유 자원에 접근을 제한한다.
 
위의 방식은 여전히 busy waiting 문제점을 지니고 있어 필요 없이 CPU를 점유하고 있는 경우가 발생해 자원을 낭비하게 된다.
 
 
> 3차 해결 (busy waiting 프로세스 강제로 wait state 보내기)
 
세마포어 Semaphore
공유된 자원의 데이터에 여러 프로세스, 스레드가 접근하는 것을 막는 것으로, 동시에 접근할 수 있는 허용 가능 갯수(Count)를 가진다.
세마포러는 소유할 수 없어 세마포어를 소유하지 않은 스레드가 세마포어를 해제할 수 있는 문제가 발생한다.
Mutex의 busy waiting(spin lock) 문제를 해결해주는 동기화 방법이다.
Mutex에서는 참/거짓의 값만 가진 boolean 변수 lock만 이용 하지만 Semaphore에서는 integer 값의 변수를 이용한다.
진입 구역과 퇴출 구역을 각각 wait()함수와 signal()함수가 담당한다.
구조체의 Count 값에 따라서 Binary Semaphore / Counting Semaphore로 나누어져 각 종류에 따라 두 함수가 다르게 정의된다.

• Binary Semaphore
  세마포어 구조체의 Count 값이 1로 초기화된 경우로, 즉 사용 가능한 자원이 1개여서 여러 개의 프로세스가 하나의 자원을 가지고 경쟁한다. Mutex Lock과 거의 비슷하지만 세마포어는 waiting queue를 가져 busy waiting 현상을 방지할 수 있다.
• Counting Semaphore
  세마포어 구조체의 Count 값이 1보다 큰 값(2개 이상)으로 초기화된 경우로, 여러 프로세스에 제한된 양의 자원을 할당해 줄 때 유용하다. 사용가능한 자원이 여러개이므로 임계 구역에 진입 가능한 프로세스도 여러개이다.

 
 
Mutex 등 busy waiting한 경우 vs. Semaphore 등 Block & Wakeup한 경우
 
두 방법 모두 오버헤드가 발생하기 때문에 그 시간이 짧게 걸리는 방법을 각 상황에 맞게 사용하면 된다.

- 임계 구역이 매우 짧고, 진입하고자 하는 프로세스가 많지 않아 busy waiting하게 되더라도 그 시간이 적으면 busy waiting 하는것이 오히려 유리하다.
- 임계 구역이 매우 길고, 진입하고자 하는 프로세스가 매우 많다면 Block & Wakeup 구조가 유리하다.

 
위의 경우에도 Deadlock, Starvation의 문제가 있다.
 
Deadlock
둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 영원히 기다리는 현상.
만약 두 프로세스가 모두 wait()함수를 호출하면 모두 block 상태가 되어 어느 것도 signal()함수를 호출할 수 없어 ready queue에서 빠져나올 수 없이 block 상태로 영원히 기다리는 현상.
서로를 영원히 기다리게 되어 semaphore 큐에서 빠져나갈 수 없는 Starvation 현상을 동반한다.
 
Priority Inversion 우선 순위 역전 현상
우선순위가 높은 프로세스가 block되어 우선순위가 낮은 프로세스가 점유하고 있는 자원을 wait()하고 있는 경우 우선순위가 낮은 프로세스가 먼저 실행되는 현상.
-> PIP(Priority Inheritance Protocol)를 이용해, 즉 우선순위가 높은 프로세스가 우선순위 낮은 프로세스의 자원을 대기하고 있을 때 자신의 우선순위를 상속하는 방식을 이용해 우선순위 역전 현상을 해결
 
 

---

* https://systorage.tistory.com/entry/CS-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%94
* https://charles098.tistory.com/91