Operating System.10 Synchronization 2

Condition Synchronization(조건 동기화)

• 조건 동기화(Condition Synchronization)는 병행 프로그래밍에서 여러 스레드 또는 프로세스 간의 실행 순서를 조정하고 조율하는 메커니즘이다.

• 이는 특정 조건이 만족될 때까지 스레드나 프로세스의 실행을 블록하고, 조건이 충족되면 실행을 재개하는 방식으로 동작한다.

• 조건 변수(Condition Variable):

  • 조건 동기화를 위해 사용되는 핵심적인 데이터 구조(waiting queue)이다.
  • 스레드나 프로세스가 특정 조건을 기다리거나 조건의 변화를 알리는 데 사용된다.
  • 조건 변수는 보통 뮤텍스(Mutex)와 함께 사용되어 조건의 평가와 스레드의 블록/언블록을 안전하게 관리한다.

• Wait 연산:

  • 스레드나 프로세스가 특정 조건을 기다리는 연산이다.
  • 조건이 만족되지 않으면 해당 스레드는 블록(Block) 상태로 전환되어 실행이 중단된다.
  • 이때 뮤텍스를 해제하여 다른 스레드가 조건을 변경할 수 있도록 한다.

• Signal 연산:

  • 조건이 충족되었음을 알리는 연산이다.
  • 조건을 만족시키는 스레드가 Signal 연산을 호출하면, 해당 조건을 기다리는 스레드 중 하나가 블록 상태에서 해제되어 실행을 재개한다.
  • 여러 개의 스레드가 기다리고 있다면, 시스템에 따라 무작위로 또는 우선순위에 따라 하나의 스레드가 선택된다.

• Broadcast 연산:

  • Signal 연산과 유사하지만, 조건을 기다리는 모든 스레드를 블록 상태에서 해제하는 연산이다.
  • 조건을 만족시키는 스레드가 Broadcast 연산을 호출하면, 해당 조건을 기다리는 모든 스레드가 실행을 재개한다.

상태 변수(State Variable)

• 조건 동기화에서 공유 자원의 상태를 나타내는 변수이다.
• 상태 변수는 스레드 간에 공유되며, 스레드들은 이 변수의 값을 기반으로 조건을 평가하고 실행을 조정한다.

1. 상태 변수의 정의:

   • 상태 변수는 공유 자원의 현재 상태를 표현하는 데 사용되는 변수이다.
   • 상태 변수의 값은 공유 자원의 가용성, 점유 여부, 데이터의 존재 여부 등을 나타낸다.
   • 스레드들은 상태 변수의 값을 검사하여 특정 조건을 판단하고 실행을 결정한다.

2. 상태 변수의 예시:

   • 버퍼의 현재 크기를 나타내는 변수
   • 공유 자원의 사용 가능 여부를 나타내는 boolean 변수
   • 데이터의 존재 여부를 나타내는 변수
   • 스레드의 실행 단계를 나타내는 변수

3. 상태 변수와 조건 변수의 관계:

   • 상태 변수는 조건 변수와 함께 사용되어 조건 동기화를 구현한다.
   • 스레드는 조건 변수를 사용하여 상태 변수의 값을 기반으로 대기하거나 실행을 재개한다.
   • 상태 변수의 값이 변경되면 조건 변수를 통해 대기 중인 스레드에게 신호를 보낸다.

4. 상태 변수의 접근과 갱신:

   • 상태 변수는 임계 영역(Critical Section)에서 접근되고 갱신된다.
   • 스레드는 상호 배제(Mutual Exclusion) 메커니즘을 사용하여 상태 변수에 대한 배타적 접근을 보장한다.
   • 상태 변수의 값을 변경할 때는 원자적(Atomic)으로 이루어져야 한다.

5. 상태 변수의 초기화:

   • 상태 변수는 공유 자원의 초기 상태를 나타내도록 초기화된다.
   • 초기값은 공유 자원의 가용성, 데이터의 존재 여부 등을 반영한다.

6. 상태 변수의 사용 예시:

   • 생산자-소비자 문제에서 버퍼의 현재 크기를 나타내는 변수
   • 읽기-쓰기 락(Lock)에서 공유 자원의 사용 가능 여부를 나타내는 변수
   • 세마포어(Semaphore)에서 자원의 가용성을 나타내는 변수

• 상태 변수는 조건 동기화에서 핵심적인 역할을 한다.
• 스레드들은 상태 변수의 값을 기반으로 조건을 평가하고 실행을 조정하여 공유 자원에 대한 안전한 접근과 동기화를 보장한다.

• 상태 변수는 조건 변수와 함께 사용되어 스레드 간의 통신과 협력을 가능하게 한다.

• 상태 변수를 올바르게 정의하고 관리하는 것은 병행 프로그래밍에서 중요하다.
• 상태 변수의 초기화, 접근, 갱신은 임계 영역 내에서 이루어져야 하며, 스레드 간의 동기화와 상호 배제를 적절히 처리해야 한다.
• 상태 변수를 효과적으로 활용함으로써 병행 시스템의 정확성과 효율성을 높일 수 있다.

Simple join() 함수 구현 예시

• State variable : done
• Lock for the state variable : m
  • mutex를 활용하여 상호배제를 하지 않을 경우 아래와 같은 잘못된 시나리오가 발생한다.
  • State Variable이 없을 경우 아래와 같은 잘못된 시나리오가 발생한다.

Producer/Consumer Problem

• 생산자-소비자 문제(Producer-Consumer Problem)는 병행 프로그래밍에서 자주 등장하는 고전적인 동기화 문제 중 하나이다.
• 이 문제는 두 가지 유형의 프로세스 또는 스레드, 즉 생산자(Producer)와 소비자(Consumer)가 공유 버퍼를 사용하여 데이터를 주고받는 상황을 다룬다.

1. 문제 정의:

   • 생산자(Producer)는 데이터를 생성하여 공유 버퍼에 저장하는 역할을 한다.
   • 소비자(Consumer)는 공유 버퍼에서 데이터를 읽어와 소비하는 역할을 한다.
   • 공유 버퍼는 한정된 크기를 가지며, 버퍼가 가득 차면 생산자는 대기해야 하고, 버퍼가 비어있으면 소비자는 대기해야 한다.
   • 생산자와 소비자는 동시에 공유 버퍼에 접근할 수 있어 동기화 문제가 발생할 수 있다.

2. 문제의 조건:

   • 생산자는 공유 버퍼에 데이터를 추가할 수 있어야 한다.
   • 소비자는 공유 버퍼에서 데이터를 읽어올 수 있어야 한다.
   • 공유 버퍼의 크기는 제한되어 있다.
   • 생산자는 버퍼가 가득 찼을 때 대기해야 하고, 소비자는 버퍼가 비어있을 때 대기해야 한다.
   • 데이터의 무결성을 보장하기 위해 생산자와 소비자의 동시 접근을 제어해야 한다.

3. 동기화 메커니즘:

   • 뮤텍스(Mutex): 공유 버퍼에 대한 상호 배제를 보장하기 위해 사용된다.
   • 세마포어(Semaphore): 버퍼의 가용 공간과 채워진 공간을 추적하고 동기화하기 위해 사용된다.
   • 조건 변수(Condition Variable): 생산자와 소비자 간의 통신과 조건 동기화를 위해 사용된다.

4. 해결 방법:

   • 생산자:
     • 버퍼에 데이터를 추가하기 전에 버퍼가 가득 찼는지 확인한다.
     • 버퍼가 가득 찼으면 소비자가 데이터를 소비할 때까지 대기한다.
     • 버퍼에 여유 공간이 있으면 데이터를 추가하고, 대기 중인 소비자에게 신호를 보낸다.
   • 소비자:
     • 버퍼에서 데이터를 읽어오기 전에 버퍼가 비어있는지 확인한다.
     • 버퍼가 비어있으면 생산자가 데이터를 생성할 때까지 대기한다.
     • 버퍼에 데이터가 있으면 데이터를 읽어오고, 대기 중인 생산자에게 신호를 보낸다.

5. 동기화 과정:

   • 생산자와 소비자는 공유 버퍼에 접근할 때 뮤텍스를 사용하여 상호 배제를 보장한다.
   • 생산자는 버퍼에 데이터를 추가할 때 “채워진 공간” 세마포어를 증가시키고, 소비자는 데이터를 읽어올 때 “채워진 공간” 세마포어를 감소시킨다.
   • 생산자는 버퍼가 가득 찼을 때 “가용 공간” 세마포어를 사용하여 대기하고, 소비자는 버퍼가 비어있을 때 “채워진 공간” 세마포어를 사용하여 대기한다.
   • 조건 변수를 사용하여 생산자와 소비자 간의 통신과 조건 동기화를 처리한다.

• 생산자-소비자 문제는 실제 시스템에서 다양한 형태로 응용될 수 있다.
• 예를 들어, 네트워크 패킷 처리, 작업 스케줄링, 데이터베이스 처리 등에서 생산자-소비자 모델을 활용하여 병행성을 향상시키고 시스템의 성능을 개선할 수 있다.

생산자-소비자 문제 sample

• buffer의 크기가 무한한 경우

  • producer의 제약이 사라진다.

• 2 Consumer, 1 Producer의 경우 발생하는 문제 (CASE 1)

  • 위의 경우에 아래와 같은 실행 흐름을 가질 경우 TC1가 잠들었다 TP1의 signal에 의해 다시 깨어났을 때 이미 TC2가 리소스를 사용해버린 뒤라는 문제가 발생한다.
• 2 Consumer, 1 Producer의 경우 발생하는 문제 (CASE 2)
  • 이전의 CASE1에서 if문으로 체크해줬던 조건을 반복문으로 변경하여 개선하였다.
  • 하지만 해당 경우에도 아래의 흐름과 같이 같은 조건 변수(Condition Variable)를 사용하여 Consumer가 Producer가 아닌 또다른 Consumer를 깨워줄 경우, 3개의 thread가 모두 sleep 상태에 빠지는 경우가 발생할 수 있다.
• Solution
  • Consumer는 오직 Producer만 깨우고, Producer는 오직 Consumer만 깨우도록 변경

Semaphore를 통한 Producer/Consumer problem Solution

• 위에서 봤던 pthread 함수로 이뤄진 솔루션을 semaphore로 변경할 경우 아래와 같은 코드로 변환된다.
  • 하지만 이 경우 pthread_cond_wait함수의 auto-release 기능을 semaphore에서 가지고 있지 않기 때문에 위의 코드는 m구역에 lock을 걸고 비워지기를 기다리게 되는 것이므로 deadlock이 발생할 수 밖에 없게 된다.
  • 그러므로 아래와 같이 m구역에 대한 lock과 ‘버퍼가 비워지거나 채워지는 조건’의 lock의 순서를 변경해줘야 한다.

Disadvantage of Semaphore

• 세마포어(Semaphore)는 병행 프로그래밍에서 유용한 도구이지만, 몇 가지 단점과 주의해야 할 점이 있다.

1. 복잡성 증가:

   • 세마포어를 사용하면 프로그램의 복잡성이 증가할 수 있다.
   • 세마포어의 초기값 설정, 획득(wait) 및 해제(signal) 연산의 위치와 순서를 신중히 고려해야 한다.
   • 세마포어를 잘못 사용하면 교착 상태(Deadlock), 경쟁 조건(Race Condition) 등의 문제가 발생할 수 있다.

2. 자원 낭비 가능성:

   • 세마포어를 사용할 때 스레드가 자원을 기다리는 동안 블록(Block)될 수 있다.
   • 블록된 스레드는 CPU 시간을 소비하지 않지만, 스레드가 블록되는 동안 다른 작업을 수행할 수 없다.
   • 많은 수의 스레드가 세마포어를 기다리는 경우 자원 낭비가 발생할 수 있다.

3. 우선순위 역전 문제:

   • 세마포어는 기본적으로 스레드의 우선순위를 고려하지 않는다.
   • 우선순위가 낮은 스레드가 세마포어를 획득하고 있으면, 우선순위가 높은 스레드가 대기하게 되는 우선순위 역전 문제가 발생할 수 있다.
   • 이로 인해 시스템의 실시간성이나 응답성이 저하될 수 있다.

4. 불필요한 블로킹:

   • 세마포어는 스레드 간의 동기화를 위해 사용되지만, 때로는 불필요한 블로킹을 유발할 수 있다.
   • 예를 들어, 스레드가 이미 사용 가능한 자원을 기다리는 경우에도 세마포어로 인해 블록될 수 있다.
   • 이는 성능 저하와 자원 활용의 비효율성을 초래할 수 있다.

5. 데드락(Deadlock) 가능성:

   • 세마포어를 사용할 때 데드락에 빠질 가능성이 있다.
   • 둘 이상의 스레드가 서로 다른 세마포어를 기다리는 상황에서 순환 대기(Circular Wait) 조건이 발생하면 데드락이 발생할 수 있다.
   • 데드락은 시스템의 응답이 멈추고 자원이 낭비되는 심각한 문제를 야기할 수 있다.

6. 스레드 간의 통신 제한:

   • 세마포어는 스레드 간의 동기화를 제공하지만, 스레드 간의 직접적인 통신 수단은 제공하지 않는다.
   • 스레드 간에 데이터를 교환하거나 상태를 공유하기 위해서는 별도의 메커니즘(예: 공유 메모리, 메시지 패싱 등)을 사용해야 한다.

7. 세마포어의 오용:

   • 세마포어를 부적절하게 사용하면 프로그램의 정확성과 안정성에 문제가 발생할 수 있다.
   • 예를 들어, 세마포어의 초기값을 잘못 설정하거나, 획득과 해제 연산의 균형이 맞지 않으면 예기치 않은 동작이 발생할 수 있다.

• 세마포어는 병행 프로그래밍에서 유용한 도구이지만, 사용할 때는 주의가 필요하다.

Reader-Writer Problem

• 병행 프로그래밍에서 공유 자원에 대한 읽기와 쓰기 연산을 수행하는 스레드 간의 동기화를 다루는 고전적인 문제이다.
• 이 문제에서는 여러 개의 Reader 스레드와 하나 이상의 Writer 스레드가 공유 자원에 동시에 접근할 때 발생하는 동기화 이슈를 해결하는 것이 목표이다.

1. 문제 정의:

   • 공유 자원에는 여러 개의 Reader 스레드와 하나 이상의 Writer 스레드가 접근할 수 있다.
   • Reader 스레드는 공유 자원을 읽기만 하고 수정하지 않는다.
   • Writer 스레드는 공유 자원을 읽고 수정할 수 있다.
   • 여러 개의 Reader 스레드는 동시에 공유 자원을 읽을 수 있다.
   • Writer 스레드가 공유 자원을 수정하는 동안에는 다른 스레드(Reader 또는 Writer)가 접근할 수 없어야 한다.

2. 문제의 조건:

   • Reader 스레드는 공유 자원을 동시에 읽을 수 있어야 한다.
   • Writer 스레드는 공유 자원을 배타적으로 접근해야 한다.
   • Reader 스레드와 Writer 스레드 간의 상호 배제가 보장되어야 한다.
   • 스레드 간의 공평성이 보장되어야 한다.(특정 스레드가 계속 대기하는 상황(Starvation)이 발생하지 않아야 함)

3. 해결 방법 - Reader 우선 방식:

   • Reader 스레드는 공유 자원에 자유롭게 접근할 수 있다.
   • Writer 스레드는 모든 Reader 스레드가 공유 자원에서 벗어날 때까지 대기해야 한다.
   • 새로운 Reader 스레드는 Writer 스레드가 대기 중이더라도 바로 공유 자원에 접근할 수 있다.
   • 이 방식은 Reader 스레드에 높은 우선순위를 부여하며, Writer 스레드는 Reader 스레드가 없을 때까지 대기해야 한다.

4. 해결 방법 - Writer 우선 방식:

   • Writer 스레드가 공유 자원에 접근하려고 하면, 새로운 Reader 스레드는 대기해야 한다.
   • 현재 공유 자원을 읽고 있는 Reader 스레드는 계속 읽을 수 있지만, 새로운 Reader 스레드는 Writer 스레드가 완료될 때까지 대기한다.
   • Writer 스레드는 대기 중인 다른 Writer 스레드보다 우선순위가 높다.
   • 이 방식은 Writer 스레드에 높은 우선순위를 부여하며, Reader 스레드는 Writer 스레드가 없을 때만 공유 자원에 접근할 수 있다.

5. 동기화 메커니즘:

   • 세마포어(Semaphore)나 뮤텍스(Mutex)를 사용하여 Reader 스레드와 Writer 스레드 간의 동기화를 구현할 수 있다.
   • 공유 자원에 대한 접근을 제어하기 위해 읽기 세마포어와 쓰기 세마포어를 사용할 수 있다.
   • 읽기 세마포어는 여러 개의 Reader 스레드가 동시에 접근할 수 있도록 허용하고, 쓰기 세마포어는 Writer 스레드의 배타적인 접근을 보장한다.

6. 고려 사항:

   • Reader 우선 방식에서는 Writer 스레드가 기아 상태(Starvation)에 빠질 수 있습니다. 지속적으로 Reader 스레드가 도착하면 Writer 스레드는 무한정 대기할 수 있다.
   • Writer 우선 방식에서는 Reader 스레드가 기아 상태에 빠질 수 있습니다. Writer 스레드가 계속해서 도착하면 Reader 스레드는 무한정 대기할 수 있다.
   • 공평성을 보장하기 위해 Reader 스레드와 Writer 스레드에 균등한 기회를 제공하는 방식으로 구현할 수도 있다.

• Reader 스레드와 Writer 스레드의 우선순위와 공평성을 고려해야 합니다. 또한, 스레드 간의 상호 배제와 기아 상태 방지를 위한 적절한 전략이 필요하다.