[OS] Process Syncronization

Background

공유된 데이터에 동시에 접근해서 write을 하는 것은 데이터 불일치를 유발할 수 있다. 이렇게 공유된 데이터를 동시에 여러 프로세스가 건드리는 상황을 Race condition이라고 한다. 결과적으로 최종값은 누가 그 데이터를 마지막으로 건드렸냐에 달려있게 된다. 이런 Race condition을 막기 위해 병렬로 실행되는 프로세스들은 동기화(synchronized)되어야 한다.

The Critical-Section Problem

• 그럼 Critical-Section Problem, 임계 구역 문제가 무엇인지부터 살펴보자.
• n개의 프로세스들이 공유된 데이터를 사용하기 위해 경쟁하고 있다고 가정해보자. 각각의 프로세스들은 공유된 데이터에 접근하는 코드 부분인 critical section을 가지고 있다. 우리는 하나의 프로세스가 본인의 critical section을 실행하고 있을 때 다른 프로세스가 그것의 critical section을 사용하지 않길 바란다. (Background에서 말한 동기화 문제 때문에!)
• 해결책을 위해서는 3가지 충족 조건이 요구된다.
  1. Mutual Exclusion 상호 배제
     • 어떤 프로세스가 critical section을 실행중이면 다른 프로세스들은 본인의 critical sections을 실행할 수 없다.
  2. Progress 진행
     • 만약 어떤 프로세스도 critical section을 실행하고 있지 않고, critical section을 실행하길 원하는 몇몇의 프로세스들이 있을 때, 대기하고 있는 프로세스들이 critical section을 실행할 수 있도록 해줘야 한다.
  3. Bounded Waiting 유한 대기
     • 프로세스가 critical section에 들어가기 위해 무한정으로 기다리는 현상 (=Starvation)이 일어나지 않기 위해 critical section을 실행하는 횟수에 제한(bound)가 있어야 한다.

---

Solution

1. 프로세스의 일반적인 구조
   
   • 단 2개의 프로세스 p0, p1이 있다고 가정한다.
   • 프로세스 pi의 구조는 다음과 같다. Entry section을 통해 critical section에서 공유 변수의 값을 바꾸고 후에 exit section으로 나와서 다른 프로세스가 cirtical section에 들어갈 수 잇또록 조건을 초기화해준다. 
   • do { entry section critical section exit section remainder section } while (1);​
   • 프로세스들은 그들의 액션을 동기화하기 위한 공유 변수를 사용한다.
2. Peterson's Algorithm

   // 프로세스 i 의 실행구조
   do {
       flag[i] = true; // 프로세스 i가 임계구역에 들어갈 준비가 됨
       turn = j; // 프로세스 j가 실행될 차례
       while (flag[j] && turn == j); // 프로세스 j가 임계구역에 들어갈 준비가 됬는지 && 프로세스 j가 임계구역에 들어갈 차례인지
       critical section // 프로세스 j가 임계구역 작업 마치고 flag[i]가 false가 되면 i는 무한루프 빠져나와 임계구역에 들어감
       flag[i] = false; // 프로세스 i가 작업 완료 후, flag[i] = false로 설정
       remainder section
   } while (true);

   • flag, turn 변수를 사용
   • flag: 특정한 프로세스가 임계구역으로 들어갈 준비가 되었다는 것을 나타냄 (true, false)
   • turn: 임계구역으로 진입할 프로세스의 순번 (1, 2, ...)
   • Mutual exclusion, Progress, bounded waiting 모두 만족
   • 2개의 프로세스뿐만이 아니라 3, 4개 이상의 프로세스로 쉽게 확장할 수 있다.
   • 문제점: Busy waiting (프로세스가 대기를 하고 있을 때도 CPU를 사용한다.)
3. 뮤텍스 락 (Mutex Lock)

   do {
       acquire lock // lock이 가용하다면 acquire()를 호출해서 lock을 획득하고, 다른 프로세스가 접근하지 못하도록 lock은 사용불가 처리
       critical section
       release lock // lock을 반환
       remainder section
   } while (true);
   
   acquire() {
       while (!available) /* busy wait */
       available = false;
   }
   
   release() {
       available = true;
   }

   • 프로세스가 임계구역에 들어가기전에 lock을 획득하고, 나올때는 lock을 반환하는 방식
   • mutex lock에서는 available이라는 변수를 가지고, 이 available 변수를 가지고 lock의 가용 여부를 판단
   • 단점: busy waiting (기다리면서 계속 반복 실행, CPU 시간 낭비)
4. 세마포어 (Semaphore)

   wait(S) {
       while (S <= 0)
           /* busy wait */
       S--;
   }
   
   signal(S) {
       S++;
   }

   • 카운팅 세마포어, 이진 세마포어가 있음.
   • 이진 세마포어는 0, 1로 동작하고 mutex lock과 유사
   • 카운팅 세마포어: 세마포어(S)는 프로세스가 임계구역에 들어가려할때, 즉 wait()을 호출할 때 값이 감소하고, 임계구역의 작업을 끝내고 lock을 반납할때(signal() 호출할때) 값이 증가. 만약 세마포어(S)가 0이 된다면 모든 자원들이 프로세스들에 의해 모두 사용중임을 의미. 이후 자원을 사용하려면 세마포어(S)가 0보다 커지기를 기다려야함.

---

전통적 동기화 예제

1. Producer-Consumer Problem
   • 생산자가 데이터를 생산 -> 소비자가 그 데이터를 소비하는 형태
   • 예시: 컴파일러->어셈블러, 웹 서버->웹 클라이언트
   • 생산한 데이터는 중간의 buffer라는 저장공간에 저장해두고 소비자는 여기서 필요한 만큼 가져감
   • 동기화 문제: 생산자와 소비자가 동시에 접근하는 변수를 동시에 업데이트, 즉 임계구역에 동시에 접근
2. Readers-Writers Problem
   • 임계구역에 접근하는 프로세스의 종류를 reader와 writer로 나눈다.
   • reader는 임계구역에서 데이터를 바꾸지 않고 읽기만 하는 프로세스, writer는 임계구역에서 데이터를 바꾸는 프로세스를 말한다.
   • 여기서 writer는 mutal exclusion을 보장하고, reader는 여러개가 동시에 데이터에 접근하는 것을 허용한다.
   • The first Reader Writer problem (readers-preference): reader 프로세스에 우선권을 줌. reader 프로세스가 데이터를 읽는 동안 writer 프로세스가 오면 기다리게 되고, reader 프로세스가 오면 writer 프로세스가 기다리는 것을 무시하고 데이터에 접근하여 읽음
   • The second Reader Writer problem (writers-preference): writer 프로세스에 우선권을 줌. 위와 같은 상황이라고 가정하자. writer 프로세스가 기다리는데 다른 reader 프로세스가 오면 writer 프로세스 다음 순서로 기다려야함.
   • The third Reader Writer problem: 아무에게도 우선순위를 주지 않는다.
3. Dining Philosopher Problem

   

   • 식사하는 철학자 문제
   • 원형 테이블에 5명의 철학자와 5개의 젓가락이 한짝식 있는 상황에서 일어나는 문제다.
   • 각 철학자는 "생각하기"와 "식사하기"를 반복한다. 단, 식사를 하기 위해서는 1쌍, 즉 2개의 젓가락이 필요하다.
   • 만약 0번 철학자가 4번 젓가락을 사용하게 되면 4번 철학자는 식사를 할 수 없어 0번 철학자가 식사를 마칠때까지 기다려야한다. 
   • 여기서 철학자를 스레드 혹은 프로세스, 젓가락을 세마포어로 생각할 수 있다. 
   • 그런데 여기서 문제가 생길 수 있다. 모든 철학자가 동시에 식사를 하려고 왼쪽 젓가락을 집으면 5명의 철학자가 5개의 젓가락을 모두 집어든 상황이 된다. 그 결과, 남아있는 젓가락은 없고 모든 철학자가 반대편 젓가락을 들기 위해 기다리게 된다. 하지만 식사할 수 있는 철학자는 없으므로 아무도 젓가락을 내려놓지 않고 하염없이 기다린다. 
   • 이런 상황을 교착상태(Deadlock)라고 한다. 교착상태에 대해서는 다음 게시글에서 알아보도록 한다.