동시성(Semaphore, Monitor, 전통적인 문제 3가지)

클린코드 책을 읽다가 동시성 전통적인 문제 3가지에 대한 내용이 나와서 다시 정리하게 되었다. 반효경 교수님의 운영체제 강의 내용을 바탕으로 간략하게 다시 정리해본다.

동시성 해결 방식

• 1 → 2 → 3 으로 갈수록 추상화된 방식으로 프로그래머가 사용하기 편함

1. Test & Set

• 공유데이터에 접근 및 변경을 하드웨어적으로 atomic(원자적) 하게 실행하개 해줌

2. Semaphore

• TestAndSet을 추상화한 방식
• 추상자료형 (내부 구현은 신경쓰지 않고, object, operation 으로 사용)
• object: 정수(자원의 갯수), S
• operation: P(자원획득과정), V(자원반납과정)
• 예시: P(5) → 자원의 갯수: 5, 자원 획득과정
• P연산 V연산 사이에 자원을 사용하는 코드가 들어감
• mutual semaphore(mutex)은 기본적으로 S=1 으로 설정되어 lock, unlock을 관리
• count semaphore(자원 갯수 관리), binary semaphore(lock, unlock 관리)
• 구현방식: Busy-waiting, Block-Wakeup
• Busy-waiting
  • S의 의미: 여분 자원의 갯수
  • Spin lock (자원을 차지하나 실제 사용하지는 못하는 현상 발생 가능성 있음)
• Block-Wakeup
  • S의 의미: 음수의 경우, 누군가 자원을 사용하기 위해 대기 & 양수의 경우, 자원이 남는 상태
  • 클래스 타입같은 구조형 타입을 사용하며, 리스트 구조를 사용하여 관리
  • 자원이 없을 경우, 대기열에 넣어두고 block 시켜 놓음(자원이 없을 경우 block 상태로 만들어 놓고, 대기시킴)
  • block, wakeup 하는 오버헤드가 있으나 일반적으로 block-wakeup 방식 구현이 더 좋은 편

P(S): S.value --; 
    if(S.value < 0) 
        block(); 

V(S): S.value ++; 
    if(S.value <= 0) 
        wakeup();

3. Monitor

• semaphore 는 순서 실수(P,V 연산) 등 코딩의 문제점이 있을 수 있음
• semaphore 에서는 동기화 문제는 프로그래머의 책임이라면 monitor에서는 monitor 가 책임짐
• 고급언어에서 제공하는 추상화 된 방식
• 공유데이터를 중심으로 procedure로 관리
• 모니터가 공유데이터 접근을 책임짐
• condition variable이 queue의 역할을 하며, wait(), signal() 연산으로만 접근함
• condition 이 자원의 갯수 등을 세지 않으며, Monitor가 관리함 (full, empty)

전통적인 동시성(동기화) 문제들

1. Producer-Consumer Problem (Bounded-Buffer)

• 한정된 공유 자원에서 여러 producers, consumers가 접근할 경우 문제가 될 수 있음 (공유 자원을 동시에 접근해서 변경하거나 읽을 경우)
• 공유 데이터 : Buffer 자체, 자원의 위치 pointer

해결방안

1. lock, unlock 을 사용
   • unlock 할 때, 다음 가능한 자원 위치로 변경 후 unlock하여 자원이 겹치지 않게 함
2. 자원이 모두 사용중이라 사용이 어려울 때, semaphore 사용
   • counting semaphore 사용하여, 사용할 수 있는 자원의 갯수를 관리
   • binary semaphore 를 사용하여 lock, unlock 관리

2. Readers-Writers Problem

• Read의 경우에는 동시접근이 가능해야하나, Write의 경우에는 동시접근이 불가해야함
• DB에서 보통 일어나는 문제

해결방안

• readCount 를 사용하여 reader의 갯수를 관리 → readCount 자체도 공유자원이므로 readCount에 대한 lock 관리를 mutex로 함
• db: DB 접근을 위한 lock
  • reader의 접근은 가능(shared lock) - reader의 경우 P(db)가 있다면 공유하여 사용가능
  • writer의 접근은 배타적으로 진행

// READER
P(mutex);
    readCount++;
    if(readCount == 1) // reader 최초 1명의 경우에만 P(db). 그 이후 공유
        P(db);
V(mutex);

... DB 리딩 ...

P(mutex);
    readCount--;
    if(readCount == 0)
        V(db);
V(mutex);

• reader 가 있다면 writer가 계속 접근하지 못하는 starvation 문제가 발생할 수 있다. → 일정 시간에 도착한 reader까지만 접근 가능하게 시간 제한을 두어 해결할 수 있음

3. Dining-Philosophers Problem (식사하는 철학자들)

• 자원 2개(오른쪽 젓가락, 왼쪽 젓가락)를 모두 얻어야 사용가능할 경우, 모두 1개의 자원만(오른쪽 젓가락만) 얻은채 계속 기다리는 deadlock 문제 발생가능

해결방안

1. 5명의 자리가 있다면 4명만 테이블에 앉을 수 있게 함
2. ✨ 모두 자원을 잡을 수 있는 경우에만 권한을 준다
3. 비대칭으로 (홀수는 왼쪽먼저, 짝수는 오른쪽 먼저) 자원을 획득해서 자원 획득의 순서를 맞춘다.

참고

• synchronization - 1
• synchronization - 2