[운영체제와 정보기술의 원리] 8장 가상 메모리

가상 메모리란?

프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다.

 

1. 요구 페이징

• 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식

1) 요구 페이징의 페이지 부재 처리

• CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩(page fault trap)을 발생시키게 된다
• 그러면 CPU의 제어권이 커널모드로 전환되고, 운영체제의 페이지 부재 처리루틴(page fault handler)이 호출되어 다음과 같은 순서로 페이지 부재를 처리한다. 
• 해당 페이지에 대한 접근이 적법한 경우 물리적 메모리에서 비어 있는 프레임(free frame)을 할당받아 그 공간에 해당 페이지를 읽어온다
• 만약 비어 있는 프레임이 없다면 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아낸다(swap out)

2) 요구 페이징의 성능

• 유효 접근시간이 짧을수록 요구 페이징 기법의 성능은 향상된다

 

2. 페이지 교체

• 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다
• 이때 물리적 메모리에 빈 프레임이 존재하지 않을 경우 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하는 작업이 필요하고 이것을 페이지 교체(page replacement)라고 한다. 

1) 최적 페이지 교체

빌레디의 최적 알고리즘(Belady's optimal algorithm)

• 페이지 부재율을 최소화하기 위해 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내는 알고리즘
• 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하기 때문에 실제 시스템에서 온라인으로 사용할 수는 없다
• 다만, 이 알고리즘은 성능에 대한 상한선(upper bound)을 제공한다

2) 선입선출 알고리즘(First In First Out: FIFO)

• 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다
• FIFO의 이상 현상(FIFO anomaly): FIFO 알고리즘에서 메모리를 증가시켰음에도 불구하고 페이지 부재가 오히려 늘어나는 상황

3) LRU 알고리즘(Least Recently Used)

• 시간지역성(temporal locality): 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
• 시간지역성을 이용해 페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 쫓아낸다

4) LFU 알고리즘(Least Frequently Used)

• 물리적 메모리 내에 존재하는 페이지 중에서 과거에 참조 횟수(reference count)가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재한다
• Incache-LFU: 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식
• Perfect-LFU: 메모리에 올라와있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트하는 방식

5) 클럭 알고리즘(Clock)

• 페이지 참조 시각 및 참조 횟수를 소프트웨어적으로 유지하고 비교해야 하는 LRU, LFU와 달리 하드웨어적인 지원을 통해 알고리즘의 운영 오버헤드를 줄인 방식
• NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘이라고도 불린다
• 페이지 프레임들의 참조비트를 순차적으로 조사하면서 0인 페이지를 교체한다

 

3. 페이지 프레임 할당

할당 알고리즘(allocation algorithm)

• 균등할당(equal allocation): 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 방식
• 비례할당(proportional allocation): 프로세스의 크기를 고려한 균등할당 방식
• 우선순위할당(priority allocation): 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 방식

 

4. 전역교체와 지역교체

교체할 페이지를 선정할 떄, 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분한다.

• 전역교체(global replacement)
  • 모든 페이지 프레임이 교체 대상이 될 수 있는 방법
• 지역교체(local replacement)
  • 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법

 

5. 스레싱(thrashing)

스레싱이란? 

집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못해 페이지 부재율(page fault rate)이 상승하고 CPU 이용률(CPU utilization)이 떨어지는 현상

 

MPD(multi-programming degree): 메모리에 동시에 올라가 있는 프로세스의 수

 

MPD를 적절히 조절해 CPU 이용률을 높이는 동시에 스레싱 발생을 방지하는 방법

• 워킹셋 알고리즘(working-set algorithm)
  • 집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set)이라고 한다
  • 워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘을 말한다
• 페이지 부재 빈도 알고리즘(page-fault frequency scheme)
  • 페이지의 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다