Page Fault 처리 루틴
CPU 가 논리적 주소를 물리적 주소로 변환시키기 위해 페이지 테이블을 참조했지만 invalid bit 가 설정되어 있다면 다음과 같이 행동하게 된다.
1. CPU 가 페이지 테이블을 참조한다. 하지만 invalid bit 이 설정되어 있다.
2. trap 를 발생시켜 디스크 IO 를 실행시킨다. 이때 OS 는 해당 프로세스를 block 상태로 바꾼다. 디스크 IO 가 끝나기 전까지는 다른 프로세스가 CPU 를 차지한다.
3. OS의 권한으로 디스크 IO를 실행시킨다.
4. 메모리에 적재를 한다.
5. valid bit 으로 바꿔준다.
6. block 한 프로세스를 ready 큐에 넣어주고 다시 실행시킨다.
페이지 교체 알고리즘
어떠한 페이지를 교체 아웃시킬 것인가에 대한 알고리즘
- 최적 페이지 교체
- 선입선출 알고리즘
- LRU (Least Recently Used)
- LFU (Least Frequently Used)
- Clock 알고리즘
최적 페이지 교체
Optimal 알고리즘이며 현실 세계에서는 불가능하다. 다만 성능의 상한선을 알려주는 지표가 된다.
미래를 알고 있다는 가정하에 가장 먼 미래에 참조될 페이지를 쫓아내면 된다.
선입선출 알고리즘
페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.
이 알고리즘의 문제점은 물리적 메모리의 공간이 늘어났음에도 오히려 성능은 더 나빠진다는 것이다. 그 이유는 이것을 FIFO의 이상현상이라고 부른다.
이러한 이상현상에 대해 예시를 통한 증명만 존재할 뿐 일반화해서 증명하는 자료를 찾을 수가 없었다. 하지만 다시 생각을 해보자.
물리적 메모리의 공간이 늘어나서 페이지 수가 늘어났다면 그만큼 page hit 가 일어날거라고 기대를 하여 page fault 가 적어질 것을 기대한다. 하지만 FIFO 는 page 의 과거 이력 상관 없이 그냥 먼저 온걸 먼저 내보내는 알고리즘이다. 이러한 무관성과 결합해서 생각하면 페이지 수가 늘어난 만큼 page fault 가 일어날 페이지들이 더 증가한거라고도 볼 수 있다. 따라서 FIFO 에서는 페이지 수와의 비례 관계가 존재하지는 않는다.
LRU 알고리즘
시간 지역성을 이용한 알고리즘으로 최근에 참조된 페이지는 가까운 미래에 다시 참조될 가능성이 높다는 전제 하에 실행된다. 즉, 페이지 교체시 가장 오래 전에 참조한 페이지를 쫓아낸다.
LFU 알고리즘
물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 제일 적었던 페이지를 쫓아낸다.
LRU LFU 알고리즘 구현
- LRU 알고리즘은 linkedlist 로 구현한다. 새로운 페이지가 오면 MRU에 insert를 하고 삭제를 한다면 LRU 에 있는 노드를 삭제한다. 그리고 있던 페이지가 재참조된다면 그 노드를 MRU 로 이동해준다. 모든 동작들이 O(1) 시간 복잡도를 가진다.
- LFU 알고리즘은 linkedlist 로 구현이 불가하다. 왜냐하면 있던 페이지가 재참조되면 그대로 MRU 에 붙여주는게 아니라 다른 노드와의 비교를 통해 옮겨줘야 되기 때문에 O(n) 시간 복잡도를 가진다. 이는 너무나도 오래걸려서 효용성이 없다.
대신 heap를 사용하여 O(logn) 의 시간복잡도를 이용한다. (heapify 알고리즘)
LRU LFU 의 한계
논리적 주소를 물리적 주소로 매핑하는 것은 하드웨어에서 담당하고 Page Fault 에 의한 페이지 교체만 OS 가 관여한다. 따라서 Page Fault 가 아니라 재참조가 되는 상황에서는 OS 가 무슨 상황이 벌어지는지 알 길이 없다. 그렇게 대안으로 나온 것이 클럭 알고리즘이다.
클럭 알고리즘
LRU 는 OS 가 갖고 있는 정보의 부족함으로 쓰일 수 없으니 대체제로 나온 것이 NRU (Not Recently Used) 이다. LRU는 가장 오랫동안 참조되지 못한 페이지를 교체해주는 것이지만 NRU는 최근에 참조되지 않은 페이지를 교체해준다. 즉 가장 오래됐음을 보장하진 못한다. 대부분의 운영체제는 클럭 알고리즘을 사용한다.
하드웨어의 도움으로 참조가 되었을 때 reference bit 를 1 로 세팅해준다. 소프트웨어인 os 는 페이지 테이블의 참조 비트를 확인한다.
- 참조 비트가 1인 경우 : 0으로 다시 바꿔준다.
- 참조 비트가 0인 경우 : 해당 페이지를 교체 아웃해준다.
전역 교체와 지역 교체
교체 대상이 될 프레임의 범위에 대해 전역과 지역이 존재한다.
- 전역 교체 : 모든 페이지 프레임이 교체 대상
- 지역 교체 : 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상 선정. 즉 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제
스레싱
degree of multiprogramming 이란 메모리에 올라가 있는 프로세스의 개수를 뜻한다.
우리는 메모리에 올라와있는 프로세스의 개수가 많을수록 CPU utilization 이 높아질 것을 기대한다. 하나의 프로세스가 IO 를 하기 위해 block 되어 있어도 CPU 가 일을 하지 않을수도 있지만 문맥교환을 통해 그동안 다른 프로세스가 CPU를 사용하게 할 수 있기 때문이다. 하지만 무한정으로 프로세스를 늘린다면 오히려 이용률이 떨어진다. 그 이유는 하나의 프로세스가 할당받는 메모리 공간이 작아지기 때문이다.
프로세스가 실행되기 위해서는 최소한의 메모리를 확보하고 있어야한다. code, data, stack 은 항상 참조되기 때문에 메모리 영역에 올려져 있는 편이 더 효율적이기 때문이다. 하지만 메모리 할당이 적어서 이것을 다 올리지 못하면 백업 스토어에 왔다갔다 하며 IO를 하는데 시간을 많이 쓰게 된다. 즉, page fault가 너무 많아져 메모리에 올라가있는 프로세스 모두 IO를 기다리는 시간이 생기게 된다는 뜻이다. (ready 큐에 이어 받아줄 프로세스가 없다.)
우리는 그래서 degree of multiprogramming, 즉 메모리에 한번에 올라가는 프로세스의 개수를 조절할 필요가 있어지는 것이다. 이것을 조절하는 데 두가지 방법이 있다.
- 워킹셋 알고리즘
- 페이지 부재 빈도 알고리즘
워킹셋 알고리즘
프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 만약 그렇지 않을 경우에는 프로세스에게 할당된 페이지 프레임을 모두 반납시긴 후 그 프로세스의 주소 공간 전체를 디스크로 스왑아웃한다.
이때 워킹셋을 구성하기 위해 워킹셋 윈도우의 크기를 정해야한다.
- 윈도우 크기가 작으면 지역성 집합을 모두 수용하지 못할 수도 있다. 즉 윈도우 크기가 작아서 원래는 하나의 프로세스에 필요한 최소한의 프레임들이 모두 올라가는 것이 지역성을 활용하는데 효과적이지만, 너무 작아서 이 조차도 다 못올리는 상황이 생길수도 있는 것이다.
- 윈도우 크기가 그렇다고 해서 너무 크면 스왑아웃이 많이 일어나 cpu utilization 이 적어질 수 있다.
페이지 부재 빈도 알고리즘
page-fault rate의 상한선과 하한선을 정해둔다.
- page-fault rate 가 상한선을 넘어가면 페이지 프레임 할당을 늘려준다.
- page-fault rate 가 하한선을 넘어가면 프로세스를 더 넣어서 cpu utilization 를 높여준다.
Page Size의 결정
페이지 사이즈를 줄이면
- 페이지 수 증가
- 페이지 테이블 크기의 증가 (엔트리가 증가하기 때문)
- 내부 조각 감소
- disk transfer 효율성 감소 (disk 는 데이터를 찾는 과정이 매우 오래걸려 이 과정이 최대한 없는 것이 좋다. 따라서 처음부터 페이지 하나를 크게 올려주는 것이 page fault를 줄여줘서 더 좋다.)
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적이다.
- 지역성 활용 측면에서는 좋지 못한다. (페이지 크기가 크면 코드를 순차적으로 참조할 때 page fault 가 잘 안난다.)
