(운영체제) 9 - 가상 메모리 관리

## 목차 ##

• 1. 요구 페이징
• 2. 페이지 교체 알고리즘
• 3. 스레싱과 프레임 할당
• 4. 프레임 관련 이슈

## 1. 요구 페이징 ##

• 요구 페이징(demand paging)
  • 프로세스가 요청할 때 해당 페이지를 메모리로 가져오는 가져오기(fetch) 정책

(1) 요구 페이징 개요

• 프로세스의 일부만 메모리에 올리는 이유

  • 메모리의 효율적 관리
  • 응답 속도 향상

• 게으른 스와퍼(lazy swapper)

  • 사용자가 요청한 페이지만 메모리로 가져오는 것
  • 페이저(pager)라고도 한다.

(2) 페이지 테이블 엔트리의 자료구조

• reserved

  • 직접 매핑일 경우는 페이지 번호가 곧 인덱스이므로 페이지 번호가 필요없다.
  • 연관 매핑의 경우 페이지 번호가 필요하다.

• access bit(접근 비트)

  • 페이지가 메모리로 스왑 인(swap in) 된 후 사용된 적이 있는지 나타내는 비트
  • 참조 비트(reference bit)라고도 한다.

• modified bit(변경 비트)

  • 페이지가 메모리로 스왑 인(swap in) 된 후 데이터 변경이 있었는지 나타내는 비트
  • 오염되었단 의미에서 dirty bit라고도 한다.

• valid bit(유효 비트)

  • 해당 페이지가 메모리에 있는지를 나타낸다.
  • present bit라고도 한다.

• protection bits(보호 비트들)

  • read(읽기), write(쓰기), 실행(execute) 비트들로 권한을 나타내는 비트들이다.

• caching bit(캐싱 비트)

  • 캐싱을 허용할지 말지 설정하는 비트

• frame number(프레임 번호)

  • 유효 비트가 0이면 페이지가 메모리에 존재하므로 프레임 번호 저장
  • 유효 비트가 1이면 스왑 영역에 있는 페이지의 주소 저장

(3) 페이지 부재

• 페이지가 스왑 영역에 있는 경우(유효 비트값 1)를 페이지 부재(page fault)라고 한다.

• 메모리에 여유공간이 있는 경우 페이지 부재 발생

  • 해당 페이지를 메모리의 빈 프레임으로 스왑 인(swap in)
  • 페이지 테이블 업데이트(유효 비트 0으로, 스왑 주소를 프레임 번호로)

• 메모리에 여유공간이 없는 경우 페이지 부재 발생

  • 교체 알고리즘에 의해 선정된 대상 페이지(victim page)를 스왑 아웃(swap out)
  • 해당 페이지 테이블 업데이트(유효 비트 1로, 프레임 번호를 스왑 주소로)
  • 요구 페이지 스왑 인(swap in)
  • 해당 페이지 테이블 업데이트(유효 비트 0으로, 스왑 주소를 프레임 번호로)

(4) 지역성

• 데이터 지역성(locality)

  • 메모리 접근 패턴은 일반적으로 전체에 골고루 퍼지지 않고 특정 영역에 집중된다.
  • 공간적 지역성, 시간적 지역성, 순차적 지역성
  • 페이지 부재 시에 지역성에 따라 앞으로 사용될 확률이 가장 낮다고 판단되는 페이지를 대상 페이지로 선정하기 위해 지역성을 사용

• 공간적 지역성

  • 현재 접근한 데이터와 가까운 데이터일수록 미래에 접근할 확률이 높다.

• 시간적 지역성

  • 최근에 접근한 데이터일수록 앞으로도 사용될 확률이 높다.

• 순차적 지역성

  • 프로그램 코드가 순차적으로 실행되는 경향
  • 공간적 지역성의 특별한 경우

## 2. 페이지 교체 알고리즘 ##

(1) 무작위 페이지 교체 알고리즘

• 무작위로 대상 페이지 선정

• 지역성을 고려하지 않기에 성능이 좋지 않다. 거의 사용되지 않는다.

(2) FIFO 페이지 교체 알고리즘

• 가장 먼저 메모리에 들어온 페이지를 대상 페이지로 선정

• 큐를 사용해서 구현

• 시간의 지역성만 고려하여 성능이 좋지 않다.

(3) 최적 페이지 교체 알고리즘

• 미래의 메모리 접근 패턴에서 가장 나중에 사용될 페이지를 대상 페이지로 선정

• 미래의 메모리 접근 패턴을 알 수 없어 이론만 존재하고 구현이 불가능

• 유사한 성능을 보이는 최적 근접 알고리즘(LRU, LFU 등)을 사용

  • 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하는 방식

(4) LRU 페이지 교체 알고리즘

• Least Recentry Used(최근 최소 사용)

• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 대상 페이지로 선정

• 페이지 테이블에 접근한 시간, 카운터, 혹은 참조 비트를 사용하여 최근 사용 페이지 기록

• 접근 기록을 위한 추가 메모리 공간 필요

• 일반적으로 성능이 FIFO보다 우수하고 최적 알고리즘보다 조금 떨어진다.

(5) LFU 페이지 교체 알고리즘

• Least Frequently Used(최소 빈도 사용)

• 메모리에 올라온 후 사용된 횟수가 가장 적은 페이지를 대상 페이지로 선정

• 사용 횟수 기록을 위한 추가 메모리 공간 필요

• 일반적으로 LRU 교체 알고리즘과 성능이 비슷하다.

(6) NUR 페이지 교체 알고리즘

• Not Used Recently(최근 미사용)

• LRU와 LFU와 성능이 비슷하면서 공간 낭비 문제를 완화한 알고리즘

  • 기록을 위해 페이지 테이블 엔트리의 접근(참조) 비트와 변경 비트 2개만 사용

• (접근비트, 변경비트)의 초기값은 (0,0)

  • 읽기, 실행이 발생하면 접근 비트는 1로 SET
  • 쓰기, 추가 같은 변경이 일어나면 변경 비트가 1로 SET
  • (0,0), (0,1), (1,0), (1,1) 우선순위로 대상 페이지로 선정

• 가장 많이 사용된다.

## 3. 스레싱과 프레임 할당 ##

(1) 스레싱의 발생

• 스레싱(thrashing)
  • 잦은 페이지 부재 발생으로 실제 CPU 사용시간보다 스와핑 시간이 커지는 현상
  • 멀티 프로그래밍 정도가 일정 수준에 도달하면 스레싱이 발생한다.

• 동시에 실행되는 여러 프로세스 각각에 프레임을 적절히 할당해야 스레싱 발생을 막을 수 있다.

(2) 정적 할당

• 프로세스 실행 초기에 프레임을 나누어준 후 그 크기를 고정

  • 균등 할당, 비례 할당

• 균등 할당

  • 프로세스 크기에 관계없이 모든 프로세스에 프레임을 동일하게 할당
  • 큰 프로세스의 경우 빈번한 페이지 부재 발생, 작은 프로세스의 경우에는 메모리 낭비

• 비례 할당

  • 프로세스 크기에 비례하여 프레임을 할당
  • 정적 할당이므로 프로세스 실행 중 필요한 프레임을 유동적으로 반영하지 못한다.
  • 필요없는 프레임을 미리 할당해놓아 메모리 낭비(요구 페이징의 경우 큰 프로세스라도 전체가 메모리에 올라오지 않는다.)

(3) 동적 할당

• 프로세스 실행 중 계속해서 변하는 요청을 수용하는 방식

  • 작업집합 모델, 페이지 부재 빈도 모델

• 작업집합(working set model) 모델

  • 지역성 이론을 바탕으로 한다.
  • 최근 액세스된 프레임은 이후에 또 액세스될 것이라 가정
  • 최근 일정 시간 동안 액세스된 프레임을 집합으로 만들고 이 집합을 물리 메모리에 유지
  • 작업 집합 윈도우 : 현재 시점에서 실행했던 페이지들을 살펴보는 폭(width)
  • 작업 집합 크기 : 작업 집합 모델에 유지할 페이지의 최대 수
  • 작업 집합 윈도우의 크기가 성능을 좌우하므로 적절한 크기로 잡아야한다.
  • 프로세스에 프레임을 얼마나 할당해야 할지는 알 수 없어 스레싱은 해결하지 못한다.

• 페이지 부재 빈도(page fault frequency) 모델
  • 페이지 부재가 상한 임계치 이상 발생 -> 더 많은 프레임 필요하다고 판단 -> 프레임 추가 할당
  • 페이지 부재 적게 발생 -> 프레임이 남아돈다고 판단 -> 할당된 프레임 회수

## 4. 프레임 관련 이슈 ##

(1) 전역교체와 지역교체

• 전역 교체

  • 모든 프로세스의 전체 프레임을 대상으로 교체 알고리즘 적용
  • 다른 프로세스의 페이지를 스왑아웃 시켜 스레싱에 빠뜨릴 수도 있다.
  • 전체 시스템 관점에서는 전역 교체가 효율적

• 지역 교체

  • 자신의 프로세스 프레임만 대상으로 교체 알고리즘 적용
  • 다른 프로세스에 영향을 미치지 않는다.
  • 자주 사용되는 페이지가 스왑 아웃되어 자신의 스레싱 발생 확률이 올라간다.