[Operating System] 가상 메모리 : 페이지 교체와 프레임 할당

가상 메모리의 페이지 교체와 프레임 할당에 대해 정리하였습니다.

참조 : 인프런 '개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제'

---

< 페이지 교체와 프레임 할당의 필요성 >

가상 메모리를 이용해 물리 메모리보다 큰 프로세스를 실행할 수 있지만, 그럼에도 물리 메모리의 크기는 한정되어 있습니다.

그러므로 
- 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고 = 페이지 교체
- 프로세스들에게 적절한 수의 프레임을 할당해야 합니다. = 프레임 할당

 

 

---

< 요구 페이징  >

처음부터 모든 페이지를 메모리에 적재하지 않고, 요구되는 페이지만을 메모리에 적재하는 기법입니다.

요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당 문제가 해결되어야 합니다.

 

[ 요구 페이징 진행 순서 ]

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현대 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴드가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.

+. 페이지 폴트 : 프로세스가 접근하려는 페이지가 물리 메모리에 없을 때 발생하는 예외로, 운영체제가 해당 페이지를 디스크에서 로드하도록 처리하는 과정입니다.

 

 

순수 요구 페이징은 아무런 페이지도 메모리에 프로그램을 실행하는 방법을 의미합니다.
메모리에 아무 페이지도 없이 때문에 매번 페이지 폴트를 통해 페이지를 로드합니다.

 

 

---

< 페이지 교체 알고리즘  >

요구 페이징 기법으로 페이지들을 적재하다보면 언젠가 메모리가 가득차기 때문에, 당장 실행에 필요한 페이지를 적재하기 위해 어떤 적재된 페이지를 보조기억장치(스왑 영역)로 내보내야 합니다.
→ 이때 어떤 페이지를 내보낼지 결정하는 방법이 페이지 교체 알고리즘입니다

페이지 폴트가 적은 알고리즘이 좋은 페이지 교체 알고리즘입니다.

 

• 페이지 참조열(page reference string) : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
  ex) 2 2 2 3 5 5 5 3 3 7 → 2 3 5 3 7

 

 

---

[ FIFO 페이지 교체 알고리즘 ]

: 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식입니다.

 

FIFO 페이지 교체 이미지

 

[ 단점 ] : 프로그램 실행 내내 사용될 페이지 또한 내쫓게 될 수가 있습니다.

 

 

---

[ 2차 기회 (second-chance) 페이지 교체 알고리즘 ]

: FIFO 페이지 교체 알고리즘 + 참조비트

- 가장 오래된 페이지의 참조 비트가 1일 경우 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정하는 방식입니다.

- 가장 오래된 페이지의 참조 비트가 0일 경우 내쫓습니다.

 

Ex)

 

: 여기서 페이지 3번은 제일 뒤로 가고 페이지 1번이 교체됩니다.

 

 

---

[ 최적 페이지 교체 알고리즘 ]

: 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘입니다.

 

최적 페이지 교체 이미지

 

[ 장점 ] : 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘입니다.

[ 단점 ] : 앞으로 사용 빈도가 가장 낮은 페이지를 예측하여 구현하기가 쉽지 않습니다.

→ 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 많이 사용됩니다.

 

 

---

[ LRU(Least-Recently-Used) 페이지 교체 알고리즘 ]

: 지금까지 사용 빈도가 가장 낮았던 페이지를 교체하는 알고리즘입니다.

 

LRU 페이지 교체 이미지

 

 

---

< 스래싱  >

페이지 폴트가 자주 발생하는 이유는 나쁜 페이지 교체 알고리즘을 사용해서 뿐만 아니라, 프로세스가 사용할 수 있는 프레임 자체가 적어서이기도 합니다.

프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 현상을 스래싱이라고 합니다.
→ 스래싱은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되기 않았기 때문에 발생합니다.

 

 

: 동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지는 것이 아닙니다.

 

 

---

< 여러 프레임 할당 방식 >

[ 균등 할당 ]

: 모든 프로세스들에게 균등하게 프레임을 할당하는 방식입니다.

 

ex) 300개의 프레임을 할당할 수 있는 시스템에서 10개의 프로세스가 동시 실행중이라면 30개씩 할당

 

[ 단점 ] : 실행되는 프로세스들의 크기는 각기 다르기 때문에 각 프로세스에게 동일한 프레임을 할당하는 것은 비합리적입니다.

 

 

---

[ 비례 할당 ]

: 프로세스 크기에 비례하여 프레임을 할당하는 방식입니다.

 

[ 단점 ] : 프로세스가 필요로 하는 프레임 수는 실행해봐야 알 수 있습니다.

(크기가 큰 프로세스가 실행 중 많은 프레임을 필요로 하지 않거나, 크기가 작은 프로세스가 실행 중 많은 프레임을 필요로 할 수 있습니다.)

 

균등 할당과 비례 할당은 프로세스의 실행 과정을 고려하지 않고 프로세스(혹은 물리메모리) 크기 같이 고정된 크기만 고려한 방식이라는 점에서 정적 할당 방식이라고도 부릅니다.

 

 

---

[ 작업 집할 모델 기반 할당 ]

: CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하는 방식입니다.

즉, '프로세스가 일정 기간 동안 참조한 페이지 집합' ( = 작업 집합)을 기억하여 작업집합의 크기만큼만 프레임을 할당하여 빈번한 페이지 교체를 방지합니다.

 

 

작업집합을 구하려면 다음 두 가지를 알아야 합니다.

1. 프로세스가 참조한 페이지

2. 시간 간격

 

Ex1)

: t1일 때 작업 집합 = { 5, 6, 7 }

 

Ex2)

: t2일 때 작업 집합 = { 1, 2, 4, 7, 8 }

 

 

---

[ 페이지 폴트 빈도 기반 할당 ]

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

 

 

다음 두 개의 가정에서 생겨난 할당 방식입니다.

1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.

2. 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있다.

 

페이지 폴트 빈도 기반 할당 이미지

 

 

작업 집할 모델 기반 할당과 페이지 폴드 빈도 기반 할당은 프로세스가 실행하는 과정에서 배분할 프레임을 결정하는 동적 할당 방식입니다.

 

 

---

"게임할 때 60프레임은 되어야지"에서 말하는 게임 프레임과 메모리 관리에서 사용하는 프레임은 다른 개념입니다.