Demand Paging
요구 페이징 :
프로그램 실행 시 모든 페이지를 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식
valid - invalid bit를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다.
invalid의 경우에는 2가지가 있다.
첫째는 페이지가 현재 메모리에 없고 디스크에 있는 경우,
둘째는 프로세스가 해당 페이지가 속한 주소영역을 사용하지 않는 경우이다.
1-1. Page Fault (페이지 부재)
CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우를 말한다.
페이지 폴트가 발생한 경우 주소 변환을 담당하는 HW인 MMU가 트랩을 발생시켜
운영체제가 CPU를 가지게 된다. <디스크 접근을 필요로 함>그 후 운영체제의 페이지 부재 처리 루틴이 호출되어 페이지 폴트를 처리한다.
디스크에 있는 페이지를 물리적 메모리에 올려놓는다. 그 후 해당하는 엔트리 번호를 page table에 적어놓고 invalid 를 valid로 변경한다.
대부분 발생하지 않지만 아주 특별한 경우 발생한다면 디스크 접근을 해야하고 이는 엄청난 시간을 필요로 한다. (막대한 오버헤드)
1-2. Page Replacement (페이지 교체)
페이지 교체
메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업
페이지 교체를 할 때 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 교체알고리즘이라고 한다. 이 알고리즘의 목표는 페이지 부재를 최소화하는 것이다.
1) Optimal Algorithm
가장 먼 미래에 참조되는 page를 replace
미래의 참조를 알 수가 없어서 실제로 사용못한다.
=> Offline algorithm
알고리즘의 성능에 대한 상한선을 제공 -!!
2) FIFO(first in first out) Algorithm
먼저 들어온 것을 먼저 내쫓음
FIFO anomaly 발생 가능 -!
메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황
3) LRU(Least Recently Used) Algorithm
가장 오래 전에 참조된 것을 지움
연결리스트로 구현 -> O(1)
참조된 시간 순서에 따라 한줄로 줄 세우기-! (비교가 필요없음)
4) LFU(Least Frequently Used) Algorithm
참조 횟수가 가장 적은 페이지를 지움
연결리스트로 구현 -> O(n) => 너모 느려요 (참조횟수를 비교해야해서)
힙을 이용해 구현 -> O(logn) [ 부모보다 자식이 참조횟수가 더 많도록]
1-3. 다양한 캐쉬 환경
캐시 기법
한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스 하는 방식
주소변환은 OS를 이용해서 하는 게 아니라 그저 하드웨어에서 담당한다.
즉, 페이징 시스템에서 OS는 반쪽 정보만 주어진다.
[ 메모리에 이미 그 페이지가 있다면 정보를 알 수 없다. 만약 없어서 페이지 폴트가 발생한 경우에만 CPU 제어권이 OS에게 가서 페이지가 메모리로 올라간 시간이 OS에게 주어진다.
LRU,LFU는 페이지가 참조된 횟수나 시간을 필요로 하는데 이 작업은 OS가 수행할 수 있다. 그런데 이미 페이지가 메모리에 있는 경우에는 OS는 모르게 실행되므로 실제로는 LRU, LFU는 사용할 수 없다.
1) Clock Algorithm
HW에 의해 자동으로 참조비트를 세팅한다.
OS는 참조비트를 보면서 1인것을 0으로 바꾸고 0인것을 쫓아낸다.
어느정도 LRU와 근사하게 알고리즘이 이루어진다.
reference bit와 modified bit을 함께 사용
2) 페이지 프레임의 할당
- 균등할당
- 비례할당
- 우선순위 할당
1-4. Thrashing
Thrashing
프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 CPU 이용률이 급격히 떨어지는 현상
CPU 이용률이 낮으면 OS는 메모리에 올라가는 프로세스의 수를 늘리게 된다.
MPD(Multi-Programming Degree)(메모리에 동시에 올라가 있는 프로세스의 수)
를 높이는 것이다.
그런데 MPD를 과도하게 높이면 각 프로세스마다 얻을 수 있는 메모리의 양이 작아져서 원활하게 수행되는데 필요한 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 페이지 폴트가 빈번히 발생한다.
OS는 CPU이용률이 적으니 프로세스가 적은 줄 알고 MPD를 더 늘린다.
그러면 페이지 폴트는 더욱 더 많이 발생하고 cpu는 대부분의 시간에 일을 하지 않게 된다.
이를 조절하기 위해 사용하는 알고리즘에는 워킹셋 알고리즘, PFF 알고리즘이 있다.
1-5. 워킹셋 알고리즘과 PFF알고리즘
워킹셋 : 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
워킹셋 알고리즘
프로세스의 워킹셋 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다.
페이지 부재 빈도 PFF(Page Fault Frequency) :
페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 프레임을 추가로 할당한다.
1-6. Page Size의 결정
page size를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- Internal fragmentation(내부조각) 감소
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
-> locality의 활용 측면에서는 좋지 않음 - Disk Transfer의 효율성 감소
