[운영체제] 5. Process Synchronization (4) - semaphore를 통한 동시성 문제 해결 방법, monitor

키워드

semaphore, synchronization, bounded-buffer problem, producer-consumer problem,
readers and writers problem, dining-philosophers problem, monitor

 

Classical Problems of Synchronization

• Bounded-Buffer Problem(Producer-Consumer Problem)
• Readers and Writers Problem
• Dining-Philosophers Problem

 

Bounded-Buffer Problem

(=Producer-Consumer Problem)

• Buffer: 임시로 데이터를 저장하는 공간
• Buffer의 크기가 유한한 환경에서의 생산자-소비자 문제
• 두가지 프로세스 종류
  • Producer: 생산자 프로세스
    -> 공유 buffer에 데이터를 만들어 집어넣는 역할(그림상에서 주황색으로 producer가 데이터를 집어넣음)
  • Consumer: 소비자 프로세스
  • 하나씩만 있는게 아닌 여러 개 존재

 

공유 데이터 관련 synchronization 문제

• 생산자가 둘이 동시에 도착해서 비어있는 buffer에 동시에 데이터를 만들어 집어넣을 경우 문제 발생
  -> 공유 buffer에 lock을 걸어 다른 프로세스들의 접근을 막은 후 작업 진행
• 소비자도 마찬가지

 

buffer가 유한하기 때문에 생기는 문제

• Producer
  • buffer가 다 찬 상태에서 producer가 계속 도착해 데이터를 생성하려 하면
    producer 입장에선 사용할 수 있는 자원이 없는 상황 발생
    -> consumer가 꺼내가야 생성 가능하기 때문에 기다리게 됨
  • 비어있는 buffer의 개수가 producer의 자원
• Consumer
  
  • 내용이 들어있는 buffer의 개수가 consumer의 자원
  • producer와 반대로 꺼내갈 자원이 하나도 없을 경우
    생산자 프로세스(producer)가 데이터를 만들어 집어넣어 줄 때까지 기다리게 됨

 

Semaphore를 이용해 해야할 업무 두가지

• lock/unlock 용도
  • 둘이 동시에 공유 buffer에 접근하는 것을 막기 위해 공유 buffer 전체에 lock을 걸고, 
    본인 혼자 베타적으로 접근하게 하고 접근이 끝날 경우 lock을 푸는 문제를 위해 필요
• 자원의 개수를 세는 용도
  • buffer가 가득 차거나 또는 비었을 때, producer 혹은 consumer에게 있어
    가용자원을 세는 counting semaphore 변수 필요
  • producer 입장에서는 비어있는 buffer의 개수가 자원
  • consumer 입장에서는 내용이 들어있는 buffer의 개수가 자원

 

Pseudocode(수도코드)

semaphore 변수

• full: 내용이 들어있는 buffer의 개수를 세기 위한 변수
• empty: 비어있는 buffer를 세기 위한 변수. 처음엔 모두 비어있을테니 default=n
• mutex: lock을 걸기 위한 변수

 

Readers and Writers Problem

• 읽는 프로세스, 쓰는 프로세스 두 종류가 존재
• 공유 데이터를 DB라 명명
• write(내용을 쓰는 작업)는 동시에 여럿이 하면 안되지만
  read(읽는 작업)는 동시에 여럿이 해도 synchronization 관련 아무 문제도 발생하지 않음
• 때문에 P연산, V연산을 매번 걸면서 작업해도 무방하지만
  read에 대해서 lock을 거는 행위가 비효율적이게 됨
• 따라서, write 하는 동안엔 lock을 걸어 아무도 DB에 접근하지 못하게 하지만
  read중일 경우엔 같이 읽을 수 있게 해주는게 Readers and Writers Problem에서 풀어야 할 과제가 된다.

 

Pseudocode(수도코드)

DB: 공유 데이터, db: lock에 해당하는 semaphore 변수

• reader의 경우 위에서 말한 내용 때문에 lock을 아예 안걸어도 되는줄 알았겠지만
  writer가 lock이 안걸려있으니 와서 lock을 걸고 써버리는 가능성이 있기 때문에
  lock을 걸긴 해야함
• readcount 변수(공유 변수 중 하나)를 둬서 lock을 관리
• 최초의 reader일 경우(아무도 읽고 있지 않았던 경우) DB에 lock을 걺
• 최초의 reader가 아니라면(누군가 DB에서 읽고 있는 상황일 경우)
  이미 lock이 걸려있기 때문에 DB를 읽기만하면 됨
• 하지만 readcount도 공유 변수기 때문에 그냥 증가시킬 경우 문제가 발생할 수 있음
  여러 reader가 동시에 와서 증가시킬 경우 제대로 증가가 안될 수 있기 때문
• 그래서 readcount를 바꾸기 위해서도 공유 변수에 대해서도 lock을 걸 필요가 있음
  -> readcount라는 공유 변수를 위한 lock이 mutex라는 semaphore 변수이다.
  -> 그림상의 P(mutex), V(mutex)
• 마지막에 읽는 프로세스라면 lock을 풀어줘야함
  
  
• Shared data(공유 데이터)
  • DB 자체
  • readcount: 현재 DB에 접근 중인 Reader의 수
• Synchronization variables(공유 변수)
  • mutex: readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용
  • db: reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
    
    
• Starvation 문제가 발생할 수 있다.
• reader가 도착하고 writer가 도착했을 때, writer는 기다리겠지만
  reader는 동시에 읽기가 가능하기 때문에 새롭게 도착하는 reader들이 추가로 읽기 시작하고 
  그만큼 writer는 더 기다리게 될 것이다. 
  만약, 이게 반복된다면 writer는 영원히 기다려야 하는 문제가 발생한다.
• 그렇다고 writer를 먼저 접근하게 하기엔 여러 개의 reader가 기다리는 상황이 발생하여 비효율적이게 될 가능성 존재
• 그럼 어떻게 함?
  -> 이전에 배웠던 큐에 우선순위를 두는 방법 등을 통해 해결할 수 있겠다.
• ex) 신호등을 생각.
  신호가 없을 경우 차가 계속 지나가서 영원히 건너갈 수 없는 상황이 생기지만
  신호가 있다면 언젠가 내 차례가 올 수 있음
  
  

Dining-Philosophers Problem

(=식사하는 철학자 문제)

식사하는 철학자 문제를 semaphore를 이용해 간단히 코딩한 모습

• 철학자들은 생각하는 일, 밥 먹는 일 두가지를 원탁에 앉아 진행
• 간단하게 생각=쉼, 밥=양 쪽의 젓가락을 잡고 식사라고 생각하면 됨
• 철학자들은 생각하거나 밥을 먹는 일을 무한 반복

 

위 solution의 문제점

• Deadlock의 가능성 존재
  
  • 모든 철학자가 동시에 왼쪽 젓가락을 잡을 경우
• 해결방안
  • 철학자가 밥을 먹을 때만 테이블에 앉게 하기
  • 4명의 철학자만 테이블에 동시에 앉을 수 있게 하기
  • 젓가락을 양쪽 모두 잡을 수 있을 때만 젓가락을 잡을 수 있게 하기(-> 아래 코드 참고)
  • 비대칭 - 짝수 철학자는 왼쪽 젓가락부터, 홀수 철학자는 오른쪽 젓가락부터 잡게 하기

 

Pseudocode(수도코드)

enum {thinking, hungry, eating} state[5];  // 다섯명의 상태(생각중, 배고픔, 먹는중)
semaphore self[5]=0;  // 젓가락을 잡을 수 있는 상태(0:가능, 1:불가능)
semaphore mutex=1;  // 철학자의 상태가 공유 변수라 다른 철학자가 바꿀 수 있기 때문에 lock을 나타내는 변수

void test(int i) {
  if (
    state[(i+4)%5] != eating     // 내 왼쪽이 식사중이 아닐 경우
    && state[i] == hungry        // 내가 배고플 경우
    && state[(i+1)%5] != eating  // 내 오른쪽이 식사중이 아닐 경우
  ) {
    state[i] = eating;
    V(self[i]);  // 위 조건을 만족할 때 나한테 젓가락을 잡을 수 있는 권한을 줌, 0 -> 1
  }
}

• 헷갈릴 수 있는 부분
  • semaphore는 원래 자원의 개수를 세기 때문에 초기 값을 두는데
    위의 코드에선 젓가락을 얻을 수 있는 권한의 목적으로 사용되어 semaphore의 철학에 맞지 않는 코드가 되는 부분이 있음
  • -> 추후 나올 monitor 코드를 보면 왜 이렇게 코딩했는지 알 수 있음!

 

Monitor

Semaphore의 문제점

• 프로그래머한테 P 연산, V 연산을 통해 코딩을 비교적 쉽게 만들긴 했지만 
  그럼에도 불구하고 문제가 생겼을 때 버그를 잡기가 쉽지 않음
  한 번의 실수가 모든 시스템에 치명적인 영향을 미칠 수 있다.
  • V 연산 -> P 연산: Mutual exclusion 깨짐
  • P 연산 -> P 연산: Deadlock
• 때문에 Monitor라는 것을 synchronization에서 제공

 

Monitor란?

• 프로그래밍 언어 차원에서 synchronization을 해결하는.
  즉, 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 
  high-level synchronization construct
• 어떤 공유 데이터에 접근하기 위해서는
  monitor라고 정의된 내부의 프로시저를 통해서만 공유 데이터만 접근할 수 있게 만들어놓음

• monitor는 원천적으로 monitor 내부의 프로시저가 동시에 여러 개가 실행되지 않게 통제 권한을 줌
  쉽게 말하면 monitor에 대한 동시 접근을 허락하지 않는다.
  -> 프로그래머는 lock을 걸 필요가 없어짐(semaphore와의 가장 큰 차이)
• 하나의 프로세스만 모니터를 접근 가능(나머지 프로세스는 줄서서 대기)
  
  
• semaphore에서 자원의 개수를 세는 semaphore 변수 같은 용도의
  condition variable 사용. ex) condition x, y;
• condition variable은 wait과 signal 연산에 의해서만 접근 가능

monitor로 구현한 Bounded-Buffer Problem의 모습

• 공유 buffer가 내부에 정의되어 있다.
• produce(생산), consume(소비) 코드를 실행하려면 내부 코드를 실행해야 하고
  이로인해 둘 중 하나의 프로세스만 모니터 안에서 활성화 되기 때문에 굳이 lock을 걸지 않아도 
  synchronizatioin 문제를 고려할 필요가 없어진다.