📌 요구 페이징 (demand paging)
프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 방법을 요구 페이징이라고 한다. 이름 그대로 실행에 요구되는 페이지만 적재하는 기법이다.
요구 페이징의 기본적인 양상은 다음과 같다.
- CPU가 특정 페이지에 접근하는 명령어를 실행한다.
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
- 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
- 페이지 폴트 처리 루티은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
- 다시 1번부터 반복한다.
참고로 아무런 페이지도 메모리에 적재하지 않은 채 무작성 실행부터 할 수도 있다. 이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 되고, 실행에 필요한 페이지가 어느 정도 적재된 이후 부터는 페이지 폴트 발생 빈도가 떨어진다.
이를 순수 요구 페이징 기법이라고 한다.
요구 페이징 이야기로 돌아와서, 위와 같은 요구 페이징 시스템이 안정적으로 작동하려면 필연적으로 다음 두 가지를 해결해야 한다. 바로 페이지 교체와 프레임 할당이다.
요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 된다. 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 한다.
메모리에 적재된 많은 페이지 중 어떤 페이지를 내보내는 것이 최선일까?
이를 결정하는 방법이 오늘 알아볼 페이지 교체 알고리즘이다.
즉, 쫓아낼 페이지를 결정하는 방법을 '페이지 교체 알고리즘'이라고 한다.
📌 페이지 교체 알고리즘
페이지 교체 알고리즘의 목표는 페이지 부재율을 최소화 하는 것이다. 그러므로 가까운 미래에 참조될 가능성이 적은 페이지를 선택해서 내보내는 것이 성능을 향상 시킬 수 있는 방안이 될 것이다.
✔︎ 선입선출 알고리즘 (First In First Out: FIFO)
페이지 교체 시 물리적 메모리에 '가장 먼저 올라온 페이지를 우선적으로 내보내는 알고리즘'이다.
페이지의 향후 참조 가능성을 교려하지 않기 때문에 비효율적인 상황이 발생할 수 있다.
아래 그림은 3개의 페이지 프레임을 가질 경우 9번의 페이지 부재와 3번의 페이지 히트가 발생한다.
선입선출 알고리즘에서 메모리를 증가해도 페이지 부재가 더 증가하는 FIFO의 이상 현상(FIFO abnomaly)이 발생할 수 있다.
✔︎ LRU 알고리즘 (Least Recently Used Algorithm: LRU)
페이지 교체 알고리즘의 성능 향상을 위해선 앞으로 '사용 가능성이 낮은 페이지를 우선적으로 내보내는 것이 좋다'. 이와 관련해서 시간 지역성이라는 성질이 있다. 시간 지역성은 최근에 참조된 페이지가 미래에 다시 참조될 가능성이 높은 성질을 말한다. LRU 알고리즘은 이와 같은 성질을 활용해서 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내보낸다.
LRU 알고리즘을 사용하니 8번의 페이지 부재와 4번의 페이지 히트가 발생한다. FIFO 알고리즘에 비해 페이지 부재 횟수가 감소했다.
✔︎ LFU 알고리즘 (Least Frequently Used Algorithm: LFU)
물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수가 가장 적은 페이지를 교체 시킬 페이지를 결정하는 알고리즘이다. LFU 알고리즘은 크게 2가지로 나뉜다.
- Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
- Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식
Perfect-LFU의 경우 정확하게 참조 횟수를 참조할 수 있지만 시간에 따른 참조의 변화를 반영하지 못하고, 구현이 복잡하다는 단점이 있다.
11번째로 5번째 참조를 하려고 하면 페이지 폴트가 발생한다. 이 때 LRU 알고리즘은 1번 페이지 프레임을 교체하게 된다. 이에 반해 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지 프레임을 교체하게 된다.
1번 페이지가 오랫동안 쓰이지 않았지만 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지를 교체했다. 그러나 앞으로 4번 페이지가 계속 사용되는 페이지일수도 있다.
위의 설명처럼 LFU는 최신 흐름을 잘 반영하지 못한다.
✔︎ 클럭 알고리즘 (Not Used Recently: NUR, Not Recently Used: NRU)
클럭 알고리즘은 하드웨어적인 차원을 통해 기존(LRU, LFU) 알고리즘의 소프트웨어적인 웅영 오버헤드를 줄인 방식이다.
클럭 알고리즘은 LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.
클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.
- 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
- 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.
- 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체한다.
즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘이다.
클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘이라고 부르기도 한다.
⭐️ 페이지 교체 알고리즘에 따른 페이지 폴트 방식
OPT : 최적 교체. 앞으로 가장 오랫동안 사용하지 않을 페이지 교체 (실현 가능성 희박)
FIFO : 메모리가 할당된 순서대로 페이지를 교체
LRU : 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
LFU : 사용 빈도가 가장 적은 페이지를 교체
NUR or NRU : 최근에 사용하지 않은 페이지를 교체
출처
Tech Interview for developer
혼자 공부하는 컴퓨터 구조 + 운영체제
https://zangzangs.tistory.com/143
