Shared Variables?
: 여러 thread가 x라는 instance를 참조할 때(global이든, local이든 상관 x)
: 변수의 실제 값이 저장된 메모리 공간에 접근할 때
- thread의 memory model?
- 어떤 방식으로 share?
- 실제 메모리에 어떻게 변수 인스턴스가 mapping?
Threads Memory Model: Conceptual
- 여러 thread는 하나의 process 내에서 run
- e.g shared code, data, heap, kernel context(files, installed handlers) , library segments, o
- 각 thread는 its own separate thread context
- e.g. Thread ID, stack, stack pointer, PC, condition codes, GP registers
- register values : separate and protected
- stack: separate and unprotected(다른 쓰레드가 읽고 쓰기 가능)
Three Ways to Pass Thread Argument
Malloc / Free 
-> 위 예시는 malloc한곳에 array index를 넣고 해당 주소를 전달
-> Each thread receives a unique array index 
-> 위 예시는 해당 array의 주소를 전달
-> Each thread receives a unique pointer
- producer(main): pthread_create에 (malloc한) 변수 공간의 주소를 넘긴다.
- e.g. 위 예시에서는 p / &hist[i]
- consumer(thread): 해당 포인터 역참조하여 해당 connfd 값을 얻는다. 그리고 나중에 해당 주소로 직접 free시킨다.
- e.g. hist[(long)vargp] / (int)vargp --> cast후 역참조
Cast of int
- producer: pthread_create 인자로 주소가 아닌 (void)값을 넘기기
(casts an int/long to void) - e.g. (void*)i
- consumer: void* argument를 int/long 값으로 casting하기
- e.g. hist[(long)vargp]
- 숫자 한개일때(data 수가 적을때) 작동
- Each thread receives a unique array index
- Casting from long to void* and back is safe
INCORRECT: Pointer to stack slot
-> Each thread receives the same pointer, to i (in main)
-> data race 발생: 각 thread는 i로붙 unique한 배열을 못 읽을 수도 있다. - producer: producer의 stack 주소를 넘기기
- e.g. &i
- consumer: ptr 역참조
Mapping Variable Instances to Memory
Global Variables
- data segment
- function 밖에 선언되는 변수들
- Process는 any 전역변수에 대해 process는 오직 하나의 instance(메모리공간)을 가진다.
Local automatic variables
- stack semgment
- function 내에 선언되는 static이 아닌 변수들
- 각 thread는 각 지역 변수에 대해 하나의 instance를 가진다.(shared X)
Local static variables
- data segment
- function 내에 선언되는 static 변수들
- static은 해당 함수가 수행하면서는 계속 값 유지(prog이 끝날때까지)
- 함수 호출이 끝나도 메모리에 계속 존재.
- Process는 any 지역 static 변수에 대해 하나의 instance를 가진다.
errno is special
- 전역변수임에도 stack segment!!!
- 함수 밖에 선언되지만, 각 thread는 각자 instance를 가진다.
ptr: global 변수 -> 모든 쓰레드에서 접근 가능
cnt: static local 변수 -> thread 0, 1에서 접근 가능
msgs.m : automatic local 변수이나, global pointer로 모든 쓰레드에서 접근 가능
"shared variable은 해당 instance를 2개 이상의 thread에서 참조 가능할 때"
Synchronizing Threads
Critical Section
: 여러 스레드가 동시에 접근하여 공유 자원을 수정할 수 있는 코드 영역
-> race condition을 막기 위해서 critical section안의 공유되는 변수들을 manipulate 해야한다.
-> need synchronization
-> 크리티컬 섹션에 대한 상호 배제(mutual exclusion)를 보장
-> 한 번에 하나의 스레드만 크리티컬 섹션에 접근할 수 있도록 보장
Improper Synchronization
-> cnt 변수가 공유자원인데 data race 발생. 
-> cnt을 load, update, store (critical section)
- case1:
- case2: update와 store 사이에 interleaving
- case3: load와 update 사이 interleaving
- critical section이 overlap하면 문제 발생
Progress Graphs 
- 병렬 실행 중인 스레드들의 실행 상태 공간을 시각적으로 나타낸 것입니다.
- 각 축: 스레드의 순차적인 명령어 실행 순서
- 각 점: 가능한 실행 상태
- 예를 들어 (L1, S2)는 스레드 1이 L1을 완료하고 스레드 2가 S2를 완료한 상태
- trajectory(경로): 병렬 실행 중인 스레드들의 가능한 실행 순서를 나타내는 일련의 상태 전이 과정, 즉 실행 순서
- safe(=correct): unsafe region을 방문하지 않는 경로
- Synchronization 필요
(Enforce Mutually exclusive access to critical section)
- Unsafe region:
- 크리티컬 섹션(writing cnt) 내의 명령어들이 서로 섞여서 실행되는 상태 집합
How Synchronization
- Classic Solutions
- Mutex
- Semaphore
- Other approaches
- Condition Variable
- Monitor
1. Mutex
: boolean synchronization 변수(locked이거나 unlock)
- Lock(mutex)
- mutex를 아무도 lock을 잡고 있지 않으면, locked로 바꿔주고 return
- mutex가 lock 상태면(누가 사용중), unlock 될때까지 기다리기
- Unlock(mutext)
- unlocked로 바꿔주기
- mutex가 locked 일때만 call 가능(unlock -> unlock :error)
Mutex Operations in Pthreads 
Why Mutex Works (progress graph) 
- lock과 unlock operation을 이용해서 critical section의 공유자원에 상호 배타적 접근을 하게 만든다.
- lock을 하려면, unlock상태여야하므로, 만약 locked 되어있으면, 해당 쓰레드는 기다린다. 그리고 수행이 끝난 후 unlock을 하게 되면 다른 쓰레드가 lock() 함수를 return할 수 있게 되어 사용이 가능하다.
- 즉, mutex가 forbidden region 을 만든다.
- 어떤 트라젝토리도 진입할 수 없는 영역
2. Semaphore
: 0이상의 양의 정수 인 synchronization variable 'S' 가 P와 V atomic(undivisable) operation에 의해 mainpulate된다.
- P(S) Wait(S) Down(S)
- while(S가 0이면); V operation이 실행 될 때까지 suspend한다.
- S = S - 1; return;
- V(S) Signal(S) Up(S)
- S = S + 1;
- if(waiting) wake up
만약에 다른 thread가 P operation 내에서 waiting 이면, 그중 하나를 재개하다.- 재개되는 스레드의 순서는 구현에 따라 다를 수 있지만, 일반적으로 대기열의 첫 번째 스레드가 재개됩니다.
- mutexes 들과 다르게, P 실행 안하고 V만 실행 할 수도 있다!
(mutex는 무조건 lock 함수 실행 뒤에 unlock 함수 실행)
Semaphore Operations in Pthreads
Why Semaphore Works
- Unsafe section은 S가 P 실행시 suspend하지 않고 바로 실행되므로, -1이다.
- 세마포어를 사용하여 공유 변수에 대한 상호 배제 접근을 보장할 수 있습니다.
- 세마포어는 안전하지 않은 영역을 감싸는 금지 영역을 만들어 레이스 컨디션을 방지한다.
semaphore 종류
1) Binary semaphore
- range between 0 and 1
- mutex lock과 동일
- 사용 예시
- 초기값이 1인 경우 : mutex와 동일
- 초기값이 0인 경우 : 무조건 실행이 A->B 하게 됨
- 참고: s 초기값에 따라서 처음에 p를 통과할 수 있는 개수 정해진다.(s=3)
- binary semaphore > mutex
- use mutex to protect access to resource
- 자원의 사용 여부 나타내기
2) Counting semaphore
- range >=0
- 자원의 개수 나타내기
- 공유 자원의 상태를 관리하고, 다른 스레드에게 자원 사용 가능 여부를 알려준다.
- producer-consumer problem 해결
Spinlock
- process가 lock할때 suspend 되는 동안 spin한다.
- context switch가 필요없다는 장점을 가진다.
- 빨리 lock이 풀리는 경우, spinlock을 사용하면 좋다.
- multicore processor system에서만 유용하다.
Producer-Consumer Problem 
- Producer: shared buffer가 비어있을 때까지 기다린다.
- semaphore slot: 비어있는 buffer의 크기 (초기값: n)
- P(slot)하고 insert하며 n개까지 insert 가능
- Consumer: shared buffer가 적어도 하나가 채워져있을 때까지 기다린다.
- semaphore item: 채워져있는 buffer의 크기 (초기값: 0)
- P(item)하고 remove하며 채워져있는 개수만큼 remove 가능
Producer-Consumer on an n-Element Buffer
Readers-Writers Problem
- Generalization of Mutual Exclusion Problem
- Reader는 읽기만 하므로, reader와 reader는 currently 하게 running해도 된다.
- 해당 object를 접근 할 수 있는 개수 제한이 없다.
- Writer는 object에 항상 exclusive하게 접근해야한다.
Variants of Readers-Writers
- First readers-writers problem (favors readers)
- reader는 들어왔는데 writer가 수행중이면 기다리고, reader가 수행중이면 같이 수행
- writer 기다린 후 다음 차례에서 reader가 우선순위를 가져서 새치기!
- 리더가 대기 중인 상황에서는 새로운 라이터가 자원에 접근할 수 없습니다.
- 즉, 리더가 우선권을 가지며 라이터는 리더가 모두 자원을 사용한 후에야 접근할 수 있습니다.
- writer starvation 문제 발생(무한정 기다리는 문제)
- Second readers-writers problem (favors writers)
- 라이터가 대기 중인 상황에서는 새로운 리더도 자원에 접근할 수 없습니다.
- 즉, 라이터가 우선권을 가지며 라이터가 모두 자원을 사용한 후에야 리더가 접근할 수 있습니다.
Thread Safety
- thread-safe function : 동시성 쓰레드로부터 반복적으로 호출될 때 항상 정확한 결과를 만드는 함수
- thread unsafe function :
Class1: 공유변수를 보호하지 않는 함수들
[해결] P, V 동기화 연산으로 보호(overhead 발생)
Class2: 다중호출에 대해 상태 유지하는 함수들
ex) rand() thread unsafe
-> 현재 호출의 결과가 이전 '반복실행'으로부터의 중간결과에 의존하기 때문이다.
srand() 함수를 호출한 뒤 seed 값을 가져온 후, 한 쓰레드에서 rand 반복 호출한다.
그러나, 다른 쓰레드에서 srand() 호출하여, seed 값 가져온 후 rand 반복 호출 시 pssudo-random이 된다.
[해결] 호출자가 상태정보를 인자들로 전달한다. (static data 사용 X)
srand(&seed) rand_r(int * nextp)
