리눅스 커널은 page cache라고 불리는 디스크 캐시를 구현한다. 이 캐시의 목적은 디스크 접근을 요청하지 않으면 데이터를 물리적 메모리에 저장하는 것으로 디스크의 I/O를 최소화 하는 것이다. 이 챕터에서는 페이지 캐시와 페이지 캐시를 바꾸고 디스크로 다시 전파시키는 프로세스(page writeback)에 대해 다룬다.
두 요소가 결합되어 디스크 캐시를 어떤 현대 운영체제에서도 중요한 요소로 만든다. 첫째로 디스크 접근은 메모리 접근보다 몇배는 더 느리다-밀리초 대 나노초. 메모리에서 데이터에 접근하는 것이 더 빠르고, 프로세서의 L1 혹은 L2 캐시에서 데이터에 접근하는게 더 빠르다. 두번째로 한번 접근한 데이터는 빠른 시일 내에 다시 접근될 가능성이 높다. 이 원칙은 temporal locality라고 불린다. 앞서 말한 두가지 요소때문에 메모리상의 디스크 캐시는 큰 성능 이점을 가져온다.
페이지 캐시는 RAM의 물리적 페이지로 구성되어있다. 페이지 캐시의 크기는 동적이다. 캐싱된 저장기기를 backing store(백업 저장소)라고 하는데, 이는 디스크가 캐시 데이터의 정식버전 자원으로써 존재하기 때문이다. 커널이 읽기 작업을 시작한다면, 일단 페이지 캐시에 요청한 데이터가 있는지 확인한다. 만약 있다면 커널은 디스크에 접근하는 것을 포기하고 RAM에서 데이터를 읽어오며, 이를 cache hit라고 한다. 데이터가 캐시에 없다면(cache miss) 커널은 디스크에서 데이터를 읽어오기 위해 블록 I/O작업을 스케줄링해야한다. 데이터를 다 읽은 후에 커널은 페이지 캐시를 데이터로 채워 다음 읽기가 캐시에서 발생할 수 있도록 한다. 전체 파일이 캐시될 필요는 없다; 페이지 캐시는 약간의 파일을 붙잡고 있을 수 있다(다른 파일은 하나에서 두 페이지 정도). 캐시되는 것은 접근되는 것에 의존적이다.
일반적으로 캐시는 3개의 다른 전력중 한 방법을 통해 쓰기를 구현한다. 첫번째 방법인 no-write에서는 캐시 write하지 않는다. 캐시에 저장된 데이터에 대한 쓰기 작업은 직접적으로 디스크에 쓰여지며, 동시에 캐시된 데이터를 무효화한다. 자주 사용되지는 않는 방법이다.
두번째 방법은 쓰기 작업은 자동으로 메모리상의 캐시와 디스크의 파일을 업데이트한다. 이 방법은 write-through로 불린다. 이러한 접근은 캐시를 일관되게하고, 간단하다.
리눅스가 고안한 세번째 방법은 write-back이다. Write-back 캐시에서는 프로세스는 쓰기 작업을 페이지 캐시에 직접 수행한다. 백업 저장소는 바로 혹은 직접적으로 업데이트되지 않는다. 대신, 페이지 캐시의 쓰기 대상 페이지들은 dirty로 표시되거나 혹은 dirty list에 추가된다. 주기적으로 더티 리스트의 페이지들을 디스크로 쓰는 과정이 있는데 이를 writeback이라 한다. 이후 페이지는 dirty로 표시되지 않는다. Dirty라는 용어는 페이지 캐시의 데이터를 의미하는 것이 아닌 디스크상의 데이터를 의미한다. 혼동을 막기 위해 unsynchronized라는 용어를 쓰기도 한다. Write-back은 디스크에 쓰기를 지연시킴으로써 합쳐지고 한번에 수행될 수 있기 때문에 write-through 방법보다 우수하다고 여겨진다. 단점은 복잡함이다.
캐싱의 마지막 단계는 어떤 데이터가 캐시에서 삭제되었는지 확인하는 프로세스이다(더 관련된 캐시 엔트리를 추가하거나, RAM 공간을 확보하기 위해 캐시를 줄여야 하는 경우). 이 일련의 과정을 cache eviction이라고 부른다. 리눅스의 cache eviction은 clean한 페이지를 찾고 다른것과 교체함으로써 동작한다. 만약 clean page가 캐시에 부족하다면 커널은 강제로 writeback을 통해 사용할 수 있는 clean page를 만들 수 있다. 어떤 것을 방출할 지 정하는 것이 가장 어렵다. 이상적인 방출 전략은 미래에 사용될 확률이 낮은 페이지를 방출하는 것(clairvoyant 알고리즘)이다. 하지만 이를 구현하는 것은 거의 불가능에 가깝다.
캐시 방출 전략은 clairvoyant 알고리즘에 근접하고자 시도한다. 그중 가장 일반적으로 사용되는 알고리즘이 least recenly used(LRU) 방법이다. LRU 방출전략은 페이지가 접근된 시점을 계속 추적하고, 그 시기(timestamp)가 가장 오래된 것을 방출한다. 오랜기간 사용되지 않은 데이터는 가까운 미래에 접근될 가능성이 적다는 이유이다. LRU 기법의 단점은 많은 파일들이 한번만 접근되고 이후에는 사용되지 않는 다는 것이다. 그렇기 때문에 LRU 목록의 상단에 놓는 것은 최적의 방법이 아니라는 것이다.
리눅스는 LRU의 수정버전인 two-list 전략을 구현했다. LRU 리스트 하나만 유지하는 대신 리눅스는 active 리스트와 inactive 리스트의 두 리스트를 유지한다. Active 리스트의 페이지는 hot한 것으로 간주되어 방출될 수 없다. Inactive 리스트의 페이지는 캐시 방출이 가능하다. 페이지는 inactive 리스트에 있던 페이지가 접근된 경우에만 active 리스트로 이동한다. 두 리스트 모두 pseudo-LRU 방법으로 유지된다: 끝에 추가되고, 앞에서부터 제거된다. 리스트는 균형을 이룬다: active 리스트가 더 커지면 active 리스트의 앞쪽에 있는 요소들이 inactive 리스트로 이동된다. Two-list 전략은 파일이 한번만 사용될 가능성이 높은데에서 비롯되는 실패들을 해결한다. 이 전략을 LRU/2라고 알려져있고, n개의 리스트를 이용하면 LRU/n으로 표기한다.
페이지 캐시는 RAM의 페이지의 캐시이다. 일반 파일시스템 파일, 블록 기기 파일, 메모리 매핑된 파일을 읽고 쓰는 것으로부터 페이지가 생성된다. 이 방법으로, 페이지 캐시는 최근에 접근한 파일의 조각을 포함한다. 페이지 I/O 작업동안 커널은 데이터가 페이지 캐시에 있는지 확인하고, 있다면 빠르게 요청한 페이지를 메모리에서 전달한다.
페이지 캐시의 페이지는 불연속적인 여러 물리 디스크 블록으로 구성된다. 이러한 불연속성 때문에 특정 데이터가 캐시되어있는지 확인하는 것이 어렵게 되어있다. 따라서 기기명과 블록 번호만을 가지고 페이지 캐시에 있는 데이터를 색인하는 것은 불가능하다. 게다가 리눅스 페이지 캐시는 꽤나 일반적이다. 실제로 SVR4에서의 페이지 캐시는 파일 시스템 데이터만 캐시했다. 결과적으로 SVR4 페이지 캐시는 struct vnode
라고 불리는 inode 객체와 동일한 것을 이용해 페이지 캐시를 관리했다. 리눅스 페이지 캐시는 다양한 형태의 파일과 메모리 매핑을 포함하는 어떠한 페이지 기반의 객체를 캐시하는 것을 목표로한다.
리눅스 페이지 캐시는 페이지 I/O 연산을 지원하기 위해 inode 구조체를 확장함으로써 동작할 수 있지만, 그러한 결정이 페이지 캐시를 파일로 제한한다. 일반 페이지 캐시를 유지하기 위해, 리눅스 페이지 캐시는 새로운 객체를 이용해 캐시의 엔트리와 페이지 I/O 작업을 관리한다. 그 오브젝트를 address_space
라고 한다. 15장 vm_area_struct
의 물리적 아날로그로써 address_space
를 생각해보자. 하나의 파일이 10개의 vm_area_struct
로 표현된다면, 파일은 하나의 address_space
만을 가진다 - 파일이 많은 가상 주소를 가지고 있지만, 물리적 메모리에 한번만 존재하는 것과 같다.
address_space
구조체는 <linux/fs.h>에 정의되어있다.
i_mmap
필드는 이 주소 공간의 모든 공유되어있고 개인의 매핑의 우선순위 탐색 트리이다. 우선순위 탐색 트리(priority search tree)는 heap과 radix tree를 합친 것이다. i_mmap
필드를 통해 커널은 연관된 캐시파일의 매핑을 효율적으로 찾을 수 있다.
nrpages
는 이 주소 공간의 전체 페이지 수를 나타낸다.
address_space
는 몇몇 커널 객체와 연관되어 있는데 보통은 inode와 연관된다. 이 경우, host
필드는 관련된 inode를 가리킨다. 반대로 inode와 연관되어있지 않다면 host
필드는 NULL값을 가진다.
a_ops
필드는 주소 공간 연산 테이블을 가리킨다(VFS 객체가 연산 테이블을 가리키는 것과 동일; 연관 메소드 모음). 연산 테이블은 struct address_space_operations
로 표현되며 <linux/fs.h>에 정의되어있다.
페이지 캐시를 관리하는 함수들로 이루어져있고, 가장 흔한 페이지를 캐시로부터 읽고 캐시에 데이터를 업데이트 하는 함수도 포함한다. readpage()
와 writepage()
메소드가 가장 중요하므로, 단계별로 확인해보겠다.
먼저 readpage()
와 관련된 예제 코드는 아래와 같다.
struct page *page;
int error;
// 1. find and get page
page = find_get_page(mapping, index);
if(!page) {
// 2. allocate the page
page = page_cache_alloc_cold(mapping);
if(!page) /* error allocating memory */
// 3. add to page cache
error = add_to_page_cache_lru(page, mapping, index, GFP_KERNEL);
if(error) /* error adding page to page cache */
error = mapping->a_ops->readpage(file, page);
}
첫째로 리눅스 커널이 find_get_page()
함수를 통해 페이지 캐시에서 요청받은 데이터를 찾는다. 만약 함수가 NULL을 반환한다면 캐시에 페이지가 존재하지 않는다는 의미이며, 새로운 페이지를 할당하고 페이지 캐시에 추가해야한다. 이후 요청받은 데이터를 디스크에서 읽어 페이지 캐시에 추가하고 유저에게 반환할 수 있다.
다음으로 writepage()
와 관련된 예제 코드는 아래와 같다.
// 페이지가 변경되지 않아도 실행
SetPageDirty(page);
page = __grab_cache_page(mapping, index, &cached_page, &lru_pvec);
status = a_ops->prepare_write(file, page, offset, offset+bytes);
page_fault = filemap_copy_from_user(page, offset, buf, bytes);
status = a_ops->commit_write(file, page, offset, offset+bytes);
페이지 캐시를 탐색하고, 캐시에 없다면 엔트리가 할당되고 추가된다. 이후 커널이 쓰기 요청을 설정하고 데이터가 user-space에서 커널의 버퍼로 복사된다. 그리고 마지막엔 데이터가 디스크에 쓰여진다.
커널이 페이지 I/O를 시작하기 전 페이지가 페이지 캐시에 존재하는지 확인해야하기 때문에 이 과정이 빨라야한다. 그렇지 않으면 페이지 캐시를 체크하고 탐색하는 오버헤드가 캐시가 제공하는 장점을 무효화한다. 페이지 캐시는 address_space
객체와 offset 값으로 탐색된다. 각각의 address_space
는 고유의 radix tree를 가지고 있다(page_tree
). Radix tree는 이중 트리의 한 종류로, offset만 가지고 필요한 페이지를 빠르게 탐색하는것을 가능하게 한다.
리눅스 커널 2.6버전 이전에는 페이지 캐시가 radix tree로 탐색되지 않았다. 대신 전역 해시가 시스템 전반의 페이지에 유지되었다. 해시는 이중 연결 리스트를 반환한다. 만약 필요한 페이지가 캐시에 있다면 리스트의 요소중 하나가 대응되는 페이지이다. 그렇지 않으면 페이지는 페이지 캐시에 없고, 해시함수는 NULL을 반환한다.
전역 해시는 4개의 주요 문제점이 있었다.
개별 디스크 블록 역시 블록 I/O 버퍼를 통해 페이지 캐시에 연결된다. 14장에서를 떠올려보면, 버퍼는 단일 물리 디스크 플록의 메모리상의 포현이다. 버퍼는 메모리상의 페이지를 디스크 블록과 매핑하는 디스크립터로써 동작한다: 따라서 페이지 캐시는 디스크 블록을 캐시하고 블록 I/O 연산을 나중에 버퍼링함으로써 블록 I/O 연산동안 디스크 접근을 줄일 수 있다. 이러한 캐싱은 buffer cache로 여겨진다.
블록 I/O 연산은 한번에 하나의 디스크 블록을 조작한다. 일반적인 블록 I/O 연산은 inode를 읽고 쓰는 것이다. 커널은 디스크에서 단일 블록을 읽는 로우레벨의 bread()
함수를 제공한다. 버퍼를 통해 디스크 블록은 연관된 메모리상의 페이지와 매핑되고, 페이지 캐시에 캐시된다.
버퍼와 페이지 캐시는 항상 통합되어있지 않았다. 초창기 커널에서는 두개의 분리된 디스크 캐시가 있었다. 페이지 캐시는 페이지를 캐시하고, 버퍼 캐시는 버퍼를 캐시했다. 두 캐시가 분리되어있는 덕분에 디스크 블록은 두 캐시가 공존할 수 있었다. 이는 두 캐시를 동기화 하는 노력을 낭비하게 하였고, 캐시된 항목을 복제하면서 메모리도 낭비하게 하였다. 오늘날 우리는 하나의 디스크 캐시인 페이지 캐시만을 이용한다. 커널이 여전히 버퍼를 이용하긴 하나, 이는 메모리 상의 디스크 블록을 나타내기 위함이다.
쓰기 작업은 페이지 캐시에서 뒤로 밀려난다. 페이지 캐시의 데이터가 백업 저장소의 데이터보다 새로운 것이라면, 우리는 그 데이터를 dirty하다고 표현한다. 메모리에 축적된 dirty page는 결국 디스크에 쓰여질 필요가 있다. Dirty page writeback은 세가지 상황에 발생한다.
sync()
혹은 fsync()
시스템 콜을 실행시키면, 커널은 writeback을 수행한다.이 3가지 상황은 다른 목표를 가지고 있다. 이전 커널에서는 두개의 분리된 커널 쓰레드가 작업을 수행했는데, 리눅스 커널 2.6버전부터 flusher threads라는 커널 쓰레드의 gang이 세 작업을 모두 수행한다.
CS에서의 'gang'
병렬적으로 수행할 수 있는 그룹을 의미한다.
첫째로 flusher 쓰레드는 특정 레벨까지 여유 메모리가 감소하면 dirty 데이터를 디스크로 작성해야한다. 이는 가용 물리적 메모리가 부족할 때 dirty 페이지가 가지고 있던 메모리를 다시 취득하는 것이 목적이다. 이 프로세스가 시작하는 메모리 레벨은 dirty_background_radio sysctl에 의해 설정되어있다. 여유 메모리가 임계치 이하로 떨어지면 커널은 wakeup_flusher_threads()
를 호출해 하나 이상의 flusher 쓰레드를 깨우고, 이 쓰레드들은 bdi_writeback_all()
함수를 수행한다. 이 함수는 다음 두가지 조건을 만족할 때 까지 실행된다.
다음 조건들은 flusher 쓰레드가 메모리 부족 조건을 해결함을 보장한다. Writeback은 flusher 쓰레드가 모든 dirty 페이지를 작성해서 더이상 할게 없을 때만 조건을 만족하기 전에 종료한다.
두번째로 flusher 쓰레드는 주기적으로 깨어나서 오래된 dirty 페이지를 작성한다. 이는 어떠한 dirty 페이지도 메모리에 영원히 남지 않게 하기 위함이다. 시스템 실패동안에는 메모리가 휘발되기 때문에 디스크에 작성되지 못한 메모리의 dirty 페이지는 사라진다. 결론적으로 주기적으로 페이지캐시를 디스크와 동기화 하는 것은 중요하다. 시스템 부팅시에, 타이머가 초기화되어 flusher 쓰레드를 깨우고, wb_writeback()
함수를 실행한다. 이 함수는 dirty_exprie_interval 밀리초보다 더 전에 수정된 모든 데이터를 작성해나간다. 타이머는 dirty_expire_interval 밀리초 단위로 만료되며 다시 초기화된다. 이 방법으로 flusher 쓰레드는 주기적으로 깨어나 특정 기간보다 오래된 모든 dirty 페이지를 디스크에 작성한다.
Laptop 모드는 하드디스크 활동을 줄이고 하드 드라이브를 가능한 길게 돌지 않도록(spin donw) 유지함으로써 배터리 수명을 최적화 하기위한 특별한 페이지 writeback 전략이다. 기본값으로, 이 모드는 비활성화 되어있다.
Laptop 모드는 페이지 writeback에 하나의 변화를 가져온다. Dirty page가 너무 오래되면 writeback을 수행하는 것 외에도, flusher 쓰레드는 다른 물리적 디스크 I/O를 piggyback off하여 모든 dirty 버퍼를 디스크에 플러시 한다. 이 방법으로, 페이지 writeback은 방금 디스크가 돌기 시작해 나중에 디스크가 돌지 않도록 하는 이점을 가진다.
이 변화는 dirty_expire_interval과 dirty_writeback_interval이 10분과 같이 큰 수로 설정된 경우에 가장 합리적이다. Writeback이 많이 지체된 상태로, 디스크는 거의 돌지 않을 것이며 돌기 시작하면 laptop 모드를 통해 기회를 잘 활용할 수 있다. 디스크 드라이브를 종료하는 것이 주요한 전력 절약의 요소이기 때문에 laptop 모드는 노트북의 배터리 지속시간을 크게 향상시킬 수 있다. 단점은 시스템 충돌 및 다른 실패로 많은 데이터를 잃을 수 있다.
많은 리눅스 배포판에서 배터리가 켜지고 꺼지는 것에 따라 자동으로 laptop 모드를 활성화 및 비활성화 한다. 이는 배터리 전력을 이용할 때는 laptop 모드로 실행하고, AC가 연결되면 기본 page writeback 모드로 전환하도록 한다.
리눅스 커널 2.6버전 이전에는 flusher 쓰레드의 작업은 다른 두 커널 쓰레드 bdflush와 kupdated가 담당했다.
bdflush 커널 쓰레드는 가용 메모리가 적을 때 dirty 페이지의 백그라운드 writeback을 담당했다. 임계치들이 유지되었고, bdflush는 wakeup_bdflush()
를 통해 깨어났다.
Flusher 쓰레드와 bdflush를 구분할 수 있는 두가지 차이점이 있다. 첫째는 bdflush 대몬은 언제나 하나만 존재한다는 것이다. 두번째 차이점은 bdflush가 버퍼 기반이다. 반대로 flusher 쓰레드는 페이지 기반이다. 실제 I/O 단위가 풀 페이지이지 단일 버퍼가 아니기 때문에 다르다고 할 수 있다. 페이지가 더 일반적인 단위이기 때문에 이를 관리하는 것이 버퍼를 관리하는 것보다 더 쉽다.
bdflush가 메모리가 부족하거나 버퍼의 수가 너무 많을 때만 플러시하기때문에, kupdated 쓰레드가 등장해 주기적으로 dirty 페이지를 writeback한다.
리눅스 커널 2.6 버전에서 bdflush와 kupdated에서 pdflush 쓰레드로 넘어왔다. pdflush는 page dirty flush의 약자로, 이 쓰레드는 flusher 쓰레드와 비슷하게 작동한다. 주요한 차이점은 pdflush 쓰레드의 수가 동적이라는 것이다(기본적으로 2-8 사이, 시스템의 I/O 로드에 따라 다름). pdflush 쓰레드는 특정 디스크와 연관되지 않고, 시스템의 모든 디스크에 전역적이다. 단점은 pdflush가 복잡한 디스크에서 쉽게 실수하고, 현대 하드웨어에서 쉽게 혼잡이 발생한다는 점이다. 스핀당 플러시로 전환하면 I/O 가 동기적으로 작동하게 되어 혼잡한 로직을 간단하게 하고 성능이 향상된다. flusher 쓰레드는 pdflush 쓰레드들 2.6.32 커널에서 대체하였다.
bdflush 해결책의 가장 큰 결함은 하나의 쓰레드로 구성된다는 점이다. 이는 무거운 페이지 writeback 작업동안 단일 bdflush 쓰레드가 혼잡한 기기 큐를 블락하고, 다른 기기의 큐는 상대적으로 게으른 혼란상태를 야기한다. 만약 시스템이 여러 디스크와 관련 처리 전력이 있다면, 커널은 디스크를 바쁘게 유지해야한다. 불행하게도, 많은 데이터가 writeback을 필요로 함에도 bdflush는 단일큐를 처리하다 멈추고 모든 디스크를 포화상태를 유지하지 못한다. 이는 디스크의 처리량이 유한하기 때문이고, 비교적 작은 처리량이기 때문이다. 단일 쓰레드가 페이지 writeback을 수행하는 동안, 그 쓰레드는 긴시간 단일 디스크를 기다릴 가능성이 높다(디스크 처리량이 원인). 이를 완화하기 위해 커널은 멀티쓰레드 페이지 writeback이 필요하고, 이를 통해 특정 단일 큐가 병목이 되는 것을 막을 수 있다.
리눅스 커널 2.6버전에서는 여러 flusher 쓰레드가 존재하도록 하여 문제를 해결한다. 각각의 쓰레드는 다른 flusher 쓰레드가 다른 기기 큐에 집중하도록 둔 채로 각각 dirty 페이지를 디스크로 플러시한다. pdflush로 인해 쓰레드의 수는 동적이고, 각각의 쓰레드는 계속해 superblock당 dirty 리스트에서 데이터를 끌어다 디스크에 작성하고자 노력하였다. 허나, 만약 각각의 pdflush 쓰레드가 같은 혼잡한 큐에 쓰기작업을 진행될 때를 생각해보면, 여러 pdflush 쓰레드의 성능은 단일 쓰레드의 성능 이상으로 향상하기 어려울 것이다. 메모리 사용량을 무척 클것이다. 이를 해결하기 위해 pdflush 쓰레드는 혼잡을 피한다: 혼잡하지 않은 큐에만 페이지 writeback을 시도한다. 결과적으로 pdflush 쓰레드는 같은 기기에 대해서만 하지 않고 일을 분산해 작업한다.
하지만 이런 시도도 혼잡을 피하는게 완벽하진 못했다. 현대 시스템에서는 I/O 버스 기술의 향상으로 혼잡이 발생하기 쉬워졌다(프로세서는 무어의 법칙과 같이 계속 빨라져왔지만, 하드 드라이브는 20여년 전과 비교해 약간 빨라졌을 뿐이다). 게다가 pdflush를 제외하곤 I/O 시스템의 다른 어떠한 부분도 혼잡을 피하지 않았다. 그러므로 특정 상황에서 pdflush는 기대되는 것보다 더 길게 특정 디스크에서 writeback을 피할 수 있었다. 현재의 flusher 모델은 블록 기기와 연관되어 각각의 쓰레드가 블록당 기기의 dirty 리스트에서 데이터를 가져와 디스크에 작성한다. Writeback은 동기적으로 발생하고, 쓰레드가 디스크당 하나 존재하기 때문에 복잡한 혼잡 피하기 기능을 고려할 필요도 없어졌다.
페이지 writeback의 성능 향상으로, 2.6커널은 많은 디스크를 이전 커널보다 더 많이 saturated하게 할 수 있다. 무거운 활동이 진행되면 flusher 쓰레드는 여러 디스크에 얼쳐 높은 처리량을 유지한다.