Page Frame Reclamation and Swapout (v2.4.22)

Introduction

언젠가 swap, PFRA, rmap에 대해서도 글을 써야겠다고 생각하고 있었는데, 모두 복잡하다보니 어디서부터 시작할지가 항상 고민이었다. 결국 가장 문서화가 잘 되어있는 Understanding the Linux Virtual Memory Manager 에서 시작을 해보기로 했다. 따라서 이 글은 책에서 다루는 v2.4.22에 기반한다.

References: Understanding the Linux Virtual Memory Manager

이 글은 Mel Gorman의 책과 많이 겹친다. 이 글과 같이 읽으면 좋을 것 같다.

이 글에서는 swap 자체의 동작 방식에 관한 내용은 다루지 않는다.

Page Frame Reclamation

Ch 10. Page Frame Reclamation 과 code commentary  

Swap

Ch 11. Swap Management 와  code commentary

Page Frame Replacement Algorithm

PFRA에는 다양한 종류가 있지만 리눅스는 LRU와 유사한 방식을 사용한다. LRU는 가장 마지막에 접근한 페이지 프레임을 교체하는 알고리즘이다. LRU에서는 연결 리스트로 회수 가능한 페이지 프레임들을 구성한다.

Least Recently Used

이상적으로는 이렇게 페이지 프레임에 접근할 때마다 LRU의 맨 처음으로 옮겨주어야겠지만, 현실적으로는 그게 불가능하기 때문에 LRU 리스트를 스캔할 때마다, 마지막 스캔 이후에 접근된(PG_referenced 플래그가 켜짐) 페이지들이 접근되었다는 것만 알 수 있다. (심지에 10번 접근했는지 1번 접근했는지도 모른다!) (Clock 알고리즘과 유사) 커널은 LRU 리스트를 메모리를 회수해야할 때만 스캔한다.

2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm

리스트 하나만으로 LRU 리스트를 관리하는 방식은, 자주 접근되는 페이지와 한 번씩만 접근되는 페이지들을 구분하지 못한다. [LRU-K] 따라서 2개 이상의 리스트로 관리하는 방법이 고안되었다. [2Q] 아래 그림은 간소화된 2Q를 표현한 다이어그램이다.

실제 LRU 리스트인 Am에 페이지 프레임이 삽입되기 전에, 페이지 프레임들은 FIFO 큐인 A1에 먼저 삽입된다. 이후 페이지 프레임이 다시 접근된 경우에만 Am의 head로 이동하며, A1에서 Am으로 이동하기 전에 A1에 새로운 페이지 프레임이 삽입되면 (그리고 A1 큐가 꽉찼다면) A1에서 추방되어 회수된다. 2Q는 페이지 프레임이 한 번씩만 접근되는 경우와 여러 번 접근되는 경우를 잘 구분한다.

Linux: active list & inactive list

리눅스는 2Q와 비슷하지만 조금 다르게, 2Q에서의 A1이 FIFO queue가 아니라 LRU 리스트이다. 회수의 대상이 되는 페이지 프레임들 중 자주 접근하는 것들은 active list 상에 존재하며, 그렇지 않은 것들은 inactive list에 존재한다. 또한 리눅스는 active list와 inactive list의 크기가 정해져있지 않고 유동적으로 변한다.

새로 접근하는 페이지들은 lru_cache_add()->add_page_to_inactive_list()를 통해서 inactive list의 head에 추가된다.

리눅스는 페이지를 회수할 때 active list에서 inactive list로 페이지를 옮겨오고 (refill_inactive()), inactive list에서 페이지 프레임들을 회수한다. (shrink_cache())

refill_inactive()는 active list의 페이지 프레임들을 inactive list에 옮기기 위해 active list를 스캔하는데, 이 때 페이지 프레임이 최근에 접근된 경우에는 active list의 head로 이동하며, 그렇지 않은 경우에는 inactive list의 head로 이동한다.

그 외에 페이지 폴트가 발생하거나, file descriptor를 통해서 파일을 읽는 경우에는 mark_page_accessed()로 PG_referenced 플래그를 설정하며, 이미 설정되어있는데 inactive list에 있다면 active list로 이동한다.

Lifetime of a LRU page

어떤 페이지가 LRU list에 삽입된 이후의 상태를 그래프로 나타내면 다음 그림과 같다.

Insertion

LRU 리스트에는 (사용자 공간에 매핑되었을 수도 있는) 페이지 캐시 상의 file page와, 사용자 프로세스가 사용하는 anonymous page, 그리고 사용자 공간에 매핑된 디바이스 파일의 페이지 등이 있다.

아래 다이어그램은 v2.4.22에서 어떤 경우에 lru_cache_add()를 통해 LRU 리스트에 새로운 페이지가 추가되는지 보여준다. 한 가지 참고할 점은, v2.4.22에서는 페이지가 active list에 바로 삽입되는 경우가 없고, inactive list에 먼저 삽입된 후 이후 다시 접근하면서 active list로 이동한다.

 

Promotion

페이지 프레임이 inactive list에서 active list로 이동하는 경우는 페이지 프레임이 접근될 때 페이지 프레임에 대해 mark_page_accessed()가 실행된 경우이다.

Demotion

페이지 프레임이 active list에서 inactive list로 이동하는 경우는 페이지 프레임의 회수를 위해 refill_inactive()가 active list의 페이지들을 inactive list로 옮겨올 때이다. (PG_referenced 플래그가 꺼져 있는 페이지들만 inactive list로 옮겨온다.)

Moving to head

active -> inactive or inactive -> active로 이동하는 게 아니라, 현재 속한 리스트의 head로 이동하는 경우는 두 가지가 있다. 하나는 refill_inactive()에서 inactive list로 옮길 페이지를 active list에서 찾다가 PG_referenced 플래그가 켜진 페이지를 만난 경우, PG_referenced를 clear하고 head로 옮긴다. 나머지 하나는 shrink_cache()에서 회수할 페이지를 찾는 도중 회수에 실패한 경우이다.

Eviction

페이지가 LRU 리스트에서 제외되는 경우는 페이지를 해제할 때이다. free_pages()로 해제하거나, page cache 상에서 invaliate되거나, shrink_cache()로 회수된 경우다.

 

Reclamation

페이지 프레임의 회수는 크게 두 가지 이유에 의해 발생한다. 하나는 메모리를 할당하다가 여유 메모리가 부족해서, 메모리 할당을 요청한 스레드에서 direct reclamation을 하는 경우고, 나머지 하나는 메모리 할당에는 성공했지만 여유 메모리가 zone->pages_low보다 적어져서 kswpad를 깨워 백그라운드에서 kswapd가 페이지 프레임을 회수하는 indirect reclamation이다. direct reclamation이든 indirect reclamation이든 try_to_free_pages_zone() 부터가 reclamation algorithm의 핵심 부분이다.

try_to_free_pages_zone()

이 함수는 priority를 DEF_PRIORITY (6)부터 1까지 줄여가면서 shrink_caches()를 호출해서, 최소 nr_pages (= SWAP_CLUSTER_MAX = 32)개의 페이지를 회수한다. shrink_caches()는 priority가 줄어들수록 더 aggressive하게 페이지 프레임을 회수한다. 만약 priority 1까지 시도했는데 nr_pages보다 적은 수의 페이지 프레임을 회수했다면, out_of_memory()를 호출해서 실행중인 프로세스를 죽여서 메모리를 회수한다.

int try_to_free_pages_zone(zone_t *classzone, unsigned int gfp_mask)
{
        int priority = DEF_PRIORITY;
        int nr_pages = SWAP_CLUSTER_MAX;

        gfp_mask = pf_gfp_mask(gfp_mask);
        do {
                nr_pages = shrink_caches(classzone, priority, gfp_mask, nr_pages);
                if (nr_pages <= 0)
                        return 1;
        } while (--priority);

        /*
         * Hmm.. Cache shrink failed - time to kill something?
         * Mhwahahhaha! This is the part I really like. Giggle.
         */
        out_of_memory();
        return 0;
}

shrink_caches()

shrink_caches()는 먼저 kmem_cache_reap()으로 페이지 프레임을 회수한 후, 그래도 부족하면 refill_inactive()로 active list에서 inactive list로 페이지 프레임을 옮긴 후, shrink_cache()로 inactive list에서 페이지 프레임을 회수한다. 이 때, active list에서 페이지를 nr _pages * nr_active_pages / ((nr_inactive_pages + 1) * 2) 만큼만 inactive list로 옮겨서, active list의 크기가 inactive list의 2/3이 되도록 유지하려고 노력한다.

그래도 nr_pages개의 페이지 프레임을 회수하지 못했다면 shrink_(d|i|dq)cache_memory()를 호출해서 dentry cache, inode cache, dqcache를 shrink한다.

static int shrink_caches(zone_t * classzone, int priority, unsigned int gfp_mask, int nr_pages)
{
        int chunk_size = nr_pages;
        unsigned long ratio;

        nr_pages -= kmem_cache_reap(gfp_mask);
        if (nr_pages <= 0)
                return 0;

        nr_pages = chunk_size;
        /* try to keep the active list 2/3 of the size of the cache */
        ratio = (unsigned long) nr_pages * nr_active_pages / ((nr_inactive_pages + 1) * 2);
        refill_inactive(ratio);

        nr_pages = shrink_cache(nr_pages, classzone, gfp_mask, priority);
        if (nr_pages <= 0)
                return 0;

        shrink_dcache_memory(priority, gfp_mask);
        shrink_icache_memory(priority, gfp_mask);
#ifdef CONFIG_QUOTA
        shrink_dqcache_memory(DEF_PRIORITY, gfp_mask);
#endif

        return nr_pages;
}

refill_inactive()

refill_inactive()는 active list의 tail부터 head까지, nr_pages개의 페이지 프레임을 inactive list로 옮기거나, active list의 페이지 프레임들을 inactive list로 모두 옮기기 전까지 active list를 스캔한다.

/*
 * This moves pages from the active list to
 * the inactive list.
 *
 * We move them the other way when we see the
 * reference bit on the page.
 */
static void refill_inactive(int nr_pages)
{
        struct list_head * entry;

        spin_lock(&pagemap_lru_lock);
        entry = active_list.prev;
        while (nr_pages && entry != &active_list) {
                struct page * page;

                page = list_entry(entry, struct page, lru);
                entry = entry->prev;
                if (PageTestandClearReferenced(page)) {
                        list_del(&page->lru);
                        list_add(&page->lru, &active_list);
                        continue;
                }

만약 active list의 페이지 프레임의 PG_referenced 플래그가 켜져있다면 clear하고 active list의 head로 옮긴다.

                nr_pages--;

                del_page_from_active_list(page);
                add_page_to_inactive_list(page);
                SetPageReferenced(page);
        }
        spin_unlock(&pagemap_lru_lock);
}

그렇지 않다면 페이지 프레임의 PG_referenced 플래그를 set하고 active list에서 inactive list의 head로 옮긴다. 

What pages are in inactive list

코드를 분석하기 전에 inactive list에는 어떤 유형의 페이지 프레임들이 존재하는지 먼저 살펴보자.

page frame이 파일과 연관되지 않음 (page->mapping == NULL)

페이지 프레임이 익명이며 스왑 캐시에 포함되지 않은 상태이다.

page frame이 파일과 연관되었거나 스왑 캐시에 속함 (page->mapping이 address_space를 가리킨다)

페이지 프레임이 파일의 내용을 담고 있거나, 스왑 캐시에 포함된 경우이다. 이 때 페이지 프레임과 연관된 버퍼 헤드가 존재할 수도 있고 아닐 수도 있으며, 존재한다면 버퍼 헤드를 먼저 해제해야한다.

또한 페이지 프레임이 프로세스 주소 공간에 매핑된 경우 모두 unmapping을 해야하며, 페이지 프레임에 PG_dirty 비트가 켜져있는 경우 backing storage에 writeback을 한 후 회수해야한다.

shrink_cache()

앞서 설명한 것처럼 shrink_cache()는 inactive list에서 페이지 프레임들을 회수한다. 이 함수를 순서도로 그려보면 대략 다음과 같다.

static int shrink_cache(int nr_pages, zone_t * classzone, unsigned int gfp_mask, int priority)
{
        struct list_head * entry;
        int max_scan = nr_inactive_pages / priority;
        int max_mapped = min((nr_pages << (10 - priority)), max_scan / 10);

이 함수에서는 두 가지 변수를 설정하는데, 하나는 페이지 프레임을 몇개까지 순회할지를 정하는 max_scan이다. priority에 따라서 inactive list의 16.6%부터 100%까지 스캔할 페이지의 수가 결정된다.

두 번째 파라미터는 max_mapped다. inactive list에는 프로세스의 가상 주소 공간에 매핑(mapped)된 페이지 프레임과 그렇지 않은 페이지 프레임이 있다. shrink_cache는 inactive list를 스캔하다가 max_mapped개의 매핑된 페이지 프레임을 만나기 전까지는 매핑된 페이지 프레임을 회수하지 않는다. 다르게 설명하면, 매핑된 페이지 프레임은 max_mapped번까지는 inactive list에서 만나도 skip하다가, max_mapped + 1번째부터는 swapout을 하기 시작한다. 매핑된 페이지 프레임보다 매핑되지 않은 페이지 프레임을 회수하도록 차별하는 것이다.

        spin_lock(&pagemap_lru_lock);
        while (--max_scan >= 0 && (entry = inactive_list.prev) != &inactive_list) {
                struct page * page;

pagemap_lru_lock을 획득한 후, max_scan개 만큼의 페이지 프레임을 회수하거나, inactive list를 모두 스캔하기 전까지 inactive list를 스캔한다. 이 while loop에서 entry는 inactive list의 tail부터 시작해서 inactive list의 head까지 순차적으로 이동한다.

                if (unlikely(current->need_resched)) {
                        spin_unlock(&pagemap_lru_lock);
                        __set_current_state(TASK_RUNNING);
                        schedule();
                        spin_lock(&pagemap_lru_lock);
                        continue;
                }

inactive list를 스캔하다가 타임 슬라이스를 다 써버리면, 너무 많은 CPU 시간을 소모하지 않도록 sleep한다.

                page = list_entry(entry, struct page, lru);

                BUG_ON(!PageLRU(page));
                BUG_ON(PageActive(page));

                list_del(entry);
                list_add(entry, &inactive_list);

페이지 프레임을 회수하기 전에 먼저 inactive list의 head로 옮겨서, 만약 회수하지 못하더라도 다음 스캔에서 만날 수 있도록 한다.

                /*
                 * Zero page counts can happen because we unlink the pages
                 * _after_ decrementing the usage count..
                 */
                if (unlikely(!page_count(page)))
                        continue;

page_count()가 0인 경우에는 이 페이지 프레임을 쓰고 있는 사용자가 없다는 것이므로 회수되어야 한다. inactive list에서 page_count() == 0인 페이지 프레임을 만나는 경우는 버디가 이 페이지 프레임을 회수하는 경우이므로, 다음 페이지 프레임으로 넘어간다.

                if (!memclass(page_zone(page), classzone))
                        continue;

try_to_free_pages_zone()은 특정 zone에 대해서만 페이지 프레임을 회수한다. 이 페이지 프레임이 zone에 포함되지 않는다면 다음 페이지 프레임으로 넘어간다. (이후 버전에서는 아예 zone별로 lru list를 관리한다.)

                /* Racy check to avoid trylocking when not worthwhile */
                if (!page->buffers && (page_count(page) != 1 || !page->mapping))
                        goto page_mapped;

페이지 프레임이 연관된 버퍼가 없는 경우 (!page->buffers), 페이지 캐시에 속하지 않거나 (!page->mapping), 페이지 캐시에 속하지만 참조가 1개 이상이면  (page_count(page) != 1) 프로세스의 주소 공간에 매핑된 것이므로 page_mapped 레이블로 이동한다.

이 이후의 코드에서는 1) 연관된 버퍼가 있고 프로세스에 주소 공간에 매핑이 된 페이지나 2) 연관된 버퍼가 없으며 프로세스 주소 공간에 매핑되지 않은 페이지만 고려하면 된다.

                /*
                 * The page is locked. IO in progress?
                 * Move it to the back of the list.
                 */
                if (unlikely(TryLockPage(page))) {
                        if (PageLaunder(page) && (gfp_mask & __GFP_FS)) {
                                page_cache_get(page);
                                spin_unlock(&pagemap_lru_lock);
                                wait_on_page(page);
                                page_cache_release(page);
                                spin_lock(&pagemap_lru_lock);
                        }
                        continue;
                }

PG_launder 비트가 켜진 경우에는 이미 페이지 프레임에 대해 writeback이 진행되고 있다는 것이므로 wait_on_page()로 IO가 끝날 때까지 기다린다.

                if (PageDirty(page) && is_page_cache_freeable(page) && page->mapping) {
                        /*
                         * It is not critical here to write it only if
                         * the page is unmapped beause any direct writer
                         * like O_DIRECT would set the PG_dirty bitflag
                         * on the phisical page after having successfully
                         * pinned it and after the I/O to the page is finished,
                         * so the direct writes to the page cannot get lost.
                         */
                        int (*writepage)(struct page *);

                        writepage = page->mapping->a_ops->writepage;
                        if ((gfp_mask & __GFP_FS) && writepage) {
                                ClearPageDirty(page);
                                SetPageLaunder(page);
                                page_cache_get(page);
                                spin_unlock(&pagemap_lru_lock);

                                writepage(page);
                                page_cache_release(page);

                                spin_lock(&pagemap_lru_lock);
                                continue;
                        }
                }

페이지 프레임이 페이지 캐시 (혹은 스왑 캐시)에 속하며 (page->mapping),  PG_dirty 비트가 켜져있고 (PageDirty(page)), 이 페이지 프레임을 매핑하는 프로세스가 없는 경우 (is_page_cache_freeable()), PG_launder 비트를 켠 후 writepage()로 backing storage에 writeback을 수행한다.

                /*
                 * If the page has buffers, try to free the buffer mappings
                 * associated with this page. If we succeed we try to free
                 * the page as well.
                 */
                if (page->buffers) {
                        spin_unlock(&pagemap_lru_lock);

페이지 프레임과 연관된, 디스크 상의 블록을 나타내는 버퍼가 존재하는 경우에는 버퍼를 모두 해제해야한다.

                        /* avoid to free a locked page */
                        page_cache_get(page);

                        if (try_to_release_page(page, gfp_mask)) {
                                if (!page->mapping) {
                                        /*
                                         * We must not allow an anon page
                                         * with no buffers to be visible on
                                         * the LRU, so we unlock the page after
                                         * taking the lru lock
                                         */
                                        spin_lock(&pagemap_lru_lock);
                                        UnlockPage(page);
                                        __lru_cache_del(page);

                                        /* effectively free the page here */
                                        page_cache_release(page);

                                        if (--nr_pages)
                                                continue;
                                        break;

이 부분이 헷갈린다. 사실 스왑 캐시 상의 페이지는 swapper_space->a_ops->writepage()에서 더 이상 프로세스의 주소 공간에 매핑되지 않고 swap cache만 페이지 프레임을 참조하는 경우 remove_exclusive_swap_page()에 의해 스왑 캐시에서 제거된다. 이 때, remove_exclusive_swap_page()는 이 페이지와 연관된 버퍼가 있냐 없냐에 관계 없이 페이지 프레임을 스왑 캐시에서 제거한다. 위 케이스는 스왑 캐시에 존재했던 페이지 프레임이 스왑 캐시에서 제거된 후 (page->mapping == NULL) 관련된 버퍼만 남은 경우이다.

                                } else {
                                        /*
                                         * The page is still in pagecache so undo the stuff
                                         * before the try_to_release_page since we've not
                                         * finished and we can now try the next step.
                                         */
                                        page_cache_release(page);

                                        spin_lock(&pagemap_lru_lock);
                                }

관련된 버퍼를 해제했는데 만약 스왑 캐시가 아니라 페이지 캐시 상에 존재한다면, 다음에 이 페이지 프레임을 다시 만날 때 회수를 시도한다.

                        } else {
                                /* failed to drop the buffers so stop here */
                                UnlockPage(page);
                                page_cache_release(page);

                                spin_lock(&pagemap_lru_lock);
                                continue;
                        }
                }

try_to_release_page()가 실패한 경우에는 다음 페이지 프레임으로 이동한다.

                spin_lock(&pagecache_lock);

                /*
                 * this is the non-racy check for busy page.
                 */
                if (!page->mapping || !is_page_cache_freeable(page)) {
                        spin_unlock(&pagecache_lock);
                        UnlockPage(page);
page_mapped:
                        if (--max_mapped >= 0)
                                continue;

                        /*
                         * Alert! We've found too many mapped pages on the
                         * inactive list, so we start swapping out now!
                         */
                        spin_unlock(&pagemap_lru_lock);
                        swap_out(priority, gfp_mask, classzone);
                        return nr_pages;
                }

페이지 프레임이 페이지 캐시 (혹은 스왑 캐시에) 속하지 않거나, 속하는데 프로세스의 주소 공간에 매핑된 경우에는 먼저 unmapping을 해야한다.

                /*
                 * It is critical to check PageDirty _after_ we made sure
                 * the page is freeable* so not in use by anybody.
                 */
                if (PageDirty(page)) {
                        spin_unlock(&pagecache_lock);
                        UnlockPage(page);
                        continue;
                }

페이지 프레임이 주소 공간에 매핑되어있지 않은데 PG_dirty 비트가 켜져있는 경우 누군가 파일을 읽은 것이므로 스킵한다.

                /* point of no return */
                if (likely(!PageSwapCache(page))) {
                        __remove_inode_page(page);
                        spin_unlock(&pagecache_lock);
                } else {
                        swp_entry_t swap;
                        swap.val = page->index;
                        __delete_from_swap_cache(page);
                        spin_unlock(&pagecache_lock);
                        swap_free(swap);
                }

여기까지 오면 페이지 프레임은 프로세스 주소 공간에 매핑되어있지 않으며, PG_dirty도 꺼져있으므로 바로 회수할 수 있다. 페이지 캐시에 속했는지 스왑 캐시에 속했는지에 따라 적절한 캐시에서 페이지 프레임을 회수한다.

                __lru_cache_del(page);
                UnlockPage(page);

                /* effectively free the page here */
                page_cache_release(page);

                if (--nr_pages)
                        continue;
                break;
        }
        spin_unlock(&pagemap_lru_lock);

        return nr_pages;
}

그 다음 페이지 프레임을 LRU 리스트에서 제거하고 nr_pages의 값에 따라서 페이지 프레임을 더 회수하거나 종료한다.

swapout

나머지 두 섹션은 코드가 그렇게 복잡하지 않아서 그림으로만 간단하게 설명한다. 이 섹션에서는 swap_out() 함수를 좀 더 설명한다. v2.4.22의 swap out은 reverse mapping을 지원하지 않아서 매우 원시적이다.

swapout이 발생하는 함수 호출 경로는 shrink_cache()->swap_out()->swap_out_mm()->swap_out_vma()->swap_out_pgd()->swap_out_pmd()->try_to_swap_out()이다.

우선 전역 변수인 swap_mm은 어떤 태스크의 mm_struct를 가리킨다. mm_struct에는 swap_address라는 필드가 있어서, 이 주소부터 swap_mm의 주소 공간을 스캔한다. 이 때 try_to_swap_out()은 pte에 대해 pte_young()을 체크하고 clear한다. 이 때 pte_young()이 참이라면 CPU에서 페이지에 접근한 것이므로 pte를 unmap을 하지 않는다. 혹은 페이지 프레임이 active list에 존재하는 경우에도 마찬가지로 unmap하지 않는다.

try_to_swap_out()이 호출되는 경우는 크게 세 가지가 있다.

1. 익명 페이지이며 스왑 캐시에 존재하지 않는 경우 -> 페이지 프레임을 스왑 캐시에 넣고 pte를 swap entry로 바꿔준다.
2. 익명 페이지이며 스왑 캐시에 존재하는 경우 -> pte를 swap entry로 바꿔준다.
3. 파일 페이지인 경우 -> 그냥 unmap만 해준다.

try_to_swap_out()이 (파일 페이지든 스왑 캐시 상의 익명 패이지든) pte를 unmap하여 더 이상 페이지 프레임을 주소 공간에 매핑한 프로세스가 없더라도 페이지 프레임이 바로 회수되지는 않고, 이후에 shrink_cache()에서 디스크로 writeback을 한 다음 PG_dirty 비트를 clear해야 회수가 가능하다.

swap_out()은 적어도 nr_pages개의 페이지를 프로세스 주소 공간에서 unmapping할 때까지 swap_address를 증가시키면서 프로세스의 주소 공간을 탐색한다. 만약 swap_address가 프로세스의 주소 공간의 끝인 TASK_SIZE에 도달하면 다음 swap_mm을 다음 태스크의 mm_struct로 이동한다.

v2.4.22에서 프로세스 주소 공간에 매핑된 페이지 프레임은 swap_out()으로 모든 프로세스의 주소 공간을 순회하며 매핑을 해제하기 전까지는 회수할 수 없다. 이 단점으로 인해 이후 reverse mapping이 등장한다.

References

[LRU-K] The LRU-K page replacement algorithm for database disk buffering

[2Q] 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm