7. 가상메모리

1. 요구 페이징

• 요구 페이징(demand paging) : 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 메모리에 올리지 않고 당장 사용될 페이지만을 올리는 방식
• 이를 통해 응답시간을 단축시킬 수 있고, 더 많은 프로세스를 수용할 수 있다.
• 요구 페이징 기법의 주된 효용은 프로그램이 물리적 메모리의 용량 제약을 벗어날 수 있도록 한다는 점이다.
• 요구 페이징에서는 유효-무효 비트를 두어 각 페이지가 메모리에 존재하는지 표시한다.
• 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재(page fault)가 일어났다고 말한다.
• CPU가 무효 페이지에 접근하면 MMU가 페이지 부재 트랩을 발생시킨다. 그러면 CPU의 제어권이 커널 모드로 전환되고 운영체제의 페이지 부재 처리루틴이 호출되어 다음과 같은 순서로 페이지 부재를 처리한다.
  • 해당 페이지에 대한 접근이 적법한지 먼저 체크한다. 사용하지 않는 주소 영역에 속한 페이지에 접근하거나 해당 페이지에 대한 접근 권한 위반을 했을 경우 해당 프로세스를 종료시킨다.
  • 물리적 메모리에서 비어 있는 프레임을 할당받아 그 공가넹 해당 페이지를 읽어온다. 만약 비어 있는 프레임이 없으면 기존에 메모리에 올라와 있는 페이지 중 하나를 스왑 아웃한다.
  • 이때 요청된 페이지를 디스크로부터 메모리로 적재하기까지는 오랜 시간이 소요되므로 페이지 부재를 발생시킨 프로세스는 봉쇄 상태가 된다. 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터값을 PCB에 저장한다.
  • 디스크 입출력이 완료되어 인터럽트가 발생하면 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효로 설정하고, 봉쇄되었던 프로세스를 준비 큐로 이동시킨다.
• 요구 페이지 기법의 성능에 가장 큰 영향을 끼치는 요소는 페이지 부재의 발생 빈도이다.
• 요구 페이지의 성능은 요청한 페이지를 참조하는데 걸리는 유효 접근시간으로 측정한다.
  • 유효 접근시간 = (1-P) * 메모리 접근 시간 + P * (페이지 부재 발생 처리 오버헤드 + 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드 + 요청된 페이지의 스왑 인 오버헤드 + 프로세스의 재시작 오버헤드) (P는 페이지 부재 발생비율을 의미한다.)

2. 페이지 교체

• 페이지 교체(page replacement) : 물리적 메모리에 빈 프레임이 존재하지 않을 경우 메모리에 올라와 있는 페이지 중 하나를 스왑 아웃해 빈 공간을 확보하는 작업
• 교체 알고리즘(replacement algorithm) : 페이지 교체 시 어떤 프레임에 있는 페이지를 스왑 아웃할지 결정하는 알고리즘
• 이 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다. 이를 위해서는 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 스왑 아웃해야 한다.
• 페이지 참조열(page reference string) : 참조되는 페이지들의 번호를 시간 순서에 따라 나열한 것
• 해당 번호의 페이지가 메모리에 이미 올라와 있으면 메모리에서 적중(hit)되었다고 하고, 메모리에 없는 경우에는 페이지 부재가 발생했다고 말한다.
• 최적 알고리즘(MIN, OPT) : 페이지 교체 시 물리적 메모리에 존재하는 페이지 중 가장 먼 미래에 참조될 메모리를 스왑 아웃하는 알고리즘
  • 실제 시스테에서 온라인으로 사용할 수 없는 알고리즘이므로 오프라인 알고리즘이라고 부른다.
  • 다른 알고리즘의 성능에 대한 상한선(upper bound)를 제공한다.
• 선입선출 알고리즘(FIFO) : 페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 스왑 아웃하는 알고리즘
  • FIFO의 이상현상(FIFO anomaly) : 메모리를 증가시켰음에도 불구하고 FIFO 알고리즘에서 페이지 부재가 오히려 늘어나는 상황
• LRU 알고리즘 : 페이지 교체 시 마지막 참조 시점이 가장 오래된 페이지를 스왑 아웃하는 알고리즘
• LFU 알고리즘 : 페이지 교체 시 과거에 참조 횟수가 가장 적었던 페이지를 스왑 아웃하는 알고리즘
  • 성능 향상을 위해 최저 참조 횟수를 가진 페이지가 여러 개일 경우 페이지들 중 상대적으로 더 오래전에 참조된 페이지를 스왑 아웃한다.
  • 페이지의 참조 횟수를 계산하는 방식에 따라 Incache-LFU와 Perfect-LFU로 구현할 수 있다.
    • Incache-LFU : 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식으로 스왑 아웃했다가 스왑 인한 경우 참조 횟수가 1부터 새롭게 시작된다.
    • Perfect-LFU : 메모리에 올라와 있는지 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트한다.
    • Perfect-LFU가 더 정확하지만 오버헤드가 더 크다.

• LFU 알고리즘은 LRU 알고리즘에 비해 오랜 시간 동안의 참조 기록을 반영할 수 있지만 시간에 따른 페이지 참조의 변화를 반영하지 못하고 LRU보다 구현이 복잡하다는 단점이 있다.
• 클럭 알고리즘(clock algorithm) : 하드웨어적인 지원을 통해 LRU나 LFU의 운영 오버헤드를 줄인 방식이다.
  • LRU를 근사시킨 알고리즘으로 NUR(Not Used Recently) 또는 NRU(Not Recently Used) 알고리즘으로도 불린다.
  • 오랫동안 참조되지 않은 페이지 중 하나를 교체한다. 다만 LRU와 달리 이 페이지가 참조된지 가장 오래된 페이지라는 것은 보장하지 않는다.
  • 하지만 하드웨어적인 지원으로 동작하기 때문에 LRU에 비해 페이지 관리가 훨씬 빠르고 효율적으로 이루어져 대부분의 시스템에서 페이지 교체 알고리즘으로 사용한다.
  • 클럭 알고리즘은 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조비트를 순차적으로 조사한다.
  • 참조비트(reference bit)는 각 프레임마다 하나씩 존재하고 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다. 클럭 알고리즘은 참조비트가 1인 페이지는 0으로 바꾼 후 그냥 지나가고 참조비트가 0인 페이지는 교체한다. 모든 페이지 프레임을 다 조사한 경우 첫 번쨰 페이지 프레임부터 조사 작업을 반복한다.
  • 즉, 이 알고리즘은 시계 바늘이 한 바퀴 도는 동안 한 번도 참조되지 않은 페이지인 경우 교체한다.

3. 캐싱 기법

• 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
• paging system 외에도 cache memory(CPU와 메모리 사이에 좀더 빠르게 접근할 수 있는 메모리), buffer caching(file system에서 read/write 요청을 메모리에서 빠르게 서비스하는 캐싱 기법), web caching 등 다양한 분야에서 사용한다.
• 캐시 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.
  • 그래서 buffer caching이나 web caching의 경우 O(1)에서 O(log n) 정도까지 허용한다.
  • paging system인 경우
    • page fault인 경우에만 OS가 관여한다.
    • 이때 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없고, 페이지 부재가 발생하는 경우에만 알 수 있어 O(1)인 LRU의 list 조작조차 불가능하다. 

3. 페이지 프레임의 할당

• 페이지 프레임의 할당 알고리즘은 크게 세 가지로 나눌 수 있다.
• 균등 할당(equal allocation) : 모든 프로세스에게 페이지 프레임을 균일하게 할당하는 방식
• 비례 할당(proportional allocation) : 프로세스의 크기에 비례해 페이지 프레임을 할당하는 방식
• 우선순위 할당(priority allocation) : 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당하는 방식
• 하지만 이와 같은 알고리즘만으로는 프로세스의 페이지 참조 특성을 제대로 반영하지 못할 우려가 있다.
• CPU에서 명령을 수행할 경우 일반적으로 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하므로 여러 페이지를 동시에 참조하게 된다. 따라서 프로세스를 정상적으로 수행하기 위해서는 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야 한다.
• 반복문을 실행 중인 프로세스의 경우 반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려놓는 것이 유리하다.
• 때로는 일부 프로세스에게 메모리를 할당하지 않는 방식으로 나머지 프로세스에게 최소한의 메모리 요구량을 충족시킬 수 있어야 한다.

4. 전역교체와 지역교체

• 교체할 페이지를 선정할 때 교체 대상이 될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분할 수 있다.
• 전역교체(global replacement) : 모든 페이지 프레임이 교체 대상이 될 수 있는 방법
• 지역교체(local replacement) : 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법
• 지역교체 방법은 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 하지만, 전역교체 방법은 프로세스마다 메모리를 할당하는 것이 아니라 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
• 즉, 전역교체는 교체 알고리즘을 통해 페이지를 교체할 때 어떤 프로세스의 페이지인지 신경쓰지 않아 다른 프로세스에 할당된 프레임을 빼앗아올 수 있다. 이는 프로세스별 프레임 할당량을 조절하는 또 다른 방법이 될 수 있다.
• 지역교체 방법에서는 해당 프로세스에게 할당된 프레임 내에서만 페이지를 교체할 수 있다. 즉, 교체 알고리즘을 프로세스별로 독자적으로 운영하는 경우에 해당한다.

5. 스레싱

• 스레싱(thrashing) : 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못해 페이지 부재율이 크게 상승하여 CPU 이용률이 급격히 떨어지는 현상
  • 운영체제는 CPU의 이용률이 낮을 경우 다중 프로그래밍의 정도가 낮다고 판단해 이를 높이게 된다.
  • 다중 프로그래밍의 정도(Multi-Programming Degree : MPD) : 메모리에 동시에 올라가 있는 프로세스 수
  • 그러나 MPD가 과도하게 높아지면 각 프로세스에게 할당되는 메모리 양이 지나치게 감소하고, 이로 인해 원활하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당받지 못해 페이지 부재가 빈번히 발생한다.
  • 이러한 현상이 모든 프로세스에서 발생하면 시스템은 페이지 부재를 처리하느라 매우 분주해지고 CPU의 이용률은 급속도로 떨어진다. 게다가 운영체제는 이를 메모리에 올라와 있는 프로세스 수가 적어 이러한 현상이 발생했다고 착각해 또 다른 프로세스를 메모리에 추가한다. 
  • 그 결과 프로세스는 서로의 페이지를 교체하며 스왑 인과 스왑 아웃을 지속적으로 발생시키고, CPU는 대부분의 시간에 일을 하지 않는다. 이러한 상황을 스레싱이라고 부른다.
• MPD를 적절히 조절해 CPU 이용률을 높이는 동시에 스레싱 발생을 방지하는 방법에는 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 있다.
  • 워킹셋 알고리즘(working-set algorithm) : 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘
  • 지역성 집합(locality set) : 프로세스가 집중적으로 참조하는 페이지들의 집합
  • 워킹셋(working set) : 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
  • 워킹셋 알고리즘은 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 
  • 그렇지 않은 경우 프로세스에게 할당된 페이지 프레임들을 모두 반납시키고 프로세스의 주소 공간을 스왑 아웃시킨다.
  • 워킹셋 알고리즘은 워킹셋을 구하기 위해 워킹셋 윈도우를 사용한다.
  • 특정 시각에 대한 워킹셋을 그 시각을 기준으로 일정 시간(윈도우) 동안 참조된 서로 다른 페이지들의 집합으로 정의한다. 워킹셋에 포함된 페이지들은 메모리에 유지하고 그렇지 않으면 메모리에서 쫓겨나게 된다.
  • 워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃해서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장하고, 반대의 경우 스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋을 할당한다.
  • 이를 통해 MPD를 감소 또는 증가시킴으로써 스레싱을 방지한다.
  • 윈도우의 크기가 너무 작으면 지역성 집합을 모두 수용하지 못할 수 있고, 너무 크면 MPD가 감소해 CPU 이용률이 낮아진다.
  • 워킹셋의 크기는 시간에 따라 변할 수 있다. 따라서 일종의 동적인 프레임 할당 기능까지도 수행할 수 있다.
  • 페이지 부재 빈도 알고리즘(Page Fault Frequency : PFF) : 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절하는 알고리즘
  • 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정한 상한값을 넘게 되면 이 프로세스에게 프레임을 추가 할당한다. 이때 추가로 할당할 빈 프레임이 없으면 일부 프로세스를 스왑 아웃시킨다.
  • 반면 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄인다. 
  • 이런 방식으로 메모리 내에 존재하는 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남으면 스왑 아웃되었던 프로세스에게 프레임을 할당해 MPD를 높인다.

 

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