Synchronization: Basics

※ Shared Variables in Threaded C Program

 

Question : Threaded C 프로그램에서 공유되는 변수는 무엇인가?

• "global variables are shared" 및 "stack variables are private" 처럼 간단한 질문이 아니다.

Define : 변수 x는 여러 스레드가 x의 일부 인스턴스를 참조하는 경우에만 공유된다.

다음 질문에 대한 답변이 필요하다.

• 스레드의 메모리 모델은 무엇인가?
• 변수의 인스턴스는 어떻게 메모리에 매핑되는가?
• 이러한 각 인스턴스를 참조할 수 있는 스레드는 몇 개인가?

 

※ Threads Memory Model

 

Conceptual model :

• 단일 프로세스의 컨텍스트 내에서 여러 스레드가 실행됨
• 각 스레드에는 고유한 개별 스레드 컨텍스트가 있다.
  
  • Thread ID, stack, stack pointer, PC, condition codes, and GP registers
• 모든 스레드가 나머지 프로세스 컨텍스트를 공유한다.
  
  • Code, data, heap, and shared library segments of the process virtual address space
  • Open files and installed handlers

그러나 작동상 위와 같은 모델은 엄격하게 시행되지 않는다.

• 레지스터 값은 실제로 분리되어 보호되지만 … ?
• 모든 스레드는 다른 스레드의 스택을 읽고 쓸 수 있다.

 

즉, 개념 모델과 운영 모델 간의 불일치는 혼란과 오류의 원인이 된다.

 

 

※ Example Program to illustrate Sharing

 

#include "csapp.h"
#define N 2
void *thread(void *vargp);

char **ptr;  /* Global variable */ //line:conc:sharing:ptrdec

int main()
{
    int i;
    pthread_t tid;
    char *msgs[N] = {
        "Hello from foo",
        "Hello from bar"
    };

    ptr = msgs;
    for (i = 0; i < N; i++)
        Pthread_create(&tid, NULL, thread, (void *)i);
    Pthread_exit(NULL);
}

void *thread(void *vargp)
{
    int myid = (int)vargp;
    static int cnt = 0; //line:conc:sharing:cntdec
    printf("[%d]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt); //line:conc:sharing:stack
    return NULL;
}

 

 

위 코드는 main 쓰레드를 제외한 만들어진 두 쓰레드가 main 쓰레드의 로컬 변수 msgs 를 접근하고 있는 상태이다.

즉, 쓰레드 별로 스택을 고유하게 가져야 하는게 conceptual model 이였다면 이를 깨뜨리는 상황이 위와 같은 코드이다.

그리고 순서가 다르게 나오는 것으로 보아 쓰레드가 먼저 생성되었다 하더라도 먼저 실행되지 않는 것을 짐작할 수 있다.

 

 

※ Mapping Variable Instances to Memory

 

Global variables

• 정의: 함수 외부에 선언된 변수
• 가상 메모리에는 모든 글로벌 변수의 인스턴스가 정확히 하나 포함되어 있다.

Local variables

• 정의: static 속성이 없는 내부 함수로 선언된 변수
• 각 스레드 스택에는 각 로컬 변수의 인스턴스 하나가 포함된다.

Local static variables

• 정의: static 속성을 가진 내부 함수로 선언된 변수
• 가상 메모리에는 모든 로컬 정적 변수의 인스턴스가 정확히 한 개 포함되어 있다.

 

전역 변수, 지역 변수, 지역 정적 변수를 위 코드를 통해 분리한다면 다음과 같다.

• 전역 변수 : ptr [area : data]
• 지역 변수 : i.m, msgs.m, myid.p0, myid.p1 (m : main thread / p0, p1 : thread 0, 1) [area : stack]
• 지역 정적 변수 : cnt [area : data]

 

※ Shared Variables Analysis

 

 

Answer : 여러 쓰레드가 하나 이상의 x 인스턴스를 참조하는 경우 변수 x가 공유된다. 

• ptr, cnt 및 msg가 공유됨
• i와 myid가 공유되지 않음

이때, 유심히 봐야 할 부분은 cnt, msgs.m 이다.

 

① cnt : thread 함수 내에서 정의된 로컬 정적 변수로 해당 코드 블럭 내에서만 lifetime 이 유효하며 data 영역으로 단 하나가 생성된 것이다.

그래서 만들어진 thread 0, 1 은 thread 함수 내에서 실행되기 때문에 data 영역에 존재하는 cnt 값을 공유하면서 값을 변경시킬 수 있으며 main 쓰레드 같은 경우는 thread 함수 내에 존재하지 않기 때문에 참조가 불가능하다.

 

② msgs.m : 전역 변수인 ptr 를 통해서 main 함수에서 ptr = msgs 를 하였다.

이때, 쓰레드가 생성될 경우 전역 변수인 ptr 를 공유하기 때문에 ptr 를 통해서 main 쓰레드에 존재하는 지역변수 msgs 가 indirection 이 일어나게 된다.

즉, 만들어진 thread 0, 1 은 main 쓰레드의 msgs 변수를 reference 한다고 볼 수 있다.

 

 

그렇다면 main() 에서 로컬 정적 변수가 있을 경우 다른 쓰레드에서 접근 가능한가?

 

다음과 같이 간단한 코드를 만들어서 컴파일 해봤다.

#include "csapp.h"
#define N 2
void *thread(void *vargp);

int main()
{
    int i;
    pthread_t tid;
    static int cnt = 0;

    for (i = 0; i < N; i++)
        Pthread_create(&tid, NULL, thread, (void *)i);
    Pthread_exit(NULL);
}

void *thread(void *vargp)
{
    int myid = (int)vargp;
    printf("[%d] : (cnt=%d)\n", myid, ++cnt); //line:conc:sharing:stack
    return NULL;
}

 

 

당연한 결과지만, 쓰레드 내에 변수 선언이 되어있지 않아서 컴파일이 되지 않는다.

상식적으로 main() 에서 로컬 정적 변수가 선언되어 있으면 main 스택에 cnt 라는 변수가 존재하게 되며 생성된 thread 0, 1 의 스택영역에 로컬 변수는 myid 밖에 없으므로 lifetime 이 유효해 보일지라도 비선언 에러 문구가 뜨게 된다.

 

 

※ Synchronizing Threads

 

공유 변수는 편리하다.

하지만 심각한 동기화 오류의 가능성을 제기한다.

동기화가 부적절하게 일어나는 코드를 살펴보도록 하자.

#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0; /* Counter */

int main(int argc, char **argv)
{
    long niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) {
        printf("usage: %s <niters>\n", argv[0]);
        exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    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++) //line:conc:badcnt:beginloop
        cnt++;                   //line:conc:badcnt:endloop

    return NULL;
}

 

 

두 쓰레드를 생성하여 공유되는 전역 변수 cnt 값을 인자값만큼 카운팅하여 결과가 제대로 나오는지를 확인하였다.

즉, 인자값이 niters 라고 할 경우 두 쓰레드를 생성한다면 cnt 값이 (2 * niters) 이 되어야 하는데 이상하게 다른 결과가 나타나게 되는 것이다.

이러한 현상을 동기화가 부적절하게 일어났다고 말할 수 있다.

 

 

※ Assembly Code for Counter Loop

 

 

어셈블리 코드는 총 5개로 Head, Load, Update, Store, Tail 이 존재한다.

그 중에서 유심히 봐야 할 것은 cnt++ 을 하는 Load, Update, Store 이다.

 

돌발질문 : atomic 이란 무엇인가?

 

atomic 이란 원자성이라는 의미를 가지며 쪼개질 수 없는 operation 을 의미한다.

예를 들어서 cnt++ 에 대한 operation 은 c 언어로 볼 때 atomic 하게 보일 수 있다.

그러나 위와 같이 어셈블리 코드로 변환하게 될 경우 cnt++ 에 대한 operation 은 Load, Update, Store 3 단계를 걸쳐서 일어나게 되므로 atomic 하지 않다고 볼 수 있다.

 

 

※ Concurrent Execution

 

Key idea : 일반적으로, 순차적으로 일관된 인터리빙은 가능하지만, 일부는 예상치 못한 결과를 제공한다.

• \(I_{i}\) 는 스레드 i가 명령 I을 실행함을 나타낸다.
• \(%rdx_{i}\) 는 스레드 i의 컨텍스트에서 %rdx의 내용이다.

 

 

thread 1이 HLUS 명령어를 실행하고 T를 실행하기 전에 thread 2 가 인터리빙한 경우이다.

이 경우는 thread 1이 cnt++ 에 대한 작업을 원활하게 하였기 때문에 문제가 발생하지 않는다.

 

Incorrect ordering : 두 개의 스레드가 카운터를 증가시키지만 결과는 2가 아니라 1 이다.

 

 

cnt++ 의 작업을 처리하는 세 가지 명령어 LUS 를 실행하는 도중에 인터리빙된 경우 예기치 못한 결과가 나타난다.

그래서 이러한 예기치 못한 결과를 방지하기 위해 progress graph 를 사용해서 행동을 분석할 수 있다.

 

 

※ Progress Graph

 

 

Progress Graph 는 동시 스레드의 이산 실행 상태 공간을 나타낸다.

각 축은 스레드의 명령 순서와 일치한다.

각 점은 가능한 실행 상태(\(Inst_{1}\), \(Inst_{2}\))에 해당한다.

예를 들어, (\(L_{1}\), \(S_{2}\))는 스레드 1이 \(L_{1}\)을 완료하고 스레드 2가 \(S_{2}\)를 완료한 상태를 나타낸다.

 

 

※ Trajectories(궤적) in Progress Graph

 

 

Trajectory 는 스레드의 가능한 동시 실행을 설명하는 일련의 법적 상태 전환이다.

예: H1, L1, U1, H2, L2, S1, T1, U2, S2, T2

 

 

※ Critical Sections and Unsafe Regions

 

 

L, U 및 S는 공유 변수 cnt와 관련하여 critical section 을 형성한다.

critical section 의 지침(일부 공유 변수 작성)은 인터리브하면 안된다.

이러한 인터리브가 발생하는 상태 집합을 unsafe regions 라고 부른다.

 

 

Def : 궤적이 안전하지 않은 영역에 들어가지 않는 경우 안전하다.

Claim : 궤적이 안전할 경우 올바르다.

 

 

※ Enforcing Mutual Exclusion

 

Question : 어떻게 하면 안전한 궤적을 보장할 수 있을까?

Answer : 우리는 스레드의 실행을 동기화해서 스레드들이 결코 안전하지 않은 궤적을 가질 수 없도록 해야 한다.

• 즉, 각 critical section에 대해 상호 배타적 접근을 보장할 필요가 있다.

Classic solution 

• Semaphores (Edsger Dijkstra)

기타 접근 방식

• Mutex 및 condition variables (Pthread)
• Monitors (Java)

 

※ Semaphores

 

Semaphore : 음이 아닌 전역 정수 동기화 변수이며 P, V 작업에 의해 조작된다.

P(s) :

• s가 0이 아니면 1만큼 감소하고 즉시 반환된다.
  
  • 테스트 및 감소 작업은 atomically(indivisibly) 하게 발생한다.
• s가 0이면 s가 0이 아닌 상태가 되고 V 작업에 의해 스레드가 다시 시작될 때까지 스레드를 일시 중단한다.
• 재시작 후, P 작업은 감소하여 호출자에게 제어를 반환한다.

V(s) :

• 1씩 증가한다.
• 증가 작업이 atomically(indivisibly) 하게 발생한다.
• s가 0이 되기를 기다리는 P 작업에서 차단된 스레드가 있는 경우, 해당 스레드 중 하나를 정확히 다시 시작한 다음 감소하여 P 작업을 완료한다.

세마포어 불변량: (s > = 0)

 

여기서 의문인 부분이 있다.

P(s) 에서 s 값이 0 인지 아닌지를 test 하고 만약 0 이 아닐 경우 decrement 하는 operation 을 고려해보자.

 

이러한 operation 은 test + decrement 으로 두 가지 연산을 수행하는데 왜 atomic 하나요?

 

test 하고 decrement 하는 작업을 CPU 설계자가 hardware instruction 을 제공한다고 한다.

이러한 instruction 을 Compare-And-Swap 이라고 부르며 그만큼 CPU cycle 이 많이 필요하다.

Lock based Data Structure (tistory.com) , 작년 운영체제 시간에서 Compare-And-Swap 에 대한걸 배웠는데 리마인드하게 되어서 좋았다.

 

 

※ C Semaphore Operations

 

Pthreads functions : 

#include <semaphore.h>

int sem_init(sem_t *s, 0, unsigned int val); /* s = val */
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */

 

sem_wait() 함수는 Lock(acquire) 을 하는 용도고 sem_post() 함수는 Unlock(release) 을 하는 용도로 이해하면 좋을 것 같다.

그럼 부적절하게 동기화작업이 일어나는 코드를 살펴보도록 하자.

#include "csapp.h"

void *thread(void *vargp);  /* Thread routine prototype */

/* Global shared variable */
volatile long cnt = 0; /* Counter */

int main(int argc, char **argv)
{
    long niters;
    pthread_t tid1, tid2;

    /* Check input argument */
    if (argc != 2) {
        printf("usage: %s <niters>\n", argv[0]);
        exit(0);
    }
    niters = atoi(argv[1]);

    /* Create threads and wait for them to finish */
    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++) //line:conc:badcnt:beginloop
        cnt++;                   //line:conc:badcnt:endloop

    return NULL;
}

 

critical section 으로 cnt++ 을 하는 operation 은 atomic 하게 보일지라도 그렇지 않다.

register 를 Load 하고 Update 하고 Store 즉, 3 가지 operation 을 하므로 atomic 하지 않다.

 

그러면 이를 해결하기 위해서 어떻게 해야 할까?

 

정답은 critical section 에 단 하나의 쓰레드만 접근할 수 있도록 해야 한다.

다음과 같이 코드를 수정해보자.

sem_t mutex;

int main(int argc, char **argv)
{
	...
	Sem_init(&mutex, 0, 1);
	...
}

void *thread(void *vargp)
{
    long i, niters = *((long *)vargp);

    for (i = 0; i < niters; i++) {
    	P(&mutex);
        cnt++;
        V(&mutex);
    }

    return NULL;
}

 

 

 

여러 쓰레드들은 전역변수로 선언된 sem_t 타입의 mutex 를 공유하고 있는 상태다.

mutex 를 통해 P, V operation 을 함으로써 여러 쓰레드들이 해당 mutex 의 값을 decrement, increment 작업을 하며 실행되고 있음을 짐작할 수 있다.

 

thread 1 이 P operation 을 수행한 후에 critical section 에 해당하는 operation 을 수행한다고 가정해보자.

1. P operation 으로 인해 mutex 의 값은 1 에서 0 으로 decrement 가 된 상태다.
2. Context switch 가 일어나서 thread 2 가 수행되고 바로 P operation 을 수행한다.
3.  mutex 의 값이 0 이기 때문에 thread 2 는 wait 상태가 되고 context switch 가 다시 일어나게 된다.
4. thread 1 이 critical section 에 남아 있던 operation 을 마저 수행하고 V operation 을 수행한 다음에 또 다시 context switch 가 일어나게 된다.
5. mutex 값은 1 이 되고 wait 상태였던 thread 2 는 thread 1 에서 V operation 을 통해 wake up 을 하게 된다.
6. thread 2 는 P operation 을 수행하려고 했는데 이번엔 mutex 값이 1 이므로 정상적으로 mutex 값을 decrement 하면서 critical section 에 도달하게 된다.

이러한 메커니즘으로 적절하게 동기화 작업이 일어나는 것을 알 수 있다.

 

 

세마포어의 P 및 V 작업을 통해 critical section 을 둘러싸서 공유 변수에 대한 상호 배타적 접근을 제공한다. (처음에는 1로 설정됨)

세마포어 불변성(s >= 0)은 안전하지 않은 영역을 둘러싸고 어떤 궤적으로도 들어갈 수 없는 금지된 영역을 만든다.