5주차. 프로세스 동기화 (4) - 전통적인 동기화 문제 (Producer/Consumer, Reader/Writer, Dining philosopers), Monitor

Producer - Consumer Problem

Producer

• 자원 : 비어있는 버퍼
• 공유 메모리(버퍼)에 접근하여 Empty-Buffer를 확인한다.
• 공유메모리에 접근할 때마다 빈 버퍼의 개수는 줄고, 데이터는 추가된다.

Consumer

• 자원 : 채워져있는 버퍼
• 공유 메모리(버퍼)에 접근하여 Full-Buffer를 확인한다.
• 공유 메모리에 접근할 때마다 빈 버퍼의 개수는 늘고, 데이터는 줄어든다.

동기화를 위한 Semaphore 변수

• Producer & Consumer가 존재하고 있는 상황으로 버퍼로의 동시접근을 막기 위해 Binary Semaphore로 lock / unlock 수행을 해줘야 한다.
  즉, 버퍼에 생산자든 소비자든 동시에 하나만 접근해서 조작할 수 있다.
• 생산자/소비자의 자원 개수 카운팅을 위해서 Integer Semaphore를 사용한다.

생산자 혹은 소비자가 동시에 버퍼에 접근할 수 있다.

1. Binary Semaphore (Mutex) : 소비자 or 생산자가 데이터 조작을 위해 동시에 공유버퍼에 접근하는 것을 막는다. mutual exclusion 적용
2. Counting-Semaphore : 버퍼가 가득차거나, 비었는지 확인하기 위해 버퍼의 개수를 세는 용도.

 

생산자(Producer) 코드

do {
    produce an item in X; // 데이터 생성
    
    P(empty); // 비어있는 버퍼 확인, 없으면 대기
    P(mutex);
    /* critical section */
    add X to buffer (shared memory);
    /* critical section */
    V(mutex);
    V(full); // 데이터 담은 버퍼 반환
} while(true)

do {
    P(full); // 차 있는 버퍼 확인
    P(mutex);
    /* Critical Section */
    Remove the item from buffer to Y // shared memory
    /* Critical Section */
    V(mutex);
    V(empty); // 비운 버퍼 반환
    
    consume the item in Y; // 데이터 사용
} while(true);

Producer

1. 빈 버퍼가 있는지 알기위해 P(empty) 연산 : 빈 버퍼가 있다면 버퍼 취함, 없으면 대기
2. 버퍼에 데이터 추가를 위해서 공유 버퍼에 대한 P(mutex)연산
   • 해당 버퍼를 사용중이 아니라면 수행, 사용중이면 대기
   • 사용시 Buffer(공유 메모리)에 Lock을 건다
3. 버퍼에 대한 수행 종료 후 공유 버퍼에 대한 V(mutex) 연산
   • 공유 버퍼 접근에 대한 mutex 해제
   • Buffer의 Lock을 푼다
4. 데이터를 담은 버퍼를 반환하는 V(full) 연산

Consumer

1. 데이터가 들어있는 버퍼가 있는지 P(full) 연산 : 자원이 담긴 버퍼가 있다면 해당 버퍼 취함, 없으면 대기
2. 버퍼에 들어있는 공유 데이터에 대해 P(mutex)연산
   • 사용시 Buffer에 Lock을 건다
3. 데이터를 꺼내가고 난 후 공유 데이터에 대한 V(mutex)연산
   • 사용 종류 후 Buffer에 Lock을 푼다
4. 비워진 버퍼에 대한 V(empty)연산

 

---

Readers-Writers Problem

한 프로세스가 DB에 write 중 일때 다른 process가 write를 위해 접근해서는 안되며, 프로세스가 read 중 일때 read는 동시에 모두 접근이 가능하다.

• Shared Data : DB
• readcount : 현재 DB에 접근중인 Reader의 수

Writer/Reader가 동시에 DB에 접근하는 것을 막는 Semaphore, Reader의 공유변수 readcount에 동시 접근을 막는 Semaphore가 필요하다.

1. DB를 위한 Binary-Semaphore (mutual exclusion, mutex)
2. readcount를 위한 Binary-Semaphore (mutual exclusion, mutex)

Write 코드

P(db);
/* critical section */
Wrting db is performed;
/* critical section */
V(db);

Reader 코드

P(mutex);
readcount++;
if (readCount == 1) P(db); // 첫 reader가 올 때 db를 잠금, 이후 reader에 대해서는 free pass
V(mutex);
reading DB is performed;
P(mutex);
readcount--;
if (readCount == 0) V(db); // 모든 Reader가 나오면 db잠금을 풀음, write의 starvation 발생 문제가 있다.
V(mutex);

Writer

1. writer는 DB 접근 시 사용중인지 아닌지 알기위해 P(DB) 연산
   • DB에 Lock을 걸게 된다
2. 원하는 연산 수행 후 DB를 반납하기 위해 V(DB) 연산
   • DB의 Lock을 풀어준다

Reader

reader는 read 중에 다른 프로세스의 read 접근 시 모두 허용되어야 한다.

readcount는 Reader의 공유 변수로 모든 reader들이 접근 할 수 있는 변수이다. 따라서 Critical Section으로서 해당 변수에 대해 mutual exclusion이 보장되야 한다.

1. readcount에 대해 P(mutex) 연산
   • readcount를 사용하기 위해 Lock을 건다.
   • reader가 추가 될 때마다 readcount++
   • 만약 read작업 중 자신이 첫번째 reader였으면 DB에 대해 P(DB) 연산 → (writer의 접근 막는다)
2. readcount를 반납하기 위해 V(mutex) 연산
3. DB에 대해 원하는 read 수행 (Critical Section)
4. readcount에 대한 P(mutex) 연산
   • reader가 끝날 때마다 readcount--
   • 만약 read작업 중 자신이 마지막 reader 였다면 V(DB) 연산 → DB의 Lock 해제 (write 접근 가능)
5. readcount를 반납하기 위해 V(mutex) 연산

Starvation 문제점을 내포하고 있다

• readcount가 0이 되기 직전에 reader가 계속 오면 write작업이 너무 오래 기다리는 현상이 발생할 수 있다.
• 해결방법) priority queue를 이용해서 해결해 줄수 있다. write가 너무 오래 기다리면 read 진행 중이여도 lock을 풀어준다거나, 일정 시간 이상 read가 진행되면 lock을 풀어주는 방법 등이 있다. (신호등 예를 생각, 초록불 키고 끄고)

 

---

Dining-Philoshopers Problem

5명의 철학자가 한 원탁에서 공유하는 젓가락을 가지고 식사, 생각을 번갈아 가면서 하는 상황에서 발생하는 deadlock 문제

문제 코드

/* Synchronization Variable */
Semaphore chopstic[5];

/* Pillosopher i */
do {
  P(chopstic[i]);
  P(chopstic[(i+1) % 5]);
  eat();
  V(chopstic[i]);
  V(chopstic[(i+1) % 5]);
  think();
} while(true);

위와 같이 P(왼쪽 젓가락), P(오른쪽 젓가락) 순서로 따로 하게 될 경우 P(i)까지 진행 후 P(i + 1)에서 젓가락이 사용중이라 대기하는데, 모든 철학자들이 동시에 그럴 수 있다.

→ 즉, 동시에 모든 철학자들이 왼쪽 젓가락만 들고있는 상황 → DeadLock

 

해결방안

• 테이블에 동시에 4명의 철학자까지만 앉을수 있도록한다
• 양 젓가락 두개를 집을 수 있는 상황에만 젓가락을 집도록 한다
• 짝수 번호 철학자는 오른쪽 젓가락 부터, 홀수 번호 철학자는 왼쪽 젓가락 부터 집도록 한다

 

양 젓가락 두개를 집을 수 있는 상황에만 식사하도록 하는 코드

처음 각 철학자들의 semaphore self[] 변수는 0으로 초기화 되어있다. 즉 처음에는 모두 젓가락이 없는 상황

• 따라서 양쪽 철학자들이 모두 안먹고 있고 & 자기가 배고프면 → self[i]를 V(self[i])로 젓가락을 잡을수 있도록 풀어주고, 이후에 P(self[i])로 먹을 수있는지 없는지 확인 후 먹게 된다. 그게 아니라면 P(self[i])에서 대기하게 된다
• 먹고 난 뒤 putdown() 후 think()하고 다시 젓가락들 수 있는지 확인하는 걸 반복한다
• 만약, 양쪽 철학자에 대해서 조건을 체크하는 test(i)에서 조건이 안맞는 경우, P(self[i])에서 대기하다가 다른 철학자가 putdown()을 통해 i의 양 옆 철학자가 먹을수 있다고 V(self[양 옆]) 연산을 해주면 그제서야 P(self[i])가 풀리고 먹게 된다.

self[i]

• 철학자 자신의 젓가락을 들수 있는지 없는지에 대한 semaphore
• P(self[i]) → i가 현재 젓가락을 들 수 있는지 확인 후 들음
• V(self[i]) → i가 현재 젓가락을 반납함

mutex

• 각 철학자의 상태에 변경에 대한 semaphore
• 자신의 상태를 변경하기 전 후로 P, V연산을 해준다
• P(mutex) → 젓가락을 들 때 자신의 상태를 hungry로 바꿔주고, 젓가락을 들 수 있는 상황인지 확인 후 mutex반환. 또는, 젓가락을 내려놓을 때, 자신의 상태를 thinking으로 바꿔주고, 양옆에 대해 상태를 확인해준다, 그러고 mutex 반환
• V(mutex) → 상태를 변경하고 나서, 자신 또는 양옆의 상태를 확인해주고 반환한다

 

---

Monitor

Semaphore의 문제점

• 코딩하기 힘들다.
• 정확성 (correctness)의 입증이 어렵다.
• 자발적 협력(voluntary cooperation)이 필요하다.
• 한번의 실수가 모든 시스템에 치명적 영향을 준다.
  • P(mutex) - critical section - P(mutex) → Deadlock 발생
  • V(mutex) - critical section - P(mutex) → mutual exclusion이 깨진다.
  • 순서를 잘지켜서 잘 짜야된다.

Monitor

• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct.
• Semaphore를 한단계 더 추상화 시킴으로서 P(), V()연산등의 연산 실수를 방지하고, 공유데이터의 사용은 monitor를 통해서만 사용할 수 있도록 하고, 그에 대한 관리는 monitor에서 전적으로 하게 된다.

Monitor 내부에 공유데이터, 공유 데이터를 접근하는 operation을 정의하고, 해당 공유데이터 접근은 같은 모니터 내 operation(procedure)으로만 가능하게 한다.

• 모니터는 모니터 내부의 operation(procedure)을 오직 하나의 프로세스만 실행 가능하도록 통제한다.
  → 따라서 프로그래머가 공유 데이터에 대해 따로 lock을 걸고 풀 필요가 없다.
• 외부에서 기다리는 프로세스는 모니터 내부에 Active한 프로세스가 없다면 들어와서 수행하게 된다.
  → 모니터 내부 프로세스들이 suspend되어 특정 condition 큐에서 대기중이거나 빠져 나간 경우에 하나씩 들어올 수 있게 된다

형태

monitor monitor-name {
    shared variable declaration;

    procedure body P1() {
    	...
    }
    procedure body P2() {
    	...
    }
    procedure body Pn() {
    	...
    }
}

• shared variable가 Monitor안에 선언되어서 해당 모니터 내에서만 공유데이터에 접근이 가능하고, 모니터 내에 선언된 precedure 들로만 공유변수에 접근이 가능하다.
• 모니터에 접근하는 프로세스를 제어하기 위해 condition variable을 사용한다.

Condition Variable

• 프로세스가 모니터를 기다리게 하기 위해서 기존의 Binary-semaphore (Mutex) 대신 condition variable을 사용한다.
• wait(), signal() 연산에 의해서만 접근이 가능하다

x.wait() : 재우기

• x.wait()을 invoke한 프로세스는 suspend 상태가 된다.
• 다른 프로세스가 x.signal()을 invoke하면 깨어난다.

x.signal() : 깨우기

• x.signal()은 잠들어있는 suspend 상태의 프로세스 하나를 resume 해준다.

Monitor를 이용한 Bounded-Buffer problem 구현 코드

monitor bounded_buffer {
    int buffer[N];
    condition full, empty;
    
    void produce(int x) {
    	if (empty_buffer.isEmpty()) // 비어있는 버퍼 X, empty 큐에 대기
        	empty.wait();
        add x to empty_buffer;
        full.signal(); // 버퍼 채움, full 큐에 대기하는 프로세스 깨움
    }
    
    void consumer(int *x) {
    	if (full_buffer.isEmpty()) // 데이터 있는 버퍼 X, full 큐에 대기
        	full.wait();
        remove x from full_buffer to *x;
        empty.signal(); 버퍼 비움, empty 큐에 대기하는 프로세스 깨움
    }
}

monitor가 다른 프로세스의 접근은 관리해주므로 buffer에 대한 동시적인 접근을 제어할 필요가 없다. 오직 비어있는 버퍼가 있는지, 채워져있는 버퍼가 있는지만 고려해주면 된다.

 

produce()

• empty buffer가 없으면 empty.wait()으로 suspend, empty 큐에 가서 suspend 상태로 empty 버퍼가 생겨서 자기 차례가 올때까지 기다린다.
  → 누군가 empty.signal()로 resume 시 아래 코드 진행, 버퍼에 데이터를 담고 full.signal() 해준다

• empty.wait() = semaphore에서 P(empty)
• full.signal() = semaphore에서 V(full)

consume()

• full buffer가 없으면 full.wait()으로 suspend, full 큐에 가서 suspend상태로 full 버퍼가 생겨서 자기 차례가 올때까지 기다린다
  → 누군가 full.signal()로 resume해주면 아래 코드 진행, 버퍼에서 데이터를 꺼내고 empty.signal() 해준다

• full.wait() = semaphore에서 P(full)
• empty.signal() = semaphore에서 V(empty)

모니터는 대기큐를 관리하면서 critical section을 사용하고자하는 프로세스들을 재우고, 깨우는 역활을 하는 것

Monitor를 이용한 Dining-Philosophers 구현 코드

공유 데이터

• 각 철학자의 상태인 state[5]
• 철학자 프로세스의 상태를 suspend, resume하기 위한 self[5]

pickup(i)

• i번 철학자가 젓가락을 들기위해 상태를 hugry로 변경 후, test(i)를 통해 젓가락을 들 수 있는지 확인한다. test()를 확인 후, 철학자 상태가 eating이라면 다음 eat()함수로 진행, 아니라면 젓가락을 못드는 상태이므로 eating 상태가 될때까지 (즉, 젓가락을 들 수 있는 상태) 대기한다

test(i)

• 자신의 왼쪽, 오른쪽 철학자가 먹고 있는 중이 아니고 (= 젓가락을 안쓰고 있고), 자신이 배고프다면 → eating 상태로 변경, 만약 현재 철학자가 suspend 상태면 signal()로 깨워준다

putdown(i)

• state[i] = thinking 으로 식사를 마친 철학자의 현재의 상태를 thinking으로 변경해준다. 이후에 자신이 식사를 하느라 양옆이 식사를 못먹고 suspend 되어 있을 수 있으므로, 양옆 철학자의 상태에 대해 test(양 옆)를 진행한다
• 만약 옆에 철학자가 배고팠는데 젓가락이없었으면 suspend 된 채로 대기하고 있었을 것이고, 그 철학자 양옆을 보고 (일단 한쪽은 지금 생각하게 된 철학자 i) 둘다 식사를 안하고 있다면 잠자던 철학자를 깨워준다.

---

Thread 동시성 문제 Mutex를 이용해서 해결하기

쓰레드 동시성 문제를 내포한 코드

#include<stdio.h>
#include<pthread.h>
#define NUMLOOP 100000000

unsigned int cnt = 0;

void *count(void *data)
{
	int i;
	for (i = 0; i < NUMLOOP; i++) {
		cnt++;
	}
	return NULL;
}

int main(void)
{
	pthread_t t[2];

	printf("create thread 1,2 and  plus cnt\n");

	pthread_create(&t[0], NULL, count, NULL);
	pthread_create(&t[1], NULL, count, NULL);
	pthread_join(t[0], NULL);
	pthread_join(t[1], NULL);

	printf("cnt: %d\n", cnt);

	return 0;
}

• 1억번 1을 전역변수 cnt변수에 더한다.
• 쓰레드 2개를 만들고 둘다 같은 함수를 통해서 동일한 전역변수 cnt에 1을 더하는 로직이다.
• 쓰레드는 전역변수를 공유한다.

결과

• 0.239초만에 두개의 쓰레드가 cnt 변수 하나에 대해서 1억번씩 1을 더하는 로직을 수행했다. 그런데 결과는 100803969로 전혀 잘못된 결과를 내고있다.
• cpu는 메모리에 접근해서 변수를 가져와서 연산을 수행하는데 다른 쓰레드가 변수를 가져가서 1을 더하는 동안 또 다른 쓰레드에서 연산을 수행중인 변수를 가져가서 1을 더한다면 2가 더해지지 않고 1만 더해지는 결과를 낳는다.
• 따라서 해당 변수를 동시에 접근하지 못하도록 mutual exclusion이 되도록 해야한다.

쓰레드 동시성 문제를 mutex를 이용해서 해결한 코드

#include<stdio.h>
#include<pthread.h>
#define NUMLOOP 100000000

unsigned int cnt = 0;
pthread_mutex_t mutex;

void *count(void *data)
{
	int i;
	for (i = 0; i < NUMLOOP; i++) {
		pthread_mutex_lock(&mutex);
		cnt++;
		pthread_mutex_unlock(&mutex);
	}
	return NULL;
}

int main(void)
{
	pthread_mutex_init(&mutex, NULL);
	pthread_t t[2];

	printf("create thread 1,2 and  plus cnt\n");
	pthread_create(&t[0], NULL, count, NULL);
	pthread_create(&t[1], NULL, count, NULL);
	pthread_join(t[0], NULL);
	pthread_join(t[1], NULL);
	
    printf("cnt: %d\n", cnt);

	pthread_mutex_destroy(&mutex);
	return 0;
}

• pthread_muext_t 구조체를 이용하여 mutex를 사용한다.
• mutex를 초기화를 하고 동시에 접근하면 안되는 코드 주위로 Lock/Unlock을 감싸고 종료 때 mutex를 해제한다.

결과

• 정확하게 전역변수 cnt의 값이 2억으로 나오는것을 확인할 수 있다.
• mutex를 사용하기 전에 0.2초대로 계산되는 로직이 약 15배인 3.342초에 걸쳐 수행된 것을 볼 수 있다.
• 100803969이 나왔다는 것은 거의 대부분이 동시에 접근해서 계산했다는 것인데 이제 번갈아 가면서 수행하게 된다.