[운영체제] The Producer-Consumer Probelm: 생산자-소비자 문제

The Producer-Consumer Problem

생산자-소비자 문제는 한 스레드가 정보를 생성하는 생산자 역할을 하고, 다른 스레드가 해당 정보를 소비하는 소비자 역할을 하는 상황을 말함,

이 두 스레드는 한정된 크기의 원형 버퍼를 공유함

운영체제는 프로세스와 스레드 간의 메모리 공유를 지원해야 함.

프로세스 간 공유 메모리는 운영체제가 다른 프로세스 간에 데이터를 공유할 수 있는 메커니즘을 제공해야 함을 의미

반면에 스레드는 모든 메모리를 공유하기 때문에 간단하다.

이러한 공유 자원에 대한 접근을 조율하기 위해 운영체제는 동기화 메커니즘을 사용

생산자가 버퍼에 정보를 추가할 때와 소비자가 정보를 꺼낼 때의 상호 배제를 보장하여 충돌이 발생하지 않도록 한다.

이러한 문제를 효율적으로 해결하기 위해서는 운영 체제가 적절한 동기화 기법을 제공해야 함.

• 하나의 프로세스가 정보를 생성하는 생산자인 경우
• 다른 하나의 프로세스가 그 정보를 소비하는 소비자인 경우

⇒ 프로세스들은 한정된(고정크기)원형 버퍼를 통해 통신을 함

 

 

원리

• 생산자는 버퍼에 데이터를 생성, 소비자는 버퍼에서 데이터를 소비
• 생산자는 버퍼가 가득 찰 때까지 데이터를 생성하고 소비자는 버퍼가 비어 있을 때까지 데이터를 소비

⇒ 이는 버퍼가 너무 많은 데이터로 인해 오버플로우되는 것을 방지하고, 소비자가 데이터를 사용할 수 없을 때에는 블록됨으로써 데이터 손실이나 소비자의 오작동을 방지함

 

atomic: 하나의 작업이 끝나기 전까지는 중간에 다른 작업이 끼어들지 않는다는 것을 의미

• 냉장고를 확인하여 우유가 없다고 판단한 후에 장보러 나가는 과정에서 동료가 우유를 사오는 경우가 발생함. 이렇게 되면 냉장고에 우유가 없다는 사실을 확인하고 우유를 사오기까지의 시간 동안 다른 사람이 우유를 사와서 이미 냉장고에 우유가 들어가 있는 상황이 될 수 있다. 따라서 이러한 상황을 방지하기 위해서는 냉장고를 확인하고 우유를 사오는 과정을 하나의 원자적인 작업으로 처리해야 함. 이를 위해 “동기화 기술”이 사용될 수 있다

가정:

• 메모리의 로드(load)와 저장(store) 작업은 원자적(atomic)
• 증가(increment)와 감소(decrement)는 원자적이지 않다.
• i는 공유 변수

질문:

1. 누가 이기나요?reg1 ← 5(i)reg 1→ i=6 (reg1을 i 에 저장)reg2- - ⇒ reg2 = 4문제가 발생
2. reg2 → i=4
3. reg2 ← 5(i)
4. reg1++ ⇒ reg1 = 6이 저장되고, 여기서 context switching
5. 연산을 하다가 context switching이 이루어지면,
6. 두 스레드가 각각 자신의 CPU에서 동시에 정확히 동일한 속도로 실행되고 있다면 어떻게 될까요? 무한정으로 계속될 것이 보장되나요?
   • 전역변수 i라고 한다면, 로드 및 저장을 두 스레드가 공유

---

임계 영역 알고리즘을 처리하는 조건(수업시간)

• progress
• Bounded waiting
• Mutual exlusion ⇒ 약어로 Mutex

1. init
2. (진입 조건) entry
3. c.s(critcal section)
4. Exit
5. remaining code

Synchronization Terminology

1. 동기화 (Synchronization)
   • 스레드 간의 협력을 보장하기 위해 언자적 작업을 사용하는 것을 말함
2. 상호 배제 (Mutual exclusion)
   • 특정한 활동을 한 번에 하나의 스레드만 할 수 있도록 보장하는 것임. 다른 모든 스레드는 그 활용을 할 수 없다
3. 임계 영역 (Critical section)
   • 오직 한 번에 하나의 스레드만 실행할 수 있는 코드 영역을 말함
   • 예를 들어 공유 데이터를 수정하는 코드와 같은 것이 임계영역임
4. 락(Lock)
   • 다른 스레드가 어떤 작업을 수행하는 것이 막는 매커니즘
     • 임계 영역에 진입하기 전에 락을 획득
     • 임계 영역을 빠져나올 때 락을 해제
     • 락이 잠겨있는 임계 영역에 진입하려는 스레드는 락이 해제될 때까지 기다려야

---

Enforcing Mutual Exclusion

상호 배제를 강제하는 법

1. 사용자에게 맡기기
   • 스레드가 서로 명시적으로 협력해야 함. 즉 스레드들이 서로 통신하여 상호 배제를 구현해야 함
2. 운영 체제에게 맡기기
   • 운영 체제가 상호 배제를 지원하는 기능을 제공, 운영 체제가 락과 같은 동기화 메커니즘을 제공하여 스레드 간의 상호 배제를 달성함
3. 하드웨어에게 맡기기
   • 하드웨어가 상호 배제를 위한 아키텍처적인 지원을 제공. 즉 하드웨어 수준에서 락과 같은 메커니즘을 제공하여 스레드 간의 상호 배제를 달성

 

해결방법은 다음과 같은 조건을 충족

Starvation(굶주림)을 피하기

• 스레드가 임계 영역에 액세스하려고 시도할 때 결국 성공해야 함

Deadlock(교착 상태)를 피하기

• 일부 스레드가 임계 영역에 들어가려고 시도할 때 결국 하나의 스레드는 반드시 성공해야 함

⇒ 이 방법은 스레드가 비임계 영역에서는 중단 될 수 있지만, 임계 영역에서 중단되지 않는다고 가정

 

 

Algorithm 1 - 상호 배제를 위한 방법 제안

이글루(igloo)와 그 안의 칠판(blackboard)을 사용하여 상호 배제를 구현

• 이글루와 칠판
  • 이글루는 오직 한 명의 사람(스레드)만이 동시에 들어갈 수 있는 작은 공간이고, 그 안에는 하나의 값을 담을 수 있는 칠판이 있다.
• 임계 영역 진입
  • 스레드가 임계 영역에 들어가려고 할때, 먼저 이글루에 들어가서 칠판을 확인함
  • 만약 칠판에 자신의 번호가 없다면 이글루를 나가서 바깥에서 이글루 주변을 뛰며 기다린다.
    • 잠수 후 다시 이글루로 들어가서 칠판을 다시 확인
    • 이러한 “바쁜 대기(busy waiting)”는 자신의 번호가 칠판에 올라갈 때까지 계속됨
  • 만약 칠판에 자신에 번호가 있다면, 이글루를 나가서 임계 영역으로 진입
• 임계 영역 탈출
  • 임계 영역에 나온 후, 스레드는 다시 이글루에 들어가서 다른 스레드의 번호를 칠판에 적는다.

Algorithm 2

상호 배타적인 임계 영역을 동시에 사용하는 스레드 간의 동기화를 위한 알고리즘

• 각 스레드는 자신만의 이글루가 있다
• 스레드는 자신의 블랙보드(상태를 나타내는 것)를 검사하고 수정이 가능하고, 다른 스레드의 블랙보드를 검사할 수 있지만 수정은 불가능하다.
• 블랙보드에 true라고 적혀있다면 해당 스레드가 임계영역에 들어간 상태
• 임계 영역을 실행하고자 하는 스레드는 다른 스레드의 이글루에 들어가서 해당 스레드의 블랙보드를 검사한다.
  • 스레드에 false라고 쓰여있다면 해당 스레드는 다시 자신의 이글루에 돌아가서 블랙보드에 true를 쓰고 임계 영역에 들어감
  • 스레드에 true라고 쓰여있다면 해당 스레드는 이글루에서 wait 상태로 있음. (busy waiting랑 다른 개념 이은 계속해서 조건을 확인하면서 루프를 돌며 대기하는 것인데, 이는 CPU 리소스를 낭비하여 효율적이지 않음)
• 임계 영역을 실행한 후, 해당 스레드는 다시 이글루에 들어가서 자신의 블랙보드에 false를 쓰고 임계영역을 나옴