6-4] 가상메모리: 페이지 교체와 프레임 할당

요구 페이징
처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
요구되는 페이지만 적재하는 기법

이러한 요구 페이징 시스템이 안정적으로 작동하기 위해서는
- 페이지 교체
- 프레임 할당

 

---

페이지 교체 알고리즘
요구 페이징 기법으로 페이지들을 적대하다보면 메모리는 가득 차게 되고
당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 하는데
이때, 어떤 페이지를 내보낼 지 결정하는 방법(알고리즘)이 페이지 교체 알고리즘
좋은 페이지 교체 알고리즘의 기준은 페이지 폴트가 적은 알고리즘
왜냐하면 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능이 저하되기 때문

페이지 참조열(page reference string)
페이지 폴트 횟수를 알기 위한 참조열이며
CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

연속된 페이지를 생략하는 이유는 

연속된 페이지는 페이지 폴트가 발생하지 않기 때문이다

FIFO 페이지 교체 알고리즘
가장 단순한 방식이며 메모리에 가장 먼저 올라왔던 페이지부터 내쫓는 방식

단점:
프로그램 실행 초기에 잠깐 실행될 페이지를 내쫓는 것은 좋으나
프로그램 실행 내내 사용될 페이지가 먼저 적재되었다고 내쫓아서는 안됨

FIFO 페이지 교체 알고리즘 - 보완책
2차기회(second-chance) 페이지 교체 알고리즘
참조 비트 1: CPU가 한번 참조한  적이 있는 페이지
참조 비트 0: CPU가 참조한 적이 없는 페이지

예전에 적재된 페이지에서 내쫒을 페이지를 찾는 과정에서 참조 비트가 1인 경우
최근에 적재된 페이지로 이동 후 참조 비트는 0으로 초기화

최적 페이지 교체 알고리즘
CPU에 의해 참조되는 횟수를 고려
메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지

앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이며
가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘이지만
실제 구현이 어렵고 예측을 하는 것은 불가능에 가까우니
다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주

LRU(Least-Recently-Used) 페이지 교체 알고리즘
최적 페이지 교체 알고리즘은 가장 오래 사용되지 않을 페이지를 교체한다면
LRU 페이지 교체 알고리즘은 가장 오래 사용되지 않은 페이지를 교체

기타 페이지 교체 알고리즘
이외에도 많은 페이지 교체 알고리즘들이 있다
페이지 교체 알고리즘이 무엇이고
페이지 교체는 왜 해야하는지
무엇이 좋은 페이지 교체 알고리즘인지가 중요

 

---

페이지 폴트가 자주 발생하는 이유
나쁜 페이지 교체 알고리즘을 사용한 경우도 있겠지만
프로세스가 사용할 수 있는 프레임 자체가 적은 경우도 있다

스레싱
프로세스가 실행되는 시간보다 

페이징에 더 많은 시간을 소요하면 성능(CPU 이용률)이 저해된다

따라서,

아래의 그림처

동시 실행되는 프로세스의 수를 늘리면

CPU 이용률이 높아지다가

특정 시점 이후에는

페이지 폴트가 빈번하게 발생되며 CPU 이용률이 낮아지기 시작하는 구간을

스레싱이라고 한다

스레싱 발생 이유
각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고
프로세스들에게 적절한 프레임을 할당해주어야 한다

프레임 할당
- 정적할당
1) 균등 할당 (equal allocation)
가장 단순한 방식으로 모든 프로세스들에게 균등하게 프레임을 할당하는 방식

2) 비례 할당 (proportional allocation)
프로세스 크기에 비례하여 프레임 할당하는 방

크기가 큰 프로세스지만 실행해 보니 많은 프레임을 필요로 하지 않는 경우,
크기가 작은 프로세스지만 실행해보니 많은 프레임을 필요로 하는 경우가 발생할 수도 있으니
결국, 프로세스가 필요로 하는 프레임 수는 실행해 봐야 안다

- 동적할당
1) 작업 집합 모델
프로세스가 실행하는 과정에서 배분할 프레임 결정
스레싱이 발생하는 이유는 빈번한 페이지 교체 때문
따라서, CPU가 특정 시간 동안 참조한 페이지 개수만큼만 프레임을 할당하는 방식

프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지하고
작업 집합이란 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 의미한다

작업 집합을 구하기 위해서는
프로세스가 참조한 페이지와 시간 간격을 가지고 알아낼 수 있다

2) 페이지 폴트 빈도
프로세스가 실행하는 과정에서 배분할 프레임을 결정
두 개의 가정에서 생겨난 아이디어이다
1_ 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다
2_ 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다

페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식