[9장 커널 동기화 방법]

1. 원자적 동작(Atomic Operation)

   • 중단됨이 없이 한번에 실행되는 명령. 원자(Atom)가 더 이상 쪼갤 수 없는 원소를 의미하듯 원자적 동작은 나눠지지 않는 명령등을 의미한다.

2. 원자적 정수연산, 원자적 비트연산

   • 원자적 정수연산은 특별한 자료구조인 atomic_t를 사용한다.

     1. 원자적인 함수들이 다른 자료형에 잘못 사용되는 것을 방지.
     2. 원자적동작이 엘리어스(alias)가 아닌 실제 메모리 주소를 사용하게 한다.
     3. 컴파일러가 이 자료형으로의 접근을 잘못 최적화하지 않도록 방지.
     4. 아키텍처에 따라 다른 구현을 감춰주는 역할.
   • 커널코드 작성시 모든 아키텍처에서 사용가능한 함수를 확인해 보아야 한다.

3. 스핀락(Spin Lock)

   • 최대한 하나의 스레드에 의해 잠길 수 있는 락을 말한다.

     1. 만약 어떤 스레드가 이미 잠겨진 스핀락을 다시 잠그려 시도한다면 그 스레드는 루프(Busy Loop)를 돌면서(Spin)락을 잠글 수 있을때 까지 기다린다.
     2. 이러한 스피닝(Spinning)은 동시에 하나 이상의 스레드가 같은 위험구역에 진입하는 것을 방지해 준다.
   • 다른 스레드들을 스핀하도록(프로세스 시간을 소모함) 하므로 두번의 컨텍스트 스위칭 시간보다 짥게 잡고 있도록 하는 것(휴면방식을 사용하는것) 이 중요하다.
   • 프로세서가 하나인 시스템 에서도 인터럽트 핸들러가 공유 데이터를 접근하는 것을 방지하기 위해 인터럽트를 비활성화해야 한다.
   • 실제로 보호가 필요한 것은 코드 자체가 아닌 위험구역 안에 있는 데이터이므로 락을 특정한 데이터와 관련시키는 것이 좋다. "struct foo 는 foo_lock 으로 잠김"

4. 스핀락과 보톰하프(Bottom Half)

   • 보톰하프는 프로세스 컨텍스트 코드를 선점할 수 있으므로, 만약 어떤 데이터가 보톰하프와 프로세스 컨텍스트간에 공유된다면 락을 사용함과 함께 보톰하프를 비활성화시켜 데이터를 보호해야 한다.

     • 프로세스 컨텍스트란 ? 프로세서 고유 컨텍스트(Processor Specific Context) 프로세스는 시스템의 현재 상태의 총합 으로 생각할 수 있다. 프로세스는 실행될 때마다, 프로세서의 레지스터와 스택 등을 사용 한다. 이것이 프로세스 컨텍스트이며, 프로세스가 중단될 때 CPU 고유의 컨텍스트들은 모두 그 프로세스의 task_struct에 저장되어야 한다. 스케쥴러가 이 프로세스를 다시 시작할 때, 이 컨텍스트는 이 정보로부터 복구된다.

5. Reader 와 Writer 스핀락

   • 리스트가 갱신(쓰기)되는 경우에는 다른 코드가 동시에 리스트에 쓰거나 읽지 않도록 해야 한다. 상호배제(Mutual Exclusion)가 필요하다.
   • 리스트를 탐색(읽기)하는 경우에는 다른 코드가 동시에 리스트에 쓰는 것만을 방지하면 된다. 쓰기작업이 없다면 동시에 여러 곳에 탐색이 가능하다.
   • 자료구조의 사용이 Reader/Writer로 확연히 구분되는 경우(생산자/소비자)에는 락킹 메커니즘은 Reader/Wrtier 스핀락을 제공한다.
   1. rwlock_t mr_rwlock = RW_LOCK_UNLOCKED;
   2. read_lock(&mr_rwlock);
   3. /* 위험 구역(읽기 전용) */
   4. read_unlock(&mr_rwlock);

   5. write_lock(&mr_rwlock);

   6. /* 위험 구역(읽기, 쓰기 가능) */
   7. write_unlock(&mr_rwlock);
   • 대기중인 writer는 모든 Reader가 락을 해제할 때까지 락을 잠그지 못하게 되므로 리더가 상당 수 있는 경우 기아상태가 발생하게 될 수 있다.

6. 세마포어

   • 락을 잡고 있는 시간이 길어지거나 락을 잡은 채 휴면해야 하는 경우에 사용한다.

   • 동작시나리오

     1. 어떤 태스크가 이미 잠겨진 세마포어를 잠그려 하는 경우, 세마포어는 그 태스크를 대기큐로 삽입하고 해당 태스크를 휴면 상태로 만든다.
     2. 프로세서는 다른 코드를 실행할 수 있게 된다.
     3. 세마포어를 잡고 있는 프로세스가 락을 해제하면, 대기큐에 있는 하나의 태스크가 깨어나서 세마포어를 잡게 된다.
   • 바쁜 루프로 시간을 소모하지 않기 때문에 스핀락보다 더 나은 활용도를 보여주지만 스핀락에 비해 세마포어는 훨씬 많은 부가작업이 필요하다.( 인생은 Trade-Off -_ㅡ;; )

   • 세마포어의 휴면 동작이 주는 의미

     1. 락을 기다리는 태스크들이 휴면하게 되므로 세마포어는 락을 오랫동안 잡게 되는 상황에 적합하다.
     2. 락을 잡고 있는 시간이 짧을 경우 휴면하고 대기큐를 관리하고 다시 깨워주는 추가작업들이 락을 잡고 있는 시간보다 길어질 가능성이 있다.(비효율적.)
     3. 스레드의 실행은 락 경쟁에서 휴면 상태가 될 수 있고 인터럽트 컨텍스트는 스케줄이 불가능하기 때문에 세마포어는 오직 프로세스 컨텍스트에서만 얻을 수 있다.
     4. 세마포어를 잡은채로 휴면할 경우 다른 프로세스가 같은 세마포어를 잡으려 하더라도 데드락에 빠지지 않는다.( 두번째 스레드 역시 휴면되므로 결국 첫번째 스레드가 실행)
     5. 세마포어를 사용할 경우 스핀락을 잡고 있어서는 안되는데, 왜냐하면 세마포어를 잡으려면 휴면해야 하는데 스핀락을 잡고 있는 상태에서는 휴면해서는 안된다.

   • 세마포어 VS 스핀락

     1. 락을 잡고 있는 시간을 근거로 결정을 내려야 한다.

     2. 세마포어는 커널 선점을 비활성화하지 않으므로 세마포어를 잡고 있는 코드는 선점될 수 있다.( 스케줄링에 불리하게 작용하지 않는다. )

        
        

        요구사항	추천
        락 부담이 적어야 하는 경우	스핀락
        락 기간이 짧은 경우	스핀락
        락 기간이 긴 경우	세마포어
        인터럽트 핸들러에서 락을 해야 하는 경우	반드시 스핀락(스케줄링)
        락을 소유한 채 휴면해야 하는 경우	반드시 세마포어

   • 세마포어는 동시에 여러 스레드가 같은 락을 잠글 수 있다. 선언시 그 숫자를 지정할 수 있다.

     1. 락의 갯수를 1로 지정하여 하나의 스레드만이 이 락을 잡을 수 있도록 한것을 바이너리 세마포어, 상호배제 관점에서의 뮤텍스라고 부른다.
     2. 카운팅 세마포어는 다수의 스레드가 동시에 같은 위험구역에 진입할 수 있도록 하므로 상호배제를 보장하지 않는다.

   • Reader-Writer 세마포어

     1. 모든 Reader-Writer 세마포어는 뮤텍스이다.
     2. Wirter 가 없는 한 다수의 Reader가 락을 소유할 수 있고 Reader 가 없는 상황에서 오직 하나의 Writer 만 락을 소유할 수 있다.

7. 완료 변수( Completion Variable )

   • 커널의 두 태스크를 동기화시키기 위해 사용, 한 태스크가 이 변수를 통해 다른 태스크로 이벤트를 알려주는 식으로 동작한다.
   • 세마포어를 대신하여 간단히 사용하기 위해 제공되는 방법이다.
   • complete() 을 호출하여 완료변수에 시그널 되기를 기다리는 대기중인 태스크들을 깨어나도록 하는 방법.

8. 큰 커널 락(BKL, Big Kernel Lock)

   • 특성

     1. 소유한 상태에서 휴면할 수 있다.
     2. BKL이 잠겨있는 경우 커널 선점은 비활성화 된다.
     3. 재귀적인 락이다.
     4. 오직 프로세스 컨텍스트에서만 사용가능하다.
     5. 이것은 필요악이다. 악마의 현신!!
   1. lock_kernel();
   2. /*
   3. 다른 모든 BKL 사용자들과 동기화되는 위험 지역..
   4. 여기서는 안전하게 휴면할 수 있으며, 휴면할 경우 락이 자동적으로 해제된다. 또 휴면했다가 다시 스케줄링되면 자동적으로 락을 얻는다.
   5. 즉, 어느 경우이든 데드락은 피할 수 있지만, 정말로 여기서 데이터를 보호할 생각이라면 휴면하지 말아야 한다.!!!!
   6. */
   7. unlock_kernel();

9. seq 락

   • 공유 데이터를 읽거나 쓰기 위한 아주 간단한 메커니즘을 제공.
   • 많은 Reader와 적은 Writer가 있는 경우를 위한 매우 가볍고 확장성이 좋은 락이다.( Writer를 선호, 다른 Writer가 없을경우 항상 락을 잠글 수 있다. )

10. 선점의 비활성화

    • 커널이 선점형이므로 새로 실행되는 태스크가 선점된 태스크와 동일한 위험구역에 진입할 수 있다 .그러므로 커널 코드는 스핀락을 사용하여 선점 불가능한 코드 구역을 표시해야 한다.

    • 하나의 변수가 프로세서에 고유한 변수라면 락이 필요치 않게 되지만 프로세서간 선점으로 인해 유사 동시적으로 접근될 수 있다.

      1. preempt_disable();
      2. /* 선점이 비활성화됨 ..*/
      3. preempt_enable();
      • 커널 선점을 비활성하여 한다.

11. 오더링과 배리어

    • 프로그램 코드에 정의된 순서대로 행해야 하는 경우가 있다.

      • 하드웨어를 가지고 작업할 때는 어떤 읽기 작업이 다른 읽기나 쓰기 작업 이전에 행해져야 한다는 식의 요구조건.

    • 컴파일러와 프로세서 모두가 최적화를 위해 읽기/쓰기(인텔x86예외) 명령의 순서를 마음대로 뒤바꿀수 있기 때문에 별도의 방법이 존재한다.

      • 읽기와 쓰기 명령의 순서를 바꾸는 프로세서들은 명령의 순서 요구조건을 만족시킬 수 있는 기계어 명령을 제공한다.
      • 컴파일러에게 특정 지점에서는 명령어의 순서를 바꾸지 말도록 지시할 수도 있다. 배리어(Barrier) !!
    1. a = 1;

    2. b = 2;

       // 프로세서는 a보다 먼저 b에 새로운 값을 저장할 수도 있다. 컴파일러와 프로세서는 a와 b 사이에 어떠한 관련성이 있음을 알 수 없다.

    3. // a와 b사이에 명백한 연관이 존재하지 않기 때문에 재배열이 발생한다.
    4. a = 1;
    5. b = a;
    6. // a와 b사이에 명확한 데이터 의존성이 존재하기 때문에 재배열하지 않는다. a와 b사이에 명확한 데이터 의존성이 존재.
    • barrier() 함수를 통해 컴파일러가 로드와 스토어 명령을 최적화하는 것을 방지 할 수도 있다.

12. 요약

    1. 원자적 연산 : 동기화를 담보하는 가장 단순한 방법.
    2. 스핀락 : 해당 락에 오직 하나의 보유자만이 존재할 수 있는 가벼운 락으로 경쟁이 발생하면 바쁜 대기를 수행한다.
    3. 휴면락 : 세마포어와 완료변수, seq락
    4. 경쟁상태를 유발하지 않으면서 훌륭한 동기화를 보장할 수 있는 커널코드를 작성하자!! 심플하게~!
       
       출처 : http://dblab.co.kr/category/Study/System?page=1