[sp] Synchronization: Advanced (2)

1. Thread Safety ; 쓰레드로부터 호출된 함수들은 thread-safe해야함

(1) Def: 함수가 thread-safe <=> 여러 개의 concurrent threads로부터 반복적으로 호출될 때 correct 결과를 생산

 

(2) Classesof thread-unsafe functions

 

1. 공유된 변수들을 보호하지 않는 함수 (Class 1)

 - 공유된 변수 보호 실패 (mutex lock이 걸려있지 않음)

 -> 해결 : P와 V semaphore operation을 사용하여 mutex lock을 걸어서 thread-safe하도록

 -> 동기화 operation이 코드를 느리게 함

 

2. 여러 호출에서 state를 유지하는 함수 (Class 2)

 - 여러 함수의 호출에서 지속적인 상태에 의존함 -> 이전 state를 기록해야함

ex. static state에 의존하는 랜덤 넘버 발생기

 

static unsigned int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
    next = next*1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

/* srand: set seed for rand() */
void srand(unsigned int seed)  //seed를 초기화
{
	next = seed;
}

srand : 그 전의 seed (next) 값을 잃고 새로운 next 값을 바탕으로 그 다음의 next 값을 생성

 

->해결 : argument로 state를 넘겨줌 (global state를 제거)

/* rand_r - return pseudo-random integer on 0..32767 */
int rand_r(int *nextp) //nextp를 통해 이전의 next 값을 기록
{
    *nextp = *nextp * 1103515245 + 12345;
    return (unsigned int)(*nextp/65536) % 32768;
}

결과 : seed를 유지하게 됨

 

3. static 변수에 대한 포인터를 반환하는 함수 (Class 3)

/* lock-and-copy version */
char *ctime_ts(const time_t *timep,
char *privatep)
{
    char *sharedp;
    
    P(&mutex);
    sharedp = ctime(timep); // global 변수에 대해 string으로 변환된 메모리의 주소값을 반환
    strcpy(privatep, sharedp);
    V(&mutex);
    
    return privatep;
}

ctime 호출 시점이 내가 호출하고 읽기 전에 다른 쓰레드가 ctime을 호출할 경우, 다른 쓰레드가 호출한 시점의 반환값을 읽게 됨

t1에서 ctime을 호출하고 이때 sharedp는 ctime의 return 값에 대한 메모리 주소를 가리킴

하지만 t2에서 t1이 end하는 시점에 다시 start를 하면서 ctime을 호출하고 t1이 포인터를 읽기 전에 end를 하게 되면 sharedp는 t2가 호출한 ctime의 반환값에 대한 메모리 주소를 overwrite하게 됨

 

해결1. caller가 결과를 저장하기 위한 변수의 주소를 저장하도록 함수를 변경 (caller, callee 모두 변경)

해결2. Lock-and-copy : caller에서 단순한 변경 필요하지만 메모리 free 해야함

 

 

4. thread-unsafe한 함수를 호출하는 함수들 (Class 4)

(1) thread-unsafe한 함수를 호출 : 하나의 thread-unsafe 함수를 호출하는 것은 전체 함수를 thread-unsafe하게 만듦

   -> thread-safe한 함수를 호출하도록 함수를 변경

 

2. Reentrant Functions

(1) Def: 함수가 reentrant <=> 여러 쓰레드에 의해 호출될 때 공유된 변수에 대해 access하지 않음

   -> thread-safe 함수에 대한 부분집합

        : 동기화 operation을 필요로 하지 않음

        : Class 2 함수를 thread-safe하게 만드는 유일한 방법은 reentrant (ex. rand_r)

 

 

(2) Thread-safe library functions

  - Standard C 라이브러리 안의 모든 함수들은 thread-safe

   ex) malloc, free, printf, scanf  (ass x , thread-safe  -> reentrant x)

 

  - 대부분의 unix 시스템 호출은 몇몇의 예외를 제외하고 thread-safe함

 

- 문제점 : Races

프로그램의 정확성이 다른 쓰레드가 y점에 도달하기 전에 x 점에 도달하는 하나의 쓰레드에 의존할 경우 발생

 

/* A threaded program with a race */
int main()
{
    pthread_t tid[N];
    int i; //N 쓰레드가 공유하는 i
    for (i = 0; i < N; i++)
    	Pthread_create(&tid[i], NULL, thread, &i); //각 쓰레드가 같은 i에 접근 가능
        
    for (i = 0; i < N; i++)
    	Pthread_join(tid[i], NULL);
        
    exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
    int myid = *((int *)vargp); 
    printf("Hello from thread %d\n", myid);
    return NULL;
}

 

쓰레드 간의 race가 존재함

main 쓰레드는 i를 write, peer thread는 i를 read하게 되는데 

둘이 같이 접근하게 되면서 main은 i를 1로 증가시키지만 peer thread 0은 i가 0으로 유지하게 되면서 race를 하게 됨

즉 0을 찍으려는 순간에 1이 찍히게 됨

 

 

- i가 0인 동안에 deref가 발생하는 것은 ok

하지만 그렇지 않은 경우엔 잘못된 id 값을 갖게 됨

 

 

- Race test

//Main thread

int i;
for (i = 0; i < 100; i++) {
	Pthread_create(&tid, NULL, thread, &i);
}

// Peer Thread
void *thread(void *vargp) {
    Pthread_detach(pthread_self());
    int i = *((int *)vargp);
    save_value(i);
    return NULL;
}

 

race가 없다면, 각 쓰레드는 다른 i의 값을 갖게 됨

저장된 값의 집합은 0~99 사이의 복제본을 포함함

 

 

- Experimental Results

한 번도 찍히지 않는 구간이 있음 -> race 존재함

 

-> Race 제거

/* Threaded program without the race */
int main()
{
    pthread_t tid[N];
    int i, *ptr;
    
    for (i = 0; i < N; i++) {
        ptr = Malloc(sizeof(int)); 
        *ptr = i; 
        Pthread_create(&tid[i], NULL, thread, ptr); 
        //각 쓰레드는 각자 다른 메모리를 참조하게 됨
	}
    
    for (i = 0; i < N; i++)
    	Pthread_join(tid[i], NULL);
    exit(0);
}
/* Thread routine */

void *thread(void *vargp)
{
    int myid = *((int *)vargp);
    Free(vargp);
    printf("Hello from thread %d\n", myid);
    return NULL;
}

//각 쓰레드는 각자 다른 메모리를 참조하게 됨

 

- 문제점 : Deadlock

 프로세스가 deadlocked <=> 절대 true가 되지 않을 조건을 wait함

 

 

t1은 A를, t2는 B를 갖고 있으면서 각자 B와 A를 wait

하지만 B와 A를 얻으려면 t1과 t2에 있는 A와 B를 해제해야함

따라서 계속 wait하는 상태

 

int main()
{
    pthread_t tid[2];
    Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */
    Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */
    Pthread_create(&tid[0], NULL, count, (void*) 0);
    Pthread_create(&tid[1], NULL, count, (void*) 1);
    Pthread_join(tid[0], NULL);
    Pthread_join(tid[1], NULL);
    printf("cnt=%d\n", cnt);
    exit(0);
}

void *count(void *vargp)
{
    int i;
    int id = (int) vargp;
    for (i = 0; i < NITERS; i++) {
        P(&mutex[id]); P(&mutex[1-id]);
        cnt++;
        V(&mutex[id]); V(&mutex[1-id]);
    }
    return NULL;
}

s0과 s1의 lock이 풀리는 시점이 다르므로 deadlock 상태에 빠지게 됨

 

- Deadlock Visualized in Progess Graph

 

locking은 deadlock을 발생시킬 수 있음 : 계속 wait하게 됨

 

Deadlock 지점에 들어가는 trajectory는 결국 deadlock 상태에 진입하게 되고, 각 s0과 s1이 0이 아니게 되는 것을 기다림

다른 trajectory는 lock을 해제하고 deadlock 지역을 벗어남

단점: Deadlock은 종종 비결정적 (race)

 

- Deadlock 해결

int main() 
{
    pthread_t tid[2];
    Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */
    Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */
    Pthread_create(&tid[0], NULL, count, (void*) 0);
    Pthread_create(&tid[1], NULL, count, (void*) 1);
    Pthread_join(tid[0], NULL);
    Pthread_join(tid[1], NULL);
    printf("cnt=%d\n", cnt);
    exit(0);
}

void *count(void *vargp) 
{
    int i;
    int id = (int) vargp;
    for (i = 0; i < NITERS; i++) {
        P(&mutex[0]); P(&mutex[1]);
        cnt++;
        V(&mutex[id]); V(&mutex[1-id]);
    }
    return NULL;
}

같은 순서로 resource들을 공유

 

 

- Avoided Deadlock in progree graph

 

trajectory에 갇힐 일이 없음

프로세스는 같은 순서로 lock됨

 

잠금이 해제되는 순서가 중요치 않음