[OS] 프로세스 동기화

본 내용은 Operating System Concepts 8th Edition 번역본 책을 읽고 공부한 내용입니다.

목차
1. 동기화 문제
  1) 생산자 소비자 문제
  2) Too much milk 문제
  3) 메모리 적재와 연산 도중의 문제
2. 동기화 문제의 해결책
  1) 동기화 개념 4가지
  2) 멀티스레드 동기화 기법 해결 방법
  3) 메모리 적재와 연산 도중의 문제
3. 임계 영역 문제의 해결책
  1) 싱글스레드 환경에서의 해결책
  2) n개의 프로세스가 있는 멀티스레드 시스템에서 임계 영역 문제를 해결하기 위해 충족해야 하는 세 가지 요구조건
  3) 메모리 적재와 연산 도중의 문제
4. 임계 영역에 대한 소프트웨어 기반 해결책, 알고리즘
  1) 피터슨의 해결안(Peterson's solution)
5. 세마포
  1) 세마포란?
  2) 세마포 구조
  3) 세마포로 해결할 수 있는 문제
  4) 세마포 사용 과정
  5) 세마포 구현

1. 동기화 문제

1. 생산자-소비자 문제
concurrent process에서 공유 변수의 존재 때문에 일어나는 동기화 문제를 의미한다.
생성자는 데이터를 생성하고, 소비자는 그것을 소비하려고 한다.
이 때 공통변수 업데이트 구간인 임계구역에 생성자 소비자 모두 들어갈 수 있다. 따라서 데이터의 변화가 따로 발생 가능하다. 아래 코드에서 볼 수 있듯, 생산자가 count를 올리고 있는 도중에 문맥전환(context-switching)에 의해 소비자가 돌게 되어 count를 낮추는 작업을 하게 되면 count의 값에 오류가(interleaving) 발생하는 것이다. 
아래 interleaving 차트를 보면 counter값이 T4와 T5에서 6과 4로 들쑥날쑥하게 나오는 현상이 발생한다.

2. Too much milk 문제
1. 철수가 냉장고를 열어보니 우유가 없다. 철수가 우유를 사러 간다.
2. 영희가 냉장고를 열어보니 우유가 없다. 영희가 우유를 사러 간다.
3. 철수가 우유를 사온다.
4. 영희가 우유를 사온다.
5. 이제 우유가 너무 많다.
...
여기에서 문제는 "냉장고를 열어보니 우유가 없다"와 "우유를 사서 냉장고에 넣는다"가 서로 원자성 연산이 아니기 때문에 나타난다. 쓸 데 없이 우유가 너무 많아질 수 있다.
3. 메모리 적재와 연산 도중의 문제
아래 두 thread에서도 서로 같은 i 변수를 공유하고 있기 때문에 문제가 발생할 수 있다.
1번 문제와 이유는 동일하다.

 

---

2. 동기화 문제의 해결책

1. 동기화 개념 4가지

• 동기화(Synchronization)
  스레드 간 협동을 보장하기 위해 원자성의 연산들을 사용한다.
• 상호배제(Mutual exclusion)
  오직 한 스레드가 한 번에 한 활동만 하도록 보장한다.
• 임계 영역(Critical section)
  한 번에 한 스레드만 수행되도록 한다.
• 락(Lock)
  간단히 예시로 설명해보자면, 위에 생산자-소비자 문제를 해결하기 위해서는 생산자는 더 이상 가져갈 것이 없을 때 buffer에 자물쇠를 잠궈 소비자가 애초에 접근할 수 없도록 하여 이 문제를 해결할 수 있다.

2. 멀티스레드 동기화 기법 해결 방법

• 락(Lock) 방식 - 뮤텍스(mutex), 스핀락(spinlock)
• wait-signal 방식 - 세마포(semaphore)

---

3. 임계 영역 문제의 해결책

1. 싱글스레드 환경에서의 해결책
싱글스레드 환경에서는 그냥 간단히 interrupt를 막아버리면 된다.
2. n개의 프로세스가 있는 멀티스레드 시스템에서 임계 영역 문제를 해결하기 위해 충족해야 하는 세 가지 요구조건

• 상호 배제(mutual exclusion)
  프로세스 Pi가 자신의 임계 영역에서 실행된다면 다른 프로세스들은 그들 자신의 임계 영역에서 실행될 수 없다.
• 진행(progress)
  임계 구역을 실행하고 있는 프로세스가 없을 때, 몇 개의 프로세스가 임계 구역에 진입하고자 하면 이들의 진입 순서는 이들에 의해서만 결정되어야 한다. 또한 이 선택은 무한정 연기되어서는 안된다. 
  임계 구역에 오고 싶다면, 조건이 맞는대로 들어올 수 있어야 한다.
• 한정된 대기(bounded waiting)
  프로세스가 자신의 임계 영역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 자신의 임계 영역에 진입하도록 허용되는 횟수는 한계 또는 제한이 있어야 한다.
  쉽게 말해, 각 프로세스는 "나만 기아 상태에 안 걸리면 돼! 임계 영역에 적어도 한 번은 들어갈 수 있어야 해!" 라고 외친다고 생각하자.

---

4. 임계 영역에 대한 소프트웨어 기반 해결책, 알고리즘

1. 피터슨의 해결안(Peterson's solution)
critical sections와 remainder sections를 번갈아 가며 실행하는 두 개의 프로세스가 있는 상황을 전제로 한다.

위의 코드를 한 번 쉬운 상황으로 풀어보자!
A라는 사람의 집과 B라는 사람의 집이 있다. 두 집에는 강아지가 있는데 이 두 강아지는 만나면 싸운다. 
그래서 서로의 깃발을 사용해서 지금 누가 산책하고 있는지를 서로 알려주려고 한다.

A가 산책하는 권한이 있다면, 내가 이 명령어를 쓸 수 있는 동안 계속해서 산책을 해도 된다.(임계 영역에 들어와 있어도 된다.)

while (t2_in_crit ==true && turn != 1)

A가 산책을 다 했다면 나 다 끝났어! 라는 명령어를 준다.

t1_in_crit=false; //B에게 산책해도 된다는 권한을 준다.

사실상 turn은 임계영역 접근에 대한 context switching 감독관 역할을 한다고 볼 수 있다.

5. 세마포(semaphore)

1. 세마포란?
세마포는 임계 영역 문제에 대한 하드웨어 기반 해결책으로 강력하게 제시되는 수단이다.
세마포는 정수 변수로 초기화를 한 후, 단지 두 개의 원자성 연산(atomic operation) wait()와 signal()로만 접근이 가능함을 전제로 한다.
2. 세마포 구조

• 세마포를 쓰고 싶은 자원이 존재한다. (n개라고 가정하자.)
• 대기 큐가 존재한다. 자원을 할당하지 못한 스레드가 이곳에서 잠자고 있다.
• counter 변수 - 아래 공에 쓰여져 있는 숫자로, 사용 가능한 자원 개수를 의미한다. 만약 음수라면 자원을 기다리는 스레드의 개수이다. 
• P/V 연산 : P 연산은 자원 요청 시(사용을 허가받았다), V 연산은 자원 반환 시(나 다 썼어) 사용한다.

다음 그림으로 세마포를 가장 쉽게, 직관적으로 설명할 수 있다.
프로세스는 CS에 access하고자 한다면 손을 주머니 속에 넣어 공(주도권)을 꺼내갔다가 다 쓰면 다시 넣어두면 된다!

3. 세마포로 해결할 수 있는 문제
위에서 말한 Too much milk 문제를 해결할 수 있다.
아래 그림에서 A와 B 중 먼저 이 주머니에 손을 넣어 세마포를 가져가면 그 Thread가 먼저 사용권을 가진다. 
못 가져간 thread는 대기한다.

4. 세마포 사용 과정
맨 처음, 저 주머니 안에 공을 1로 초기화해둔다고 하자. 
그러면 일단 Thread A가 먼저 선점하면 공 상태가 0이 된다. 이 때 Thread B, Thread C 모두 접근을 하면 이 공은 -2까지 줄어들어 음수로 표현될 수 있다. -2는 '두 개가 현재 대기중이다'를 의미한다.
이제 A가 반납을 한다면 공은 1이 증가되어 -1이 되고, A는 대기하고 있는 프로세스들을 깨운다. 이후 우선순위가 가장 높은 Thread가 또 공을 선점하게 된다.
 
5. 세마포 구현
세마포의 주된 단점은 이들이 모두 바쁜 대기(busy waiting)을 요구한다는 점이다. 한 프로세스가 자신의 임계 영역에 있으면, 자신의 임계 영역에 진입하려는 프로세스는 진입 코드를 계속 반복 실행해야 한다. 이러한 계속적인 반복은 다중 프로그래밍에서 큰 문제가 된다.

따라서 아래와 같이 다양한 방법을 사용하여 세마포어의 busy waiting의 한계를 극복할 수 있다.

1. busy waiting을 이용하여 세마포 구현 (앞에서 본 내용이다.)
   busy waiting은 프로세스가 다른 프로세스가 공유 자원을 사용하고 있을 때 계속해서 검사하는 방식이다. 
   
2. interrupt를 disable시켜 세마포 구현
   interrupt를 disable시키는 방식은 세마포 변수에 대한 접근을 원자적으로 수행하도록 보장하며, 공유 자원을 사용할 수 없는 경우에는 다른 프로세스로 컨텍스트 전환이 일어난다. CPU 자원을 더 효율적으로 사용할 수 있습니다.
3. test&set 명령어를 사용하여 세마포 구현
   test&set 명령어는 공유 자원을 사용하는 프로세스가 test&set 명령어를 사용하여 세마포 변수를 확인하고 세마포 변수의 값을 변경하여 공유 자원을 사용할 수 있는지 확인한다.
   이 방법은 busy waiting 방식보다는 더 효율적이지만, interrupt를 disable시키는 방식보다는 덜 효율적일 수 있다.
   

---

스핀락 VS 뮤텍스 VS 세마포어

• 스핀락(loop)
  임계 구역에 들어갈 때까지 루프를 돌며 재시도 → busy waiting
  스케줄링 지원을 받지 않기 때문에 context switching이 일어날 수 없다.
• 뮤텍스(wait, signal)
  권한을 획득할 때까지 busy waiting 상태에 머무르지 않고 sleep 상태에 들어가고 wakeup 되면 다시 권한을 시도함
• 세마포어 (이진 세마포어-사실상 뮤텍스 / 개수 세마포어)
  busy-waiting과 block-wakeup 두 가지 방식이 있다.
  busy waiting = 스핀락
  block-wakeup = block()을 호출하면 그 프로세스를 wait queue에 넣는다. wakup(P)는 blocked 프로세스 P를 깨워 ready queue로 옮긴다.