페이지 교체와 프레임 할당

song·2023년 5월 10일

혼자 공부하는 운영체제

목록 보기

15/17

가상 메모리를 사용해서 물리 메모리 보다 큰 프로세스를 실행할 수 있지만 여전히 메모리 크기가 한정되어있다. (I'm, still hungry 🍔🍖🍜🍕)

그래서, 기존에 적재된 불필요한 페이지를 선별해서 보조기억장치로 보내고 프로세스들에게 적절한 수의 프레임을 할당해야 한다.

기존에 적재된 불필요한 페이지를 선별해서 보조기억장치로 보내고 → 페이지 교체
프로세스들에게 적절한 수의 프레임을 할당 → 프레임 할당

요구 페이징

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

요구되는 페이지만 적재

요구 페이징 과정

CPU가 특정 페이지에 접근하는 명령어 실행

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

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

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

다시 1번을 수행

📍 참고

순수 요구 페이징
1. 아무런 페이지도 메모리에 적재하지 않고 걍 실행
2. 실행할 때마다 폴트 발생 (빈 메모리로 시작하기 때문)
3. 계속 폴트가 발생하며 메모리가 쌓이고 점차 폴트 횟수가 줄어듬

요구 페이징 시스템을 안정적으로 작동하기 위해 2가지 문제를 해결해야 함

페이지 교체

프레임 할당

페이지 교체

계속 메모리에 페이지를 적재하면 필요없는 페이지를 보조기억장치에 보내야 하는데, 이때 어떤 페이지를 보낼지 결정하는 방법을 페이지 교체 알고리즘이라 함

Q. 좋은 페이지 교체 알고리즘이란?

A. 페이지 폴트가 적은 알고리즘 (페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능↓)

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

페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘
최적 페이지 교체 알고리즘
LRU (Least Recently Used) 페이지 교체 알고리즘
등등

FIFO 페이지 교체 알고리즘

가장 단순한 방식

메모리에 가장 먼저 올라온 페이지부터 교체

문제점
프로그램에서 계속 사용될 페이지도 먼저 올라왔다면 교체해버림

보완법
2차 기회 페이지 교체 알고리즘 사용 (참조 비트가 1이면 기회를 주고 0이면 교체)

최적 페이지 교체 알고리즘

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

앞으로 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘

가장 낮은 페이지 폴트율을 보장

문제점
앞으로 참조할지 안 할지 예측 어려움
즉, 실제 구현이 어려워서 다른 페이지 교체 알고리즘 성능 평가용으로 사용 (전투력 측정기임)

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

가장 오래 사용되지 않은 페이지를 교체

프레임 할당

프로세스가 사용할 수 있는 프레임이 작다면 페이지 폴트가 자주 발생한다.

(성능 낮은 페이지 교체 알고리즘을 사용하는것 보다 작은 프레임 할당이 페이지 폴트가 발생하는 근본적인 이유임)

스래싱 (Thrashing)

프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저하되는 문제

동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 계속 높아지는 것은 아님

발생 이유
각 프로세스가 필요한 최소한의 프레임 수가 보장 X
즉, 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 할당해줘야 함

프레임 할당 방식

정적 할당 방식
동적 할당 방식

정적 할당 방식

: 프로세스 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식

균등 할당

가장 단순한 할당 방식

모든 프로세스들에게 균등하게 프레임을 할당

문제점: 각기 크기가 다른데 똑같이 할당하기에 비합리적

비례 할당

프로세스의 크기를 고려

프로세스 크기에 비례하여 프레임 할당

문제점: 실제 실행해보면 크기가 크다고 프레임이 많이 필요하지 않을 수 있음
(결국 프로세스를 실행해봐야 필요한 프레임 수를 알 수 있음)

동적 할당 방식

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

작업 집합 모델 (working set)

CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당

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

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

작업 집합을 구하기 위해 2가지 필요
1. 프로세스가 참조한 페이지
2. 일정 시간 간격

페이지 폴트 빈도 (PFF: Page Fault Frequency)

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

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