Synchronization : Advanced

Producer-Consumer Problem

producer와 consumer는 생성자와 소비자의 문제라고 보면 됩니다.

shared buffer는 array로 된 버퍼로 하나씩 채워갑니다. 

producer 입장에서는 계속 해서 item을 채우다가 buffer가 꽉 차면 중단합니다.

consumer는 buffer가 empty 상태가 아니면 계속 해서 소비합니다.

 

이러한 두 thread는 concurrent 하게 돌아가며 producer는 무언가를 생성하고 concumer에게 알려줍니다.

consumer은 item을 기다리다가 item이 있으면 buffer로 부터 item을 빼고 producer에게 알려줍니다.

 

한개의 mutex와 2개의 counting semaphore가 필요합니다.

mutex : 1인 세마포어를 의미

slots : buffer에 insert 가능한 크기를 의미 (counting semaphore)

items : buffer에 들어가 있는 item의 개수를 의미 (counting semaphore)

다음과 같은 구조체로 표현가능합니다.

4개의 함수를 통해 조작이 가능합니다.

sbuf_init함수와 sbuf_deinit 함수 입니다.

init 함수는 buffer를 n의 크기로 초기화 해주는 함수입니다. 

deinit 함수는 buffer를 free를 통해 해제하는 작업을 해주는 함수입니다.

producer가 호출합니다.

buffer에 item을 삽입하는 insert 함수 입니다.

먼저 P함수를 통해 buffer의 slot을 -1 합니다. item을 삽입해주어야 하기 때문입니다.

그 다음 P함수를 통해 mutex를 -1을하고 해당 buffer 위치에 item을 삽입하고 V 함수를 통해 다시 mutex를 +1

합니다.

마지막으로 items는 item이 몇개 왔는지 세는 변수이므로 V함수를 통해 items를 +1해줍니다.

consumer가 호출합니다.

buffer에 item를 삭제하는 remove 함수입니다.

먼저 P함수를 통해 items를 -1해줍니다. buffer에서 item을 삭제해주기 때문입니다.

그 다음 P함수를 통해 mutex를 -1합니다. 그리고 buffer의 해당위치에 있는 item을 뺍니다.

V함수를 통해 mutex를 +1 해줍니다.

마지막으로 V함수를 통해 slots 변수를 +1 해줍니다. item 1개가 나갔으므로 다시 slot을 +1 해주는 것입니다.

마지막에 해당 제거한 item을 return해줍니다. 

thread를 이용한 concurrent server를 구축한 모형입니다.

먼저 worker thread를 NTHREADS 만큼 만들어 주고 while 문으로 들어갑니다.

accept 하고 buffer에 해당 connfd를 insert 해줍니다.

worker thread가 하는 작업입니다.

while문을 보면 먼저 connfd에 제거된 해당 buffer의 item을 저장합니다.

echo 함수를 통해 해당 connfd를 출력하고 

close 합니다.

echo 하는 부분입니다.

echo 함수에 쓰인 변수들을 초기화 해주는 함수입니다.

 

Readers-Writers Problem

reader, writer thread가 존재해 어떻게 mutual exclusion을 해결할지 보는것입니다.

문제는 object를 여러 thread가 read, write할 수 있습니다. 

writer는 해당 object를 배타적으로 접근해야 합니다. 즉, 자신 혼자서만 사용해야합니다.

read는 object를 여러 read thread가 읽을 수 있습니다.

 

First reader-writers problem (favors readers)

reader에게 우선순위를 주는 것입니다. 

예를 들어 object에 R1이 들어오고 W1과 R2가 차례로 들어오면 

R1 -> R2 -> W1 순서로 처리됩니다.

 

Second readers-writers problem (favors writers)

writer에게 우선순위를 주는 것입니다. 

마찬가지로 W를 우선적으로 처리해 줍니다.

 

하지만 결국 두개 모두 starvation 문제가 존재하게 됩니다.

위에서 해당된 problem을 그대로 구현한 code입니다. 마찬가지로 starvation 문제가 발생합니다.

 

Crucial concept : Thread Safety

thread로 호출된 함수들은 thread-safe 해야 합니다.

thread safe하다는 의미는 수많은 thread로 부터 함수를 반복적으로 호출하더라도 공유된 자원이 우리가 예상한대로

결과가 나올때를 의미합니다.

 

thread safe를 4단계로 나눌 수 있습니다.

class 1 : 공유 자원을 protect 하지 않는 함수 (공유 변수를 여러 thread들이 sharing 할때 mutex lock을 하지않음)

class 2 : thread들이 함수를 계속 호출하는데 호출 할 때마다 상태를 계속 기억해야하는 함수

class 3 : return 값이 static variable입니다. 따라서 thread들이 static variable의 pointer을 return 하는 함수

class 4 : thread-unsafe 함수를 호출하는 함수

 

Thread-Unsafe Functions

Class 1

sared variable을 protect 하지 않는 경우

P, V 함수를 통해 고칠 수 있습니다.

 

Class 2

해당함수는 전역변수 next가 랜덤하게 수를 return하는 함수입니다.

여기서 문제점은 여러 thread들이 srand함수에 접근해 next변수를 바뀌게하면 원래 예상된 결과값을 잃게 됩니다.

이전에 본 rand함수를 새롭게 만들어야 합니다. nextp라는 past argument를 인자로 넘겨줍니다. 

따라서 값을 계속해서 기억하는 것입니다.

 

Class 3

위의 함수는 이미 thread-unsafe한 상황을 P와 V를 통해 고친 상태입니다.

ctime함수에 인자로 들어가는 timep는 전역변수이기 때문에 여러 thread가 ctime을 호출하면 그 사이에 

공유된 메모리의 값이 변경될 수 있습니다. 따라서 ctime은 thread-unsafe한 함수입니다.

이를 고치기 위해 2가지 방법이 존재합니다.

1. Rewrite Function

말 그대로 모든 함수 코드들을 고치는 것입니다. 하지만 이런 방법은 너무 복잡합니다.

2. Lock and copy

ctime함수를 누구도 호출할 수 없게 하는것입니다. 

따라서 ctime부분을 mutex lock을 걸어 P, V를 통해 실현하는 것입니다.

 

Class 4

thread unsafe한 함수를 호출하는 경우를 말합니다.

 

Reentrant Functions

thread-safe 함수중에 reentrant한 함수를 정의합니다.

여러 thread가 이 함수를 호출하는데 thread간의 shared variable이 전혀 없는 것을 reentrant라고 합니다.

 

예를 들어 위에서 본 rand_r 함수 같은 경우 nextp를 자신이 가지고 있음으로 상태를 keep 하고 전역변수

문제를 해결했습니다. 따라서 rand_r은 reentrant한 함수입니다.

 

EX)

Not thread-safe, not reentrant (thread safe하지도 않고 reentrant하지도 않은 함수)

int tmp; //전역변수
int add(int a){
	tmp = a;
    return tmp + 10;
}

 

Not thread-safe, but reentrant (thread-safe 하지는 않지만 reentrant인 함수)

int tmp; //전역변수
int add(int a){
	tmp = a;
    return a + 10;
}

 

Thread-safe but not reentrant (thread-safe 하지만 reentrant 하지는 않은 함수)

thread_local int tmp;
int add(int a){
	tmp = a;
    return tmp + 10;
}

thread_local 변수를 설정해 해당 thread에서만 접근가능하게 설정합니다.

 

Thread-safe and reentrant (thread safe 하고 reentrant인 함수)

int add(int a){
	return a + 10;
}

 

Thread-Safe Library Functions

stdio.h 에 있는 함수들은 모두 thread-safe 합니다.

하지만 위에 보이는 함수들이 대표적으로 예외 case입니다.

이러한 unsafe함수들을 reentrant version(safe) 함수로 바꿀 수 있습니다.

 

One worry : Races

위의 코드를 살펴보면 main thread가 i = 0 일 때 peer thread 0을 만들고 

main thread에서는 i = 1로 바꿔놨습니다. 

여기서 peer thread 0 도 i에 접근하는데 이 때 main thread의 i가 서로 동일합니다.

결국 여기서 race가 발생하게 됩니다.

실제로 race가 발생하는지 알아봅니다.

100개의 thread를 만들고 각 thread마다 i를 저장하는지 확인합니다.

정상적으로 race가 발생하지 않으면 중복되는 값이 없어야 합니다.

정상으로 나오려면 no race 처럼 균등하게 일어나야 합니다.

하지만 그렇지 않습니다.

따라서 race가 발생합니다.

 

Race Elimination

이를 해결하기 위해 main thread에서 malloc을 해 heap space를 사용하는 것입니다.

그리고 i값이 아니라 ptr의 값을 넘기는 것입니다.

 

Another worry : Deadlock

또 다른 문제점으로 deadlock이 발생할 수 있습니다.

예를 들어 thread 1 이 공유 자원 A를 소비하고 B를 소비한다고 하자.

또한 thread 2 가 공유자원 B를 소비하고 A를 소비한다고 하면

thread 1 이 A를 소비하고 B를 소비할 때 thread 2 가 B를 잡고 있어 진행이 어렵게 됩니다.

위 code를 보면 thread 0 번은 semaphore 0번을 잡고 thread 1 도 semaphore 1번을 잡은 상태이기에

thread 0 번이 1번을 잡아야 진행되는데 thread 1 번 때문에 진행이 안되는 상태입니다.

thread의 P함수를 바꿔줌으로써 순서를 바꿔주었습니다.