운영체제 10장 가상메모리 페이지 교체 알고리즘

가상 메모리

• 물리 메모리의 한계를 극복하기 위한 기술

Demanding Paging

백업 공간을 두고 프로세스가 요구하는 필요한 페이지만 메모리 위에 올리는 것이다. 백업 공간과 메모리 사이의 스와핑이 발생하기 때문에 페이지 부재 시 지연이 발생한다.

Prepaging

미리 사용될 것 같은 페이지를 메모리에 올려두는 방식이다. 그러나 페이지 부재가 발생할 때 많은 지연이 발생하게 된다.

Page Fault

페이지 부재는 CPU가 접근하려는 페이지가 메모리 위에 없는 경우이다.

처리 과정

1. 해당 페이지 확인
2. valid bit==0이면 cpu에 인터럽트 신호를 보내고 내부의 해당 ISR(인터럽트 서비스 루틴)- 인터럽트 핸들러가 관리하는 인터럽트 발생시 행동 루틴 - 로 간다.
3. 디스크를 탐색해 페이지를 찾는다.
4. 페이지의 비어있는 곳에 프로세스를 할당한다.
5. 테이블에서 해당 valid bit를 1로 변경
6. ISR을 종료하고 프로세스 실행

페이지 교체 알고리즘

---

FIFO

먼저 들어온 페이지를 먼저 내보내는 알고리즘이다.

Optimal

가장 오랫동안 사용되지 않을 페이지를 교체 페이지로 선택한다. 그러나 사용되지 않을 페이지를 선택하는 과정이 합리적이지 않을 수 있다.

LRU

최근에 사용하지 않는 것을 교체하는 알고리즘으로 과거에 페이지 기록을 통해 구한다. 현재 가장 많이 사용하는 알고리즘

프레임 할당

---

1. 글로벌 교체 - 메모리 상의 모든 프로세스에 대한 페이지를 교체
2. 지역 교체 - 메모리 상에서 해당 프로세스 페이지에 대해서만 교체

• 메모리 사용 효율은 글로벌 교체 방식이 더 좋다.

쓰레싱

메모리에 할당된 프로세스가 올라갈수록 CPU 이용률이 올라갈 것이라고 생각하지만 일정 구간을 넘어 서게 되면 효율이 감소해 이용률이 감소한다. 프로세스가 증가할수록 메모리의 빈 프레임 개수가 줄어들어 디스크와 메모리 사이의 스와핑이 계속 해서 발생하기 때문에 cpu에 많은 무리가 가게 된다. 이 현상을 쓰레싱이라고 한다.

해결 방법

1. 지역 교체를 사용하는 것이다. 메모리 사용 효율은 떨어진다.
2. 프로세스 당 적절한 메모리를 할당해준다.

정적 할당

1. 동일 할당 - 프로세스에게 같은 프레임을 할당하는 것이다.
2. 비례 할당 - 프로세스 크기에 따른 할당. 크기에 따라 사용률이 증가하진 않아서 비효율적이다.

정적 할당

1. Working set이란 현재 시간에서 일정 시간 이전 사이에 사용된 페이지의 집합이다. 따라서 많이 참조하는 페이지를 계싼해서 프레임을 할당한다.
2. Page fault frequency - 페이지 부재율은 프로세스 할당 프레임 수에 반비례한다. 할당 프레임수가 적을수록 부재가 늘어난다. 상한선과 하한선을 설정해 프레임을 할당한다.

성능 향상을 위해 고려해야 할 페이지 크기 할당

내부 단편화, 페이지 스와핑, 테이블 크기, 메모리 해상도, 페이지 부재 확률, 지역성 등을 고려한다.

커널에서의 페이지 할당

커널은 메모리와는 다르게 연속적인 공간할당이 되어야 효율적이다.

1. 버디 시스템 - 2의 지수승 크기로 할당한다. (내부 단편화가 줄어들때까지)
2. 슬랩 할당