week4_0327.md

• 리눅스의 연결리스트 가 일반적인 연결리스트 보다 나은 점은 무엇인가?

  • 개념
    • 일반적인 연결리스트
      
      • 구조체를 연결리스트로 만드는 개념
    • 리눅스의 연결리스트
      
      • 구조체 안에 연결리스트 노드를 넣는 개념
  • 리눅스 연결리스트 의 장점
    • list_head 구조체를 정의해놓고, 계속 재사용하면 된다. 코드 중복을 줄일 수 있고, 코드 재사용이 가능하다.
    • 구조체를 연결리스트로 구현하고 싶을 때, prev, next 포인터를 선언하는 것 대신 list_head 구조체를 포함하면 되므로 가독성이 좋고, 유지보수가 용이하다.
    • C에는 제네릭이 없다. 따라서 일반적인 연결리스트 로 모든 연결리스트를 구현하면 인자의 타입만 다르고 몸체가 비슷한 함수들을 각 구조체별로 구현해야 할 것이다. 그에 반해 리눅스 연결리스트 는 list_head 연결리스트의 함수들을 모든 구조체에서 사용할 수 있다.
  • 연결리스트 노드를 구조체 안에 넣는다면, 부모 구조체의 데이터들에는 어떻게 접근할까?
    • 구조체의 주소와 구조체 내 멤버의 주소 차이 (offset) 가 컴파일 시간에 정해지는 특성을 이용하여 부모 구조체에 접근한다.
    • container_of 매크로는 이미 우리가 알고 있는 list_head 구조체의 주소에서 컴파일 시간에 결정된 부모 구조체와 list_head의 offset 을 뺀다. 그 결과로 부모 구조체의 주소를 얻을 수 있다.

• 리눅스의 레드블랙트리 가 전통적인 레드블랙트리 와 다른 점을 설명하시오.

  • rbtree의 기본 법칙들을 만족하면서, 세세한 구현 부분 (최적화 부분) 을 리눅스의 사정에 맞게 바꿨을 것이다.
  • 구체적인 차이점을 알기가 쉽지 않아서, 각자의 개인적인 생각을 공유하였다.
    • rbtree는 CFS스케줄러에 사용된다. 이때 vruntime이 가장 적은 프로세스를 빠르게 선택하기 위해 rbtree의 제일 왼쪽 자식을 cache에 보관한다. 이렇게 rbtree의 사용 용도에 따라 필요한 작업을 추가하는 것을 최적화 라고 할 수 있고, 이러한 점이 전통적인 레드블랙트리 와의 차이가 될 수 있다.
    • 레드블랙트리 는 준 균형 상태를 유지하기 위해 데이터 변동 시 균형을 맞추기 위한 작업을 해야한다. 따라서 최적화 가 균형을 유지하는 코드에 리눅스 특유의 구현 방법을 사용했다는 것을 의미할 수도 있다.

• 리눅스의 CFS스케줄러가 rbtree를 사용하는 이유를 rbtree가 여타 자료구조와 비교하여 가지는 장점을 근거로 설명하시오.

  • rbtree
    • CFS스케줄러는 vruntime이 가장 작은 프로세스를 다음 실행할 프로세스로 결정한다. rbtree에서 키값이 가장 작은 것은 제일 왼쪽 자식이므로 탐색이 용이하다.
    • rbtree는 최악의 경우에도 O(log N)의 일정한 실행 시간을 보장한다. 이는 실시간 스케줄링을 수행하는 스케줄러에게 중요한 특성이다.
    • rbtree는 준 균형 트리다. 간단한 법칙들로 이러한 준 균형 트리를 유지할 수 있는데, 이 덕분에 삽입, 제거 연산에 부가 비용을 크게 들이지 않고도 준 균형 상태를 유지할 수 있다.
      • 이에 반해 AVL트리는 엄격한 균형 트리인데, 엄격한 조건 덕에 rbtree보다 삽입, 제거에 더 많은 연산이 필요하다.
  • 해시테이블
    • 일반적인 탐색시간은 O(1)이지만, 최악 탐색시간이 O(N)으로, rbtree보다 크다. 가장 작은 키값을 찾는 것 역시 O(N)의 시간복잡도를 갖는다.
      • 일정하지 않은 탐색시간은 스케줄링 성능에 악영향을 준다.
    • 해시 충돌을 해결하기 위한 방법을 추가적으로 적용해야 하며, 해시 함수 또한 필요하다.
  • 연결리스트
    • 키값을 기준으로 정렬하려면 삽입 O(N), 삭제 O(N), 탐색 O(N)이고, 정렬하지 않는다면 삽입 O(1), 삭제 O(N), 탐색 O(N)이다.
      • 탐색이 자주 일어나는 스케줄러에서 사용하기에는 적합하지 않다.
  • 최소 힙
    • 최소 힙은 탐색시간이 O(1)이고, 삽입 연산은 O(log N)이다. 그렇다면 최소 힙이 CFS스케줄러에 사용되지 않는 이유는 무엇일까?
      • 리눅스에서 최소 힙은 배열로 구현한다. 배열의 특성상 모든 원소들이 순차적으로 메모리에 저장되어야 한다. 프로세스의 수가 많으므로 배열은 큰 메모리를 차지할 수밖에 없다. 이러한 연속적이고 큰 메모리의 할당을 위해 Storage compaction이 필요할 수 있고, 이는 성능의 bottleneck 이다.
      • 최소 힙의 탐색시간은 O(1)이지만, 이는 삭제 없이 단지 루트 노드를 들여다보기만 하는 시간이다. 만약에 루트 노드를 삭제할 때는(프로세스를 runqueue에서 제거할 때) O(log N)의 시간복잡도를 가지며, 키값(vruntime) 업데이트 시에도 O(log N)의 시간복잡도를 가진다. 루트 노드가 아닌 노드를 삭제할 때의 시간복잡도는 O(N)이다. 따라서, 최소 힙은 rbtree보다 효율적이지 않다.

• 각 자료구조의 장단점을 기술하고, 사용되는 상황을 예시로 제시하시오.

  • 연결리스트

    • 사용
      • 탐색의 성능이 좋지 않으므로, 탐색이 적고 삽입, 삭제가 많은 경우에 사용된다.
    • 장점
      • 동적으로 데이터를 관리할 수 있다.
      • 원소들이 인접한 메모리 공간에 모여있을 필요가 없다.
      • 구현이 간단하다.
    • 단점
      • 탐색 시 선형탐색 외에는 다른 방법이 없다. 이때 시간복잡도는 O(N)이다.

  • 큐

    • 사용
      • 선입선출이 필요한 경우에 사용된다.
      • producer-consumer problem
    • 장점
      • 데이터의 삽입, 삭제가 간단하고 빠르다.
    • 단점
      • 큐에 중간에 위치한 데이터로의 접근이 어렵다.

  • 맵

    • 사용
      • 사전과 전화번호부와 같이, 특별한 고유값(이름, ID 등)으로 데이터를 찾을 때 주로 사용한다.
    • 구현
      • 자가균형이진탐색트리 또는 해시테이블 로 구현
        • 자가균형이진탐색트리
          • 최악의 상황에서 O(log N)의 시간복잡도를 가진다.
          • 비교연산이 가능한 모든 데이터는 이진탐색트리로 구현 가능
        • 해시테이블
          • 점근적 복잡도는 해시테이블 이 O(1)으로 이진탐색트리 의 O(log N)보다 좋다. 그러나 최악의 상황에서는 O(N)으로 불리하다.
    • 장점
      • 키값을 이용하여 데이터로 빠르게 접근 가능
    • 단점
      • 자가균형이진탐색트리 의 단점
        • 구현이 복잡하다
        • 트리의 균형도에 따라 최악 탐색시간이 달라진다.
        • 트리의 균형도를 유지하기 위해서는 부가 작업이 필요하다.
      • 해시테이블 의 단점
        • 해시 함수에 의존적이다.
        • 비교적 큰 해시테이블 크기만큼의 메모리를 미리 할당하므로 공간복잡도가 크다.
        • 충돌을 해결하는 알고리즘을 추가적으로 적용해야 한다.