[sp] Synchronization: Basics

1. Shared Variables in Threaded C Programs

(1) shared <=> 여러 개의 thread가 x의 몇 instance를 reference

 

2. Threads Memory Model

(1) 여러 개의 스레드는 하나의 프로세스의 context에서 수행됨

(thread는 execute flow)

(2) 각 스레드는 각자의 분리된 스레드 context가 있음 : Thread ID, stack, stack pointer, PC, condition codes, and GP registers

(3) 모든 스레드는 remaining process context를 공유

 - code, data, heap, process의 가상 주소 공간의 shared library segments 

 - open 파일과 설치된 handlers

 

(4) 레지스터 값은 분리되고 보호되어있어서 원칙적으로 서로 reference할 수 없음

하지만, 스레드는 다른 스레드의 스택을 read, write할 수 있음

 

char **ptr; /* global var */
int main()
{
    long i;
    pthread_t tid;
    char *msgs[2] = {
    "Hello from foo",
    "Hello from bar"
    };
    // main 스레드의 local 변수로 스택에 저장
    
    ptr = msgs; // 글로벌 변수로 로컬 변수 접근
    for (i = 0; i < 2; i++)
    	Pthread_create(&tid, NULL, thread, (void *)i); // 스레드 생성
    Pthread_exit(NULL);
}
void *thread(void *vargp)
{
    long myid = (long)vargp;
    static int cnt = 0;  // static -> data 영역에 할당
    // 또다른 스레드도 cnt를 공유, thread 함수 안에서만 생존
    printf("[%ld]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt);
    // thread 실행히 ptr[myid]를 통해 main 스레드의 local 변수에 접근
    return NULL;
}

peer 스레드는 메인 스레드 스택을 글로벌 변수인 ptr을 통해 indirect하게 reference

 

 

3. 변수 instance를 메모리로 맵핑

(1) 글로벌 변수

 - 함수 밖에서 선언

 - 가상 메모리는 글로벌 변수 하나의 instance를 포함

 

(2) 로컬 변수

 - static attribute 없이 함수 안에서 선언

 - 각 스레드 스택은 각 로컬 변수 하나의 instance를 포함

 - 프로세스 안에서 동일한 이름의 local 변수가 여러 개 있음

 - 스레드 여러개를 실행 -> 각 스레드마다 각 스택의 자신의 로컬 변수가 있음 => 중복된 로컬 변수 여러개가 있을 수 있음 (스레드 스택 안에선 한개)

 

(3) 로컬 static 변수

 - static attribute을 가지며 함수 안에서 선언

 - 가상 메모리는 local static 변수의 하나의 instance를 가짐

 

char **ptr; /* global var */
int main()
{
	pthread_t tid;
    // 로컬 변수로 메인 스레드 스택의 변수 (i.m, msgs.m)
    long i;
    char *msgs[2] = {
    "Hello from foo",
    "Hello from bar"
	};
    //
    ptr = msgs;
    for (i = 0; i < 2; i++)
        Pthread_create(&tid, NULL, thread, (void *)i);
    Pthread_exit(NULL);
}
void *thread(void *vargp)
{
    long myid = (long)vargp; // 2개의 instance (myid.p0 - peer 스레드 0의 스택 변수, myid.p1 - peer 스레드 1의 스택 변수)
    static int cnt = 0; // cnt는 data 영역의 변수로 peer 스레드 서로 공유
    printf("[%ld]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt);
    return NULL;
}

 

(4) Shared variable analysis

- ptr : data segment, 모든 스레드가 공유 -> shared

- cnt : data segment, peer 스레드끼리 공유 -> shared

- i.m : main stack, shared x

- msgs.m : indirection , 모든 스레드가 공유 -> shared

- myid.p0, myid.p1 : shared x

 

-> 변수 x가 shared <=> 여러 스레드는 최소 하나의 x의 instance를 refenrence

따라서 ptr, cnt, msgs는 shared

i, myid는 not shared

 

(5) Synchronization

bad

/* Global shared variable */
volatile long cnt = 0; /* Counter */
// 스레드 0,1에 접근, 실제 메인 메모리에 직접 store, load
int main(int argc, char **argv)
{
    long niters;
    pthread_t tid1, tid2;
    
    niters = atoi(argv[1]);
    //스레드 생성
    Pthread_create(&tid1, NULL, thread, &niters);
    Pthread_create(&tid2, NULL, thread, &niters);
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);
    
    /* Check result */
    if (cnt != (2 * niters))
    	printf("BOOM! cnt=%ld\n", cnt);
    else
    	printf("OK cnt=%ld\n", cnt);
    exit(0);
}

/* Thread routine */
void *thread(void *vargp) 
{ 
    long i, niters = *((long *)vargp); 
    for (i = 0; i < niters; i++)
    	cnt++; 
    return NULL; 
}

cnt는 20000이 되어야 함

 

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

->

 

(6) Concurrent Execution

 : 일반적으로 순차적으로 일관된 interleaving은 가능하지만, 예상치 못한 결과를 발생

  - Ii는 스레드 i가 I 명령어를 실행함을 의미

  - %rdxi는 스레드의 i context에서 %rdx의 content

스레드 1에서 store하면서 cnt가 1 증가

스레드 1의 cs안에서 타이머 인터럽트가 걸리고 스레드 2번으로 context switch

스레드 2의 cs를 빠져나오고 tail에서 cnt가 2로 증가 후 context switch되면서 스레드 1로 변경

 

Load: cnt -> 레지스터에 저장

Update: 레지스터의 저장된 값을 1 증가 시켜서 기존 레지스터에 update

Store: 레지스터 값을 cnt에 저장

// cnt++;

 

 

- 부적절한 ordering : 두 개의 스레드는 counter를 증가시키지만, 결과는 2대신 1

critical section이 interleaving되면 원하는 결과가 나올 수 없음

 

 

 

(7) Progress graph : concurrent한 스레드들의 개별 execution state space을 표현

 - 각 축은 스레드에서 inst들의 순차적인 순서와 일치

 - 각 점들은 가능한 execution state(Inst1, Inst2)와 일치

 - (L1, S1)은 스레드 1이 L1을 완료했고 스레드 2가 S2를 완료했음을 의미

 - trajectory는 스레드의 가능한 concurrent execution 하나를 묘사하는 legal transitions의 sequence

ex. H1, L1, U1, H2, L2, S1, T1, U2, S2, T2

 

 - L, U ,S는 shared 변수 cnt에 대한 critical section을 형성

 - CS의 insts는 interleaving될 수 없음!

 - interleaving이 발생한 state의 집합들은 unsafe region을 형성

 

 

- trajectory가 safe <=> unsafe region에 들어가지 않음

- trajectory가 correct <=> sage

 

3. Enforcing Mutual Exclusion (synchronize thread)

 - 어떻게 safe trajectory를 보장? -> 스레드의 execution을 synchronize => unsafe trajectory를 절대로 가지지 않음

 : 각 cs에 대해 mutually exclusive access를 보장해야함

 

(1) solution : Semaphores , Mutex & condition variables (Pthreads), Monitors

 

(2) Semaphores

 - non-negative global integer synchronization variable (0 이상)

 -> P와 V operation에 의해 조작

 

 - P(s)

 : s가 0이 아니면, s를 1 감소하고 즉시 리턴 -> atomical하게 test와 감소 operation이 발생 (indivisibly)

 : s가 0이면, s가 0이 아니고 스레드가 V에 의해 다시 시작할 때까지 (wake) 스레드를 suspend (sleep)

 : wake후, P operation이 s를 감소시키고 호출자에 대한 control을 리턴\

 

- V(s)

 : s를 1 증가 -> 증가 operation은 atomical하게 발생

 : s가 0이 아니게 될 때까지 wait하면서 P operation에서 block된 스레드가 있으면, 그 중 하나의 스레드를 wake하고, s를 감소하면서 P operation을 완성

 

- semaphore는 invariant (s>=0)

cs는 lock을 잡은 하나의 스레드만 들어갈 수 있음

이때 s = 0이 되고 다른 스레드가 cs에 들어가려고 하면 sleep됨

들어간 스레드가 cs에서 나와서 s = 1로 증가시키고 V(s)를 수행하면 다른 스레드를 깨워서 같은 과정을 반복

 

(3) C Semephore Operations

 

(4) Using  Semaphores for Mutual Exclusion

 - Basic idea

 : 1로 초기화된 semaphore mutex와 공유된 각 변수 (또는 공유된 변수의 관련 집합)와 연결

 : P(mutex) 와 V(mutex) operation으로 해당 cs을 둘러

 

- Terminology

 : binary semaphore - 값이 항상 0 또는 1

 : Mutex - mutual exclusion에 사용된 binary semaphore

  - P operation : 뮤텍스를 locking

  - V operation : 뮤텍스를 unlocking / releasing

  - "Holding" mutex : lock돼 있거나 아직 unlock되지 않은 상태 , cs 안에 들어가 있음

  - Counting semaphore : 카운터로서 허용가능한 resource의 세트에 사용

 

(5) Proper Synchronization

 - 공유된 변수 cnt에 대해 mutex를 정의 및 초기화

volatile long cnt = 0; /* Counter */
sem_t mutex; /* Semaphore that protects cnt */

Sem_init(&mutex, 0, 1); /* mutex = 1 */

 

 - P와 V로 CS를 둘러쌈

for (i = 0; i < niters; i++) {
    P(&mutex);
    cnt++; // cs를 보호 -> automically execute -> interleaving x
    V(&mutex);
}

단 bad 경우보다 느려짐