Synchronization : Basics

Threads Memory Model

Conceptual model

여러 thread들은 하나의 process내에서 작동합니다.

각 thread들은 각자의 thread context를 가집니다.

예를 들어 thread ID, stack, stack pointer, PC, condition code, and GP register 가 있습니다.

모든 thread들은 이외에 나머지 것들을 공유합니다.

예를들어 Code, data(전역변수), heap, 라이브러리가 있습니다.

 

Operational model

어떠한 thread들도 다른 thread의 stack 영역의 data를 write, read할 수 있습니다.

 

concetual model과 operational model의 mismatch때문에 문제점이 발생합니다.

 

Example Program to Illustrate Sharing

첫번째 **ptr은 전역변수로 설정되 있어 공유할 수 있는 data segment로 들어가게 됩니다.

main thread에서는 stack내에 변수 i와 msgs가 있습니다.

ptr은 main thread stack 내에 있는 masg를 가리킵니다.

이제 main theread에서 peer thread 2개를 만듭니다.

각자의 peer thread는 각자의 stack를 가집니다. 각자의 peer thread는 thread 함수를 실행합니다.

thread 함수내에서 static 변수는 전역변수 처럼 data segment로 들어가게 됩니다.

printf("[%ld]: %s (cnt=%d)\n, myid, ptr[myid], ++cnt); 를 하게 되면

ptr을 통해 data segment영역에 접근할 수 있습니다. 또한 ptr은 현재 main thread의 msgs를 가리키므로

결국 main thread내의 stack영역에 접근할 수 있는것입니다. 

cnt는 static 변수이기 때문에 1번만 초기화 됩니다. 

따라서 첫번째 thread함수에서는 cnt = 0으로 초기화되었으므로 이제 더이상 초기화 되지않습니다.

그렇게 되면 peer1에서는 cnt가 1로 출력되고 peer2에서는 cnt가 0으로 초기화 되지않고 1로 시작해

출력할때는 ++이 되므로 2가 출력됩니다.

 

Mapping Variable Instance to Memory

Global variables

가상메모리 공간에 하나만 존재합니다.

Local variables

static으로 선언되지 않은 함수 안에서 선언된 변수를 말합니다.

각 thread stack 내에서 가질 수 있습니다.

Local static variables

static으로 함수안에 선언된 변수입니다. 

초기화가 한번만 됩니다.

전역 변수처럼 data segment에 저장되지만 static이 선언된 thread가 종료되면 같이 없어집니다.

가상 메모리 공간안에서 하나만 있을 수 있습니다.

ptr은 전역변수로서 data segment에 저장됩니다. 

변수 i와 msgs는 main thread 안에서 선언된 변수이므로 main thread stack에 저장됩니다.

변수 myid와 cnt는 각각 peer thread에 선언된 local 변수입니다. 

myid는 각 thread stack에 저장되지만 static으로 선언된 cnt는 전역변수 처럼 data segment에 저장되고

해당 thread가 종료되면 사라집니다.

변수 ptr은 main, peer1 ,peer2 모두 접근 가능합니다.

변수 cnt는 static 이지만 main에서 접근할 수 없습니다. static은 각 thread가 생성되고 종료되면 같이 사라지기

때문에 main thread에서는 접근하기 전에 이미 사라져있습니다.

변수 i는 main thread에서 는 접근 가능하지만 다른 thread에서는 접근이 불가합니다.

아무리 thread 끼리 공유할 수 있지만 ptr로 연결이 되지않기 때문입니다.

반면 변수 msgs는 ptr로 연결이 되기 때문에 다른 thread들도 접근이 가능합니다.

 

Synchronizing Threads

thread를 동기화하다보면 예상못한 상황이 생길 수 있습니다.

각 thread가 cnt에 접근해 ++를 수행할 수 있습니다. 

실행을 해보면 어쩔 때는 cnt = 20000이 되고 어쩔 때는 cnt = 13051이 되며

다르게 결과가 나옵니다. 

왜 그런것일까?

cnt를 ++하는 assembly 코드를 살펴보면 총 3가지로 나눌 수 있습니다.

Load, Update, Store입니다.

결론적으로 말하면 L, U, S 는 Atomic(원자성)해야합니다. 완전히 일체형으로 이뤄줘야 한다는 의미입니다.

그 사이에 다른 context switching이 일어나면 문제가 발생합니다.

이러한 명령어 L, U, S는 critical section이라고 합니다. 하나로 뭉쳐야합니다.

하지만 이러한 instruction order은 스케줄링에 의해 실행되기 때문에 개발자가 할 수 없는 부분입니다.

위의 그림은 정상입니다. critical section이 뭉쳐있습니다.

위의 그림은 atomic이 아닙니다. 따라서 문제가 발생합니다.

 

Progress Graphs

thread 1, 2번이 동시에 실행될 때 실행하는 과정을 그래프로 보여줍니다.

위의 그래프를 보면 thread 1, 2가 실행중입니다. 

(L1, S2)로 가는데 여러 경우의 수가 존재합니다.

Critical Sections and Unsafe Regions

L, U, S는 Critical section으로 atomic 해야합니다.

따라서 unsafe region으로 설정되어 이 영역에 들어올 경우 문제가 발생합니다.

 

Enforcing Mutual Exclusion

그렇다면 어떻게 프로그래머는 safe 한 공간을 보장할 수 있을까?

이에 대한 해답은 synchronize(동기화) 하는 것입니다. 

thread들은 서로 공유 될 수 있기 때문에 critical section에 해당하는 instruction들이 interleaving되지 않도록

동기화 하는 것입니다. 

이를 위해 Semaphore라는 것을 사용합니다.

 

Semaphores

세마포어는 항상 0보다 크거나 같은 정수 전역 변수 입니다. 

이러한 변수는 P(wait, sleep), V(signal, wake up) 에 의해 조작할 수 있습니다.

 

P(s)

s라는 세마포어 변수가 0인지 아닌지 부터 체크합니다.

만약 0이 아니라면 -1을 하고 return 합니다. (이러한 수행은 모두 atomic 하게 수행됩니다. 하드웨어적으로)

만약 0이라면 P를 호출한 함수는 suspend(sleep) 되고 나중에 V 함수에 의해 s값을 +1 해주기 전까지 

잠자고 있는 상태 입니다. (모든 thread 들은 P를 호출할 수 있으므로 s의 값을 계속 변경 가능)

깨어난 다음에는 정상 처럼 P함수를 통해 s값을 -1하고 return 하고 caller 에게 제어권을 넘겨줍니다.

 

V(s)

s의 값을 +1 합니다. (atomic 하게 실행)

만약 P 함수에 의해 block 된 thread가 있으면 그 중에 1개를 깨우고 P함수를 실행해 s를 -1 합니다.

 

t1이  먼저 P 함수를 하면 t2, t3가 P를 호출해도 sleep 상태로 들어갑니다. 

따라서 t1이 먼저 critical section으로 들어가게 되면 lock 상태가 됩니다. 

그 다음 V 함수를 통해  critical section을 빠져나오게 되면 unlock 상태가 됩니다.

이제 t2, t3 둘중에 하나를 깨워서 P함수를 실행합니다.

sep_init 함수는 세마포어를 초기화 해주는 함수입니다. s를 val로 초기화

sem_wait 함수는 P 함수입니다.

sem_post 함수는 V 함수입니다.

위에서 봤던 코드입니다.

for(i = 0; i < niters; i++)
	cnt++;

위 코드가 문제를 일으키기 때문에  atomic 해야합니다.

즉, cnt 부분을 세마포어로 묶어주면 됩니다.

 

Using Semaphores for Mutal Exclusion

 세마포어 변수 mutex를 1로 초기화 해줍니다.

그 다음 critical section에 해당하는 부분을 P(mutex), V(mutex)로 묶어줍니다. 

 

Binary semaphore : 세마포어 값이 0 또는 1이 될때를 의미합니다.

Counting semaphore : 세마포어가 0 또는 1 이 아니고 여러개의 값을 가지고 있는 경우를 말합니다.

 

세마포어로 mutex를 선언하고 1로 초기화 합니다.

위의 코드를 다음과 같이 고쳐줍니다.

처음에 P를 통해 lock 하고 V를 마지막에 unlock 합니다.

 

Why Mutexes Work

mutex를 쓰게 되면 critical section으로 묶여져 있는 공유변수, 자료구조는 mutualy exclusive 하게 사용됩니다.

따라서 unsafe 공간을 무조건 피해가게 하는 장치가 됩니다.