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

[1two13]

요구 페이징

• 프로세스를 메모리에 적재할 때 필요한 페이지만 메모리에 적재하는 기법이다.

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

순수 요구 페이징 기법

• 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행하는 것이다.
• 실행에 필요한 페이지가 어느 정도 적재되기 전까지 페이지 폴트가 계속 발생한다.

요구 페이징 시스템이 안정적으로 작동하기 위한 방법 2️⃣

1. 페이지 교체
2. 프레임 할당

[1two13]

1. 페이지 교체 알고리즘

• 쫓아낼 페이지를 결정하는 방법이다.
• 페이지 폴트를 가장 적게 일으키는 알고리즘이 좋다. 페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문이다.
• 페이지 폴트 발생 횟수는 페이지 참조열을 통해 알 수 있다.
  • 페이지 참조열: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열이다. 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문에 연속된 페이지는 생략한다.

대표적인 페이지 교체 알고리즘 3️⃣

1. FIFO 페이지 교체 알고리즘

• 적재된 페이지 순서대로 교체하는 알고리즘이다.
• 단점: 프로그램 실행 초기에 적재된 페이지가 프로그램 실행 내내 사용될 내용을 포함하고 있을 수 있는데 먼저 적재되어 교체될 수 있다.
• 2차 기회 페이지 교체 알고리즘: 위의 단점을 개선한 FIFO 페이지 교체 알고리즘의 변형이다. 만약 페이지의 참조 비트가 1인 경우 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정한다.

2. 최적 페이지 교체 알고리즘

• CPU 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.
• 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다.
• 다만, 실제 구현이 어렵다. 앞으로 오랫동안 사용되지 않을 페이지를 예측하기 어렵기 때문이다.
• 그래서 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용한다. 최적 페이지 교체 알고리즘을 실행했을 때 발생하는 페이지 폴트 횟수를 하한선으로 간주하여 평가한다.

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

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다.
• 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 아이디어를 토대로 만들어졌다.

[1two13]

2. 스래싱과 프레임 할당

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

스래싱

• 지나치게 빈번한 페이지 교체(페이징)으로 인해 CPU 이용률이 낮아지는 문제이다. 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 발생한다.

프레임 할당 방식

• 균등 할당(정적 할당 방식): 모든 프로세스에 균등하게 프레임을 배분하는 방식
• 비례 할당(정적 할당 방식): 프로세스 크기에 비례하여 프레임을 배분하는 방식
• 작업 집합 모델(동적 할당 방식): 작업 집합의 크기만큼만 프레임을 할당하는 방식이다. 즉, 빈번한 페이지 교체를 방지할 수 있다.
  • 작업 집합: 실행 중인 프로세스가 일정 기간 동안 참조한 페이지 집합
• 페이지 폴트 빈도(동적 할당 방식): 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식이다.

[1two13]

✚ 작업 집합 구하는 방법

1. 프로세스가 참조한 페이지
2. 일정 시간 간격