메모리에 있는 페이지들 중 어떤 페이지를 보조 기억 장치로 보내야 할까?
🎈 요구 페이징
실행에 필요한 페이지만 메모리에 적재하는 기법
- CPU가 페이지에 접근하는 명령어를 실행한다
- 해당 페이지가 메모리에 있으면 (유효비트면) CPU는 프레임에 접근한다.
- 없으면 페이지 폴트가 발생한다.
- 페이지 폴트 처리 루틴으로 해당 페이지를 메모리로 보낸다.
이 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당을 해결해야 한다.
🎈 페이지 교체 알고리즘
메모리에서 쫓아낼 페이지를 결정하는 알고리즘, 페이지 폴트를 적게 일으킬수록 좋다.
먼저 페이지 폴트 횟수를 알아야 하는데, 페이지 참조열을 통해서 알 수 있다.
페이지 참조열 (page reference string)
CPU가 접근한 페이지를 순서대로 늘어놓은 문자열
연속된 중복 접근은 제외한다. 한 페이지에 여러번 연속으로 접근하면, 최초 접근 이후로 페이지 폴트는 발생하지 않기 때문이다.
🔰 FIFO 페이지 교체
오래 머무른 페이지부터 쫓아낸다.
자주 쓰이는 페이지도 쫓아내버리므로 좋은 방법은 아니다.
벨라디 이상현상
프레임 개수를 늘리면 페이지 폴트가 줄어든다고 생각하지만, FIFO에서는 오히려 늘어날 수 도 있다.
FIFO는 사용 여부를 고려하지 않고 도착 순서로만 쫓아내기 때문에 아직 한창 쓸 페이지도 먼저 들어왔다는 이유로 쫓겨나게 된다. 프레임 수가 바뀌면 쫓아내는 순서가 통째로 달라지는데, 하필 곧 다시 쓸 페이지를 더 자주 쫓아내는 배치가 되면 폴트가 늘어난다.
FIFO의 사용 무시 정책이 근본적으로 결함이며 사용 기반 (LRU)이 필요함을 나타낸다.
고전 예시 참조열 : 1 2 3 4 1 2 5 1 2 3 4 5
3 프레임 (FIFO) → 페이지 폴트 9번
4 프레임 (FIFO) → 페이지 폴트 10번
🔰 LRU 페이지 교체
안 쓰던건 앞으로도 안쓸 것
메모리에 있는 페이지들 중에서 가장 오랫동안 사용하지 않은 페이지를 보내버린다.
Clock (2차 기회) 알고리즘
LRU는 구현이 비싸다. 매 메모리 접근마다 타임스탬프를 찍거나 스택을 갱신해야 하는 것은 부담되므로, 실제 OS는 참조 비트 하나로 LRU를 근사한다.
프레임들을 시계처럼 원형으로 늘어놓고 바늘이 돌아가면서 프레임을 방문한다.
각 프레임엔 참조 비트가 있고, 하드웨어가 그 페이지를 쓸 때마다 1로 세팅한다.
참조 비트 = 0: 최근에 안 썼다는 뜻 → 교체하고 바늘 이동참조 비트 = 1: 최근에 썼으니 2차 기회 줌 → 비트를 0으로 지우고 교체 없이 바늘만 이동 → 다음 바퀴 돌아올 때까지 다시 안 쓰이면 그땐 쫓겨남
향상된 Clock : 참조 비트 + 변경 비트 를 같이 봐서, 참조 0, 변경 0 (안 쓰였고 수정도 안 된) 페이지를 우선 교체한다
🔰 최적 페이지 교체
페이지 참조열을 참고해서, 미래에 가장 오랫동안 사용하지 않을 페이지를 쫓아낸다.
가장 낮은 페이지 폴트율을 보장한다.
- 근데 미래를 어떻게 예상?
- 그래서 실제 운영체제에서는 잘 안쓴다고 한다.
- 다른 알고리즘을 평가할 때, 해당 상황에서의 최소 페이지 폴트가 얼만지 계산하기 위해 사용된다.
🎈 스래싱 (Thrashing)
페이징에 지나치게 많은 시간을 쏟게 되어 성능이 저하되는 문제
아무리 효율적인 알고리즘으로 페이지를 교체해도, 근본적으로 메모리에 프레임 수 자체가 적으면 페이지 폴트가 자주 발생하고, 페이징에 많은 시간을 쏟게 된다.
메모리가 페이지를 교체하는 동안 CPU는 그저 기다려야 한다. 프로세스를 많이 실행하면 CPU 이용율이 늘어나지만, 너무 많이 실행하면 CPU 이용율이 떨어지게 된다.
스래싱 해결을 위해서는 프로세스에 프레임 수를 충분히 할당해 줄 수 있어야 한다. 프레임 할당 방식에도 종류가 있다.
- 균등 할당
- 모든 프로세스에 프레임 개수를 똑같이 할당하는 방법
- 당연히 좋은 방법은 아닌듯 하다
- 비례 할당 (정적 할당)
- 프로세스 크기에 비례하게 프레임을 할당하는 방법
- 크기는 큰데 프레임은 별로 안쓰는 프로세스도 있다.
- 동적 할당
- 실행해보면서 결정한다.
- 작업 집합 모델을 사용하거나, 페이지 폴트 빈도를 사용한다.
🔰 작업 집합 모델 (working set model)
작업 집합
프로세스가 특정 시간 동안 참조한 페이지들의 집합
작업 집합을 메모하고, 특정 시간 동안 집중적으로 참조한 페이지의 개수 만큼만 프레임을 할당한다.
예를 들어, 7시간 동안 참조한 페이지가 [5, 5, 5, 5, 6, 6, 7] 라면,
작업 집합은 {5, 6, 7} 이 되므로 프레임을 3개 할당한다.🔰 페이지 폴트 빈도 (PFF)
페이지 폴트율이 상한선과 하한선 범위 안에 오게끔 프레임을 할당한다.
페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 할당받았다.
페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 할당받았다.
페이지 폴트율이 상한선보다 높아지면 프레임을 더 할당해주면 된다.
페이지 폴트율이 하한선보다 낮아지면 프레임을 회수한다.
