14. 페이지 교체와 프레임 할당

🖥️ 운영체제 🖥️ 

페이징을 통해서 물리 메모리보다 큰 프로세스를 실행할 수 있지만, 그래도 물리 메모리의 크기는 한정되어 있다.

 

따라서 기존에 적재된 불필요한 페이지를 선별해서 보조기억장치로 내보내고(페이지 아웃)

프로세스들에게 적절한 수의 프레임을 할당해야 한다.

 

요구 페이징 (Demand Paging)

처음부터 모든 페이지를 적재하는 것이 아니라, 필요한 페이지만을(요구되는 페이지만) 메모리에 적재하는 기법.

 

(순수 요구 페이징_일단 실행부터 해보기_페이지 폴트가 계속 발생)

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.

2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.

3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트가 발생한다.

4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고, 유효 비트를 1로 설정한다.

5. 다시 1번을 수행한다.

 

위와 같은 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체, 프레임 할당에 유의해야 한다.

 

페이지 교체 알고리즘

요구 페이징 기법으로 페이지들을 적재하다보면 언젠가는 메모리가 가득 차게 된다.

당장 실행에 필요한 페이지를 적재하려면 기존에 적재된 페이지를 보조기억장치로 내보내야 한다.

어떤 페이지를 내보낼지 결정하는 방법이 페이지 교체 알고리즘이다.

 

무엇이 좋은 페이지 교체 알고리즘일까?

 

페이지 폴트가 적은 알고리즘.

- 페이지 폴트가 발생하면 보조기억장치에 접근해야 하기 때문에 성능 저하 문제가 발생하기 때문

 

페이지 참조열(page reference string)

- CPU가 참조하는 페이지들 중 연속된 페이지를 생략한(이후에는 페이지 폴트 발생 X) 페이지열

FIFO 페이지 교체 알고리즘

- 메모리에 먼저 적재된 페이지부터 나가는 방식.

프로그램 실행 내내 사용될 페이지는 먼저 적재되었따고 내쫓아서는 안된다.

FIFO에서는 이 케이스를 커버하지 못함.

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

-FIFO 페이지 교체 알고리즘의 보완책

 

참조 비트가 1인 경우, 바로 내쫓지 않고 적재된 시간을 현재시간으로 설정하고 맨 뒤로 보냄.

즉 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정.

 

참조 비트가 0인 경우 바로 내쫓음.

(오래 메모리에 있었음에도 CPU가 참조한 적이 없었기 때문에)

 

 

최적 페이지 교체 알고리즘

- CPU에 의해 참조되는 횟수를 고려

- 자주 사용될 페이지가 메모리에 오래 남아 있어야함.

- 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘임

- 하지만 앞으로 오랫동안 사용되지 않을 페이지를 에측하는 것이 어려움.

- so 다른 페이지 교체 알고리즘 성능 평가를 위한 척도로 간주

 

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

- 최근에 가장 오래 사용되지 않은 페이지 교체

---

페이지 폴트가 자주 발생하는 이유는?

- 나쁜 페이지 교체 알고리즘을 사용해서

- 프로세스가 사용할 수 있는 프레임 자체가 적어서

 

스래싱(Thrashing)

너무 많은 프로세스를 동시에 실행하면 스래싱이 발생함.

 

스래싱은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않으면 발생한다.

-> 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고, 프로세스들에게 적절한 프레임을 할당해줘야함.

 

프레임 할당

1. 정적 할당 방식(프로세스의 실행 과정 고려 x, 프로세스나 메모리의 크기만 고려)

 

균등 할당(equl allocation)

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

 

비례 할당(proportional allocation)

- 프로세스의 크기를 고려해서 프로세스 크기에 비례해 프레임 할당.

 

but 크기가 큰 프로세스이지만 막상 실행해보니 많은 프레임이 필요하지 않을 수도 있음.

반대로 크기가 작은 프로세스지만 막상 실행해보니 많은 프레임을 필요로 할 수도 있음.

즉 프로세스가 필요로 하는 프레임 수는 실행해봐야 알 수 있다는 것.

 

 

2. 동적 할당 방식

작업 집합 모델 (Working Set Model)

- 프로세스가 실행되는 과정에서 배분할 프레임 결정

- 스래싱 발생의 원인은 빈번한 페이지 교체였다. 따라서 CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼 프레임을 할당.

(ex 3초동안 7개의 페이지를 참조했다면, 최소 7개의 프레임을 할당해주기)

 

프로세스가 일정 기간 동안 참조한 페이지 집합을 기억해서 빈번한 페이지 교체를 방지.

작업집합: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합.

 

 

페이지 폴트 빈도

- 프로세스가 실행되는 과정에서 배분할 프레임 결정

 

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

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

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

 

 

 

 

학습 출처: https://www.youtube.com/watch?v=bls_GjX-4U8&list=PLVsNizTWUw7FCS83JhC1vflK8OcLRG0Hl