Demand Paging
Demand Paging을 사용하는 가상 메모리에서는 페이지들이 실행 과정에서 필요로 할 때 load 된다.
Basic Concept
swap-in 시에 Pager는 프로세스가 swap-out 되기 전에 실제로 사용될 페이지들이 어떤 것인지를 추측한다.
Pager는 프로세스 전체를 swap-in 하는 대신에 실제 필요한 페이지들만 메모리로 읽어온다.
사용되지 않을 페이지를 메모리에 가져오지 않음으로써 시간과 메모리 낭비를 줄일 수 있다.
valid/invalid bit를 사용할 수 있다.
- valid
해당 페이지가 메모리에 있다는 의미이다. - invalid
해당 페이지가 유효하지 않거나, 디스크에 존재한다는 의미이다.
만약 프로세스가 메모리에 올라와 있지 않은 페이지를 접근하려고 하면, 페이지 부재 트립(Page-fault trap)이 발생한다.
페이지가 적재되고 나면 프로세스는 수행을 계속하는 데, 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때까지 필요할 때마다 페이지 부재(Page Fault)가 발생한다. 이후, 일단 필요한 모든 페이지가 load 되고 나면, 더 이상 fault는 발생하지 않는다.
이는 어떤 페이지가 필요해지기 전에는 해당 페이지를 메모리로 적재하지 않는 "pure demand paging"이다.
프로그램들은 한 명령어에서도 여러 page fault를 일으킬 가능성이 있지만, 실제 프로그램들은 어느 한 특정 작은 부분만 집중적으로 참조하는 경향이 있기 때문에, demand paging은 만족할만한 성능을 보인다.
Page Replacement
기본적인 페이지 교체
페이지 교체(Page Replacement)는 아래와 같이 행해진다.
- 만약 빈 frame이 없다면, 현재 사용되고 있지 않은 프레임을 찾아서 비운다.
- 해당 프레임의 내용을 swap space에 쓰고, 페이지 테이블을 변화시킨다. (프레임이 비어있음을 나타냄)
- 비워진 프레임을 page fault를 발생시킨 프로세스에게 할당하여 사용한다.
빈 frame이 없는 경우에 디스크를 두 번 접근해야 하므로 page fault service time이 2배 소요된다.
이러한 overhead는 modify bit 또는 dirty bit를 사용해서 감소시킬 수 있다.
Demand Paging 시스템은 아래 두 가지 중요한 문제를 해결해야 한다.
- 프레임 할당 알고리즘(Frame Allocation Algorithm)
- 페이지 교체 알고리즘(Page-replacement Algorithm)
즉, 각 프로세스에게 얼마나 많은 frame을 할당해야 하는지와 어떤 page를 교체해야 하는지를 결정해야 한다.
일반적으로, page-fault rate가 가장 낮은 페이지를 선정하여 교체한다.
앞으로 설명할 페이지 교체 알고리즘을 설명하기 위해 3개의 프레임을 가진 메모리를 가정하고, page reference string은 아래와 같다.
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
FIFO Page Replacement
메모리에 가장 오래 올라와 있던 page를 바꾸는 방법이다.
예시 page reference string에 대해 15개의 page fault를 일으킨다.
Belady의 모순은 프로세스에게 frame을 더 주었음에도, page fault가 더 증가하는 것을 의미한다.
Optimal Page Replacement
앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 방법이다.
예시 page reference string에 대해 9개의 page fault를 일으킨다.
미래를 예측해야하기 때문에 실제로 구현하기 힘들다.
LRU Page Replacement
LRU는 각 페이지마다 마지막 사용 시간을 유지하고, 페이지 교체 시에 가장 오랫동안 사용되지 않은 페이지를 교체한다.
예시 page reference string에 대해 12개의 page fault를 일으킨다.
LRU 알고리즘은 페이지 교체 알고리즘으로 자주 사용되며, 좋은 알고리즘으로 인정받고 있다.
하지만, 이 알고리즘을 구현하기 위해서는 하드웨어의 지원이 필요하며, 아래 두 가지 방법이 가능하다.
-
계수기(Counters)
각 페이지 항목마다 time-of-use field를 넣는다. -
스택(stack)
페이지 번호에 대한 스택을 유지하여, top이 가장 최근, bottom이 가장 오래된 페이지가 된다.
LRU Approximation Page Replacement
LRU page replacement를 충분히 지원할 수 있는 하드웨어는 거의 없다.
그러나, 많은 시스템들이 참조 비트(Reference bit)의 형태로 어느 정도의 지원을 하려고 한다.
처음에 모든 참조 비트는 0으로 초기화 고, 프로세스가 실행되면서 참조되는 페이지의 비트는 1로 바뀐다.
-
부가적 참조 비트 알고리즘(Additional-Reference Bits Algorithm)
일정한 간격마다 참조 비트를 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있다.
각 페이지에 대해 8비트의 참조 비트를 사용하며, 가장 최근 8구간 동안의 해당 페이지의 사용 기록을 담는다. -
2차 기회 알고리즘(Second-Chance Algorithm)
2차 기회 알고리즘의 기본은 FIFO 교체 알고리즘이다. 이와 함께 페이지가 선택될 때마다 참조 비트를 확인한다.
참조 비트가 0이면 페이지를 교체하고, 1이면 다시 한번 기회를 준 뒤 FIFO로 넘어간다. -
개선된 2차 기회 알고리즘(Enhanced Second-Chance Algorithm)
(0, 0) : 최근에 사용되지도 변경되지도 않은 경우 (교체하기 가장 좋은 페이지)
(0, 1) : 최근에 사용되지는 않았지만, 변경은 된 경우 ( 교체에 적당하지 않은 페이지)
(1, 0) : 최근에 사용은 되었으나, 변경은 되지 않은 경우 ( 다시 사용될 가능성이 높은 페이지)
(1, 1) : 최근에 사용도 되었고, 변경도 된 경우 (다시 사용될 가능성이 높으며 교체에 적당하지 않은 페이지)
Counting-Based Page Replacement)
아래 두 가지 기법이 있다.
-
LFU (Least Frequently Used) : 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
-
MFU (Most Frequently Used) : 참조 횟수가 가장 큰 페이지를 교체하는 알고리즘
이 두 가지 알고리즘은 구현하는 데 비용이 많이 들고, OPT 알고리즘을 근사하지 못하기 때문에 잘 쓰이지 않는다.
Thrashing
충분한 frame을 할당받지 못한 프로세스는 page fault가 바로 발생하게 된다.
이미 활발하게 사용되는 페이지들로만 이루어져 있으므로, 어떤 페이지가 교체되든 바로 다시 필요해진다.
이런 과도한 페이징 작업을 스레싱(Thrashing)이라고 한다.
원인
만약 많은 프로세스들이 실행을 위해 추가의 프레임을 원한다면, 계속해서 page fault가 발생할 것이다.
이에 따라, 프로세스들이 paging device를 기다리는 동안 CPU 이용률은 계속해서 떨어진다.
CPU 스케줄러는 CPU 이용률이 떨어지는 것을 보고, 계속 새로운 프로세스를 추가하려고 할 것이다.
계속해서 더 많은 page fault와 더 긴 pageing device waiting time이 생기게 된다.
이에 스레싱(Thrashing)이 발생하게 되고, 시스템의 처리율이 상당히 낮아지게 된다.
스레싱(Thrashing) 현상을 방지하기 위해서는 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 한다.
프로세스가 실제로 사용하고 있는 프레임의 수가 몇 개인가를 알아보는 것은 프로세스 실행의 지역성 모델(Locality model)을 기반으로 한다.
지역성 모델이란 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 말한다.
Working-Set Model
작업 집합 모델(Working-Set Model)은 지역성을 기반으로 하고 있다.
최근 △만큼의 page reference를 관찰하겠다는 것이다.
한 프로세스가 최근 △번 페이지를 참조했다면, 그 안에 들어있는 서로 다른 페이지들의 집합을 작업 집합이라고 부른다.
Allocating Kernel Memory
커널 메모리는 보통 사용자 모드 프로세스에게 할당해 주기 위한 페이지 리스트와는 별도의 메모리 풀에서 할당받는다.
Buddy System
버디 시스템은 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 메모리를 할당한다.
메모리는 이 세그먼트로부터 2의 거듭제곱 단위로 할당된다.
합병(Coalescing)라고 부르는 과정을 통해 서로 인접한 버디들이 손쉽게 하나의 큰 세그먼트로 합쳐질 수 있다.
Slab allocation
슬랩(Slab)은 하나 이상의 연속된 페이지들로 구성되어 있으며, 캐시(Cache)는 하나 이상의 슬랩들로 구성된다.
