프로세스 동기화 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킴
• 동시접근 이라는 단어 때문에 하나의 CPU에서 발생하는 race condition이 이해가 안갈 수 있다.
  • 하지만 오히려 하나의 CPU에서 여러개의 프로세스가 공유 데이터를 사용하려고 동작하는 과정에서 발생한다는 것을 안다면 이해가 쉬워진다.
• 일관성 유지를 위해 협력 프로세스 간 실행 순서를 정해주는 매커니즘이 필요함
• race condition 을 막기 위해서는 concurrent process는 동기화되어야 함

Race Condition : 여러 프로세스들이 공유 데이터를 접근하는 상황에서 데이터의 최종 연산 결과가 그 데이터를 다룬 마지막 프로세스에 따라 달라지는 현상

동기화

• 한정적인 시스템 자원에 여러 개의 쓰레드/ 프로세스 가 동시에 접근하면 작업의 결과값이 처리 순서에 따라 달라지는 문제가 발생할 수 있다. 즉, 동기화의 목적은 데이터 일관성(Data Consistency)을 보장해주는 것이다.

• 자원에 대한 처리 권한을 부여하거나 순서를 조정하면서 동시에 접근하면서 생길 수 있는 문제들을 방지한다.

• 실행의 순서를 동기화(실행 순서 정의)하고 메모리 접근에 대해 동기화(동시 접근을 막고, 한 순간에 하나의 쓰레드/프로세스만 해당 자원에 접근하도록) 한다.

임계 영역 문제

• n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재한다
• 하나의 프로세스가 임계영역에 있을 때는 다른 모든 프로세스는 임계영역에 들어갈 수 없어야 한다

임계 영역 (Critical Section)

• 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역을 임계 영역이라 말한다. 즉, 전역 변수에 둘 이상의 쓰레드가 동시에 접근해서 연산을 실행하는 경우 문제가 발생하고, 이러한 문제를 일으키는 코드 블록을 가리킨다.
• 전역 변수 자체에 할당된 메모리 공간을 가리키는게 아니라 상황에 따라 한 줄일 수도, 여러 줄이 묶여서 임계 영역을 구성하기도 한다.
  임계 영역은 시간이 지나면 종료되고, 어떤 프로세스가 임계 영역에 접근하기 위해서는 지정된 시간만큼 대기해야만 한다.
• 쓰레드나 프로세스가 배타적인(Exclusive) 사용권을 보장받기 위해서 세마포어나 뮤텍스같은 동기화 매커니즘이 사용된다.
• 한 프로세스 내 스레드 사이에서만 동기화가 가능하다.

임계 영역 문제 해결을 위한 3 가지 필수조건

1. Mutual Exclusion (상호 배제)

   • 프로세스 P1 이 임계 영역에서 실행 중이면, 다른 프로세스들은 가진 임계 영역에서 실행될 수 없다.

2. Progress (진행)

   • 임계 영역이 비어있을 때 어떤 프로세스가 들어갈지 적절히 선택하는 것이다.
   • 임계 영역에서 실행중인 프로세스가 없고 별도의 동작이 없는 프로세스들만 임계 영역 진입 후보로서 참여할 수 있다.

3. Bounded Waiting (한정된 대기)

   • P1 이 임계 영역에 진입 신청 후부터 받아들여질 때까지 다른 프로세스들이 임계 영역에 진입하는 횟수는 제한되어야 한다.
   • 기아상태를 방지하기 위해서 한번 들어갔다 나온 프로세스에게 다음에 들어갈 때 제한을 주는 것이다.

상호배제의 방법

1. SW적 해결법

• Peterson's 알고리즘
  
• Dekker's 알고리즘

-> 속도 느림, 구현 복잡, Busy Waiting, Interrupt에 의해 선점당할 수 있음

2. HW적 해결법

• 동기화 지원 HW (Synchronization HW)
  

  • 하드웨어적으로 test&modify를 원자적으로 수행할 수 있도록 지원하는 경우 앞의 문제(spin lock)는 간단히 해결된다
  • test and set으로 한번에 lock의 값을 확인하고 없으면 ciritcal section으로 들어가기 전에 lock의 값을 변환하고 들어간다.

-> 3개 이상의 프로세스가 접근하면 Busy waiting 가능성 높음

3. OS를 이용한 해결

• Spinlock

  • 하나의 프로세스가 Lock을 소유하면 그 Lock이 반환될 때까지 계속 확인하며 기다리는 기법
  • P(S) : key를 갖고 들어감, V(S) : 나오면서 key를 반납함, P V는 OS에서 원자성을 보장
  • 싱글 CPU에서 유용하지 않음 -> 만약 하나의 프로세스가 Lock을 가지고 있고, 그 프로세스가 Lock을 풀어주기 위해서는 필연적으로 Context Switching이 일어아냐 하기 때문임
  • Busy Waiting 문제 존재 -> Loop 을 돌면서 대기하기 때문

• Semaphore
  

  • 바이너리 세마포어(S가 0 or 1)/ 카운팅 세마포어(S가 0 이상 정수)로 나뉨
  • Spinlock과 목적은 동일하지만, Spinlock의 단점을 해결한 기법
  • P(S) : 자원을 획득하는 과정, V(S) : 자원을 반납하는 과정, OS에서 원자성 보장
  • P(S), V(S)는 spinlock과 같은 방식이지만 S 변수 하나마다 ready queue하나가 할당 됨 -> Loop이 아닌 Ready Queue에서 대기하다가 공유자원을 할당받는 형식 -> Busy Waiting 해결
  • 기다리는 프로세스는 block(asleep)상태가 됨 => 대기 큐에서 누군가가 깨워야 하기 때문에 starvation 발생할 수 있음

4. Language level 해결법

• Monitor
  • 항상 하나의 프로세스만 진입할 수 있음
  • 하나의 프로세스 내에서 스레드 간의 동기화에 사용됨
  • 상호 배제를 언어가 보장함
  • 사용하기가 쉬움 (synchronized 사용)