기본 개념 정리

• 상호 배제 (Mutual Exclusion): 공유 자원에 접근할 수 있는 스레드는 단 하나뿐이다. 임계 영역은 동시에 여러 스레드가 접근하지 못하도록 보장한다.
• 동기화 (Synchronization): 두 개 이상의 프로세스나 스레드 간의 실행 순서를 조절하는 메커니즘. 한 작업이 다른 작업의 완료를 기다려야 할 때 사용된다.
• 비동기 처리 (Asynchronous Execution): 특정 이벤트 발생을 기다리는 동안 다른 작업을 수행하며, 블로킹 없이 진행 가능하다. 주로 스레드 또는 콜백 기반으로 구현된다.
• 병행성 (Concurrency): 여러 작업이 서로 번갈아가며 실행되는 상태. 시간 점에서 하나의 작업만 실행되지만, 시간 간격 내에서는 여러 작업이 수행된다.
• 병렬성 (Parallelism): 다중 코어 시스템에서 동시에 여러 작업이 실행되는 현상. 실제 동시에 여러 작업이 처리된다.

생산자-소비자 문제

공유 버퍼를 통해 데이터를 주고받는 두 종류의 스레드가 존재한다: 생산자는 데이터를 생성하고, 소비자는 데이터를 소모한다. 다음 조건을 만족해야 한다.

1. 버퍼에 대한 접근은 반드시 상호 배제되어야 한다.
2. 여러 생산자 또는 소비자가 동시에 작동해도 되지만, 버퍼의 상태에 따라 대기해야 한다.
3. 버퍼가 비어 있으면 소비자는 생산자를 기다려야 하고, 버퍼가 가득 차면 생산자는 소비자를 기다려야 한다.

신호등 기법 (Semaphore)

class BoundedBuffer {
    private final Semaphore mutex = new Semaphore(1);
    private final Semaphore fullBuffers = new Semaphore(0);
    private final Semaphore emptyBuffers = new Semaphore(n);

    public void deposit(Object item) {
        emptyBuffers.acquire();  // 버퍼 공간 확보
        mutex.acquire();         // 버퍼 접근 잠금
        add(item);               // 항목 삽입
        mutex.release();
        fullBuffers.release();   // 완료 알림
    }

    public Object remove() {
        fullBuffers.acquire();   // 항목 존재 확인
        mutex.acquire();         // 버퍼 접근 잠금
        Object item = remove();  // 항목 제거
        mutex.release();
        emptyBuffers.release();  // 공간 반환
        return item;
    }
}

관찰자 기법 (Monitor)

class BoundedBuffer {
    private final Lock lock = new ReentrantLock();
    private int count = 0;
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public void deposit(Object item) {
        lock.lock();
        try {
            while (count == n) {
                notFull.await();  // 버퍼 꽉 찼을 경우 대기
            }
            add(item);
            count++;
            notEmpty.signal();    // 소비자 깨우기
        } finally {
            lock.unlock();
        }
    }

    public Object remove() {
        lock.lock();
        try {
            while (count == 0) {
                notEmpty.await(); // 버퍼 비었을 경우 대기
            }
            Object item = remove();
            count--;
            notFull.signal();   // 생산자 깨우기
            return item;
        } finally {
            lock.unlock();
        }
    }
}

독자-저자 문제

공유 데이터를 읽는 독자와 수정하는 저자가 존재한다. 다음 규칙을 준수해야 한다.

1. 저자는 단일 스레드만 허용된다.
2. 독자는 병렬로 여러 명이 동시에 읽을 수 있다.
3. 독자 우선 또는 저자 우선 전략 중 하나를 선택할 수 있다.

독자 우선 (Reader-Friendly) - 신호등 방식

class SharedResource {
    private int readerCount = 0;
    private final Semaphore readMutex = new Semaphore(1);
    private final Semaphore writeMutex = new Semaphore(1);

    public void write() {
        writeMutex.acquire();
        // 데이터 변경
        writeMutex.release();
    }

    public void read() {
        readMutex.acquire();
        if (readerCount == 0) {
            writeMutex.acquire();  // 첫 독자라면 저자 차단
        }
        readerCount++;
        readMutex.release();

        // 데이터 읽기

        readMutex.acquire();
        readerCount--;
        if (readerCount == 0) {
            writeMutex.release();  // 마지막 독자면 저자 허용
        }
        readMutex.release();
    }
}

저자 우선 (Writer-Friendly) - 관찰자 방식

class SharedResource {
    private int activeReaders = 0;
    private int activeWriters = 0;
    private int waitingReaders = 0;
    private int waitingWriters = 0;

    private final Lock lock = new ReentrantLock();
    private final Condition canRead = lock.newCondition();
    private final Condition canWrite = lock.newCondition();

    public void write() {
        lock.lock();
        try {
            while (activeReaders > 0 || activeWriters > 0) {
                waitingWriters++;
                canWrite.await();
                waitingWriters--;
            }
            activeWriters++;
        } finally {
            lock.unlock();
        }

        // 데이터 작성

        lock.lock();
        try {
            activeWriters--;
            if (waitingWriters > 0) {
                canWrite.signal();  // 쓰기 대기자 우선 깨우기
            } else if (waitingReaders > 0) {
                canRead.signalAll();  // 모든 독자 깨우기
            }
        } finally {
            lock.unlock();
        }
    }

    public void read() {
        lock.lock();
        try {
            while (activeWriters > 0 || waitingWriters > 0) {
                waitingReaders++;
                canRead.await();
                waitingReaders--;
            }
            activeReaders++;
        } finally {
            lock.unlock();
        }

        // 데이터 읽기

        lock.lock();
        try {
            activeReaders--;
            if (activeReaders == 0 && waitingWriters > 0) {
                canWrite.signal();  // 쓰기자 깨우기
            }
        } finally {
            lock.unlock();
        }
    }
}

철학가 식사 문제

5명의 철학가가 원탁에 앉아 있으며, 각각 왼쪽과 오른쪽에 포크가 하나씩 있다. 식사는 두 개의 포크를 동시에 가져야 가능하며, 생각할 때는 포크를 내려놓는다. 무한 데드락을 피하기 위한 조건을 설정해야 한다.

포크 사용 상태 관리 (신호등 기법)

class DiningPhilosophers {
    private final int N = 5;
    private final Semaphore[] forks = new Semaphore[N];
    private final Semaphore mutex = new Semaphore(1);
    private final int[] state = new int[N];  // THINKING, HUNGRY, EATING

    public DiningPhilosophers() {
        for (int i = 0; i < N; i++) {
            forks[i] = new Semaphore(1);
        }
    }

    public void takeForks(int i) {
        mutex.acquire();
        state[i] = HUNGRY;
        test(i);
        mutex.release();
        forks[i].acquire();  // 포크 획득
    }

    public void putForks(int i) {
        mutex.acquire();
        state[i] = THINKING;
        test((i - 1) % N);  // 왼쪽 인접자 검사
        test((i + 1) % N);  // 오른쪽 인접자 검사
        mutex.release();
        forks[i].release();  // 포크 반납
    }

    private void test(int i) {
        if (state[i] == HUNGRY &&
            state[(i - 1) % N] != EATING &&
            state[(i + 1) % N] != EATING) {
            state[i] = EATING;
            forks[i].release();  // 포크 허용
        }
    }
}