#14. 기타 전통적 동기화 문제

전통적 동기화 예제

- Producer and Consumer Problem

  * 생산자-소비자 문제

  * 유한버퍼 문제 (Bounded Buffer Problem)

- Readers-Writers Problem

  * 공유 데이터베이스 접근

- Dining Philosopher Problem

  * 식사하는 철학자 문제

 

Readers-Writers Problem

- 공통 데이터베이스

  * Readers : read data. never modify it.

  * Writers : read data and modify it

  * 상호배타 : 한 번에 한 개의 프로세스만 접근 - 비효율적

- 효율성 재고 

  * Each read or write of the shared data must happen withing a critical section.

  * Guarantee mutual exclustion for writers.

  * Allow multiple readers to execute in the critical section at once.

(여러 Reader Process는 Critical Section에 접근 가능하지만, Writer Process는 Mutual Exclusion이 되어야 한다. 즉, 하나의 Reader가 들어오면 다른 Reader도 들어올 수 있음. 단, Writer는 오로지 한번에 하나만 접근 가능.)

- 변종

  * The first R/W problem (readers-preference)

(우선권을 Reader에게 먼저 줌)

  * The second R/W problem (writers-preference)

(우선권을 Writer에게 먼저 줌)

  * The Third R/W problem

(우선권을 아무에게도 안 줌)

 

 (정리 : Readers-Writers Problem은 Critical Section에 Reader Process가 Access하면 Writers가 접근하지 못하는것. 반대도 성립. 단, 효율성 재고 측면에서 Reader Process가 접근 중 다른 Reader Process는 접근 가능)

 

Dining Philosopher Problem

- 식사하는 철학자 문제

  * 5명의 철학자, 5개의 젓가락, 생각 -> 식사 -> 생각 -> 식사 ...

  * 식사하려면 2개의 젓가락 필요

- 프로그래밍

  * 젓가락 : 세마포어(# of permit = 1)

  * 젓가락과 세마포어에 일련번호: 0 - 4

  * 왼쪽 젓가락 -> 오른쪽 젓가락

 (예를 들어 한 철학자가 젓가락을 들면 다른 철학자는 들지 못한다. 이걸 코드로 작성해보자 )

package com.company;

import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
    int id;         // philosopher id
    Semaphore lfticks, rtticks;

    public Philosopher(int id, Semaphore lfticks, Semaphore rtticks) {
        this.id = id;
        this.lfticks = lfticks;
        this.rtticks = rtticks;
    }

    void eating() {
        System.out.println("[" + id + "] eating");
    }

    void thinking() {
        System.out.println("[" + id + "] thinking");
    }


    @Override
    public void run() {
        try {
            while(true) {
                lfticks.acquire();
                rtticks.acquire();
                eating();

                lfticks.release();
                rtticks.release();
                thinking();
            }

        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

public class Test_14 {
    static final int num = 5;

    public static void main(String[] args) {
        int i;

        /* Chopsticks */
        Semaphore[] stick = new Semaphore[num];
        for(i = 0; i < num; ++i) {
            stick[i] = new Semaphore(1);
        }

        /* Philosophers */
        Philosopher[] phil = new Philosopher[num];
        for(i = 0; i < num; ++i) {
            phil[i] = new Philosopher(i, stick[i], stick[(i + 1) % num]);
        }

        /* let philosophers eat and think */
        for(i = 0; i < num; ++i) {
            phil[i].start();
        }
    }

}

실행해보면 철학자가 랜덤으로 밥을 먹고, 생각을 한다. 그런데 중간에 실행을 하다가 멈춰 버리는 현상이 나타난다. 이유가 뭘까?

- 잘못될 결과(Starvation  기아)

- 모든 철학자가 식사를 하지 못해 굶어 죽는 상황 

deadlock(= 교착상태)

(철학자들이 모두 배가 고파 불행하게도 모두 왼쪽 젓가락을 들었다. 이러면 오른쪽 젓가락이 있어야 밥을 먹을 수 있는데, 자신의 오른쪽 철학자가 왼쪽 젓가락을 들고 있어서 모두 밥을 못먹는 상황이 생길 수 있다.)

 

  

Deadlock

- 프로세스는 실행을 위해 여러 자원을 필요로 한다.

  * CPU, 메모리, 파일, 프린터, ......

  * 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할 때 (e.g, 다른 프로세스가 사용 중) 대기해야

  * 다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착상태 가능성!

- 교착상태 필요 조건 (Necessary Conditions)

  * Mutual exclusion (상호베타)

  * Hold and Wait (보유 및 대기)

  * No Preemption (비선점)

  * Circular wait (환형대기)

(이 모든게 만족되면 교착상태가 일어날 수 있음) 

 

 

 Resources

- 동일 자원

  * 동일 형식 (type) 자원이 여러 개 있을 수 있다. (instance)

  * 예) 동일 CPU 2개, 동일 프린터 3개 등

- 자원의 사용

  * 요청 (request) -> 사용 (use) -> 반납 (release)

- 자원 할당도 (Resource Allocation Graph)

  * 어떤 자원이 어떤 프로세스에게 할당되었는가? 

  * 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는가?

  * 자원: 사각형, 프로세스: 원, 할당: 화살표

 

- 교착상태 필요조검

  * 자원 할당도 상에 원이 만들어져야 (환형대기)

  * 충분조건은 아님

 

- 예제 : 식사하는 철학자 문제

  * 원이 만들어지지 않게 하려면?

  * 가령 짝수번째 철학자는 오른쪽 젓가락을 들고, 홀수번째 철학자는 왼쪽 젓가락을 들게해서

원형을 이루지 않게 하면 dead lock 상태에 놓이지 않는다.