[운영체제] 14-3 페이지 교체와 프레임 할당

이 글을 혼자 공부하는 컴퓨터구조 + 운영체제 (한빛미디어) 책을 읽고 혼자 공부한 내용입니다.
잘못 이해한 부분이 있을 수 있고, 문제가 있는 부분 댓글로 알려주시면 수정하겠습니다.

 

요구 페이징

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법

 

기본적인 양상

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

 

순수 요구 페이징

아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행 가능

이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트 계속 발생,

실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어짐

---

페이지 교체 알고리즘

페이지 폴트를 가장 적게 일으키는 알고리즘이 좋은 알고리즘

 

페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있고,

페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미

 

2 2 2 3 5 5 5 3 3 7 <- CPU가 접근한 순서

2 3 5 3 7 <- 페이지 참조열

 

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

중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않아서임

 

FIFO 페이지 교체 알고리즘

• 가장 단순한 방법
• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식

 

2차 기회 페이지 교체 알고리즘

• FIFO의 변형
• 참조 비트가 1일 경우, 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정
• 0일 경우 이 페이지는 가장 오래된 페이지이면서 동시에 사용되지 않은 페이지라고 보아 보조기억장치로 내보냄

 

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려
• 가장 낮은 페이지 폴트율을 보장하는 알고리즘
• 실제 구현은 어려움, 앞으로 오랫동안 사용되지 않을 페이지를 예측하긴 어렵기 때문

 

LRU 페이지 교체 알고리즘

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
• 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체

---

스래싱과 프레임 할당

근본적으로 프레임이 부족하면 CPU는 페이지 폴트가 자주 발생할 수 밖에 없음

 

스래싱은 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제

-> 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제

 

동시에 실행되는 프로세스의 수(멀티프로그래밍의 정도)를 늘린다고 해서 CPU의 이용률이 그에 비례해서 증가하는 것은 아님

스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문

 

그렇기에 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 함

 

균등할당 

• 가장 단순한 형태의 프레임 할당 방식
• 모든 프로세스에 균등하게 프레임을 제공함
• 당연히 비합리적

 

비례할당

• 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스 크기가 작으면 프레임을 적게 나눠 주는 방식
• 이것도 완벽한 방식은 아님
• 막상 실행했는데 많은 프레임을 필요로 하지 않는 경우가 있기 때문

 

균등할당과 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식이라고도 함

 

작업 집합 모델

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

 

작업 집합

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

 

이 두개 방식은 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식이라고도 함

 

페이지 폴트율 기반

페이지 폴트율에 상한선과 하한선을 정하고,

그 내부 범위 안에서만 프레임을 할당하는 방식