운영체제 - Process synchronization

• Race Condition
  : 여러 프로세스가 공통된 데이터를 조작할 때 결과가 접근 순서에 의해 결정되는 현상
  
  

• Critical section
  : 프로세스의 코드의 일부분으로서, 다른 프로세스와 공동으로 사용하는 변수, 테이블, 파일 등을 변경하는 부분
  : 해결 방안
   1. 상호 배제(mutual exclusive) : 한 프로세스가 임계 구역에서 실행하고 있으면 어떤 프로세스도 임계 구역에 진입할 수 없어야 한다. SW로 가능하지만, 매우 복잡하여 HW로 대부분 보조
   2. 진행(progress) : 임계 구역을 실행하고 있는 프로세스가 없을 때, 몇 개의 프로세스가 임계 구역에 진입하고자 하면 이들의 진입 순서는 이들에 의해서만 결정되어야 한다. 또한 이 선택은 무한정 연기되어서는 안된다. 
   3. 한계 대기(bounded waiting) : 한 프로세스가 자신의 임계 구역에 진입하고자 요청을 한 후부터 이 요청이 허용될 때까지 다른 프로세스가 그들의 임계 구역에 진입할 수 있는 회수가 제한되어야한다.
  
   - Peterson's Solution (Dekker) : flag를 이용
   - Baker algorithm: 가게에 들어오는 손님들은 번호를 하나 받으며, 가장 낮은 번호를 받은 손님 순으로 서비스를 받는다. 그런데 모든 손님이 다른 번호를 받도록 보장할 수 없다. 만약 두 손님이 같은 번호를 받으면 이름 순으로 서비스를 받는다. 모두 다른 번호를 받도록 하기 위해서는 변호를 받는 것 자체가 임계 구역.
  
   - Bounded-Buffer problem
    

   - Readers and Writers problem
    
  

   - Dining-philosopher problem : 다익스트라가 제안, 다섯명의 철학자가 있다. 이들은 생각에 잠기거나 먹는 것 외에는 아무것도 하지 않는다. 철학자들은 원형 테이블에 앉아 있으며, 테이블 중앙에 밥이 있다. 그런데 젖가락이 다섯개 밖에 없다. 배가 고프면 철학자는 가장 가까이 있는 두개의 젖가락을 집는다. 철학자는 한 번에 하나의 젖가락만 집을 수 있으며, 옆 사람이 집고 있는 젖가락은 집을 수 없으며, 두 개의 젖가락을 모두 집어야 식사를 할 수 있다. 식사를 한 후에는 다시 두 개의 젖가락을 모두 내려놓고 생각에 잠긴다. -> 데드락 발생
  
   - Mutex
   : MUTual EXclusion으로 상호배제라고도 한다. Critical Section를 가진 스레드의 Running Time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술이다. 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 locking과 unlocking를 사용한다. 두 스레드가 동시에 사용할 수 없다는 의미.
  
   - Semaphore
   : 리소스의 상태를 나타내는 간단한 카운터

   
    ■ Busy waiting
     : 한 프로세스가 임계 구역에 있는 동안 다른 프로세스들은 임계구역에 진입하는 지속적인 loop 코드를 돌려야 한다.
     : 

  Busy waiting 을 하는 세마포어를 spinlock이라 한다.
     : spinlock은 문맥 전환이 필요없어 오래 동안 busy waiting을 하지 않는다면 효과적인 방법이다.
     : 성능저하를 초래할 수 있다 -> Semaphore
  
    ■ Blocking & Wake-up
     : 각 세마포어가 waiting queue에 할당
     : wait()로 block, signal()로 wake up 
     : wait와 signal을 반드시 원자적으로 수행
  
  - Mutex vs Semaphore 출처: http://ninako21.tistory.com/500
    : 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
    : 세마포어는 소유할 수 없는 반면 뮤텍스는 소유가 가능하며 소유주가 이에 대한 책임을 진다.
    : 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 이 뮤텍스를 해제할 수 있다. 하지만 세마포어의 경우 이러한 세마포어를 소유하지 않는 스레드가 세마포어를 해제할 수 있다.
    : 세마포어는 시스템 범위에 걸쳐 있고 파일 시스템상의 파일 형태로 존재한다. 반면 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 clean up 된다.
    : 가장 큰 차이점은 관리하는 동기화 대상의 갯수이다.
     뮤텍스는 동기화 대상이 오직 하나 뿐일 때, 세마포어는 동기화 대상이 하나 이상일 때 사용한다.
  
  - 모니터
    : 세마포어의 부적절한 사용으로 발생하는 에러를 해결하기 위한 높은 수준의 추상화 데이터 타입으로, 편리하고 효율적인 프로세스 동기화 메커니즘을 제공.