Chapter 9: 가상 메모리의 관리

Page Fault Frequency (residence bit = 0)가 높을 수록 가상메모리의 장점이 줄어든다.

→ 커널의 개입을 통한 디스크와의 입출력을 요구 (프로세스 대기)

 

9.1 하드웨어의 사용

mapping에 걸리는 시간을 최소화 = 가상메모리의 성능 UP

추가 비용을 들여 하드웨어를 장착(ex. TLB)

 

📌 페이지를 관리하기 위한 정보

• 참조 비트 : 해당 페이지가 변경 없이 단순 참조
• 갱신 비트 : 해당 페이지의 내용 변경

 

9.2 관리 기법

적재 정책

 실행에 필요한 페이지를 언제 적재할지 결정하는 정책

1. 요구 적재(Demanding Fetch)
   • 페이지가 참조될 때 적재하는 기법
   • 장점 : 메모리에 관한 오버헤드가 없음
   • 단점 : 적재될 때까지 해당 프로세스를 대기로 만드는 문맥교환과 디스크 입출력 부담
2. 예측 적재(Anticipatory Fetch)
   • Prepaging(선페이징)이라고도 함
   • 장점 : 예측이 잘 될 경우에는 페이지 부재 빈도 줄임
   • 단점 : 예측을 위한 오버헤드, 참조되지 않는 페이지 적재 메모리 낭비

 

배치 정책

페이징에서는 페이지와 프레임의 크기가 같아서 신경쓰지 않는다.

세그먼테이션 사용 경우 세그먼트의 크기가 다르므로 세그먼트 수용할 수 있는 배치 정책 사용

• fit기법 사용(7.5)

 

할당 정책

프로세스에게 메모리를 얼마큼씩 줄 것인지 결정하는 정책

고정 할당 (Fixed Allocation)	가변 할당(Variable Allocation)
고정된 프레임의 개수를 준다	실행중 프로세스에게 부여된 프레임의 수가 달라짐
지역 교체 (Local replacement)	전역 교체 (Global replacement)
할당된 프레임 중 교체될 프레임 선택	메모리의 모든 프레임중 교체될 프레임 선택 고정할당 사용 불가능

 

교체 정책

메모리에 빈프레임이 없을 때 적재될 페이지를 위해 교체해야함.

어떤 페이지를 선택할지 결정하는 정책

1. 최적 기법 (Optimal , Min)
   • 미래에 참조될 때까지 시간이 가장 긴페이지를 선택 후 교체
     • 미래에 참조를 모름 → 현실적으로 구현 불가능
   • 성능 비교용 모델
     
     
2. FIFO기법
   • 적재된지 가장 오래된 페이지(가장 먼저 적재된 페이지)를 교체
   • 시간기록(Time Stamping기법)
   • 큐를 사용 - 교체 대상이 큐의 맨 앞(헤드포인터) 유지
   • 장점 : 교체대상을 바로 알 수 있다
   • 단점 : 큐 내의 페이지들이 적정 위치에 있도록 자리를 잡아주는데 오버헤드가 발생한다.
   • page fault
     • 자주 일어남 = 충분한 프레임이 할당 X, 충분한 메모리 X
     • BUT, 프레임을 더 주면 부재율이 올라가는 현상 : FIFO 모순(Belady’s Anomaly)
       
       
3. LRU(Least Recently Used) 기법
   • 참조된지 가장 오래된 페이지
   • 구현 방법
     • Time stamping (오버헤드 감수해야함)
     • LRU스택 사용 (스택의 bottom이 교체대상)
   • 미래는 알 수 없지만, 최근 참조된 것이 당분간 자주 참조한다는 판단
     
     
4. Second Chance 기법
   • FIFO의 변형, LRU 근접하는 기법
   • 적재된지 가장 오래된 페이지 교체, 적재 후 참조된 적 있으면 한번 더 남음
   • 참조비트를 사용한다.
   • 구현
     • 순환 큐 사용 → clock기법
     • 참조비트가 1이면 순환큐를 따라 다음 포인터로 이동한다.
       
       
5. 개선된 Second Chance 기법(NUR [Not Used Recently]기법)
   • clock기법 + 갱신비트
   • 적재 중 변경된 경우 가급적 교체를 미뤄 디스크 쓰기 작업 줄인다.
   • 구현
     1. 포인터를 이동하며 참조비트와 갱신비트 모두 0인 페이지 교체 (없으면 2)
     2. 포인터를 이동하며 참조 0 갱신 1 페이지 교체 (교체 후 모든 프레임의 참조비트는 0)
     3. 1,2를 반복한다.
   • NUR기법
     • 참조비트를 시스템에서 주기적으로 0으로 만들어준다.
       
       
6. LFU(Least Frequently Used) MFU(Most Frequently Used)
   • 현실 가능성이 매우 떨어짐
   • 적재되어있는 동안 참조된 횟수를 누적 기록후 그 값으로 교체 선택
   • LFU : 많이 참조된 페이지는 계속 참조된다 → 값이 가장 작은 페이지 교체
   • MFU : 많이 참조된 페이지는 더이상 참조 안된다 → 값이 가장 큰 페이지 교체
     
     
7. 페이지 버퍼링 기법
   • 적재 가용 프레임으로 풀을 유지
   • fault → 메모리에 올리는 페이지를 풀에 넣는다.
   • 교체 대상 → 디스크로가고 풀에 넣는다.
   • 장점: 빠른 응답, 실제 교체 응답시간 줄여줌, 페이지 재참조시 시간 줄여줌
   • delayed frame, delayed write

 

📌 지역성과 스레싱 (Locality & Thrashing)

Locality: 시간대별로 일부 명령 or 프로그램 특정 부분이 집중적으로 실행되는 현상

Thrashing: 참조될 페이지의 반복적 교체가 과도한 페이지 부재야기 → 시스템의 성능 ↓

 

Working set 이론과 PFF

working set: 프로세스가 특정 시점에서 집중적으로 참조하는 페이지들의 집합

→ 페이지의 부재를 최소화하기 위함

• 단점 : 매 페이지를 참조할 때 마다 working set 조정해야해서 오버헤드 부담

윈도사이즈 = 일정 크기의 시간

PFF: working set을 페이지 부재의 간격에 근거하여 결정하는 방법

• 부재가 없을 경우에 working set 조정안함 오버헤드 부담이 적음

fault 많음 → 프레임이 많다 → 페이지 회수
적정 fault 간격
fault 적음 → 프레임이 적다 → 페이지 추가

 

클리닝 정책(Cleaning Strategy)과 부하 조절(Load Control)

클리닝: 적재 중 내용이 변경된 페이지를 언제 디스크에 기록할까?

 

요구 클리닝

• 교체 대상으로 선택되었을 때
• 응답성 떨어짐

 

예측 클리닝

• 디스크 부하전이면 미리 기록
• 기록후 교체전 변경이면 낭비

 

부하조절 : 다중 프로그래밍의 degree를 결정하는 것

• 정도 낮으면 성능 떨어짐
• 정도 높으면 스래싱(메모리부족)
• L=S 법칙, 50% rule