⚠️ 해당 포스팅은 인프런 공룡책 강의를 듣고 개인적으로 정리하는 글입니다. 정확하지 않은 정보가 있을 수 있으니 주의를 요합니다.
Section 08
Chapter 7 CPU Synchronization Example
Classic Problems of Synchronization
- 다수 동시성 제어의 고전적 문제에는 여러가지가 있다.
: The Bounded-Buffer Problem (한정 버퍼 문제)
: The Readers-Writers Problem
: The Dining-Philosophers Problem (철학자들의 저녁식사 문제)
The Bounded-Buffer Problem
- 다시 생산자 - 소비자 문제로 돌아가서 각각 하나의 항목을 보유할 수 있는 n개의 버퍼로 구성된 풀이 있다고 가정해보자.
- 생산자는 소비자를 위해 버퍼를 가득 채워야하고, 소비자는 생산자를 위해 버퍼를 비워야 한다.
- 이 문제는 어렵지 않게 해결할 수 있다.
Shared Data Structures
- 공유 데이터 구조에서, 바이너리 세마포어
mutex가 있다.
:mutex는 버퍼 풀에 접근할 때 상호 배제를 제공하는 역할을 맡게된다.
: 또한, 초기값은 1로 배정한다. - 더해서, 두 개의 카운팅 세마포어
empty,full이 있다.
: 버퍼가 비어있는지, 차있는지 판단하기 위한 세마포어이다.
:empty는 초기값을 n으로,full은 초기값을 0으로 배정한다.
while(true) {
/* produce an item in next_produced */
. . .
wait(empty); // buffer
wait(mutex); // mutex
/* add next_produced to the buffer */
signal(mutex);
signal(full);
}
while(true) {
/* remove an item from buffer to next_consumed */
. . .
wait(full); // 다 찰 때까지 대기한다.
wait(mutex);
/* consume the itenm in next_consumed */
signal(mutex);
signal(empty); // 버퍼가 비었음을 알린다.
}-
위의 방법에서 생산자는 아래와 같이 동작한다.
: 소비자가 버퍼를 전부 소모할 때까지 대기한다.
: 다 비우면 생산자가 동작한다.
: 생산자 여러 개가 움직이게 될 수도 있기 때문에mutex로 상호 배제한다. -
자바의 코드도 아래 첨부한다.
public class BoundedBuffer {
public static void main(String[] args) {
CashBox cashBox = new CashBox(5);
Thread[] producers = new Thread[1];
Thread[] consumers = new Thread[1];
for (int i = 0; i<producers.length; i++) {
producers[i] = new Thread(new ProdRunner(cashBox));
producers[i].start();
}
for (int i = 0; i < consumers.length; i ++) {
consumers[i] = new Thread(new ConsRunner(cashBox));
consumers[i].start();
}
}
}
class ProdRunner implements Runnable{
CashBox cashBox;
public ProdRunner (CashBox cashBox) {
this.cashBox = cashBox;
}
@Override
public void run() {
try {
while(true) {
Thread.sleep((long)(Math.random()*500));
int money = ((int)(1 + Math.random()*9))*10000;
cashBox.give(money);
}
}catch(InterruptedException e) {}
}
}
class ConsRunner implements Runnable{
CashBox cashBox;
public ConsRunner (CashBox cashBox) {
this.cashBox = cashBox;
}
@Override
public void run() {
try {
while(true) {
Thread.sleep((long)(Math.random()*500));
int money = cashBox.take();
}
}catch(InterruptedException e) {}
}
}
class CashBox{
private int[] buffer;
private int count, in, out;
public CashBox(int bufferSize) {
buffer = new int[bufferSize];
count = in = out = 0;
}
synchronized public void give(int money) throws InterruptedException{
while(count == buffer.length) {
try {
wait();
}
catch(InterruptedException e) {}
}
buffer[in] = money;
in = (in + 1) % buffer.length;
count++;
System.out.println("여기있다, 용돈 : " + money + "원");
notify();
}
synchronized public int take() throws InterruptedException{
while(count == 0) {
try {
wait();
}
catch(InterruptedException e) {}
}
int money = buffer[out];
out = (out + 1) % buffer.length;
count --;
System.out.println("고마워유, 용돈 : " + money + "원");
notify();
return money;
}
}
The Readers-Writers Problem
- 프로세스가 동시성을 지니고 돌아갈 때, 독자(reader)와 작가(writer)는 어떻게 공유 데이터에 접근할까?
(각각 동시성을 가지고 돌아가는 프로세스 간에 공유되는 데이터베이스를 생각해보자.) - 독자의 경우 오로지 데이터베이스를 읽기만 하는 반면, 작가의 경우 데이터베이스를 읽는 것은 물론 수정을 해야하는 상황이 생긴다.
- 분명히 알아두어야 할 것은, 둘 이상의 독자가 공유 데이터에 동시에 접근하더라도 전혀 부작용이 없다는 것이다.
- 그러나, 한 작가 프로세스가 다른 작가 프로세스 혹은 독자 프로세스와 데이터베이스에 동시에 접근할 시 데이터 불일치(data inconsistency) 현상이 발생한다.
-
일반적으로는 이 문제에 대해 reader-writer locks로 해결할 수 있다.
: 실행하려는 프로세스가 독자 프로세스인지, 작가 프로세스인지에 따라 락을 다르게 적용한다.
: 독자 프로세스가 락을 획득하면 모든 독자 프로세스에 관한 락은 풀고, 작가 프로세스에만 락을 적용한다.
: 작가 프로세스가 락을 획득하면 작가, 독자 모두에게 락을 적용한다.
결국 뮤텍스락에서 달라진건 독자 프로세스가 작업할 때도 다른 독자 프로세스 진입을 허용하는 것뿐이다. -
독자-작가 문제에 대한 몇 가지 변형 예제를 들어보자.
모든 변형에는 우선 순위가 포함된다. -
The first readers-writers problem
: 독자 프로세스는 자신 이외의 독자 프로세스가 종료되기 전까지wait()을 호출할 수 없다.
: 이 말은, 간단하게 얘기해서 작가 프로세스는 독자 프로세스 모두가 종료될 때까지 대기함을 의미한다.
: 만약 독자 프로세스가 계속해서 물밀듯이 들어오면 작가 프로세스는 기아(Starvation) 상태에 빠질 수 있다. -
The second readers-writers problem
: 만약 작가 프로세스가 오브젝트에 접근하면, 새로운 독자 프로세스는 실행할 수 없다.
: 작가 프로세스에게 우선 순위를 높게 주어 먼저 실행하게 만드는 것이다.
: 이 역시, 작가 프로세스가 물밀듯이 들어올 경우 독자 프로세스가 기아 상태에 빠질 수 있다.
- 첫번째 독자-작가 문제, 즉 독자에게 우선권을 주는 문제에 대해 더 알아보도록 하자.
:rw_mutx는 독자, 작가 사이의 상호 배제를 위해 사용한다.
:mutex는 공유 변수인read_count에 대한 상호 배제를 위해 사용한다.
:read_count는 얼마나 많은 프로세스가 읽고 있는지 나타내기 위해 사용한다.
read_count = 0 -> 작가 프로세스 진입
while(true) {
wait(rw_mutex); // 독자로부터 신호가 오면 진입
/* writing is performed */
signal(rw_mutex);
}
while(true) {
wait(mutex); // 공유 자원 접근을 위한 요청
read_count++; // 읽고 있는 프로세스의 수 더하기
if(read_count == 1)
wait(rw_mutex); // 독자 프로세스는 여러 프로세스가 진입이 가능하다.
signal(mutex);
/* reading is performed */
wait(mutex); // 공유 자원 접근을 위한 요청
read_count --;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
}-
위의 코드를 보면 어째서 작가 프로세스가 기아 상태에 빠질 수 있는지 파악할 수 있을 것이다.
-
다시 정리해보자.
: 작가 프로세스가 임계 영역에 접근하면 많은 독자 프로세스는waiting상태에 빠질 것이다.
: 이 때 한 개의 독자 프로세스는rw_mutex에서, 그리고 나머지 독자 프로세스는mutex에서 대기하고 있을 것이다.
: 또한, 작가가signal(rw_mutex)연산을 실행할 때 대기중인 작가 프로세스를 실행할지, 독자 프로세스를 실행할지는 모두 스케줄러에 의해 결정된다.
: 어떤 프로세스의 우선 순위를 높이느냐에 따라 해결책이 갈리게 된다.
: 독자 프로세스의 우선 순위를 높인다면 첫번째 방법, 작가 프로세스의 우선 순위를 높인다면 두번째 방법이 될 것이다.
: 이에 대해 뭐가 좋다는 이야기 할 수 없고, 자신의 환경에 맞춰 설정해야 한다.
The Dining-Philosophers Problem
- 다섯 명의 철학자가 원형의 식탁에 앉아 평생동안 생각하거나 밥먹거나, 두 행동만 한다고 생각해보자.
- 철학자들에게 제공된 젓가락은 딱 다섯 개이다.
- 철학자들은 배가 고파지면 두 개의 젓가락이 있어야 음식을 먹을 수 있다.
- 만약 인접한 철학자가 동시에 배고파지면, 한 철학자는 젓가락을 못잡을 것이다.
- 이 상황은 여러 자원을 여러 프로세스가 공유하고 있는 상황이다.
- 상호배제를 포함하여 데드락, 기아를 방지하는 방법은 무엇이 있을까?
- 어떻게 해야 철학자들이 굶어 죽지 않을 수 있을까?
Semaphore Solution
while (true) {
wait (chopstick[i]); // Left
wait (chopstick[(i+1) % 5]); // Right
/* eat for a while */
signal (chopstick[i]);
signal (chopstick[(i+1) % 5]);
/* think for a while */
}- 가장 간단한 방법으로, 각 젓가락에 세마포어를 부여해주는 방식이다.
- 철학자들은 젓가락을 잡을 때
wait()연산을 실행하고, 젓가락을 놓을 때signal()연산을 실행한다. - 이 방법은 간단하게 상호 배제를 보장해준다.
- 그러나, 5명의 철학자가 동시에 배고파지기라도 하면, 그 누구도 양쪽의 젓가락을 집을 수 없게 된다.
다들 왼쪽 젓가락을 잡고 오른쪽 젓가락을 달라고 서로 싸우는 꼴이 된다. - 즉, 데드락과 기아 문제를 해결하지 못한 방법이다.
Pobssible remedies to the deadlock problem (데드락 문제 해결법)
- 철학자의 수를 네 명으로 제한하는 방법
철학자, 즉 프로세스의 수를 제한할 수 있을 때 사용한다. - 양쪽의 젓가락이 놓여져 있을 때만 젓가락을 집게 하는 방법
- 비대칭 전략
: 홀수 번호의 철학자는 먼저 왼쪽 젓가락을 집게 하고,
: 짝수 번호의 철학자는 먼저 오른쪽 젓가락을 집게한다. - 하지만, 모두 기아 문제까지는 해결하지 못한다.
Monitor Solution
- 모니터를 이용해 해결하는 방법이다.
- 철학자들은 양쪽의 젓가락이 모두 놓여져 있을 때 젓가락을 집는다.
- 그리고, 철학자들의 상태를
thinking,hungry,eating로 구분한다. - 한 철학자가 음식을 먹으려면, 인접한 두 철학자가
eating상태가 아니어야 한다. - 또한, 상태 변수를 이용하여 철학자가
hungry상태이지만 음식을 먹을 수 없을 때 스스로를 지연시키도록 한다.
package Synchronization;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
enum State {
THINKING, HUNGRY, EATING
}
public class DiningPhilosophers {
public static void main(String[] args) throws Exception {
int numOfPhils = 5;
Philosopher[] philosophers = new Philosopher[numOfPhils];
DiningPhilosopherMonitor monitor = new DiningPhilosopherMonitor(numOfPhils);
for (int i = 0; i < philosophers.length; i++)
new Thread(new Philosopher(i, monitor)).start();
}
}
class Philosopher implements Runnable {
private int id;
private DiningPhilosopherMonitor monitor;
public Philosopher(int id, DiningPhilosopherMonitor monitor) {
this.id = id;
this.monitor = monitor;
}
@Override
public void run() {
while (true) {
think();
monitor.pickup(id);
eat();
monitor.putdown(id);
}
}
private void think() {
try {
System.out.println(id + ": Now I'm thinking.");
Thread.sleep((long) (Math.random() * 500));
}
catch (InterruptedException e) {
}
}
private void eat() {
try {
System.out.println(id + ": Now I'm eating.");
Thread.sleep((long) (Math.random() * 50));
}
catch (InterruptedException e) {
}
}
}
class DiningPhilosopherMonitor {
private int numOfPhils;
private State[] state;
private Condition[] self; // Condition Value
private Lock lock;
public DiningPhilosopherMonitor(int num) {
numOfPhils = num;
state = new State[num];
self = new Condition[num];
lock = new ReentrantLock();
for (int i = 0; i < num; i++) {
state[i] = State.THINKING;
self[i] = lock.newCondition(); // Condition
}
}
private int leftOf(int i) {
return (i + numOfPhils - 1) % numOfPhils;
}
private int rightOf(int i) {
return (i + 1) % numOfPhils;
}
private void test(int i) {
if (state[i] == State.HUNGRY && state[leftOf(i)] != State.EATING && state[rightOf(i)] != State.EATING) {
state[i] = State.EATING;
self[i].signal();
}
}
public void pickup(int id) {
lock.lock();
try {
state[id] = State.HUNGRY;
test(id);
if (state[id] != State.EATING) self[id].await();
} catch (InterruptedException e) {
} finally {
lock.unlock();
}
}
public void putdown(int id) {
lock.lock();
try {
state[id] = State.THINKING;
test(leftOf(id));
test(rightOf(id));
} finally {
lock.unlock();
}
}
}
- 젓가락의 배포를 담당하는 모니터로
DiningPhilosopher를 사용한다. - 각 철학자는 음식을 먹기 전에
pickup()연산을 실행한다. - 음식을 다 먹으면
putdown()연산을 실행한다. - 이 방법 역시 상호 배제와 데드락 문제는 해결하였지만, 기아 문제는 해결하지 못했다.
Alternative Approaches
- 뮤텍스락, 세마포어, 모니터와 같은 반응형 어플리케이션은 멀티 코어 시스템에서 성능을 상당히 끌어올릴 수 있는 것은 사실이다.
- 그러나, 경쟁 상황의 리스크를 주고 데드락이 일어날 가능성을 높이게 된다.
- 이에 대해 여러 대안이 있다.
: Transactional Memory : 메모리 자체를 원자적으로 설정하는 방법
: OpenMP
: Functional Programming Language : 모든 것이 함수이므로 상호 배제의 가능성 자체가 사라지는 방법
즐겁게 하자 🤭