가상 메모리

가상 메모리(virtual memory)

• 운영체제는 어떤 방식으로 프로세스에게 메모리를 할당하는가?
• 시분할 시스템 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어 사용하고 보통 몇몇 프로그램들에게 집중적으로 메모리를 할당하고 회수하는 방식을 채택한다.
• 프로세스의 빠른 수행을 위해 프로그램마다 최소한 확보해야 하는 메모리의 크기가 존재하기 때문이다.
• 기본적으로 당장 필요하지 않은 부분은 디스크의 스왑 영역에 내려놓았다가 사용하기 때문에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약이 없다고 봐도 된다. 운영체제는 더 나아가 프로그램이 물리적 메모리를 고려할 필요 없이 자기 자신만이 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원한다.
• 프로그램은 0번지 부터 시작하는 자기 자신만의 메모리 주소 공간인 가상 메모리를 가정할 수 있다. 필요시 가상메모리의 일부만이 스왑영역에서 메모리에 swap in 하여 사용하게 된다.
• 프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 가상메모리 기법은 요구 페이징 방식과 요구 세그먼테이션 방식으로 구현될 수 있다.

요구 페이징(demand paging)

• 프로그램 실행시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식을 말한다.
• 특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재한다.
• 당장 실행할 페이지만을 메모리에 적재하기 때문에 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 올리는 데 소요되는 입출력 오버헤드도 줄어든다.
• 프로그램을 구성하는 페이지 중 사용하는 일부만을 메모리에 적재하므로 물리적 메모리의 용량보다 큰 프로그램도 실행할 수 있게 된다.
• 특정 프로세스를 구성하는 페이지 중에서 메모리에 존재하는지 여부를 구별하기 위하여 유효-무효 비트를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다.
• 요구페이징의 부재 처리
  • CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효 비트가 무효로 세팅되어 있는 경우 페이지 부재(page fault)가 일어났다고 말한다.
  • CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 MMU가 페이지 부재 트랩(trap)을 발생시킨다.
• 요구 페이징의 성능
  • 성능에 가장 큰 영향을 미치는 요소는 페이지 부재의 발생 빈도이다.
  • 페이지 부재가 일어나면 요청된 페이지를 디스크로부터 메모리로 읽어오는 막대한 오버헤드가 발생한다.
• 페이지 교체
  • 페이지 부재가 발생해서 요청된 페이지를 디스크에서 메모리로 읽어와야 할 때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
  • 이 경우에는 메모리에 올라와 있는 페이지 중 하나를 swap out 하여 빈 공간을 확보하는 페이지 교체작업이 필요하다.
  • 어떠한 프레임에 있는 페이지를 swap out 할지 결정하는 알고리즘인 교체 알고리즘의 목표는 페이지 부재율을 최소화하는 것이다.
  • 어떻게 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택하여 swap out 시킬 수 있을까?
    • 최적 페이지 교체 알고리즘
      • 가장 먼 미래에 참조될 페이지를 swap out
      • 발레디의 최적 알고리즘
      • 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 알고리즘을 운영하기 때문에 현실에 적용할 수는 없는 오프라인 알고리즘으로 다른 알고리즘의 성능에 대한 상한선을 제공한다.
    • 선입선출 알고리즘
      • 페이지 교체시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 swap out
      • 교체 대상 페이지가 계속해서 많은 참조가 이루어지면서 메모리 공간이 늘어나도 성능이 나빠지는 FIFO 이상현상(FIFO anomaly)이 발생할 수 있다.
    • LRU 알고리즘(Least Recently Used)
      • 페이지 교체시 마지막 참조 시점이 가장 오래된 페이지를 swap out
      • 메모리 페이지의 참조 성향 중 시간지역성을 반영
      • 시간지역성이란 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
    • LFU 알고리즘(Least Frequently Used)
      • 페이지의 참조 횟수가 가장 적었던 페이지를 swap out
      • LRU 알고리즘 보다 오랜 시간 동안 참조기록을 반영할 수 있다는 장점이 있지만 LFU 알고리즘은 시간에 따른 페이지 참조의 변화를 반영하지 못한다.
      • Incache-LFU
        • 페이지가 물리적 메모리에 올라온 후부터의 참조 횟수를 카운트하는 방식
        • 페이지가 메모리에서 쫓겨났다가 다시 들어온 경우 참조 횟수는 초기화됨
      • Perfect-LFU
        • 메모리에 올라와있는지의 여부와 상관없이 그 페이지의 과거 총 참조 횟수를 카운트하는 방식
        • 오버헤드가 상대적으로 크다.
    • 클럭 알고리즘
      • 클럭 알고리즘은 오랫동안 참조되지 않은 페이지 중 하나를 교체한다.
      • 클럭 알고리즘은 하드웨어적인 지원을 통해 참조시각 및 참조 횟수를 비교하고 유지하여 오버헤드를 줄인 방식이다.
      • 각 프레임마다 참조 비트가 하나씩 존재하며 그 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
      • 교체할 페이지를 선정하기 위해 페이지 프레임들의 참조 비트를 순차적으로 조사하여 참조 비트가 1인페이지는 0으로 바꾼 후 지나가고 참조비트가 0인 페이지는 교체한다. 모든 페이지 프레임을 다 조사한 경우 첫 번째 페이지 프레임부터 조사작업을 반복한다.
      • 시곗바늘이 한바퀴 돌아오는 동안에 다시 참조되지 않을 경우 페이지는 교체된다.
      • 적어도 시곗바늘이 한 바퀴를 도는데 소요되는 시간만큼 페이지를 메모리에 유지시켜 둠으로써 페이지 부재율을 줄이도록 설계되었기 때문에 2차 기회 알고리즘이라고도 부른다.
  • 페이지 프레임의 할당
    • 프로세스 여러 개가 동시에 수행되는 상황에서 각 프로세스에 얼마만큼의 메모리 공간을 할당할 것인가?
      • 프로세스를 정상적으로 수행하기 위해서는 적어도 일정 수준 이상의 페이지 프레임을 각 프로세스에 할당해야한다.
        • CPU에서 명령을 실행할 때에는 일반적으로 여러 페이지를 동시에 참조하게 된다. 명령을 실행할 때 프로세스의 주소 공간 중 코드, 데이터, 스택 등 각기 다른 영역을 참조하기 때문이다.
        • 반복문을 구성하는 페이지도 한꺼번에 메모리에 올려야 페이지 부재가 발생하지 않는다.
    • 할당 방식
      • 균등 할당
        • 모든 프로세스에게 페이지 프레임을 균일하게 할당한다.
      • 비례 할당
        • 프로세스의 크기에 비례해 페이지 프레임을 할당한다.
      • 우선순위 할당
        • 프로세스의 우선순위에 따라 페이지 프레임을 다르게 할당한다.
  • 전역 교체와 지역 교체
    • 전역 교체
      • 모든 페이지 프레임이 교체 대상이 될 수 있다.
      • 전체 메모리를 각 프로세스가 공유해서 사용하고 교체 알고리즘에 근거해서 할당되는 메모리 양이 가변적으로 변하는 방법이다.
      • 교체되는 페이지가 어떤 프로세스에 속한 것인지 고려하지 않기 때문에 교체 시 다른 프로세스에 할당된 프레임을 빼앗아올 수 있다. 결과적으로 프로세스별 프레임 할당량을 조절할 수 있게 된다.
      • LRU, LFU 클럭 등의 알고리즘을 물리적 메모리 내에 존재하는 전체 페이지 프레임들을 대상으로 적용하는 경우를 말한다.
      • 워킹 셋 알고리즘
      • PFF 알고리즘
    • 지역 교체
      • 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있다.
      • 프로세스마다 페이지 프레임을 미리 할당하는 것을 전제로 한다.
      • 프로세스별로 페이지 프레임을 할당하고, 교체할 페이지도 그 프로세스에게 할당된 프레임 내에서 선정하게 된다.
      • LRU, LFU 등의 알고리즘을 프로세스별로 독자적으로 운영하는 경우를 말한다.
  • 스레싱(thrashing)
    • 스레싱 현상이란 집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 않아서 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어지는 것을 말한다.
    • 메모리에 동시에 올라가 있는 프로세스의 수를 다중 프로그래밍의 정도 (Multi-Programming Degree, MPD)라고 부른다.
    • 운영체제는 CPU 이용률이 낮을 경우 추가로 프로세스를 메모리에 올려서 MPD를 높인다. 그러나 어느 정도 MPD 이상일 경우 페이지 부재가 발생하는 빈도가 높아지면서 CPU 이용률이 다시 낮아지고 운영체제가 착각하여 다시 MPD를 높이는 악순환이 발생한다.
    • 그러므로 스레싱을 발생하지 않도록 하면서 CPU 이용률을 최대한 높일 수 있도록 MPD를 조절하는 것이 중요하다.
    • 워킹셋 알고리즘
      • 프로세스는 일정시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다.
      • 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set)이라고 한다.
      • 워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘이다.
      • 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 프로세스에게 메모리를 할당한다.
      • 그렇지 않을 경우 프로세스에게 할당된 페이지 프레임을 모두 반납 후 swap out 시킨다.
    • 페이지 부재 알고리즘
      • 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.
      • 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한 값을 넘게 되면 이 프로세스에 할당된 프레임 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 더 할당한다.
      • 이때 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 swap out 시켜서 메모리에 올라가 있는 프로세스의 수를 조절한다.
      • 반대로 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄이고 추가로 swap out 되어있던 프로세스에게 프레임을 할당함으로써 MPD를 높인다.