ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Pintos] 동기화(Synchronization) - Semaphores, Locks, Monitors, Optimization Barriers
    프로젝트/Pintos 2021. 3. 31. 11:37
    반응형

    스레드(Thread)

    쓰레드는 프로세스 내에서 실행되는 흐름의 단위를 말한다. 환경에 따라 하나의 프로세스 내에서 두 개 이상의 쓰레드가 실행될 수 있는데 이를 멀티스레드(multithread) 라고 한다. 멀티 쓰레드는 멀티 프로세스와 여러 작업이 동시에 이루어 진다는 공통점이 있지만, 멀티 프로세스에서 각 프로세스는 독립적으로 실행되며 각 프로세스는 별개의 메모리 공간을 차지하는 반면 멀티 스레드는 프로세스 내의 메모리를 공유하여 사용할 수 있다는 차이점이 존재하며 이러한 자원을 공유하는 특성 때문에 pintos 의 스레드 설계는 스레드간의 동기화(Synchronization) 에 신경을 써야한다. 이 포스트는 pintos 의 동기화에 사용될 수 있는 여러 방법들을 소개한다.

     

     

    Disabling Interrupts

    커널의 스케쥴링 방식에 따라 커널 스레드가 CPU 를 사용하고 있을 때 다른 스레드에 의해 CPU 의 사용을 선점(preemption) 당할 수 있는지의 여부가 달라진다. Pintos 는 커널 스레드가 언제든 선점당할 수 있는 Preemptible kernel 이다.(Non-preemtible kernel 에서는 스레드가 CPU 의 사용권을 다른 스레드에게 이양한 후에야 다른 스레드가 그 CPU 를 사용할 수 있다.)

    Interrupt 를 비활성화 하는 것만으로 synchronization 을 실현할 수 있다. thread preemption 은 timer interrupt 에 의해 일어나기 때문에 interrupt 자체를 막아버리는 것이다. 이 방법은 external interrupt handlers 를 동기화시키기 위해 주로 사용되는데, external interrupt 는 프로그램 내부에서 발생하는 interrupt 와 다르게 외부에서 발생하는 interrupt 로, sleep 이 불가하기 때문에 다른 동기화 도구가 사용될 수 없고 가장 우선적으로 처리되어야 하기 때문에 외부 인터럽트가 실행되는 동안은 다른 모든 interrupt 를 비활성화한다.

    <thread/interrupt.h> 에 interrupt 들을 활성/비활성 할 수 있는 Type, function 들이 있다.

     

    Semaphores

    멀티 스레드 프로그램에서는 여러 스레드가 메모리 등의 자원을 공유하게 되고 여러 스레드에 의해 공유되어 사용되는 자원을 공유자원이라고 한다. 각 스레드에서 이 공유자원을 엑세스 하는 코드구역을 임계구역(Critical Section) 이라고 하며, 같은 공유 데이터를 여러 스레드에서 동시에 접근하면 시간차이로 인한 잘못된 결과로 이어질 수 있기 때문에 하나의 스레드가 임계구역에 들어가 있다면 다른 스레드들은 임계구역에 접근하는 것을 제한하여야 한다.

     

    세마포(Semaphores) 는 공유자원을 여러 스레드가 동시에 접근하지 못하도록 하는 도구로 하나의 nonnegative integer 와 두 개의 operators 로 이루어진다. nonnegative integer 는 사용 가능한 공유자원의 개수를 의미한다. 이 값이 2 라면 2개의 스레드가 동시에 접근 가능하고, 이 값이 0 이라면 사용 가능한 공유자원이 없음을 의미한다. 이 수는 다른 방식으로는 조작할 수 없고 오직 아래 두 개의 operator 로만 조작이 가능하다.

    • "Down"(or "P") : 어떤 스레드가 임계구역으로 들어와서 공유자원을 사용하고자 요청할 때 실행되고, 현재 사용 가능한 공유자원의 개수가 1개 이상이면(양수개이면) 이 수를 1 줄이고 임계구역을 실행한다.(공유자원을 사용한다.) 만약 현재 사용 가능한 공유자원의 개수가 0 이하면 이 값이 양수가 될 때까지 임계구역을 실행하지 않고 기다린다.
    • "Up"(or "V") : 스레드가 임계구역의 실행을 모두 마치고 공유자원을 반납할 때 실행된다. 사용 가능한 공유자원의 개수를 1 늘린다.

     

    세마포는 초기화 값에 따라 그 용도가 달라질 수 있다. 우선, 특정 스레드가 단 한번 일어나는 다른 event 가 끝나길 기다려야 하는 경우 0 으로 초기화 된 세마포를 사용한다. 예를 들어, 스레드 A 가 진행 중에 스레드 B 를 시작하고 A 는 B 가 특정 작업을 끝내길 기다려야 하는 경우가 있다.

    스레드 A 에서는 0 으로 초기화 한 세마포 S 를 만든 후 스레드 B 를 시작하면서 이 세마포를 함께 넘겨준 후 Down(S) 을 한다. 이 때, 현재 S.value 값이 0 이므로 스레드 A 는 block() 되어 기다리고, 스레드 B 는 특정 Event 를 수행한다. 이후 B 가 Event 를 끝내고 Up(S) 을 호출하면 S.value 값이 1이 되어 스레드 A 의 block() 이 풀리고, A 의 Down 으로 인해 바로 다시 S.value 값은 0 으로 되고 A 의 작업을 이어간다. 이 경우 스레드 A 의 start B 후 Down(S) 가 실행되기 전에 B 의 작업이 모두 끝나고 Up(S) 이 먼저 실행될 수 있지만, Down 에서 A 가 block 되지 않고 바로 진행된다는 점만 다를 뿐 세마포는 의도한 대로 작동한다.

     

    하나의 공유자원에 접근을 제어할 때는 1 로 초기화된 세마포를 사용한다. 스레드 A 가 공유자원을 사용하기 전에 "Down" 을 하면 A 가 우선 실행되고 도중에 공유자원에 접근하는 다른 스레드들은 A 가 "Up" 을 호출하기 전까지 대기한다.

     

    1 이상으로 초기화된 세마포는 여러 개의 공유자원을 사용하는 경우를 나타내지만 거의 사용되지 않는다.

     

    세마포의 값이 0 으로 초기화 된 경우와 1 로 초기화 되는 경우가 헷갈리는 경우 다음과 같이 생각하면 될 것 같다.

    • 0 으로 초기화 되는 경우 : 스레드 A 가 우선 기다림 -> 스레드 B 의 작업이 끝나면 A 가 실행
    • 1 로 초기화 되는 경우 : 스레드 A 가 우선 실행됨 -> A 의 작업이 끝나면 기다리던 B 가 실행 

    세마포의 구조는 <threads/synch.h> 에 구현되어 있다. 세마포는 공유자원이 반환되기를 기다리며 block 되어 있는 waiting threads 의 list 를 <lib/kernel/list.c> 에 구현되어 있는 linked list 를 사용하여 저장한다. 아래는 pintos 에 구현되어 있는 세마포의 코드를 간단히 나타낸 것이다.

    void down(S){
        if(S.value == 0){
        	add this thread to S.list
            block();
        }
        S.value--;
    }
    
    void up(S){
        if(S.list is not empty){
        	remove this thread to S.list
            wakeUp(P)
        }
        S.value++;
    }

     

    Locks

    lock 도 마찬가지로 공유자원을 관리하는 동기화도구 중 하나로, 위에서 설명한 초기화 값이 1 인 세마포와 거의 비슷하게 동작한다. lock 에서는 "Up" 대신 "release", "Down" 대신 "acquire" 라는 이름의 operator 로 동작한다. lock 에는 세마포에는 없는 하나의 제약이 있는데, acquire 를 호출한 스레드만이 해당 lock 을 release 할 수 있다는 것이다. 0 으로 초기화 된 세마포의 설명에서 세마포는 스레드 A 에서 Down 을 하고 B 에서 Up 이 가능하였지만 lock 은 이러한 동작이 불가능하다. 이러한 제약으로 인해 문제가 발생한다면, 세마포를 사용하도록 하자.

    Lock 의 구조 및 코드 역시 <threads/synch.h> 에 구현되어 있다.

    반응형

    Monitors

    모니터는 동기화 문제를 해결하는 세마포나 락보다 활용도가 높고 사용이 쉬운 도구이다. 모니터는 공유자원, 모니터 락, 조건변수로 이루어진다. 모니터 락은 위에서 설명한 락과 유사하게 동작한다. lock 을 acquire 하면 이 스레드는 release 되기 전까지 "in the monitor" 상태가 된다. 이 상태에 여러 개의 스레드들이 있을 수 있고, 여기에 있는 스레드들은 서로 Mutual Exclusion(상호배타), 즉 공유자원을 하나의 스레드만 사용할 수 있는 상태가 된다. 별다른 조건이 없다면 여기에 있는 스레드들은 하나씩 차례로 실행되고 release 를 통해 빠져나간다. 모니터에는 여기에 추가로 Condition variables(조건 변수)를 추가할 수 있다. 임계구역을 실행중이던 스레드는 wait(condition) 명령을 통해 실행을 멈추고 대기 상태로 들어갈 수 있고, 이후 다른 대기중이던 스레드가 임계구역을 실행시킨다. 대기 상태의 스레드는 condition 이 true 가 될 때까지 대기하게 되는데, 실행중인 스레드에서 signal(condition) 명령을 통해 wait 되어 있는 스레드 중 하나의 condition 을 true 로 만들어 깨울 수 있다. broadcast(condition) 명령어는 현재 wait 중인 모든 condition 을 모두 true 로 만들어 깨운다.

     

    더 직관적인 이해를 위해 예제를 보도록 하자.

    void put (char ch) {
        lock_acquire (&lock);
        while (n == BUF_SIZE)
        	cond_wait (&not_full, &lock);
        buf[head++ % BUF_SIZE] = ch;
        n++;
        cond_signal (&not_empty, &lock);
        lock_release (&lock);
    }
    
    char get (void) {
        char ch;
        lock_acquire (&lock);
        while (n == 0)
        	cond_wait (&not_empty, &lock);
        ch = buf[tail++ % BUF_SIZE];
        n--;
        cond_signal (&not_full, &lock);
        lock_release (&lock);
    }

     

    이 예제에서 producer 스레드들은 put 함수를 통해 글자를 입력하고, consumer 스레드들은 get 함수를 통하여 글자들을 읽어온다. 버퍼의 크기는 한정적이므로 BUF_SIZE 가 가득 찬 경우에는 put 을 block 하여야 하고, 더 이상 읽어 올 글자가 버퍼에 남아 있지 않은 경우에는 get 을 block 하여야 한다.

    처음에는 버퍼에 아무 글자도 없을 것이기 때문에 get 은 cond_wait(&not_empty) 에 의해 not_empty 가 true 가 될 때까지 대기 상태가 된다. 이와 동시에 put 함수에서는 하나의 글자를 버퍼에 쓰고 cond_signal(&not_empty) 를 하여 &not_empty 라는 조건을 true 로 만들어주고, 이는 get 함수가 대기상태에서 깨어나 다시 진행되게 만들며 버퍼에 쓰여진 글자가 있기 때문에 정상적으로 글자를 읽어낸다. 반대의 경우도 마찬가지로 put 함수가 반복되어 버퍼가 가득 차게 되면 put 함수에서는 cond_wait(&not_full) 로 put 함수가 더 이상 실행될 수 없도록 대기 상태로 만들고 get 함수가 글자를 읽어 버퍼를 비워준 후에 cond_signal(&not_full) 을 통해 not_full 조건을 true 로 만들어 준 후에 다시 실행된다.

     

     

    Optimization Barriers

    컴파일러는 프로그램의 최적화를 위해(성능향상을 위해) 처리 순서에 dependency 가 없는 경우 statements 를 임의로 reorder 하는 경우가 있다. 하지만 얼핏 연관(dependency) 가 없어보이지만 실제로는 연관성이 있는 경우가 있다. 이러한 경우 컴파일러가 임의로 순서를 바꾸거나 최적화 해버리는 실수를 방지하기 위해 사용되는 것이 Optimization Barriers 이다.

     

    하나의 예를 들어보자.

    /* <devices/timer.c>
     * Wait for a timer tick. */
    int64_t start = ticks;
    while (ticks == start)
        barrier ();

    이것은 too_many_loops() 라는 함수에 존재하는 코드인데, while 문을 통해 반복문을 여러차례 반복시켜서 ticks 가 흘러가게 하여 시간을 재는 용도로 이용된다. 하지만 이러한 배경이 없이 이 코드 자체만 보면, barrier() 라는 부분이 없다면 while(ticks == start) 부분은 내부에서 아무런 작업도 하지 않으므로 컴파일러가 자칫 무한루프라고 인식하여 코드 자체를 무한루프로 최적화시킬 수 있다. barrier() 는 이러한 최적화를 하지 않도록 컴파일러에게 알려주는 명령이다.

     

    멀티스레드 간의 실행에서 barrier() 사용의 예제를 하나 더 보도록 하자.

    /* thread 1 */
    x = 0;
    while (x == 0)
        barrier();
    print y;
    
    
    /* thread 2 */
    y = 1;
    barrier();
    y = 10;
    barrier();
    x = 1;

    위 코드의 의도는 thread 1 의 print y 에서 y 의 값으로 10이 출력되게 하고 싶다. barrier() 가 없다면 컴파일러가 실수할 수 있는 상황이 몇 가지 있다. 우선, thread 1 에서 컴파일러는 while (x == 0) 를 무한루프로 인식하고 더 이상 진행하지 않도록 최적화할 수가 있다. 이 경우 y 는 출력되지 않는다. 또한, thread 2 에서 y = 1, y = 10 은 그 자체로 보면 순서가 상관없는 코드이므로 컴파일 단계에서 순서가 뒤바뀔 가능성이 있다. 이 경우 y 는 1 로 출력된다. 마찬가지로 x = 1 또한 y = 1, y = 10 과 순서가 뒤바뀔 수 있는데, 이 경우 x = 1 이 먼저 실행되면 y = 10 이 실행되기 전에 thread 1 의 print y 가 실행되어 의도하지 않은 y 값이 출력되는 상황이 발생할 수 있다.

     

    반응형
Designed by Tistory.