Egloos | Log-in
F/OSS study
F/OSS study
[Linux] priority search tree (1)
Linux: 2.6.32


priority search tree (이하 PST)는 메모리 페이지의 reverse mapping을 위해 사용되는 자료 구조이다.
즉 해당하는 페이지가 어느 프로세스의 어느 위치에 매핑되어 있는지를 찾아내는 것이다.

이것은 시스템 내의 메모리가 부족할 때 프로세스가 사용하는 메모리 페이지를 해지하기 위해 필요한데
공유 매핑의 경우 하나의 페이지를 여러 프로세스에서 (혹은 한 프로세스 내에서도 여러 위치에서)
참조하고 있을 수 있기 때문에 해당 페이지를 해지하려면 그 페이지를 참조하는 모든 곳의
페이지 테이블을 찾아서 더 이상 페이지가 존재하지 않는다고 표시해야 하기 때문이다.

이러한 작업을 효율적으로 수행하기 위해 매핑된 모든 페이지에 대해 별도의 자료 구조를 두는 대신
해당 페이지를 매핑하는 메모리 구역(vm_area_struct) 별로 관리하는 방법을 사용하는데
이 때 사용되는 것이 바로 PST이다.

PST는 다른 tree 자료 구조와는 좀 다른 특징을 가지는데
각 노드는 하나의 (키) 값을 가지는 것이 아니라 두 개(메모리 구역의 시작과 끝 주소)의 값을 가진다는 것이다.
PST는 radix tree와 heap의 특성을 적절히 혼합한 것으로
메모리 구역의 끝 주소는 heap index로 동작하며 PST는 전체적으로 (max) heap과 비슷한 구조를 갖게 된다.
즉 가장 큰 heap index를 가지는 노드(메모리 구역)가 가장 상위 노드가 된다.
하지만 같은 heap index를 가지며 radix index가 다른 경우가 있을 수 있는데
이러한 경우에는 radix index가 더 작은 노드, 즉 더 넓은 범위를 가지는 메모리 구역이 상위 노드가 된다.
같은 높이(level)에 있는 노드들은 radix index를 통해 정렬하는데
부모 노드가 주어진 높이에서 가질 수 있는 최대 heap index를 계산하여
그 절반보다 작은 radix index를 가지면 left child로, 그렇지 않으면 right child로 들어간다.

더욱이 일반 PST와 달리 리눅스의 reverse mapping에 사용되는 PST는
radix index나 heap index가 동일한 노드가 존재할 수도 있으므로 이를 처리할 수 있어야 한다.
(이러한 경우는 나중에 살펴보기로 한다.)


위의 그림은 6개의 노드로 이루어진 PST를 보여준다.
가장 상위의 root 노드는 heap index 6을 가지며,
오른쪽 자식 노드([5, 6])도 heap index가 6이지만 radix index가 작은 쪽이 부모 노드가 된다.
새로운 노드가 삽입되는 경우는 먼저 heap index를 비교하고 같은 경우에만 radix index를 비교한다.
heap index가 작은 노드가 삽입되는 경우에는 자식 노드가 삽입될 방향을 결정하기 위해
radix index를 살펴보는데, 현재 노드가 (단계별로) 가질 수 있는 heap index의 최대값(2의 지수승)의
절반보다 작으면 왼쪽에, 절반보다 크면 오른쪽에 삽입된다.

최초에 [1, 6] 노드 만 있었을 때 [2, 5] 노드가 삽입되는 경우를 먼저 생각해 보자.
[2, 5] 노드의 heap index는 6보다 작은 5이므로 자식 노드로 삽입되어야 한다.
root 노드의 heap index는 6이므로 현재 트리가 가질 수 있는 최대의 heap index는 2의 지수승이 되므로 2^3 - 1 = 7이며
따라서 0~3 사이의 radix index를 가지는 노드는 왼쪽에 4~7 사이의 index를 가지는 오른쪽에 삽입된다.
[2, 5] 노드는 radix index가 2이므로 [1, 6] 노드의 왼쪽으로 삽입된다.

다음에 [3, 4] 노드가 삽입된다고 하면
먼저 root 노드보다 heap index가 작으므로 자식 노드가 되어야 하는데
radix index가 3이므로 왼쪽으로 삽입된다.
그러면 이제 [2, 5] 노드와 비교를 하는데 역시 heap index가 작으므로 자식 노드가 되며
이번에는 [2, 5] 노드가 가질 수 있는 radix index의 범위인 0 ~ 3을 반으로 나누어
0~1 사이의 값인 경우 왼쪽에, 2~3 사이의 값인 경우 오른쪽에 삽입되는데
따라서 [3, 4] 노드의 경우에는 오른쪽에 삽입된다.

아래는 PST의 삽입 과정을 처리하는 prio_tree_insert() 함수의 코드이다.
(이해를 돕기 위해 주석을 추가하였다.)

struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
        struct prio_tree_node *node)
{
    struct prio_tree_node *cur, *res = node;
    unsigned long radix_index, heap_index;
    unsigned long r_index, h_index, index, mask;
    int size_flag = 0;

    /* 삽입할 노드의 radix index와 heap index를 읽는다 */
    get_index(root, node, &radix_index, &heap_index);

    /*
     * PST가 비어 있거나 삽입될 노드가 현재 PST가 처리할 수 있는 heap index보다
     * 더 큰 heap index를 가진다면 PST를 확장하여 root 노드로 삽입한다.
     */
    if (prio_tree_empty(root) ||
            heap_index > prio_tree_maxindex(root->index_bits))
        return prio_tree_expand(root, node, heap_index);

    /* 비교할 노드: 초기값은 root 노드이다 */
    cur = root->prio_tree_node;
    /* child의 방향을 결정할 때 계산을 쉽게해주는 마스크 값 */
    mask = 1UL << (root->index_bits - 1);

    while (mask) {
        /* 현재 비교할 노드의 radix index와 heap index를 읽는다 */
        get_index(root, cur, &r_index, &h_index);

        /* 완전히 동일한 노드라면 처리할 수 없다! 기존의 노드를 반환한다 */
        if (r_index == radix_index && h_index == heap_index)
            return cur;

        /*
         * 삽입된 노드의 heap index가 현재 비교 중인 노드의 heap index보다 크거나
         * heap index는 같고 radix index가 더 작다면 현재 노드를 삽입된 노드로 바꾸고
         * 원래의 노드를 아래로 추가한다
         */
        if (h_index < heap_index ||
            (h_index == heap_index && r_index > radix_index)) {
            struct prio_tree_node *tmp = node;
            node = prio_tree_replace(root, cur, node);
            cur = tmp;
            /* swap indices */
            index = r_index;
            r_index = radix_index;
            radix_index = index;
            index = h_index;
            h_index = heap_index;
            heap_index = index;
        }

        /*
         * size_flag는 tree가 가득찬 경우에 설정된다.
         * size_flag가 설정되어 있다면 원래의 PST의 leaf 노드에
         * 동일한 radix index를 가지는 노드마다 overflow subtree라는
         * 별도의 PST가 생성된다. 하지만 이 경우 트리 내의 모든 노드는
         * 같은 radix index를 가지므로 대신 노드의 크기("size")
         * (즉, heap_index - radix_index 값)를 index로 사용하여
         * 트리를 구성한다.
         */
        if (size_flag)
            index = heap_index - radix_index;
        /*
         * 그렇지 않은 (일반적인) 경우라면 radix index를 이용한다
         */
        else
            index = radix_index;

        /*
         * 현재 index와 mask 값을 비교하여 자식 노드가 추가될 방향을 결정한다.
         * mask에는 현재 level의 최대값의 절반에 해당하는 비트 만이 설정되어 있으므로
         * mask에 해당하는 비트값이 설정되어 있다는 것은 오른쪽 자식이 됨을 의미한다.
         */
        if (index & mask) {
            /* 오른쪽 자식 노드가 비어있었다면 추가하고 종료한다 */
            if (prio_tree_right_empty(cur)) {
                INIT_PRIO_TREE_NODE(node);
                cur->right = node;
                node->parent = cur;
                return res;
            /* 그렇지 않다면 오른쪽 자식 노드와 다시 비교한다 */
            } else
                cur = cur->right;
        /* mask 비트가 설정되어 있지 않으면 왼쪽으로 삽입된다 */
        } else {
            /* 왼쪽 자식 노드가 비어있었다면 추가하고 종료한다 */
            if (prio_tree_left_empty(cur)) {
                INIT_PRIO_TREE_NODE(node);
                cur->left = node;
                node->parent = cur;
                return res;
            /* 그렇지 않다면 왼쪽 자식 노드와 다시 비교한다 */
            } else
                cur = cur->left;
        }

        /*
         * 여기까지 왔다면 자식 노드와 다시 비교해야 함을 의미한다.
         * 다음 번에 추가될 방향을 결정하기 위해 mask 비트를 갱신한다.
         */
        mask >>= 1;

        /*
         * 만약 mask 비트가 0이 되었다면 해당 노드를 삽입하기 위한 경로 내의
         * 모든 노드가 이미 존재하기 때문에 더 이상 트리에 노드를 추가할 수 없다.
         * 이제 노드의 size를 index로 하는 overflow subtree를 구성하기 위해
         * size_flag를 설정하고 mask를 최대값으로 설정한다.
         */
        if (!mask) {
            mask = 1UL << (BITS_PER_LONG - 1);
            size_flag = 1;
        }
    }
    /* Should not reach here */
    BUG();
    return NULL;
}

위의 코드에서 흥미로운 부분은 mask 변수와 size_flag 변수에 대한 부분이다.

먼저 mask 변수를 보자면 위의 그림에서 최대 heap_index는 6이었으므로
root->index_bits는 3이되고 (2^3 = 8) 따라서 mask의 초기값은 4가 된다.
이것은 root 노드의 자식 노드 방향을 결정할 때 0~3과 4~7로 나누었으므로
단순히 4 (0b100) 비트가 설정되었는지를 비교하면 간단해진다.
마찬가지로 다음 자식 노드에서 0~1과 2~3를 결정하는 경우나
4~5와 6~7을 결정하는 경우에도 2 (0b10) 비트 만을 비교하면 된다.
(위의 그림에서 가장 오른쪽에 mask 값을 볼 수 있다.)

size_flag는 트리가 가득 찬 경우에 설정된다고 했는데
위의 그림에서 아래와 같이 [0, 0], [0, 1], [0, 2] 노드가 새로 추가되는 경우를 생각해보면 알 수 있다.


prio_tree_insert() 함수를 따라가보면 트리가 가득찬 경우
PST의 leaf 노드 아래에는 동일한 radix index를 가지는 노드들이 모이게 된다.
특이한 점은 subtree를 구성할 때 mask를 최대값(2^31)으로 설정한다는 점인데
이로 인해 대부분의 노드는 왼쪽 자식으로 삽입되어 simle linked list와 비슷하게 된다.

왜 현재 root의 index_bits 만큼 증가시키지 않고 최대값으로 했을까 고민을 좀 해 보았는데
(나름대로 생각해 본 결과) subtree의 경우에는 PST와 달리 최대값이 동적으로 증가되는 경우
expand()에 해당하는 연산을 처리하기가 까다롭고 (만약 이를 처리한다고 하면
모든 leaf 마다 subtree가 있는지 검사하여 expand() 함수를 호출해야 하는데
노드가 많은 경우 성능에 좋지 않은 영향을 미치게 될 것이다),
대부분의 경우 overflow subtree의 높이가 그리 크지 않을 것이므로
지금처럼 처리해도 크게 문제될 것이 없는 듯 하다.

by namhyung | 2009/12/11 19:06 | Kernel | 트랙백(1) | 덧글(1)
트랙백 주소 : http://studyfoss.egloos.com/tb/5194196
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from F/OSS study at 2009/12/12 00:18

제목 : [Linux] priority search tree..
Linux: 2.6.32 이전 글 보기 : [Linux] priority search tree (1) 이번에는 PST에서 노드를 삭제하는 과정을 살펴보도록 하자. 특정한 노드를 삭제할 때 해당 노드가 leaf라면 그냥 삭제하고 부모 노드에서 포인터 만 끊어주면 된다. leaf가 아니라면 child 노드 중에서 heap index가 큰 쪽을 끌어올린다. 마찬가지로 두 child의 heap index가 동일하다면 (radix i......more

Commented by namhyung at 2009/12/11 23:43
지금 확인해 본 결과 UTLK (리눅스 커널의 이해) 3판에 나온 그림 17-2는 잘못 되었다. 그림의 트리는 완벽히 균형을 이루고 있는데 자세히 살펴보면 오른쪽 노드의 radix index는 4보다 작으므로 오른쪽에 있을 수 없다! 모든 노드는 왼쪽으로 옮겨져야 하고 일부는 overflow subtree를 구성해야 한다. 이렇게 그리면 트리가 길어져서 공간을 많이 차지하니까 일부러 그렇게 그렸을까? @.@;;

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
binutils perf kernel sed synchronization SMP block-layer documentation blktrace algorithm git scm script awk CAaQA3 linux CARM gcc computer-architecture x86 compiler elf bash C vcs build glibc memory patch emacs
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan be..
by pordanaia at 08/05
Informsi yang bagus dan b..
by jamalsu at 08/01
as inforasi yang menarik http..
by jamalsu at 07/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X