페이지 교체 & 프레임 할당
페이징에서 페이지 교체, 프레임 할당을 어떻게 하는지 알아보자.
요구 페이징 demand paging
: 필요한 페이지만을 메모리에 적재하는 기법
- CPU가 특정 페이지에 접근하는 명령어를 실행
- 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근
- 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정
- 1을 수행
순수 요구 페이징 pure demand paging
: 아무런 페이지도 메모리에 적재하지 않은 채 실행하는 기법
실행하는 순간부터 페이지 폴트가 계속 발생하고 어느 정도 페이지가 적재된 이후부터 발생 빈도가 떨어진다.
페이징 시스템이 작동하려면 페이지 교체와 프레임 할당이 해결되어야 한다.
페이지 교체 알고리즘
좋은 알고리즘 == 페이지 폴트를 적게 일으키는 알고리즘
페이지 폴트가 일어나면 보조기억장치에서 필요한 페이지를 가져와야 하기 때문임.
페이지 교체 알고리즘을 이해하려면 페이지 폴트 횟수를 알 수 있어야 한다.
페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있다.
CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다.
아래와 같은 순서로 CPU가 페이지에 접근했다 치자.
연속된 페이지를 생략한 페이지열, 아래 숫자열이 페이지 참조열임.
중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않는다.
FIFO 페이지 교체 알고리즘
말 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫒는 방식임.
프로그램 전반에 사용될 페이지를 내쫒을수 있음.
2차 기회 페이지 교체 알고리즘
FIFO 페이지 교체 알고리즘의 보완책임.
참조 비트를 이용해 한 번더 기회를 주는 알고리즘이다.
페이지의 참조 비트가 1일 경우 참조 비트를 0으로 만든 뒤 최근에 적재된 페이지로 간주한다.
이 상황에서 페이지 6이 적재되어야 한다 치자.
기존 FIFO 알고리즘이었으면 페이지 3이 내쫓아질 것이다.
하지만 2차 기회 알고리즘은 페이지 3의 참조 비트를 0으로 바꾼 뒤 페이지 1을 내쫓는다.
페이지 1이 적재되었던 프레임에 페이지 6을 적재하면 된다.
최적 페이지 교체 알고리즘
CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘이다.
즉 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.
가장 낮은 페이지 폴트율을 보장하는 알고리즘이다.
구현이 매우 어렵기 때문에 운영체제에서 사용하기보다 다른 알고리즘의 이론상 성능을 평가하는 도구로 쓴다.
LRU 페이지 교체 알고리즘
가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다.
사용되지 않을 페이지를 교체하는 것과는 다르게 어렵지만 구현 가능하다.
스래싱과 프레임 할당
프레임이 부족하면 CPU는 페이지 폴트가 자주 발생한다.
페이지 교체에 너무 많은 시간이 걸리면 성능에도 큰 악영향이 초래된다.
이처럼 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱 thrashing이라고 한다.
메모리에서 동시 실행되는 프로세스의 수를 멀티프로그래밍의 정도라고 한다.
스래싱이 발생하는 근본적인 원인: 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
이를 위해 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.
- 균등 할당: 가장 단순한 할당 방식으로 모든 프로세스들에게 균등하게 프레임을 할당하는 방식이다.
- 비례 할당: 프로세스의 크기에 비례하여 프레임을 할당하는 방식이다.
균등 할당과 비례 할당은 정적 할당 방식(프로세스와 물리 메모리의 크기만 고려)이다.
하나의 프로세스가 필요로 하는 프레임의 수는 실행해 봐야 안다.
작업 집합 모델 working set model
프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지한다.
참조 지역성의 원리와 비슷하다.
실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합 working set이라고 한다.
CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해 주면 된다.
페이지 폴트 빈도 PFF; Page-Fault Frequency
:페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식이다.
- 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
- 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
