Linux 10. Synchronization

1. Synchronization

여러 쓰레드가 shared resource에 동시에 접근하려는 상황에 한 순간에 한명만 점유할 수 있도록 보장해야 한다.

critial section은 한번에 한명만 실행하고 있음을 보장하는 code segment이다. 대게 critical section은 shared variable에 접근하는 부분이다.

critical section이 보호되지 않는 상태에서 여러 쓰레드가 자원에 접근하는 상황에 결과를 장담할 수 없다 이를 race condition이라고 한다.

critical section을 보호하기 위해 entry에 lock을 잡고 들어가서 exit에서 Lock을 해제한다.

i의 값을 증가시는 함수를 호출하는 두 thread가 있다고 하자. 운이 좋으면 예상하는대로 작업이 진행될 수 있겠지만

Thread2가 Time2에 get i를 수행해버리면 7값을 가져와서 결과가 달라질 수 있다.

2. Sharing resources

Local variable들은 thread들 각각이 가지고 있는 stack영역에 저장되기 때문에 서로 공유되지 않는다. 

global variable들은 thread들 끼리 공유된다. data segment에 저장되어 있어 모두로부터 접근이 가능하다.

dynamic object들은 heap영역에 저장되어 thread들 간의 share가 가능하다.

 

3. critical section in Linux kernel

race condition이 발생하는 상황을 살펴보자.

1번 task가 queue에서 데이터를 하나 read하려고한다. 즉 critical section에 진입한다. 그런데 중간에 interrupt가 발생해버렸다. Interrupt Service Routine이 interrupt handler를 호출하고 queue에 push작업을 처리하려고 한다. task 1, 2에 의해 shared_q에 대한 race condition이 발생한다.

task1이 read를 위해 ciritical section에 진입했다. 이때 cpu 자원을 양보하기 위해 preemption이 발생해서(혹은 block되어 sleep 상태가 되어서)  Task1이 중단되고 Task2가 이어서 실행됐다. 똑같이 task2가 read를 수행하려 critical section에 진입한다. 마찬가지로 race condition이 발생한다.

(CFS는 task scheduler이다)

 

이러한 race condition을 막기 위해 critical section을 보호해서 consistency를 확보해야 한다.

 

single core라면 critical section에 진입한 작업에 대해 preemption (interrupt)를 disabling 시킴으로써 해결할 수 있을 것이다.

multi core 환경에서는 단순히 preemtion, interrupt를 disable시키는 것 만으로는 부족해서 lock, atomic operation(cpu가 한 작업 처리에 여러 Operation을 동시에 수행)을 활용할 수 있다.

 

4. Disabling preemption 

아까의 상황에서 critical section을 preemption disable로 보호할 수 있다. 그럼 Task1의 critical section이 끝날때까지 cpu는 작업을 계속한다.

하지만 이렇게 interrupt가 발생하는 상황에서는 위 그림처럼 작업순서가 꼬여버릴 수 있다. disable preemption이 interrupt까지 막을 수는 없기 때문에 interrupt disable을 따로 해줘야 한다.

kernel Fucntion이다.

preempt_disable을 하면 preempt_count를 증가시키고 preempt_enable을 하면 preempt_count를 감소시킨다. preempt_count가 0이면 preemptable하다.

 

5. Disabling interrupts 

이렇게 critical section은 interrupt로부터 보호할 수 있다.

single core에서는 preemption과 interrupt를 둘다 막았을 때 아무 문제가 없을 수 있지만 그림처럼 multicore환경에서는 동시에 task2가 critical section에 진입하는 경우가 생길 수 있다. 따라서 multicore환경에서는 lock, atomic operation등이 추가로 필요하다.

 

6. Atomic operation

atomic operation은 process들과 완전히 독립적으로 실행된다. process들을 interleaving하게 수행하기 위해서(concurrenct programming) lock, atomic operation들이 활용될 수 있다.

atomic operation은 여러 작업을 한 cpu 명령으로 처리하도록 해준다. 읽고 수정하고 쓰기를 한 타임에 single operation으로 처리하기 때문에 다른 process가 끼어들 순간이 없다. atomic operation은 하드웨어(cpu)차원에서 지원해준다. 

atomic_set등의 함수를 활용하면 특정 global 변수를 보호하기위해 lock을 사용하지 않고도 편하게 (게다가 성능도 훨씬 빠르다) critical section을 보호할 수 있다.

inline으로 함수가 호출되는 방식이 아닌 직접 코드를 삽입하며 어셈블리 언어로 구현된다.

0번지가 output 1이상이 input이다.

+m (v->counter) : 부분이 %1을 output에 더해서 메모리에 저장하라는 부분이고

ir (i)가 input을 나타낸다. 매개변수 int i에는 어떤 변수 a 이렇게 집어넣어도 되고 그냥 2 같이 상수를 집어넣어도 된다.

 

이렇게 atomic operation을 잘 활용하면 Lock없이 concurrent programming을 하여 훨씬 fine grained operation을 가능하게 해줄 수 있다. (뒤에서 더 자세히 설명)

 

GCC 에도 builtin function으로 atomic operation 함수를 제공한다. 위에서 설명한 어셈블리 코드들을 기반으로 만들어져 있으며 built in 함수들이기 때문에 커널에서든 응용프로그램 영역에서든 gcc로 빌드만 한다면 어디서든 바로 사용할 수 있다.

 

7. GCC built in functions : atomic operation 

시험에 나옴 코드 쓰는거 실행결과 디버깅하는거

i 값을 가져와서 1값을 더하고 i 에 저장한다. 함수의 반환값은 previous value이다.

int x = 3;
int ret = 0;

ret = __sync_fetch_and_add(&x, 1);
printf(ret)   // 3 (previous value) 
printf(x)     // 4

i에 1을 대입한다. 마찬가지로 return값은 previous value이다. 위 코드에서 printf(ret)은 0이고 printf(i)는 1이다.

compare and swap은 x랑 oldval이 같으면 x에 newval을 write한다. 마찬가지로 return value는 previous value이다.

i가 0과 같으므로 i에 1을 대입한다 return은 이전 값인 0이다.

int x = 1;
ret = __sync_val_compare_and_swap(&x, 1, 2)
printf(x) // 2
printf(ret) // 1

첫번째 쓰레드가 while문으로 진입한다.

i는 0과 같으므로 1을 i에 저장하고 return 값은 0이므로 false가 되어 while문을 뚫고 지나간다. 즉 while문 아래 코드를 실행한다.

 

이어서 두번째 쓰레드가 foo를 호출해서 while문으로 진입한다. 

이때 i는 1인데 0과 다르므로 값은 변경하지 않고 이전 값 1을 리턴한다. 그럼 while문에 true로 걸려서 infinite loop를 돌게 된다. 즉 첫번째 쓰레드 이후에 쓰레드들은 foo를 호출하더라도 while밑에 critical section으로 진입하지 못한다.

 

이렇게 atomic operation을 잘 활용하면 Lock없이 concurrent programming을 하여 훨씬 fine grained operation을 가능하게 해줄 수 있다. lock을 foo에 거는 비용이 더 크고 만약 foo가 복잡한 경우라면 뜯어고쳐야 하는 부분이 훨씬 많을 것이다. 이렇게 직접 작은 작업 단위에서 lock과 같이 구현할 수 있기 때문에 더 fine grained하다고 한다.

 

예를들어 아래같이 tree자료구조가 있다고 하자

          ㅇ
         /  \
        ㅇ   ㅇ
       / \  / \
      ㅇ  ㅇ ㅇ ㅇ
               \
                ㅇ  <----만약 이 노드의 자식으로 노드를 추가하고싶다면?

저 트리에 대한 concurrency를 확보하기 위해서는 제일 root node에 lock을 걸면 된다 root부터 접근하므로 첫번째로 lock을 확보한 쓰레드를 제외하고는 아무도 접근할 수 없다. 

하지만 이보다 상대적으로 적은 cost로 CAS(compare and swap)을 활용해서도 문제를 해결할 수 있다.

추가하려는 노드의 부모한테만 CAS를 걸면 동시에 다른 쓰레드들은 다른 위치에 얼마든지 노드 삽입 작업을 할 수 있으면서도 원래 쓰레드는 작업을 무사히 마칠 수 있다. 이런게 fine grained하다는 것이다.

첫번째 쓰레드 첫번째 루프 통과 i = 1 ret = 1  // i = 1 두번째 루프에서 걸림

두번째 쓰레드  i = 1이므로 첫번재 루프에서 걸림

 

CAS로 simple한 spinlock을 구현했다. 이렇게 CAS를 활용했을 때 장점이 있다. 지금 보이는 코드는 acquire 시도를 했는데 while루프에 걸려버려서 아무것도 못하지만. while을 if문으로 바꿔서 커스텀한다면 얼마든지 lock을 확보할 때까지 다른일을 하도록 지시할수도 있다.

 

여기에는 또 한가지 문제가 있다. 

첫번째 쓰레드가 자원을 얻어서 작업을 처리하고 있다. 그런데 뒤이어 2, 3, 4번 쓰레드가 while루프에 걸렸다. 1번 쓰레드가 자원을 반환했을 때, 이어서 누가 자원을 확보할지 알수 없다. 최악에 상황에는 먼저 도착한 2번이 끝까지 자원을 얻지못하는 starvation이 일어날 수도 있다. 이런 unfairness를 해결하기 위한 방법으로 ticket lock 을 fetch-and-add로 쉽게 구현할 수 있다.

첫번째 쓰레드 ticket = 0, turn 0 ---------acquire---------- myturn = 0, ticket = 1 while 통과 ---------release---------- turn = 1

두번째 쓰레드 ticket = 1, turn = 0 --------------aquire------------ myturn 1, ticket = 2 while 루프에 걸림 turn == myturn == 1 루프 탈출 ------------release-------------- turn = 2

세번째 쓰레드 ticket = 2, turn = 0 -------------aquire------------- myturn = 2, ticket = 3 while 루프에 걸림 turn == myturn == 2 루프 탈출

코드쓰기 디버깅 시험에 나온다