⛳ 메모리의 과할당으로 페이지를 교체해야 할 때, 페이지 교체 알고리즘이 쓰인다.
페이지 교체 알고리즘이란?
: 페이지 부재가 발생할 시, 새로운 페이지를 할당할 때 현재 할당된 페이지 중 어떤 것을 교체할 지 결정하는 방법
- 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.
여기서 어떤 페이지를 out 시켜야할 지 정해야 한다. (이때 out 되는 페이지를 victim page라고 부름)
기왕이면 수정이 되지 않는 페이지를 선택해야 좋다.
(Why? : 만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸림)
1. FIFO
: 가장 먼저 들어온 페이지를 내린다.
-
가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법임
-
초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음
하지만 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함
2. OPT(OPTimal)
: 최적의 교체 알고리즘
- 가장 오랫동안 사용되지 않을 페이지를 교체 -> 단, 예측이 힘드므로 현실적으로 불가능 ( 미래 예측)
3. LRU(Least-Recently-Used)
: 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라 생각하는 알고리즘
- 가장 많이 쓰이는 페이지 교체 알고리즘
- 구현을 위해 하드웨어가 필요할 수 있음
- Counter를 적용한 방법과 Stack을 적용한 방법이 있음
4. LFU(Least-Frequently-Used)
: 가장 적게 사용된 페이지를 새로운 페이지와 교체
5. MFU(Most-Frequently-Used)
: 가장 적게 사용된 페이지는 단순히 가장 최근에 사용된 페이지였을 가능성이 높으므로 가장 많이 사용된 페이지를 새로운 페이지와 교체
교체 범위에 따른 방식
1) Global 교체
: 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
2) Local 교체
: 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식
→ 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 함. 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적
다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음
따라서, 다양한 프로세스의 페이지가 메모리에 존재함
페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이
💥 오버헤드 이슈
: 페이지 교체가 많이 이루어지면, 입출력 연산이 많이 발생하게 되면서 오버헤드 문제가 발생함
오버헤드 해결법
방법1
변경비트를 모든 페이지마다 둬서, victim 페이지가 정해지면 해당 페이지의 비트를 확인
해당 비트가 set 상태 → 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 뜻 (즉, 페이지가 메모리 올라온 이후 한번이라도 수정이 일어났던 것. 따라서 이건 디스크에 기록해야함)
bit가 clear 상태 → 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황 (즉, 디스크와 내용이 같아서 기록할 필요가 없음)
디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대 절반으로 감소시키는 방법
방법2
페이지 교체 알고리즘을 상황에 따라 잘 선택해야 함
현재 상황에서 페이지 폴트를 발생할 확률을 최대한 줄여줄 수 있는 교체 알고리즘을 사용
