커널은 페이지 IO를 하기 전에 항상 페이지 캐시에 원하는 페이지가 있는가를 검사해야 한다.
이러한 검사는 빠르게 이루어져야 한다. 그렇지 않다면 페이지 캐시를 검색하고 조사하는 시간 때문에 캐시를 사용하는 의미가 없어질 것이기 때문이다.
앞에서 살펴보았듯이 페이지 캐시를 찾기 위해서는 address_space 객체와 오프셋값을 사용한다.
각 address_space는 page_tree라는 고유의 래딕스 트리를 갖는다. 래딕스 트리란 바이너리 트리의 일종으로, 이것은 파일의 오프셋만 가지고도 해다아 페이지를 빠르게 찾을 수 있도록 해준다. find_get_page()와 같은 페이지 검색 함수는 radix_tree_lookup() 함수를 호출하는데, 이것은 바로 이러한 래딕스 트리를 이용하게 된다.
래딕스 트리의 중요 코드느느 lib/radix-tree.c에 있다.
낡은 페이지 해시 테이블
2.6커널 이전에는 페이지 캐시에서 래딕스 트리 대신, 시스템의 모든 페이지에 대한 전역적인 해시를 사용했다. 이 해시는 주어진 값과 동일한 해시값을 갖는 항목들의 이중 연결리스트를 리턴해 주었다. 만약 원하는 페이지가 캐시에 있다면, 이 리스트 중의 한 항목이 바로 그페이지다.
이러한 해시 테이블은 다음과 같은 문제점이 있다.
하나의 전역 락이 해시를 보호한다. 부하가 중간정도인 시스템에서도 락 경쟁이 심하다.
해시가 시스템의 모든 페이지를 포함하고 있으므로, 해시의 크키가 너무 컸다. 그에 반해, 현재 파일과 관련된 페이지만을 갖고 있는 경우에는 적당했다.
해시 참조가 실패한 경우의 처리가 너무 느렸는데, 특히 해시값에 해당하는 리스트를 순회하는 부분이 매우느렸다.
해시는 다른 알고리즘보다 많은 메모리를 소모하는 경향이 있다.
2.6커널에서 도입된 래딕스 트리 기반 페이지 캐시는 위의 모든 문제점을 해결했다.
이러한 검사는 빠르게 이루어져야 한다. 그렇지 않다면 페이지 캐시를 검색하고 조사하는 시간 때문에 캐시를 사용하는 의미가 없어질 것이기 때문이다.
앞에서 살펴보았듯이 페이지 캐시를 찾기 위해서는 address_space 객체와 오프셋값을 사용한다.
각 address_space는 page_tree라는 고유의 래딕스 트리를 갖는다. 래딕스 트리란 바이너리 트리의 일종으로, 이것은 파일의 오프셋만 가지고도 해다아 페이지를 빠르게 찾을 수 있도록 해준다. find_get_page()와 같은 페이지 검색 함수는 radix_tree_lookup() 함수를 호출하는데, 이것은 바로 이러한 래딕스 트리를 이용하게 된다.
래딕스 트리의 중요 코드느느 lib/radix-tree.c에 있다.
낡은 페이지 해시 테이블
2.6커널 이전에는 페이지 캐시에서 래딕스 트리 대신, 시스템의 모든 페이지에 대한 전역적인 해시를 사용했다. 이 해시는 주어진 값과 동일한 해시값을 갖는 항목들의 이중 연결리스트를 리턴해 주었다. 만약 원하는 페이지가 캐시에 있다면, 이 리스트 중의 한 항목이 바로 그페이지다.
이러한 해시 테이블은 다음과 같은 문제점이 있다.
하나의 전역 락이 해시를 보호한다. 부하가 중간정도인 시스템에서도 락 경쟁이 심하다.
해시가 시스템의 모든 페이지를 포함하고 있으므로, 해시의 크키가 너무 컸다. 그에 반해, 현재 파일과 관련된 페이지만을 갖고 있는 경우에는 적당했다.
해시 참조가 실패한 경우의 처리가 너무 느렸는데, 특히 해시값에 해당하는 리스트를 순회하는 부분이 매우느렸다.
해시는 다른 알고리즘보다 많은 메모리를 소모하는 경향이 있다.
2.6커널에서 도입된 래딕스 트리 기반 페이지 캐시는 위의 모든 문제점을 해결했다.
