9. 가상 메모리

0. 서론

8장의 모든 내용은 운영체제가 별도로 관여하지만, 이 장의 내용은 전적으로 운영체제가 관여

• 주소 바인딩은 하드웨어가 전담

 

1. 요구 페이징 (Demand Paging)

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

• 페이징에서도 스와핑을 사용할 수 있음
• 하나의 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지는 보조기억장치에 남겨둘 수 있음

 

장점

• 당장 필요한 페이지만 적재하기 때문에 메모리 사용량 감소
• 프로세스 전체를 메모리에 올리는데 소요되는 입출력 오버헤드 감소
• 메모리가 더 많은 프로세스를 수용할 수 있으므로 응답시간 감소
• 프로그램이 물리 메모리의 용량 제약을 벗어날 수 있음

 

2. 페이지 폴트 (Page Fault)

 

CPU가 메모리에 적재되어있지 않은 (유효 비트가 0인) 페이지로 접근하는 상황

• MMU가 Page Fault Trap을 발생시킴

 

페이지 폴트 처리 과정

• 1. 해당 페이지에 대한 접근이 올바른지 확인
  → 잘못된 접근이라면 해당 프로세스를 Abort시킴
• 2. 메모리에 비어있는 프레임을 하나 할당받음
  → 비어있는 프레임이 없다면 메모리에 적재된 페이지 중 하나를 Swap Out시킴
• 3. 해당 페이지를 디스크에서 메모리로 읽어옴
  → 디스크 I/O가 끝나기까지 해당 프로세스는 Blocked 상태가 됨
  → 디스크 I/O가 끝나면 페이지 테이블에서 해당 페이지의 유효 비트를 1로 설정
  → Ready Queue에 프로세스를 삽입

 

어떤 페이지를 Swap Out할 것인가?

• 어떤 페이지를 Swap Out할 것인지 결정하기 위한 알고리즘이 필요
• 해당 알고리즘은 Page Fault Rate를 최소화하는 것이 목표
• 다양한 페이지 교체 알고리즘 등장

 

3. Optimal Algorithm

 

가장 낮은 Page Fault Rate를 보장하는 페이지 교체 알고리즘

• 앞으로 가장 오랫동안 참조되지 않을 페이지를 Swap Out
• 타 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용됨 (미래를 예측하는 것은 현실적으로 불가능)

 

4. FIFO Algorithm

 

메모리에 가장 먼저 올라온 페이지를 Swap Out하는 페이지 교체 알고리즘

 

 

Belady's Anomaly

• 일반적으로 프레임의 개수가 늘어날수록 페이지 폴트 발생 횟수가 감소하지만, FIFO Algorithm의 경우 오히려 증가하는 모순이 존재

 

5. LRU (Least Recently Used) Algorithm & LFU (Least Frequently Used) Algorithm

 

LRU Algorithm: 가장 오랫동안 사용되지 않은 페이지를 Swap Out하는 페이지 교체 알고리즘

 

 

LFU Algorithm: 누적 참조 횟수가 가장 적은 페이지를 Swap Out하는 페이지 교체 알고리즘

• 최저 참조 횟수를 가진 페이지가 여러 개 존재 시 LRU 알고리즘을 따르도록 구현하는 것이 효율적
• 페이지가 메모리에 적재될 때부터의 참조 횟수를 세는 Incache-LFU 방식과 과거의 총참조 횟수를 세는 Perfect-LFU 방식이 존재 (위 예시의 경우 두 방식의 결과가 같음)

 

LRU Algorithm, LFU Algorithm의 구현

 

• LRU Algorithm
  → Double Linked List를 통한 구현
  → 특정 페이지가 참조되었을 때 갱신을 위한 시간복잡도가 O(1)
• LFU Algorithm
  → Min Heap을 통한 구현
  → 특정 페이지가 참조되었을 때 갱신을 위한 시간복잡도가 O(log N)

 

6. 캐싱 (Caching) 

한정된 빠른 공간 (캐시)에 요청된 데이터를 저장해두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식

• 페이지 교체 알고리즘의 "어떤 페이지를 Swap Out 할 것인가"는 곧 "어떤 페이지를 캐싱할 것인가"와 같음
• 캐싱은 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용
• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용 불가

 

페이징 시스템에서 LRU Algorithm, LFU Algorithm은 채택될 수 있는가?

• 운영체제는 페이지 폴트가 발생했을 때만 관여
  
• 특정 페이지가 이미 메모리에 적재된 상황에서 해당 페이지가 참조될 경우 페이지 폴트가 발생하지 않음
• 이때 CPU의 제어권이 운영체제에 넘어가지 않으므로 운영체제는 해당 페이지의 참조 시각 및 참조 횟수 등을 알 수 없음
• 즉, 자료구조에 대한 조작 자체가 불가능하므로 페이징 시스템에서 채택될 수 없음
  → 또한 두 알고리즘은 페이지 참조 시각 및 참조 횟수 등을 소프트웨어적으로 유지 및 비교해야 하므로 오버헤드가 발생
  → Clock Algorithm 등장

 

7. Clock Algorithm

 

하드웨어적 지원을 통해 기존 알고리즘 (LRU, LFU)의 소프트웨어적 오버헤드를 줄인 페이지 교체 알고리즘

• LRU의 근사 알고리즘, NRU (Not Recently Used) 알고리즘 등으로 불림
  → 간단히 말해, 시곗바늘이 한 바퀴 도는 동안 다시 참조되지 않은 페이지를 교체하는 알고리즘
  → 대부분의 시스템에서 페이지 교체 알고리즘으로 채택
• 참조 비트를 사용해서 Swap Out 대상 페이지를 선정
  → 페이지 테이블의 비트는 운영체제가 아닌 MMU가 설정
  → 그러므로 기존 알고리즘에 비해 페이지 관리가 빠르고 효율적
  → 참조 비트값이 0인 경우 : 해당 페이지를 Swap Out
  → 참조 비트값이 1인 경우 : 참조 비트값을 0으로 바꾸고 시계 방향으로 포인터 이동
• 참조 비트와 수정 비트를 함께 사용할 수 있음
  → 수정 비트값이 1인 경우 최근에 변경된 페이지임을 의미하므로 보조기억장치에 Write가 필요
  → 속도 개선을 위해 참조 비트값이 0이면서 수정 비트값이 0인 페이지를 Swap Out하는 방식 등을 사용 가능

 

8. 프레임 할당 & 전역 교체 & 지역 교체

각 프로세스에 얼마만큼의 프레임을 할당할 것인가?

• 명령어 수행 중 Page Fault Rate를 감소시키기 위해 최소한 할당되어야 하는 프레임의 수가 존재
  → 예) 하나의 루프를 구성하는 페이지의 경우 한꺼번에 할당되는 것이 유리
• 세 가지 방법이 존재
  → Equal Allocation (균등 할당) : 모든 프로세스에 똑같은 개수의 프레임 할당
  → Proportional Allocation (비례 할당) : 프로세스 크기에 비례하여 프레임 할당
  → Priority Allocation (우선순위 할당) : 프로세스의 우선순위에 따라 프레임 할당

 

Global Replacement

• 메모리상의 모든 프로세스의 페이지에 대해 교체 작업을 수행
• 예) FIFO, LRU, LFU 알고리즘 등을 메모리에 적재된 모든 페이지에 대해 전역적으로 운영
• 예) Working-Set Algorithm, PFF Algorithm

 

Local Replacement

• 메모리상의 본인 프로세스의 페이지에 대해 교체 작업을 수행
• 예) FIFO, LRU, LFU 알고리즘 등을 각 프로세스별로 운영

 

9. 스레싱 (Thrashing)

 

Page Fault Rate가 상승해 CPU Utilization이 급격히 감소하는 현상

• 프로세스의 원활한 수행에 필요한 최소한의 프레임 수를 할당받지 못한 경우 발생

 

발생 과정

• 1. Page Fault Rate 증가
• 2. CPU Utilization 감소
• 3. 운영체제는 MPD (Multi-Programming Degree)를 높여야 한다고 판단
• 4. 다른 프로세스가 시스템에 추가됨
• 5. 프로세스 당 할당된 프레임의 수가 더욱 감소
• 6. 페이지 폴트가 더 빈번히 발생 → Page Fault Rate 증가
• 7. 프로세스가 페이지 Swap In / Swap Out으로 바쁘므로 대부분의 시간에 CPU는 한가함 → CPU Utilization 감소

 

해결

• 스레싱이 발생하지 않도록 하면서 CPU Utilization을 최대한 높일 수 있도록 MPD를 조절
  → 예) Working-Set Algorithm, PFF Algorithm

 

10. Working-Set Algorithm

Locality of Reference (참조 지역성의 원리)

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조
• 집중적으로 참조되는 해당 페이지들의 집합을 Locality Set이라고 함

Working-Set Algorithm

 

• Locality of Reference에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 Working Set이라고 정의함
• Working Set이 한 번에 메모리에 적재될 수 있는 경우에만 해당 프로세스에 메모리를 할당
• 불가능할 경우 프로세스는 모든 프레임을 반납한 후 Swap Out되어 Suspended 상태가 됨
• 궁극적으로 MPD를 조절하고 스레싱을 방지
• 메모리에 적재된 프로세스들의 Working Set 크기의 합이 할당된 프레임의 수보다 큰 경우
  → 일부 프로세스를 Swap Out시켜 남은 프로세스의 Working Set이 메모리에 모두 적재되는 것을 보장 (MPD 감소)
• 메모리에 적재된 프로세스들의 Working Set을 전부 할당하고도 프레임이 남는 경우
  → Swap Out되었던 프로세스 중 Working Set을 한 번에 메모리에 적재할 수 있는 프로세스를 다시 Swap In (MPD 증가)
• Window Size Δ
  → 작을 경우 : Locality Set을 모두 수용하지 못하는 문제 발생
  → 클 경우 : MPD가 감소해 CPU Utilization이 감소하는 문제 발생

 

11. PFF (Page Fault Frequency) Algorithm

Page Fault Rate의 상한값과 하한값을 설정

• Page Fault Rate가 상한값을 넘으면 한 프로세스에 대한 프레임 할당 수를 증가시킴
• Page Fault Rate가 하한값을 넘으면 한 프로세스에 대한 프레임 할당 수를 감소시킴
• 빈 프레임이 없을 경우 일부 프로세스를 Swap Out (MPD 감소)
• 프레임이 남는 경우 일부 프로세스를 Swap In (MPD 증가)

 

12. 페이지 사이즈의 결정

페이지의 크기가 감소한다면?

• 페이지 수 증가
• 페이지 테이블 크기 증가
• 내부 단편화 감소
• 디스크 탐색의 효율성 감소 (한 번의 탐색으로 많이 가져올수록 유리하므로)
• 장기적으로 Page Fault Rate 감소 (메모리에 필요한 데이터와 불필요한 데이터가 함께 적재되는 비율이 줄어드므로)
• Locality의 측면에서 불리함

페이지의 크기를 증가시키는 것이 일반적으로 유리함

 

이화여자대학교 반효경 교수님의 운영체제 강의를 정리한 글입니다.

http://www.kocw.net/home/cview.do?cid=3646706b4347ef09

운영체제

 

또한 반효경 교수님의 "운영체제와 정보기술의 원리" 책을 참고하였습니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=238716482

운영체제와 정보기술의 원리