1.9 Kernel Data Structures

 이제 운영 체제 구현에 중요한 주제인 시스템 내의 data structure에 대해 살펴보자.

 

1.9.1 Lists, Stacks, and Queues

 배열은 각 요소에 직접 액세스 할 수 있는 간단한 데이터 구조다. 주 메모리 또한 이러한 배열로 구성되어 있기 때문에 저장되는 데이터 항목이 한 바이트보다 크면 여러 바이트가 항목에 할당되고 "항목 번호 × 항목 크기" 로 주소가 지정된다. 하지만 크기가 다양한 항목을 저장하거나 남은 항목의 상대적 위치를 보존해야하는 경우에는 배열이 다른 데이터 구조로 대체된다.

• Singly Linked List - 그 다음 항목을 가르킴. 마지막은 null
• Doubly Linked List - Singly Linked List에서 확장되어 그 이전의 항목도 가르킴
• Circularly Linked List - 마지막이 첫 번째 요소를 가르킴

 보통 이러한 자료구조는 다른 책에서 다루겠다.

 

Stack

 Stack은 마지막에 들어간 항목이 먼저 나오는 후입선출(LIFO) 원칙을 사용하는 순차적으로 정렬된 데이터 구조이다. 보통 push, pop을 통해 넣고 빼낼 수 있으며, 함수 호출에서 이러한 스택 구조를 사용하여 매개변수, 지역 변수, 반환 주소가 스택에 푸시가 되고, 함수 호출에서 반환이 될 때, 이 항목들이 스택에서 팝된다.

 

Queue

 Queue는 선입선출(FIFO)로 프린터로 전송된 작업들을 제출된 순서로 인쇄가 되게 추상화 하거나, CPU에서 실행되기를 기다리는 작업은 종종 queue에서 대기를 한다. 따라서 우리가 생각하는 대기 줄로 여기서는 기다리는 작업들을 조직화하는 데 자주 사용된다.

 

1.9.2 Trees

 트리는 데이터를 계층적으로 나타내기 위해 사용되는 데이터 구조인데, 이 전과는 반대로 부모-자식 관계라는 성질이 있다. General Tree에서는 부모는 무제한의 자식을 가질 수 있고, Binary Tree에서는 부모가 최대 두 개의 자식만을 가질 수 있고, 이를 각각 왼쪽 자식과 오른쪽 자식이라고 한다. 여기서 Binary Search Tree는 두 자식 사이에 순서가 있어야 한다. 예를 들면 왼쪽 자식이 오른쪽 자식 보다 작거나 같다 라는 규칙이 필요하다는 것이다. BST에서 항목을 검색할 때, 최악의 경우에 성능이 O(n)이고, 이러한 상황을 해결하기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree, AVL)를 생성하는 알고리즘을 사용할 수 있다. 여기서 더 나아가 Linux에서는 Red-Black Tree를 CPU-scheduling algorithm의 일부로 사용하게 된다.

 

1.9.3 Hash Functions and Maps

 해시 함수는 데이터를 입력으로 받아서 해당 데이터에 숫자 연산을 수행한 뒤 숫자 값을 반환하는 함수이다. 이 숫자는 일반적으로 배열로 구성된 테이블 내에서 데이터를 빠르게 검색하기 위한 인덱스로 사용될 수 있다. 크기가 n인 리스트에서 데이터 항목을 검색하는 데는 최대 O(n) 의 비교가 필요할 수 있는데, 해시 함수를 사용한다면 테이블에서 데이터를 검색하는데 거의 O(1)과 같은 상수 시간이 걸리게 할 수 있다.

 해시 함수의 잠재적 위기는 두 개의 고유한 입력이 동일한 출력 값으로 연결될 수 있다는 건데, 같은 테이블 위치로 연결이 될 수 있는 이런 hash collision은 테이블 위치에 모든 동일한 해시 값을 가진 항목을 포함하는 연결 리스트를 만들어 해결할 수 있다. 이는 충돌이 많을 수록 해시 함수의 효율이 떨어지게 된다.

 해시 함수의 사용 예시는 Hash Map을 구현하는 것이다. 해시 함수를 사용하여 키와 값을 매핑하는데 사용되며, 매핑이 한번 설정이 되면, 키에 대한 해시 함수를 적용하여 해시 맵에서 값을 가져올 수 있다.

 

1.9.4 Bitmaps

 비트맵은 n개의 이진 숫자로 이루어진 문자열로, n개의 항목의 상태를 나타내는 데 사용될 수 있다. 비트맵의 장점은 공간 효율성을 고려할 때 드러난다. 그 예로 중형 디스크 드라이브는 몇 천 개의 디스크 블록이라는 개별 단위로 나눌 수 있는데, 비트맵은 각 디스크 블록의 가용성을 나타내는 데 사용될 수 있다.