-
- 개념
- 일반적인 연결리스트
- 구조체를 연결리스트로 만드는 개념
- 리눅스의 연결리스트
- 구조체 안에 연결리스트 노드를 넣는 개념
- 일반적인 연결리스트
- 리눅스 연결리스트 의 장점
list_head
구조체를 정의해놓고, 계속 재사용하면 된다. 코드 중복을 줄일 수 있고, 코드 재사용이 가능하다.- 구조체를 연결리스트로 구현하고 싶을 때,
prev
,next
포인터를 선언하는 것 대신list_head
구조체를 포함하면 되므로 가독성이 좋고, 유지보수가 용이하다. C
에는 제네릭이 없다. 따라서 일반적인 연결리스트 로 모든 연결리스트를 구현하면 인자의 타입만 다르고 몸체가 비슷한 함수들을 각 구조체별로 구현해야 할 것이다. 그에 반해 리눅스 연결리스트 는list_head
연결리스트의 함수들을 모든 구조체에서 사용할 수 있다.
- 연결리스트 노드를 구조체 안에 넣는다면, 부모 구조체의 데이터들에는 어떻게 접근할까?
- 구조체의 주소와 구조체 내 멤버의 주소 차이 (offset) 가 컴파일 시간에 정해지는 특성을 이용하여 부모 구조체에 접근한다.
container_of
매크로는 이미 우리가 알고 있는list_head
구조체의 주소에서 컴파일 시간에 결정된 부모 구조체와list_head
의 offset 을 뺀다. 그 결과로 부모 구조체의 주소를 얻을 수 있다.
- 개념
-
rbtree
의 기본 법칙들을 만족하면서, 세세한 구현 부분 (최적화 부분) 을 리눅스의 사정에 맞게 바꿨을 것이다.- 구체적인 차이점을 알기가 쉽지 않아서, 각자의 개인적인 생각을 공유하였다.
rbtree
는CFS스케줄러
에 사용된다. 이때vruntime
이 가장 적은 프로세스를 빠르게 선택하기 위해rbtree
의 제일 왼쪽 자식을cache
에 보관한다. 이렇게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)
으로 불리하다.
- 점근적 복잡도는 해시테이블 이
- 자가균형이진탐색트리
- 자가균형이진탐색트리 또는 해시테이블 로 구현
- 장점
- 키값을 이용하여 데이터로 빠르게 접근 가능
- 단점
- 자가균형이진탐색트리 의 단점
- 구현이 복잡하다
- 트리의 균형도에 따라 최악 탐색시간이 달라진다.
- 트리의 균형도를 유지하기 위해서는 부가 작업이 필요하다.
- 해시테이블 의 단점
- 해시 함수에 의존적이다.
- 비교적 큰 해시테이블 크기만큼의 메모리를 미리 할당하므로 공간복잡도가 크다.
- 충돌을 해결하는 알고리즘을 추가적으로 적용해야 한다.
- 자가균형이진탐색트리 의 단점
- 사용
-