☁ Development ☁

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 

1. 커널 동기화 ?

   • 메모리를 공유하는 응용 프로그램은 항상 동시적인 접근으로부터 공유된 자원을 보호해야 한다.
   • 다수의 실행중인 스레드가 동시에 데이터를 변경할 경우 다른 스레드가 변경한 부분을 또 다른 스레드가 잘못 덮어써버릴 가능성이 있다.

   • 멀티프로세싱, 선점형 스케줄링 환경에서는 다양한 동시성 문제가 발생할 수 있다.

     
     

2. Critical Region(위험구역) and Race Condition (경쟁 상태)

   • 위험구역이란 공유된 데이터를 접근하여 조작하는 코드 부분을 가리킨다. 원자적 실행을 보장해야 한다.

   • 경쟁상태란 스레드들이 위험구역에 들어가기 위해 경쟁하는 상태.

     
     

3. 락킹(Locking)

   • 한번에 오직 하나의 스레드만이 공유하는 자료구조를 조작할 수 있다는 것을 확실할 방법.
   • 특별한 구역에서 다른 스레드가 동작하고 있을 때 해당 자료구조를 접근하지 못하게 하는 방법.

   • 락은 동시성을 방지하여 경쟁상태로부터 큐를 보호할 수 있다.

     1. 스레드는 방에 들어서면서 방문을 잠근다. 공유 데이터의 사용이 끝나면 스레드는 자물쇠를 열고 방을 떠난다.
     2. 만약 다른 스레드가 방문에 도착했을 때 문이 잠겨져 있다면, 안에 있는 스레드가 문을 열고 나올 때까지 기다린 후에 방에 들어가게 된다.

     3. 스레드는 락을 잠그고, 락은 데이터를 보호한다.

        
        

4. 동시성

   • 프로그램들이 선점되면서 스케줄링 된다는 사실에서 비롯된다. 어떤 프로세스가 위험지역에 있을 때 비자발적으로 선점돼 버리는 일이 발생할 수 있다.

     • 유사동시성(peudo-concurrency) - 실제로는 동시에 발생하지 않지만 서로 엇갈려서 실행돼 마치 동시에 실행되는 것과 같은 효과가 발생.
     • 진정한동시성(true-concurrency) - 대칭형 멀티프로세싱 시스템에서 두 프로세스는 정확히 가튼 시간에 하나의 위험지역에 진입 할 수 있다.

   • 커널에서의 동시성의 원인

     1. 인터럽트 - 비동기적으로 어느때나 발생하여 현재 실행중인 코드를 중단시킨다.
     2. softirq와 태스크릿 - 커널은 현재 동작중인 코드를 중단하기 위해 거의 언제라도 softirq나 태스크릿을 레이즈하거나 스케줄할 수 있다.
     3. 커널 선점 - 커널도 선점형이므로, 커널에 있는 한 태스크가 다른 태스크를 선점할 수 있다.
     4. 유저공간에서의 휴면과 동기화 - 커널의 태스크는 휴면할 수 있으며 따라서 스케줄러가 새로운 프로세스를 실행하게 된다.
     5. 대칭형 멀티프로세싱 - 2개 이상의 프로세서가 코드를 동시에 실행할 수 있다.

   • 동시성으로 인해 문제가 발생되는 경우 (락이 없다면..) : 경쟁상태가 발생

     1. 커널에서 어떤 자원을 조작하고 있는 도중에 인터럽트가 발생하여 같은 자원에 접근하는 경우.
     2. 커널이 공유 자원을 사용하고 있는 동안 커널 코드가 선점되는 경우.
     3. 위험지역을 실행하는 도중 커널 코드가 휴면하는 경우.

     4. 두 프로세서가 동시에 공유데이터에 접근하는 경우.

        
        

5. 보호영역의 결정

   • 동시에 접근될 수 있는 모든 코드는 보호가 필요로 하므로, 사실 보호가 필요없는 코드를 먼저 찾아내는 법도 있다.

     1. 특정스레드에 로컬한 데이터가 있을 경우.( 로컬자동변수, 스택에서만 존재하는 자료구조들.. )
     2. 특정 태스크에 의해서만 사용되는 데이터.

   • 보호영역의 선정 ( 커널의 거의 모든 전역 데이터와 공유 데이터는 어떠한 형식으로든 동기화. )

     1. 데이터가 전역적인가 ? 다른 스레드가 이 데이터에 접근 가능한가?
     2. 데이터가 프로세스 컨텍스트와 인터럽트 컨텍스트간에 공유되는가?
     3. 데이터를 사용하는 도중 프로세스가 선점되는 경우, 새로 스케줄된 프로세스가 같은 데이터에 접근하는가?
     4. 현재 프로세스가 휴면(or 블록)하는 경우가 있는가? 만약 그렇다면 휴면(블록)시 공유 데이터가 어떤 상태에 놓이게 되는가?
     5. 다른 곳에서 이 데이터가 해제되지 않으려면 어떻게 해야 하는가?

     6. 이 함수가 다른 프로세서에서 호출되면 어떤 일이 벌어지는가?

        
        

6. 데드락(Deadlock)

   • 어떠한 스레드도 더 이상 진행할 수 없는 상태

     • 각 스레드가 어떤 자원을 얻으려 대기하지만 이미 모든 자원의 락이 잡혀있을 때 발생한다. 모든 스레드가 서로에 대해 대기하므로 이미 잡고 있는 자원을 해제할 수도 없다.
   • 셀프 데드락(self-deadlock) 이란 어떤 스레드가 자기 자신이 이미 잡고 있는 락을 다시 얻으려 시도할려고 할때 발생.

   • 죽음의 포옹(deadly embrace) or ABBA 데드락 이란 2개의 스레와 2개의 락이 있는 경우 발생.

     • 스레드1이 락 A를 얻음 / 스레드2가 락 B를 얻음
     • 스레드1이 락 B를 얻으려 함 / 스레드2가 락 A를 얻으려 함
     • 스레드1이 락 B에 대해 대기 / 스레드2가 락 A에 대해 대기

   • 데드락 방지

     1. 중첩된 락은 반드시 같은 순서로 잠겨져야 한다. 죽음의 포옹을 방지.

        • 서로 다른 구조체를 보호하는 cat, dog, fox 라는 3개의 락이 있을 때 어떤 함수가 cat->dog->fox 순서로 접근을 하였다.
        • 다른 모든 함수 역시 같은 순서로 락들을 잠가야 한다.

     2. 기아현상(starvation)을 방지해야 한다. 코드가 종료하는가를 되짚어 봐야 한다. 어떠한 코드도 무한대기가 일어나서는 안된다.!

        • 락이 풀리기를 대기중인 스레드들은 적당한!! 시간에 락을 얻을 수 있어야만 한다.
     3. 같은 락을 두 번 잠그지 않아야 한다.( 리눅스에서는 재귀적 락을 제공하지 하는다. )

     4. 락은 최대한 단순하게 설계해야 한다.

        
        

7. 경쟁과 확장성

   • 현재 사용되고 있는 어떤 락을 다른 스레드가 얻으려 하는 상황을 락경쟁(Lock Contention) 혹은 경쟁이라고 한다.

     • 경쟁이 심한 락일수록 시스템 성능 저하에 더 큰 영향을 미친다.
   • 확장성이란 어떤 시스템이 얼마나 잘 확장될 수 있는가를 가리킨다.
   • 락킹의 세세함(granularity) 이란 그 락이 보호하는 데이터의 크기를 고려하는 것을 의미한다.

   • 정확하지않은(coarse)락은 많은 양의 데이터, 전체 서브시스템의 자료구조를 보호하는 경우이다.

     • 락경쟁이 심할 경우 확장성의 저하로 이어진다.

   • 매우 촘촘한(fine grained)락은 매우 적은 양의 데이터, 큰 구조체에 속한 하나의 항목만을 보호한다.

     • 충분한 락 경쟁이 없는 경우 소모적인 부하로서 작용한다. 
       
       
       출처 : http://dblab.co.kr/category/Study/System?page=1  

• TASK_RUNNING

  • 프로세스가 CPU에서 실행 중이거나 실행되기를 기다리는 중이다.
• TASK_INTERRUPTIBLE
• • 프로세스가 어떤 조건에 맞아떨어지기를 기다리면서 보류 중(자는중)이다. 프로세스를 깨울수 있는 조건으로는 하드웨어 인터럽트가 발생하거나, 프로세스가 기다리고 있는 자원이 해지되거나, 프로세스에 시그널을 전달하는 것이 있을 수 있다.

• TASK_UNINTERRUPTIBLE

  • TASK_INTERRUPTIBLE과 비슷하지만 잠들어 있는 프로세스에 시그널을 전달해도 프로세스 상태가 바뀌지 않는다는 차이가 있다. 이 프로세스 상태는 거의 사용하지 않는다. 그러나 프로세스가 정해진 사건이 발생하기를 기다리는 도중에 방해를 받으면 안 되는 특수한 상황에서 유용하다. 예를 들어, 프로세스가 장치 파일을 열 때 해당 장치 드라이버가 자신이 다룰 하드웨어 장치가 있는지 조사하는 경우에 이러한 상태를 사용할 수 있다. 장치 드라이버는 조사를 완료할 때까지 방해를 받으면 안된다. 그렇지 않으면 하드웨어 장치가 예측할 수 없는 상태에 빠질 수도 있다.

• TASK_STOPPED

  • 프로세스 실행이 중단 되었다. 프로세스는 SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU의 시그널을 받으면 현재의 상태가 된다.

• TASK_TRACED

  • 프로세스 실행이 디버거에 의해 멈춘 경우이다. 디버거가 테스트 프로그램을 모니터링하기 위해 ptrace()  시스템 콜을 수행하는 것처럼 프로세스가 다른 프로세스에 의해 모니터링 될 때 시그널은 프로세스를 TASK_TRACED 상태에 둔다.

• EXIT_ZOMBIE

  • 프로세스가 종료되었지만 부모 프로세스가 wait4() 또는 waitpid() 시스템 콜을 호출하여 종료 프로세스의 정보를 반환하지 않은 경우이다. 부모 프로세스가 wait() 계열 시스템 콜을 호출하기 전에는 종료한 프로세스의 프로세스 디스크립터에 들어 있는 데이터를 부모 프로세스가 필요로 할 수 있기때문에 커널은 데이터를 삭제해서는 안된다.

• EXIT_DEAD

  • 마지막 상태로 부모 프로세스가 wait4() 또는 waitpid() 시스템 콜을 방금 수행하였으므로 시스템에서 제거되는 중이다. EXIT_ZOMBIE에서 EXIT_DEAD로 상태를 바꾸는 것은 같은 프로세스에 대해 다른 스레드가 wait() 콜을 수행함으로써 발생하는 경쟁 조건을 피하기 위해서이다.

리눅스 커널의 물리 메모리 관리는 페이지 단위로 이루어진다. 그렇다면 예를 들어 19byte를 요청한다고 해서 시스템의 페이지 단위인 4K byte가 할당될까? 그렇지는 않다. 예를 들어 kmalloc을 사용하여 19 byte를 요청하게 되면 32byte가 할당된다. 그렇다면 kmalloc은 어떻게 32byte를 할당하게 할까? 이것이 이번 장에서 얘기할 슬랩 할당자 덕분이다.