[SW 정글 69일차] 오늘은 Concurrency 되짚어 보기

오늘은 일요일이여서 잠시 pintos project 2 구현을 멈추고 project 1을 진행하면서 확실히 나의 것으로 만들지 못한 concurrency에 대해 복습해보려고 한다.

공부자료는 three easy pieces와 컴퓨터 시스템 12장이다.

좋은 자료는 내 곁에 항상 있고 나는 그 자료를 기반으로 나의 것으로 만들 시간과 노력만 있으면 된다.

 

 

 

Concurrency를 이해하는데 알아두면 좋은 개념은 스레드라고 생각한다.

스레드는 한 마디로 말하자면 하나의 프로세스 내에서 실행되는 작업의 흐름 단위이다.

조금 더 구체적으로 말하면 하나의 프로세스는 code, data, stack, heap 영역으로 나뉘어진 각자의 주소 공간을 할당받는데 프로세스 안에 여러 스레드가 존재하게 되면 스레드마다 또 다시 각각의 주소공간이 생기는 것이 아닌 stack을 제외한 주소 공간(code, data, heap)을 공유한다.

하나의 프로세스 내에 여러 스레드가 존재하면 CPU는 작업의 단위를 스레드로 생각하기에 스레드도 프로세스와 마찬가지로 어디까지 작업이 진행됐는지를 저장하는 프로그램 카운터와 연산을 위한 레지스터를 가지고 있다.

그래서 스레드들끼리도 context swiching이 발생하고 스레드들의 상태를 저장하기 위해서 스레드 제어 블록(TCB)가 필요하다.

 

왜 갑자기 스레드에 대한 개념을 설명했는지에 대한 이유는 concurrency를 하기 위해서는 멀티프로세싱으로도 가능하지만 스레드를 사용하여 멀티스레딩도 가능하기에 멀티스레딩을 하기 위한 본질의 개념인 스레드를 알고 넘어가기 위해서이다.

 

Concurrency를 수행하기 위해서 가장 조심해야할 것은 공유자원접근이다.

하나의 프로세스 내에 여러 스레드가 존재하고 각각의 스레드는 모두가 공유하고 있는 자원들이 존재할 것이다.

스레드들이 스케쥴링에 따라 각자 언제 CPU를 선점할지 모르는 상황에서 공유하고 있는 자원을 마음대로 접근한다면 우리가 예상하지 못한 결과를 내보일 수 있다.

그래서 우리는 동기화를 해주어야하고 동기화를 위한 여러 primitives가 존재한다.

오늘은 이 synchronization primitives를 중점으로 두어 공부를 하고 정리할 것이다.

 

 

 

1. concurrency 관련 용어

먼저, concurrency를 공부하면서 자주 마주칠 용어를 간단하게 정리하려고 한다.

 

1) 임계 영역 (critical section)

전체적인 코드 내에서 변수나 자료 구조와 같은 공유 자원을 접근하는 코드의 일부분을 의미한다.

 

2) 경쟁 조건 (race condition)

멀티 스레드가 거의 동시에 임계 영역을 실행하려고 할 때 발생하며 공유 자료 구조를 모두가 갱신하려고 시도한다면 우리가 예상하고 있는 결과와 다른 결과를 내보일 수 있다.

 

3) 상호 배제 (mutual exclusion)

상호 배제는 여러 스레드가 임계 영역에 거의 동시에 접근하여 경쟁 조건에 빠져 예상치 못한 결과를 내는 것을 막아주는 기법 중 하나이다.

상호 배제를 통해 하나의 스레드만이 임계 영역에 진입할 수 있도록 한다.

 

상호 배제가 지켜지기 위해 요구되는 사항들이 존재한다.

- 임계 영역에 스레드가 존재한다면 다른 스레드의 진입을 금지한다.

- 임계 영역에 스레드가 없다면 스레드는 임계 영역에 진입할 수 있어야한다.

- 스레드의 임계 영역 진입은 유한 시간 내에 허용되어야 한다.

 

 

 

 

2. 락 (lock)

락은 위에서 언급한 임계 영역에 여러 스레드가 들어가 공유자원을 동시적으로 접근하여 작업이 이루어지는 상황을 막아 임계 영역이 마치 하나의 원자 단위 명령어인 것처럼 실행되도록 하는 것이다.

원자 단위라는 것은 더 이상 2개이상으로 쪼개질 수 없다는 것으로 임계 영역의 흐름은 마치 하나의 원자같이 생각되도록 한다는 것이다.

 

이러한 생각이 나온 이유는 아래와 같다.

위 명령어는 어떠한 스레드가 변수에 값을 더하는 연산과정을 어셈블리어로 나타낸 것이다.

프로세서는 하나의 라인, 예를 들면 첫 번째 줄을 실행하고 있었다면 이 작업은 원자성을 가지고 있어 어떠한 인터럽트도 해당 작업이 끝나기 전에는 받아들일 수 없다.

즉, 메인 메모리에 해당 주소에서 자원을 읽어 레지스터의 %eax위치에 올리는 작업이 시작됐으면 인터럽트나 프로세서 선점은 일어날 일이 없다는 것이다.

이러한 설정이 존재한다면 공유 자원을 여러 스레드가 접근하여 연산을 하고자 한다면 경쟁조건이 나올 수 밖에 없기 때문에 공유 자원을 접근하여 작업을 하는 코드부분을 임계영역으로 잡아서 그 임계영역을 lock이라는 것으로 둘러 마치 하나의 원자 단위로 만든다는 것이 lock이라는 것이다.

 

그러면 락(lock)을 조금 더 구체화 해보자.

락은 하나의 변수를 의미하고 락을 사용하기 위해서는 락 변수를 선언해주어야 한다.

락 변수는 락의 상태를 의미하는데 상태는 사용가능 상태(unlock 또는 free)이거나 사용 중인 상태(acquired) 상태 2가지가 존재한다.

락 자료구조에는 락을 보유한 쓰레드에 대한 정보나 락을 대기하는 스레드들에 대한 정보를 저장할 수도 있다.

 

락에는 lock()과 unlock()이라는 2가지 루틴이 존재한다.

lock() 루틴은 락 획득을 시도하는 것으로 어떠한 스레드도 락을 갖고 있지 않으면 lock()을 호출한 스레드는 락을 획득하여 임계 영역으로 들어갈 수 있게 된다.

이렇게 임계 영역에 들어간 스레드를 락 소유자(owner)라고 하며 락 소유자(owner)가 존재하는 경우에 다른 스레드가 lock()을 호출해도 임계 영역에 들어갈 수 없다.

락 소유자(owner)가 unlock()을 호출하면 락이 풀리며 다른 스레드가 lock()을 호출하여 임계 영역에 들어갈 수 있는 상태가 된다.

 

락을 구현한 방법은 여러가지가 존재한다.

첫 번째로 인터럽트를 제어하는 것이다.

단일 프로세스 시스템에서 사용한 방법으로 lock()함수가 호출되면 인터럽트를 비활성화하여 임계 영역을 상호 배제가 유지되도록하는 것이다.

장점은 단순하다는 것이지만 단점이 많이 존재한다.

lock()을 요청하는 스레드에게 인터럽트를 활성/비활성화하는 특권 연산을 실행할 수 있도록 허가하는 것으로 스레드가 신뢰할만하다면 문제가 없지만 greedy한 프로그램이 프로세서를 독점하여 사용할 수 있는 문제가 발생한다.

두 번째 단점으로는 멀티프로세서에서는 적용할 수 없다는 것이다.

여러 프로세서가 실행 중이라면 각 스레드가 동일한 임계 영역을 진입하려고 할 수 있고 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서를 비활성화하게 하지는 못한다.

즉, 다른 프로세서에서 임계 영역을 진입할 수 있다는 것이다.

세 번째 단점으로는 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트 시점을 놓칠 수 있다는 것이다.

 

두 번째로 TAS나 compare And Wait를 통해 제어하는 것인데 깊게 정리할 내용은 아닌 듯하다.

이는 spin lock을 유도한다.

(spin lock은 락이 풀릴 때까지 while문으로 계속 기다리는 것, busy wait이 발생하여 프로세서에게 큰 부담이 되고 다른 스레드가 선점할 수 없는 현상이 발생할 수 있고 멀티 프로세서에서는 효과적이지 않음.)

스핀 락을 해결하는 첫 번째 방법은 락이 해제되기를 기다리며 스핀해야하는 경우 자신에게 할당된 프로세서를 다른 스레등게 양보하는 것이다.

void init() {
    flag = 0;
}

void lock() {
    while (TestAndSet (&flag, 1) == 1)
        yield();
}

void unlock() {
    flag = 0;
}

이 방법의 단점은 비용이 많이 드는 것이다.

계속해서 yield()를 하게 되면 그 만큼 context swithing이 더 자주 발생하게 되는 것이고 컴퓨터에게는 큰 비용으로 작용한다.

그리고 starvation 현상이 발생할 수 있다는 단점도 존재한다.

 

두 번째 방법은 락을 다른 스레드가 갖고 있을 때 lock()을 호출한 스레드들을 잠들게 하는 것이다.

운영체제의 지원과 큐를 이용한 락을 대기하는 스레드를 관리하는 것이 필요하다.

 

 

 

 

3. 세마포어 (semaphore)

다양한 병행성(concurrency) 문제를 해결하기 위해서는 위에서 정리한 락(lock)과 condition variable 모두 필요하다.

condition variable은 읽기는 했는데 여기에 정리할 만큼 나의 것으로 만들지 못해 다음에 다시 읽고 정리하려고 한다.

 

세마포어는 정수 값을 갖는 객체로서 sema_wait(), sema_post() 두 개의 루틴으로 컨트롤할 수 있다.

세모포어는 초기값에 의해 동작이 결정되기 때문에 사용하기 전에 초기 값을 설정해야한다.

#include <semaphore.h>

sem_t s;
sem_init (%s, 0, 1);

sem_init(sem_t *s, int pshared, unsigned int value)을 이용하여 세마포어의 초기값을 설정할 수 있다.

첫 번째 인자에는 semaphore 변수를 넣고 두 번째 인자에는 0이 아닌 정수가 들어가면 해당 세마포어가 서로 다른 프로세스들 사이에서 공유가 가능하다는 것이고 0이면 하나의 프로세스 내의 스레드끼리만 공유가 가능하다는 것이다.

세 번재 인자는 세포마어의 초기값을 value로한다는 것을 의미한다.

 

 

int sem_wait (sem_t *s) {
    // semaphore s의 value를 1만큼 감소
    // s가 음수이면 wait
}

int sem_post (sem_t *s) {
    // semaphore s를 1만큼 증가
    // 한 개이상의 스레드가 waiting 중이라면 wake해줌
}

위 2개의 루틴은 project 1때 구현한 경험이 있다.

여기서는 간단히 어떠한 역할을 하는지 적었고 이 루틴들은 다수의 스레드들에 의해 동시에 호출되는 것을 가정한다.

이 루틴들에는 핵심적인 성질들이 존재한다.

 

1) sem_wait() 함수는 즉시 리턴(세파포어의 값이 1이상이면)하거나 세마포어 값이 1이상이 될 때까지 호출자를 대기시킨다.

 

2) sem_post() 함수는 대기하지 않고 세마포어 값을 증가시키고 대기 중인 스레드 중 하나를 깨운다.

 

3) 세마포어가 음수라면 그 값은 현재 대기 중인 스레드의 개수와 같다.

 

세마포어는 자식 프로세스가 종료되기를 기다리는 부모 프로세스의 condition에도 적용이 가능하다.

초기값을 0으로 준 semaphore를 사용하여 2가지의 경우(자식 프로세스가 ready상태인 경우, 자식 프로세스가 exit상태인 경우)를 모두 커버할 수 있다.

 

 

---

[오늘의 나는 어땠을까?]

오늘은 일요일이여서 휴식 차 푹자고 하루를 시작했다.

일단은 오늘 목표를 내가 할 수 있는 가능성을 생각하여 정했다.

목표는 concurrency부분을 이해하고 나의 것으로 만드는 것이였는데 conditional variable 부분을 제외하면 나의 것이 된 기분이 든다.

아직 의문이 드는 부분들이 있지만 계속해서 복습을 하다보면 풀릴 것이라고 생각하고 concurrency는 언제든 시간이 나면 다시 볼 생각이다.

 

아직 project 2구현을 할 수 있는 날이 3일이나 남았다.

system call을 완벽히 구현하지는 못하더라도 어떻게 구현이 되는지는 완벽히 이해하고 싶다.

최선을 다하자.