메모리에 있는 페이지들 중 어떤 페이지를 보조 기억 장치로 보내야 할까?
🎈 요구 페이징
실행에 필요한 페이지만 메모리에 적재하는 기법
- CPU가 페이지에 접근하는 명령어를 실행한다
- 해당 페이지가 메모리에 있으면 (유효비트면) CPU는 프레임에 접근한다.
- 없으면 페이지 폴트가 발생한다.
- 페이지 폴트 처리 루틴으로 해당 페이지를 메모리로 보낸다.
이 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당을 해결해야 한다.
🎈 페이지 교체 알고리즘
메모리에서 쫓아낼 페이지를 결정하는 알고리즘, 페이지 폴트를 적게 일으킬수록 좋다.
먼저 페이지 폴트 횟수를 알아야 하는데, 페이지 참조열을 통해서 알 수 있다.
페이지 참조열 (page reference string)
CPU가 접근한 페이지를 순서대로 늘어놓은 문자열
연속된 중복 접근은 제외한다. 한 페이지에 여러번 연속으로 접근하면, 최초 접근 이후로 페이지 폴트는 발생하지 않기 때문이다.
🔰 FIFO 페이지 교체
오래 머무른 페이지부터 쫓아낸다.
자주 쓰이는 페이지도 쫓아내버리므로 당연히 좋은 방법은 아니다.
🔰 최적 페이지 교체
페이지 참조열을 참고해서, 미래에 가장 오랫동안 사용하지 않을 페이지를 쫓아낸다.
가장 낮은 페이지 폴트율을 보장한다.
- 근데... 미래를 어떻게 예상?
- 그래서 실제 운영체제에서는 잘 안쓴다고 한다.
- 다른 알고리즘을 평가할 때, 해당 상황에서의 최소 페이지 폴트가 얼만지 계산하기 위해 사용된다.
🔰 LRU 페이지 교체
안 쓰던건 앞으로도 안쓸 것
메모리에 있는 페이지들 중에서 가장 오랫동안 사용하지 않은 페이지를 보내버린다.
🎈 스래싱 (Thrashing)
페이징에 지나치게 많은 시간을 쏟게 되어 성능이 저하되는 문제
아무리 효율적인 알고리즘으로 페이지를 교체해도, 근본적으로 메모리에 프레임 수 자체가 적으면 페이지 폴트가 자주 발생하고, 페이징에 많은 시간을 쏟게 된다.
메모리가 페이지를 교체하는 동안 CPU는 그저 기다려야 한다. 프로세스를 많이 실행하면 CPU 이용율이 늘어나지만, 너무 많이 실행하면 CPU 이용율이 떨어지게 된다.
스래싱 해결을 위해서는 프로세스에 프레임 수를 충분히 할당해 줄 수 있어야 한다. 프레임 할당 방식에도 종류가 있다.
- 균등 할당
- 모든 프로세스에 프레임 개수를 똑같이 할당하는 방법
- 당연히 좋은 방법은 아닌듯 하다
- 비례 할당 (정적 할당)
- 프로세스 크기에 비례하게 프레임을 할당하는 방법
- 크기는 큰데 프레임은 별로 안쓰는 프로세스도 있다.
- 동적 할당
- 실행해보면서 결정한다.
- 작업 집합 모델을 사용하거나, 페이지 폴트 빈도를 사용한다.
🔰 작업 집합 모델 (working set model)
작업 집합
프로세스가 특정 시간 동안 참조한 페이지들의 집합
작업 집합을 메모하고, 특정 시간 동안 집중적으로 참조한 페이지의 개수 만큼만 프레임을 할당한다.
예를 들어, 7시간 동안 참조한 페이지가 [5, 5, 5, 5, 6, 6, 7] 라면,
작업 집합은 {5, 6, 7} 이 되므로 프레임을 3개 할당한다.🔰 페이지 폴트 빈도 (PFF)
페이지 폴트율이 상한선과 하한선 범위 안에 오게끔 프레임을 할당한다.
페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 할당받았다.
페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 할당받았다.
페이지 폴트율이 상한선보다 높아지면 프레임을 더 할당해주면 된다.
페이지 폴트율이 하한선보다 낮아지면 프레임을 회수한다.
